Theoretische Grundlagen der Informatik

Aktuelles

Zum Üben: Klausur 2 SS17

Lösung Übungsblatt 12 Aufgabe 4

Klausureinsicht voraussichtlich 26./27. Juli

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 folgenden Montag 24:00 Uhr 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 017.04.2018keine Abgabe
Übungsblatt 117.04.201823.04.2018 24:00 Uhr
Übungsblatt 224.04.201830.04.2018 24:00 Uhr
Übungsblatt 301.05.201807.05.2018 24:00 Uhr
Übungsblatt 408.05.201814.05.2018 24:00 Uhr
Übungsblatt 514.05.201821.05.2018 24:00 Uhr
Übungsblatt 622.05.201828.05.2018 24:00 Uhr
Übungsblatt 729.05.201804.06.2018 24:00 Uhr
Übungsblatt 805.06.201811.06.2018 24:00 Uhr
Übungsblatt 911.06.201818.06.2018 24:00 Uhr
Übungsblatt 1019.06.201825.06.2018 24:00 Uhr
Übungsblatt 1125.06.201802.07.2018 24:00 Uhr
Übungsblatt 1203.07.201809.07.2018 24:00 Uhr
Übungsblatt 1310.07.201816.07.2018 24:00 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