Theoretische Informatik und Grundlagen der KI

Bereich

4 SWS Vorlesung im Bereich Informatik III (Theoretische Informatik)
Wahlpflichtvorlesung im Gebiet syntaktische und operationelle Beschreibungen

Zeit und Ort

Donnerstag, 8.45-10.00 Uhr, Hörsaal MI HS3
Freitag, 8.45-10.00 Uhr, Hörsaal MI HS2
Beginn: Freitag, 28.04.2006, 8:45 Uhr

Klausur

tba.

Übung

2 SWS Übung zur Vorlesung
Übungsleiter: Dipl.-Ing. Christian Schallhart
Zeit: Donnerstag, 16:30
Raum: 03.09.014

Übungen Download

Typ Blatt Download Blatt 1 O-Notation, Palindrome auf TMs, Klassen und Probleme, Festes Wortproblem hier klicken... Blatt 2 Zeit- und Platzkonstruierbarkeit, Platzbeschraenkte Berechnungen, Membership von Problemen, Übersetzung von Problemen hier klicken... Blatt 3 Logspace Reduktionen, DSPACE(n)!=P, Reduktionen hier klicken... Blatt 4 Upward Translation, Abschlusseigenschaften, Alternation hier klicken...

Hörerkreis

Studierende im Hauptstudium der Informatik
Studierende mit Nebenfach Informatik

Voraussetzungen

Stoff des Informatik-Grundstudiums, insbesondere TGI und die Vorlesung Informatik IV

Inhalt

Inhalt der Vorlesung

Literatur

Literatur:

[1]

J. L. Balcázar, J. Díaz, and J. Gabarró. Structural Complexity I, volume 11 of EATCS Monographs on Theoretical Computer Science. Springer, 1988.

[2]

J. L. Balcázar, J. Díaz, and J. Gabarró. Structural Complexity II, volume 22 of EATCS Monographs on Theoretical Computer Science. Springer, 1990.

[3]

J. E. Hopcroft and J. D. Ullman. Formal Languages and Their Relation to Automata. Addison-Wesley, 1968.

[4]

J. E. Hopcroft and J. D. Ullman. Introduction to Automata Theory, Languages and Computation. Addison-Wesley, 1979.

[5]

C. H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994.

[6]

K. R. Reischuk. Einführung in die Komplexitätstheorie. Teubner, 1990.

Weiterführende Literatur:

[1]

L. A. Hemaspaandra and M. Ogihara. The Complexity Theory Companion. EATCS Monographs in Theoretical Computer Science. Springer, 2002.

[2]

K. Wagner and G. Wechsung. Computational Complexity. Mathematics and its applications (East Europeans series). VEB Deutscher Verlag der Wissenschaften, Berlin, 1986.

Sprechstunde

nach Vereinbarung