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:423.352
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.450
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.835
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:581.114
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.430
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:34932
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:441.103
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:20740
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:24724
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:06892
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:43573
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:13532
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:48610
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:02671
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:14508
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:06390
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:54434
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