Serviceverbund KIM

Streaming Server

Login |
 
 

Theoretische Grundlagen der Informatik

Dozent

Prof. Dr. Dietmar Saupe

Termine (Vorlesung)

Di 08:15 - 09:45 A 701
Do 08:15 - 09:45 A 703

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/22 (Di) - Organisatorisches, Übersicht Themen, Beispiele zum Vorlesungsstoff

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