Theoretische Informatik und Logik
Theoretische Informatik und Logik
Lehrveranstaltung mit SWS 4/2/0 (Vorlesung/Übung/Praktikum) in SS 2021
Dozent
Tutor
Umfang (SWS)
- 4/2/0
Module
Leistungskontrolle
- Klausur
Matrix-Kanal
Vorlesungsreihe
Die Vorlesung vermittelt eine vertiefende Einleitung in die theoretische Informatik, beginnend mit den Grundlagen der Berechenbarkeits- und Komplexitätstheorie, Prädikatenlogik und deren Bezug zu Komplexität und Datenbanken, bis hin zu weiterführenden Themen wie Gödels Unvollständigkeitstheoreme und die Beziehung von Logik und formalen Sprachen. Wir stoßen vor zu den Grenzen der Informatik und Mathematik, treffen auf fleißige Biber und verrückte Logiker, vergleichen SQL mit Tic Tac Toe und stellen die großen Fragen unseres Fachgebiets.
Die Vorlesung ist weitgehend selbsterklärend, aber Grundlagen aus der Veranstaltung Formale Systeme können hilfreich sein.
Termine
Im Sommersemester 2021 findet die Lehrveranstaltung rein digital statt. Die Vorlesungen werden als Videoreihe auf YouTube veröffentlicht. Links finden sich unter diesem YouTube-Kanal.
Zudem werden einige Live-Sessions zur Konsultation angeboten. Diese werden aufgrund der großen Teilnehmerzahl jeweils über Zoom abgehalten. Die Einwahldetails finden sich im Bereich Links der OPAL-Seite dieser Lehrveranstaltung. Ein Login oder die Installation spezieller Software ist nicht erforderlich. Konsultationstermine werden hier bekannt gegeben:
Montag, 02.04.2021, 2.DS (09:20–10:50): Einführung und Willkommen(falsch angekündigter Termin; Konsultationen sind erst später geplant)- Montag, 03.05.2021, 2.DS (9:20–10:50): 1. Konsultation
- Montag, 07.06.2021, 2.DS (9:20–10:50): 2. Konsultation
- Montag, 19.07.2021, 2.DS (9:20–10:50): 3. Konsultation
- Mittwoch, 11.08.2021, 6.DS (16:40–18:10): Besprechung der Musterklausur
Klausur
Die Klausur (90 Minuten) findet am Freitag, dem 13.08.2021 im Zeitraum 08:50–11:20 Uhr als Onlineklausur statt. Bitte beachten Sie die Hinweise zur Durchführung der Klausur. Eine kurze Probeklausur zum Test der Prüfungsplattform findet am 03.08.2021 von 16:30–17:00 Uhr statt. Die Probeklausur dient lediglich dazu, Sie mit der Prüfungsplattform vertraut zu machen. Sie entspricht weder hinsichtlich der Bearbeitungszeit noch der Aufgabentypen der tatsächlichen Prüfungsklausur. Wir stellen dafür gesondert eine Musterklausur bereit, die am Mittwoch, dem 11.08.2021 im Zeitraum 16:40–18:10 Uhr in einer Konsultation besprochen wird. Bitte beachten Sie die Hinweise zur Durchführung der Probeklausur.
Klausureinsicht zur Wiederholungsklausur
Am Mittwoch, dem 2022-04-13, besteht ab 14:00 Uhr die Möglichkeit zur Einsicht in die Wiederholungsklausur. Zur Terminvergabe kontaktieren Sie bitte Maximilian Marx.
Übungen
Die Einschreibungen in die Übungsgruppen erfolgt über OPAL. Die Übungen starten in Kalenderwoche 17, also in der Woche, die am 26.4.2021 beginnt.
Bitte beachten Sie: Für die Teilnahme an einer Übungsgruppe ist die Einschreibung in dieser Gruppe verpflichtend. Studierenden ohne Einschreibung kann die Teilnahme an einer selbstgewählten Übung nicht garantiert werden. Übungsleiter sind berechtigt, nicht eingeschriebene Studierende bei Überfüllung aus der Übung zu verweisen.
Übungsblätter
Aufgabenblätter werden ungefähr eine Woche vor der Übung hier bereitstellt werden. Zur Vorbereitung auf die Prüfung wird auch eine Musterklausur bereitgestellt.
- 1. Übungsblatt
- 2. Übungsblatt
- 3. Übungsblatt
- 4. Übungsblatt
- 5. Übungsblatt
- 6. Übungsblatt
- 7. Übungsblatt
- 8. Übungsblatt
- 9. Übungsblatt
- 10. Übungsblatt
- 11. Übungsblatt
- 12. Übungsblatt
Unterlagen
Die vollständigen Foliensätze zur Vorlesung erscheinen spätestens kurz nach der Vorlesung online (siehe Termine und Unterlagen). Weiterführende Literatur ist unter Literatur angegeben. Die Quellen der Vorlesungsfolien sind auf github verfügbar: https://github.com/knowsys/TheoLog
Alle Foliensätze der Vorlesungen können entsprechend den Lizensbedingungen von Creative Commons CC By 3.0 Deutschland genutzt, weitergegeben und modifiziert werden. Als Namensnennung ist folgende Angabe einzufügen:
(C) Markus Krötzsch, https://iccl.inf.tu-dresden.de/web/TheoLog2021, CC BY 3.0 DE
Bildrechte können davon abweichen und sind gesondert angegeben. Die Foliensätze enthalten keinerlei Texte, die aus Werken entnommen sind, für welche die VG Wort Verwertungsrechte vertritt.
Besonderen Dank gilt allen Contributors, die Anmerkungen und Verbesserungen beigetragen haben: Daniel Borchmann, Maximilian Marx, Dominik (freeDom-), CniKKoR, Marcus Rossel, SchermulyM, David Tiede, Francesco Kriegel, Robert Peine, Christian Lewe, Martin Wudenka, Sönke (eknoes), Jonny Seitz, Niklas Wünsche, und Florian Ulbrich. (Stand Juli 2018; Ergänzungen sind willkommen.)
Kontakt
Zur Kommunikation unter Vorlesungsteilnehmern steht ein Matrix-Kanal zur Verfügung. Dieser kann auch für Fragen zu Organisation und Inhalten der Vorlesung verwendet werden.
Kommentare und Bug Reports können gern auch direkt über die entsprechenden Seiten auf github gepostet werden:
https://github.com/knowsys/TheoLog
Alternativ können Hinweise zu Tippfehlern in den Vorlesungsfolien auch an die Mailingliste geschickt werden.
Persönliche Fragen können auch direkt an das Organisationsteam (siehe Links oben) gestellt werden, falls sie aus einem zwingenden Grund nicht über andere Kanäle gerichtet werden können. Allgemein Fragen sollten Sie aber immer in geteilten Kanälen stellen, damit auch Ihre Kommilitoninnen und Kommilitonen davon profitieren (oder vielleicht sogar direkt helfen können).Allgemein sind die Vorlesungsfolien und Übungsunterlagen ausreichend detailliert für das Studium. Weitere Lehrmaterialien können dennoch hilfreich sein, um Details nachzuschlagen oder sich weiter im Thema zu vertiefen.
Allgemeine Lehrbücher
- Uwe Schöning: Theoretische Informatik -- kurz gefasst. Spektrum Akademischer Verlag.
- (deutschsprachiger Standardtext; in der Tat ziemlich kurz gefasst)
- Michael Sipser: Introduction to the Theory of Computation. Cengage Learning.
- (Standardtext zur Berechnung und Sprachen, speziell zum Thema Komplexität zu empfehlen; leider nur auf Englisch)
- Christopher Moore, Stephan Meterns: The Nature of Computation. Oxford University Press.
- (sehr guter, moderner Text zu Komplexität und Berechnung, weniger formell; leider nur auf Englisch)
- John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman: Einführung in Automatentheorie, Formale Sprachen und Berechenbarkeit. Pearson Studium.
- (aus dem Englischen übertragenes Standardwerk; Original ev. besser)
Unterhaltung
Besonders spannende und interessante Themen aus der theoretischen Informatik und der Geschichte ihrer Protagonisten kann man auch in weniger formalen Texten nachlesen:
- Apostolos Doxiadis, Christos Papadimitriou: Logicomix: An Epic Search for Truth. Bloomsbury
- (Graphic Novel, inspiriert von Russels Leben und der Geschichte der Logik, wenn auch in Teilen frei erfunden)
- Scott Aaronson: Quantum Computing Since Democritus. Cambridge
- (informeller Text (eigentlich eine Sammlung von Blogeinträgen) mit interessanten Denkanstößen rund um Berechnung und Komplexität)
- Douglas Hofstadter: Gödel, Escher, Bach: An Eternal Golden Braid. Basic Books
- (der Klassiker; in viele Sprachen übersetzt, aber im Original am besten)
Berechnung und Komplexität
Die Bücher von Sipser und Moore & Mertens sind hier bereits sehr gute Referenzen. Wer darüber hinaus noch mehr Details sucht, der kann die folgenden Fachbücher konsultieren:
- Christos H. Papadimitriou: Computational Complexity Academic Internet Publ., 2007.
- (Standardwerk zu vielen Themen der Komplexitätstheorie)
- Sanjeev Arora, Boaz Barak: Computational Complexity: A Modern Approach Cambridge University Press.
- (Detailllierter und umfangreicher Text zur Komplexitätstheorie)
Prädikatenlogik
Die Vorlesungsfolien sollten bei diesem Thema ausreichen. Die Darstellung des Themas in der Literatur ist ziemlich uneinheitlich, so dass verschiedene Bücher oft leicht unterschiedliche Definitionen verwenden. Wer dennoch weitere Details nachschlagen will, dem nützen eventuell die folgenden Bücher:
- Uwe Schöning: Logik für Informatiker. Spektrum Akademischer Verlag.
- (leichte Abweichungen in Notation und Darstellung)
- Martin Kreuzer, Stefan Kühling: Logik für Informatiker. Pearson Studium.
- (sehr knapp und informell; eventuell interessant als Quelle für Übungsaufgaben)
- Steffen Hölldobler: Logik und Logikprogrammierung. Synchron Verlag.
- (Schwerpunkt auf Logikprogrammierung und Prädikatenlogik)
- Steffen Hölldobler, Sebastian Bader, Bertram Fronhöfer, Ursula Hans, Pascal Hitzler, Markus Krötzsch, Tobias Pietzsch: Logik und Logikprogrammierung, Band 2: Aufgaben und Lösungen Synchron Verlag
- (Aufgabensammlung aus den Logikvorlesungen vergangener Jahre)
Spezielle Themen
- Torkel Franzén: 'Gödel's Theorem: An Incomplete Guide to Its Use and Abuse. A K Peters.
- (Gut verdaulicher Text zu Gödels Unvollständigkeitssätzen, einschl. deren Beziehungen zur Berechenbarkeitstheorie)
- Raymond M. Smullyan: A Beginner's Guide to Mathematical Logic. Dover Publications, 2014.
- (Erster Teil: Einleitung und Logikrätsel. Zweiter Teil: Umfassende Entwicklung von Gödels Unvollständigkeitsbeweisen mit Gödel-Nummern und Gödel-Sätzen)
Veranstaltungskalender abonnieren (icalendar)
| Vorlesung | 1. Einleitung und Motivation | DS2, 12. April 2021 in Video | Datei |
| Video 1, Video 2 | |||
| Vorlesung | 2. Berechenbarkeit und Unentscheidbarkeit | DS4, 15. April 2021 in Video | Datei |
| Video 1, Video 2 | |||
| Übung | 1. Übungsblatt | Datei | |
| Vorlesung | 3. WHILE und LOOP | DS2, 19. April 2021 in Video | Datei |
| Video 1, Video 2, Video 3 | |||
| Vorlesung | 4. Das Halteproblem und Reduktionen | DS4, 22. April 2021 in Video | Datei |
| Video 1, Video 2, Video 3 | |||
| Übung | 2. Übungsblatt | Datei | |
| Vorlesung | 5. Der Satz von Rice/Das Postsche Korrespondenzproblem | DS2, 26. April 2021 in Video | Datei |
| Video 1, Video 2, Video 3 | |||
| Vorlesung | 6. Unentscheidbare Probleme formaler Sprachen | DS4, 29. April 2021 in Video | Datei |
| Video 1, Video 2, Video 3 | |||
| Übung | 3. Übungsblatt | Datei | |
| Konsultation | 1. Konsultation | DS2, 3. Mai 2021 in Zoom | |
| Vorlesung | 7. Einführung in die Komplexitätstheorie | DS4, 6. Mai 2021 in Video | Datei |
| Video 1, Video 2, Video 3 | |||
| Übung | 4. Übungsblatt | Datei | |
| Vorlesung | 8. Beziehungen zwischen Komplexitätsklassen / Effizient lösbare Probleme | DS2, 10. Mai 2021 in Video | Datei |
| Video 1, Video 2, Video 3 | |||
| Entfällt | Himmelfahrt | DS4, 13. Mai 2021 in - | |
| Vorlesung | 9. NP und NP-Vollständigkeit | DS2, 17. Mai 2021 in Video | Datei |
| Video 1, Video 2, Video 3 | |||
| Übung | 5. Übungsblatt | Datei | |
| Vorlesung | 10. NP, Teil 2 | DS4, 20. Mai 2021 in Video | Datei |
| Video 1, Video 2, Video 3 | |||
| Übung | 6. Übungsblatt | Datei | |
| Entfällt | Pfingstferien | DS2, 24. Mai 2021 in - | |
| Entfällt | Pfingstferien | DS4, 27. Mai 2021 in - | |
| Vorlesung | 11. NL und PSpace | DS2, 31. Mai 2021 in Video | Datei |
| Video 1, Video 2 | |||
| Vorlesung | 12. PSpace-Vollständigkeit | DS4, 3. Juni 2021 in Video | Datei |
| Video 1, Video 2, Video 3 | |||
| Übung | 7. Übungsblatt | Datei | |
| Konsultation | 2. Konsultation | DS2, 7. Juni 2021 in Zoom | |
| Vorlesung | 13. Prädikatenlogik: Syntax und Semantik | DS4, 10. Juni 2021 in Video | Datei |
| Video 1, Video 2, Video 3 | |||
| Übung | 8. Übungsblatt | Datei | |
| Vorlesung | 14. Modelltheorie und logisches Schließen | DS2, 14. Juni 2021 in Video | Datei |
| Video 1, Video 2 | |||
| Vorlesung | 15. Logisches Schließen | DS4, 17. Juni 2021 in Video | Datei |
| Video 1, Video 2 | |||
| Übung | 9. Übungsblatt | Datei | |
| Vorlesung | 16. Logisches Schließen (2) | DS2, 21. Juni 2021 in Video | Datei |
| Video 1, Video 2, Video 3 | |||
| Vorlesung | 17. Funktionen und Normalformen | DS4, 24. Juni 2021 in Video | Datei 1, Datei 2 |
| Video 1, Video 2, Video 3 | |||
| Übung | 10. Übungsblatt | Datei | |
| Vorlesung | 18. Unifikation | DS2, 28. Juni 2021 in Video | Datei |
| Video 1, Video 2 | |||
| Vorlesung | 19. Resolution | DS4, 1. Juli 2021 in Video | Datei |
| Video 1, Video 2, Video 3 | |||
| Übung | 11. Übungsblatt | Datei | |
| Vorlesung | 20. Resolution (2) | DS2, 5. Juli 2021 in Video | Datei |
| Video 1, Video 2 | |||
| Vorlesung | 21. Endliche Modelle und Datenbanken | DS4, 8. Juli 2021 in Video | Datei |
| Video 1, Video 2, Video 3 | |||
| Übung | 12. Übungsblatt | Datei | |
| Vorlesung | 22. Datalog | DS2, 12. Juli 2021 in Video | Datei |
| Video 1, Video 2, Video 3 | |||
| Vorlesung | 23. Gödels 1. Unvollständigkeitssatz | DS4, 15. Juli 2021 in Video | |
| Konsultation | 3. Konsultation | DS2, 19. Juli 2021 in Zoom | |
| Seminar | Bachelor-How-To (ein Service des iFSR) | DS7, 20. Juli 2021 in Videokonferenz | Datei |
| Vorlesung | 24. Gödel, Turing und der ganze Rest | DS4, 22. Juli 2021 in Video | |
| Konsultation | Besprechung der Musterklausur | DS6, 11. August 2021 in (online) | Datei 1, Datei 2 |
Kalender
