Theoretische Informatik und Logik
Theoretische Informatik und Logik
Course with SWS 4/2/0 (lecture/exercise/practical) in SS 2026
Lecturer
Tutor
- Maximilian Marx
- Stephan Mennicke
- Lukas Gerlach
- Florens Förster
- Cornelius Lübke
- Anna Dolma Hornschild
SWS
- 4/2/0
Modules
Examination method
- Written exam
Lecture series
Beschreibung
Die Vorlesung ist weitgehend selbsterklärend, aber Grundlagen aus der Veranstaltung Formale Systeme können hilfreich sein.
Vorlesungen
Die Vorlesungstermine sind
Die erste Vorlesung findet am Montag, dem 13. April 2026 statt.
Übungen
Die Einschreibung ist ab Montag, dem 13. April 2026, 15:00 Uhr möglich. Für die Teilnahme an einer Übungsgruppe ist die Einschreibung in dieser Gruppe verpflichtend. Studierenden ohne Einschreibung kann die Teilnahme an einer selbst gewählten Übung nicht garantiert werden. Übungsleiter sind berechtigt, nicht eingeschriebene Studierende bei Überfüllung der Übung zu verweisen.
Der Übungsbetrieb startet am 20. April 2026 zu Ihren jeweiligen Terminen in den angegebenen Räumen. Die Übungsblätter können in der Spalte der jeweiligen Übung unter Termine und Unterlagen heruntergeladen werden.
Unterlagen
Die vollständigen Foliensätze zur Vorlesung erscheinen bis zur Woche 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
(C) Markus Krötzsch, https://iccl.inf.tu-dresden.de/web/TheoLog2024, CC BY 3.0 DE
Bildrechte können davon abweichen und sind gesondert in den LaTeX-Dateien angegeben. Die Foliensätze enthalten keinerlei Texte, die aus Werken entnommen sind, für welche die VG Wort Verwertungsrechte vertritt.
Die Nutzung der Materialien in eigenen Lehrveranstaltungen ist willkommen, sofern der obige Lizenztext in allen abgeleiteten Foliensätzen angegeben wird. Rückmeldungen sind ebenfalls willkommen (z.B. als Issue zu diesem Repository); wir verlinken hier gern auf die Homepages der entsprechenden Kurse. Interessierte Lehrende können ihre abgewandelten Quellen auch mit in diesem Respository veröffentlichen -- kontaktieren Sie Prof. Krötzsch.
Die Folien wurden erstellt von Markus Krötzsch. Eine vollständige Liste der Beitragenden ist unter https://github.com/mkroetzsch/TheoLog/graphs/contributors zu finden.
Kontakt
Zur Kommunikation unter Vorlesungsteilnehmern der TU Dresden steht ein Matrix-Kanal zur Verfügung.
Kommentare und Bug Reports können gern auch direkt über die entsprechenden Seiten auf github gepostet werden: https://github.com/mkroetzsch/TheoLog
Persönliche Fragen können direkt an das Organisationsteam (siehe Links oben) gestellt werden, falls sie aus einem zwingenden Grund nicht über andere Kanäle gerichtet werden können. Allgemeine 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)
Subscribe to events of this course (icalendar)
| Lecture | Einleitung und Übersicht | DS3, April 13, 2026 in HÜL/S386 |
Calendar
