Theoretische Informatik

Es sollen theoretische Grundlagen der Informatik vermittelt und diskutiert werden.

Dabei stehen folgende Schwerpunkte im Mittelpunkt:  

Algorithmus

formale Sprachen, Grammatiken, Chomsky-Hierarchie

Entscheidbarkeit, Erkennbarkeit, endliche Automaten, Kellerautomaten, Turingmaschine

reguläre Ausdrücke, Chomsky-Normalform, Pumping Lemmata, Halteproblem 

Berechenbarkeit, LOOP-Programme, WHILE-Programme, Ackermannfunktion, GOTO-Programme, partiell-rekursive Funktionen

Zeitkomplexität, NP-Vollständigkeit, NP-vollständige Probleme (SAT, 3SAT, RUCKSACK)