Theoretische Informatik und Logik (SS2017)

Theoretische Informatik und Logik

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

Dozent

• Markus Krötzsch

Tutor

• Daniel Borchmann
• Francesco Kriegel
• Florian Starke

Umfang (SWS)

• 4/2/0

Module

• INF-B-290
• INF-D-330

Leistungskontrolle

• Klausur

• Information
• Termine und Unterlagen

Die Vorlesung 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.

Termine

Die erste Vorlesung findet am Mittwoch, den 05.04.2017, statt. Weitere Termine sind jeweils:

• Mittwoch, 4.DS (13:00–14:30) HSZ/0004
• Freitag, 3.DS (11:10–12:40) HSZ/0004

Übungen

Die Einschreibungen in die Übungsgruppen erfolgt über JExam. Die Einschreibung ist möglich ab 28. März, 17:00 Uhr.

Bitte beachten Sie: 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 sind berechtigt, nicht eingeschriebene Studierende bei Überfüllung aus der Übung zu verweisen.

Achtung

• Die Übungen beginnen in der zweiten Vorlesungswoche
• Die Übung am Freitag in der 2. DS einmalig vom 14. April auf den 13. April, 1.DS, APB/E008 verlegt.
• Ab sofort (20. April) gibt es einen weiteren Übungstermin Donnerstag, 1. DS, APB/E008; die Einschreibung über jExam ist ab sofort möglich
• Die Übung Mittwoch 5. DS bei Francesco Kriegel findet ab sofort im Raum *APB/E010* statt
• Die Übung Mittwoch 5. DS bei Francesco Kriegel wird einmalig vom vorlesungsfreien Dies Academicus auf Freitag, den 19. Mai, 2. DS, APB/E008 verlegt.
• Die Übung am Donnerstag, den 25. Mai, in der 1. DS wird einmalig verlegt auf Mittwoch, den 24. Mai, 1. DS, Raum APB/E023.
• Die Übung am Donnerstag, den 25. Mai, in der 6. DS wird einmalig verlegt auf Montag, den 29. Mai, 2. DS, Raum WIL/C104.
• Die Übung am Dienstag, den 13. Juni, 5. DS findet einmalig zeitgleich mit der Übung am Mittwoch, dem 14. Juni, 5. DS, im selben Raum statt.

Übungsblätter

Aufgabenblätter werden ungefähr eine Woche vor der Übung hier bereitstellt werden.

• 1. Übungsblatt
• 2. Übungsblatt
• 3. Übungsblatt
• 4. Übungsblatt (Haskell-Programm (als pdf) zur „Lösung" des PCP)
• 5. Übungsblatt
• 1. Repetitorium
• 6. Übungsblatt, Musterlösung für Aufgabe 3
• 7. Übungsblatt, Musterlösung für Aufgabe 4
• 8. Übungsblatt

Unterlagen

Die vollständigen Foliensätze zur Vorlesung erscheinen spätestens kurz nach der Vorlesung online (siehe Termine und Unterlagen). Weiterführende Literatur ist unter Literatur angegeben. Die Quellen der Vorlesungsfolien sind auf github verfügbar: https://github.com/mkroetzsch/TheoLog

Alle Foliensätze der Vorlesungen können entsprechend den Lizensbedingungen von Creative Commons CC By 3.0 Deutschland genutzt, weitergegeben und modifiziert werden. Als Namensnennung ist folgende Angabe einzufügen:

(C) Markus Krötzsch, https://iccl.inf.tu-dresden.de/web/TheoLog2017, CC BY 3.0 DE

Bildrechte können davon abweichen und sind gesondert angegeben. Die Foliensätze enthalten keinerlei Texte, die aus Werken entnommen sind, für welche die VG Wort Verwertungsrechte vertritt.

Kontakt

Fragen können am einfachsten in Vorlesung oder Übungsgruppe gestellt werden oder per Email an Markus Krötzsch und Daniel Borchmann. Kommentare und Bug Reports können gern auch direkt über die entsprechenden Seiten auf github gepostet werden: https://github.com/mkroetzsch/TheoLog

Veranstaltungskalender abonnieren (icalendar)

Vorlesung	Einleitung, Übersicht, Turingmaschinen	DS4, 5. April 2017 in HSZ/0004	Datei 1,  Datei 2
Vorlesung	Berechenbarkeit und Unentscheidbarkeit	DS3, 7. April 2017 in HSZ/0004	Datei 1,  Datei 2
Vorlesung	WHILE und LOOP	DS4, 12. April 2017 in HSZ/0004	Datei 1,  Datei 2
Vorlesung	Das Halteproblem und Reduktionen	DS4, 19. April 2017 in HSZ/0004	Datei 1,  Datei 2
Vorlesung	Der Satz von Rice und das Postsche Korrespondenzproblem	DS3, 21. April 2017 in HSZ/0004	Datei 1,  Datei 2
Vorlesung	Unentscheidbare Probleme formaler Sprachen	DS4, 26. April 2017 in HSZ/0004	Datei 1,  Datei 2
Vorlesung	Einführung in die Komplexitätstheorie	DS3, 28. April 2017 in HSZ/0004	Datei 1,  Datei 2
Vorlesung	Komplexitätsklassen / Effizienz / Reduktionen	DS4, 3. Mai 2017 in HSZ/0004	Datei 1,  Datei 2
Übung	Repetitorium 1	DS3, 5. Mai 2017 in HSZ/0004
Vorlesung	NP und NP-Vollständigkeit	DS4, 10. Mai 2017 in HSZ/0004	Datei 1,  Datei 2
Vorlesung	NP (Teil 2)	DS3, 12. Mai 2017 in HSZ/0004	Datei 1,  Datei 2
Vorlesung	NL und PSpace	DS3, 19. Mai 2017 in HSZ/0004	Datei 1,  Datei 2
Vorlesung	PSpace-Vollständigkeit	DS4, 24. Mai 2017 in HSZ/0004	Datei 1,  Datei 2
Vorlesung	Prädikatenlogik: Syntax und Semantik	DS3, 26. Mai 2017 in HSZ/0004	Datei 1,  Datei 2
Vorlesung	Modelltheorie und logisches Schließen	DS4, 31. Mai 2017 in HSZ/0004	Datei 1,  Datei 2
Übung	Repetitorium 2	DS3, 2. Juni 2017 in HSZ/0004
Vorlesung	Logisches Schließen	DS4, 14. Juni 2017 in HSZ/0004	Datei 1,  Datei 2
Vorlesung	Logisches Schließen (2)	DS3, 16. Juni 2017 in HSZ/0004	Datei 1,  Datei 2
Vorlesung	Funktionen und Normalformen	DS4, 21. Juni 2017 in HSZ/0004	Datei 1,  Datei 2
Vorlesung	Unifikation	DS3, 23. Juni 2017 in HSZ/0004	Datei 1,  Datei 2
Vorlesung	Resolution	DS4, 28. Juni 2017 in HSZ/0004	Datei 1,  Datei 2
Vorlesung	Resolution / Endliche Modelle	DS3, 30. Juni 2017 in HSZ/0004	Datei 1,  Datei 2
Vorlesung	Gödels Unvollständigkeitssätze	DS4, 5. Juli 2017 in HSZ/0004	Datei 1,  Datei 2
Übung	Repetitorium 3	DS3, 7. Juli 2017 in HSZ/0004
Übung	Besprechung Probeklausur	DS4, 12. Juli 2017 in HSZ/0004
Vorlesung	Gödel, Turing und der ganze Rest	DS3, 14. Juli 2017 in HSZ/0004	Datei 1,  Datei 2

Kalender