Berechenbarkeit und Entscheidbarkeit (WS 95/96)

Prof. J. Esparza

Bereich: Informatik III, VO 3+1

Zeit und Ort:
Montag, 12.00 - 13.00 Uhr (Raum 0602)
Mittwoch, 11.00 - 13.00 Uhr (Raum 0220)

Erster Vorlesungstermin:
Montag, 6.11.1995

Inhalt:
1. Das Kardinalitätsargument
2. Drei Programmiersprachen
3. Rekursive Funktionen
4. Turingmaschinen
5. Entscheidbarkeit

Voraussetzungen: Vordiplom

Übungsschein: Ja, bei bestandener Klausur. [ zur Übungsseite ]

Skript: berechenbarkeit.ps.gz

Literatur:
E. Engeler, P. Läuchli: Berechnungstheorie für Informatiker, Teubner 1988.
U. Schöning: Theoretische Informatik kurz gefaßt, BI Wissenschaftsverlag 1992.
J.E. Hopcroft, J.D. Ullman: Introduction to Automata Theory, Languages and Compilation, Addison-Wesley 1979. Dt. Übersetzung: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie, Addison-Wesley 1988. (Das ist die erste Auflage. Die überarbeitete Auflage ist besser übersetzt!)
F.C. Hennie: Introduction to Computability, Addison-Wesley 1977.
G.S. Boolos, R.C. Jeffrey: Computability and Logic, 3rd ed., Cambridge University Press 1989.
M. Davis: Computability and Unsolvability, McGraw-Hill 1958.


Zurück zu den Lehrveranstaltungen am Lehrstuhl Brauer