Theoretische Grundlagen der Informatik

Theoretische Grundlagen der Informatik

Dozent

Prof. Dr. Dietmar Saupe

Termine (Vorlesung)

Inhalt

Die Vorlesung gibt eine Einführung in die theoretischen Grundlagen der Informatik. Folgende Themen werden u.a. behandelt: 1. Formale Sprachen und Automatentheorie Chomsky-Hierarchie (reguläre, kontextfreie, Typ0-Sprachen, reguläre Ausdrücke) Grammatiken (Typen, Eindeutigkeit, Abgeschlossenheit) Automatenmodelle (endliche Automaten, Kellerautomaten, Turingmaschinen) 2. Entscheidbarkeit und Berechenbarkeit Entscheidbarkeit, Aufzählbarkeit Universelle Turingmaschine, Diagonalisierung, Halteproblem Berechenbarkeit, µ-rekursive Funktionen, Church/Turing-These 3. Komplexitätstheorie Optimierungs- und Entscheidungsprobleme Codierung Klassen P und NP, NP-Vollständigkeit Parametrisierte Komplexität

Weitere Details zum Inhalt der Vorlesung im LSF und auf der Webseite zur Vorlesung.

Episoden

2014/04/24 (Do) - Grammatiken, Chomsky - Hierarchie, verschiedene Sprachen

2014/04/28 (Mo) - Wortproblem fuer kontextsensitive Sprachen, Mehrdeutige Grammatiken, Backus-Natur Form, Endliche Automaten und regulaere Sprachen

2014/04/29 (Di) - Uebungsaufgaben, nicht deterministische endliche Automaten, Satz von Rabin, Scott, Beispiel, Zusammenfassung 

2014/05/01 (Do) - keine Aufzeichnung (Tag der Arbeit)

2014/05/05 (Mo) - Regulaere Ausdruecke, Satz von Kleene, Pumping Lemma

2014/05/06 (Di) - Pumping Lemma, Aequivalenzrelationen und Miniautomaten, Myhill-Nerode-Relation 

2014/05/08 (Do) - Aequivalenz-Relation, Aequivalenzklassenautomat, Wohldefiniertheit

2014/05/13 (Di) - Algorithmus Minimalautomat, Abschlusseigenschaften, Entscheidbarkeit bei regulaeren Sprachen

2014/05/15 (Do) - kontextfreie Sprachen, Pumping-Lemma, Abschlusseigenschaften, Komplimentbildung

2014/05/20 (Di) - CYK-Algorithmus, Automaten, Kellerautomaten

2014/05/22 (Do) - Kellerautomaten, deterministisch-kontextfreie Sprachen, Abgeschlossenheitseigenschaften, Entscheidbarkeit

2014/05/27 (Di) - Turing-Maschine, linear beschraenkte Turing-Maschinen, Algorithmus-Defintion, Grammatik-Regeln

2014/05/29 (Do) - keine Aufzeichnung (Christi Himmelfahrt)

2014/06/03 (Di) - Kuroda Normalform, Zusammenfassung 1. Abschnitt, intuitive Berechenbarkeit, Turing-Berechenbarkeit, Mehrband-TM, Notation

2014/06/05 (Do) - Folien, formale Definition von Berechenbarkeit, DIV und MOD, Goto/While/TM/Loop, Goto Programm P2, Endphase

2014/06/10 (Di) - Ackermann-Funktion, Lemma A-E, Bew. durch strukturelle Induktion, Berechnung via Stick, Implementierung der Stack-Operationen

2014/06/12 (Do) - Ackermann-Fnkt. - Berechenbarkeit, Halteproblem/ Unentscheidbarkeit/ Reduzierbarkeit, Aequivalenzen, Evaluation

2014/06/17 (Di) - Video zum Halteproblem, spezielles Halteproblem, weitere unentscheidbare Probleme, allgemeines Halteproblem, Halteproblem auf leerem Band, Satz von Rice

2014/06/19 (Do) - keine Aufzeichnung (Fronleichnam)

2014/06/24 (Di) - Komplexitaetstheorie, Komplexitaetsklassen, Komplexitaetsklasse P, Effiziente Algorithmen, P-NP-Problem, Ueberblick, NP-Vollstaendigkeit

2014/06/26 (Do) - Postsches Korrespondenz-Problem, Gruppen: Kopierregeln, Ueberfuehrungsregeln, Loeschregeln

2014/07/01 (Di) - Wiederholung der Begriffe, Nicht-determ. TM, Reduzierbarkeit, Beweisskizze NP-Haerte

2014/07/03 (Do) - Uebungs-Sitzung: Wiederholung, Klausur 2011 Aufg. 1, Aufg. 2, Aufg. 3, Klausur 2010 Aufg. 2, Aufg. 4, Beweis-Wiederholung

2014/07/08 (Di) - SAT-Problem, weitere NP-vollst. Probleme, konjunktive Normalform, 3 KNF-SAT

2014/07/10 (Do) - Uebungs-Sitzung 2: K 1 2011 Aufg. 4, K 1 SS 11 Aufg. 6, subset sum (ss), Partition, NP-Haerte

2014/07/15 (Di) - Baum NP-vollstaendiger Probleme, 3 SAT, SETCOVER, CLIQUE

2014/07/17 (Do) - RUCKSACK-Problem, PARTITION, BINPACKING, Uebersicht NP-vollstaendige Probleme

2014/07/22 (Di) - Wiederholung (Fragen), Satz von Goedel

2014/07/24 (Do) - keine Aufzeichnung