Einführung in die Theoretische Informatik
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