Theoretische Informatik II
(für Computervisualisten)

Stundenplan

Ergebnisse der Prüfungsklausur vom 02.08.2006

Ergebnisse der Übungsscheinnachklausur vom 17.07.2006

Ergebnisse der Prüfungsklausur vom 09.02.2006

Ergebnisse der Übungsscheinklausur vom 24.01.2006 (Bitte genau nachschauen, wer den Übungsschein bekommt!)

Übungsblätter:

8.Übungsblatt   9.Übungsblatt 10.Übungsblatt 11.Übungsblatt 12.Übungsblatt 13.Übungsblatt 14.Übungsblatt

Vorlesungsmaterialien:
Algorithmen für N-V-Schnittpunkte
Chan's Algorithmus für konvexe Hülle
C++ Code Durchmesser einer Punktemenge
Aufbau Punktlokalisierungsdatenstruktur, Punktlokalisierung
Turingmaschinen und NP-Vollständigkeit

Ziel:
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 Wintersemester gibt es neben effizienten geometrischen Algorithmen eine minimalistische Einführung in die Komplexitätstheorie, insbesondere NP-Vollständigkeit.

Hörerkreis:
Studenten der Computervisualistik im Grundstudium.

Prüfung:

• schriftlich, 2 Stunden, am Ende des Wintersemesters 2005/06
• Zulassungsvoraussetzung zur Prüfung: Übungsschein.
• Am Ende des Wintersemesters gibt es eine einstündige Klausur. Wer diese Klausur besteht und die des vorangegangenen Sommersemesters bestanden hat, bekommt den Übungsschein und darf an der Prüfungsklausur teilnehmen.

Literaturhinweise:

	Michiel Smid. Vorlesungsskript Theoretische Informatik für Computervisualisten (.ps) (.pdf).
Algorithmische Geometrie
	de Berg, van Kreveld, Overmars, Schwarzkopf. Computational Geometry, Algorithms and Applications. Springer-Verlag, 2000.
	Klein. Algorithmische Geometrie (2. Auflage). Springer-Verlag, 2005.
Theoretische Informatik NP-Vollständigkeit
	Kapitel 16 - 20 über NP-Vollständigkeit aus David Mounts Lecture Notes zu CMSC 451. Wenn in diesen Lecture Notes von dem Text oder von CLRS die Rede ist, so ist damit das Buch Introduction to Algorithms von Cormen, Leiserson, Rivest und Stein gemeint.
	Schöning. Theoretische Informatik - kurzgefasst. Spektrum-Verlag.
	Wagner. Theoretische Informatik - Eine kompakte Einführung. Springer-Verlag, 2003.
Mathematische Grundlagen
	Farin, Hansford. Lineare Algebra - Ein geometrischer Zugang. Springer-Verlag, 2003.