Account
Edit tools
Intern
SucheSearch
English

Theoretische Informatik und Logik

Aus International Center for Computational Logic
Wechseln zu:Navigation, Suche

Theoretische Informatik und Logik

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

Dozent

Tutor

Umfang (SWS)

  • 4/2/0

Module

Leistungskontrolle

  • Klausur

Vorlesungsreihe


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.

Einsicht in die Wiederholungsklausur

Die Einsicht in die Wiederholungsklausur findet am 27.04.2018 von 14:00 bis 15:00 im Raum APB/3027 statt. Bitte melden Sie sich dazu vorher per E-Mail bei Stefan Borgwardt an.

Wiederholungsklausur und Lernraum

Die Wiederholungsklausur findet am 2.03.2018 von 7:30 bis 9:00 (90 Minuten) im Hörsaal HSZ/04/H statt. Bitte seien Sie mindestens 10 Minuten vor Beginn der Klausur im Hörsaal. Stellen Sie bitte auch sicher, dass Sie zur Klausur eingeschreiben sind; die Einschreibung erfolgt über JExam.

Wir bieten einen betreuten Lernraum zur Wiederholungsklausur am 27.02.2018 von 13:00 bis 14:30 im Raum APB/3027 an. Dort können Sie alle Ihre Fragen zum Vorlesungsstoff stellen.

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.

Zur Vorbereitung auf die Prüfung wird auch eine Musterklausur bereitgestellt.

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

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)

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















Abgerufen von „https://iccl.inf.tu-dresden.de/w/index.php?title=Theoretische_Informatik_und_Logik_(SS2017)&oldid=31693“