Theoretische Grundlagen der Informatik

Aktuelles

Zum Üben:
Klausur 1 2018 
Klausur 2 2018

Inhalte

Die Vorlesung gibt eine Einführung in die theoretischen Grundlagen der Informatik. Folgende Themen werden u.a. behandelt:

  • Formale Sprachen und Automatentheorie
    • Chomsky-Hierarchie
      (reguläre, kontextfreie, Typ0-Sprachen, reguläre Ausdrücke)
    • Grammatiken (Typen, Eindeutigkeit, Abgeschlossenheit)
    • Automatenmodelle
      (endliche Automaten, Kellerautomaten, Turingmaschinen)

  • Entscheidbarkeit und Berechenbarkeit
    • Entscheidbarkeit, Aufzählbarkeit
    • Universelle Turingmaschine, Diagonalisierung, Halteproblem
    • Berechenbarkeit, µ-rekursive Funktionen, Church/Turing-These

  • Komplexitätstheorie
    • Optimierungs- und Entscheidungsprobleme
    • Codierung
    • Klassen P und NP, NP-Vollständigkeit
    • Parametrisierte Komplexität
Vorlesung im Zeus

Die Vorlesung wurde im SS2014 durch den Serviceverbund KIM aufgezeichnet. Die Aufzeichnungnen sind unter folgendem Link verfügbar:

Aufzeichnung der Vorlesung

Folien zur Vorlesung. Achtung, diese Foliensammlung deckt weder die gesamte Vorlesung noch das gesamte Skript ab!

Ergänzungen zur Vorlesung (aktuelle Version vom 11.05.2016). Die Vorlesung beruht hauptsächlich auf dem Hochschultaschenbuch "Theoretische Informatik – kurzgefasst" von Uwe Schöning (5. Auflage, 2008, Spektrum Akademischer Verlag). Diese Ergänzungen beinhalten eine kleine Sammlung von Beispielen, Vertiefungen oder weitere Erläuterungen, die in der Vorlesung behandelt werden und in dem Buch nicht oder nicht so ausführlich dargestellt sind. Sie bilden daher keinen zusammen hängenden Text und dienen auch keinesfalls als Ersatz des Buchs.

Übungsblätter

Übungsblätter werden immer am Dienstag auf der Vorlesungswebseite als PDF-Datei zur Verfügung gestellt.

Die Abgabe der Lösung als LaTeX erzeugte PDF-Datei ist per SVN-Repository bis zum Donnerstag 24:00 Uhr in der Woche darauf möglich.

Weitere, organisatorische Informationen zum SVN-Repository finden Sie unter: read.me 
Falls Probleme beim Öffnen dieses Links oder bei der Benutzung des SVN-Repository auftreten, schreiben Sie bitte eine E-Mail an alexander.artiga-gonzalez@uni-konstanz.de.

LaTeX-Kompendium finden Sie unter LaTeX-Kompendium und eine LaTeX-Vorlage (nicht obligatorisch) unter template_TI.tex.zip

Viele Aufgaben müssen mit der Software jflap erstellt werden. Ein entsprechender Hinweis steht dann bei den Aufgaben.

AusgabeAbgabe
Übungsblatt 116.04.201921.04.2019, 24 Uhr
Übungsblatt 216.04.201925.04.2019, 24 Uhr
Übungsblatt 323.04.201902.05.2019, 24 Uhr
Übungsblatt 430.04.201909.05.2019, 24 Uhr
Übungsblatt 507.05.201916.05.2019, 24 Uhr
Übungsblatt 614.05.201923.05.2019, 24 Uhr
Übungsblatt 722.05.201930.05.2019, 24 Uhr
Übungsblatt 827.05.201906.06.2019, 24 Uhr
Übungsblatt 905.06.201913.06,2019, 24 Uhr
Übungsblatt 1012.06.201920.06.2019, 24 Uhr
Übungsblatt 1118.06.201927.06.2019, 24 Uhr
Übungsblatt 1225.06.201904.07.2019, 24 Uhr
Übungsblatt 1304.07.201911.07.2019, 24 Uhr
Übungsblatt 1411.07.201917.07.2019, 24 Uhr

Klausurzulassung

Für die Teilnahme an der Klausur ist das Erreichen von mindestens 60% der möglichen Punkte aus den Übungsaufgaben erforderlich. Die Teilnahmeerlaubnis zur Klausur behält auch für Klausuren in zukünftigen Semestern ihre Gültigkeit, falls an der Klausur nicht teilgenommen oder die Klausur nicht bestanden wird. 

Literatur

Zum Gödelschen UnvollständigkeitssatzGoedel's Incompleteness Theorem and the Emergence of AI