Kopf
Department of Computer Science
Chair of Algorithm Engineering (Ls11)
Home Contact Deutsch English
menu-en

 

Algorithmische Geometrie

Die Vorlesung Algorithmische Geometrie (4V+2Ü) wird im Sommersemester 2007 von Prof. Dr. Jan Vahrenhold angeboten. Die Übungen zur Vorlesung werden ebenfalls durch den Dozenten betreut.

Das Vorlesungsverzeichnis enthält die Belegnummern und offiziellen Kommentare zu Vorlesung und Übungen.

 


Zeit und Ort

  • Vorlesung: Montag/Dienstag, 10:15-11:50 Uhr (mit 5 min. Pause).
  • Ort: Seminarraum 304, OH-14.
  • Beginn: Montag, 02. April 2007, 10:15 Uhr.
  • Übungen: Zweistündig, nach Vereinbarung (s.u.).
  • Ort: Raum U-08, OH-16(!).

 


Zuordnung

Die Veranstaltung ist im Hauptstudium des Diplom- und des Lehramtsstudiengang "Informatik" anrechenbar. Durch den Prüfungsausschuss wurden folgenden Zuordnungen gnehmigt:

  • Diplom-Studiengang "Informatik" (DPO'01), Schwerpunktgebiet 4 (Algorithmen, Komplexität und formale Modelle).
  • Lehramtsstudiengang "Informatik" (LPO'94), Bereich A1 (Komplexitätstheorie) bzw. Bereich C2 (Graphentheorie/Kombinatorik).

Studierende, die nach anderen Studien- bzw. Prüfungsordnungen studieren, mögen sich bei Zuordnungsfragen bitte persönlich bei mir melden. Danke!

 


Aktuelle Informationen

Bitte beachten Sie, dass die nachfolgenden Informationen noch vorläufig sind und ggfs. in der ersten Vorlesungswoche aktualisiert werden können.

  • (08.07.2007) Die Unterlagen zu Kapitel 06 sind vervollständigt worden.
  • (01.07.2007) Die Unterlagen zu Kapitel 05 sind vervollständigt worden.
  • (26.06.2007) Als Klausurtermin wurde Montag, 13.08.2007, 10:00-11:30 Uhr, vereinbart. Die Klausur findet in Raum R. 202, OH-14, statt.
  • (25.06.2007) Die Unterlagen zu Kapitel 04 sind vervollständigt worden.
  • (18.06.2007) Die Unterlagen zu Kapitel 04 sind ergänzt worden.
  • (05.06.2007) Die Unterlagen zu Kapitel 03 sind vervollständigt worden.
  • (28.05.2007) Die Unterlagen zu Kapitel 03 sind ergänzt worden.
  • (19.05.2007) Die Unterlagen zu Kapitel 02 sind vervollständigt worden.
  • (06.05.2007) Die Unterlagen zu Kapitel 02 sind erweitert worden.
  • (30.04.2007) Die Übung am 02.05.2007 fällt (wie in der Vorlesung besprochen) aus.
  • (08.04.2007) Die Unterlagen zu Kapitel 01 sind vervollständigt worden.
  • (08.04.2007) Die Modalitäten zum Erwerb von Leistungsnachweisen etc. wurden nach Studiengängen ausdifferenziert.
  • (28.02.2007) Die Vorlesung beginnt am Montag, 02. April 2007.

 


Inhalt

Die algorithmische Geometrie beschäftigt sich mit der Entwicklung und Realisierung effizienter Algorithmen für die Lösung geometrischer Probleme. Diese Probleme, die sich mit geometrischen Objekten wie Punkten, Linien oder Polygonen (bzw. deren höherdimensionalen Entsprechungen) beschäftigen, sind für viele Anwendungsgebiete von Bedeutung, z.B. für Geographische Informationssysteme, Computer Aided Design oder (vektor-orientierte) Computergraphik.

In dieser Vorlesung werden wir uns mit verschiedenen Klassen von Aufgabenstellungen befassen, z.B. mit der Berechnung von Nachbarschaftsbeziehungen, Triangulierungen und der Beantwortung von Lokalisierungsanfragen. Hierbei werden wir verschiedene Entwurfs- und Analysetechniken kennen lernen, die zur Behandlung geometrischer Problemstellungen verwendet werden können.

Da die betrachteten Problemstellungen anschaulich relativ einfach zu beschreiben sind und die entwickelten Techniken und Algorithmen meist auf elementarer Euklidischer Geometrie basieren, sind zum Verständnis der Vorlesung nur Kenntnisse aus dem Grundstudium notwendig. Grundsätzliches Interesse am Themenbereich "Algorithmen und Datenstrukturen" (d.h. Freude an den Themen der Vorlesung DAP2) ist jedoch mehr als hilfreich.

 


Vorlesungsunterlagen

Die in der Vorlesung vorgestellten Folien werden hier im Laufe des Semesters veröffentlicht. Das für den Zugriff auf die Folien notwendige Passwort wird in der Vorlesung bekannt gegeben.

Folien

Beispielkonfigurationen

An dieser Stelle werden Beispielkonfigurationen zum Mitschreiben in der Vorlesung bzw. zur eigenen Nachbereitung bereit gestellt.

  • Kapitel 02: Konvexe Hülle (Teil 1), Stand: 22.04.2007.

Errata/Nachträge/OAQs

An dieser Stelle werden Errata (jedoch keine Korrekturen von Tippfehlern) und/oder Nachträge veröffentlicht. Bei Bedarf werden über den Vorlesungsstoff hinaus gehende (also nicht prüfungsrelevante!) Fragen (so genannte occasionally asked questions) diskutiert.

  • (09.10.2007) Die Unterlagen zu Kapitel 01-04 sind um Tippfehler bereinigt worden. Vielen Dank an alle Studierenden, die Korrekturhinweise gegeben haben!
  • (30.08.2007) Die Volumen-Berechnungen in Kapitel 1 wurden der Orientierung bzgl. der "Rechte-Hand-Regel" angepasst.
  • (14.08.2007) Es wurden kleine (Tipp-)Fehler in den Kapitel 2, 3 und 5 behoben. Die Errata sind hier, hier und hier ergänzt.
  • (06.08.2007) Die Folien für Kapitel 07 wurden so überarbeitet, dass alle bis zu diesem Zeitpunkt bekannten Fehler korrigiert wurden. Die Errata sind hier zusammen gestellt.
  • (06.08.2007) Die Folien für Kapitel 06 wurden so überarbeitet, dass alle bis zu diesem Zeitpunkt bekannten Fehler korrigiert wurden. Die Errata sind hier zusammen gestellt.
  • (06.08.2007) Die Folien für Kapitel 05 wurden so überarbeitet, dass alle bis zu diesem Zeitpunkt bekannten Fehler korrigiert wurden. Die Errata sind hier zusammen gestellt.
  • (25.06.2007) Die Folien für Kapitel 04 wurden so überarbeitet, dass alle bis zu diesem Zeitpunkt bekannten Fehler korrigiert wurden. Die Errata sind hier zusammen gestellt.
  • (05.06.2007) Die Folien für Kapitel 03 wurden so überarbeitet, dass alle bis zu diesem Zeitpunkt bekannten Fehler korrigiert wurden. Die Errata sind hier zusammen gestellt.
  • (19.05.2007) Die Folien für Kapitel 02 wurden so überarbeitet, dass alle bis zu diesem Zeitpunkt bekannten Fehler korrigiert wurden. Die Errata sind hier zusammen gestellt.
  • (25.04.2007) OAQ 2: "Was ist ein 'Abstrakter Datentyp'?"
  • (25.04.2007) OAQ 1: "Was ist die formale Definition einer Zusammenhangskomponente im IRd?"
  • (24.04.2007) OAQ 0: "Warum folgt aus der linearen Abhängigkeit der Zeilen der Matrix auf Folie 1.101, dass alle vier Punkte kozirkulär sind?"
  • (24.04.2007) Die Folien für Kapitel 01 wurden so überarbeitet, dass alle bis zu diesem Zeitpunkt bekannten Fehler korrigiert wurden. Die Errata sind hier zusammen gestellt.

 


Übungen

Die Übungen finden Mittwoch, 14:00-15:30 Uhr, in Raum U08, OH-16 statt, es wird eine Übungsgruppe eingerichtet. Bei Terminkollisionen mit anderen Veranstaltungen besteht eine gewisse Flexibilität; sprechen Sie mich gerne bei Bedarf deswegen an. Der erste Übungstermin ist Mittwoch, 11.04.2007.

Nachfolgend stehen die jeweils aktuellen Übungszettel im PDF-Format bereit.

  • Blatt 01 (.pdf), Abgabe am 10.04.2007, Besprechung am 11.04.2007.
  • Blatt 02 (.pdf), Abgabe am 16.04.2007, Besprechung am 18.04.2007.
  • Blatt 03 (.pdf), Abgabe am 23.04.2007, Besprechung am 25.04.2007.
  • Blatt 04 (.pdf), Abgabe am 07.05.2007, Besprechung am 09.05.2007.
  • Blatt 05 (.pdf), Abgabe am 14.05.2007, Besprechung am 16.05.2007.
  • Blatt 06 (.pdf), Abgabe am 21.05.2007, Besprechung am 23.05.2007.
  • Blatt 07 (.pdf), Abgabe am 29.05.2007, Besprechung am 30.05.2007.
  • Blatt 08 (.pdf), Abgabe am 11.06.2007, Besprechung am 13.06.2007.
  • Blatt 09 (.pdf), Abgabe am 18.06.2007, Besprechung am 20.06.2007.
  • Blatt 10 (.pdf), Abgabe am 25.06.2007, Besprechung am 27.06.2007.
  • Blatt 11 (.pdf), Abgabe am 02.07.2007, Besprechung am 04.07.2007.
  • Blatt 12 (.pdf), Abgabe am 09.07.2007, Besprechung am 11.07.2007.

Errata/Nachträge

 


Literatur

Die Vorlesung basiert im Wesentlichen auf dem nachfolgend angegebenen (englischsprachigen) Lehrbüchern:

  • M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf: "Computational Geometry: Algorithms and Applications", 2. Auflage, Springer, Berlin, 2000.
  • F. P. Preparata, M. I. Shamos "Computational Geometry: An Introduction", 2. Auflage, Springer, Berlin, 1988.

Für den erfolgreichen Besuch der Vorlesung ist es jedoch nicht zwingend notwendig, diese (sehr guten) Bücher zu erwerben.

Weitere Literaturhinweise sind im Kapitel "Organisatorisches" zu finden.

 


Fachprüfung/Leistungsnachweis/Studiennachweis

  • Studierende nach DPO'01: Für die erfolgreiche Teilnahme an der Vorlesung und an den Übungen wird ein Leistungsnachweis ausgestellt. Bedingung hierfür ist (neben der Teilnahme) die Bearbeitung von 50% der Aufgaben (jeweils 50% der Aufgaben von Blatt 2-7 und 50% der Aufgaben von Blatt 8-14) sowie das Vorrechnen von zwei Aufgaben in der Übung.
    Eine Fachprüfung kann in Form einer Klausur im Unfang von 90 min. Dauer abgelegt werden.
  • Studierende nach LPO'94: Für die erfolgreiche Teilnahme an der Vorlesung und an den Übungen wird ein qualifizierter Studiennachweis ausgestellt. Bedingung hierfür ist (neben der Teilnahme) die Bearbeitung von 50% der Aufgaben (jeweils 50% der Aufgaben von Blatt 2-7 und 50% der Aufgaben von Blatt 8-14), wobei mindestens eine Programmieraufgabe akzeptabel gelöst werden muss, sowie das Vorrechnen von zwei Aufgaben in der Übung.
    Ein Leistungsnachweis (im Sinne der LPO'03) kann durch Bestehen einer Klausur im Unfang von 120 min. Dauer erhalten werden.
  • Studierende nach anderen Prüfungsordnungen: Bitte halten Sie mit mir Rücksprache.

 

 
Sitemap Imprint
<www  ls11.cs.uni-dortmund.de>
The university does not accept liability for the contents of linked external internet sites