186.122 Algorithmic Geometry
Diese Lehrveranstaltung ist in allen zugeordneten Curricula Teil der STEOP.
Diese Lehrveranstaltung ist in mindestens einem zugeordneten Curriculum Teil der STEOP.

2020W, VU, 2.0h, 3.0EC
TUWEL

Merkmale

  • Semesterwochenstunden: 2.0
  • ECTS: 3.0
  • Typ: VU Vorlesung mit Übung
  • Format der Abhaltung: Distance Learning

Lernergebnisse

Nach positiver Absolvierung der Lehrveranstaltung sind Studierende in der Lage

  • grundlegende Konzepte, Strukturen und Problemdefinitionen der Algorithmischen Geometrie zu erklären. 
  • die vorgestellten Algorithmen zu erklären, zu bewerten und zu analysieren
  • für verwandte Problemstellungen angemessene Algorithmen und Datenstrukturen auszuwählen und anzupassen
  • unbekannte angewandte und theoretische geometrische Probleme eigenständig zu modellieren, zu analysieren, effiziente Lösungen zu entwerfen und diese ggf. zu implementieren 

Inhalt der Lehrveranstaltung

Räumliche Daten werden in den unterschiedlichsten Bereichen der Informatik verarbeitet, z.B. in Computergrafik und Visualisierung, in geographischen Informationssystemen, in der Robotik usw. Die algorithmische Geometrie beschäftigt sich mit dem Entwurf und der Analyse geometrischer Algorithmen und Datenstrukturen. In diesem Modul werden häufig verwendete Techniken und Konzepte der algorithmischen Geometrie vorgestellt und anhand ausgewählter und anwendungsbezogener Fragestellungen vertieft. Konkrete Vorlesungsthemen sind Algorithmen und Datenstrukturen für:

  • konvexe Hülle
  • Linienschnitte
  • Polygontriangulierung
  • Bereichsabfragen
  • Punktlokalisierung
  • Voronoi-Diagramme und Delaunay-Triangulierungen
  • Dualität von Punkten und Geraden
  • Quadtrees
  • Well-Separated Pair Decomposition
  • Sichtbarkeitsgraphen

Methoden

  • Definition, Entwurf und Analyse von Algorithmen und Datenstrukturen, Diskussion und formale Beweise algorithmischer und geometrischer Eigenschaften, Beispiele
  • Gemeinsames und eigenständiges Bearbeiten und Lösen von Übungsbeispielen
  • Diskussion von Übungsbeispielen und Beweisideen in (virtuellen) Lern- und Übungsgruppen
  • Vorlesungsinhalte werden als Videoaufzeichnung wöchentlich bereitgestellt und regelmäßig in live-Diskussionen besprochen

Prüfungsmodus

Prüfungsimmanent

Weitere Informationen

Distance Learning

Die LVA findet im "distance learning" Betrieb statt. Es werden wöchentlich Lehrvideos bereitgestellt, die jederzeit angeschaut werden können. Es gibt im Übungsteil mehrere Übungszettel, die gelöst und abgegeben werden. Daneben wird es etwa alle 2-3 Wochen eine live-Einheit zur Vertiefung des Stoffes geben (Termine Dienstags von 9:00-11:00 Uhr). Weitere elektronische Lernangebote sind Quizzes und betreute Diskussionforen in TUWEL.

Die erste Einheit am 6.10.2020 findet live von 9:00-11:00 Uhr in Zoom statt. Der Link wird rechtzeitig an alle angemeldeten TeilnehmerInnen bekannt gegeben.

 

ECTS-Breakdown

25 h Besuch von Vorlesung und Übung
30 h Nachbereitung der Vorlesung und Vorbereitung der Übungen
19.5 h Prüfungsvorbereitung
0.5 h Mündliche Prüfung
------
75 h gesamt 

Allgemeine und organisatorische Fragen bitte an alggeom@ac.tuwien.ac.at.

Vortragende

Institut

LVA Termine

TagZeitDatumOrtBeschreibung
Di.09:00 - 11:0006.10.2020 Zoom MeetingEinführungsvorlesung
Di.09:00 - 11:0020.10.2020 - 01.12.2020 Zoom MeetingLive Webinar
Di.09:00 - 11:0027.10.2020 - 24.11.2020 Zoom MeetingExercise Session
Di.09:00 - 11:0015.12.2020 Zoom MeetingExercise Session
Algorithmic Geometry - Einzeltermine
TagDatumZeitOrtBeschreibung
Di.06.10.202009:00 - 11:00 Zoom MeetingEinführungsvorlesung
Di.20.10.202009:00 - 11:00 Zoom MeetingLive Webinar
Di.27.10.202009:00 - 11:00 Zoom MeetingExercise Session
Di.03.11.202009:00 - 11:00 Zoom MeetingLive Webinar
Di.10.11.202009:00 - 11:00 Zoom MeetingExercise Session
Di.17.11.202009:00 - 11:00 Zoom MeetingLive Webinar
Di.24.11.202009:00 - 11:00 Zoom MeetingExercise Session
Di.01.12.202009:00 - 11:00 Zoom MeetingLive Webinar
Di.15.12.202009:00 - 11:00 Zoom MeetingExercise Session

Leistungsnachweis

  • Lösen und Abgeben von Übungszetteln mit Theorieaufgaben
  • Implementierung von Algorithmen (optional)
  • Präsentation und Diskussion des Lehrinhaltes in einer mündlichen Prüfung

Die mündliche Prüfung zählt zu 70% der Note, der Übungsteil zu 30%.

Prüfungen

TagZeitDatumOrtPrüfungsmodusAnmeldefristAnmeldungPrüfung
Di. - 22.12.2020mündlich24.11.2020 12:00 - 17.12.2020 23:59in TISSAlgorithmic Geometry Oral Exam
Di. - 19.01.2021mündlich24.11.2020 12:00 - 14.01.2021 23:59in TISSAlgorithmic Geometry Oral Exam
Di. - 23.02.2021mündlich24.11.2020 12:00 - 18.02.2021 23:59in TISSAlgorithmic Geometry Oral Exam

LVA-Anmeldung

Von Bis Abmeldung bis
03.09.2020 00:00 09.10.2020 00:00 20.10.2020 00:00

Gruppen-Anmeldung

GruppeAnmeldung VonBis
Group 106.10.2020 08:0014.10.2020 23:59

Curricula

Literatur

Vortragsfolien bzw. Artikel zu bestimmten Themen werden in der Vorlesung kostenlos verteilt und/oder zum Download angeboten.

Empfohlene Literatur:

M. de Berg, O. Cheong, M. van Kreveld, M. Overmars:
Computational Geometry Algorithms and Applications, Springer 2008.

D. Mount:
CMSC 754 Computational Geometry Lecture Notes, U. Maryland 2014.

Vorkenntnisse

Grundkenntnisse in Entwurf und Analyse von Algorithmen

Vorlesungsfolien und Videos werden zur Verfügung gestellt

Sprache

Englisch