VIDEO-SERVER

Informatik III

von Prof. Dr. rer. nat. Jürgen Dix

\

Beschreibung

· Grammatiken der Chomsky Hierarchie (Typ3-Typ 0)
· Reguäre Ausdrücke, Satz von Kleene,
· Endliche Automaten (indet.), epsilon Kanten, Pumping Lemma,
· Kellerautomaten, Turingmaschinen
· Busy Beaver, Halteproblem, Reduktionen, aufzaehlbar/entscheidbar
· Random access machines, P/NP

10.2010

Vorlesungsaufzeichnungen

25.10.201001:33:422.936
Terminologie
Einführung; 1. Terminologie: 1.1 Sprache, Grammatik: Alphabet und Wort, Sprache, Reguläre Ausdrücke, Grammatik, einfache Grammatiken, Ableitung, Rechnung, Indeterminismus, Erzeugte Sprache L(G), Äquivalenz, Lemma 1.9, Dycksprache.
29.10.201001:17:541.236
Terminologie
1.2 Warum Sprachen?: Fakt 1.11, Boolesche Ausdrücke, Fakt 1.12, Definition 1.13 (Satisfiability), Graphen, Definition 1.14 (Erreichbarkeitsproblem), Definition 1.15. 1.3 Die Chomsky-Hierarchie: Definition 1.16 (Sprachklassen), kontextfrei (cf), kontextsensitiv (cs), beschränkt, Definition 1.17 (Sprachklassen), Beispiel 1.18. 1.4 Probleme über Sprachen: Definition 1.19 (Problem, Algorithmus), Beispiel 1.20 (Einige Probleme). 1.5 Endlich, unendlich und dann?: Definition 1.21 (Endlich, unendlich), Mögliche Antworten, Lemma 1.22
01.11.201001:31:031.516
Automatentheorie und formale Sprachen
Automatentheorie und formale Sprachen: 2.1 DEAen (e.a.): Darstellung als Graph, Definition 2.1 (Endlicher Automat), Beispiel 2.2, Definition 2.3 (Von einem e.a. akzeptierte Sprache), Beispiel 2.4, Beispiel 2.5, Beispiel 2.6. 2.2 NDEAs (nd e.a.): In-/ Determinierte endliche Automaten, Definition 2.7 (Indeterminierter endlicher Automat), Schreibweisen, Definition 2.8 (Von nd e.a. akzeptierte Sprache), Indeterminismus, Darstellung als Graph, Idee, Lemma 2.9
05.11.201001:28:58895
Automatentheorie und formale Sprachen
2.2 NDEAs (nd e.a.): Lemma 2.9, Theorem 2.10, Beweis, Ein konkretes Beispiel, in-/determinierter Automat, Konstruktion determinierter endlicher Automat, Übungsblatt 2. 2.3 Automaten mit E-Kanten: Definition 2.11 (Automat mit E-Kanten), Definition 2.12 (E-nd e.a. akzeptierte Sprache), Theorem 2.13 (E-nd e.a. gleich mächtig wie nd e.a.)
08.11.201001:34:111.206
Automatentheorie und formale Sprachen
2.3 Automaten mit E-Kanten: Theorem 2.13 (E-nd e.a. gleich mächtig wie nd e.a.), Figure. 2.4 ea = Typ 3: Theorem 2.14 (Satz von Kleene: RAT = L3), Beispiel 2.15. 2.5 Pumping Lemma: (Nicht) reguläre Sprache, Theorem 2.16 (Pumping-Lemma für L3-Sprachen), Beweis 1. Fall / 2. Fall, Nicht rationale Sprachen, Theorem 2.17 (Erweitertes Pumping-Lemma für L3).
15.11.201001:29:34764
Automatentheorie und formale Sprachen
2.5 Pumping Lemma: Theorem 2.17 (Erweitertes Pumping-Lemma für L3), Wiederholung. 2.6 Wortprobleme: Definition 2.18 (erreichbar, co-erreichbar, trim), Figure, Definition 2.19 (Teilautomaten), Definition 2.20, Lemma 2.21, Lemma 2.22, Lemma 2.23, Korollar. 2.7 Rational-Regulär: Theorem 2.24 (Hauptsatz von Kleene), Induktionsanfang, Induktionsschritt.
22.11.201001:33:44875
Kellerautomaten
3.5 PDAs: Definition 3.23 (Push-Down-Automat), Übergangsrelation, Definition 3.24 (Konfiguraion des PDA), Definition 3.25 (Rechnung), Definition 3.26 (von PDA akzeptierte Sprache), Beispiel 3.27, Beispiel 3.28, Theorem 3.29 (finale Zustände -> leerer Keller), Theorem 3.30 (leerer Keller -> finale Zustände), Theorem 3.31 (PDA akzeptieren L2), Lemma 3.32 (cf-Grammatik -> PDA) und Beweis, M. 3.4 Pumping-Lemma für cf: Theorem 3.21 (Pumping Lemma für cf Sprachen), Theorem 3.22 (Ogdens Lemma)
26.11.201001:26:20551
Kellerautomaten
3.4 Pumping-Lemma für cf: Theorem 3.21 (Pumping Lemma für cf Sprachen), Beweis. 3.5 PDAs: Theorem 3.31 (PDA akzeptieren L2), Lemma 3.32 (cf-Grammatik -> PDA), Idee, M, n -> n+1, Regel, Lemma 3.34 (PDA -> cf-Grammatik), Variablen, Übergänge, Kombinationen, Durchlaufene Zustände, Ableitung, Grammatik (-Regeln). 3.6 Abschlusseigenschaften: Theorem 3.36 (Abschlusseigenschaften von L2), Theorem 3.37. 3.1 Ableitungsbäume: Definition 3.1 (Ableitungsbaum zu einer Grammatik), Ablesen eines Wortes, Idee, Theorem 3.2, Figure, Beispiel 3.3, Definition 3.4 (Linksableitung), Definition 3.5 (Mehrdeutigkeit), Beispiel 3.6, Beispiel 3.7.
30.11.201001:30:24539
Kellerautomaten
3.2 Umformungen: Definition 3.8 ((co-) erreichbare, nutzlose Symbole), Theorem 3.9 (cf-Grammatik ohne nutzlose Symbole), Algorithmus und Grammatik co-erreichbarer Variablen, Theorem 3.10 (Normalform), Definition 3.11 (E-Regel, nullbare Variablen), Theorem 3.12 (E-Regeln sind eliminierbar), Induktionsanfang und Induktionsschritt, Regel, Beispiel 3.13, Lemma 3.14, Definition 3.15 (Kettenproduktion), Theorem 3.16 (Kettenproduktionen sind eliminerbar), Theorem 3.17 (Normalform für cf. Grammatiken). 3.3 Normalformen: Definition 3.18 (Chomsky-Normalform), Theorem 3.19 (Chomsky-Normalform), Definition 3.20 (Greibach-Normalform). 3.7 Wortprobleme: Das Wortproblem und L3/L2, Chart-Parsing, Beispiel 3.38
06.12.201001:31:06773
Turing Maschinen
4. Turing Maschinen (re): Berechenbarkeit und Komplexität, Robustheit, Ausblick und Eigenschaften von Turing-Maschinen. 4.1 DTM’n: Definition 4.1 (Turing-Maschine (DTM)), Funktion, Band einer DTM ist einseitig unbeschränkt, Beispiel 4.2 (a durch b ersetzen), Beispiel 4.2 (L), Beispiel 4.4 (Copy), Fakt 4.5 (Übergangsfunktion nicht überall definiert), Beispiel 4.6 (Print n), 4 Elemente, Definition 4.7 (Konfiguration einer DTM), Definition 4.8 (Nachfolgekonfiguration), Definition 4.9 (Eingabe), Definition 4.10 (Halten, Hängen), Definition 4.11 (Rechnung), Beispiel 4.12 (Replace(a)), Definition 4.13 (TM-berechenbar), Definition 4.14 (Von einer DTM akzeptierte Sprache), Definition 4.15 (TM part, TM), Kodieren. 4.2 Flußdiagramme: Graphische Darstellung der Übergangsfunktion einer DTM, Elemente, Beispiel 4.16, Beispiel 4.17 (R), Beispiel 4.18 (L), Beispiel 4.19 (Copy), Sie rechnet so.
10.12.201001:28:43475
Turing Maschinen
4.2 Flußdiagramme: Beispiel 4.20 (SR), Beispiel 4.21 (SL). 4.3 Varianten von TMn: Turing-Maschine die nie hängen bleibt, Definition 4.22 (zw-DTM), Theorem 4.23 (Simulation von zw-DTM durch DTM), Beweis, Definition 4.24 (DTM mit k Halbbändern, k-DTM), Theorem 4.25 (Simulation von k-DTM durch DTM). 4.4 NTMn: Definition 4.26 (NTM), Definition 4.27 (Nachfolgekonfiguration, Rechnung), Definition 4.28 (NTM: Halten, Hängen, Akzeptieren), Haltekonfigurationen, Beispiel 4.29, Beispiel 4.30 (Composite), Theorem 4.31 (Simulation von NTM durch DTM). 4.5 Universelle DTMn: Übergänge, Beispiel 4.32 (Gödelisierung).
13.12.201001:34:13447
Turing Maschinen
Übungsblätter 4 und 5. 4.8 Unentscheidbar: Definition 4.43 (Busy Beaver), Theorem 4.44 (BB ist nicht berechenbar), Beweis. 4.7 DTM Typ 0: Satz 4.39 (Rekursiv aufzählbar = Typ 0), Lemma 4.40 (DTM akzeptierte Sprachen vom Typ 0), Beweis, Lemma 4.41 (Rekursiv aufzählbar impliziert Typ 0), Beispiel 4.42 (TM mit Begrenzern), zwei- und dreistöckige Symbole, Ableitung. 4.6 Entscheidbar/Aufzählbar: Akzeptieren und Entscheiden, Definition 4.33 (Entscheidbar), Definition 4.34 (Akzeptierbar), Definition 4.35 (Rekursiv Aufzählbar (r.e.)), Satz 4.36 (Akzeptierbar = Rekursiv Aufzählbar)
03.01.201101:31:48497
Turing Maschinen
Übungsblatt 6. 4.6 Entscheidbar/Aufzählbar: Satz 4.37 (Entscheidbar vs. Akzeptierbar). 4.8 Unentscheidbar: Definition 4.45 (Probleme über DTMn als Sprachen), Definition 4.46 (Jede Zahl ist Gödelnummer), Definition 4.47 (Allgemeines Hauptproblem), Definition 4.48 (Spezielles Halteproblem), Definition 4.49 (Null-Halteproblem), Definition 4.50 (Leerheitsproblem), Definition 4.51 (Totalitätsproblem), Definition 4.52 (Gleichheitsproblem), Definition 4.53 (Entscheidungsproblem), Satz 4.54 (Spezielles Halteproblem ist unentscheidbar), Beweis, Satz 4.55 (Akzeptierbarkeit von H), Satz 4.56 (H ist nicht aufzählbar), totale und berechenbare Funktion, Definition 4.57 (Reduktion), Satz 4.59 (Unentscheidbarkeit von H0), Per Reduktion Unentscheidbarkeit von Problemen zeigen
10.01.201101:29:02482
Turing Maschinen und P versus NP
Turing Maschinen: Definition 4.57 (Reduktion). P versus NP: Definition 5.1 (NTIME(T(n)), DTIME(T(n))), Definition 5.2 (NSPACE(S(n)), DSPACE(S(n))), Halten, hängen nach n Schritten, Stoppen nach n Schritten, Theorem 5.3 (Bandkompression), Theorem 5.4 (Zeitbeschleunigung), Lemma 5.5 (Wachstumsrate von DTIME, DSPACE), Definition 5.6 (P, NP, PSPACE). Übungsblatt 7
17.01.201101:33:14402
P versus NP
5.1 Die Struktur von PSPACE: Lemma 5.5 (Wachstumsrate von DTIME, DSPACE), Definition 5.6 (P, NP, PSPACE), Sudoku, Theorem 5.7 (Charakterisierung von NP), Theorem 5.8 (Existenz von schwersten Problemen), Definition 5.9 (Polynomial-Zeit-Reduzibilität), Lemma 5.10 (Polynomial-Zeit-Reduktionen)
31.01.201101:28:06293
P versus NP
5.1 Die Struktur von PSPACE: Theorem 5.7 (Charakterisierung von NP). 5.2 Vollständige und harte Probleme: Definition 5.11 (Vollständig, Hart (Schwer)), Theorem 5.12 (NP-vollständige Probleme), Definition 5.13 (co-NP). 5.3 Beispiele: Beispiel 5.14 (NP vollständige Beispiele), Definition 5.15 (Varianten von Hamilton Circle), Definition 5.16 (Maximale Clique: LCliquek), Definition 5.17 (k-colorability: LColork), Definition 5.18 (SAT, k-CNF, k-DNF), Theorem 5.19 (NP-vollständige Probleme), Definition 5.20 (Vertex Cover: LVertexk), Beispiel 5.21 (CNF-SATpol Cliquek), Beispiel 5.22 (hamdir pol Hamundir), Beispiel 5.23 (hamundir pol Hamcostkr)
04.02.201101:12:54410
Anwendungen
6.1 Praktische Bedeutung: Theoretische Komplexität vs. praktische Anwendbarkeit, Compilerbau, Lexikalische Analyse, Syntaxanalyse, Reguläre Ausdrücke, Kleine Automaten. 6.2 Satz von Myhill-Nerode: Definition 6.1, Lemma 6.2, Beispiel 6.3, Theorem 6.4 (Satz von Myhill-Nerode), Beweis. 6.3 Der Minimalautomat: Definition 6.5 (ML, der zu L passende Automat), Äquivalenz, Theorem 6.6 (Minimalität von ML), Beweis