Humboldt-Universität
zu
Berlin,
Institut
für Informatik
Lehrstuhl
für Komplexität und Kryptografie
Vorlesung: Theoretische Informatik II
Dozent:
Prof.
Johannes Köbler
Übungen: Olaf
Beyersdorff, Amin
Coja-Oghlan, Peter
Liske, Christian Rothe,
Carsten Schwarz
Termine: |
VL Di 09-11 (RUD 25, 3.001)
Prof. J. Köbler |
|
VL Do 09-11 (RUD 25, 3.001)
Prof. J. Köbler |
|
UE Mo 13-15 (RUD
26, 1.305) P. Liske / C. Rothe |
|
UE Mo
15-17 (RUD 26, 1.305) C. Schwarz |
|
UE Di
11-13 (RUD 26, 1.305) O. Beyersdorff |
|
UE Di
15-17 (RUD 26, 1.305) O. Beyersdorff |
|
UE Do
11-13 (RUD 26, 1.305) A. Coja-Oghlan |
|
UE Do 15-17 (RUD 26, 1.305)
A. Coja-Oghlan |
|
|
Zuordnung: Grundstudium, 3.
Semester |
|
Die Einschreibung zu den Übungen und die Vergabe der Punkte erfolgt
über das Goya-System.
Klausurtermine:
-
die Klausur Theoretische Informatik 2 findet am 2.
März 2005 um 15 Uhr in UL 6, 1115 (Hauptgebäude, Kinosaal)
statt
-
die Nach- und Wiederholungsklausur Theoretische Informatik
3 findet am 4. März 2005 um 10 Uhr in RUD 25, 3.001 statt.
Konsultationstermine:
-
Die Probeklausur wird in den Übungen in der Woche vom 14.02. bis 18.02.05
besprochen.
-
Konsultation Nachklausur Theoretische Informatik 3: am 24.02.05 um
13 Uhr, Raum 3.101 (RUD 25)
-
Konsultation Theoretische Informatik 2: am 24.02.05 um 15 Uhr,
Raum 3.101 (RUD 25)
-
Konsultation Theoretische Informatik 2: am 01.03.05 um 15 Uhr,
Raum 3.101 (RUD 25)
Hinweise zu den Klausuren:
-
Anmeldung zu den Klausuren bis 16.02.05 bei Herrn Herold
-
Zur Zulassung zur Klausur ThI 2 sind mindestens 65 Punkte bei den schriftlichen
Aufgaben erforderlich.
-
Hilfsmittel (Skripte, Rechner etc.) sind zur Klausur nicht zugelassen.
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.
-
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.
Übungsaufgaben
-
Übung
1, Aufgaben 1-6 (pdf)
-
Übung
2, Aufgaben 7-12 (pdf)
-
Übung
3, Aufgaben 13-16 (pdf)
-
Übung
4, Aufgaben 17-22 (pdf)
-
Übung
5, Aufgaben 23-28 (pdf)
-
Übung
6, Aufgaben 29-33 (pdf)
Musterlösung
Aufgabe 30 (pdf)
-
Übung
7, Aufgaben 34-38 (pdf)
-
Übung
8, Aufgaben 39-42 (pdf)
-
Übung
9, Aufgaben 43-46 (pdf)
-
Übung
10, Aufgaben 47-51 (pdf)
-
Übung
11, Aufgaben 52-58 (pdf)
-
Übung
12, Aufgaben 59-63 (pdf)
-
Übung
13, Aufgaben 64-71 (pdf)
-
Übung
14, Aufgaben 72-84 (pdf)
-
Probeklausur
(pdf)
Carsten Schwarz
Erstellt am 06.09.2004