Account
Edit tools
Internal
SucheSearch
Deutsch

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 2018

Lecturer

Tutor

SWS

  • 4/2/0

Modules

Examination method

  • Written exam

Lecture series


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 09.04.2018, statt. Weitere Termine sind jeweils:

  • Montag, 2.DS (09:20–10:50) HSZ/0004
  • Freitag, 3.DS (11:10–12:40) HSZ/0004

Klausureinsicht zur Wiederholungsklausur

Die Klausureinsicht zur Wiederholungsklausur findet am Mittwoch, den 17.04.2019, von 11:10 Uhr bis 12:30 Uhr im Raum APB 3027 statt.

Klausureinsicht

Am Mittwoch den 24.10.2018 kann Einsicht in die Klausur genommen werden. Die Einsicht findet in Raum APB/3027 statt. Bitte kommen Sie zu Beginn eines Ihrem Nachnamen zugewiesenen Zeitfensters:

  • 09:00-09:15 A-B
  • 09:15-09:30 C-D
  • 09:30-09:45 E-F
  • 09:45-10:00 G-G
  • 10:00-10:15 H-J
  • 10:15-10:30 K-K
  • 10:30-10:45 L-L
  • 10:45-11:00 M-Q
  • 11:00-11:15 R-R
  • 11:15-11:30 S-S
  • 11:30-11:45 T-V
  • 11:45-12:00 W-Z

Klausur

Die Klausur findet am 10. August 2018 um 11:10 im Hörsaalzentrum (Bergstr. 64) statt (ohne Gewähr, Änderungen werden vom Prüfungsamt bekanntgegeben). Bitte beachten Sie die Aufteilung auf zwei Hörsäle: 

* Studierende im Studiengang BACHELOR INFORMATIK: HSZ/0003
* Studierende im Studiengang DIPLOM INFORMATIK: HSZ/0004

Lernräume

In Vorbereitung auf die Klausur wird es folgende Termine für Lernräume geben:

  • Mittwoch 01.08.2018, 11-13:00 Uhr, APB/3027
  • Mittwoch 01.08.2018, 13-15:00 Uhr, APB/3027


Diese können zur angegeben Zeit ohne vorherige Terminabsprache besucht werden.


Übungen

Die Einschreibungen in die Übungsgruppen erfolgt über JExam.

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.

Übungsblätter

Aufgabenblätter werden ungefähr eine Woche vor der Übung hier bereitstellt werden. Zur Vorbereitung auf die Prüfung wird auch eine Musterklausur bereitgestellt.


Musterklausur

Als Prüfungsvorbereitung wird eine Musterklausur zur Verfügung gestellt. Diese wird am 20.07. in der Vorlesungszeit vorgerechnet werden. Folien

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/knowsys/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/TheoLog2018, 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.

Besonderen Dank gilt allen Contributors, die Anmerkungen und Verbesserungen beigetragen haben: Daniel Borchmann, Maximilian Marx, Dominik (freeDom-), CniKKoR, Marcus Rossel, SchermulyM, David Tiede, Francesco Kriegel, Robert Peine, Christian Lewe, Martin Wudenka, Sönke (eknoes), Jonny Seitz, Niklas Wünsche, und Florian Ulbrich. (Stand Juli 2018; Ergänzungen sind willkommen.)

Kontakt

Fragen können am einfachsten in Vorlesung oder Übungsgruppe gestellt werden oder per Email an das Organisationsteam (siehe Links oben). Kommentare und Bug Reports können gern auch direkt über die entsprechenden Seiten auf github gepostet werden: https://github.com/knowsys/TheoLog

Allgemein sind die Vorlesungsfolien und Übungsunterlagen ausreichend detailliert für das Studium. Weitere Lehrmaterialien können dennoch hilfreich sein, um Details nachzuschlagen oder sich weiter im Thema zu vertiefen.

Allgemeine Lehrbücher

  • Uwe Schöning: Theoretische Informatik -- kurz gefasst. Spektrum Akademischer Verlag.
(deutschsprachiger Standardtext; in der Tat ziemlich kurz gefasst)
  • Michael Sipser: Introduction to the Theory of Computation. Cengage Learning.
(Standardtext zur Berechnung und Sprachen, speziell zum Thema Komplexität zu empfehlen; leider nur auf Englisch)
  • Christopher Moore, Stephan Meterns: The Nature of Computation. Oxford University Press.
(sehr guter, moderner Text zu Komplexität und Berechnung, weniger formell; leider nur auf Englisch)
  • John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman: Einführung in Automatentheorie, Formale Sprachen und Berechenbarkeit. Pearson Studium.
(aus dem Englischen übertragenes Standardwerk; Original ev. besser)

Unterhaltung

Besonders spannende und interessante Themen aus der theoretischen Informatik und der Geschichte ihrer Protagonisten kann man auch in weniger formalen Texten nachlesen:

  • Apostolos Doxiadis, Christos Papadimitriou: Logicomix: An Epic Search for Truth. Bloomsbury
(Graphic Novel, inspiriert von Russels Leben und der Geschichte der Logik, wenn auch in Teilen frei erfunden)
  • Scott Aaronson: Quantum Computing Since Democritus. Cambridge
(informeller Text (eigentlich eine Sammlung von Blogeinträgen) mit interessanten Denkanstößen rund um Berechnung und Komplexität)
  • Douglas Hofstadter: Gödel, Escher, Bach: An Eternal Golden Braid. Basic Books
