Theoretische Informatik 1

Typ

Vorlesung (2V+2Ü)

Veranstalter

Prof. Dr. Jacobo Torán, Dipl.-Inform. Wolfgang Lindner

Inhalt

Die Vorlesung Theoretische Informatik I behandelt die Formalisierung des für die Informatik grundlegenden Konzeptes des Algorithmus. Hierfür werden verschiedene abstrakte Berechnungsmodelle (Turingmaschinen etc.) betrachtet und die Churchsche These begründet. Die Vorlesung endet mit einer Einführung in die Komplexitätstheorie.

Geplante Folgeveranstaltungen

Theoretische Informatik II, Algorithmen, Komplexitätstheorie, Theorielabor, Parallele Algo- rithmen, Rekursionstheorie.

Literatur

• U. Schöning, Theoretische Informatik, kurzgefaßt. Spektrum Akademischer Verlag, 3. Auflage 1997.
• J. Hopcroft und J. Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley, 1979