Theoretische Grundlagen der Informatik: Tutorium 09 + 11

Organisatorisches

Dies ist die Webseite der Tutorien Nummer 9 und 11 von Dominik Bruhn zu der Vorlesung Theoretische Grundlagen der Informatik, die im Wintersemester 2009/2010 vom IKS am KIT gehalten wird. Die Tutorien finden Mittwochs um 15:45 in Raum -133 im AVG und 17:15 im Raum SR-107 des Informatikgebäudes statt. Auf dieser Homepage findet man im Anschluss an das Tutorium die Beamer-Folien. Die hier zum Download angebotenen Lösungen entsprechen nicht hundertprozentig den im Tutorium vorgestellten.

Kontakt

Kontakt per Mail:

Literatur

Introduction to the Theory of Computation von Michael Sipser (gebundene Ausgabe)
Introduction to the Theory of Computing von Michael Sipser (Taschenbuch)
Algorithmen - Eine Einführung von Cormen et al.
Introduction to Algorithms von Cormen et al.

Folien

Nr	Datum	Thema	Folien	Lösungen
1	28.10.2009	Automaten, Grammatiken, Reguläre Ausdrücke	download	download
2	04.11.2009	Potenzmengenkonstruktion, Minimalautomaten	download	download
3	11.11.2009	Chomsky-Normalform, CYK-Algorithmus, Pumping Lemma	download	download
4	18.11.2009	Turingmaschinen, Pumping Lemma für kontextfreie Sprachen	download	download
5	25.11.2009	Gödelnummern, Entscheidbarkeit, PCP	download	download
6	02.12.2009	Entscheidbarkeit, Berechenbarkeit, Aufzählbarkeit	download	download
7	09.12.2009	Kolmogorow Komplexität, Prädikatenlogik	download	download
8	16.12.2009	Komplexitätstheorie	download	download
9	13.01.2010	Komplexitätstheorie, NP-vollständig, NP-schwer	download	download
10	20.01.2010	Komplexitätstheorie, Traveling Salesman, Clique, P vs. NP	download	download
11	27.01.2010	Entropie, Informationsgehalt, Huffman Kodierung	download	download
12	03.02.2010	Kanalkapazität, Codierungen, Huffmann-Codierung	download	download
13	10.02.2010	Wiederholung von wichtigen Dingen	download	download