Theoretische Informatik und Logik
Theoretische Informatik und Logik
Lehrveranstaltung mit SWS 4/2/0 (Vorlesung/Übung/Praktikum) in SS 2022
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.
Prüfung
Die Prüfung findet in Form einer 90-minütigen Klausur am 12.08.2022 morgens im Trefftz-Bau (Räume TRE/MATH/H und TRE/PHYS/E) statt. Weitere Informationen werden hier ergänzt. (Aktueller Stand: 11.07.2022)
Als Hilfsmittel ist ein Blatt DIN A4 („Formelsammlung“) zugelassen; es sind keine sonstigen Hilfsmittel zugelassen.
Vorlesungen
Vorlesungstermine:
- Mo 3. DS
- Do 4. DS
Die Vorlesung wird zunächst virtuell (über Zoom) durchgeführt. Die Links zu den Zoom-Terminen finden sich im Reiter „Termine und Unterlagen“. Die 1. Vorlesung findet am 4. April 2022 statt.
Übungen
Es wird sowohl virtuelle Übungsgruppen als auch Übungen in Präsenz geben.
Die Einschreibung in die Übungsgruppen erfolgt über die OPAL-Seite der Lehrveranstaltung ab 04.04.2022 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. Übungsleiter:innen von Präsenzgruppen sind berechtigt und verpflichtet, die Einhaltung etwaiger Hygieneregeln zu überprüfen sowie Beschränkungen der Personenanzahl in den Übungsräumen durchzusetzen.
Übungsgruppen finden ab dem 11. April 2022 zu ihren jeweiligen Terminen statt. Die virtuellen Übungen werden über das an der TU Dresden gehostete System BigBlueButton abgehalten. Links auf die entsprechenden digitalen Räume werden über OPAL bekanntgegeben. Ü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 und ein Matrix-Kanal 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/Einleitung/Übersicht | DS3, 4. April 2022 in Videokonferenz | Datei 1, Datei 2 |
| Video | |||
| Vorlesung | 2. Vorlesung: Berechenbarkeit und Unentscheidbarkeit | DS4, 7. April 2022 in Videokonferenz | Datei 1, Datei 2 |
| Video | |||
| Übung | 1. Übungsblatt | Datei | |
| Vorlesung | 3. Vorlesung: LOOP und WHILE | DS3, 11. April 2022 in Videokonferenz | Datei 1, Datei 2 |
| Video | |||
| Vorlesung | 4. Vorlesung: Das Halteproblem und Reduktionen | DS4, 14. April 2022 in Videokonferenz | Datei 1, Datei 2 |
| Video | |||
| Vorlesung | 5. Vorlesung: Der Satz von Rice und das Postsche Korrespondenzproblem | DS4, 21. April 2022 in Videokonferenz | Datei 1, Datei 2 |
| Video | |||
| Übung | 2. Übungsblatt | Datei | |
| Vorlesung | 6. Vorlesung: Unentscheidbare Probleme formaler Sprachen | DS3, 25. April 2022 in Videokonferenz | Datei 1, Datei 2 |
| Video | |||
| Vorlesung | 7. Vorlesung: Einführung in die Komplexitätstheorie | DS4, 28. April 2022 in Videokonferenz | Datei 1, Datei 2 |
| Video | |||
| Übung | 3. Übungsblatt | Datei | |
| Vorlesung | 8. Vorlesung: Beziehungen zwischen Komplexitätsklassen / Effizient lösbare Probleme | DS3, 2. Mai 2022 in Videokonferenz | Datei 1, Datei 2 |
| Video | |||
| Vorlesung | 9. Vorlesung: NP und NP-Vollständigkeit | DS4, 5. Mai 2022 in Videokonferenz | Datei 1, Datei 2 |
| Video | |||
| Übung | 4. Übungsblatt | Datei | |
| Vorlesung | 10. Vorlesung: NP, Teil 2 | DS3, 9. Mai 2022 in Videokonferenz | Datei 1, Datei 2 |
| Video | |||
| Übung | 5. Übungsblatt | Datei | |
| Vorlesung | 11. Vorlesung: NL und PSpace | DS3, 16. Mai 2022 in Videokonferenz | Datei 1, Datei 2 |
| Video | |||
| Vorlesung | 12. Vorlesung: PSpace-Vollständigkeit | DS4, 19. Mai 2022 in Videokonferenz | Datei 1, Datei 2 |
| Video | |||
| Übung | 6. Übungsblatt | Datei | |
| Vorlesung | 13. Vorlesung: Prädikatenlogik – Syntax und Semantik | DS3, 23. Mai 2022 in Videokonferenz | Datei 1, Datei 2 |
| Video | |||
| Übung | 7. Übungsblatt | Datei | |
| Vorlesung | 14. Vorlesung: Modelltheorie und logisches Schließen | DS3, 30. Mai 2022 in Videokonferenz | Datei 1, Datei 2 |
| Video | |||
| Vorlesung | 15. Vorlesung: Logisches Schließen und Gleichheit | DS4, 2. Juni 2022 in Videokonferenz | Datei 1, Datei 2 |
| Video | |||
| Übung | 8. Übungsblatt | Datei | |
| Vorlesung | 16. Vorlesung: Logisches Schließen – Unentscheidbarkeit | DS3, 13. Juni 2022 in Videokonferenz | Datei 1, Datei 2 |
| Video | |||
| Vorlesung | 17. Vorlesung: Funktionen und Normalformen | DS4, 16. Juni 2022 in Videokonferenz | Datei 1, Datei 2 |
| Video | |||
| Übung | 9. Übungsblatt | Datei | |
| Vorlesung | 18. Vorlesung: Unifikation | DS3, 20. Juni 2022 in Videokonferenz | Datei 1, Datei 2 |
| Video | |||
| Vorlesung | 19. Vorlesung: Resolution | DS4, 23. Juni 2022 in Videokonferenz | Datei 1, Datei 2 |
| Video | |||
| Übung | 10. Übungsblatt | Datei | |
| Vorlesung | 20. Vorlesung: Resolution (2) | DS3, 27. Juni 2022 in Videokonferenz | Datei 1, Datei 2 |
| Video | |||
| Vorlesung | 21. Vorlesung: Endliche Interpretationen und Datenbanken | DS4, 30. Juni 2022 in Videokonferenz | Datei 1, Datei 2 |
| Video | |||
| Übung | 11. Übungsblatt | Datei | |
| Vorlesung | 22. Vorlesung: Datalog | DS3, 4. Juli 2022 in Videokonferenz | Datei 1, Datei 2 |
| Video | |||
| Vorlesung | 23. Vorlesung: Gödels 1. Unvollständigkeitssatz | DS4, 7. Juli 2022 in Videokonferenz | Datei 1, Datei 2 |
| Video | |||
| Übung | 12. Übungsblatt | Datei | |
| Vorlesung | 24. Vorlesung: Gödel, Turing und der ganze Rest | DS3, 11. Juli 2022 in Videokonferenz | Datei 1, Datei 2 |
| Video | |||
| Entfällt | Vorlesung | DS4, 14. Juli 2022 in Terminlos | |
| Übung | Besprechung der Übungsklausur | DS5, 8. August 2022 in Videokonferenz | Datei 1, Datei 2 |
| Konsultation | Repetitorium | DS6, 11. August 2022 in Videokonferenz | |
Kalender