(der Klassiker; in viele Sprachen übersetzt, aber im Original am besten)

Berechnung und Komplexität

Die Bücher von Sipser und Moore & Mertens sind hier bereits sehr gute Referenzen. Wer darüber hinaus noch mehr Details sucht, der kann die folgenden Fachbücher konsultieren:

  • Christos H. Papadimitriou: Computational Complexity Academic Internet Publ., 2007.
(Standardwerk zu vielen Themen der Komplexitätstheorie)
  • Sanjeev Arora, Boaz Barak: Computational Complexity: A Modern Approach Cambridge University Press.
(Detailllierter und umfangreicher Text zur Komplexitätstheorie)

Prädikatenlogik

Die Vorlesungsfolien sollten bei diesem Thema ausreichen. Die Darstellung des Themas in der Literatur ist ziemlich uneinheitlich, so dass verschiedene Bücher oft leicht unterschiedliche Definitionen verwenden. Wer dennoch weitere Details nachschlagen will, dem nützen eventuell die folgenden Bücher:

  • Uwe Schöning: Logik für Informatiker. Spektrum Akademischer Verlag.
(leichte Abweichungen in Notation und Darstellung)
  • Martin Kreuzer, Stefan Kühling: Logik für Informatiker. Pearson Studium.
(sehr knapp und informell; eventuell interessant als Quelle für Übungsaufgaben)
(Schwerpunkt auf Logikprogrammierung und Prädikatenlogik)
(Aufgabensammlung aus den Logikvorlesungen vergangener Jahre)

Spezielle Themen

  • Torkel Franzén: 'Gödel's Theorem: An Incomplete Guide to Its Use and Abuse. A K Peters.
(Gut verdaulicher Text zu Gödels Unvollständigkeitssätzen, einschl. deren Beziehungen zur Berechenbarkeitstheorie)
  • Raymond M. Smullyan: A Beginner's Guide to Mathematical Logic. Dover Publications, 2014.
(Erster Teil: Einleitung und Logikrätsel. Zweiter Teil: Umfassende Entwicklung von Gödels Unvollständigkeitsbeweisen mit Gödel-Nummern und Gödel-Sätzen)

Subscribe to events of this course (icalendar)

Lecture Einleitung, Übersicht, Turingmaschinen DS2, April 9, 2018 in HSZ/0004 File 1,  File 2
Lecture Berechenbarkeit und Unentscheidbarkeit DS3, April 13, 2018 in HSZ/0004 File 1,  File 2
Lecture WHILE und LOOP DS2, April 16, 2018 in HSZ/0004 File 1,  File 2
Lecture Das Halteproblem und Reduktionen DS3, April 20, 2018 in HSZ/0004 File 1,  File 2
Lecture Satz von Rice/Postsches Korrespondenzproblem DS3, April 27, 2018 in HSZ/0004 File 1,  File 2
Lecture Unentscheidbare Probleme formaler Sprachen DS2, April 30, 2018 in HSZ/0004 File 1,  File 2
Lecture Einführung in die Komplexitätstheorie DS3, May 4, 2018 in HSZ/0004 File 1,  File 2
Lecture Komplexitätsklassen / Effizienz / Reduktionen DS2, May 7, 2018 in HSZ/0004 File 1,  File 2
Lecture NP und NP-Vollständigkeit DS3, May 11, 2018 in HSZ/0004 File 1,  File 2
Lecture NP (2) DS2, May 14, 2018 in HSZ/0004 File 1,  File 2
Lecture NL und PSpace DS3, May 18, 2018 in HSZ/0004 File 1,  File 2
Lecture PSpace-Vollständigkeit DS2, May 28, 2018 in HSZ/0004 File 1,  File 2
Lecture Prädikatenlogik: Syntax und Semantik DS3, June 1, 2018 in HSZ/0004 File 1,  File 2
Lecture Modelltheorie und logisches Schließen DS2, June 4, 2018 in HSZ/0004 File 1,  File 2
Lecture Logisches Schließen DS3, June 8, 2018 in HSZ/0004 File 1,  File 2
Lecture Logisches Schließen (2) DS2, June 11, 2018 in HSZ/0004 File 1,  File 2
Exercise Repetitorium 1 DS3, June 15, 2018 in HSZ/0004 File
Lecture Funktionen und Normalformen DS2, June 18, 2018 in HSZ/0004 File 1,  File 2
Lecture Unifikation DS3, June 22, 2018 in HSZ/0004 File 1,  File 2
Lecture Resolution DS2, June 25, 2018 in HSZ/0004 File 1,  File 2
Lecture Resolution (2) DS3, June 29, 2018 in HSZ/0004 File 1,  File 2
Lecture Endliche Modelle und Datenbanken DS2, July 2, 2018 in HSZ/0004 File 1,  File 2
Lecture Datalog DS3, July 6, 2018 in HSZ/0004 File 1,  File 2
Lecture Gödels Unvollständigkeitssätze DS2, July 9, 2018 in HSZ/0004 File 1,  File 2
Lecture Gödel, Turing und der ganze Rest DS3, July 13, 2018 in HSZ/0004 File 1,  File 2
Exercise Repetitorium 2 DS2, July 16, 2018 in HSZ/0004 File
Exercise Besprechung Musterklausur DS3, July 20, 2018 in HSZ/0004 File


Calendar


Retrieved from "https://iccl.inf.tu-dresden.de/w/index.php?title=Theoretische_Informatik_und_Logik_(SS2018)/en&oldid=25318"