Theoretische Informatik und Logik

From International Center for Computational Logic

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

Wir planen eine Wiederholungsklausur anzubieten.




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