Theoretische Informatik und Logik(SS2019)

Theoretische Informatik und Logik

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

Dozent

• Steffen Hölldobler

Tutor

• Emmanuelle Dietz
• Marcos Cramer

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