Vorlesung: Theoretische Informatik III

Übungen: Olaf Beyersdorff, Hiep Han, Carsten Schwarz


Termine:	VL Mi 15-17 (RUD 26, 0.115) Prof. J. Köbler
	UE Di 11-13 (RUD 26, 1.305, 14tgl./1.) O. Beyersdorff
	UE Di 11-13 (RUD 26, 1.305, 14tgl./2.) O. Beyersdorff
	UE Do 09-11 (RUD 26, 1.305, 14tgl./1.) O. Beyersdorff
	UE Do 09-11 (RUD 26, 1.305, 14tgl./2.) O. Beyersdorff
	UE Fr 09-11 (RUD 26, 1.307, 14tgl./1.) C. Schwarz
	UE Fr 01-11 (RUD 26, 1.307, 14tgl./2.) C. Schwarz

Zuordnung:	Grundstudium, 4. Semester

Klausurtermine

Theoretische Informatik III: 15. Juli, Einlass: 13:00 Uhr, Dauer: ca. 2 Stunden, Raum: UL 6, 2116 (Auditorium Maximum)
Nachschreibeklausur Theoretische Informatik II: 22. Juli, Einlass: 10:00 Uhr, Dauer: ca. 2 Stunden, Raum: RUD 26, 0.115

Hilfsmittel (Skripte, Rechner etc.) sind zur Klausur nicht zugelassen.

Übersicht Übungen

	Übung Dienstags 11-13 Uhr	Übung Donnerstags 9-11 Uhr	Übung Freitags 9-11 Uhr
Woche ab dem 5. Juli	Probeklausur	Probeklausur	keine Übung
Woche ab dem 12. Juli	Kosultation zu Theo III	Kosultation zu Theo III	keine Übung

Die Kosultation zu Theo II wird am 19. Juli, 14:15 Uhr, in RUD 25, 3.113 stattfinden.

Inhalte und Lernziele

Während in der Vorlesung TI2 die Themengebiete Automaten und formale Sprachen im Mittelpunkt standen, befassen wir uns in der VL TI3 vorwiegend mit verschiedenen Entwurfsmethoden für effiziente Algorithmen. Die hierzu nötigen Kenntnisse über algebraische und relationale Strukturen wie etwa Graphen werden ebenfalls in der VL vermittelt. Da die gefundenen Algorithmen "nur" obere Schranken für den benötigten Rechenaufwand liefern, untersuchen wir auch Methoden der Komplexitätstheorie, diesen Aufwand nach unten abzuschätzen. Um auch NP-vollständige Probleme in der Praxis mit vertretbarem Aufwand bewältigen zu können, werden u.a. auch approximative und/oder randomisierte Lösungsverfahren eingesetzt, die oftmals auf heuristischen Ansätzen beruhen.

Empfohlene Literatur

Blum: Theoretische Informatik. Oldenbourg 1998.
Emden-Weinert, Hougardy, Kreuter, Prömel, Steger: Einführung in Graphen und Algorithmen, Vorlesungsskript, 450 Seiten, Berlin 1996.
Garey, Johnson: Computers and Intractability - A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, 1979.
Hopcroft, Ullman: Introduction to Automata Theory, Languages, and Computation. Addison Wesley, 1979.
Lewis, Papadimitriou: Elements of the Theory of Computation. Prentice-Hall, 1981.
Motwani, Raghavan: Randomized Algorithms. Cambridge University Press, 1995.
Papadimitriou: Computational Complexity. Addison-Wesley, 1994.
Schmidt, Ströhlein: Relations and Graphs. Springer Verlag, 1993.
Schöning: Perlen der Theoretischen Informatik. BI-Wissenschaftsverlag, 1995.
Schöning: Theoretische Informatik - kurz gefaßt. Spektrum Akademischer Verlag, 1997.
Sipser: Introduction to the Theory of Computation. PWS Publishing Company, 1997.
Tittmann: Graphentheorie. Fachbuchverlag Leipzig, 2003.
Wagner: Einführung in die Theoretische Informatik, Grundlagen und Modelle. Springer Verlag, 1994.
Wegener: Theoretische Informatik. Teubner Verlag, 1993.

Vorlesung: Theoretische Informatik III

Klausurtermine

Übersicht Übungen

Inhalte und Lernziele

Empfohlene Literatur

Aufgabenblätter

Skript (pdf)