Theoretische Informatik und Logik
Theoretische Informatik und Logik
Course with SWS 4/2/0 (lecture/exercise/practical) in SS 2022
Lecturer
Tutor
SWS
- 4/2/0
Modules
Examination method
- Written exam
Matrix channel
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.
Wiederholungsklausur
Prüfungstermin: 24.02.2023 08:00 Uhr WEB/KLEM/U
Als Hilfsmittel ist ein Blatt DIN A4 („Formelsammlung“) zugelassen; es sind keine sonstigen Hilfsmittel erlaubt.
Klausureinsicht
2. Termin: Am 10.11.2022 bieten wir Ihnen im Raum ABP 2040 von 13:00 bis 14:00 Uhr die Möglichkeit zur Klausureinsicht.
Bitte melden Sie sich hierzu per Mail (mailto:doerthe.arndt@tu-dresden.de) an. In Ausnahmefällen können ebenfalls Individualtermine vereinbart werden
Prüfungsergebnisse
Die Prüfungsergebnisse wurden an das Prüfungsamt übermittelt.
Prüfung
Die Prüfung findet in Form einer 90-minütigen Klausur am 12.08.2022 im Trefftz-Bau in den Räumen TRE/MATH/H (Anfangsbuchstaben des Familiennamens A–L) und TRE/PHYS/E (Anfangsbuchstaben M–Z) statt. Klausurbeginn ist 9:00 Uhr, bitte seien Sie jedoch spätestens 08:45 Uhr da. Einlass ist ab 08:30 Uhr.
Am 11.08.2022 findet um 16:30 Uhr ein Repetitorium statt.
(Stand: 10.08.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).Subscribe to events of this course (icalendar)
| Lecture | 1. Vorlesung: Willkommen/Einleitung/Übersicht | DS3, April 4, 2022 in Video conference | File 1, File 2 |
| Video | |||
| Lecture | 2. Vorlesung: Berechenbarkeit und Unentscheidbarkeit | DS4, April 7, 2022 in Video conference | File 1, File 2 |
| Video | |||
| Exercise | 1. Übungsblatt | File | |
| Lecture | 3. Vorlesung: LOOP und WHILE | DS3, April 11, 2022 in Video conference | File 1, File 2 |
| Video | |||
| Lecture | 4. Vorlesung: Das Halteproblem und Reduktionen | DS4, April 14, 2022 in Video conference | File 1, File 2 |
| Video | |||
| Lecture | 5. Vorlesung: Der Satz von Rice und das Postsche Korrespondenzproblem | DS4, April 21, 2022 in Video conference | File 1, File 2 |
| Video | |||
| Exercise | 2. Übungsblatt | File | |
| Lecture | 6. Vorlesung: Unentscheidbare Probleme formaler Sprachen | DS3, April 25, 2022 in Video conference | File 1, File 2 |
| Video | |||
| Lecture | 7. Vorlesung: Einführung in die Komplexitätstheorie | DS4, April 28, 2022 in Video conference | File 1, File 2 |
| Video | |||
| Exercise | 3. Übungsblatt | File | |
| Lecture | 8. Vorlesung: Beziehungen zwischen Komplexitätsklassen / Effizient lösbare Probleme | DS3, May 2, 2022 in Video conference | File 1, File 2 |
| Video | |||
| Lecture | 9. Vorlesung: NP und NP-Vollständigkeit | DS4, May 5, 2022 in Video conference | File 1, File 2 |
| Video | |||
| Exercise | 4. Übungsblatt | File | |
| Lecture | 10. Vorlesung: NP, Teil 2 | DS3, May 9, 2022 in Video conference | File 1, File 2 |
| Video | |||
| Exercise | 5. Übungsblatt | File | |
| Lecture | 11. Vorlesung: NL und PSpace | DS3, May 16, 2022 in Video conference | File 1, File 2 |
| Video | |||
| Lecture | 12. Vorlesung: PSpace-Vollständigkeit | DS4, May 19, 2022 in Video conference | File 1, File 2 |
| Video | |||
| Exercise | 6. Übungsblatt | File | |
| Lecture | 13. Vorlesung: Prädikatenlogik – Syntax und Semantik | DS3, May 23, 2022 in Video conference | File 1, File 2 |
| Video | |||
| Exercise | 7. Übungsblatt | File | |
| Lecture | 14. Vorlesung: Modelltheorie und logisches Schließen | DS3, May 30, 2022 in Video conference | File 1, File 2 |
| Video | |||
| Lecture | 15. Vorlesung: Logisches Schließen und Gleichheit | DS4, June 2, 2022 in Video conference | File 1, File 2 |
| Video | |||
| Exercise | 8. Übungsblatt | File | |
| Lecture | 16. Vorlesung: Logisches Schließen – Unentscheidbarkeit | DS3, June 13, 2022 in Video conference | File 1, File 2 |
| Video | |||
| Lecture | 17. Vorlesung: Funktionen und Normalformen | DS4, June 16, 2022 in Video conference | File 1, File 2 |
| Video | |||
| Exercise | 9. Übungsblatt | File | |
| Lecture | 18. Vorlesung: Unifikation | DS3, June 20, 2022 in Video conference | File 1, File 2 |
| Video | |||
| Lecture | 19. Vorlesung: Resolution | DS4, June 23, 2022 in Video conference | File 1, File 2 |
| Video | |||
| Exercise | 10. Übungsblatt | File | |
| Lecture | 20. Vorlesung: Resolution (2) | DS3, June 27, 2022 in Video conference | File 1, File 2 |
| Video | |||
| Lecture | 21. Vorlesung: Endliche Interpretationen und Datenbanken | DS4, June 30, 2022 in Video conference | File 1, File 2 |
| Video | |||
| Exercise | 11. Übungsblatt | File | |
| Lecture | 22. Vorlesung: Datalog | DS3, July 4, 2022 in Video conference | File 1, File 2 |
| Video | |||
| Lecture | 23. Vorlesung: Gödels 1. Unvollständigkeitssatz | DS4, July 7, 2022 in Video conference | File 1, File 2 |
| Video | |||
| Exercise | 12. Übungsblatt | File | |
| Lecture | 24. Vorlesung: Gödel, Turing und der ganze Rest | DS3, July 11, 2022 in Video conference | File 1, File 2 |
| Video | |||
| No session | Vorlesung | DS4, July 14, 2022 in Terminlos | |
| Exercise | Besprechung der Übungsklausur | DS5, August 8, 2022 in Video conference | File 1, File 2 |
| Consultation | Repetitorium | DS6, August 11, 2022 in Video conference | |
Calendar
