Sidebar
BA-INF 114 : Grundlagen der Algorithmischen Geometrie
Vorlesungszeiten (SS 2022)
| Was | Wann | Wo | Beginn | Umfang | Dozent/Tutor |
|---|---|---|---|---|---|
| Vorlesung | Di 12:15-13:45 Do 10:15-11:45 | HS 7, Hörsaalzentrum Campus Poppelsdorf | 5. April | 4 SWS | Anne Driemel |
| Übung | Mittwoch 10:15-11:45 Mittwoch 12:15-13:45 | SR 2.050, INF / B-IT (Seminarraum) | 6. April | 2 SWS | Frederik Brüning Dorian Reineccius |
Aktuelle Hinweise:
- Die Vorlesungen am Di 3. Mai und Do 5. Mai müssen wegen Krankheit leider ausfallen.
- Die Übungstermine am Mi 18. Mai müssen wegen dem Dies Academicus ausfallen. Als Ersatztermin wird es eine Übung am Mo 16. Mai um 16-18 Uhr im SR 2.050 geben.
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 bestimmt man eine kleinste Anzahl von Standpunkten in einer Kunstgalerie, von denen aus insgesamt alle Kunstwerke sichtbar sind? 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 gibt eine Einführung in algorithmische Techniken wie Sweep, Divide-and-Conquer, randomisierte inkrementelle Konstruktion, Dynamisierung, amortisierte Kostenanalyse und kompetitive Analyse. Wir werden wichtige geometrische Strukturen wie konvexe Hülle, Voronoi-Diagramm und Delaunay-Triangulation sowie höherdimensionale Datenstrukturen behandeln.
Die 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.
Literatur
- Rolf Klein. Algorithmische Geometrie, 2. Auflage. Springer
- Rolf Klein, Anne Driemel, Herman Haverkort. Algorithmische Geometrie, 3. Auflage. Springer (wird in Auszügen zur Verfügung gestellt) Inhalt der neuen Ausgabe
Übungszettel
Begleitend zur Vorlesung werden wöchentlich Übungsaufgaben veröffentlicht. Diese sollen dazu dienen, die Inhalte der Vorlesung zu vertiefen. Die erfolgreiche Bearbeitung der Aufgaben ist für die Zulassung zur Prüfung erforderlich (mind. 50% der Punkte). Abgabe der Lösungen erfolgt immer Montags. Zusätzlich werden in den Übungen Präsenzaufgaben bearbeitet.
eCampus
Kursmaterialen und Übungszettel werden über die entsprechende Seite im eCampus bereitgestellt.
Prüfung
Das Modul wird mit einer mündlichen Prüfung abgeschlossen (Zulassungsvoraussetzungen sind mind. 50% der Übungspunkte). Mehr Informationen zu den Prüfungsmodalitäten und Terminen werden zeitnah auf eCampus veröffentlicht.