Theoretische Informatik I
(für Computervisualisten)

Sommersemester 2004

Vorlesung:
Mittwochs 11-13, G50-H3 (außer Freitag, 16.7. 11-13, G55-231)

Vorlesung vom 9. Juni verlegt auf 7. Juni 18-20, G50-H3
Vorlesung vom 23. Juni verlegt auf 21. Juni 18-20, G50-H3

Folien zur Vorlesung vom 14.04.04: Theorie   Dovetailing
Folien zur Vorlesung vom 21.04.04: HelloWorld   FermatsLastTheorem
Folien zur Vorlesung vom 28.04.04: insertion sort
Folien zur Vorlesung vom 19.05.04: merge sort
Folien zur Vorlesung vom 26.05.04: Maximale Elemente
Folien zur Vorlesung vom 02.06.04: Minimaler Punktabstand   verbesserter Algorithmus
Folien zur Vorlesung vom 16.06.04: H-V-Schnittpunkte
Folien zur Vorlesung vom 30.06.04: Skelett des BentleyOttmann Sweeps
Folien zur Vorlesung vom 16.07.04: Jarvis' march

Ergebnisse der Übungsscheinklausur zu Teil I vom 07.07.2004.

Übungen:

Zeit Ort Beginn Do 7:30 -   9:00 gKW G05-307 15. April Do 7:30 -   9:00 uKW G05-307  22. April Fr 9:15 - 10:45 gKW G29-K058 16. April Fr 9:15 - 10:45 uKW G29-K058 23. April

1.Übungsblatt 2.Übungsblatt 3.Übungsblatt 4.Übungsblatt 5.Übungsblatt 6.Übungsblatt 7.Übungsblatt 8.Übungsblatt

Übungsgruppe von Fr. 21.05. verlegt auf Di. 18.05. 17:00-18:30 Uhr in G05-307. Übungsgruppe von Do. 20.05. bitte auf die übrigen Termine aufteilen (13.05., 14.05, 18.05.) oder bei Bianca Truthe melden, falls keiner der Termine passt. Das 8.Übungsblatt und die Reste des 7.Übungsblattes werden in der ersten Übung im Wintersemester besprochen!

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. In diesem Sommersemester werden unter anderem behandelt: Berechenbarkeit, Analyse von Algorithmen, Teile-und-Herrsche Algorithmen, Plane-Sweep Algorithmen, Berechnung der Schnittpunkte in einer Menge von Liniensegmenten.

Hörerkreis:
Studenten der Computervisualistik im Grundstudium.

Prüfung:

• schriftlich, 2 Stunden, am Ende des Wintersemesters 2004/05
• Zulassungsvoraussetzung zur Prüfung: Übungsschein.
• Am Ende des Sommersemesters 2004 und Wintersemesters 2004/05 gibt es jeweils eine einstündige Klausur. Wer beide Klausuren besteht, bekommt den Übungsschein und darf am Ende des Wintersemesters 2004/05 an der Klausur teilnehmen.

Literaturhinweise:

	Michiel Smid. Vorlesungsskript Theoretische Informatik für Computervisualisten.
Algorithmische Geometrie
	de Berg, van Kreveld, Overmars, Schwarzkopf. Computational Geometry, Algorithms and Applications. Springer-Verlag, 2000.
	Klein. Algorithmische Geometrie. Addison-Wesley, 1997.
Theoretische Informatik NP-Vollständigkeit
	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.