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, M.
Füssel,
P. Liske, C. Schwarz
Klausurtermin
Die Klausur findet am 30.3.2004 von 9.00 bis 12.00 Uhr im Kinosaal
(Hauptgebäude) statt.
Noch ein wichtiger Hinweis zur Klausur: Bücher, Skripte oder
andere Unterlagen dürfen nicht verwendet werden.
Konsultationen
Die Konsultationen zur Prüfung "Theoretische Informatik 2" finden
Mittwoch, 24. März, 9 bis 11 Uhr (mit Carsten Schwarz) und
Donnerstag, 25. März, 13 bis 15 Uhr (mit Matthias Füssel)
im Johann von Neumann-Haus, Raum 3.110 statt.
Bitte schickt rechtzeitig eine E-Mail mit
- euren Fragen bzw. den nicht verstandenen Übungsaufgaben und
- der Konsultation, an der ihr teilnehmen werdet,
an caschwar@informatik.hu-berlin.de,
damit wir diese sinnvoll strukturieren können.
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 Di 11-13 (RUD
26, 0'313) O. Beyersdorff |
|
UE Mi
13-15 (RUD 26, 1'305) O. Beyersdorff |
|
UE Mi
15-17 (RUD 26, 1'308) C. Schwarz |
|
UE Do
15-17 (RUD 25, 4.111) C. Schwarz |
|
UE Fr
09-11 (RUD 26, 1'308) M. Füssel |
|
UE Fr 11-13 (RUD
26, 1'308)
P. Liske |
|
|
Zuordnung:
Grundstudium, 3.
Semester |
|
Die Einschreibung zu den Übungen und die Vergabe der Punkte
erfolgt
über das Goya-System.
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 12-15 (pdf)
- Übung 4, Aufgaben 16-20 (pdf)
- Übung 5, Aufgaben 21-26 (pdf)
- Übung 6, Aufgaben 27-31 (pdf)
- Übung 7, Aufgaben 32-36 (pdf)
- Übung 8, Aufgaben 37-40 (pdf)
- Übung 9, Aufgaben 41-44 (pdf)
- Übung 10, Aufgaben 45-49 (pdf)
- Übung 11, Aufgaben 50-55 (pdf)
- Übung 12, Aufgaben 56-62 (pdf)
- Probeklausur (pdf)
- Klausur (pdf)
Skript
JK
Erstellt am 05.08.2003