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)
- Chomsky-Hierarchie
- 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.
Ausgabe | Abgabe | |
---|---|---|
Übungsblatt 0 | 17.04.2018 | keine Abgabe |
Übungsblatt 1 | 17.04.2018 | 23.04.2018 24:00 Uhr |
Übungsblatt 2 | 24.04.2018 | 30.04.2018 24:00 Uhr |
Übungsblatt 3 | 01.05.2018 | 07.05.2018 24:00 Uhr |
Übungsblatt 4 | 08.05.2018 | 14.05.2018 24:00 Uhr |
Übungsblatt 5 | 14.05.2018 | 21.05.2018 24:00 Uhr |
Übungsblatt 6 | 22.05.2018 | 28.05.2018 24:00 Uhr |
Übungsblatt 7 | 29.05.2018 | 04.06.2018 24:00 Uhr |
Übungsblatt 8 | 05.06.2018 | 11.06.2018 24:00 Uhr |
Übungsblatt 9 | 11.06.2018 | 18.06.2018 24:00 Uhr |
Übungsblatt 10 | 19.06.2018 | 25.06.2018 24:00 Uhr |
Übungsblatt 11 | 25.06.2018 | 02.07.2018 24:00 Uhr |
Übungsblatt 12 | 03.07.2018 | 09.07.2018 24:00 Uhr |
Übungsblatt 13 | 10.07.2018 | 16.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
- 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