BA-INF 114 : Grundlagen der Algorithmischen Geometrie

Vorlesungszeiten (SS 2023)

Was Wann Wo Beginn Umfang Dozent/Tutor
Vorlesung Di 12:15-13:45
Do 10:15-11:45
HS 7, Hörsaalzentrum Campus Poppelsdorf* 11. April 4 SWS Herman Haverkort
Übung Mi 14:15-15:45
Mi 16:15-17:45
SR 2.050, INF / B-IT (Seminarraum) 19. April 2 SWS Jacobus Conradi

* Die Vorlesung am 6. Juli findet abweichend im Institut für Informatik, Raum 0.016 statt.

Aktuelle Hinweise:

  • Wir fangen nach Ostern an. Es gibt keine Vorlesungen am 4. und 6. April.

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

Ü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). 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.


Page Tools