Vorlesung: Theoretische Informatik III

Dozent: Prof. Johannes Köbler

Übungen: J. Mayer, Dr. L. Popova-Zeugmann, D. Schlatter

Inhalte und Lernziele

Wärend 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 vielfach 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.
• 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.

Aufgabenblätter

• Aufgabenblatt 1
• Aufgabenblatt 2
• Aufgabenblatt 3
• Aufgabenblatt 4
• Aufgabenblatt 5
• Aufgabenblatt 6

Prüfung

• Teilnehmerliste
• Probeklausur (mit Punkten; vorgesehene Zeit: 60 Minuten)
• Lösung zur Probeklausur
• Lösung zur Klausur
• Klausurergebnisse

Organisatorisches

Skript