Theoretische Informatik und Logik

Lehrveranstaltung mit SWS 4/2/0 (Vorlesung/Übung/Praktikum) in SS 2019

Dozent

Steffen Hölldobler

Tutor

Umfang (SWS)

4/2/0

Module

INF-B-290

Leistungskontrolle

Klausur

Vorlesungsreihe

Theoretische Informatik und Logik

Information

Neuigkeiten

Aufgrund der derzeitigen Ausnahmesituation können wir zurzeit eine Einsichtnahme in die Nachholklausur vom 28.2.2020 nur für diejenigen Studierenden organisieren, die diese Nachholklausur nicht bestanden haben. Falls Sie die Nachholklausur nicht bestanden haben und eine Einsichtnahme erwünschen, melden Sie sich bitte bis spätestens 8. Juni 2020 bei marcos (punkt) cramer (at) tu-dresden.de.

Klausur

Der Prüfungstermin ist Freitag, der 2.8.2019 um 9:20 Uhr in HSZ/AUDI/H. Die Klausur wird 90 Minuten dauern. Bitte bereits 15 Minuten vor Beginn (9:05 Uhr) anwesend sein.

Für die Prüfung gelten folgende Regeln:
- Es sind keine Unterlagen und Hilfsmittel zugelassen.
- Aufgrund des technischen Fortschritts sind auch keine Uhren (wie Telefone) am Platz erlaubt.
- Alle müssen ordnungsgemäß für die Klausur angemeldet sein.

Vorlesung

Die Vorlesung findet montags in der 2.DS (HSZ/0004) und freitags in der 3.DS (HSZ/0004) statt.

Teil 1: Die Slides für die Vorlesung sind hier. Der Benutzername ist student und das Passwort wird während der Vorlesung bekannt gegeben. Es ist das gleiche Passwort wie für das Material in der Formale Systeme Vorlesung WS2018.
Teil 2: Die Slides für die Vorlesung sind hier. Der Benutzername und das Passwort wird während der Vorlesung bekannt gegeben.

Übungen

In den Übungen werden die untenstehenden Aufgaben und die Übungen auf den Vorlesungsslides besprochen besprochen.

Die folgenden Übungen finden ab der Woche vom 8.4.2019 statt. In der ersten Übungswoche (8.4. - 12.4.) werden Übungen zur Aussagenlogik wiederholt.

montags, 3.DS (APB/E001) (Marcos Cramer)
dienstags, 4.DS (APB/E008) (Tobias John)
mittwochs, 5.DS (APB/E010) (Marcos Cramer)
freitags, 1.DS (APB/E010) (Tobias John)
freitags, 2.DS (APB/E009) (Emmanuelle Dietz)
freitags, 4.DS (APB/E001) (Emmanuelle Dietz)

Aufgaben zur Prädikatenlogik

Lösungen zu fast allen Übungsaufgaben, und weitere Übungsaufgaben finden sich in dem Buch

"S. Hölldobler et al.: Logik und Logikprogrammierung, Band II: Aufgaben und Lösungen, Synchron Publishers GmbH, 2011""

4.1 Syntax

Konstruktion von Teiltermen (Aufgabenstellung), 2. Übungswoche
Über Nachbarn (Aufgabenstellung), 2. Übungswoche

4.2 Substitutionen

Substitutionskomposition ist eine Substitution (Aufgabenstellung), 3. Übungswoche
Eigenschaften von Substitutionen (Aufgabenstellung), 3. Übungswoche

4.3 Semantik

Beispiele zur Interpretationsanwendung (Aufgabenstellung), 4. Übungswoche
Verschiedene Interpretationen einer Formel (Aufgabenstellung), 4. Übungswoche
Existenz einer Herbrand-Interpretation (Aufgabenstellung), 4. Übungswoche

Knifflige Existenz (Aufgabenstellung), 5. Übungswoche
Falscher Satz für einelementige Domänen (Aufgabenstellung), 5. Übungswoche
Formel ohne endliche Modelle (Aufgabenstellung), 5. Übungswoche

4.4 Äquivalenz und Normalform

Modellverlust beim Skolemisieren (Aufgabenstellung), 6. Übungswoche
Normalformen (Aufgabenstellung), 6. Übungswoche

4.5 Unifikation

Unifikationsprobleme I (Aufgabenstellung), 7. Übungswoche
Unifikationsprobleme II (Aufgabenstellung), 7. Übungswoche
Vergleichbarkeit von Unifikatoren (Aufgabenstellung), 7. Übungswoche
Zur Terminierung des Unifikationsalgorithmus (Aufgabenstellung), 7. Übungswoche

4.6 Beweisverfahren

Resolutionsverfahren (Aufgabenstellung), 8. Übungswoche
Schrittweiser Resolutionsbeweis (Aufgabenstellung), 8. Übungswoche
Notwendigkeit der Faktorisierung (Aufgabenstellung), 8. Übungswoche

Aufgaben zur Theoretischen Informatik

I. Berechenbarkeit

1. Turingmaschinen (Aufgabenstellung), 9. Übungswoche

2. Rekursive Funktionen und Post'sches Korrespondenzproblem (Aufgabenstellung), 10. Übungswoche

3. LOOP- und WHILE Programme (Aufgabenstellung), 11.Übungswoche (aktualisiert am 3.7.2019)

II. Komplexität

4. Komplexitätsklasse NP (Aufgabenstellung) 12. Übungswoche