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 2024

Dozent

Tutor

Umfang (SWS)

  • 4/2/0

Module

Leistungskontrolle

  • Klausur

Matrix-Kanal

Vorlesungsreihe


Prüfung

Klausureinsicht

Ihre Klausur können Sie am 23. Oktober 2024 ab 13:00 Uhr in APB 3027 einsehen. Dafür buchen Sie sich bitte einen entsprechenden Zeitslot via OPAL. Bringen Sie zur Einsicht einen Lichtbildausweis mit und seien Sie pünktlich.

Lernräume

Wir dürfen in diesem Semester drei Lernräume anbieten:

  • Montag, 05.08.2024 14:00-15:30 Uhr in APB E023
  • Mittwoch, 07.08.2024 13:00-14:30 Uhr in APB E023
  • Freitag, 09.08.2024 13:00-14:30 Uhr in APB E023

Klausur: Zeit & Ort

Die Klausur über 90 Minuten findet am Mittwoch, den 14.08.2024 um 8:30 Uhr im HSZ/AUDI (Audimax im Hörsaalzentrum) statt. Der Einlass beginnt um 8:15 Uhr. Versuchen Sie bitte, pünktlich vor Ort zu sein.

Hilfsmittel

Es sind keine Hilfsmittel erlaubt, insbesondere keine technischen und elektronischen Hilfsmittel oder Formelsammlungen und Nachschlagewerke.

Beschreibung

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

Vorlesungen

Die Vorlesungstermine sind

  • montags 3.DS (11:10–12:40) in HÜL/S386 sowie
  • donnerstags 4.DS (13:00–14:30) in HSZ/0002.

Die erste Vorlesung findet am Montag, dem 8. April 2024 statt.

Übungen

Die Einschreibung in die Übungsgruppen wird über OPAL erfolgen. Die Einschreibung ist ab Montag, dem 8. April 2024, 18:00 Uhr möglich. Für die Teilnahme an einer Übungsgruppe ist die Einschreibung in dieser Gruppe verpflichtend. Studierenden ohne Einschreibung kann die Teilnahme an einer selbst gewählten Übung nicht garantiert werden. Übungsleiter sind berechtigt, nicht eingeschriebene Studierende bei Überfüllung aus der Übung zu verweisen.

Die folgenden Termine für Übungen werden von uns angeboten:

  • Gruppe A: montags 5. DS (14:50-16:20) in APB E008 (Übungsleiter: Florens Förster)
  • Gruppe B: dienstags 5. DS (14:50-16:20) in APB E006 (Übungsleiter: Dörthe Arndt)
  • Gruppe C: mittwochs 3. DS (11:10-12:40) in APB E008 (Übungsleiter: Anton Claußnitzer)
  • Gruppe D: mittwochs 5. DS (14:50-16:20) in APB E010 (Übungsleiter: Florens Förster)
  • Gruppe E: donnerstags 3. DS (11:10-12:40) in APB E006 (Übungsleiter: Marcos Cramer)
  • Gruppe F: donnerstags 5. DS (14:50-16:20) in POT 0106 (Übungsleiter: Linus Wemmer)
  • Gruppe G: freitags 2. DS (9:20-10:50) in APB E009 (Übungsleiter: Stephan Mennicke)

Die Übungsgruppe G wird vorläufig als hybride Übung für Studierende der TU Dresden angeboten. Die Plattform, für die Übung ist BigBlueButton. Nutzen Sie diesen Link, um der Veranstaltung zu seiner Zeit beizutreten. Sie benötigen einen ZIH-Login, um der Veranstaltung beitreten zu können. Dieses zusätzliche Angebot ist ein Pilotversuch. Sollte sich dieses Format als umständlich oder schwer durchführbar erweisen, wechseln wir zum ausschließlichen Präsenzmodus.


Der Übungsbetrieb startet am 15. April 2024 zu Ihren jeweiligen Terminen in den angegebenen Räumen. Die Übungsblätter können in der Spalte der jeweiligen Übung unter Termine und Unterlagen heruntergeladen werden.

WHILE/LOOP Simulator

Wir bieten einen Online-Simulator für WHILE- und LOOP-Programme an. Der Simulator unterstützt zusätzlich zu den Grundsprachen einige der Abkürzungen aus der Vorlesung. Im Menü unter Beispiele finden sich einige Beispielprogramme, die in das Programmfeld kopiert werden können.

Der Simulator wurde von Simon Meusel entwickelt. Der Quellcode ist frei verfügbar unter https://github.com/knowsys/while-simulator . Pull-Requests sind Willkommen.

Unterlagen

Die vollständigen Foliensätze zur Vorlesung erscheinen bis zur Woche 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

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

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

Die Nutzung der Materialien in eigenen Lehrveranstaltungen ist willkommen, sofern der obige Lizenztext in allen abgeleiteten Foliensätzen angegeben wird. Rückmeldungen sind ebenfalls willkommen (z.B. als Issue zu diesem Repository); wir verlinken hier gern auf die Homepages der entsprechenden Kurse. Interessierte Lehrende können ihre abgewandelten Quellen auch mit in diesem Respository veröffentlichen -- kontaktieren Sie Prof. Krötzsch.

Die Folien wurden erstellt von Markus Krötzsch. Eine vollständige Liste der Beitragenden ist unter https://github.com/mkroetzsch/TheoLog/graphs/contributors zu finden.

