Vorlesung Theoretische Informatik I für Computervisualisten

Sommersemester 2006

Prüfung:

• schriftlich, 2 Stunden, am Ende des Wintersemesters 2006/07
• Zulassungsvoraussetzung zur Prüfung: Übungsschein.
• Am Ende des Sommersemesters 2006 und Wintersemesters 2006/07 gibt es jeweils eine einstündige Klausur. Wer beide Klausuren besteht, bekommt den Übungsschein und darf am Ende des Wintersemesters 2006/07 an der Prüfungsklausur teilnehmen.
• Ergebnisse der Übungsscheinklausur vom 12. Juli 2006

Inhalt:

• Dies ist eine zwei-semestrige Vorlesung, in der Grundzüge der Theoretischen Informatik wie Berechenbarkeit und NP-Vollständigkeit und der Entwurf und die Analyse von effizienten, geometrischen Algorithmen behandelt werden.
• Im Sommersemester werden unter anderem behandelt: Analyse von Algorithmen, Teile-und-Herrsche Algorithmen, Plane-Sweep Algorithmen, Berechnung der Schnittpunkte in einer Menge von Liniensegmenten.

Literatur:

• Michiel Smid: Vorlesungsskript Theoretische Informatik für Computervisualisten.
• Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Schwarzkopf: Computational Geometry, Algorithms and Applications. Springer-Verlag, 2000.
• Rolf Klein: Algorithmische Geometrie. Addison-Wesley, 1997.
• Uwe Schöning: Theoretische Informatik - kurzgefasst. Spektrum-Verlag.
• Klaus W. Wagner: Theoretische Informatik - Eine kompakte Einführung. Springer-Verlag, 2003.
• Gerald E. Farin, Dianne Hansford: Lineare Algebra - Ein geometrischer Zugang. Springer-Verlag, 2003.(Mathematische Grundlagen)

Übungsblätter:

• Übungsblatt 1
• Übungsblatt 2
• Übungsblatt 3
• Übungsblatt 4
• Übungsblatt 5
• Übungsblatt 6

Folien:

• Fermats Last Theorem (Vorlesung am 12. April 2006)
• Maximale Elemente (Teile-und-Herrsche-Algorithmus) (Vorlesung am 17. Mai 2006)

Informationen:

• Stundenplan laut Univis