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

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

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.

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

• U. Schöning, Theoretische Informatik - kurzgefasst, Spektrum Akademischer Verlag.
• P. Linz, An Introduction to Formal Languages and Automata, Jones & Bartlett Learning.
• A. Asteroth, Ch. Baier, Theoretische Informatik, Pearson Studium.
• K. Erk, L. Priese Theoretische Informatik: Eine umfassende Einführung, Springer Verlag.
• J. E. Hopcroft, R. Motwani, J. D. Ullman, Einführung in die Automatentheorie, formale Sprachen und Komplexitätstheorie, Pearson Studium.
• I. Wegener, Theoretische Informatik - eine algorithmische Einführung, B. G. Teubner Verlag.
• U. Brandes, Vorlesungsmanuskript vom SS 2006

Zum Gödelschen Unvollständigkeitssatz: Goedel's Incompleteness Theorem and the Emergence of AI