Kontakt

Zur Kommunikation unter Vorlesungsteilnehmern der TU Dresden steht ein Matrix-Kanal zur Verfügung.

Kommentare und Bug Reports können gern auch direkt über die entsprechenden Seiten auf github gepostet werden: https://github.com/mkroetzsch/TheoLog

Persönliche Fragen können direkt an das Organisationsteam (siehe Links oben) gestellt werden, falls sie aus einem zwingenden Grund nicht über andere Kanäle gerichtet werden können. Allgemeine Fragen sollten Sie aber immer in geteilten Kanälen stellen, damit auch Ihre Kommilitoninnen und Kommilitonen davon profitieren (oder vielleicht sogar direkt helfen können).

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 und Übersicht DS3, 8. April 2024 in HÜL/S386 Datei 1,  Datei 2
Vorlesung Berechenbarkeit und Unentscheidbarkeit DS4, 11. April 2024 in HSZ/0002 Datei 1,  Datei 2
Übung Übung 1 Datei
Vorlesung WHILE und LOOP DS3, 15. April 2024 in HÜL/S386 Datei 1,  Datei 2
Vorlesung Das Halteproblem und Reduktionen DS4, 18. April 2024 in HSZ/0002 Datei 1,  Datei 2
Übung Übung 2 Datei
Vorlesung Der Satz von Rice und das Postsche Korrespondenzproblem DS3, 22. April 2024 in HÜL/S386 Datei 1,  Datei 2
Vorlesung Unentscheidbare Probleme formaler Sprachen DS4, 25. April 2024 in HSZ/0002 Datei 1,  Datei 2
Übung Übung 3 Datei
Vorlesung Einführung in die Komplexitätstheorie DS3, 29. April 2024 in HÜL/S386 Datei 1,  Datei 2
Vorlesung Beziehungen zwischen Komplexitätsklassen / Effizient lösbare Probleme DS4, 2. Mai 2024 in HSZ/0002 Datei 1,  Datei 2
Übung Übung 4 Datei
Vorlesung NP und NP-Vollständigkeit DS3, 6. Mai 2024 in HÜL/S386 Datei 1,  Datei 2
Entfällt Christi Himmelfahrt (gesetzlicher Feiertag) DS4, 9. Mai 2024 in HSZ/0002
Übung Übung 5 Datei
Vorlesung NP, Teil 2 DS3, 13. Mai 2024 in HÜL/S386 Datei 1,  Datei 2
Vorlesung NL und PSpace DS4, 16. Mai 2024 in HSZ/0002 Datei 1,  Datei 2
Entfällt Pfingstmontag (gesetzlicher Feiertag) DS3, 20. Mai 2024 in HÜL/S386
Entfällt Pfingsten (vorlesungsfreie Woche) DS4, 23. Mai 2024 in HSZ/0002
Übung Übung 6 Datei
Vorlesung PSpace-Vollständigkeit DS3, 27. Mai 2024 in HÜL/S386 Datei 1,  Datei 2
Vorlesung Prädikatenlogik: Syntax und Semantik DS4, 30. Mai 2024 in HSZ/0002 Datei 1,  Datei 2
Übung Übung 7 Datei
Vorlesung Modelltheorie und logisches Schließen DS3, 3. Juni 2024 in HÜL/S386 Datei 1,  Datei 2
Vorlesung Logisches Schließen (1) DS4, 6. Juni 2024 in HSZ/0002 Datei 1,  Datei 2
Entfällt Keine Vorlesung DS3, 10. Juni 2024 in HÜL/S386
Entfällt OUTPUT.DD DS4, 13. Juni 2024 in HSZ/0002
Übung Übung 8 Datei
Vorlesung Logisches Schließen (2) DS3, 17. Juni 2024 in HÜL/S386 Datei 1,  Datei 2
Vorlesung Funktionen und Normalformen DS4, 20. Juni 2024 in HSZ/0002 Datei 1,  Datei 2
Übung Übung 9 Datei
Vorlesung Unifikation DS3, 24. Juni 2024 in HÜL/S386 Datei 1,  Datei 2
Vorlesung Resolution (1) DS4, 27. Juni 2024 in HSZ/0002 Datei 1,  Datei 2
Übung Übung 10 Datei
Vorlesung Resolution (2) DS3, 1. Juli 2024 in HÜL/S386 Datei 1,  Datei 2
Vorlesung Endliche Modelle und Datenbanken DS4, 4. Juli 2024 in HSZ/0002 Datei 1,  Datei 2
Übung Übung 11 Datei
Vorlesung Datalog DS3, 8. Juli 2024 in HÜL/S386 Datei 1,  Datei 2
Vorlesung Gödels 1. Unvollständigkeitssatz DS4, 11. Juli 2024 in HSZ/0002 Datei 1,  Datei 2
Übung Übung 12 Datei
Vorlesung Gödel, Turing und der ganze Rest DS3, 15. Juli 2024 in HÜL/S386 Datei 1,  Datei 2
Vorlesung Repetitorium DS4, 18. Juli 2024 in HSZ/0002 Datei
Konsultation Lernraum - Probeklausur (Achtung: 14:00-15:30 Uhr) DS4, 5. August 2024 in APB E023 Datei 1,  Datei 2
Konsultation Lernraum DS4, 7. August 2024 in APB E023
Konsultation Lernraum DS4, 9. August 2024 in APB E023


Kalender
























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