Beschreibung

Kursinformationen: In vielen Bereichen der Informatik wie Robotik, Computergrafik, virtuelle Realität und geografische Informationssysteme müssen räumliche Daten gespeichert, analysiert und erstellt oder bearbeitet werden. Dieser Kurs befasst sich mit den algorithmischen Aspekten dieser Aufgaben: Wir untersuchen Techniken und Konzepte, die für den Entwurf und die Analyse geometrischer Algorithmen und Datenstrukturen erforderlich sind. Jede Technik und jedes Konzept wird anhand eines Problems veranschaulicht, das in einem der oben genannten Anwendungsbereiche auftritt.

Ziele:
Am Ende dieses Kurses sollten die Teilnehmer in der Lage sein
- zu entscheiden, welcher Algorithmus oder welche Datenstruktur verwendet werden soll, um ein bestimmtes geometrisches Grundproblem zu lösen;
- neue Probleme zu analysieren und mithilfe von Konzepten und Techniken aus dem Kurs eigene effiziente Lösungen zu finden.

Voraussetzungen:
Um diesen Kurs erfolgreich absolvieren zu können, sollten Sie bereits über Grundkenntnisse in Algorithmen und Mathematik verfügen. Hier ist eine kurze Liste dessen, was Sie wissen sollten:
- O-Notation, Ω-Notation, Θ-Notation; wie man Algorithmen analysiert
- Grundrechnung: Manipulieren von Summationen, Lösen von Wiederholungen, Arbeiten mit Logarithmen usw.
- Grundlegende Wahrscheinlichkeitstheorie: Ereignisse, Wahrscheinlichkeitsverteilungen, Zufallsvariablen, Erwartungswerte usw.
- Grundlegende Datenstrukturen: verknüpfte Listen, binäre Suchbäume usw.
- Graph Terminologie
- Programmierkenntnisse für praktische Aufgaben

Das meiste Material in diesem Kurs basiert auf dem folgenden Buch:
M. de Berg, O. Cheong, M. van Kreveld und M. Overmars. Computational Geometry: Algorithmen und Anwendungen (3. Auflage). Springer-Verlag, 2008.
Es ist nicht zwingend erforderlich, dieses Buch zu kaufen. Wenn die Teilnehmer jedoch mehr wissen möchten, als in diesem Kurs angeboten wird, oder sich das in den Vorlesungen behandelte Material noch einmal ansehen möchten, empfehlen wir den Kauf dieses Buches.

Die Videovorträge enthalten einige sehr kleine Fehler. Eine Liste dieser Fehler finden Sie unter Ressourcen. Wenn Sie glauben, einen Fehler gefunden zu haben, melden Sie ein Problem, indem Sie auf die quadratische Flagge unten in der Vorlesung oder im Quiz klicken, in der Sie den Fehler gefunden haben.

Preis: Kostenlos anmelden!

Geometrische Algorithmen - EIT Digital