Seitenleiste
Grundlagen der algorithmischen Geometrie
BA-INF114 (WS 2018/2019)
Termine
| Art | Wann | Wo | Beginn | LP | Dozent und Übungsleitung |
|---|---|---|---|---|---|
| V4 | Donnerstag 12:00-13:30 | CP1-HSZ Hörsaal 4 | 11. Okt. | 5,5 | Dr. Herman Haverkort Prof. Dr. Anne Driemel |
| Montag 12:00-13:30 | CP1-HSZ Hörsaal 7 | 15. Okt. | |||
| Ü2 | Mittwoch 12:00-13:30 | CP1-HSZ Seminarraum 3 | 17. Okt. | 3,5 |
Achtung: die Vorlesungen und Übungen fangen um 12:00 an (das steht nicht ganz korrekt in Basis).
Information
Wenn Sie wichtige Mitteilungen über diese Vorlesung gerne über E-Mail erhalten, bitte senden Sie eine Nachricht an haverkort@uni-bonn.de, oder registrieren Sie sich während der Vorlesung.
Prüfung
Die Prüfung ist mündlich. Termine sind verfügbar zwischen 9:00 und 12:00 Uhr am Di 5. Feb., Mi 6. Feb., und Do 7. Feb. (für den 1. Termin), und am Di 26. März, und Mi 27. März (für den 2. Termin). Bitte kontaktieren Sie Antje Bertram um einen Termin zu vereinbaren. Die Prüfungen finden statt im Institut für Informatik im Raum 2.012.
Inhalte
Wie bestimmt man in einer Menge von Punkten am schnellsten zu jedem Punkt seinen nächsten Nachbarn? Wie lässt sich der Durchschnitt von zwei Polygonen effizient berechnen? Wie findet man ein Ziel in unbekannter Umgebung? Mit diesen und vielen anderen Fragen beschäftigt sich die Algorithmische Geometrie. Wir betrachten Probleme, die einen realen Anwendungshintergrund besitzen und dabei auch aus theoretischer Perspektive reizvoll sind.
Diese Bachelor-Vorlesung ist für alle Studenten geeignet, die die Algorithmen und Berechnungskomplexität I gehört haben, es ist aber auch möglich dieser Veranstaltung ohne diese Vorbereitung zu folgen.
Skript/Literatur
Die Vorlesung basiert im Grunde vollständig auf dem Buch Algorithmische Geometrie von Rolf Klein. Kleinere Ausnahmen von dieser Regel werden in der Vorlesung entsprechend gekennzeichnet. Als ergänzende Literatur eignet sich außerdem Computational Geometry von Mark de Berg, Otfried Cheong, Marc van Kreveld und Mark Overmars (3. Ausgabe).
In den Vorlesungen bzw. den darauffolgenden Übungen wurden/werden bis jetzt die folgenden Abschnitte besprochen:
| Do | 11.10. | 1.1, 2.2, 2.3.1 |
| Mo | 15.10. | 1.2.4, 1.2.5, 2.3.2 (untere Schranke) |
| Do | 18.10. | 2.3.2 (Algorithmus) |
| Mo | 22.10. | 2.3.3 |
| Do | 25.10. | 2.3.4 (Entscheidung leer/nicht-leer) |
| Mo | 29.10. | 2.3.4 (Durchschnitt) |
| Do | 1.11. | keine Vorlesung (Feiertag) |
| Mo | 5.11. | 2.4, 3.1, 3.3.2 (Speicher, Abfragen) |
| Do | 8.11. | 3.3.2 (Konstruktion), 3.2 |
| Mo | 12.11. | 3.3.2 (Entfernen), 3.3.1 |
| Do | 15.11. | 1.2.3, 4.1.1, 4.1.2 (Algorithmus) |
| Mo | 19.11. | 1.2.3, 4.1.2 (Analyse) |
| Do | 22.11. | 4.1.4; Graham Scan für KH in 2D (notes); untere Schranke (notes) |
| Mo | 26.11. | Kleinster umschließender Kreis (Abschnitt 4.7 in De Berg et al.) (slides) |
| Do | 29.11. | Klein, Abschn. 4.2; der in der Vorlesung vorgestellte Triangulierungsalgorithmus wird beschrieben (um 90 grad gedreht) in diesem Paper, Abschn. 1-3; eine ähnliche Lösung findet man in De Berg et al., Abschn. 3.2-3.3 |
| Mo | 3.12. | Klein, Abschn. 5.1-5.3 |
| Mi | 5.12. | keine Übung (Dies) |
| Do | 6.12. | Klein, Abschn. 1.2.2, 5.4 |
| Mo | 10.12. | Klein, Abschn. 6.2 |
| Do | 13.12. | Klein, Abschn. 1.2.2, 6.4 |
| Mo | 17.12. | keine Vorlesung |
| Mi | 19.12. | keine Übung |
| Do | 20.12. | keine Vorlesung |
| Vom 22.12. bis zum 6.1. keine Vorlesungen und keine Übungen (Weihnachtsferien) | ||
| Mo | 7.1. | Klein, Abschn. 6.3 |
| Do | 10.1. | Klein, Abschn. 5.5.2, 5.5.3 |
| Mo | 14.1. | Klein, Abschn. 4.3 (bis einschl. 4.3.1) und 4.4 (bis einschl. Lemma 4.22) |
| Do | 17.1. | Klein, Abschn. 7.1, 7.2 (Theorem 7.7) |
| Mo | 21.1. | Klein, Abschn. 7.2 (Bug-Strategie), 7.3 (außer Theorem 7.11) (voraussichtlich) |
| Do | 24.1. | Klein, Abschn. 7.3.2, 4.3.3, 5.3.1, 5.3.3 (Theorem 5.11) (voraussichtlich) |
| Mo | 28.1. | keine Vorlesung |
| Do | 31.1. | keine Vorlesung |
Übungen
Begleitend zur Vorlesung gibt es wöchentliche Übungszettel. Die Lösungen werden in ebenfalls wöchentlichen Übungen besprochen. Bearbeiten der Übungsaufgaben und Teilnahme an den Übungen ist zwar freiwillig aber in höchstem Maße empfohlen, da die Übungen die Vorlesung vertiefen und dadurch auf die Prüfung vorbereiten.
Übungszettel
Hier werden wöchentlich Übungszettel hochgeladen. Die erste Übung (in der 2. Vorlesungswoche) findet mit einem Präsenzzettel statt.
- Übungszettel 1 (Besprechung: 24.10.)
- Übungszettel 2 (Besprechung: 31.10.)
- Übungszettel 3 (Besprechung: 07.11.)
- Übungszettel 4 (Besprechung: 14.11.)
- Übungszettel 5 (Besprechung: 21.11.)
- Übungszettel 6 (Besprechung: 28.11.)
- Übungszettel 7 (Besprechung: 12.12.)
- Übungszettel 8 (Besprechung: 09.01.)
- Übungszettel 9 (Besprechung: 16.01.)
- Übungszettel 10 (Besprechung: 23.01.)
lehre/ws1819/algorithmische-geometrie.txt · Zuletzt geändert: 2019/01/30 11:12 von driemel