Theoretische Informatik und Logik
Theoretische Informatik und Logik
Course with SWS 4/2/0 (lecture/exercise/practical) in SS 2025
Lecturer
Tutor
SWS
- 4/2/0
Modules
Examination method
- Written exam
Lecture series
Die Lehrveranstaltung 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.
Vorlesungen
Vorlesungstermine:
- Mo 3. DS, HÜL/S386/H
- Do 4. DS, HSZ/0002/E
Übungen
Die Einschreibung in die Übungsgruppen erfolgt über die OPAL-Seite der Lehrveranstaltung ab 07.04.2025 15:00 Uhr. 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:innen sind berechtigt, nicht eingeschriebene Studierende bei Überfüllung aus der (digitalen) Übung zu verweisen.
Übungsgruppen finden ab dem 14. April 2025 zu ihren jeweiligen Terminen statt. Übungsblätter können über den Reiter „Termine und Unterlagen“ abgerufen werden.
Individuelles Feedback für Ihre Lösungen: Als zusätzliche Hilfe bieten wir in diesem Semester an, von Studierenden eingereichte Lösungsansätze zu sichten und Ihnen dazu eine Rückmeldung zu geben. Die Details (Abgabetermin & Umfang) werden von den Tutor:innen festgelegt. Unterlagen können per E-Mail an die Tutor:innen abgegeben werden (als digitales Dokument, egal ob Handyfoto der eigenen Handschrift oder am Computer geschriebener Text).
Kontakt
Zur Kommunikation unter Vorlesungsteilnehmer:innen der TU Dresden stehen ein OPAL-Diskussionsforum zur Verfügung.
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.
Allgemeine Fragen sollten Sie aber immer in geteilten Kanälen stellen, damit auch Ihre Kommiliton:innen davon profitieren (oder vielleicht sogar direkt helfen können).Subscribe to events of this course (icalendar)
| Lecture | 1. Vorlesung: Willkommen und Einleitung | DS3, April 7, 2025 in HÜL/S386/H | |
| Lecture | 2. Vorlesung: Berechenbarkeit und Unentscheidbarkeit | DS4, April 10, 2025 in HSZ/0002/E | |
| Lecture | 3. Vorlesung: WHILE und LOOP | DS3, April 14, 2025 in HÜL/S386/H | |
| Lecture | 4. Vorlesung: Das Halteproblem und Reduktionen | DS4, April 17, 2025 in HSZ/0002/E | |
| No session | Ostermontag | DS3, April 21, 2025 in HÜL/S386/H | |
| Lecture | 5. Vorlesung: Der Satz von Rice und das Postsche Korrespondenzproblem | DS4, April 24, 2025 in HSZ/0002/E | |
| Lecture | 6. Vorlesung: Unentscheidbare Probleme formaler Sprachen | DS3, April 28, 2025 in HÜL/S386/H | |
| No session | 1. Mai | DS4, May 1, 2025 in APB | |
| Lecture | 7. Vorlesung: Einführung in die Komplexitätstheorie | DS3, May 5, 2025 in HÜL/S386/H | |
| Lecture | 8. Vorlesung: Beziehungen zwischen Komplexitätsklassen / Effizient lösbare Probleme | DS4, May 8, 2025 in HSZ/0002/E | |
| Lecture | 9. Vorlesung: NP und NP-Vollständigkeit | DS3, May 12, 2025 in HÜL/S386/H | |
| Lecture | 10. Vorlesung: NP, Teil 2 | DS4, May 15, 2025 in HSZ/0002/E | |
| Lecture | 11. Vorlesung: NL und PSpace | DS3, May 19, 2025 in HÜL/S386/H | |
| Lecture | 12. Vorlesung: PSpace-Vollständigkeit | DS4, May 22, 2025 in HSZ/0002/E | |
| Lecture | 13. Vorlesung: Prädikatenlogik: Syntax und Semantik | DS3, May 26, 2025 in HÜL/S386/H | |
| No session | Himmelfahrt | DS4, May 29, 2025 in HSZ/0002/E | |
| Lecture | 14. Vorlesung: Modelltheorie und logisches Schließen | DS3, June 2, 2025 in HÜL/S386/H | |
| Lecture | 15. Vorlesung: Logisches Schließen und Gleichheit | DS4, June 5, 2025 in HSZ/0002/E | |
| No session | Pfingsten | DS3, June 9, 2025 in HÜL/S386/H | |
| No session | Pfingsten | DS4, June 12, 2025 in HSZ/0002/E | |
| Lecture | 16. Vorlesung: Logisches Schließen – Unentscheidbarkeit | DS3, June 16, 2025 in HÜL/S386/H | |
| Lecture | 17. Vorlesung: Funktionen und Normalformen | DS4, June 19, 2025 in HSZ/0002/E | |
| Lecture | 18. Vorlesung: Unifikation | DS3, June 23, 2025 in HÜL/S386/H | |
| Lecture | 19. Vorlesung: Resolution | DS4, June 26, 2025 in HSZ/0002/E | |
| Lecture | 20. Vorlesung: Resolution (2) | DS3, June 30, 2025 in HÜL/S386/H | |
| Lecture | 21. Vorlesung: Endliche Interpretationen und Datenbanken | DS4, July 3, 2025 in HSZ/0002/E | |
| Lecture | 22. Vorlesung: Datalog | DS3, July 7, 2025 in HÜL/S386/H | |
| Lecture | 23. Vorlesung: Gödels 1. Unvollständigkeitssatz | DS4, July 10, 2025 in HSZ/0002/E | |
| Lecture | 24. Vorlesung: Gödel, Turing und der ganze Rest | DS3, July 14, 2025 in HÜL/S386/H |
Calendar
