Modulnummer:

1101120

Leistungspunkte:

6 ECTS

Lehrveranstaltungen:

• Vorlesung Einführung in die Theoretische Informatik (3 SWS)
• Übung Einführung in die Theoretische Informatik (1 SWS)

Prüfung:

Klausur (120 min) oder mündliche Prüfung (20 min)

Prüfungsvorleistungen:

Lösen von Übungsaufgaben

Inhalt:

Berechenbarkeit:

• Turing-Maschinen und weitere Formalierungen des Algorithmenbegriffs
• Church-sche These
• Entscheidbarkeit, Aufzählbarkeit
• Beweismethode Diagonalisierung
• Unentscheidbarkeit des Halteproblems
• Beweismethode Reduktion
• Weitere unentscheidbare Probleme (insbesondere Post-sches Korrespondenzproblem, Satz von Rice)
• Umgang mit unentscheidbaren Problemen

Komplexität:

• O-Notation, Eingabekodierung
• Zeitkomplexität, Speicherplatzkomplexität
• Komplexitätsklassen, insbesondere P, NP, PSPSACE, EXPTIME
• Das Problem P =? NP
• NP-Vollständigkeit, Beweismethode Polynomialzeitreduktion
• Wichtige NP-vollständige Probleme
• Umgang mit schwer lösbaren Problemen

Formale Sprachen:

• Formale Sprache, Grammatik
• Chomsky-Hierarchie
• Maschinenmodelle (linear beschränkter Akzeptor, Kellerautomat, endlicher Automat
• Normalformen
• Reguläre Sprachen (Akzeptierung, Pumping-Lemma,  Myhill/Nerode-Index, reguläre Ausdrücke)
• Kontextfreie Sprachen (Akzeptierung, Pumping-Lemma, CYG-Algorithmus)
• Moore-Automaten und Mealy-Automaton