Friedrich-Alexander-Universität DruckenUnivisEnglish FAU-Logo
Techn. Fakultät Willkommen am Department Informatik FAU-Logo
Codesign
Lehrstuhl für Informatik 12
Theoretische Informatik II
SS 05

Department Informatik  >  Informatik 12  >  Lehre  >  Theoretische Informatik II, SS 05

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:

Blatt 0 Blatt 1 Blatt 2
Blatt 3 Blatt 4 Blatt 5
Blatt 6 Blatt 7 Blatt 8
Blatt 9 Blatt 10 Blatt 11
Blatt 12    

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.
  Impressum Stand: 25 July 2005.   R.W.