LVs des Lehrstuhls für Efficient Algorithms
Informationstheorie und theoretische Informatik (INHN0013) Campus Heilbronn
| Vortragende/r (Mitwirkende/r) | |
|---|---|
| Nummer | 0000001627 |
| Art | Vorlesung |
| Umfang | 3 SWS |
| Semester | Wintersemester 2025/26 |
| Unterrichtssprache | English |
| Stellung in Studienplänen | Siehe TUMonline |
Teilnahmekriterien
Siehe TUMonline
Anmerkung: -
Anmerkung: -
Beschreibung
Formale Sprachen, Grammatiken, Chomsky Hierarchy.
Reguläre Sprachen: DFA, NFA mit und ohne ε-Transitionen, reguläre Ausdrücke und Übersetzungen dazwischen;
Systeme von Gleichungen zwischen Sprachen; Abschluss unter Booleschen Operationen; Ardens Lemma; Pumping Lemma; Entscheidungsprobleme; Minimierung; Satz von Myhill-Nerode.
CFLs: PDAs und Übersetzungen zw. CFGs und PDAs; Beweis, dass DPDAs schwächer als PDAs sind;
Abschlusseigenschaften; CYK Algorithmus; Pumping Lemma; Chomsky und Greibach Normalformen.
Kontextsensitive Sprachen und LBAs.
Berechenbarkeit: Berechenbarkeit, Entscheidbarkeit, Halb-Entscheidbarkeit, rekursive Aufzählbarkeit und ihre
Beziehungen; Existenz nichtberechenbarer Funktionen; Turing Maschinen, akzeptierte Sprachen und Typ-0
Sprachen; Äquivalenz von Turing Maschinen, While-Programmen und Goto-Programmen; Primitive und μ-rekursive
Funktionen; Reduktionen zwischen Problemen; das Halteproblem; universelle Turing Maschinen; Satz von Rice und
Satz von Rice-Shapiro; Unentscheidbarkeit des Postschen Korrespondenzproblems und wichtiger Probleme auf
CFGs.
Komplexitätstheorie: Zeit und Platzkomplexitätsklassen; Polynomialzeitreduktionen; die Klassen P und NP; NPVollständigkeit;
Satz von Cook; wichtige NP-vollständige Probleme und Reduktionen zwischen ihnen.
Grundlagen der Informationstheorie
Reguläre Sprachen: DFA, NFA mit und ohne ε-Transitionen, reguläre Ausdrücke und Übersetzungen dazwischen;
Systeme von Gleichungen zwischen Sprachen; Abschluss unter Booleschen Operationen; Ardens Lemma; Pumping Lemma; Entscheidungsprobleme; Minimierung; Satz von Myhill-Nerode.
CFLs: PDAs und Übersetzungen zw. CFGs und PDAs; Beweis, dass DPDAs schwächer als PDAs sind;
Abschlusseigenschaften; CYK Algorithmus; Pumping Lemma; Chomsky und Greibach Normalformen.
Kontextsensitive Sprachen und LBAs.
Berechenbarkeit: Berechenbarkeit, Entscheidbarkeit, Halb-Entscheidbarkeit, rekursive Aufzählbarkeit und ihre
Beziehungen; Existenz nichtberechenbarer Funktionen; Turing Maschinen, akzeptierte Sprachen und Typ-0
Sprachen; Äquivalenz von Turing Maschinen, While-Programmen und Goto-Programmen; Primitive und μ-rekursive
Funktionen; Reduktionen zwischen Problemen; das Halteproblem; universelle Turing Maschinen; Satz von Rice und
Satz von Rice-Shapiro; Unentscheidbarkeit des Postschen Korrespondenzproblems und wichtiger Probleme auf
CFGs.
Komplexitätstheorie: Zeit und Platzkomplexitätsklassen; Polynomialzeitreduktionen; die Klassen P und NP; NPVollständigkeit;
Satz von Cook; wichtige NP-vollständige Probleme und Reduktionen zwischen ihnen.
Grundlagen der Informationstheorie
Inhaltliche Voraussetzungen
Diskrete Strukturen, Computational Mathematics I & II