Vorlesung: Theoretische Informatik II
Dozent: Prof.
Johannes Köbler
| Termine: |
VL VL UE UE UE UE UE UE |
Di Do Di Di Do Do Fr Fr |
09-11 09-11 11-13 15-17 11-13 15-17 09-11 11-13 |
RUD 25, 3.001 RUD 25, 3.001 RUD 26, 1'305 RUD 26, 1'305 RUD 25, 3.113 RUD 26, 1'305 RUD 25, 3.113 RUD 25, 3.113 |
J. Köbler J. Köbler M. Zelke S. Kuhnert S. Müller M. Weyer W. Kössler W. Kössler |
| Zuordnung: | Grundstudium, 3. Semester |
Übungsschein: Auf den Übungsblättern sind einige Aufgaben schriftlich zu lösen. 50% der Punkte sind notwendig für einen Übungsschein, für den außerdem 3 der mündlichen Aufgaben in der Übung vorzurechnen sind. Der Übungsschein ist Voraussetzung für die Zulassung zur Prüfung.
Fragestunde vor der Prüfung: Am Donnerstag, 19.02.2009, gibt es im Raum 4.012 (RUD25) von 14 bis 15 Uhr noch einmal Gelegenheit, Fragen zu Vorlesung und Übung zu stellen.
Prüfung: Die Prüfung findet am Dienstag, 24.02.2009, um 9 Uhr im großen Hörsaal (RUD26, 0'115) statt. Die Nachklausur wird Mitte/Ende Juli stattfinden.
Nachklausur: Die Nachklausur findet am Fr., 24.07.2009, um 9:00 Uhr in RUD26 0'115 statt.
- Die Einsicht findet am 4.8. um 14:00 im RUD25 4.015 statt.
Inhalte und Lernziele
Die VL führt in die Kerngebiete der Theoretischen Informatik ein, wobei die Themengebiete Automaten und formale Sprachen im Mittelpunkt stehen. Die hierbei behandelten Fragen sind nicht nur aus theoretischer Sicht interessant, sondern bilden zugleich die Grundlage für so praktische Anwendungsgebiete wie den Compilerbau. Aufbauend auf dem Automatenmodell der Turingmaschine läßt sich der Begriff des Algorithmus formalisieren, der in allen Bereichen der Informatik eine zentrale Rolle spielt. Die für den praktischen Einsatz wichtige Frage, welcher Rechenaufwand zur Lösung algorithmischer Problemstellungen nötig ist, führt uns einerseits zu verschiedenen Entwurfsmethoden für effiziente Algorithmen (wobei sich Kenntnisse über algebraische und relationale Strukturen, insbesondere Graphen, als überaus nützlich erweisen). Da die gefundenen Algorithmen "nur" obere Schranken für den benötigten Rechenaufwand liefern, versuchen wir andererseits mit Methoden der Komplexitätstheorie, diesen Aufwand auch nach unten abzuschätzen.
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.
- Rich: Automata, Computability, and Complexity. Pearson Prentice Hall, 2008.
- Schacht: Folien zur Theoretischen Informatik II aus dem Wintersemester 2006/07
- 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.
- Harry Mairson : The Pumping Lemma (poem)
Aufgabenblätter
Abgabe der schriftlichen Lösungen im Erdgeschoss von Haus 4!
Bitte Angabe von Name, Matrikelnr., Übungstermin und ggf. Goya-Gruppe nicht vergessen!
Blatt 1 (mündl. Besprechung: 21.-24.10.2008; schriftl. Abgabe: bis 28.10.2008, 9:10 Uhr)
Blatt 2 (mündl. Besprechung: 28.-31.10.2008; schriftl. Abgabe: bis 04.11.2008, 9:10 Uhr)
Blatt 3 (mündl. Besprechung: 04.-07.11.2008; schriftl. Abgabe: bis 11.11.2008, 9:10 Uhr)
Blatt 4 (mündl. Besprechung: 11.-14.11.2008; schriftl. Abgabe: bis 18.11.2008, 9:10 Uhr)
Blatt 5 (mündl. Besprechung: 18.-21.11.2008; schriftl. Abgabe: bis 25.11.2008, 9:10 Uhr)
Blatt 6 (mündl. Besprechung: 25.-28.11.2008; schriftl. Abgabe: bis 02.12.2008, 9:10 Uhr)
Blatt 7 (mündl. Besprechung: 02.-05.12.2008; schriftl. Abgabe: bis 09.12.2008, 9:10 Uhr)
Blatt 8 (mündl. Besprechung: 09.-12.12.2008; schriftl. Abgabe: bis 16.12.2008, 9:10 Uhr)
Blatt 9 (mündl. Besprechung: 16.-19.12.2008; schriftl. Abgabe: bis 06.01.2009, 9:10 Uhr)
Blatt 10 (mündl. Besprechung: 06.-09.01.2009; schriftl. Abgabe: bis 13.01.2009, 9:10 Uhr)
Blatt 11 (mündl. Besprechung: 13.-16.01.2009; schriftl. Abgabe: bis 20.01.2009, 9:10 Uhr)
Blatt 12 (mündl. Besprechung: 20.-23.01.2009; schriftl. Abgabe: bis 27.01.2009, 9:10 Uhr)
Blatt 13 (mündl. Besprechung: 27.-30.01.2009; schriftl. Abgabe: bis 03.02.2009, 9:10 Uhr)
Blatt 14 (mündl. Besprechung: 03.-06.02.2009; schriftl. Abgabe: bis 10.02.2009, 9:10 Uhr)
Probeklausur (mündl. Besprechung: 10.-13.02.2009; Lösungsvorschläge)