 |
Einführung in die Theoretische Informatik II
| Dozent |
Rolf Wanka |
| Umfang |
V3 + Ü2,
Studenten der Informatik, 2. Semester |
Ort
und Zeit der Vorlesungen
|
Mi. 9:15-10:00, Hörsaal H7
Fr. 12:30 - 14:00, Hörsaal H7
|
Ort
und Zeit der Übung
|
siehe
hier (als pdf-File) als Stundenplan.
|
Übungs-/Probeklausur:
-
Die Übungsklausur wurde am Freitag, d.
22. Juli 2005 im
Hörsaal H7 in der Zeit von
14:00 Uhr (pünktlich) bis 15:45 Uhr
geschrieben.
-
Die Korrektur läuft gerade. Sobald sie fertig ist,
wird das hier stehen!
Inhalte:
- Turingmaschinen, die Churche These und Entscheidbarkeit
- NP-Vollständigkeit
- Grammatiken und die Chomsky-Hierarchie
- Kontextfreie Grammatiken und Kontextfreie Sprachen
- Kellerautomaten
Übungsblätter:
Skript-Teile:
Der ausgearbeitete Anfang von Abschnitt 1.4 "Unentscheidbare Probleme"
kann hier als pdf-File
heruntergeladen werden.
Die Fortsetzung:
Nun gibt es auch die Abschnitte 1.5 (Reduktionen und der
Satz von Rice) und 1.6 (Rekursive
Aufzählbarkeit) in ausgearbeiteter Form
hier als pdf-File
(das pdf-File enthält auch Abschnitt 1.4, ab Seite 4 ist der
neue Text zu finden).
Klausur:
Die zeitlich nächste Theorie-Klausur wird am
30. September 2005 geschrieben werden.
Die Inhalte dieser "Nachklausur" werden sich an den
Vorlesungen Stoyan/Müller/Strehl der vergangenen Jahre orientieren.
Der Inhalt der aktuellen Vorlesung "Einführung in die
Theoretische Informatik II" wird ab der Klausur im Frühjahr
2006 verbindlich sein.
Literatur:
Die Vorlesung orientiert sich sehr stark am Lehrbuch:
- Ingo Wegener. Theoretische Informatik - eine
algorithmenorientierte Einführung, Teubner, 2. Auflage 1999.
Das Buch kostet 21,90 EUR und kann im einschlägigen
Internetbuchhandel, z.B. bei
und in jeder Präsenzbuchhandlung
bestellt werden.
Eine gelungene Abrundung des Inhalts seines Buches präsentiert
Ingo Wegener in:
- Ingo Wegener. Kompendium Theoretische Informatik - Eine
Ideensammlung, Teubner 1996.
Es gibt eine ganze Reihe sehr guter Bücher zu den Grundbegriffen
der Theoretischen Informatik. Ein paar seien hier genannt:
- John E. Hopcroft, Jeffrey D. Ullman. Introduction to
Automata Theory, Languages, and Computation, Addison-Wesley 1997.
- John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman. Introduction to
Automata Theory, Languages, and Computation, Addison-Wesley,
2nd Edition 2001.
- Juraj Hromkovic. Theoretische Informatik - Berechenbarkeit,
Komplexitätstheorie, Algorithmik, Kryptographie. Eine Einführung,
Teubner, 2. Auflage 2004.
- Bernard M. Moret. The Theory of Computation,
Addison-Wesley 1997.
- Uwe Schöning. Theoretische Informatik kurzgefaßt,
Spektrum Akademischer Verlag, 4. Auflage 2001.
- Klaus W. Wagner. Einführung in de Theoretische Informatik -
Grundlagen und Modelle, Springer 1991.
- Ingo Wegener. Theoretische Informatik - eine
algorithmenorientierte Einführung, Teubner, 2. Auflage 1999.
- Ingo Wegener. Kompendium Theoretische Informatik - Eine
Ideensammlung, Teubner 1996.
|
|
