International Center for Computational Logic - Benutzerbeiträge [de]

Daniel Borchmann

2017-08-29T13:24:08Z

Daniel Borchmann:

{{Mitarbeiter
|Vorname=Daniel
|Nachname=Borchmann
|Akademischer Titel=Dr. rer. nat.
|Forschungsgruppe=Automatentheorie
|Stellung=Wissenschaftlicher Mitarbeiter
|Ehemaliger=1
|Telefon=+49 351 463 38351
|Email=daniel.borchmann@tu-dresden.de
|Raum=APB 3024
|Bild=Borchmann-real-23.png
|DBLP=http://dblp.uni-trier.de/pers/hd/b/Borchmann:Daniel.html
|Google Scholar=https://scholar.google.com/citations?user=Cum9LiAAAAAJ&hl=en
|Alternative URI=http://lat.inf.tu-dresden.de/~borch/
|Public Key=Borchmann-public-key.asc
|Publikationen anzeigen=1
|Abschlussarbeiten anzeigen=1
}}

Daniel Borchmann

2017-07-24T10:32:35Z

Daniel Borchmann:

{{Mitarbeiter
|Vorname=Daniel
|Nachname=Borchmann
|Akademischer Titel=Dr. rer. nat.
|Forschungsgruppe=Automatentheorie
|Stellung=Wissenschaftlicher Mitarbeiter
|Ehemaliger=0
|Telefon=+49 351 463 38351
|Email=daniel.borchmann@tu-dresden.de
|Raum=APB 3024
|Bild=Borchmann-real-23.png
|DBLP=http://dblp.uni-trier.de/pers/hd/b/Borchmann:Daniel.html
|Google Scholar=https://scholar.google.com/citations?user=Cum9LiAAAAAJ&hl=en
|Alternative URI=http://lat.inf.tu-dresden.de/~borch/
|Public Key=Borchmann-public-key.asc
|Publikationen anzeigen=1
|Abschlussarbeiten anzeigen=1
}}

Datei:Borchmann-public-key.asc

2017-07-24T10:32:17Z

Daniel Borchmann:

Formale Systeme (WS2016)

2017-07-18T06:32:36Z

Daniel Borchmann: Aufgeräumt

