Theoretische Grundlagen der Informatik

Aktuelles

Die Vorlesung findet digital statt, bis der reguläre Lehrbetrieb an der Universität wieder aufgenommen wird. Dazu wird wöchentlich im SVN als Lehrprogramm angegeben:

• Zwei Vorlesungsaufzeichnungen 
• Zugehörige Seiten in dem Manuskript und anderen Quellen
• Übungsaufgaben (mit Abgabe)
• Online-Besprechung der vergangenen Übungsaufgaben

Für die Tellnahme an der Veranstaltung Isl die Anmeldung In ZEuS erforderllch.
Es ist dabel die Email-Adresse vorname.nachname@uni-konstanz.de zu verwenden!
Frist: Dienstag, 21.04.2020.

Die Studieninhalte werden über Videoaufzeichnungen der Vorlesungen und online Übungen (Videokonferenz) angeboten. Die wöchentliche Angabe der jeweiligen Inhalte, sowie die Einstellung, Abgabe und Rückgabe der Korrekturen von Übungsaufgaben wird über SVN abgewickelt. Dort ist auch ein Vorlesungsskript (nur für die private Verwendung) erhältlich.
Die Anmeldung bei ZEuS mit der uni-konstanz.de Email-Adresse ist für das Setzen der entsprechenden Rechte im SVN und die Einladungen für digitale Meetings erforderlich.

Studierende erhalten (spätestens am Mittwoch, 22.04.2020, morgens) eine Email mit den lnformationen zum Zugang zum SVN und die Einladung zur Videokonferenz der ersten Übung am Mittwoch, 22.04.2020, 15:15h.

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

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

Skript zur Vorlesung. Als Skript dient das Buch "Theoretosche Informatik - kurz gefasst" von U. Schöning. Wir stellen eine vom Autor zur Verfügung gestellte elektronische Version im SVN zum Abruf bereit.

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.

Program

• Woche vom 20.-26.04.2020 (alle weiteren Wochen dann im SVN): 
  • Di: Vorlesung 1
  • Mi, 15:15h, Übung (online)
  • Do: Vorlesung 2
  • Stoff TI-Skript1.pdf, S. 53-61.
  • Aufgaben: Übungsblatt 1 (ab Di im SVN)

Übungsblätter

Übungsblätter werden immer am Dienstag im SVN als PDF-Datei zur Verfügung gestellt. Die Abgabe der Lösung als LaTeX erzeugte PDF-Datei ist per SVN-Repository bis zum Donnerstag 8:00 Uhr in der Woche darauf möglich.

Weitere, organisatorische Informationen zum SVN-Repository finden Sie demnächst unter read.me.

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. (Zugehöriges Skript wird zur privaten Verwendung im SVN zur Verfügung gestellt.)
• 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.

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