Vorlesung Theoretische Informatik


Dozent: Prof. Dr. R. Schrader



Die Vorlesung findet jeweils im Seminarraum, Weyertal 80 statt.

Die Übungen finden

im Seminarraum, Weyertal 80 statt (die Übungen beginnen am 22.10.2001).



Inhalt der Vorlesung

Die Vorlesung beinhaltet eine Einführung in die zentralen Gebiete der Theoretischen Informatik: verschiedene Maschinenmodelle, Church'sche These, Berechenbarkeit, Komplexitätstheorie, formale Sprachen, Automaten, probabilistische Algorithmen und Nichtapproximierbarkeit.

Literatur::

  • I. Wegener: Theoretische Informatik, Teubner
  • K. R. Reischuk: Einführung in die Komplexitätstheorie, Teubner
  • U. Schöning: Perlen der Theoretischen Informatik, BI
  • D. P. Bovet und P. Crescenzi: Theory of Computational Complexity, Prentice-Hall


    Skript zu Theoretische Informatik:

  • Inhaltsverzeichnis (04.02.02)
  • Kapitel 1 (19.10.01)
  • Kapitel 2 (24.10.01)
  • Kapitel 3 (07.11.01)
  • Kapitel 4 (16.11.01)
  • Kapitel 5 (28.11.01)
  • Kapitel 6 (28.11.01)
  • Kapitel 7 (13.12.01)
  • Kapitel 8 (19.12.01)
  • Kapitel 9 (18.01.02)
  • Kapitel 10 (04.02.02)
  • Literaturhinweise (04.02.02)


    Vortrag von Michael Bialowons:

  • Zur Geschichte der theoretischen Informatik / Alan Turing
  • Literaturverzeichnis


    Übungen zu Theoretische Informatik:

  • 1. Übung (22.10.01)
  • 2. Übung (29.10.01)
  • 3. Übung (05.11.01)
  • 4. Übung (12.11.01)
  • 5. Übung (19.11.01)
  • 6. Übung (26.11.01)
  • 7. Übung (03.12.01)
  • 8. Übung (10.12.01)
  • 9. Übung (14.01.01)
  • 10. Übung (21.01.01)