{{Vorlesung
|Title=Formale Systeme
|Research group=Wissensbasierte Systeme
|Lecturers=Markus Krötzsch;
|Tutors=Monika Sturm; Daniel Borchmann;
|Term=WS
|Year=2016
|Module=INF-B-270, INF-B-275, INF-LE-EUI, IST-05-PF-HS
|SWSLecture=4
|SWSExercise=2
|SWSPractical=0
|Exam type=Klausur
|Description=Die Vorlesung ''Formale Systeme'' vermittelt eine Einleitung in die Gebiete der formalen Sprachen, Automatentheorie und Aussagenlogik. Dies beinhaltet einige der wichtigsten Grundlagen der Informatik, wie z.B. reguläre Ausdrücke, formale Grammatiken sowie Methoden zur praktischen Lösung von "schweren" (NP-vollständigen) Problemen. Damit bildet die Vorlesung die Grundlage für die Vorlesung ''Theoretische Informatik und Logik'' und für viele vertiefende Vorlesungen.

== Wichtige Hinweise zur Wiederholungsklausur ==

Voraussetzung für die Teilnahme an der Wiederholungsklausur ''Formale Systeme'' ist
eine ordnungsgemäße Einschreibung!

Die Klausur findet am 08.08.2017 um 09:20 Uhr im ZEU/LICH/H statt. Die
Plätze sind spätestens 10 Minuten vor Beginn einzunehmen. Für die
Bearbeitung der Klausur stehen 90 Minuten zur Verfügung. Es sind keine
Hilfsmittel zugelassen. Bitte vergessen Sie nicht, Ihren
Studentenausweis und einen Lichtbildausweis mitzubringen.

== Termine ==

Die erste Vorlesung ist am Montag, 10.10.2016. Weitere Termine sind jeweils:

* montags 3.DS (11:10–12:40) HSZ/0002
* donnerstags 4.DS (13:00–14:30) HSZ/0003

mit Ausnahme von Mo, 31.10., (Reformationstag) und der vorlesungsfreien Zeit zum Jahreswechsel (keine Vorlesungen vom 22.12.2016 bis zum 3.1.2017). Die Prüfung findet am 14.2.2017 statt. Alle Studierende müssen sich mittels der in ihrem Studiengang verwendeten Verfahren anmelden.

== Hinweise ==

Mathematikstudenten, welche die Vorlesung im Rahmen ihres Nebenfachs besuchen, melden sich bitte so schnell wie möglich per E-Mail bei Herrn Borchmann.

== Übungen ==

Die Einschreibungen in die Übungsgruppen erfolgt über [https://jexam.inf.tu-dresden.de 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. Die Einschreibung ist nur noch bis '''Montag, den 17. Oktober''' möglich.

* Die Übung am Donnerstag in der 1. DS findet im Raum APB E008 statt, die Übung am Freitag in der 3. DS findet im Raum APB E006 statt. Zu beiden Zeitslots finden insbesondere ''keine Übungen im HSZ'' statt.

* Die Übungen beginnen aber der 2. Vorlesungswoche (42. KW), also ab dem 17. Oktober.

* Die Übung am Mittwoch in der 6. Doppelstunde findet nicht mehr in der E009 statt, sondern in der E006.

* Die Übung am Freitag, den 18. November, in der 5. DS im Raum E009 findet einmalig nicht statt.

* Die Übungen finden auch in der letzten Vorlesungswoche statt, bis also einschließlich 03.02.2017.

===Übungsblätter===

* [[Medium:FS16-uebung-01.pdf|1. Übungsblatt]]
* [[Medium:FS16-uebung-02.pdf|2. Übungsblatt]]
* [[Medium:FS16-uebung-03.pdf|3. Übungsblatt]]
* [[Medium:FS2016-uebung-04.pdf|4. Übungsblatt]]
* [[Medium:FS2016-uebung-05.pdf|5. Übungsblatt]]
* [[Medium:FS2016-uebung-06.pdf|6. Übungsblatt]]
* [[Medium:FS2016-uebung-07.pdf|7. Übungsblatt]]
* [[Medium:FS2016-uebung-08.pdf|8. Übungsblatt]]
* [[Medium:FS2016-uebung-09.pdf|9. Übungsblatt]]
* [[Medium:FS2016-uebung-10.pdf|10. Übungsblatt]]
* [[Medium:FS2016-uebung-11.pdf|11. Übungsblatt]]
* [[Medium:FS2016-uebung-12.pdf|12. Übungsblatt]]
* [[Medium:FS2016-uebung-13.pdf|13. Übungsblatt]]

===Repetitorien===

* [[Medium:FS2016-repititorium-1.pdf|Aufgabenblatt für das 1. Repetitorium]]
* [[Medium:FS2016-repetitorium-2.pdf|Aufgabenblatt für das 2. Repetitorium]]; dieses Repetitorium findet zur Vorlesungszeit am Montag, den 30.01. statt.

===Musterklausur===

Als Prüfungsvorbereitung wird eine [[Medium:FS2016-musterklausur.pdf|Musterklausur]] zur Verfügung gestellt. Diese wird am 26.01. in der Vorlesungszeit vorgerechnet werden.

==Lernraum==

Es wird zur Prüfungsvorbereitung ein Lernraum angeboten. Dieser findet am 10.02.2017 statt. Bitte beachten dazu Sie die aktuellen Aushänge in der Fakultät.

== 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.

Alle Foliensätze der Vorlesungen können entsprechend den Lizensbedingungen von [https://creativecommons.org/licenses/by/3.0/de/ 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/FS2016, 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 ==

Für Fragen rund um den Stoff und Vorlesungsbetrieb ist eine Mailingliste eingerichtet worden, auf der sich Teilnehmer_innen der Vorlesung einschreiben können. Dazu muss nur das [https://mailman.zih.tu-dresden.de/groups/listinfo/inf-thi-fs2016 Anmeldeformular] ausgefüllt werden. '''Fast alle Fragen sollten auf diesem Weg gestellt werden.''' Auch Hinweise zu Tippfehlern in den Vorlesungsfolien sollten am besten direkt an die Liste geschickt werden.

Persönliche Fragen können auch direkt an das Organisationsteam (siehe Links oben) gestellt werden, falls sie aus einem zwingenden Grund nicht an die Mailingliste gerichtet werden können. Allgemein Fragen sollten Sie aber immer an die Liste richten, damit auch Ihre Kommilitonen davon profitieren (oder vielleicht sogar direkt helfen können).
|Literature=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.

== Formale Sprachen, Komplexität und Entscheidbarkeit ==

=== Lehrbücher ===

* Uwe Schöning: '''Theoretische Informatik -- kurz gefasst.''' Spektrum Akademischer Verlag.
: ''(deutschsprachiger Standardtext; in der Tat ziemlich kurz gefasst)''
* 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)''
* Michael Sipser: '''Introduction to the Theory of Computation.''' Cengage Learning.
: ''(Standardtext zu Sprachen und Berechnungskomplexität; leider nur auf Englisch)''

=== Online verfügbare Skripte ===

* [[Franz Baader]]: '''[https://lat.inf.tu-dresden.de/teaching/ws2013-2014/FS/script_2016-02.pdf Skript Formale Systeme, Teil 1 – Automaten und formale Sprachen].''' TU Dresden.
* [[Christel Baier]], [[Manuela Berg]], [[Walter Nauber]]: '''[http://www.inf.tu-dresden.de/content/institutes/thi/algi/lehre/WS1415/FS/lecture_notes/Skript_FS_C_Baier_WS1112.pdf Formale Systeme WS 2011/2012: Skript zur Vorlesung].''' TU Dresden.

Die Vorlesungen haben kleine Abweichungen von diesen Skripten, stimmen aber in vielen wichtigen Punkten überein.

== Aussagenlogik ==

Die Vorlesungsfolien sollten bei diesem Thema ausreichen. 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)''
* [[Steffen Hölldobler]]: '''[[Book3008|Logik und Logikprogrammierung]].''' Synchron Verlag.
: ''(Schwerpunkt auf Logikprogrammierung und Prädikatenlogik, aber auch einiges zur Aussagenlogik)''
* [[Steffen Hölldobler]], [[Sebastian Bader]], [[Bertram Fronhöfer]], [[Ursula Hans]], [[Pascal Hitzler]], [[Markus Krötzsch]], [[Tobias Pietzsch]]: '''[[Book3001|Logik und Logikprogrammierung, Band 2: Aufgaben und Lösungen]]''' Synchron Verlag
: ''(Aufgabensammlung aus den Logikvorlesungen vergangener Jahre)''
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Willkommen/Einleitung formale Sprachen
|Room=HSZ/0002
|Date=2016/10/10
|DS=DS3
|Download=FS2016-01-overlay.pdf, FS2016-01-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Grammatiken und die Chomsky-Hierarchie
|Room=HSZ/0003
|Date=2016/10/13
|DS=DS4
|Download=FS2016-02-overlay.pdf, FS2016-02-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Endliche Automaten
|Room=HSZ/0002
|Date=2016/10/17
|DS=DS3
|Download=FS2016-03-overlay.pdf, FS2016-03-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Nichtdeterministische endliche Automaten
|Room=HSZ/0003
|Date=2016/10/20
|DS=DS4
|Download=FS2016-04-overlay.pdf, FS2016-04-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Abschlusseigenschaften regulärer Sprachen
|Room=HSZ/0002
|Date=2016/10/24
|DS=DS3
|Download=FS2016-05-overlay.pdf, FS2016-05-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Reguläre Ausdrücke (1)
|Room=HSZ/0003
|Date=2016/10/27
|DS=DS4
|Download=FS2016-06-overlay.pdf, FS2016-06-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Reguläre Ausdrücke (2)
|Room=HSZ/0003
|Date=2016/11/03
|DS=DS4
|Download=FS2016-07-overlay.pdf, FS2016-07-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Minimale Automaten
|Room=HSZ/0002
|Date=2016/11/07
|DS=DS3
|Download=FS2016-08-overlay.pdf, FS2016-08-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Minimale Automaten (2)
|Room=HSZ/0003
|Date=2016/11/10
|DS=DS4
|Download=FS2016-09-overlay.pdf, FS2016-09-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Grenzen regulärer Sprachen/Probleme für Automaten
|Room=HSZ/0002
|Date=2016/11/14
|DS=DS3
|Download=FS2016-10-overlay.pdf, FS2016-10-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Von regulären zu kontextfreien Sprachen
|Room=HSZ/0003
|Date=2016/11/17
|DS=DS4
|Download=FS2016-11-overlay.pdf, FS2016-11-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Das Wortproblem kontextfreier Sprachen
|Room=HSZ/0002
|Date=2016/11/21
|DS=DS3
|Download=FS2016-12-overlay.pdf,FS2016-12-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Das Pumping Lemma kontextfreier Sprachen
|Room=HSZ/0003
|Date=2016/11/24
|DS=DS4
|Download=FS2016-13-overlay.pdf, FS2016-13-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Abschlusseigenschaften kontextfreier Sprachen
|Room=HSZ/0002
|Date=2016/11/28
|DS=DS3
|Download=FS2016-14-overlay.pdf, FS2016-14-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Kellerautomaten
|Room=HSZ/0003
|Date=2016/12/01
|DS=DS4
|Download=FS2016-15-overlay.pdf, FS2016-15-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Kellerautomaten und Typ-2-Grammatiken
|Room=HSZ/0002
|Date=2016/12/05
|DS=DS3
|Download=FS2016-16-overlay.pdf, FS2016-16-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Repetitorium 1
|Room=HSZ/0003
|Date=2016/12/08
|DS=DS4
|Download=FS2016-repititorium-1.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Deterministische Typ-2-Sprachen / Entscheidungsprobleme
|Room=HSZ/0002
|Date=2016/12/12
|DS=DS3
|Download=FS2016-17-overlay.pdf, FS2016-17-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Turingmaschinen
|Room=HSZ/0003
|Date=2016/12/15
|DS=DS4
|Download=FS2016-18-overlay.pdf, FS2016-18-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Nichtdeterminismus und Unentscheidbarkeit
|Room=HSZ/0002
|Date=2016/12/19
|DS=DS3
|Download=FS2016-19-overlay.pdf, FS2016-19-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Typ-0- und Typ-1-Sprachen
|Room=HSZ/0003
|Date=2017/01/05
|DS=DS4
|Download=FS2016-20-overlay.pdf, FS2016-20-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Aussagenlogik
|Room=HSZ/0002
|Date=2017/01/09
|DS=DS3
|Download=FS2016-21-overlay.pdf, FS2016-21-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Äquivalenz und Normalformen
|Room=HSZ/0003
|Date=2017/01/12
|DS=DS4
|Download=FS2016-22-overlay.pdf, FS2016-22-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Logisches Schließen
|Room=HSZ/0002
|Date=2017/01/16
|DS=DS3
|Download=FS2016-23-overlay.pdf, FS2016-23-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Horn-Logik / Komplexität
|Room=HSZ/0003
|Date=2017/01/19
|DS=DS4
|Download=FS2016-24-overlay.pdf, FS2016-24-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NP-Vollständigkeit
|Room=HSZ/0002
|Date=2017/01/23
|DS=DS3
|Download=FS2016-25-overlay.pdf, FS2016-25-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Besprechung Musterklausur
|Room=HSZ/0003
|Date=2017/01/26
|DS=DS4
|Download=FS2016-musterklausur.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Repetitorium 2
|Room=HSZ/0002
|Date=2017/01/30
|DS=DS3
|Download=FS2016-repetitorium-2.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Zusammenfassung und Ausblick
|Room=HSZ/0003
|Date=2017/02/02
|DS=DS4
|Download=FS2016-26-overlay.pdf, FS2016-26-print.pdf,
}}

Formale Systeme (WS2016)

2017-07-18T06:31:12Z

Daniel Borchmann: Hinweis zur Wiederholungsklausur

{{Vorlesung
|Title=Formale Systeme
|Research group=Wissensbasierte Systeme
|Lecturers=Markus Krötzsch;
|Tutors=Monika Sturm; Daniel Borchmann;
|Term=WS
|Year=2016
|Module=INF-B-270, INF-B-275, INF-LE-EUI, IST-05-PF-HS
|SWSLecture=4
|SWSExercise=2
|SWSPractical=0
|Exam type=Klausur
|Description=Die Vorlesung ''Formale Systeme'' vermittelt eine Einleitung in die Gebiete der formalen Sprachen, Automatentheorie und Aussagenlogik. Dies beinhaltet einige der wichtigsten Grundlagen der Informatik, wie z.B. reguläre Ausdrücke, formale Grammatiken sowie Methoden zur praktischen Lösung von "schweren" (NP-vollständigen) Problemen. Damit bildet die Vorlesung die Grundlage für die Vorlesung ''Theoretische Informatik und Logik'' und für viele vertiefende Vorlesungen.

== Wichtige Hinweise zur Wiederholungsklausur ==

Voraussetzung für die Teilnahme an der Klausur ''Formale Systeme'' ist
eine ordnungsgemäße Einschreibung!

Die Klausur findet am 08.08.2017 um 09:20 Uhr im ZEU/LICH/H statt. Die
Plätze sind spätestens 10 Minuten vor Beginn einzunehmen. Für die
Bearbeitung der Klausur stehen 90 Minuten zur Verfügung. Es sind keine
Hilfsmittel zugelassen. Bitte vergessen Sie nicht, Ihren
Studentenausweis und einen Lichtbildausweis mitzubringen.

== Termin zur Klausureinsicht ==

Die Einsicht zur Klausur findet am Dienstag, den 2. Mai 2017, nachmittags statt. Zur Anmeldung schreiben Sie bitte eine kurze Mitteilung an Daniel Borchmann mit Namen, Matrikelnummer, und Wunschzeit (zwischen 13:00 und 16:00 Uhr).

== Wichtige Hinweise zur Klausur ==
Voraussetzung für die Teilnahme an der Klausur ''Formale Systeme'' ist
eine ordnungsgemäße Einschreibung!

Die Klausur findet am 14.02.2017 um 13:00 Uhr im HSZ statt. Die
Plätze sind spätestens 10 Minuten vor Beginn einzunehmen. Für die
Bearbeitung der Klausur stehen 90 Minuten zur Verfügung. Es sind keine
Hilfsmittel zugelassen. Bitte vergessen Sie nicht, Ihren
Studentenausweis und einen Lichtbildausweis mitzubringen.

Die Aufteilung in die einzelnen Hörsäle erfolgt nach Studiengang:
* Studiengang Bachelor Informatik HSZ/0002
* Studiengang Bachelor Medieninformatik: HSZ/0004
* Studiengänge Bachelor/Master Mathematik: HSZ/0004
* Studiengang Diplom Informatik: HSZ/0003
* Studiengänge Informationssystemtechnik: HSZ/0003

== Termine ==

Die erste Vorlesung ist am Montag, 10.10.2016. Weitere Termine sind jeweils:

* montags 3.DS (11:10–12:40) HSZ/0002
* donnerstags 4.DS (13:00–14:30) HSZ/0003

mit Ausnahme von Mo, 31.10., (Reformationstag) und der vorlesungsfreien Zeit zum Jahreswechsel (keine Vorlesungen vom 22.12.2016 bis zum 3.1.2017). Die Prüfung findet am 14.2.2017 statt. Alle Studierende müssen sich mittels der in ihrem Studiengang verwendeten Verfahren anmelden.

== Hinweise ==

Mathematikstudenten, welche die Vorlesung im Rahmen ihres Nebenfachs besuchen, melden sich bitte so schnell wie möglich per E-Mail bei Herrn Borchmann.

== Übungen ==

Die Einschreibungen in die Übungsgruppen erfolgt über [https://jexam.inf.tu-dresden.de 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. Die Einschreibung ist nur noch bis '''Montag, den 17. Oktober''' möglich.

* Die Übung am Donnerstag in der 1. DS findet im Raum APB E008 statt, die Übung am Freitag in der 3. DS findet im Raum APB E006 statt. Zu beiden Zeitslots finden insbesondere ''keine Übungen im HSZ'' statt.

* Die Übungen beginnen aber der 2. Vorlesungswoche (42. KW), also ab dem 17. Oktober.

* Die Übung am Mittwoch in der 6. Doppelstunde findet nicht mehr in der E009 statt, sondern in der E006.

* Die Übung am Freitag, den 18. November, in der 5. DS im Raum E009 findet einmalig nicht statt.

* Die Übungen finden auch in der letzten Vorlesungswoche statt, bis also einschließlich 03.02.2017.

===Übungsblätter===

* [[Medium:FS16-uebung-01.pdf|1. Übungsblatt]]
* [[Medium:FS16-uebung-02.pdf|2. Übungsblatt]]
* [[Medium:FS16-uebung-03.pdf|3. Übungsblatt]]
* [[Medium:FS2016-uebung-04.pdf|4. Übungsblatt]]
* [[Medium:FS2016-uebung-05.pdf|5. Übungsblatt]]
* [[Medium:FS2016-uebung-06.pdf|6. Übungsblatt]]
* [[Medium:FS2016-uebung-07.pdf|7. Übungsblatt]]
* [[Medium:FS2016-uebung-08.pdf|8. Übungsblatt]]
* [[Medium:FS2016-uebung-09.pdf|9. Übungsblatt]]
* [[Medium:FS2016-uebung-10.pdf|10. Übungsblatt]]
* [[Medium:FS2016-uebung-11.pdf|11. Übungsblatt]]
* [[Medium:FS2016-uebung-12.pdf|12. Übungsblatt]]
* [[Medium:FS2016-uebung-13.pdf|13. Übungsblatt]]

===Repetitorien===

* [[Medium:FS2016-repititorium-1.pdf|Aufgabenblatt für das 1. Repetitorium]]
* [[Medium:FS2016-repetitorium-2.pdf|Aufgabenblatt für das 2. Repetitorium]]; dieses Repetitorium findet zur Vorlesungszeit am Montag, den 30.01. statt.

===Musterklausur===

Als Prüfungsvorbereitung wird eine [[Medium:FS2016-musterklausur.pdf|Musterklausur]] zur Verfügung gestellt. Diese wird am 26.01. in der Vorlesungszeit vorgerechnet werden.

==Lernraum==

Es wird zur Prüfungsvorbereitung ein Lernraum angeboten. Dieser findet am 10.02.2017 statt. Bitte beachten dazu Sie die aktuellen Aushänge in der Fakultät.

== 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.

Alle Foliensätze der Vorlesungen können entsprechend den Lizensbedingungen von [https://creativecommons.org/licenses/by/3.0/de/ 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/FS2016, 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 ==

Für Fragen rund um den Stoff und Vorlesungsbetrieb ist eine Mailingliste eingerichtet worden, auf der sich Teilnehmer_innen der Vorlesung einschreiben können. Dazu muss nur das [https://mailman.zih.tu-dresden.de/groups/listinfo/inf-thi-fs2016 Anmeldeformular] ausgefüllt werden. '''Fast alle Fragen sollten auf diesem Weg gestellt werden.''' Auch Hinweise zu Tippfehlern in den Vorlesungsfolien sollten am besten direkt an die Liste geschickt werden.

Persönliche Fragen können auch direkt an das Organisationsteam (siehe Links oben) gestellt werden, falls sie aus einem zwingenden Grund nicht an die Mailingliste gerichtet werden können. Allgemein Fragen sollten Sie aber immer an die Liste richten, damit auch Ihre Kommilitonen davon profitieren (oder vielleicht sogar direkt helfen können).
|Literature=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.

== Formale Sprachen, Komplexität und Entscheidbarkeit ==

=== Lehrbücher ===

* Uwe Schöning: '''Theoretische Informatik -- kurz gefasst.''' Spektrum Akademischer Verlag.
: ''(deutschsprachiger Standardtext; in der Tat ziemlich kurz gefasst)''
* 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)''
* Michael Sipser: '''Introduction to the Theory of Computation.''' Cengage Learning.
: ''(Standardtext zu Sprachen und Berechnungskomplexität; leider nur auf Englisch)''

=== Online verfügbare Skripte ===

* [[Franz Baader]]: '''[https://lat.inf.tu-dresden.de/teaching/ws2013-2014/FS/script_2016-02.pdf Skript Formale Systeme, Teil 1 – Automaten und formale Sprachen].''' TU Dresden.
* [[Christel Baier]], [[Manuela Berg]], [[Walter Nauber]]: '''[http://www.inf.tu-dresden.de/content/institutes/thi/algi/lehre/WS1415/FS/lecture_notes/Skript_FS_C_Baier_WS1112.pdf Formale Systeme WS 2011/2012: Skript zur Vorlesung].''' TU Dresden.

Die Vorlesungen haben kleine Abweichungen von diesen Skripten, stimmen aber in vielen wichtigen Punkten überein.

== Aussagenlogik ==

Die Vorlesungsfolien sollten bei diesem Thema ausreichen. 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)''
* [[Steffen Hölldobler]]: '''[[Book3008|Logik und Logikprogrammierung]].''' Synchron Verlag.
: ''(Schwerpunkt auf Logikprogrammierung und Prädikatenlogik, aber auch einiges zur Aussagenlogik)''
* [[Steffen Hölldobler]], [[Sebastian Bader]], [[Bertram Fronhöfer]], [[Ursula Hans]], [[Pascal Hitzler]], [[Markus Krötzsch]], [[Tobias Pietzsch]]: '''[[Book3001|Logik und Logikprogrammierung, Band 2: Aufgaben und Lösungen]]''' Synchron Verlag
: ''(Aufgabensammlung aus den Logikvorlesungen vergangener Jahre)''
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Willkommen/Einleitung formale Sprachen
|Room=HSZ/0002
|Date=2016/10/10
|DS=DS3
|Download=FS2016-01-overlay.pdf, FS2016-01-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Grammatiken und die Chomsky-Hierarchie
|Room=HSZ/0003
|Date=2016/10/13
|DS=DS4
|Download=FS2016-02-overlay.pdf, FS2016-02-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Endliche Automaten
|Room=HSZ/0002
|Date=2016/10/17
|DS=DS3
|Download=FS2016-03-overlay.pdf, FS2016-03-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Nichtdeterministische endliche Automaten
|Room=HSZ/0003
|Date=2016/10/20
|DS=DS4
|Download=FS2016-04-overlay.pdf, FS2016-04-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Abschlusseigenschaften regulärer Sprachen
|Room=HSZ/0002
|Date=2016/10/24
|DS=DS3
|Download=FS2016-05-overlay.pdf, FS2016-05-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Reguläre Ausdrücke (1)
|Room=HSZ/0003
|Date=2016/10/27
|DS=DS4
|Download=FS2016-06-overlay.pdf, FS2016-06-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Reguläre Ausdrücke (2)
|Room=HSZ/0003
|Date=2016/11/03
|DS=DS4
|Download=FS2016-07-overlay.pdf, FS2016-07-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Minimale Automaten
|Room=HSZ/0002
|Date=2016/11/07
|DS=DS3
|Download=FS2016-08-overlay.pdf, FS2016-08-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Minimale Automaten (2)
|Room=HSZ/0003
|Date=2016/11/10
|DS=DS4
|Download=FS2016-09-overlay.pdf, FS2016-09-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Grenzen regulärer Sprachen/Probleme für Automaten
|Room=HSZ/0002
|Date=2016/11/14
|DS=DS3
|Download=FS2016-10-overlay.pdf, FS2016-10-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Von regulären zu kontextfreien Sprachen
|Room=HSZ/0003
|Date=2016/11/17
|DS=DS4
|Download=FS2016-11-overlay.pdf, FS2016-11-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Das Wortproblem kontextfreier Sprachen
|Room=HSZ/0002
|Date=2016/11/21
|DS=DS3
|Download=FS2016-12-overlay.pdf,FS2016-12-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Das Pumping Lemma kontextfreier Sprachen
|Room=HSZ/0003
|Date=2016/11/24
|DS=DS4
|Download=FS2016-13-overlay.pdf, FS2016-13-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Abschlusseigenschaften kontextfreier Sprachen
|Room=HSZ/0002
|Date=2016/11/28
|DS=DS3
|Download=FS2016-14-overlay.pdf, FS2016-14-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Kellerautomaten
|Room=HSZ/0003
|Date=2016/12/01
|DS=DS4
|Download=FS2016-15-overlay.pdf, FS2016-15-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Kellerautomaten und Typ-2-Grammatiken
|Room=HSZ/0002
|Date=2016/12/05
|DS=DS3
|Download=FS2016-16-overlay.pdf, FS2016-16-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Repetitorium 1
|Room=HSZ/0003
|Date=2016/12/08
|DS=DS4
|Download=FS2016-repititorium-1.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Deterministische Typ-2-Sprachen / Entscheidungsprobleme
|Room=HSZ/0002
|Date=2016/12/12
|DS=DS3
|Download=FS2016-17-overlay.pdf, FS2016-17-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Turingmaschinen
|Room=HSZ/0003
|Date=2016/12/15
|DS=DS4
|Download=FS2016-18-overlay.pdf, FS2016-18-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Nichtdeterminismus und Unentscheidbarkeit
|Room=HSZ/0002
|Date=2016/12/19
|DS=DS3
|Download=FS2016-19-overlay.pdf, FS2016-19-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Typ-0- und Typ-1-Sprachen
|Room=HSZ/0003
|Date=2017/01/05
|DS=DS4
|Download=FS2016-20-overlay.pdf, FS2016-20-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Aussagenlogik
|Room=HSZ/0002
|Date=2017/01/09
|DS=DS3
|Download=FS2016-21-overlay.pdf, FS2016-21-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Äquivalenz und Normalformen
|Room=HSZ/0003
|Date=2017/01/12
|DS=DS4
|Download=FS2016-22-overlay.pdf, FS2016-22-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Logisches Schließen
|Room=HSZ/0002
|Date=2017/01/16
|DS=DS3
|Download=FS2016-23-overlay.pdf, FS2016-23-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Horn-Logik / Komplexität
|Room=HSZ/0003
|Date=2017/01/19
|DS=DS4
|Download=FS2016-24-overlay.pdf, FS2016-24-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NP-Vollständigkeit
|Room=HSZ/0002
|Date=2017/01/23
|DS=DS3
|Download=FS2016-25-overlay.pdf, FS2016-25-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Besprechung Musterklausur
|Room=HSZ/0003
|Date=2017/01/26
|DS=DS4
|Download=FS2016-musterklausur.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Repetitorium 2
|Room=HSZ/0002
|Date=2017/01/30
|DS=DS3
|Download=FS2016-repetitorium-2.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Zusammenfassung und Ausblick
|Room=HSZ/0003
|Date=2017/02/02
|DS=DS4
|Download=FS2016-26-overlay.pdf, FS2016-26-print.pdf,
}}

Theoretische Informatik und Logik (SS2017)

2017-07-12T13:46:31Z

Daniel Borchmann: Musterlösung für Aufgabe 10.4

{{Vorlesung
|Title=Theoretische Informatik und Logik
|Research group=Automatentheorie; Wissensbasierte Systeme
|Lecturers=Markus Krötzsch;
|Tutors=Daniel Borchmann; Francesco Kriegel; Florian Starke
|Term=SS
|Year=2017
|Module=INF-B-290, INF-D-330
|SWSLecture=4
|SWSExercise=2
|SWSPractical=0
|Exam type=Klausur
|Description=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 (WS2016)|Formale Systeme]] können hilfreich sein.

==Klausur==

Die Klausur findet am 24.07.2017 von 14:50 bis 16:20 (90 Minuten) im HSZ/AUDI/H statt. Bitte seien Sie mindestens 10 Minuten vor offiziellem Beginn der Klausur im Hörsaal. Stellen Sie bitte auch sicher, dass Sie zur Klausur eingeschreiben sind; die Einschreibung erfolgt über [https://jexam.inf.tu-dresden.de/ JExam].

==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 [https://jexam.inf.tu-dresden.de/ 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.

* [[Medium:TheoLog17-uebung-01.pdf|1. Übungsblatt]]
* [[Medium:TheoLog17-uebung-02.pdf|2. Übungsblatt]]
* [[Medium:TheoLog17-uebung-03.pdf|3. Übungsblatt]]
* [[Medium:TheoLog17-uebung-04.pdf|4. Übungsblatt]] ([[Medium:TheoLog17-uebung-04-pcp-in-haskell.pdf|Haskell-Programm (als pdf)]] zur „Lösung" des PCP)
* [[Medium:TheoLog17-uebung-05.pdf|5. Übungsblatt]]
* [[Medium:TheoLog17-repetitorium-1.pdf|1. Repetitorium]]
* [[Medium:TheoLog17-uebung-06.pdf|6. Übungsblatt]], [[Medium:TheoLog17-uebung-06-03-musterloesung.pdf|Musterlösung für Aufgabe 3]]
* [[Medium:TheoLog17-uebung-07.pdf|7. Übungsblatt]], [[Medium:TheoLog17-uebung-07-04-musterloesung.pdf|Musterlösung für Aufgabe 4]]
* [[Medium:TheoLog17-uebung-08.pdf|8. Übungsblatt]]
* [[Medium:TheoLog17-repetitorium-2.pdf|2. Repetitorium]]
* [[Medium:TheoLog17-uebung-09.pdf|9. Übungsblatt]]
* [[Medium:TheoLog17-uebung-10.pdf|10. Übungsblatt]], [[Medium:TheoLog17-uebung-10-04-musterloesung.pdf|Musterlösung für Aufgabe 4]]
* [[Medium:TheoLog17-repetitorium-3.pdf|3. Repetitorium]]
* [[Medium:TheoLog17-uebung-11.pdf|11. Übungsblatt]]

Zur Vorbereitung auf die Prüfung wird auch eine [[Medium:TheoLog17-musterklausur.pdf|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 [https://creativecommons.org/licenses/by/3.0/de/ 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
|Literature=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)''
* [[Steffen Hölldobler]]: '''[[Book3008|Logik und Logikprogrammierung]].''' Synchron Verlag.
: ''(Schwerpunkt auf Logikprogrammierung und Prädikatenlogik)''
* [[Steffen Hölldobler]], [[Sebastian Bader]], [[Bertram Fronhöfer]], [[Ursula Hans]], [[Pascal Hitzler]], [[Markus Krötzsch]], [[Tobias Pietzsch]]: '''[[Book3001|Logik und Logikprogrammierung, Band 2: Aufgaben und Lösungen]]''' Synchron Verlag
: ''(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)''
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Einleitung, Übersicht, Turingmaschinen
|Room=HSZ/0004
|Date=2017/04/05
|DS=DS4
|Download=TheoLog2017-Vorlesung-01-overlay.pdf, TheoLog2017-Vorlesung-01-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Berechenbarkeit und Unentscheidbarkeit
|Room=HSZ/0004
|Date=2017/04/07
|DS=DS3
|Download=TheoLog2017-Vorlesung-02-overlay.pdf, TheoLog2017-Vorlesung-02-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=WHILE und LOOP
|Room=HSZ/0004
|Date=2017/04/12
|DS=DS4
|Download=TheoLog2017-Vorlesung-03-overlay.pdf, TheoLog2017-Vorlesung-03-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Das Halteproblem und Reduktionen
|Room=HSZ/0004
|Date=2017/04/19
|DS=DS4
|Download=TheoLog2017-Vorlesung-04-overlay.pdf, TheoLog2017-Vorlesung-04-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Der Satz von Rice und das Postsche Korrespondenzproblem
|Room=HSZ/0004
|Date=2017/04/21
|DS=DS3
|Download=TheoLog2017-Vorlesung-05-overlay.pdf, TheoLog2017-Vorlesung-05-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Unentscheidbare Probleme formaler Sprachen
|Room=HSZ/0004
|Date=2017/04/26
|DS=DS4
|Download=TheoLog2017-Vorlesung-06-overlay.pdf, TheoLog2017-Vorlesung-06-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Einführung in die Komplexitätstheorie
|Room=HSZ/0004
|Date=2017/04/28
|DS=DS3
|Download=TheoLog2017-Vorlesung-07-overlay.pdf, TheoLog2017-Vorlesung-07-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Komplexitätsklassen / Effizienz / Reduktionen
|Room=HSZ/0004
|Date=2017/05/03
|DS=DS4
|Download=TheoLog2017-Vorlesung-08-overlay.pdf, TheoLog2017-Vorlesung-08-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Repetitorium 1
|Room=HSZ/0004
|Date=2017/05/05
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NP und NP-Vollständigkeit
|Room=HSZ/0004
|Date=2017/05/10
|DS=DS4
|Download=TheoLog2017-Vorlesung-09-overlay.pdf, TheoLog2017-Vorlesung-09-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NP (Teil 2)
|Room=HSZ/0004
|Date=2017/05/12
|DS=DS3
|Download=TheoLog2017-Vorlesung-10-overlay.pdf, TheoLog2017-Vorlesung-10-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NL und PSpace
|Room=HSZ/0004
|Date=2017/05/19
|DS=DS3
|Download=TheoLog2017-Vorlesung-11-overlay.pdf, TheoLog2017-Vorlesung-11-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=PSpace-Vollständigkeit
|Room=HSZ/0004
|Date=2017/05/24
|DS=DS4
|Download=TheoLog2017-Vorlesung-12-overlay.pdf, TheoLog2017-Vorlesung-12-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Prädikatenlogik: Syntax und Semantik
|Room=HSZ/0004
|Date=2017/05/26
|DS=DS3
|Download=TheoLog2017-Vorlesung-13-overlay.pdf,TheoLog2017-Vorlesung-13-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Modelltheorie und logisches Schließen
|Room=HSZ/0004
|Date=2017/05/31
|DS=DS4
|Download=TheoLog2017-Vorlesung-14-overlay.pdf, TheoLog2017-Vorlesung-14-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Repetitorium 2
|Room=HSZ/0004
|Date=2017/06/02
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Logisches Schließen
|Room=HSZ/0004
|Date=2017/06/14
|DS=DS4
|Download=TheoLog2017-Vorlesung-15-overlay.pdf, TheoLog2017-Vorlesung-15-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Logisches Schließen (2)
|Room=HSZ/0004
|Date=2017/06/16
|DS=DS3
|Download=TheoLog2017-Vorlesung-16-overlay.pdf, TheoLog2017-Vorlesung-16-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Funktionen und Normalformen
|Room=HSZ/0004
|Date=2017/06/21
|DS=DS4
|Download=TheoLog2017-Vorlesung-17-overlay.pdf, TheoLog2017-Vorlesung-17-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Unifikation
|Room=HSZ/0004
|Date=2017/06/23
|DS=DS3
|Download=TheoLog2017-Vorlesung-18-overlay.pdf, TheoLog2017-Vorlesung-18-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Resolution
|Room=HSZ/0004
|Date=2017/06/28
|DS=DS4
|Download=TheoLog2017-Vorlesung-19-overlay.pdf, TheoLog2017-Vorlesung-19-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Resolution / Endliche Modelle
|Room=HSZ/0004
|Date=2017/06/30
|DS=DS3
|Download=TheoLog2017-Vorlesung-20-overlay.pdf, TheoLog2017-Vorlesung-20-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Gödels Unvollständigkeitssätze
|Room=HSZ/0004
|Date=2017/07/05
|DS=DS4
|Download=TheoLog2017-Vorlesung-21-overlay.pdf, TheoLog2017-Vorlesung-21-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Repetitorium 3
|Room=HSZ/0004
|Date=2017/07/07
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Besprechung Probeklausur
|Room=HSZ/0004
|Date=2017/07/12
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Zusammenfassung und Ausblick
|Room=HSZ/0004
|Date=2017/07/14
|DS=DS3
}}

Datei:TheoLog17-uebung-10-04-musterloesung.pdf

2017-07-12T13:41:38Z

Daniel Borchmann:

Datei:TheoLog17-musterklausur.pdf

2017-07-11T06:48:00Z

Daniel Borchmann: Daniel Borchmann lud eine neue Version von „Datei:TheoLog17-musterklausur.pdf“ hoch

Theoretische Informatik und Logik (SS2017)

2017-07-10T12:15:04Z

Daniel Borchmann: Korrekte Bezeichnung des Audimax

{{Vorlesung
|Title=Theoretische Informatik und Logik
|Research group=Automatentheorie; Wissensbasierte Systeme
|Lecturers=Markus Krötzsch;
|Tutors=Daniel Borchmann; Francesco Kriegel; Florian Starke
|Term=SS
|Year=2017
|Module=INF-B-290, INF-D-330
|SWSLecture=4
|SWSExercise=2
|SWSPractical=0
|Exam type=Klausur
|Description=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 (WS2016)|Formale Systeme]] können hilfreich sein.

==Klausur==

Die Klausur findet am 24.07.2017 von 14:50 bis 16:20 (90 Minuten) im HSZ/AUDI/H statt. Bitte seien Sie mindestens 10 Minuten vor offiziellem Beginn der Klausur im Hörsaal. Stellen Sie bitte auch sicher, dass Sie zur Klausur eingeschreiben sind; die Einschreibung erfolgt über [https://jexam.inf.tu-dresden.de/ JExam].

==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 [https://jexam.inf.tu-dresden.de/ 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.

* [[Medium:TheoLog17-uebung-01.pdf|1. Übungsblatt]]
* [[Medium:TheoLog17-uebung-02.pdf|2. Übungsblatt]]
* [[Medium:TheoLog17-uebung-03.pdf|3. Übungsblatt]]
* [[Medium:TheoLog17-uebung-04.pdf|4. Übungsblatt]] ([[Medium:TheoLog17-uebung-04-pcp-in-haskell.pdf|Haskell-Programm (als pdf)]] zur „Lösung" des PCP)
* [[Medium:TheoLog17-uebung-05.pdf|5. Übungsblatt]]
* [[Medium:TheoLog17-repetitorium-1.pdf|1. Repetitorium]]
* [[Medium:TheoLog17-uebung-06.pdf|6. Übungsblatt]], [[Medium:TheoLog17-uebung-06-03-musterloesung.pdf|Musterlösung für Aufgabe 3]]
* [[Medium:TheoLog17-uebung-07.pdf|7. Übungsblatt]], [[Medium:TheoLog17-uebung-07-04-musterloesung.pdf|Musterlösung für Aufgabe 4]]
* [[Medium:TheoLog17-uebung-08.pdf|8. Übungsblatt]]
* [[Medium:TheoLog17-repetitorium-2.pdf|2. Repetitorium]]
* [[Medium:TheoLog17-uebung-09.pdf|9. Übungsblatt]]
* [[Medium:TheoLog17-uebung-10.pdf|10. Übungsblatt]]
* [[Medium:TheoLog17-repetitorium-3.pdf|3. Repetitorium]]
* [[Medium:TheoLog17-uebung-11.pdf|11. Übungsblatt]]

Zur Vorbereitung auf die Prüfung wird auch eine [[Medium:TheoLog17-musterklausur.pdf|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 [https://creativecommons.org/licenses/by/3.0/de/ 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
|Literature=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)''
* [[Steffen Hölldobler]]: '''[[Book3008|Logik und Logikprogrammierung]].''' Synchron Verlag.
: ''(Schwerpunkt auf Logikprogrammierung und Prädikatenlogik)''
* [[Steffen Hölldobler]], [[Sebastian Bader]], [[Bertram Fronhöfer]], [[Ursula Hans]], [[Pascal Hitzler]], [[Markus Krötzsch]], [[Tobias Pietzsch]]: '''[[Book3001|Logik und Logikprogrammierung, Band 2: Aufgaben und Lösungen]]''' Synchron Verlag
: ''(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)''
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Einleitung, Übersicht, Turingmaschinen
|Room=HSZ/0004
|Date=2017/04/05
|DS=DS4
|Download=TheoLog2017-Vorlesung-01-overlay.pdf, TheoLog2017-Vorlesung-01-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Berechenbarkeit und Unentscheidbarkeit
|Room=HSZ/0004
|Date=2017/04/07
|DS=DS3
|Download=TheoLog2017-Vorlesung-02-overlay.pdf, TheoLog2017-Vorlesung-02-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=WHILE und LOOP
|Room=HSZ/0004
|Date=2017/04/12
|DS=DS4
|Download=TheoLog2017-Vorlesung-03-overlay.pdf, TheoLog2017-Vorlesung-03-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Das Halteproblem und Reduktionen
|Room=HSZ/0004
|Date=2017/04/19
|DS=DS4
|Download=TheoLog2017-Vorlesung-04-overlay.pdf, TheoLog2017-Vorlesung-04-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Der Satz von Rice und das Postsche Korrespondenzproblem
|Room=HSZ/0004
|Date=2017/04/21
|DS=DS3
|Download=TheoLog2017-Vorlesung-05-overlay.pdf, TheoLog2017-Vorlesung-05-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Unentscheidbare Probleme formaler Sprachen
|Room=HSZ/0004
|Date=2017/04/26
|DS=DS4
|Download=TheoLog2017-Vorlesung-06-overlay.pdf, TheoLog2017-Vorlesung-06-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Einführung in die Komplexitätstheorie
|Room=HSZ/0004
|Date=2017/04/28
|DS=DS3
|Download=TheoLog2017-Vorlesung-07-overlay.pdf, TheoLog2017-Vorlesung-07-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Komplexitätsklassen / Effizienz / Reduktionen
|Room=HSZ/0004
|Date=2017/05/03
|DS=DS4
|Download=TheoLog2017-Vorlesung-08-overlay.pdf, TheoLog2017-Vorlesung-08-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Repetitorium 1
|Room=HSZ/0004
|Date=2017/05/05
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NP und NP-Vollständigkeit
|Room=HSZ/0004
|Date=2017/05/10
|DS=DS4
|Download=TheoLog2017-Vorlesung-09-overlay.pdf, TheoLog2017-Vorlesung-09-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NP (Teil 2)
|Room=HSZ/0004
|Date=2017/05/12
|DS=DS3
|Download=TheoLog2017-Vorlesung-10-overlay.pdf, TheoLog2017-Vorlesung-10-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NL und PSpace
|Room=HSZ/0004
|Date=2017/05/19
|DS=DS3
|Download=TheoLog2017-Vorlesung-11-overlay.pdf, TheoLog2017-Vorlesung-11-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=PSpace-Vollständigkeit
|Room=HSZ/0004
|Date=2017/05/24
|DS=DS4
|Download=TheoLog2017-Vorlesung-12-overlay.pdf, TheoLog2017-Vorlesung-12-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Prädikatenlogik: Syntax und Semantik
|Room=HSZ/0004
|Date=2017/05/26
|DS=DS3
|Download=TheoLog2017-Vorlesung-13-overlay.pdf,TheoLog2017-Vorlesung-13-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Modelltheorie und logisches Schließen
|Room=HSZ/0004
|Date=2017/05/31
|DS=DS4
|Download=TheoLog2017-Vorlesung-14-overlay.pdf, TheoLog2017-Vorlesung-14-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Repetitorium 2
|Room=HSZ/0004
|Date=2017/06/02
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Logisches Schließen
|Room=HSZ/0004
|Date=2017/06/14
|DS=DS4
|Download=TheoLog2017-Vorlesung-15-overlay.pdf, TheoLog2017-Vorlesung-15-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Logisches Schließen (2)
|Room=HSZ/0004
|Date=2017/06/16
|DS=DS3
|Download=TheoLog2017-Vorlesung-16-overlay.pdf, TheoLog2017-Vorlesung-16-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Funktionen und Normalformen
|Room=HSZ/0004
|Date=2017/06/21
|DS=DS4
|Download=TheoLog2017-Vorlesung-17-overlay.pdf, TheoLog2017-Vorlesung-17-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Unifikation
|Room=HSZ/0004
|Date=2017/06/23
|DS=DS3
|Download=TheoLog2017-Vorlesung-18-overlay.pdf, TheoLog2017-Vorlesung-18-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Resolution
|Room=HSZ/0004
|Date=2017/06/28
|DS=DS4
|Download=TheoLog2017-Vorlesung-19-overlay.pdf, TheoLog2017-Vorlesung-19-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Resolution / Endliche Modelle
|Room=HSZ/0004
|Date=2017/06/30
|DS=DS3
|Download=TheoLog2017-Vorlesung-20-overlay.pdf, TheoLog2017-Vorlesung-20-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Gödels Unvollständigkeitssätze
|Room=HSZ/0004
|Date=2017/07/05
|DS=DS4
|Download=TheoLog2017-Vorlesung-21-overlay.pdf, TheoLog2017-Vorlesung-21-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Repetitorium 3
|Room=HSZ/0004
|Date=2017/07/07
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Besprechung Probeklausur
|Room=HSZ/0004
|Date=2017/07/12
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Zusammenfassung und Ausblick
|Room=HSZ/0004
|Date=2017/07/14
|DS=DS3
}}

Theoretische Informatik und Logik (SS2017)

2017-07-10T12:14:06Z

Daniel Borchmann: Hinweis zur Klausur

{{Vorlesung
|Title=Theoretische Informatik und Logik
|Research group=Automatentheorie; Wissensbasierte Systeme
|Lecturers=Markus Krötzsch;
|Tutors=Daniel Borchmann; Francesco Kriegel; Florian Starke
|Term=SS
|Year=2017
|Module=INF-B-290, INF-D-330
|SWSLecture=4
|SWSExercise=2
|SWSPractical=0
|Exam type=Klausur
|Description=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 (WS2016)|Formale Systeme]] können hilfreich sein.

==Klausur==

Die Klausur findet am 24.07.2017 von 14:50 bis 16:20 (90 Minuten) im HSZ/AUDI statt. Bitte seien Sie mindestens 10 Minuten vor offiziellem Beginn der Klausur im Hörsaal. Stellen Sie bitte auch sicher, dass Sie zur Klausur eingeschreiben sind; die Einschreibung erfolgt über [https://jexam.inf.tu-dresden.de/ JExam].

==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 [https://jexam.inf.tu-dresden.de/ 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.

* [[Medium:TheoLog17-uebung-01.pdf|1. Übungsblatt]]
* [[Medium:TheoLog17-uebung-02.pdf|2. Übungsblatt]]
* [[Medium:TheoLog17-uebung-03.pdf|3. Übungsblatt]]
* [[Medium:TheoLog17-uebung-04.pdf|4. Übungsblatt]] ([[Medium:TheoLog17-uebung-04-pcp-in-haskell.pdf|Haskell-Programm (als pdf)]] zur „Lösung" des PCP)
* [[Medium:TheoLog17-uebung-05.pdf|5. Übungsblatt]]
* [[Medium:TheoLog17-repetitorium-1.pdf|1. Repetitorium]]
* [[Medium:TheoLog17-uebung-06.pdf|6. Übungsblatt]], [[Medium:TheoLog17-uebung-06-03-musterloesung.pdf|Musterlösung für Aufgabe 3]]
* [[Medium:TheoLog17-uebung-07.pdf|7. Übungsblatt]], [[Medium:TheoLog17-uebung-07-04-musterloesung.pdf|Musterlösung für Aufgabe 4]]
* [[Medium:TheoLog17-uebung-08.pdf|8. Übungsblatt]]
* [[Medium:TheoLog17-repetitorium-2.pdf|2. Repetitorium]]
* [[Medium:TheoLog17-uebung-09.pdf|9. Übungsblatt]]
* [[Medium:TheoLog17-uebung-10.pdf|10. Übungsblatt]]
* [[Medium:TheoLog17-repetitorium-3.pdf|3. Repetitorium]]
* [[Medium:TheoLog17-uebung-11.pdf|11. Übungsblatt]]

Zur Vorbereitung auf die Prüfung wird auch eine [[Medium:TheoLog17-musterklausur.pdf|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 [https://creativecommons.org/licenses/by/3.0/de/ 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
|Literature= 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)''
* [[Steffen Hölldobler]]: '''[[Book3008|Logik und Logikprogrammierung]].''' Synchron Verlag.
: ''(Schwerpunkt auf Logikprogrammierung und Prädikatenlogik)''
* [[Steffen Hölldobler]], [[Sebastian Bader]], [[Bertram Fronhöfer]], [[Ursula Hans]], [[Pascal Hitzler]], [[Markus Krötzsch]], [[Tobias Pietzsch]]: '''[[Book3001|Logik und Logikprogrammierung, Band 2: Aufgaben und Lösungen]]''' Synchron Verlag
: ''(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)''
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Einleitung, Übersicht, Turingmaschinen
|Room=HSZ/0004
|Date=2017/04/05
|DS=DS4
|Download=TheoLog2017-Vorlesung-01-overlay.pdf, TheoLog2017-Vorlesung-01-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Berechenbarkeit und Unentscheidbarkeit
|Room=HSZ/0004
|Date=2017/04/07
|DS=DS3
|Download=TheoLog2017-Vorlesung-02-overlay.pdf, TheoLog2017-Vorlesung-02-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=WHILE und LOOP
|Room=HSZ/0004
|Date=2017/04/12
|DS=DS4
|Download=TheoLog2017-Vorlesung-03-overlay.pdf, TheoLog2017-Vorlesung-03-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Das Halteproblem und Reduktionen
|Room=HSZ/0004
|Date=2017/04/19
|DS=DS4
|Download=TheoLog2017-Vorlesung-04-overlay.pdf, TheoLog2017-Vorlesung-04-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Der Satz von Rice und das Postsche Korrespondenzproblem
|Room=HSZ/0004
|Date=2017/04/21
|DS=DS3
|Download=TheoLog2017-Vorlesung-05-overlay.pdf, TheoLog2017-Vorlesung-05-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Unentscheidbare Probleme formaler Sprachen
|Room=HSZ/0004
|Date=2017/04/26
|DS=DS4
|Download=TheoLog2017-Vorlesung-06-overlay.pdf, TheoLog2017-Vorlesung-06-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Einführung in die Komplexitätstheorie
|Room=HSZ/0004
|Date=2017/04/28
|DS=DS3
|Download=TheoLog2017-Vorlesung-07-overlay.pdf, TheoLog2017-Vorlesung-07-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Komplexitätsklassen / Effizienz / Reduktionen
|Room=HSZ/0004
|Date=2017/05/03
|DS=DS4
|Download=TheoLog2017-Vorlesung-08-overlay.pdf, TheoLog2017-Vorlesung-08-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Repetitorium 1
|Room=HSZ/0004
|Date=2017/05/05
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NP und NP-Vollständigkeit
|Room=HSZ/0004
|Date=2017/05/10
|DS=DS4
|Download=TheoLog2017-Vorlesung-09-overlay.pdf, TheoLog2017-Vorlesung-09-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NP (Teil 2)
|Room=HSZ/0004
|Date=2017/05/12
|DS=DS3
|Download=TheoLog2017-Vorlesung-10-overlay.pdf, TheoLog2017-Vorlesung-10-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NL und PSpace
|Room=HSZ/0004
|Date=2017/05/19
|DS=DS3
|Download=TheoLog2017-Vorlesung-11-overlay.pdf, TheoLog2017-Vorlesung-11-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=PSpace-Vollständigkeit
|Room=HSZ/0004
|Date=2017/05/24
|DS=DS4
|Download=TheoLog2017-Vorlesung-12-overlay.pdf, TheoLog2017-Vorlesung-12-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Prädikatenlogik: Syntax und Semantik
|Room=HSZ/0004
|Date=2017/05/26
|DS=DS3
|Download=TheoLog2017-Vorlesung-13-overlay.pdf,TheoLog2017-Vorlesung-13-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Modelltheorie und logisches Schließen
|Room=HSZ/0004
|Date=2017/05/31
|DS=DS4
|Download=TheoLog2017-Vorlesung-14-overlay.pdf, TheoLog2017-Vorlesung-14-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Repetitorium 2
|Room=HSZ/0004
|Date=2017/06/02
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Logisches Schließen
|Room=HSZ/0004
|Date=2017/06/14
|DS=DS4
|Download=TheoLog2017-Vorlesung-15-overlay.pdf, TheoLog2017-Vorlesung-15-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Logisches Schließen (2)
|Room=HSZ/0004
|Date=2017/06/16
|DS=DS3
|Download=TheoLog2017-Vorlesung-16-overlay.pdf, TheoLog2017-Vorlesung-16-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Funktionen und Normalformen
|Room=HSZ/0004
|Date=2017/06/21
|DS=DS4
|Download=TheoLog2017-Vorlesung-17-overlay.pdf, TheoLog2017-Vorlesung-17-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Unifikation
|Room=HSZ/0004
|Date=2017/06/23
|DS=DS3
|Download=TheoLog2017-Vorlesung-18-overlay.pdf, TheoLog2017-Vorlesung-18-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Resolution
|Room=HSZ/0004
|Date=2017/06/28
|DS=DS4
|Download=TheoLog2017-Vorlesung-19-overlay.pdf, TheoLog2017-Vorlesung-19-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Resolution / Endliche Modelle
|Room=HSZ/0004
|Date=2017/06/30
|DS=DS3
|Download=TheoLog2017-Vorlesung-20-overlay.pdf, TheoLog2017-Vorlesung-20-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Gödels Unvollständigkeitssätze
|Room=HSZ/0004
|Date=2017/07/05
|DS=DS4
|Download=TheoLog2017-Vorlesung-21-overlay.pdf, TheoLog2017-Vorlesung-21-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Repetitorium 3
|Room=HSZ/0004
|Date=2017/07/07
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Besprechung Probeklausur
|Room=HSZ/0004
|Date=2017/07/12
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Zusammenfassung und Ausblick
|Room=HSZ/0004
|Date=2017/07/14
|DS=DS3
}}

Datei:TheoLog17-uebung-09.pdf

2017-07-04T06:17:42Z

Daniel Borchmann: Daniel Borchmann lud eine neue Version von „Datei:TheoLog17-uebung-09.pdf“ hoch

Datei:TheoLog17-musterklausur.pdf

2017-07-03T11:48:33Z

Daniel Borchmann: Daniel Borchmann lud eine neue Version von „Datei:TheoLog17-musterklausur.pdf“ hoch

Datei:TheoLog17-uebung-09.pdf

2017-06-27T11:05:56Z

Daniel Borchmann: Daniel Borchmann lud eine neue Version von „Datei:TheoLog17-uebung-09.pdf“ hoch

Datei:TheoLog17-uebung-09.pdf

2017-06-27T10:19:04Z

Daniel Borchmann: Daniel Borchmann lud eine neue Version von „Datei:TheoLog17-uebung-09.pdf“ hoch

Datei:TheoLog17-uebung-09.pdf

2017-06-27T09:58:52Z

Daniel Borchmann: Daniel Borchmann lud eine neue Version von „Datei:TheoLog17-uebung-09.pdf“ hoch

Datei:TheoLog17-uebung-11.pdf

2017-06-27T06:41:10Z

Daniel Borchmann: Daniel Borchmann lud eine neue Version von „Datei:TheoLog17-uebung-11.pdf“ hoch

Theoretische Informatik und Logik (SS2017)

2017-06-26T12:28:34Z

Daniel Borchmann: Formulierung für Hinweis auf Musterklausur verbessert

{{Vorlesung
|Title=Theoretische Informatik und Logik
|Research group=Automatentheorie; Wissensbasierte Systeme
|Lecturers=Markus Krötzsch;
|Tutors=Daniel Borchmann; Francesco Kriegel; Florian Starke
|Term=SS
|Year=2017
|Module=INF-B-290, INF-D-330
|SWSLecture=4
|SWSExercise=2
|SWSPractical=0
|Exam type=Klausur
|Description=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 (WS2016)|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 [https://jexam.inf.tu-dresden.de/ 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.

* [[Medium:TheoLog17-uebung-01.pdf|1. Übungsblatt]]
* [[Medium:TheoLog17-uebung-02.pdf|2. Übungsblatt]]
* [[Medium:TheoLog17-uebung-03.pdf|3. Übungsblatt]]
* [[Medium:TheoLog17-uebung-04.pdf|4. Übungsblatt]] ([[Medium:TheoLog17-uebung-04-pcp-in-haskell.pdf|Haskell-Programm (als pdf)]] zur „Lösung" des PCP)
* [[Medium:TheoLog17-uebung-05.pdf|5. Übungsblatt]]
* [[Medium:TheoLog17-repetitorium-1.pdf|1. Repetitorium]]
* [[Medium:TheoLog17-uebung-06.pdf|6. Übungsblatt]], [[Medium:TheoLog17-uebung-06-03-musterloesung.pdf|Musterlösung für Aufgabe 3]]
* [[Medium:TheoLog17-uebung-07.pdf|7. Übungsblatt]], [[Medium:TheoLog17-uebung-07-04-musterloesung.pdf|Musterlösung für Aufgabe 4]]
* [[Medium:TheoLog17-uebung-08.pdf|8. Übungsblatt]]
* [[Medium:TheoLog17-repetitorium-2.pdf|2. Repetitorium]]
* [[Medium:TheoLog17-uebung-09.pdf|9. Übungsblatt]]
* [[Medium:TheoLog17-uebung-10.pdf|10. Übungsblatt]]
* [[Medium:TheoLog17-uebung-11.pdf|11. Übungsblatt]]

Zur Vorbereitung auf die Prüfung wird auch eine [[Medium:TheoLog17-musterklausur.pdf|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 [https://creativecommons.org/licenses/by/3.0/de/ 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
|Literature=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)''
* [[Steffen Hölldobler]]: '''[[Book3008|Logik und Logikprogrammierung]].''' Synchron Verlag.
: ''(Schwerpunkt auf Logikprogrammierung und Prädikatenlogik)''
* [[Steffen Hölldobler]], [[Sebastian Bader]], [[Bertram Fronhöfer]], [[Ursula Hans]], [[Pascal Hitzler]], [[Markus Krötzsch]], [[Tobias Pietzsch]]: '''[[Book3001|Logik und Logikprogrammierung, Band 2: Aufgaben und Lösungen]]''' Synchron Verlag
: ''(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)''
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Einleitung, Übersicht, Turingmaschinen
|Room=HSZ/0004
|Date=2017/04/05
|DS=DS4
|Download=TheoLog2017-Vorlesung-01-overlay.pdf, TheoLog2017-Vorlesung-01-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Berechenbarkeit und Unentscheidbarkeit
|Room=HSZ/0004
|Date=2017/04/07
|DS=DS3
|Download=TheoLog2017-Vorlesung-02-overlay.pdf, TheoLog2017-Vorlesung-02-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=WHILE und LOOP
|Room=HSZ/0004
|Date=2017/04/12
|DS=DS4
|Download=TheoLog2017-Vorlesung-03-overlay.pdf, TheoLog2017-Vorlesung-03-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Das Halteproblem und Reduktionen
|Room=HSZ/0004
|Date=2017/04/19
|DS=DS4
|Download=TheoLog2017-Vorlesung-04-overlay.pdf, TheoLog2017-Vorlesung-04-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Der Satz von Rice und das Postsche Korrespondenzproblem
|Room=HSZ/0004
|Date=2017/04/21
|DS=DS3
|Download=TheoLog2017-Vorlesung-05-overlay.pdf, TheoLog2017-Vorlesung-05-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Unentscheidbare Probleme formaler Sprachen
|Room=HSZ/0004
|Date=2017/04/26
|DS=DS4
|Download=TheoLog2017-Vorlesung-06-overlay.pdf, TheoLog2017-Vorlesung-06-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Einführung in die Komplexitätstheorie
|Room=HSZ/0004
|Date=2017/04/28
|DS=DS3
|Download=TheoLog2017-Vorlesung-07-overlay.pdf, TheoLog2017-Vorlesung-07-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Komplexitätsklassen / Effizienz / Reduktionen
|Room=HSZ/0004
|Date=2017/05/03
|DS=DS4
|Download=TheoLog2017-Vorlesung-08-overlay.pdf, TheoLog2017-Vorlesung-08-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Repetitorium 1
|Room=HSZ/0004
|Date=2017/05/05
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NP und NP-Vollständigkeit
|Room=HSZ/0004
|Date=2017/05/10
|DS=DS4
|Download=TheoLog2017-Vorlesung-09-overlay.pdf, TheoLog2017-Vorlesung-09-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NP (Teil 2)
|Room=HSZ/0004
|Date=2017/05/12
|DS=DS3
|Download=TheoLog2017-Vorlesung-10-overlay.pdf, TheoLog2017-Vorlesung-10-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NL und PSpace
|Room=HSZ/0004
|Date=2017/05/19
|DS=DS3
|Download=TheoLog2017-Vorlesung-11-overlay.pdf, TheoLog2017-Vorlesung-11-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=PSpace-Vollständigkeit
|Room=HSZ/0004
|Date=2017/05/24
|DS=DS4
|Download=TheoLog2017-Vorlesung-12-overlay.pdf, TheoLog2017-Vorlesung-12-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Prädikatenlogik: Syntax und Semantik
|Room=HSZ/0004
|Date=2017/05/26
|DS=DS3
|Download=TheoLog2017-Vorlesung-13-overlay.pdf,TheoLog2017-Vorlesung-13-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Modelltheorie und logisches Schließen
|Room=HSZ/0004
|Date=2017/05/31
|DS=DS4
|Download=TheoLog2017-Vorlesung-14-overlay.pdf, TheoLog2017-Vorlesung-14-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Repetitorium 2
|Room=HSZ/0004
|Date=2017/06/02
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Logisches Schließen
|Room=HSZ/0004
|Date=2017/06/14
|DS=DS4
|Download=TheoLog2017-Vorlesung-15-overlay.pdf, TheoLog2017-Vorlesung-15-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Logisches Schließen (2)
|Room=HSZ/0004
|Date=2017/06/16
|DS=DS3
|Download=TheoLog2017-Vorlesung-16-overlay.pdf, TheoLog2017-Vorlesung-16-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Funktionen und Normalformen
|Room=HSZ/0004
|Date=2017/06/21
|DS=DS4
|Download=TheoLog2017-Vorlesung-17-overlay.pdf, TheoLog2017-Vorlesung-17-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Unifikation
|Room=HSZ/0004
|Date=2017/06/23
|DS=DS3
|Download=TheoLog2017-Vorlesung-18-overlay.pdf, TheoLog2017-Vorlesung-18-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Resolution
|Room=HSZ/0004
|Date=2017/06/28
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Endliche Modelle und das Auswertungsproblem
|Room=HSZ/0004
|Date=2017/06/30
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Gödels Unvollständigkeitssätze
|Room=HSZ/0004
|Date=2017/07/05
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Repetitorium 3
|Room=HSZ/0004
|Date=2017/07/07
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Besprechung Probeklausur
|Room=HSZ/0004
|Date=2017/07/12
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Zusammenfassung und Ausblick
|Room=HSZ/0004
|Date=2017/07/14
|DS=DS3
}}

Theoretische Informatik und Logik (SS2017)

2017-06-26T12:26:54Z

Daniel Borchmann: 11. Blatt freigegeben

{{Vorlesung
|Title=Theoretische Informatik und Logik
|Research group=Automatentheorie; Wissensbasierte Systeme
|Lecturers=Markus Krötzsch;
|Tutors=Daniel Borchmann; Francesco Kriegel; Florian Starke
|Term=SS
|Year=2017
|Module=INF-B-290, INF-D-330
|SWSLecture=4
|SWSExercise=2
|SWSPractical=0
|Exam type=Klausur
|Description=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 (WS2016)|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 [https://jexam.inf.tu-dresden.de/ 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.

* [[Medium:TheoLog17-uebung-01.pdf|1. Übungsblatt]]
* [[Medium:TheoLog17-uebung-02.pdf|2. Übungsblatt]]
* [[Medium:TheoLog17-uebung-03.pdf|3. Übungsblatt]]
* [[Medium:TheoLog17-uebung-04.pdf|4. Übungsblatt]] ([[Medium:TheoLog17-uebung-04-pcp-in-haskell.pdf|Haskell-Programm (als pdf)]] zur „Lösung" des PCP)
* [[Medium:TheoLog17-uebung-05.pdf|5. Übungsblatt]]
* [[Medium:TheoLog17-repetitorium-1.pdf|1. Repetitorium]]
* [[Medium:TheoLog17-uebung-06.pdf|6. Übungsblatt]], [[Medium:TheoLog17-uebung-06-03-musterloesung.pdf|Musterlösung für Aufgabe 3]]
* [[Medium:TheoLog17-uebung-07.pdf|7. Übungsblatt]], [[Medium:TheoLog17-uebung-07-04-musterloesung.pdf|Musterlösung für Aufgabe 4]]
* [[Medium:TheoLog17-uebung-08.pdf|8. Übungsblatt]]
* [[Medium:TheoLog17-repetitorium-2.pdf|2. Repetitorium]]
* [[Medium:TheoLog17-uebung-09.pdf|9. Übungsblatt]]
* [[Medium:TheoLog17-uebung-10.pdf|10. Übungsblatt]]
* [[Medium:TheoLog17-uebung-11.pdf|11. Übungsblatt]]

Zur Vorbereitung der Klausur wird auch eine [[Medium:TheoLog17-musterklausur.pdf|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 [https://creativecommons.org/licenses/by/3.0/de/ 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
|Literature=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)''
* [[Steffen Hölldobler]]: '''[[Book3008|Logik und Logikprogrammierung]].''' Synchron Verlag.
: ''(Schwerpunkt auf Logikprogrammierung und Prädikatenlogik)''
* [[Steffen Hölldobler]], [[Sebastian Bader]], [[Bertram Fronhöfer]], [[Ursula Hans]], [[Pascal Hitzler]], [[Markus Krötzsch]], [[Tobias Pietzsch]]: '''[[Book3001|Logik und Logikprogrammierung, Band 2: Aufgaben und Lösungen]]''' Synchron Verlag
: ''(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)''
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Einleitung, Übersicht, Turingmaschinen
|Room=HSZ/0004
|Date=2017/04/05
|DS=DS4
|Download=TheoLog2017-Vorlesung-01-overlay.pdf, TheoLog2017-Vorlesung-01-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Berechenbarkeit und Unentscheidbarkeit
|Room=HSZ/0004
|Date=2017/04/07
|DS=DS3
|Download=TheoLog2017-Vorlesung-02-overlay.pdf, TheoLog2017-Vorlesung-02-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=WHILE und LOOP
|Room=HSZ/0004
|Date=2017/04/12
|DS=DS4
|Download=TheoLog2017-Vorlesung-03-overlay.pdf, TheoLog2017-Vorlesung-03-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Das Halteproblem und Reduktionen
|Room=HSZ/0004
|Date=2017/04/19
|DS=DS4
|Download=TheoLog2017-Vorlesung-04-overlay.pdf, TheoLog2017-Vorlesung-04-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Der Satz von Rice und das Postsche Korrespondenzproblem
|Room=HSZ/0004
|Date=2017/04/21
|DS=DS3
|Download=TheoLog2017-Vorlesung-05-overlay.pdf, TheoLog2017-Vorlesung-05-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Unentscheidbare Probleme formaler Sprachen
|Room=HSZ/0004
|Date=2017/04/26
|DS=DS4
|Download=TheoLog2017-Vorlesung-06-overlay.pdf, TheoLog2017-Vorlesung-06-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Einführung in die Komplexitätstheorie
|Room=HSZ/0004
|Date=2017/04/28
|DS=DS3
|Download=TheoLog2017-Vorlesung-07-overlay.pdf, TheoLog2017-Vorlesung-07-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Komplexitätsklassen / Effizienz / Reduktionen
|Room=HSZ/0004
|Date=2017/05/03
|DS=DS4
|Download=TheoLog2017-Vorlesung-08-overlay.pdf, TheoLog2017-Vorlesung-08-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Repetitorium 1
|Room=HSZ/0004
|Date=2017/05/05
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NP und NP-Vollständigkeit
|Room=HSZ/0004
|Date=2017/05/10
|DS=DS4
|Download=TheoLog2017-Vorlesung-09-overlay.pdf, TheoLog2017-Vorlesung-09-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NP (Teil 2)
|Room=HSZ/0004
|Date=2017/05/12
|DS=DS3
|Download=TheoLog2017-Vorlesung-10-overlay.pdf, TheoLog2017-Vorlesung-10-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NL und PSpace
|Room=HSZ/0004
|Date=2017/05/19
|DS=DS3
|Download=TheoLog2017-Vorlesung-11-overlay.pdf, TheoLog2017-Vorlesung-11-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=PSpace-Vollständigkeit
|Room=HSZ/0004
|Date=2017/05/24
|DS=DS4
|Download=TheoLog2017-Vorlesung-12-overlay.pdf, TheoLog2017-Vorlesung-12-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Prädikatenlogik: Syntax und Semantik
|Room=HSZ/0004
|Date=2017/05/26
|DS=DS3
|Download=TheoLog2017-Vorlesung-13-overlay.pdf,TheoLog2017-Vorlesung-13-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Modelltheorie und logisches Schließen
|Room=HSZ/0004
|Date=2017/05/31
|DS=DS4
|Download=TheoLog2017-Vorlesung-14-overlay.pdf, TheoLog2017-Vorlesung-14-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Repetitorium 2
|Room=HSZ/0004
|Date=2017/06/02
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Logisches Schließen
|Room=HSZ/0004
|Date=2017/06/14
|DS=DS4
|Download=TheoLog2017-Vorlesung-15-overlay.pdf, TheoLog2017-Vorlesung-15-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Logisches Schließen (2)
|Room=HSZ/0004
|Date=2017/06/16
|DS=DS3
|Download=TheoLog2017-Vorlesung-16-overlay.pdf, TheoLog2017-Vorlesung-16-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Funktionen und Normalformen
|Room=HSZ/0004
|Date=2017/06/21
|DS=DS4
|Download=TheoLog2017-Vorlesung-17-overlay.pdf, TheoLog2017-Vorlesung-17-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Unifikation
|Room=HSZ/0004
|Date=2017/06/23
|DS=DS3
|Download=TheoLog2017-Vorlesung-18-overlay.pdf, TheoLog2017-Vorlesung-18-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Resolution
|Room=HSZ/0004
|Date=2017/06/28
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Endliche Modelle und das Auswertungsproblem
|Room=HSZ/0004
|Date=2017/06/30
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Gödels Unvollständigkeitssätze
|Room=HSZ/0004
|Date=2017/07/05
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Repetitorium 3
|Room=HSZ/0004
|Date=2017/07/07
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Besprechung Probeklausur
|Room=HSZ/0004
|Date=2017/07/12
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Zusammenfassung und Ausblick
|Room=HSZ/0004
|Date=2017/07/14
|DS=DS3
}}

Datei:TheoLog17-uebung-11.pdf

2017-06-26T12:25:20Z

Daniel Borchmann:

Datei:TheoLog17-musterklausur.pdf

2017-06-23T21:30:39Z

Daniel Borchmann: Daniel Borchmann lud eine neue Version von „Datei:TheoLog17-musterklausur.pdf“ hoch

Datei:TheoLog17-musterklausur.pdf

2017-06-23T21:27:39Z

Daniel Borchmann: Daniel Borchmann lud eine neue Version von „Datei:TheoLog17-musterklausur.pdf“ hoch

Datei:TheoLog17-musterklausur.pdf

2017-06-23T14:14:55Z

Daniel Borchmann: Daniel Borchmann lud eine neue Version von „Datei:TheoLog17-musterklausur.pdf“ hoch

Datei:TheoLog17-musterklausur.pdf

2017-06-23T14:11:42Z

Daniel Borchmann: Daniel Borchmann lud eine neue Version von „Datei:TheoLog17-musterklausur.pdf“ hoch

Theoretische Informatik und Logik (SS2017)

2017-06-23T13:59:42Z

Daniel Borchmann: Tippfehler in Link zur Musterklausur korrigiert

{{Vorlesung
|Title=Theoretische Informatik und Logik
|Research group=Automatentheorie; Wissensbasierte Systeme
|Lecturers=Markus Krötzsch;
|Tutors=Daniel Borchmann; Francesco Kriegel; Florian Starke
|Term=SS
|Year=2017
|Module=INF-B-290, INF-D-330
|SWSLecture=4
|SWSExercise=2
|SWSPractical=0
|Exam type=Klausur
|Description=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 (WS2016)|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 [https://jexam.inf.tu-dresden.de/ 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.

* [[Medium:TheoLog17-uebung-01.pdf|1. Übungsblatt]]
* [[Medium:TheoLog17-uebung-02.pdf|2. Übungsblatt]]
* [[Medium:TheoLog17-uebung-03.pdf|3. Übungsblatt]]
* [[Medium:TheoLog17-uebung-04.pdf|4. Übungsblatt]] ([[Medium:TheoLog17-uebung-04-pcp-in-haskell.pdf|Haskell-Programm (als pdf)]] zur „Lösung" des PCP)
* [[Medium:TheoLog17-uebung-05.pdf|5. Übungsblatt]]
* [[Medium:TheoLog17-repetitorium-1.pdf|1. Repetitorium]]
* [[Medium:TheoLog17-uebung-06.pdf|6. Übungsblatt]], [[Medium:TheoLog17-uebung-06-03-musterloesung.pdf|Musterlösung für Aufgabe 3]]
* [[Medium:TheoLog17-uebung-07.pdf|7. Übungsblatt]], [[Medium:TheoLog17-uebung-07-04-musterloesung.pdf|Musterlösung für Aufgabe 4]]
* [[Medium:TheoLog17-uebung-08.pdf|8. Übungsblatt]]
* [[Medium:TheoLog17-repetitorium-2.pdf|2. Repetitorium]]
* [[Medium:TheoLog17-uebung-09.pdf|9. Übungsblatt]]
* [[Medium:TheoLog17-uebung-10.pdf|10. Übungsblatt]]

Zur Vorbereitung der Klausur wird auch eine [[Medium:TheoLog17-musterklausur.pdf|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 [https://creativecommons.org/licenses/by/3.0/de/ 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
|Literature=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)''
* [[Steffen Hölldobler]]: '''[[Book3008|Logik und Logikprogrammierung]].''' Synchron Verlag.
: ''(Schwerpunkt auf Logikprogrammierung und Prädikatenlogik)''
* [[Steffen Hölldobler]], [[Sebastian Bader]], [[Bertram Fronhöfer]], [[Ursula Hans]], [[Pascal Hitzler]], [[Markus Krötzsch]], [[Tobias Pietzsch]]: '''[[Book3001|Logik und Logikprogrammierung, Band 2: Aufgaben und Lösungen]]''' Synchron Verlag
: ''(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)''
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Einleitung, Übersicht, Turingmaschinen
|Room=HSZ/0004
|Date=2017/04/05
|DS=DS4
|Download=TheoLog2017-Vorlesung-01-overlay.pdf, TheoLog2017-Vorlesung-01-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Berechenbarkeit und Unentscheidbarkeit
|Room=HSZ/0004
|Date=2017/04/07
|DS=DS3
|Download=TheoLog2017-Vorlesung-02-overlay.pdf, TheoLog2017-Vorlesung-02-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=WHILE und LOOP
|Room=HSZ/0004
|Date=2017/04/12
|DS=DS4
|Download=TheoLog2017-Vorlesung-03-overlay.pdf, TheoLog2017-Vorlesung-03-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Das Halteproblem und Reduktionen
|Room=HSZ/0004
|Date=2017/04/19
|DS=DS4
|Download=TheoLog2017-Vorlesung-04-overlay.pdf, TheoLog2017-Vorlesung-04-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Der Satz von Rice und das Postsche Korrespondenzproblem
|Room=HSZ/0004
|Date=2017/04/21
|DS=DS3
|Download=TheoLog2017-Vorlesung-05-overlay.pdf, TheoLog2017-Vorlesung-05-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Unentscheidbare Probleme formaler Sprachen
|Room=HSZ/0004
|Date=2017/04/26
|DS=DS4
|Download=TheoLog2017-Vorlesung-06-overlay.pdf, TheoLog2017-Vorlesung-06-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Einführung in die Komplexitätstheorie
|Room=HSZ/0004
|Date=2017/04/28
|DS=DS3
|Download=TheoLog2017-Vorlesung-07-overlay.pdf, TheoLog2017-Vorlesung-07-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Komplexitätsklassen / Effizienz / Reduktionen
|Room=HSZ/0004
|Date=2017/05/03
|DS=DS4
|Download=TheoLog2017-Vorlesung-08-overlay.pdf, TheoLog2017-Vorlesung-08-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Repetitorium 1
|Room=HSZ/0004
|Date=2017/05/05
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NP und NP-Vollständigkeit
|Room=HSZ/0004
|Date=2017/05/10
|DS=DS4
|Download=TheoLog2017-Vorlesung-09-overlay.pdf, TheoLog2017-Vorlesung-09-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NP (Teil 2)
|Room=HSZ/0004
|Date=2017/05/12
|DS=DS3
|Download=TheoLog2017-Vorlesung-10-overlay.pdf, TheoLog2017-Vorlesung-10-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NL und PSpace
|Room=HSZ/0004
|Date=2017/05/19
|DS=DS3
|Download=TheoLog2017-Vorlesung-11-overlay.pdf, TheoLog2017-Vorlesung-11-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=PSpace-Vollständigkeit
|Room=HSZ/0004
|Date=2017/05/24
|DS=DS4
|Download=TheoLog2017-Vorlesung-12-overlay.pdf, TheoLog2017-Vorlesung-12-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Prädikatenlogik: Syntax und Semantik
|Room=HSZ/0004
|Date=2017/05/26
|DS=DS3
|Download=TheoLog2017-Vorlesung-13-overlay.pdf,TheoLog2017-Vorlesung-13-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Modelltheorie und logisches Schließen
|Room=HSZ/0004
|Date=2017/05/31
|DS=DS4
|Download=TheoLog2017-Vorlesung-14-overlay.pdf, TheoLog2017-Vorlesung-14-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Repetitorium 2
|Room=HSZ/0004
|Date=2017/06/02
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Logisches Schließen
|Room=HSZ/0004
|Date=2017/06/14
|DS=DS4
|Download=TheoLog2017-Vorlesung-15-overlay.pdf, TheoLog2017-Vorlesung-15-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Logisches Schließen (2)
|Room=HSZ/0004
|Date=2017/06/16
|DS=DS3
|Download=TheoLog2017-Vorlesung-16-overlay.pdf, TheoLog2017-Vorlesung-16-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Funktionen und Normalformen
|Room=HSZ/0004
|Date=2017/06/21
|DS=DS4
|Download=TheoLog2017-Vorlesung-17-overlay.pdf, TheoLog2017-Vorlesung-17-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Resolution
|Room=HSZ/0004
|Date=2017/06/23
|DS=DS3
|Download=TheoLog2017-Vorlesung-18-overlay.pdf, TheoLog2017-Vorlesung-18-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Endliche Modelle und das Auswertungsproblem
|Room=HSZ/0004
|Date=2017/06/28
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Gödels Unvollständigkeitssätze
|Room=HSZ/0004
|Date=2017/06/30
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Logik höherer Ordnung
|Room=HSZ/0004
|Date=2017/07/05
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Repetitorium 3
|Room=HSZ/0004
|Date=2017/07/07
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Besprechung Probeklausur
|Room=HSZ/0004
|Date=2017/07/12
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Zusammenfassung und Ausblick
|Room=HSZ/0004
|Date=2017/07/14
|DS=DS3
}}

Theoretische Informatik und Logik (SS2017)

2017-06-23T13:57:24Z

Daniel Borchmann: Musterklausur freigegeben

{{Vorlesung
|Title=Theoretische Informatik und Logik
|Research group=Automatentheorie; Wissensbasierte Systeme
|Lecturers=Markus Krötzsch;
|Tutors=Daniel Borchmann; Francesco Kriegel; Florian Starke
|Term=SS
|Year=2017
|Module=INF-B-290, INF-D-330
|SWSLecture=4
|SWSExercise=2
|SWSPractical=0
|Exam type=Klausur
|Description=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 (WS2016)|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 [https://jexam.inf.tu-dresden.de/ 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.

* [[Medium:TheoLog17-uebung-01.pdf|1. Übungsblatt]]
* [[Medium:TheoLog17-uebung-02.pdf|2. Übungsblatt]]
* [[Medium:TheoLog17-uebung-03.pdf|3. Übungsblatt]]
* [[Medium:TheoLog17-uebung-04.pdf|4. Übungsblatt]] ([[Medium:TheoLog17-uebung-04-pcp-in-haskell.pdf|Haskell-Programm (als pdf)]] zur „Lösung" des PCP)
* [[Medium:TheoLog17-uebung-05.pdf|5. Übungsblatt]]
* [[Medium:TheoLog17-repetitorium-1.pdf|1. Repetitorium]]
* [[Medium:TheoLog17-uebung-06.pdf|6. Übungsblatt]], [[Medium:TheoLog17-uebung-06-03-musterloesung.pdf|Musterlösung für Aufgabe 3]]
* [[Medium:TheoLog17-uebung-07.pdf|7. Übungsblatt]], [[Medium:TheoLog17-uebung-07-04-musterloesung.pdf|Musterlösung für Aufgabe 4]]
* [[Medium:TheoLog17-uebung-08.pdf|8. Übungsblatt]]
* [[Medium:TheoLog17-repetitorium-2.pdf|2. Repetitorium]]
* [[Medium:TheoLog17-uebung-09.pdf|9. Übungsblatt]]
* [[Medium:TheoLog17-uebung-10.pdf|10. Übungsblatt]]

Zur Vorbereitung der Klausur wird auch eine [[Medium:TheoLog17-musterklausur|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 [https://creativecommons.org/licenses/by/3.0/de/ 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
|Literature=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)''
* [[Steffen Hölldobler]]: '''[[Book3008|Logik und Logikprogrammierung]].''' Synchron Verlag.
: ''(Schwerpunkt auf Logikprogrammierung und Prädikatenlogik)''
* [[Steffen Hölldobler]], [[Sebastian Bader]], [[Bertram Fronhöfer]], [[Ursula Hans]], [[Pascal Hitzler]], [[Markus Krötzsch]], [[Tobias Pietzsch]]: '''[[Book3001|Logik und Logikprogrammierung, Band 2: Aufgaben und Lösungen]]''' Synchron Verlag
: ''(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)''
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Einleitung, Übersicht, Turingmaschinen
|Room=HSZ/0004
|Date=2017/04/05
|DS=DS4
|Download=TheoLog2017-Vorlesung-01-overlay.pdf, TheoLog2017-Vorlesung-01-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Berechenbarkeit und Unentscheidbarkeit
|Room=HSZ/0004
|Date=2017/04/07
|DS=DS3
|Download=TheoLog2017-Vorlesung-02-overlay.pdf, TheoLog2017-Vorlesung-02-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=WHILE und LOOP
|Room=HSZ/0004
|Date=2017/04/12
|DS=DS4
|Download=TheoLog2017-Vorlesung-03-overlay.pdf, TheoLog2017-Vorlesung-03-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Das Halteproblem und Reduktionen
|Room=HSZ/0004
|Date=2017/04/19
|DS=DS4
|Download=TheoLog2017-Vorlesung-04-overlay.pdf, TheoLog2017-Vorlesung-04-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Der Satz von Rice und das Postsche Korrespondenzproblem
|Room=HSZ/0004
|Date=2017/04/21
|DS=DS3
|Download=TheoLog2017-Vorlesung-05-overlay.pdf, TheoLog2017-Vorlesung-05-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Unentscheidbare Probleme formaler Sprachen
|Room=HSZ/0004
|Date=2017/04/26
|DS=DS4
|Download=TheoLog2017-Vorlesung-06-overlay.pdf, TheoLog2017-Vorlesung-06-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Einführung in die Komplexitätstheorie
|Room=HSZ/0004
|Date=2017/04/28
|DS=DS3
|Download=TheoLog2017-Vorlesung-07-overlay.pdf, TheoLog2017-Vorlesung-07-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Komplexitätsklassen / Effizienz / Reduktionen
|Room=HSZ/0004
|Date=2017/05/03
|DS=DS4
|Download=TheoLog2017-Vorlesung-08-overlay.pdf, TheoLog2017-Vorlesung-08-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Repetitorium 1
|Room=HSZ/0004
|Date=2017/05/05
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NP und NP-Vollständigkeit
|Room=HSZ/0004
|Date=2017/05/10
|DS=DS4
|Download=TheoLog2017-Vorlesung-09-overlay.pdf, TheoLog2017-Vorlesung-09-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NP (Teil 2)
|Room=HSZ/0004
|Date=2017/05/12
|DS=DS3
|Download=TheoLog2017-Vorlesung-10-overlay.pdf, TheoLog2017-Vorlesung-10-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NL und PSpace
|Room=HSZ/0004
|Date=2017/05/19
|DS=DS3
|Download=TheoLog2017-Vorlesung-11-overlay.pdf, TheoLog2017-Vorlesung-11-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=PSpace-Vollständigkeit
|Room=HSZ/0004
|Date=2017/05/24
|DS=DS4
|Download=TheoLog2017-Vorlesung-12-overlay.pdf, TheoLog2017-Vorlesung-12-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Prädikatenlogik: Syntax und Semantik
|Room=HSZ/0004
|Date=2017/05/26
|DS=DS3
|Download=TheoLog2017-Vorlesung-13-overlay.pdf,TheoLog2017-Vorlesung-13-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Modelltheorie und logisches Schließen
|Room=HSZ/0004
|Date=2017/05/31
|DS=DS4
|Download=TheoLog2017-Vorlesung-14-overlay.pdf, TheoLog2017-Vorlesung-14-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Repetitorium 2
|Room=HSZ/0004
|Date=2017/06/02
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Logisches Schließen
|Room=HSZ/0004
|Date=2017/06/14
|DS=DS4
|Download=TheoLog2017-Vorlesung-15-overlay.pdf, TheoLog2017-Vorlesung-15-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Logisches Schließen (2)
|Room=HSZ/0004
|Date=2017/06/16
|DS=DS3
|Download=TheoLog2017-Vorlesung-16-overlay.pdf, TheoLog2017-Vorlesung-16-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Funktionen und Normalformen
|Room=HSZ/0004
|Date=2017/06/21
|DS=DS4
|Download=TheoLog2017-Vorlesung-17-overlay.pdf, TheoLog2017-Vorlesung-17-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Resolution
|Room=HSZ/0004
|Date=2017/06/23
|DS=DS3
|Download=TheoLog2017-Vorlesung-18-overlay.pdf, TheoLog2017-Vorlesung-18-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Endliche Modelle und das Auswertungsproblem
|Room=HSZ/0004
|Date=2017/06/28
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Gödels Unvollständigkeitssätze
|Room=HSZ/0004
|Date=2017/06/30
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Logik höherer Ordnung
|Room=HSZ/0004
|Date=2017/07/05
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Repetitorium 3
|Room=HSZ/0004
|Date=2017/07/07
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Besprechung Probeklausur
|Room=HSZ/0004
|Date=2017/07/12
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Zusammenfassung und Ausblick
|Room=HSZ/0004
|Date=2017/07/14
|DS=DS3
}}

Datei:TheoLog17-musterklausur.pdf

2017-06-23T13:55:23Z

Daniel Borchmann: Daniel Borchmann lud eine neue Version von „Datei:TheoLog17-musterklausur.pdf“ hoch

Datei:TheoLog17-musterklausur.pdf

2017-06-23T12:17:41Z

Daniel Borchmann:

Datei:TheoLog17-uebung-10.pdf

2017-06-20T12:40:16Z

Daniel Borchmann: Daniel Borchmann lud eine neue Version von „Datei:TheoLog17-uebung-10.pdf“ hoch

Theoretische Informatik und Logik (SS2017)

2017-06-20T06:09:15Z

Daniel Borchmann: 2. Repetitorium

{{Vorlesung
|Title=Theoretische Informatik und Logik
|Research group=Automatentheorie; Wissensbasierte Systeme
|Lecturers=Markus Krötzsch;
|Tutors=Daniel Borchmann; Francesco Kriegel; Florian Starke
|Term=SS
|Year=2017
|Module=INF-B-290, INF-D-330
|SWSLecture=4
|SWSExercise=2
|SWSPractical=0
|Exam type=Klausur
|Description=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 (WS2016)|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 [https://jexam.inf.tu-dresden.de/ 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.

* [[Medium:TheoLog17-uebung-01.pdf|1. Übungsblatt]]
* [[Medium:TheoLog17-uebung-02.pdf|2. Übungsblatt]]
* [[Medium:TheoLog17-uebung-03.pdf|3. Übungsblatt]]
* [[Medium:TheoLog17-uebung-04.pdf|4. Übungsblatt]] ([[Medium:TheoLog17-uebung-04-pcp-in-haskell.pdf|Haskell-Programm (als pdf)]] zur „Lösung" des PCP)
* [[Medium:TheoLog17-uebung-05.pdf|5. Übungsblatt]]
* [[Medium:TheoLog17-repetitorium-1.pdf|1. Repetitorium]]
* [[Medium:TheoLog17-uebung-06.pdf|6. Übungsblatt]], [[Medium:TheoLog17-uebung-06-03-musterloesung.pdf|Musterlösung für Aufgabe 3]]
* [[Medium:TheoLog17-uebung-07.pdf|7. Übungsblatt]], [[Medium:TheoLog17-uebung-07-04-musterloesung.pdf|Musterlösung für Aufgabe 4]]
* [[Medium:TheoLog17-uebung-08.pdf|8. Übungsblatt]]
* [[Medium:TheoLog17-repetitorium-2.pdf|2. Repetitorium]]
* [[Medium:TheoLog17-uebung-09.pdf|9. Übungsblatt]]
* [[Medium:TheoLog17-uebung-10.pdf|10. Ü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 [https://creativecommons.org/licenses/by/3.0/de/ 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
|Literature=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)''
* [[Steffen Hölldobler]]: '''[[Book3008|Logik und Logikprogrammierung]].''' Synchron Verlag.
: ''(Schwerpunkt auf Logikprogrammierung und Prädikatenlogik)''
* [[Steffen Hölldobler]], [[Sebastian Bader]], [[Bertram Fronhöfer]], [[Ursula Hans]], [[Pascal Hitzler]], [[Markus Krötzsch]], [[Tobias Pietzsch]]: '''[[Book3001|Logik und Logikprogrammierung, Band 2: Aufgaben und Lösungen]]''' Synchron Verlag
: ''(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)''
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Einleitung, Übersicht, Turingmaschinen
|Room=HSZ/0004
|Date=2017/04/05
|DS=DS4
|Download=TheoLog2017-Vorlesung-01-overlay.pdf, TheoLog2017-Vorlesung-01-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Berechenbarkeit und Unentscheidbarkeit
|Room=HSZ/0004
|Date=2017/04/07
|DS=DS3
|Download=TheoLog2017-Vorlesung-02-overlay.pdf, TheoLog2017-Vorlesung-02-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=WHILE und LOOP
|Room=HSZ/0004
|Date=2017/04/12
|DS=DS4
|Download=TheoLog2017-Vorlesung-03-overlay.pdf, TheoLog2017-Vorlesung-03-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Das Halteproblem und Reduktionen
|Room=HSZ/0004
|Date=2017/04/19
|DS=DS4
|Download=TheoLog2017-Vorlesung-04-overlay.pdf, TheoLog2017-Vorlesung-04-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Der Satz von Rice und das Postsche Korrespondenzproblem
|Room=HSZ/0004
|Date=2017/04/21
|DS=DS3
|Download=TheoLog2017-Vorlesung-05-overlay.pdf, TheoLog2017-Vorlesung-05-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Unentscheidbare Probleme formaler Sprachen
|Room=HSZ/0004
|Date=2017/04/26
|DS=DS4
|Download=TheoLog2017-Vorlesung-06-overlay.pdf, TheoLog2017-Vorlesung-06-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Einführung in die Komplexitätstheorie
|Room=HSZ/0004
|Date=2017/04/28
|DS=DS3
|Download=TheoLog2017-Vorlesung-07-overlay.pdf, TheoLog2017-Vorlesung-07-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Komplexitätsklassen / Effizienz / Reduktionen
|Room=HSZ/0004
|Date=2017/05/03
|DS=DS4
|Download=TheoLog2017-Vorlesung-08-overlay.pdf, TheoLog2017-Vorlesung-08-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Repetitorium 1
|Room=HSZ/0004
|Date=2017/05/05
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NP und NP-Vollständigkeit
|Room=HSZ/0004
|Date=2017/05/10
|DS=DS4
|Download=TheoLog2017-Vorlesung-09-overlay.pdf, TheoLog2017-Vorlesung-09-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NP (Teil 2)
|Room=HSZ/0004
|Date=2017/05/12
|DS=DS3
|Download=TheoLog2017-Vorlesung-10-overlay.pdf, TheoLog2017-Vorlesung-10-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NL und PSpace
|Room=HSZ/0004
|Date=2017/05/19
|DS=DS3
|Download=TheoLog2017-Vorlesung-11-overlay.pdf, TheoLog2017-Vorlesung-11-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=PSpace-Vollständigkeit
|Room=HSZ/0004
|Date=2017/05/24
|DS=DS4
|Download=TheoLog2017-Vorlesung-12-overlay.pdf, TheoLog2017-Vorlesung-12-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Prädikatenlogik: Syntax und Semantik
|Room=HSZ/0004
|Date=2017/05/26
|DS=DS3
|Download=TheoLog2017-Vorlesung-13-overlay.pdf,TheoLog2017-Vorlesung-13-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Modelltheorie und logisches Schließen
|Room=HSZ/0004
|Date=2017/05/31
|DS=DS4
|Download=TheoLog2017-Vorlesung-14-overlay.pdf, TheoLog2017-Vorlesung-14-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Repetitorium 2
|Room=HSZ/0004
|Date=2017/06/02
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Logisches Schließen
|Room=HSZ/0004
|Date=2017/06/14
|DS=DS4
|Download=TheoLog2017-Vorlesung-15-overlay.pdf, TheoLog2017-Vorlesung-15-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Logisches Schließen (2)
|Room=HSZ/0004
|Date=2017/06/16
|DS=DS3
|Download=TheoLog2017-Vorlesung-16-overlay.pdf, TheoLog2017-Vorlesung-16-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Resolution
|Room=HSZ/0004
|Date=2017/06/21
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Endliche Modelle und das Auswertungsproblem
|Room=HSZ/0004
|Date=2017/06/23
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Gödels Unvollständigkeitssätze
|Room=HSZ/0004
|Date=2017/06/28
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Logik höherer Ordnung
|Room=HSZ/0004
|Date=2017/06/30
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=tbd
|Room=HSZ/0004
|Date=2017/07/05
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Repetitorium 3
|Room=HSZ/0004
|Date=2017/07/07
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Besprechung Probeklausur
|Room=HSZ/0004
|Date=2017/07/12
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Zusammenfassung und Ausblick
|Room=HSZ/0004
|Date=2017/07/14
|DS=DS3
}}

Datei:TheoLog17-repetitorium-2.pdf

2017-06-20T06:07:17Z

Daniel Borchmann:

Datei:TheoLog17-uebung-09.pdf

2017-06-20T05:41:41Z

Daniel Borchmann: Daniel Borchmann lud eine neue Version von „Datei:TheoLog17-uebung-09.pdf“ hoch

Datei:TheoLog17-uebung-09.pdf

2017-06-20T05:39:25Z

Daniel Borchmann: Daniel Borchmann lud eine neue Version von „Datei:TheoLog17-uebung-09.pdf“ hoch

Datei:TheoLog17-uebung-10.pdf

2017-06-19T10:20:15Z

Daniel Borchmann: Daniel Borchmann lud eine neue Version von „Datei:TheoLog17-uebung-10.pdf“ hoch

Theoretische Informatik und Logik (SS2017)

2017-06-19T10:18:51Z

Daniel Borchmann: Blatt 10 hochgeladen

{{Vorlesung
|Title=Theoretische Informatik und Logik
|Research group=Automatentheorie; Wissensbasierte Systeme
|Lecturers=Markus Krötzsch;
|Tutors=Daniel Borchmann; Francesco Kriegel; Florian Starke
|Term=SS
|Year=2017
|Module=INF-B-290, INF-D-330
|SWSLecture=4
|SWSExercise=2
|SWSPractical=0
|Exam type=Klausur
|Description=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 (WS2016)|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 [https://jexam.inf.tu-dresden.de/ 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.

* [[Medium:TheoLog17-uebung-01.pdf|1. Übungsblatt]]
* [[Medium:TheoLog17-uebung-02.pdf|2. Übungsblatt]]
* [[Medium:TheoLog17-uebung-03.pdf|3. Übungsblatt]]
* [[Medium:TheoLog17-uebung-04.pdf|4. Übungsblatt]] ([[Medium:TheoLog17-uebung-04-pcp-in-haskell.pdf|Haskell-Programm (als pdf)]] zur „Lösung" des PCP)
* [[Medium:TheoLog17-uebung-05.pdf|5. Übungsblatt]]
* [[Medium:TheoLog17-repetitorium-1.pdf|1. Repetitorium]]
* [[Medium:TheoLog17-uebung-06.pdf|6. Übungsblatt]], [[Medium:TheoLog17-uebung-06-03-musterloesung.pdf|Musterlösung für Aufgabe 3]]
* [[Medium:TheoLog17-uebung-07.pdf|7. Übungsblatt]], [[Medium:TheoLog17-uebung-07-04-musterloesung.pdf|Musterlösung für Aufgabe 4]]
* [[Medium:TheoLog17-uebung-08.pdf|8. Übungsblatt]]
* [[Medium:TheoLog17-uebung-09.pdf|9. Übungsblatt]]
* [[Medium:TheoLog17-uebung-10.pdf|10. Ü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 [https://creativecommons.org/licenses/by/3.0/de/ 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
|Literature=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)''
* [[Steffen Hölldobler]]: '''[[Book3008|Logik und Logikprogrammierung]].''' Synchron Verlag.
: ''(Schwerpunkt auf Logikprogrammierung und Prädikatenlogik)''
* [[Steffen Hölldobler]], [[Sebastian Bader]], [[Bertram Fronhöfer]], [[Ursula Hans]], [[Pascal Hitzler]], [[Markus Krötzsch]], [[Tobias Pietzsch]]: '''[[Book3001|Logik und Logikprogrammierung, Band 2: Aufgaben und Lösungen]]''' Synchron Verlag
: ''(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)''
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Einleitung, Übersicht, Turingmaschinen
|Room=HSZ/0004
|Date=2017/04/05
|DS=DS4
|Download=TheoLog2017-Vorlesung-01-overlay.pdf, TheoLog2017-Vorlesung-01-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Berechenbarkeit und Unentscheidbarkeit
|Room=HSZ/0004
|Date=2017/04/07
|DS=DS3
|Download=TheoLog2017-Vorlesung-02-overlay.pdf, TheoLog2017-Vorlesung-02-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=WHILE und LOOP
|Room=HSZ/0004
|Date=2017/04/12
|DS=DS4
|Download=TheoLog2017-Vorlesung-03-overlay.pdf, TheoLog2017-Vorlesung-03-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Das Halteproblem und Reduktionen
|Room=HSZ/0004
|Date=2017/04/19
|DS=DS4
|Download=TheoLog2017-Vorlesung-04-overlay.pdf, TheoLog2017-Vorlesung-04-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Der Satz von Rice und das Postsche Korrespondenzproblem
|Room=HSZ/0004
|Date=2017/04/21
|DS=DS3
|Download=TheoLog2017-Vorlesung-05-overlay.pdf, TheoLog2017-Vorlesung-05-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Unentscheidbare Probleme formaler Sprachen
|Room=HSZ/0004
|Date=2017/04/26
|DS=DS4
|Download=TheoLog2017-Vorlesung-06-overlay.pdf, TheoLog2017-Vorlesung-06-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Einführung in die Komplexitätstheorie
|Room=HSZ/0004
|Date=2017/04/28
|DS=DS3
|Download=TheoLog2017-Vorlesung-07-overlay.pdf, TheoLog2017-Vorlesung-07-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Komplexitätsklassen / Effizienz / Reduktionen
|Room=HSZ/0004
|Date=2017/05/03
|DS=DS4
|Download=TheoLog2017-Vorlesung-08-overlay.pdf, TheoLog2017-Vorlesung-08-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Repetitorium 1
|Room=HSZ/0004
|Date=2017/05/05
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NP und NP-Vollständigkeit
|Room=HSZ/0004
|Date=2017/05/10
|DS=DS4
|Download=TheoLog2017-Vorlesung-09-overlay.pdf, TheoLog2017-Vorlesung-09-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NP (Teil 2)
|Room=HSZ/0004
|Date=2017/05/12
|DS=DS3
|Download=TheoLog2017-Vorlesung-10-overlay.pdf, TheoLog2017-Vorlesung-10-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NL und PSpace
|Room=HSZ/0004
|Date=2017/05/19
|DS=DS3
|Download=TheoLog2017-Vorlesung-11-overlay.pdf, TheoLog2017-Vorlesung-11-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=PSpace-Vollständigkeit
|Room=HSZ/0004
|Date=2017/05/24
|DS=DS4
|Download=TheoLog2017-Vorlesung-12-overlay.pdf, TheoLog2017-Vorlesung-12-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Prädikatenlogik: Syntax und Semantik
|Room=HSZ/0004
|Date=2017/05/26
|DS=DS3
|Download=TheoLog2017-Vorlesung-13-overlay.pdf,TheoLog2017-Vorlesung-13-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Modelltheorie und logisches Schließen
|Room=HSZ/0004
|Date=2017/05/31
|DS=DS4
|Download=TheoLog2017-Vorlesung-14-overlay.pdf, TheoLog2017-Vorlesung-14-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Repetitorium 2
|Room=HSZ/0004
|Date=2017/06/02
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Logisches Schließen
|Room=HSZ/0004
|Date=2017/06/14
|DS=DS4
|Download=TheoLog2017-Vorlesung-15-overlay.pdf, TheoLog2017-Vorlesung-15-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Logisches Schließen (2)
|Room=HSZ/0004
|Date=2017/06/16
|DS=DS3
|Download=TheoLog2017-Vorlesung-16-overlay.pdf, TheoLog2017-Vorlesung-16-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Resolution
|Room=HSZ/0004
|Date=2017/06/21
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Endliche Modelle und das Auswertungsproblem
|Room=HSZ/0004
|Date=2017/06/23
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Gödels Unvollständigkeitssätze
|Room=HSZ/0004
|Date=2017/06/28
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Logik höherer Ordnung
|Room=HSZ/0004
|Date=2017/06/30
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=tbd
|Room=HSZ/0004
|Date=2017/07/05
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Repetitorium 3
|Room=HSZ/0004
|Date=2017/07/07
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Besprechung Probeklausur
|Room=HSZ/0004
|Date=2017/07/12
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Zusammenfassung und Ausblick
|Room=HSZ/0004
|Date=2017/07/14
|DS=DS3
}}

Datei:TheoLog17-uebung-10.pdf

2017-06-19T10:16:10Z

Daniel Borchmann:

Datei:TheoLog17-uebung-09.pdf

2017-06-09T08:56:17Z

Daniel Borchmann: Daniel Borchmann lud eine neue Version von „Datei:TheoLog17-uebung-09.pdf“ hoch

Datei:TheoLog17-uebung-09.pdf

2017-06-09T08:48:26Z

Daniel Borchmann: Daniel Borchmann lud eine neue Version von „Datei:TheoLog17-uebung-09.pdf“ hoch

Theoretische Informatik und Logik (SS2017)

2017-06-08T13:09:11Z

Daniel Borchmann: 9. Übungsblatt

{{Vorlesung
|Title=Theoretische Informatik und Logik
|Research group=Automatentheorie; Wissensbasierte Systeme
|Lecturers=Markus Krötzsch;
|Tutors=Daniel Borchmann; Francesco Kriegel; Florian Starke
|Term=SS
|Year=2017
|Module=INF-B-290, INF-D-330
|SWSLecture=4
|SWSExercise=2
|SWSPractical=0
|Exam type=Klausur
|Description=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 (WS2016)|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 [https://jexam.inf.tu-dresden.de/ 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.

* [[Medium:TheoLog17-uebung-01.pdf|1. Übungsblatt]]
* [[Medium:TheoLog17-uebung-02.pdf|2. Übungsblatt]]
* [[Medium:TheoLog17-uebung-03.pdf|3. Übungsblatt]]
* [[Medium:TheoLog17-uebung-04.pdf|4. Übungsblatt]] ([[Medium:TheoLog17-uebung-04-pcp-in-haskell.pdf|Haskell-Programm (als pdf)]] zur „Lösung" des PCP)
* [[Medium:TheoLog17-uebung-05.pdf|5. Übungsblatt]]
* [[Medium:TheoLog17-repetitorium-1.pdf|1. Repetitorium]]
* [[Medium:TheoLog17-uebung-06.pdf|6. Übungsblatt]], [[Medium:TheoLog17-uebung-06-03-musterloesung.pdf|Musterlösung für Aufgabe 3]]
* [[Medium:TheoLog17-uebung-07.pdf|7. Übungsblatt]], [[Medium:TheoLog17-uebung-07-04-musterloesung.pdf|Musterlösung für Aufgabe 4]]
* [[Medium:TheoLog17-uebung-08.pdf|8. Übungsblatt]]
* [[Medium:TheoLog17-uebung-09.pdf|9. Ü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 [https://creativecommons.org/licenses/by/3.0/de/ 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
|Literature=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)''
* [[Steffen Hölldobler]]: '''[[Book3008|Logik und Logikprogrammierung]].''' Synchron Verlag.
: ''(Schwerpunkt auf Logikprogrammierung und Prädikatenlogik)''
* [[Steffen Hölldobler]], [[Sebastian Bader]], [[Bertram Fronhöfer]], [[Ursula Hans]], [[Pascal Hitzler]], [[Markus Krötzsch]], [[Tobias Pietzsch]]: '''[[Book3001|Logik und Logikprogrammierung, Band 2: Aufgaben und Lösungen]]''' Synchron Verlag
: ''(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)''
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Einleitung, Übersicht, Turingmaschinen
|Room=HSZ/0004
|Date=2017/04/05
|DS=DS4
|Download=TheoLog2017-Vorlesung-01-overlay.pdf, TheoLog2017-Vorlesung-01-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Berechenbarkeit und Unentscheidbarkeit
|Room=HSZ/0004
|Date=2017/04/07
|DS=DS3
|Download=TheoLog2017-Vorlesung-02-overlay.pdf, TheoLog2017-Vorlesung-02-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=WHILE und LOOP
|Room=HSZ/0004
|Date=2017/04/12
|DS=DS4
|Download=TheoLog2017-Vorlesung-03-overlay.pdf, TheoLog2017-Vorlesung-03-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Das Halteproblem und Reduktionen
|Room=HSZ/0004
|Date=2017/04/19
|DS=DS4
|Download=TheoLog2017-Vorlesung-04-overlay.pdf, TheoLog2017-Vorlesung-04-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Der Satz von Rice und das Postsche Korrespondenzproblem
|Room=HSZ/0004
|Date=2017/04/21
|DS=DS3
|Download=TheoLog2017-Vorlesung-05-overlay.pdf, TheoLog2017-Vorlesung-05-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Unentscheidbare Probleme formaler Sprachen
|Room=HSZ/0004
|Date=2017/04/26
|DS=DS4
|Download=TheoLog2017-Vorlesung-06-overlay.pdf, TheoLog2017-Vorlesung-06-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Einführung in die Komplexitätstheorie
|Room=HSZ/0004
|Date=2017/04/28
|DS=DS3
|Download=TheoLog2017-Vorlesung-07-overlay.pdf, TheoLog2017-Vorlesung-07-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Komplexitätsklassen / Effizienz / Reduktionen
|Room=HSZ/0004
|Date=2017/05/03
|DS=DS4
|Download=TheoLog2017-Vorlesung-08-overlay.pdf, TheoLog2017-Vorlesung-08-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Repetitorium 1
|Room=HSZ/0004
|Date=2017/05/05
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NP und NP-Vollständigkeit
|Room=HSZ/0004
|Date=2017/05/10
|DS=DS4
|Download=TheoLog2017-Vorlesung-09-overlay.pdf, TheoLog2017-Vorlesung-09-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NP (Teil 2)
|Room=HSZ/0004
|Date=2017/05/12
|DS=DS3
|Download=TheoLog2017-Vorlesung-10-overlay.pdf, TheoLog2017-Vorlesung-10-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NL und PSpace
|Room=HSZ/0004
|Date=2017/05/19
|DS=DS3
|Download=TheoLog2017-Vorlesung-11-overlay.pdf, TheoLog2017-Vorlesung-11-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=PSpace-Vollständigkeit
|Room=HSZ/0004
|Date=2017/05/24
|DS=DS4
|Download=TheoLog2017-Vorlesung-12-overlay.pdf, TheoLog2017-Vorlesung-12-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Prädikatenlogik: Syntax und Semantik
|Room=HSZ/0004
|Date=2017/05/26
|DS=DS3
|Download=TheoLog2017-Vorlesung-13-overlay.pdf,TheoLog2017-Vorlesung-13-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Modelltheorie und logisches Schließen
|Room=HSZ/0004
|Date=2017/05/31
|DS=DS4
|Download=TheoLog2017-Vorlesung-14-overlay.pdf, TheoLog2017-Vorlesung-14-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Repetitorium 2
|Room=HSZ/0004
|Date=2017/06/02
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=tbd
|Room=HSZ/0004
|Date=2017/06/14
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=tbd
|Room=HSZ/0004
|Date=2017/06/16
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=tbd
|Room=HSZ/0004
|Date=2017/06/21
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=tbd
|Room=HSZ/0004
|Date=2017/06/23
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=tbd
|Room=HSZ/0004
|Date=2017/06/28
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=tbd
|Room=HSZ/0004
|Date=2017/06/30
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=tbd
|Room=HSZ/0004
|Date=2017/07/05
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Repetitorium 3
|Room=HSZ/0004
|Date=2017/07/07
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Besprechung Probeklausur
|Room=HSZ/0004
|Date=2017/07/12
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Zusammenfassung und Ausblick
|Room=HSZ/0004
|Date=2017/07/14
|DS=DS3
}}

Datei:TheoLog17-uebung-09.pdf

2017-06-08T13:08:06Z

Daniel Borchmann:

Theoretische Informatik und Logik (SS2017)

2017-06-01T08:30:38Z

Daniel Borchmann: Musterlösung für Aufgabe 7.4

Datei:TheoLog17-uebung-07-04-musterloesung.pdf

2017-06-01T08:28:39Z

Daniel Borchmann:

Theoretische Informatik und Logik (SS2017)

2017-05-26T06:54:02Z

Daniel Borchmann: Musterlösungen für Aufgabe 6.3 hinzugefügt

Datei:TheoLog17-uebung-06-03-musterloesung.pdf

2017-05-26T06:51:20Z

Daniel Borchmann:

Theoretische Informatik und Logik (SS2017)

2017-05-24T12:14:19Z

Daniel Borchmann: Update zur Übungsplanung

Datei:TheoLog17-uebung-08.pdf

2017-05-24T08:55:55Z

Daniel Borchmann: Daniel Borchmann lud eine neue Version von „Datei:TheoLog17-uebung-08.pdf“ hoch

Theoretische Informatik und Logik (SS2017)

2017-05-23T11:00:12Z

Daniel Borchmann: Weitere Übungsverlegung wegen Himmelfahrt

Datei:TheoLog17-uebung-08.pdf

2017-05-22T13:16:23Z

Daniel Borchmann: Daniel Borchmann lud eine neue Version von „Datei:TheoLog17-uebung-08.pdf“ hoch

Datei:TheoLog17-uebung-08.pdf

2017-05-22T13:03:53Z

Daniel Borchmann: Daniel Borchmann lud eine neue Version von „Datei:TheoLog17-uebung-08.pdf“ hoch

Theoretische Informatik und Logik (SS2017)

2017-05-22T13:02:47Z

Daniel Borchmann: Verweis auf 8. Übungsblatt hinzugefügt

Datei:TheoLog17-uebung-08.pdf

2017-05-22T12:55:10Z

Daniel Borchmann: