Vorlesung Theoretische Informatik für Ingenieur-Informatiker und Berufs- und Sekundarschullehrer im berufsbegleitenden Studium

Sommersemester 2006

Lehrbeauftragter:	Dr. Ralf Stiebe
Semester:	Grundstudium, 2. Semester
Wochenstunden:	2+1+0
Zuhörerkreis:	Ing-IF 05, BS Berufsschullehrer 04, BS Sekundarschullehrer 05
Voraussetzungen:

Ing-IF: Mündliche Prüfung (zu dieser Vorlesung und zur Vorlesung Logik)
Termin: 21.9.2006; Einschreibung ab sofort im Prüfungsamt
Konsultation: am 14.9.2006 um 13:15 Uhr im Raum 29-E037
Lehrer: Klausur zum Erwerb eines unbenoteten Übungsscheines.
Termin: Konsultation am 12.9.2006; Klausur am 19.9.2006; jeweils um 9:30 Uhr im Raum 22A-203
Die Klausuren sind endlich korrigiert und erfreulicherweise haben alle den Schein erreicht.

Modelle der Berechenbarkeit
Turingmaschinen, Loop-Programme, While-Programme
Entscheidbarkeit
Entscheidungsprobleme, Halteproblem für Turingmaschine und seine Unentscheidbarkeit
Komplexitätstheorie
Zeit- und Platzkomplexität, Komplexitätsklassen, NP-Vollständigkeit
Formale Sprachen
Regelgrammatiken, Chomsky-Hierarchie, endliche Automaten, reguläre Ausdrücke, Kellerautomaten, Pumping-Lemmata für reguläre und kontextfreie Sprachen
Das Wichtigste in Kürze (PDF-Datei)

Skript (PDF-Format)
Ergänzung zum Skript: Weitere NP-vollständige Probleme
U. Schöning: Theoretische Informatik - kurzgefaßt. Spektrum Akademischer Verlag, 1994.

Last modified: Wed Nov 01 11:19:20 MEZ 2006