Vorlesung: Theoretische Informatik III

Übungen: Olaf Beyersdorff, Peter Liske, Carsten Schwarz


Termine:	VL Mi 15-17 (RUD 26, 0'115) Prof. J. Köbler
	UE Di 11-13 (RUD 25, 4.112, ab 20.04.) P. Liske
	UE Di 11-13 (RUD 25, 4.112, ab 27.04.) P. Liske
	UE Mi 13-15 (RUD 25, 4.112, ab 21.04.) C. Schwarz
	UE Mi 13-15 (RUD 25, 4.112, ab 28.04.) C. Schwarz
	UE Do 11-13 (RUD 26, 1'306, ab 22.04.) O. Beyersdorff
	UE Do 11-13 (RUD 26, 1'306, ab 29.04.) O. Beyersdorff

Zuordnung:	Grundstudium, 4. Semester

Klausurtermine:

Nachklausur Theoretische Informatik II: 21. Juli, 9 Uhr, Raum 0`115 (großer Hörsaal im Erwin- Schrödinger- Zentrum)
Klausur Theoretische Informatik III: 5. August , 9 Uhr, Audimax (Hauptgebäude, Unter den Linden)

Konsultationen:

für Theoretische Informatik II: 15. Juli, 15 Uhr, Raum 4.112
für Theoretische Informatik III: 28. Juli, 11 Uhr, Raum 3.101
für Theoretische Informatik III: 3. August, 13 Uhr, Raum 3.101

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.
Wagner: Einführung in die Theoretische Informatik, Grundlagen und Modelle. Springer Verlag, 1994.
Wegener: Theoretische Informatik. Teubner Verlag, 1993.

Vorlesung: Theoretische Informatik III

Inhalte und Lernziele

Empfohlene Literatur

Aufgabenblätter

Skript (pdf)