Theoretische Informatik und Logik
Theoretische Informatik und Logik
Lehrveranstaltung mit SWS 4/2/0 (Vorlesung/Übung/Praktikum) in SS 2025
Dozent
Tutor
Umfang (SWS)
- 4/2/0
Module
Leistungskontrolle
- Klausur
Vorlesungsreihe
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).Veranstaltungskalender abonnieren (icalendar)
| Vorlesung | 1. Vorlesung: Willkommen und Einleitung | DS3, 7. April 2025 in HÜL/S386/H | |
| Vorlesung | 2. Vorlesung: Berechenbarkeit und Unentscheidbarkeit | DS4, 10. April 2025 in HSZ/0002/E | |
| Vorlesung | 3. Vorlesung: WHILE und LOOP | DS3, 14. April 2025 in HÜL/S386/H | |
| Vorlesung | 4. Vorlesung: Das Halteproblem und Reduktionen | DS4, 17. April 2025 in HSZ/0002/E | |
| Entfällt | Ostermontag | DS3, 21. April 2025 in HÜL/S386/H | |
| Vorlesung | 5. Vorlesung: Der Satz von Rice und das Postsche Korrespondenzproblem | DS4, 24. April 2025 in HSZ/0002/E | |
| Vorlesung | 6. Vorlesung: Unentscheidbare Probleme formaler Sprachen | DS3, 28. April 2025 in HÜL/S386/H | |
| Entfällt | 1. Mai | DS4, 1. Mai 2025 in APB | |
| Vorlesung | 7. Vorlesung: Einführung in die Komplexitätstheorie | DS3, 5. Mai 2025 in HÜL/S386/H | |
| Vorlesung | 8. Vorlesung: Beziehungen zwischen Komplexitätsklassen / Effizient lösbare Probleme | DS4, 8. Mai 2025 in HSZ/0002/E | |
| Vorlesung | 9. Vorlesung: NP und NP-Vollständigkeit | DS3, 12. Mai 2025 in HÜL/S386/H | |
| Vorlesung | 10. Vorlesung: NP, Teil 2 | DS4, 15. Mai 2025 in HSZ/0002/E | |
| Vorlesung | 11. Vorlesung: NL und PSpace | DS3, 19. Mai 2025 in HÜL/S386/H | |
| Vorlesung | 12. Vorlesung: PSpace-Vollständigkeit | DS4, 22. Mai 2025 in HSZ/0002/E | |
| Vorlesung | 13. Vorlesung: Prädikatenlogik: Syntax und Semantik | DS3, 26. Mai 2025 in HÜL/S386/H | |
| Entfällt | Himmelfahrt | DS4, 29. Mai 2025 in HSZ/0002/E | |
| Vorlesung | 14. Vorlesung: Modelltheorie und logisches Schließen | DS3, 2. Juni 2025 in HÜL/S386/H | |
| Vorlesung | 15. Vorlesung: Logisches Schließen und Gleichheit | DS4, 5. Juni 2025 in HSZ/0002/E | |
| Entfällt | Pfingsten | DS3, 9. Juni 2025 in HÜL/S386/H | |
| Entfällt | Pfingsten | DS4, 12. Juni 2025 in HSZ/0002/E | |
| Vorlesung | 16. Vorlesung: Logisches Schließen – Unentscheidbarkeit | DS3, 16. Juni 2025 in HÜL/S386/H | |
| Vorlesung | 17. Vorlesung: Funktionen und Normalformen | DS4, 19. Juni 2025 in HSZ/0002/E | |
| Vorlesung | 18. Vorlesung: Unifikation | DS3, 23. Juni 2025 in HÜL/S386/H | |
| Vorlesung | 19. Vorlesung: Resolution | DS4, 26. Juni 2025 in HSZ/0002/E | |
| Vorlesung | 20. Vorlesung: Resolution (2) | DS3, 30. Juni 2025 in HÜL/S386/H | |
| Vorlesung | 21. Vorlesung: Endliche Interpretationen und Datenbanken | DS4, 3. Juli 2025 in HSZ/0002/E | |
| Vorlesung | 22. Vorlesung: Datalog | DS3, 7. Juli 2025 in HÜL/S386/H | |
| Vorlesung | 23. Vorlesung: Gödels 1. Unvollständigkeitssatz | DS4, 10. Juli 2025 in HSZ/0002/E | |
| Vorlesung | 24. Vorlesung: Gödel, Turing und der ganze Rest | DS3, 14. Juli 2025 in HÜL/S386/H |
Kalender
