Online-Vorlesungen Logo

Suchbegriff

Informatik I

Informatik II

Informatik III

Künstliche Intelligenz

Programmierkurs I

Grundlagen der Programmierung

Betriebssystemarchitektur

Betriebssystemarchitektur II

Operating Systems and System Programming

Linux-Crashkurs

Seite 1 von 4

>>

Informatik III

Informatik / Grundvorlesung

Universität: TU Clausthal
Dozent: Prof. Dr. rer. nat. Jürgen Dix
Aufzeichnungsdatum: Wintersemester 2010/2011
Sprache: Deutsch


Link zur Vorlesung!


Inhalt:

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

Online Vorlesungen Bottom Line Grafik
Sitemap