Vorlesung: Theoretische Informatik

Inhalt:

Mengen, Algorithmus, Grammatik, Chomsky-Hierarchie, Entscheidbarkeit, Erkennbarkeit, endliche Automaten, reguläre Ausdrücke, Pumping Lemma, Chomsky-Normalform, Kellerautomaten, Turingmaschine, Halteproblem, LOOP-Programme, WHILE-Programme, Ackermannfunktion, GOTO-Programme, partiell-rekursive Funktionen, Zeitkomplexität, NP-Vollständigkeit, NP-vollständige Probleme (SAT, 3SAT, RUCKSACK).

Literatur:

U. Schöning: Theoretische Informatik - kurz gefasst. Weitere Literaturangaben erfolgen in der Vorlesung.

Materialien:

Ein Skript zur Vorlesung wird zur Verfügung gestellt.

Leistungsnachweis:

Mündliche Prüfung (Voraussetzung: aktive Teilnahme an den Übungen).

Voraussetzungen:

Grundbegriffe der Mathematik

B.Sc. Mathematik mit Informatik,

M.Sc. Mathematik oder Biomathematik (Spezialvorlesung)