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: titut@dbruhn.de
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
- 28.10.2009:
Automaten, Grammatiken, Reguläre Ausdrücke
Folien, Lösungen - 04.11.2009:
Potenzmengenkonstruktion, Minimalautomaten
Folien, Lösungen - 11.11.2009:
Chomsky-Normalform, CYK-Algorithmus, Pumping Lemma
Folien, Lösungen - 18.11.2009:
Turingmaschinen, Pumping Lemma für kontextfreie Sprachen
Folien, Lösungen - 25.11.2009:
Gödelnummern, Entscheidbarkeit, PCP
Folien, Lösungen - 02.12.2009:
Entscheidbarkeit, Berechenbarkeit, Aufzählbarkeit
Folien, Lösungen - 09.12.2009:
Kolmogorow Komplexität, Prädikatenlogik
Folien, Lösungen - 16.12.2009:
Komplexitätstheorie
Folien, Lösungen - 13.01.2010:
Komplexitätstheorie, NP-vollständig, NP-schwer
Folien, Lösungen - 20.01.2010:
Komplexitätstheorie, Traveling Salesman, Clique, P vs. NP
Folien, Lösungen - 27.01.2010:
Entropie, Informationsgehalt, Huffman Kodierung
Folien, Lösungen - 03.02.2010:
Kanalkapazität, Codierungen, Huffmann-Codierung
Folien, Lösungen - 10.02.2010:
Wiederholung von wichtigen Dingen
Folien, Lösungen