Video-Server > Vorlesungen > Informatik III

Informatik III

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

25:14 Std12.372 Aufrufe26.10.2010
Kamera Anja Michaela Kaiser

Hinweise zum Player

Um die Aufzeichnungen auf dieser Webseite wiedergeben zu können, muss Javascript aktiviert sein. Zudem wird für alle Browser die aktuelle Version des Adobe Flash Players benötigt.



Vorlesungen


Terminologie

Vorlesung Nr. 1

01:33 Std25.10.20102.550 Aufrufe

Vorlesung starten

Inhalt:
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.

Terminologie

Vorlesung Nr. 2

01:17 Std29.10.20101.073 Aufrufe

Vorlesung starten

Inhalt:
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

Automatentheorie und formale Sprachen

Vorlesung Nr. 3

01:31 Std01.11.20101.320 Aufrufe

Vorlesung starten

Inhalt:
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

Automatentheorie und formale Sprachen

Vorlesung Nr. 4

01:28 Std05.11.2010751 Aufrufe

Vorlesung starten

Inhalt:
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.)

Automatentheorie und formale Sprachen

Vorlesung Nr. 5

01:34 Std08.11.20101.039 Aufrufe

Vorlesung starten

Inhalt:
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).

Automatentheorie und formale Sprachen

Vorlesung Nr. 6

01:29 Std15.11.2010617 Aufrufe

Vorlesung starten

Inhalt:
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.

Kellerautomaten

Vorlesung Nr. 7

01:33 Std22.11.2010736 Aufrufe

Vorlesung starten

Inhalt:
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)

Kellerautomaten

Vorlesung Nr. 8

01:26 Std26.11.2010468 Aufrufe

Vorlesung starten

Inhalt:
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.

Kellerautomaten

Vorlesung Nr. 9

01:30 Std30.11.2010468 Aufrufe

Vorlesung starten

Inhalt:
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

Turing Maschinen

Vorlesung Nr. 10

01:31 Std06.12.2010697 Aufrufe

Vorlesung starten

Inhalt:
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.

Turing Maschinen

Vorlesung Nr. 11

01:28 Std10.12.2010422 Aufrufe

Vorlesung starten

Inhalt:
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).

Turing Maschinen

Vorlesung Nr. 12

01:34 Std13.12.2010403 Aufrufe

Vorlesung starten

Inhalt:
Ü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)

Turing Maschinen

Vorlesung Nr. 13

01:31 Std03.01.2011424 Aufrufe

Vorlesung starten

Inhalt:
Ü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

Turing Maschinen und P versus NP

Vorlesung Nr. 14

01:29 Std10.01.2011391 Aufrufe

Vorlesung starten

Inhalt:
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

P versus NP

Vorlesung Nr. 15

01:33 Std17.01.2011351 Aufrufe

Vorlesung starten

Inhalt:
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)

P versus NP

Vorlesung Nr. 16

01:28 Std31.01.2011264 Aufrufe

Vorlesung starten

Inhalt:
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)

Anwendungen

Vorlesung Nr. 17

01:12 Std04.02.2011398 Aufrufe

Vorlesung starten

Inhalt:
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


Impressum · Kontakt© TU Clausthal 2017