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

Forschungsprojekt Algebraische und logische Grundlagen der Informatik (WS2026)

2026-09-15T11:49:15Z

Sascha Klüppelholz:

{{Vorlesung
|Title=Forschungsprojekt
|Title_EN=Research Project
|Research group=Algebraische und logische Grundlagen der Informatik
|Lecturers=Christel Baier
|Language=DE,EN
|Term=WS
|Year=2026
|Module=INF-25-Ma-FP
|SWSLecture=0
|SWSExercise=0
|SWSPractical=100h
|Description=Das Forschungsprojekt ist angedacht für Studierende der Studiengänge ''Master Computer Science'' und ''Diplom Informatik''. Teilnehmende bearbeiten ausgewählte Themen aus den Bereichen Model Checking, Automatentheorie und Logik mit dem Ziel, Fähigkeiten für ihre forschungsorientierte Spezialisierung und unabhängige Forschungsarbeiten zu erwerben.

=== Anmeldung ===

Wenn Sie das Forschungsprojekt an unserem Lehrstuhl belegen möchten, senden Sie eine E-Mail an [mailto:studies_alg@mailbox.tu-dresden.de studies_alg@mailbox.tu-dresden.de].

=== Prüfungsleistung ===

'''Master Computer Science (PO 2025)'''
* {{ModuleLink|INF-25-Ma-FP}}: Komplexe Leistung (200 Stunden)
'''Diplom Informatik (PO 2025)'''
* {{ModuleLink|INF-25-Ma-FP}}: Komplexe Leistung (200 Stunden)

Als Komplexe Leistung ist eine Projektarbeit, eine Präsentation (25 Minuten) sowie eine mündliche Fragenrunde (15 Minuten) vorgesehen.

=== Kontakt ===

Bei organisatorischen Fragen senden Sie eine E-Mail an [mailto:studies_alg@mailbox.tu-dresden.de studies_alg@mailbox.tu-dresden.de].

|Description_EN=The Research Project is intended for students enrolled in the Master Computer Science and Diplom Informatik programs. Participants study selected topics from the fields of model checking, automata theory and logics. The purpose of this course is for students to acquire skills for their research-oriented specialization and independent research work.

=== Registration ===

If you want to take the Research Project with our chair, please send an e-mail to [mailto:studies_alg@mailbox.tu-dresden.de studies_alg@mailbox.tu-dresden.de].

=== Examination ===

'''Master Computer Science (PO 2025)'''
* {{ModuleLink|INF-25-Ma-FP}}: ''Komplexe Leistung'' (200 hours)

'''Diplom Informatik (PO 2025)'''
* {{ModuleLink|INF-25-Ma-FP}}: ''Komplexe Leistung'' (200 hours)

The ''Komplexe Leistung'' (complex or multi-part examination) consists of a written project report, a presentation (25 minutes) and an oral question-and-answer session (15 minutes).

=== Contact ===

In case of organizational questions, please send an e-mail to [mailto:studies_alg@mailbox.tu-dresden.de studies_alg@mailbox.tu-dresden.de].

}}

Belegseminar Algebraische und logische Grundlagen der Informatik (WS2026)

2026-09-15T11:47:54Z

Sascha Klüppelholz:

{{Vorlesung
|Title=Belegseminar
|Title_EN=Student Project Seminar (Belegseminar)
|Research group=Algebraische und logische Grundlagen der Informatik
|Lecturers=Christel Baier
|Language=DE,EN
|Term=WS
|Year=2026
|Module=INF-25-Ma-BSem
|SWSLecture=0
|SWSExercise=4
|SWSPractical=0
|Description=Im Rahmen des Belegseminars wird ein Thema mit Bezug zu den aktuellen Projekten des Lehrstuhls bearbeitet. Einen Überblick finden Sie auf der [[Algebraische und logische Grundlagen der Informatik|Seite des Lehrstuhls]] im Tab ''Aktive Projekte''.

In der Regel sollte das Belegseminar in Kombination mit einem großen Beleg am Lehrstuhl belegt werden. Es kann allerdings auch unabhängig davon belegt werden.

=== Anmeldung ===

Wenn Sie das Belegseminar an unserem Lehrstuhl belegen möchten, senden Sie eine E-Mail an [mailto:studies_alg@mailbox.tu-dresden.de studies_alg@mailbox.tu-dresden.de].

=== Prüfungsleistung ===
'''Diplom Informatik (PO 2025)'''
* {{ModuleLink|INF-25-Ma-BSem}}: Komplexe Leistung (50 Stunden)

Als Komplexe Leistung ist eine Präsentation inkl. Fragenrunde (25 Minuten) sowie eine schriftliche Zusammenfassung (ca. 5-8 Seiten) vorgesehen.

=== Kontakt ===

Bei organisatorischen Fragen senden Sie eine E-Mail an [mailto:studies_alg@mailbox.tu-dresden.de studies_alg@mailbox.tu-dresden.de].

|Description_EN=As part of this course, you will work on a topic related to current research projects of the chair. An overview is given on the [[Algebraische und logische Grundlagen der Informatik|page of the chair]] under the tab ''Active projects''.

The Student Project Seminar is intended to be taken in combination with a ''Großer Beleg''. However, it can also be taken independently thereof.

=== Registration ===

If you want to take the Student Project Seminar with our chair, please send an e-mail to [mailto:studies_alg@mailbox.tu-dresden.de studies_alg@mailbox.tu-dresden.de].

=== Examination ===
'''Diplom Informatik (PO 2025)'''
* {{ModuleLink|INF-25-Ma-BSem}}: ''Komplexe Leistung'' (50 hours)

The ''Komplexe Leistung'' (complex or multi-part examination) consists of a presentation incl. question-and-answet session (25 minutes) and a written report (approx. 5-8 pages).

=== Contact ===

In case of organizational questions, please send an e-mail to [mailto:studies_alg@mailbox.tu-dresden.de studies_alg@mailbox.tu-dresden.de].
}}

Bachelorseminar Algebraische und logische Grundlagen der Informatik (WS2026)

2026-09-15T11:47:24Z

Sascha Klüppelholz:

{{Vorlesung
|Title=Bachelorseminar
|Title_EN=Bachelor Seminar
|Research group=Algebraische und logische Grundlagen der Informatik
|Lecturers=Christel Baier
|Language=DE
|Term=WS
|Year=2026
|Module=INF-25-Ba-BaSe
|SWSLecture=0
|SWSExercise=4
|SWSPractical=0
|Description=Im Rahmen des Bachelorseminars wird ein Thema mit Bezug zu den aktuellen Projekten des Lehrstuhls bearbeitet. Einen Überblick finden Sie auf der [[Algebraische und logische Grundlagen der Informatik|Seite des Lehrstuhls]] im Tab ''Aktive Projekte''.

In der Regel sollte das Bachelorseminar in Kombination mit einer Bachelorarbeit am Lehrstuhl belegt werden. Es kann allerdings auch unabhängig davon belegt werden.

=== Anmeldung ===

Wenn Sie das Bachelorseminar an unserem Lehrstuhl belegen möchten, senden Sie eine E-Mail an [mailto:studies_alg@mailbox.tu-dresden.de studies_alg@mailbox.tu-dresden.de].

=== Prüfungsleistung ===
'''Bachelor Informatik (PO 2025)'''
* {{ModuleLink|INF-25-Ba-BaSe}}: Komplexe Leistung (50 Stunden)

'''Bachelor Angewandte Informatik (PO 2025)'''
* {{ModuleLink|INF-25-Ba-BaSe}}: Komplexe Leistung (50 Stunden)

Als Komplexe Leistung ist eine Präsentation inkl. Fragenrunde (25 Minuten) sowie eine schriftliche Zusammenfassung (ca. 5-8 Seiten) vorgesehen.

=== Kontakt ===

Bei organisatorischen Fragen senden Sie eine E-Mail an [mailto:studies_alg@mailbox.tu-dresden.de studies_alg@mailbox.tu-dresden.de].
|Description_EN=As part of this course, you will work on a topic related to current research projects of the chair. An overview is given on the [[Algebraische und logische Grundlagen der Informatik|page of the chair]] under the tab ''Active projects''.

The Bachelor Seminar is intended to be taken in combination with a bachelor's thesis. However, it can also be taken independently of a thesis.

=== Registration ===

If you want to take the Bachelor Seminar with our chair, please send an e-mail to [mailto:studies_alg@mailbox.tu-dresden.de studies_alg@mailbox.tu-dresden.de].

=== Examination ===
'''Bachelor Informatik (PO 2025)'''
* {{ModuleLink|INF-25-Ba-BaSe}}: ''Komplexe Leistung'' (50 hours)

'''Bachelor Angewandte Informatik (PO 2025)'''
* {{ModuleLink|INF-25-Ba-BaSe}}: ''Komplexe Leistung'' (50 hours)

The ''Komplexe Leistung'' (complex or multi-part examination) consists of a presentation incl. question-and-answet session (25 minutes) and a written report (approx. 5-8 pages).

=== Contact ===

In case of organizational questions, please send an e-mail to [mailto:studies_alg@mailbox.tu-dresden.de studies_alg@mailbox.tu-dresden.de].
}}

Analyse eines Forschungsthemas: Algebraische und logische Grundlagen der Informatik (WS2026)

2026-09-15T11:46:31Z

Sascha Klüppelholz:

{{Vorlesung
|Title=Analyse eines Forschungsthemas
|Title_EN=Analysis of a Research Topic
|Research group=Algebraische und logische Grundlagen der Informatik
|Lecturers=Christel Baier
|Language=DE,EN
|Term=WS
|Year=2026
|Module=INF-25-Ma-AFT
|SWSLecture=0
|SWSExercise=0
|SWSPractical=40h
|UmfangAlternativ=Projekte (40 Stunden)
|Description=Im Rahmen der Veranstaltung wird ein Thema mit Bezug zu den aktuellen Projekten des Lehrstuhls bearbeitet. Einen Überblick finden Sie auf der [[Algebraische und logische Grundlagen der Informatik|Seite des Lehrstuhls]] im Tab ''Aktive Projekte''.

''Analyse eines Forschungsthemas'' kann in Kombination mit einer Abschlussarbeit belegt werden oder unabhängig davon.

=== Anmeldung ===

Wenn Sie ''Analyse eines Forschungsthemas'' an unserem Lehrstuhl belegen möchten, senden Sie eine E-Mail an [mailto:studies_alg@mailbox.tu-dresden.de studies_alg@mailbox.tu-dresden.de].

=== Prüfungsleistung ===
'''Diplom Informatik (PO 2025)'''
* {{ModuleLink|INF-25-Ma-AFT}}: Komplexe Leistung (80 Stunden)

Als Komplexe Leistung ist eine Präsentation inkl. Fragenrunde (30 Minuten) sowie eine schriftliche Zusammenfassung (ca. 10 Seiten) vorgesehen.

=== Kontakt ===

Bei organisatorischen Fragen senden Sie eine E-Mail an [mailto:studies_alg@mailbox.tu-dresden.de studies_alg@mailbox.tu-dresden.de].
|Description_EN=As part of this course, you will work on a topic related to current research projects of the chair. An overview is given on the [[Algebraische und logische Grundlagen der Informatik|page of the chair]] under the tab ''Active projects''.

''Analysis of a Research Topic'' can be attended in combination with a thesis at the chair or separately.

=== Registration ===

If you want to take ''Analysis of a Research Topic'' with our Chair, please send an e-mail to [mailto:studies_alg@mailbox.tu-dresden.de studies_alg@mailbox.tu-dresden.de].

=== Examination ===
'''Diplom Informatik (PO 2025)'''
* {{ModuleLink|INF-25-Ma-AFT}}: ''Komplexe Leistung'' (80 hours)

The ''Komplexe Leistung'' (complex or multi-part examination) consists of a presentation incl. question-and-answet session (30 minutes) and a written report (approx. 10 pages).

=== Contact ===

In case of organizational questions, please send an e-mail to [mailto:studies_alg@mailbox.tu-dresden.de studies_alg@mailbox.tu-dresden.de].
}}

Seminar Selected Topics in Logic and Verification (WS2026)

2026-09-15T11:45:26Z

Sascha Klüppelholz:

{{Vorlesung
|Title=Seminar „Selected Topics in Logic and Verification“
|Title_EN=Seminar “Selected Topics in Logic and Verification”
|Research group=Algebraische und logische Grundlagen der Informatik
|Lecturers=Christel Baier; Jakob Piribauer
|Language=EN
|Term=WS
|Year=2026
|Module=CMS-SEM, INF-25-Ma-FTK-Sem
|SWSLecture=0
|SWSExercise=2
|SWSPractical=0
|Description=
{{MissingTranslation|Language=de}}

In this seminar, a selection of research papers from the areas of logic and verification will be discussed. These papers range from classical topics in logic and automata theory to recent research, in particular in formal verification and model checking.

Dieses Seminar richtet sich in erster Linie an Studierende der Studiengänge Master Computer Science und Diplom Informatik.

=== Anmeldung ===

Für die Teilnahme ist eine Registrierung via Opal bis zum 19. Oktober erforderlich. Wir verlinken zum Opal-Kurs, sobald dieser eingerichtet ist.

=== Voraussetzungen ===

Es werden fundierte Kenntnisse in Theoretischer Informatik und Logik vorausgesetzt.

=== Termine ===

Alle fristgerecht in Opal registrierten Teilnehmer:innen werden per E-Mail über die Einführungsveranstaltung informiert. Anschließend wird allen Teilnehmer:innen je ein Thema und ein Betreuer zugeteilt. Danach wird das weitere Vorgehen individuell mit dem Betreuer besprochen.

Die geforderten Vorträge werden als Blockveranstaltung im Zeitraum Januar–März 2027 stattfinden. Die genauen Termine werden zu einem späteren Zeitpunkt bekanntgegeben.

Die schriftliche Ausarbeitung ist bis zum 28. Februar 2027 einzureichen.

=== Prüfungsleistung ===

'''Master Computer Science (PO 2025)'''
* {{ModuleLink|INF-25-Ma-FTK-Sem}}: Komplexe Leistung (40 Stunden)

'''Diplom Informatik (PO 2025)'''
* {{ModuleLink|INF-25-Ma-FTK-Sem}}: Komplexe Leistung (40 Stunden)

Als Komplexe Leistung ist ein Tafelvortrag (45 Minuten) sowie eine mündliche Fragenrunde (10 Minuten) vorgesehen.

'''Master Computational Modeling and Simulation'''
* {{ModuleLink|CMS-SEM}}:  Präsentation und  Seminararbeit

=== Kontakt ===

Bei organisatorischen Fragen senden Sie eine E-Mail an [mailto:studies_alg@mailbox.tu-dresden.de studies_alg@mailbox.tu-dresden.de].

|Description_EN=In this seminar, a selection of research papers from the areas of logic and verification will be discussed. These papers range from classical topics in logic and automata theory to recent research, in particular in formal verification and model checking.

This seminar is mainly intended for students enrolled in the Master Computer Science and Diplom Informatik programs.

=== Registration ===

Registration via Opal is required until October 19. We will link to the Opal course once it is set up.

=== Prerequisites ===

For the seminar, profound knowledge in theoretical computer science and logics is presumed.

=== Dates ===

All participants registered in Opal by the due date will be notified about the initital meeting by e-mail. Each participant will then be assigned a topic and a supervisor. After that, further proceedings are arranged individually between each participant and their supervisor.

Presentations will be held between Januar and March 2027. The specific dates will be announced later.

The seminar paper (Seminararbeit) is due by February 28, 2027.

=== Examination ===

'''Master Computer Science (PO 2025)'''
* {{ModuleLink|INF-25-Ma-FTK-Sem}}: ''Komplexe Leistung'' (40 hours)

'''Diplom Informatik (PO 2025)'''
* {{ModuleLink|INF-25-Ma-FTK-Sem}}: ''Komplexe Leistung'' (40 hours)

The ''Komplexe Leistung'' (complex or multi-part examination) consists of a black board presentation (45 minutes) and an oral question-and-answer session (10 minutes).

'''Master Computational Modeling and Simulation'''
* {{ModuleLink|CMS-SEM}}:  presentation and  seminar paper

=== Contact ===

In case of organizational questions, please send an e-mail to [mailto:studies_alg@mailbox.tu-dresden.de studies_alg@mailbox.tu-dresden.de].

}}

Proseminar Theoretische Informatik (WS2026)

2026-09-15T11:44:51Z

Sascha Klüppelholz:

{{Vorlesung
|Title=Proseminar „Theoretische Informatik“
|Title_EN=Proseminar “Theoretische Informatik”
|Research group=Algebraische und logische Grundlagen der Informatik
|Lecturers=Sascha Klüppelholz
|Language=DE
|Term=WS
|Year=2026
|Module=INF-25-Ba-WIA
|SWSLecture=0
|SWSExercise=2
|SWSPractical=0
|Description=Das Thema des Proseminars ist die Analyse von Algorithmen. Es werden u. a. Algorithmen aus den Büchern [https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/ „Introduction to Algorithms“] von Cormen, Leiserson, Rivest und Stein, [https://www-cs-faculty.stanford.edu/~knuth/gkp.html „Concrete Mathematics“] von Graham, Knuth und Patashnik sowie [https://diestel-graph-theory.com/german/index.html „Graphentheorie“] von Diestel betrachtet.

=== Anmeldung ===

Für die Teilnahme ist eine Registrierung [https://bildungsportal.sachsen.de/opal/auth/RepositoryEntry/55848075267 via Opal] bis zum 12. Oktober erforderlich.

=== Voraussetzungen ===

Neben dem Interesse an theoretischer Informatik setzt das Proseminar solide Kenntnisse in den Gebieten Algorithmen und Datenstrukturen sowie Mathematik im Umfang der ersten zwei Studiensemester voraus.

=== Termine ===

Die Auftaktveranstaltung findet voraussichtlich am 15. oder 16. Oktober statt. Details werden allen fristgerecht in Opal eingeschriebenen Teilnehmer:inne per E-Mail mitgeteilt. Anschließend wird allen Teilnehmer:innen je ein Thema und ein Betreuer zugeteilt. Das weitere Vorgehen wird individuell mit dem Betreuer besprochen.

Die Vorträge werden als Blockveranstaltung im Zeitraum Januar–März 2027 stattfinden. Termine werden später bekanntgegeben.

Die schriftliche Ausarbeitung ist bis zum 14. März 2027 einzureichen.

=== Prüfungsleistung ===

'''Bachelor Informatik (PO 2025)'''
* {{ModuleLink|INF-25-Ba-WIA}}: Komplexe Leistung (60 Stunden)

'''Bachelor Angewandte Informatik (PO 2025)'''
* {{ModuleLink|INF-25-Ba-WIA}}: Komplexe Leistung (60 Stunden)

'''Diplom Informatik (PO 2025)'''
* {{ModuleLink|INF-25-Ba-WIA}}: Komplexe Leistung (60 Stunden)

Als Komplexe Leistung ist ein Folienvortrag (25 Minuten) sowie eine mündliche Fragenrunde (15 Minuten) vorgesehen.

=== Kontakt ===

Bei organisatorischen Fragen senden Sie eine E-Mail an [mailto:studies_alg@mailbox.tu-dresden.de studies_alg@mailbox.tu-dresden.de].

|Description_EN=
{{MissingTranslation|Language=en}}

Das Thema des Proseminars ist die Analyse von Algorithmen. Es werden u. a. Algorithmen aus den Büchern [https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/ „Introduction to Algorithms“] von Cormen, Leiserson, Rivest und Stein, [https://www-cs-faculty.stanford.edu/~knuth/gkp.html „Concrete Mathematics“] von Graham, Knuth und Patashnik sowie [https://diestel-graph-theory.com/german/index.html „Graphentheorie“] von Diestel betrachtet.

=== Registration ===

Registration [https://bildungsportal.sachsen.de/opal/auth/RepositoryEntry/55848075267 via Opal] is required until October 12.

=== Prerequisites ===

Besides an interest in theoretical computer science, the ''Proseminar'' requires solid foundations in algorithms and data structures as well as mathematics as covered in the first two semesters of the study program.

=== Dates ===

The initial meeting will be held on October 15 or 16. All participants registered in Opal by the due date will be notified about the details by e-mail. Each participant will then be assigned a topic and a supervisor. After that, further proceedings are arranged individually between each participant and their supervisor.

The required presentations will be held en bloc between January and March 2027. The specific dates will be announced later.

The written paper is due by March 14, 2027.

=== Examination ===

'''Bachelor Informatik (PO 2025)'''
* {{ModuleLink|INF-25-Ba-WIA}}: ''Komplexe Leistung'' (60 hours)

'''Bachelor Angewandte Informatik (PO 2025)'''
* {{ModuleLink|INF-25-Ba-WIA}}: ''Komplexe Leistung'' (60 hours)

'''Diplom Informatik (PO 2025)'''
* {{ModuleLink|INF-25-Ba-WIA}}: ''Komplexe Leistung'' (60 hours)

The ''Komplexe Leistung'' (complex or multi-part examination) consists of a presentation (25 minutes) and an oral question-and-answer session (15 minutes).

=== Contact ===

In case of organizational questions, please send an e-mail to [mailto:studies_alg@mailbox.tu-dresden.de studies_alg@mailbox.tu-dresden.de].

}}

Seminar Games and Graphs (WS2026)

2026-09-15T11:44:10Z

Sascha Klüppelholz:

{{Vorlesung
|Title=Seminar „Games and Graphs“
|Title_EN=Seminar “Games and Graphs”
|Research group=Algebraische und logische Grundlagen der Informatik
|Lecturers=Christel Baier; Jakob Piribauer
|Language=EN
|Term=WS
|Year=2026
|Module=INF-25-Ma-FTK-Sem
|SWSLecture=0
|SWSExercise=2
|SWSPractical=0
|Description=
{{MissingTranslation|Language=de}}

The topic of this seminar are infinite-duration games that are played between two or more players on a graph structure. Such games can be used to model a wide range of multi-agent systems or as theoretical tools in areas like logic and complexity theory. Hence, they play an important role in theoretical computer science, in particular in verification and synthesis.
The topics of the seminar address various forms of these games with different objectives and properties and algorithms to solve them.

Many of the topics can be found in the book [https://arxiv.org/abs/2305.10546 “Games on graphs: From logic and automata to algorithms”] edited by Fijalkow et al. (2025).

=== Anmeldung ===

Für die Teilnahme ist eine Registrierung via Opal bis zum 19. Oktober erforderlich. Wir verlinken zum Opal-Kurs, sobald dieser eingerichtet ist.

=== Voraussetzungen ===

Es werden fundierte Kenntnisse in Theoretischer Informatik und Logik vorausgesetzt.

=== Termine ===

Alle fristgerecht in Opal registrierten Teilnehmer:innen werden per E-Mail über die Einführungsveranstaltung informiert. Anschließend wird allen Teilnehmer:innen je ein Thema und ein Betreuer zugeteilt. Danach wird das weitere Vorgehen individuell mit dem Betreuer besprochen.

Die geforderten Vorträge werden als Blockveranstaltung im Zeitraum Januar-März 2027 stattfinden. Die genauen Termine werden zu einem späteren Zeitpunkt bekanntgegeben.

Die schriftliche Ausarbeitung ist bis zum 28. Februar 2027 einzureichen.

=== Prüfungsleistung ===

'''Master Computer Science (PO 2025)'''
* {{ModuleLink|INF-25-Ma-FTK-Sem}}: Komplexe Leistung (40 Stunden)

'''Diplom Informatik (PO 2025)'''
* {{ModuleLink|INF-25-Ma-FTK-Sem}}: Komplexe Leistung (40 Stunden)

Als Komplexe Leistung ist ein Folienvortrag (25 Minuten) sowie eine mündliche Fragenrunde (15 Minuten) vorgesehen.

=== Kontakt ===

Bei organisatorischen Fragen senden Sie eine E-Mail an [mailto:studies_alg@mailbox.tu-dresden.de studies_alg@mailbox.tu-dresden.de].

|Description_EN=The topic of this seminar are infinite-duration games that are played between two or more players on a graph structure. Such games can be used to model a wide range of multi-agent systems or as theoretical tools in areas like logic and complexity theory. Hence, they play an important role in theoretical computer science, in particular in verification and synthesis.
The topics of the seminar address various forms of these games with different objectives and properties and algorithms to solve them.

Many of the topics can be found in the book [https://arxiv.org/abs/2305.10546 “Games on graphs: From logic and automata to algorithms”] edited by Fijalkow et al. (2025).
=== Registration ===

Registration via Opal is required until October 19. We will link to the Opal course once it is set up.

=== Prerequisites ===

For the seminar, profound knowledge in theoretical computer science and logics is presumed.

=== Dates ===

All participants registered in Opal by the due date will be notified about the initial meeting by e-mail. Each participant will then be assigned a topic and a supervisor. After that, further proceedings are arranged individually between each participant and their supervisor.

Presentations will be held between January and March 2027. The specific dates will be announced later.

The seminar paper (Seminararbeit) is due by February 28, 2027.

=== Examination ===

'''Master Computer Science (PO 2025)'''
* {{ModuleLink|INF-25-Ma-FTK-Sem}}: ''Komplexe Leistung'' (40 hours)

'''Diplom Informatik (PO 2025)'''
* {{ModuleLink|INF-25-Ma-FTK-Sem}}: ''Komplexe Leistung'' (40 hours)

The ''Komplexe Leistung'' (complex or multi-part examination) consists of a presentation (25 minutes) and an oral question-and-answer session (15 minutes).

=== Contact ===

In case of organizational questions, please send an e-mail to [mailto:studies_alg@mailbox.tu-dresden.de studies_alg@mailbox.tu-dresden.de].

}}

Proseminar Theoretische Informatik (WS2026)

2026-09-15T11:43:16Z

Sascha Klüppelholz:

{{Vorlesung
|Title=Proseminar „Theoretische Informatik“
|Title_EN=Proseminar “Theoretische Informatik”
|Research group=Algebraische und logische Grundlagen der Informatik
|Lecturers=Sascha Klüppelholz
|Language=DE
|Term=WS
|Year=2026
|Module=INF-25-Ba-WIA
|SWSLecture=0
|SWSExercise=2
|SWSPractical=0
|Description=Das Thema des Proseminars ist die Analyse von Algorithmen. Es werden u. a. Algorithmen aus den Büchern [https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/ „Introduction to Algorithms“] von Cormen, Leiserson, Rivest und Stein, [https://www-cs-faculty.stanford.edu/~knuth/gkp.html „Concrete Mathematics“] von Graham, Knuth und Patashnik sowie [https://diestel-graph-theory.com/german/index.html „Graphentheorie“] von Diestel betrachtet.

=== Anmeldung ===

Für die Teilnahme ist eine Registrierung [https://bildungsportal.sachsen.de/opal/auth/RepositoryEntry/55848075267 via Opal] bis zum 12. Oktober erforderlich.

=== Voraussetzungen ===

Neben dem Interesse an theoretischer Informatik setzt das Proseminar solide Kenntnisse in den Gebieten Algorithmen und Datenstrukturen sowie Mathematik im Umfang der ersten zwei Studiensemester voraus.

=== Termine ===

Die Auftaktveranstaltung findet voraussichtlich am 15. oder 16. Oktober statt. Details werden allen fristgerecht in Opal eingeschriebenen Teilnehmer:inne per E-Mail mitgeteilt. Anschließend wird allen Teilnehmer:innen je ein Thema und ein Betreuer zugeteilt. Das weitere Vorgehen wird individuell mit dem Betreuer besprochen.

Die Vorträge werden als Blockveranstaltung im Zeitraum Januar–März 2027 stattfinden. Termine werden später bekanntgegeben.

Die schriftliche Ausarbeitung ist bis zum 14. März 2027 einzureichen.

=== Prüfungsleistung ===

'''Bachelor Informatik (PO 2025)'''
* {{ModuleLink|INF-25-Ba-WIA}}: Komplexe Leistung (60 Stunden)

'''Bachelor Angewandte Informatik (PO 2025)'''
* {{ModuleLink|INF-25-Ba-WIA}}: Komplexe Leistung (60 Stunden)

'''Diplom Informatik (PO 2025)'''
* {{ModuleLink|INF-25-Ba-WIA}}: Komplexe Leistung (60 Stunden)

Als Komplexe Leistung ist ein Folienvortrag (25 Minuten) sowie eine mündliche Fragerunde (15 Minuten) vorgesehen.

=== Kontakt ===

Bei organisatorischen Fragen senden Sie eine E-Mail an [mailto:studies_alg@mailbox.tu-dresden.de studies_alg@mailbox.tu-dresden.de].

|Description_EN=
{{MissingTranslation|Language=en}}

Das Thema des Proseminars ist die Analyse von Algorithmen. Es werden u. a. Algorithmen aus den Büchern [https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/ „Introduction to Algorithms“] von Cormen, Leiserson, Rivest und Stein, [https://www-cs-faculty.stanford.edu/~knuth/gkp.html „Concrete Mathematics“] von Graham, Knuth und Patashnik sowie [https://diestel-graph-theory.com/german/index.html „Graphentheorie“] von Diestel betrachtet.

=== Registration ===

Registration [https://bildungsportal.sachsen.de/opal/auth/RepositoryEntry/55848075267 via Opal] is required until October 12.

=== Prerequisites ===

Besides an interest in theoretical computer science, the ''Proseminar'' requires solid foundations in algorithms and data structures as well as mathematics as covered in the first two semesters of the study program.

=== Dates ===

The initial meeting will be held on October 15 or 16. All participants registered in Opal by the due date will be notified about the details by e-mail. Each participant will then be assigned a topic and a supervisor. After that, further proceedings are arranged individually between each participant and their supervisor.

The required presentations will be held en bloc between January and March 2027. The specific dates will be announced later.

The written paper is due by March 14, 2027.

=== Examination ===

'''Bachelor Informatik (PO 2025)'''
* {{ModuleLink|INF-25-Ba-WIA}}: ''Komplexe Leistung'' (60 hours)

'''Bachelor Angewandte Informatik (PO 2025)'''
* {{ModuleLink|INF-25-Ba-WIA}}: ''Komplexe Leistung'' (60 hours)

'''Diplom Informatik (PO 2025)'''
* {{ModuleLink|INF-25-Ba-WIA}}: ''Komplexe Leistung'' (60 hours)

The ''Komplexe Leistung'' (complex or multi-part examination) consists of a presentation (25 minutes) and an oral question-and-answer session (15 minutes).

=== Contact ===

In case of organizational questions, please send an e-mail to [mailto:studies_alg@mailbox.tu-dresden.de studies_alg@mailbox.tu-dresden.de].

}}

Proseminar Binäre Entscheidungsgraphen (WS2026)

2026-09-15T11:42:57Z

Sascha Klüppelholz:

{{Vorlesung
|Title=Proseminar „Binäre Entscheidungsgraphen“
|Title_EN=Proseminar “Binäre Entscheidungsgraphen”
|Research group=Algebraische und logische Grundlagen der Informatik
|Lecturers=Sascha Klüppelholz
|Language=DE
|Term=WS
|Year=2026
|Module=INF-25-Ba-WIA
|SWSLecture=0
|SWSExercise=2
|SWSPractical=0
|Description=Das Thema des Proseminars sind Binäre Entscheidungsgraphen (engl. ''binary decision diagrams'', kurz BDDs). Diese wurden erstmals von Lee und Akers zur Darstellung von Schaltfunktionen vorgestellt. Heutzutage werden verschiedene Varianten von ''ordered BDDs'' in zahlreichen Verifikationswerkzeugen und Model Checkern wie z. B. nuSMV oder Prism als Datenstruktur zur effizienten Speicherung und Analyse von Systemmodellen eingesetzt.

Die individuell zu bearbeitenden Seminarthemen befassen sich mit den theoretischen Grundlagen binärer Entscheidungsgraphen. Insbesondere sollen die wichtigsten Operatoren und Algorithmen auf BDDs vorgestellt und hinsichtlich ihrer theoretischen Komplexität untersucht werden.

=== Anmeldung ===

Für die Teilnahme ist eine Registrierung [https://bildungsportal.sachsen.de/opal/auth/RepositoryEntry/55848075268 via Opal] bis zum 12. Oktober erforderlich.

=== Voraussetzungen ===

Neben dem Interesse an theoretischer Informatik setzt das Proseminar solide Kenntnisse in den Gebieten Algorithmen und Datenstrukturen sowie Mathematik im Umfang der ersten zwei Studiensemester voraus.

=== Termine ===

Die Auftaktveranstaltung findet voraussichtlich am 15. oder 16. Oktober statt. Details werden allen fristgerecht in Opal eingeschriebenen Teilnehmer:inne per E-Mail mitgeteilt. Anschließend wird allen Teilnehmer:innen je ein Thema und ein Betreuer zugeteilt. Das weitere Vorgehen wird individuell mit dem Betreuer besprochen.

Die Vorträge werden als Blockveranstaltung im Zeitraum Januar–März 2027 stattfinden. Termine werden später bekanntgegeben.

Die schriftliche Ausarbeitung ist bis zum 14. März 2027 einzureichen.

=== Prüfungsleistung ===

'''Bachelor Informatik (PO 2025)'''
* {{ModuleLink|INF-25-Ba-WIA}}: Komplexe Leistung (60 Stunden)

'''Bachelor Angewandte Informatik (PO 2025)'''
* {{ModuleLink|INF-25-Ba-WIA}}: Komplexe Leistung (60 Stunden)

'''Diplom Informatik (PO 2025)'''
* {{ModuleLink|INF-25-Ba-WIA}}: Komplexe Leistung (60 Stunden)

Als Komplexe Leistung ist ein Folienvortrag (25 Minuten) sowie eine mündliche Fragenrunde (15 Minuten) vorgesehen.

=== Kontakt ===

Bei organisatorischen Fragen senden Sie eine E-Mail an [mailto:studies_alg@mailbox.tu-dresden.de studies_alg@mailbox.tu-dresden.de].

|Description_EN=
{{MissingTranslation|Language=en}}

Das Thema des Proseminars sind Binäre Entscheidungsgraphen (engl. ''binary decision diagrams'', kurz BDDs). Diese wurden erstmals von Lee und Akers zur Darstellung von Schaltfunktionen vorgestellt. Heutzutage werden verschiedene Varianten von ''ordered BDDs'' in zahlreichen Verifikationswerkzeugen und Model Checkern wie z. B. nuSMV oder Prism als Datenstruktur zur effizienten Speicherung und Analyse von Systemmodellen eingesetzt.

Die individuell zu bearbeitenden Seminarthemen befassen sich mit den theoretischen Grundlagen binärer Entscheidungsgraphen. Insbesondere sollen die wichtigsten Operatoren und Algorithmen auf BDDs vorgestellt und hinsichtlich ihrer theoretischen Komplexität untersucht werden.

=== Registration ===

Registration [https://bildungsportal.sachsen.de/opal/auth/RepositoryEntry/55848075268 via Opal] is required until October 12.

=== Prerequisites ===

Besides an interest in theoretical computer science, the ''Proseminar'' requires solid foundations in algorithms and data structures as well as mathematics as covered in the first two semesters of the study program.

=== Dates ===

The initial meeting will be held on October 15 or 16. All participants registered in Opal by the due date will be notified about the details by e-mail. Each participant will then be assigned a topic and a supervisor. After that, further proceedings are arranged individually between each participant and their supervisor.

The required presentations will be held en bloc between January and March 2027. The specific dates will be announced later.

The written paper is due by March 14, 2027.

=== Examination ===

'''Bachelor Informatik (PO 2025)'''
* {{ModuleLink|INF-25-Ba-WIA}}: ''Komplexe Leistung'' (60 hours)

'''Bachelor Angewandte Informatik (PO 2025)'''
* {{ModuleLink|INF-25-Ba-WIA}}: ''Komplexe Leistung'' (60 hours)

'''Diplom Informatik (PO 2025)'''
* {{ModuleLink|INF-25-Ba-WIA}}: ''Komplexe Leistung'' (60 hours)

The ''Komplexe Leistung'' (complex or multi-part examination) consists of a presentation (25 minutes) and an oral question-and-answer session (15 minutes).

=== Contact ===

In case of organizational questions, please send an e-mail to [mailto:studies_alg@mailbox.tu-dresden.de studies_alg@mailbox.tu-dresden.de].

}}

Grosser Beleg Algebraische und logische Grundlagen der Informatik (WS2026)

2026-09-15T11:42:07Z

Sascha Klüppelholz:

{{Vorlesung
|Title=Großer Beleg
|Title_EN=Student Research Project (Großer Beleg)
|Research group=Algebraische und logische Grundlagen der Informatik
|Lecturers=Christel Baier
|Language=DE,EN
|Term=WS
|Year=2026
|Module=INF-25-Ma-GB
|SWSLecture=0
|SWSExercise=0
|SWSPractical=100h
|Description=Im Rahmen der Veranstaltung wird ein Thema mit Bezug zu den aktuellen Projekten des Lehrstuhls bearbeitet. Einen Überblick finden Sie auf der [[Algebraische und logische Grundlagen der Informatik|Seite des Lehrstuhls]] im Tab ''Aktive Projekte''.

In der Regel sollte der Große Beleg in Kombination mit dem Belegseminar am Lehrstuhl belegt werden. Er kann allerdings auch unabhängig davon belegt werden.

=== Anmeldung ===

Wenn Sie den Großen Beleg an unserem Lehrstuhl belegen möchten, senden Sie eine E-Mail an [mailto:studies_alg@mailbox.tu-dresden.de studies_alg@mailbox.tu-dresden.de].

=== Prüfungsleistung ===

'''Diplom Informatik (PO 2025)'''
* {{ModuleLink|INF-25-Ma-GB}}: Komplexe Leistung (180 Stunden)

Als Komplexe Leistung ist eine Belegarbeit, eine Präsentation (25 Minuten) sowie eine mündliche Fragenrunde (15 Minuten) vorgesehen.

=== Kontakt ===

Bei organisatorischen Fragen senden Sie eine E-Mail an [mailto:studies_alg@mailbox.tu-dresden.de studies_alg@mailbox.tu-dresden.de].

|Description_EN=As part of this course, you will work on a topic related to current research projects of the chair. An overview is given on the [[Algebraische und logische Grundlagen der Informatik|page of the chair]] under the tab ''Active projects''.

The Student Research Project is intended to be taken in combination with a Student Project Seminar. However, it can also be taken independently thereof.

=== Registration ===

If you want to take the Student Research Project with our chair, please send an e-mail to [mailto:studies_alg@mailbox.tu-dresden.de studies_alg@mailbox.tu-dresden.de].

=== Examination ===

'''Diplom Informatik (PO 2025)'''
* {{ModuleLink|INF-25-Ma-GB}}: ''Komplexe Leistung'' (180 hours)

The ''Komplexe Leistung'' (complex or multi-part examination) consists of a Belegarbeit (written project), a presentation (25 minutes) and an oral question-and-answer session (15 minutes).

=== Contact ===

In case of organizational questions, please send an e-mail to [mailto:studies_alg@mailbox.tu-dresden.de studies_alg@mailbox.tu-dresden.de].
}}

Grosser Beleg Algebraische und logische Grundlagen der Informatik (WS2026)

2026-09-15T11:40:17Z

Sascha Klüppelholz:

{{Vorlesung
|Title=Großer Beleg
|Title_EN=Student Research Project (Großer Beleg)
|Research group=Algebraische und logische Grundlagen der Informatik
|Lecturers=Christel Baier
|Language=DE,EN
|Term=WS
|Year=2026
|Module=INF-25-Ma-GB
|SWSLecture=0
|SWSExercise=0
|SWSPractical=100h
|Description=Im Rahmen der Veranstaltung wird ein Thema mit Bezug zu den aktuellen Projekten des Lehrstuhls bearbeitet. Einen Überblick finden Sie auf der [[Algebraische und logische Grundlagen der Informatik|Seite des Lehrstuhls]] im Tab ''Aktive Projekte''.

In der Regel sollte der Große Beleg in Kombination mit dem Belegseminar am Lehrstuhl belegt werden. Er kann allerdings auch unabhängig davon belegt werden.

=== Anmeldung ===

Wenn Sie den Großen Beleg an unserem Lehrstuhl belegen möchten, senden Sie eine E-Mail an [mailto:studies_alg@mailbox.tu-dresden.de studies_alg@mailbox.tu-dresden.de].

=== Prüfungsleistung ===

'''Diplom Informatik (PO 2025)'''
* {{ModuleLink|INF-25-Ma-GB}}: Komplexe Leistung (180 Stunden)

Als Komplexe Leistung ist eine Belegarbeit, eine Präsentation (25 Minuten) sowie eine Mündliche Fragerunde (15 Minuten) vorgesehen.

=== Kontakt ===

Bei organisatorischen Fragen senden Sie eine E-Mail an [mailto:studies_alg@mailbox.tu-dresden.de studies_alg@mailbox.tu-dresden.de].

|Description_EN=As part of this course, you will work on a topic related to current research projects of the chair. An overview is given on the [[Algebraische und logische Grundlagen der Informatik|page of the chair]] under the tab ''Active projects''.

The Student Research Project is intended to be taken in combination with a Student Project Seminar. However, it can also be taken independently thereof.

=== Registration ===

If you want to take the Student Research Project with our chair, please send an e-mail to [mailto:studies_alg@mailbox.tu-dresden.de studies_alg@mailbox.tu-dresden.de].

=== Examination ===

'''Diplom Informatik (PO 2025)'''
* {{ModuleLink|INF-25-Ma-GB}}: ''Komplexe Leistung'' (180 hours)

The ''Komplexe Leistung'' (complex or multi-part examination) consists of a Belegarbeit (written project), a presentation (25 minutes) and an oral question-and-answer session (15 minutes).

=== Contact ===

In case of organizational questions, please send an e-mail to [mailto:studies_alg@mailbox.tu-dresden.de studies_alg@mailbox.tu-dresden.de].
}}

Forschungsprojekt Algebraische und logische Grundlagen der Informatik (WS2026)

2026-09-15T11:38:01Z

Sascha Klüppelholz:

{{Vorlesung
|Title=Forschungsprojekt
|Title_EN=Research Project
|Research group=Algebraische und logische Grundlagen der Informatik
|Lecturers=Christel Baier
|Language=DE,EN
|Term=WS
|Year=2026
|Module=INF-25-Ma-FP
|SWSLecture=0
|SWSExercise=0
|SWSPractical=100h
|Description=Das Forschungsprojekt ist angedacht für Studierende der Studiengänge ''Master Computer Science'' und ''Diplom Informatik''. Teilnehmende bearbeiten ausgewählte Themen aus den Bereichen Model Checking, Automatentheorie und Logik mit dem Ziel, Fähigkeiten für ihre forschungsorientierte Spezialisierung und unabhängige Forschungsarbeiten zu erwerben.

=== Anmeldung ===

Wenn Sie das Forschungsprojekt an unserem Lehrstuhl belegen möchten, senden Sie eine E-Mail an [mailto:studies_alg@mailbox.tu-dresden.de studies_alg@mailbox.tu-dresden.de].

=== Prüfungsleistung ===

'''Master Computer Science (PO 2025)'''
* {{ModuleLink|INF-25-Ma-FP}}: Komplexe Leistung (200 Stunden)
'''Diplom Informatik (PO 2025)'''
* {{ModuleLink|INF-25-Ma-FP}}: Komplexe Leistung (200 Stunden)

Als Komplexe Leistung ist eine Projektarbeit, eine Präsentation (25 Minuten) sowie eine Mündliche Fragerunde (15 Minuten) vorgesehen.

=== Kontakt ===

Bei organisatorischen Fragen senden Sie eine E-Mail an [mailto:studies_alg@mailbox.tu-dresden.de studies_alg@mailbox.tu-dresden.de].

|Description_EN=The Research Project is intended for students enrolled in the Master Computer Science and Diplom Informatik programs. Participants study selected topics from the fields of model checking, automata theory and logics. The purpose of this course is for students to acquire skills for their research-oriented specialization and independent research work.

=== Registration ===

If you want to take the Research Project with our chair, please send an e-mail to [mailto:studies_alg@mailbox.tu-dresden.de studies_alg@mailbox.tu-dresden.de].

=== Examination ===

'''Master Computer Science (PO 2025)'''
* {{ModuleLink|INF-25-Ma-FP}}: ''Komplexe Leistung'' (200 hours)

'''Diplom Informatik (PO 2025)'''
* {{ModuleLink|INF-25-Ma-FP}}: ''Komplexe Leistung'' (200 hours)

The ''Komplexe Leistung'' (complex or multi-part examination) consists of a written project report, a presentation (25 minutes) and an oral question-and-answer session (15 minutes).

=== Contact ===

In case of organizational questions, please send an e-mail to [mailto:studies_alg@mailbox.tu-dresden.de studies_alg@mailbox.tu-dresden.de].

}}

Exploration of a Research Subject: Algebraische und logische Grundlagen der Informatik (WS2026)

2026-09-15T11:34:43Z

Sascha Klüppelholz:

{{Vorlesung
|Title_EN=Exploration of a Research Subject
|Research group=Algebraische und logische Grundlagen der Informatik
|Lecturers=Christel Baier
|Language=DE,EN
|Term=WS
|Year=2026
|Module=INF-25-Ma-ERS
|SWSLecture=0
|SWSExercise=0
|SWSPractical=40h
|Description=Im Rahmen der Veranstaltung wird ein Thema mit Bezug zu den aktuellen Projekten des Lehrstuhls bearbeitet. Einen Überblick finden Sie auf der [[Algebraische und logische Grundlagen der Informatik|Seite des Lehrstuhls]] im Tab ''Aktive Projekte''.

''Exploration of a Research Subject'' kann in Kombination mit einer Abschlussarbeit belegt werden oder unabhängig davon.

=== Anmeldung ===

Wenn Sie ''Exploration of a Researchb Subject'' an unserem Lehrstuhl belegen möchten, senden Sie eine E-Mail an [mailto:studies_alg@mailbox.tu-dresden.de studies_alg@mailbox.tu-dresden.de].

=== Prüfungsleistung ===
'''Master Computer Science (PO 2025)'''
* {{ModuleLink|INF-25-Ma-ERS}}: Komplexe Leistung (80 Stunden)

Als Komplexe Leistung ist eine Präsentation inkl. Fragenrunde (30 Minuten) sowie eine schriftliche Zusammenfassung (ca. 10 Seiten) vorgesehen.

=== Kontakt ===

Bei organisatorischen Fragen senden Sie eine E-Mail an [mailto:studies_alg@mailbox.tu-dresden.de studies_alg@mailbox.tu-dresden.de].

|Description_EN=As part of this course, you will work on a topic related to current research projects of the chair. An overview is given on the [[Algebraische und logische Grundlagen der Informatik|page of the chair]] under the tab ''Active projects''.

''Exploration of a Research Subject'' can be attended in combination with a thesis at the chair or separately.

=== Registration ===

If you want to take ''Exploration of a Research Subject'' with our chair, please send an e-mail to [mailto:studies_alg@mailbox.tu-dresden.de studies_alg@mailbox.tu-dresden.de].

=== Examination ===
'''Master Computer Science (PO 2025)'''
* {{ModuleLink|INF-25-Ma-ERS}}: ''Komplexe Leistung'' (80 hours)

The ''Komplexe Leistung'' (complex or multi-part examination) consists of a presentation incl. question-and-answet session (30 minutes) and a written report (approx. 10 pages).

=== Contact ===

In case of organizational questions, please send an e-mail to [mailto:studies_alg@mailbox.tu-dresden.de studies_alg@mailbox.tu-dresden.de].
}}

Belegseminar Algebraische und logische Grundlagen der Informatik (WS2026)

2026-09-15T11:32:10Z

Sascha Klüppelholz:

{{Vorlesung
|Title=Belegseminar
|Title_EN=Student Project Seminar (Belegseminar)
|Research group=Algebraische und logische Grundlagen der Informatik
|Lecturers=Christel Baier
|Language=DE,EN
|Term=WS
|Year=2026
|Module=INF-25-Ma-BSem
|SWSLecture=0
|SWSExercise=4
|SWSPractical=0
|Description=Im Rahmen des Belegseminars wird ein Thema mit Bezug zu den aktuellen Projekten des Lehrstuhls bearbeitet. Einen Überblick finden Sie auf der [[Algebraische und logische Grundlagen der Informatik|Seite des Lehrstuhls]] im Tab ''Aktive Projekte''.

In der Regel sollte das Belegseminar in Kombination mit einem großen Beleg am Lehrstuhl belegt werden. Es kann allerdings auch unabhängig davon belegt werden.

=== Anmeldung ===

Wenn Sie das Belegseminar an unserem Lehrstuhl belegen möchten, senden Sie eine E-Mail an [mailto:studies_alg@mailbox.tu-dresden.de studies_alg@mailbox.tu-dresden.de].

=== Prüfungsleistung ===
'''Diplom Informatik (PO 2025)'''
* {{ModuleLink|INF-25-Ma-BSem}}: Komplexe Leistung (50 Stunden)

Als Komplexe Leistung ist eine Präsentation inkl. Fragerunde (25 Minuten) sowie eine schriftliche Zusammenfassung (ca. 5-8 Seiten) vorgesehen.

=== Kontakt ===

Bei organisatorischen Fragen senden Sie eine E-Mail an [mailto:studies_alg@mailbox.tu-dresden.de studies_alg@mailbox.tu-dresden.de].

|Description_EN=As part of this course, you will work on a topic related to current research projects of the chair. An overview is given on the [[Algebraische und logische Grundlagen der Informatik|page of the chair]] under the tab ''Active projects''.

The Student Project Seminar is intended to be taken in combination with a ''Großer Beleg''. However, it can also be taken independently thereof.

=== Registration ===

If you want to take the Student Project Seminar with our chair, please send an e-mail to [mailto:studies_alg@mailbox.tu-dresden.de studies_alg@mailbox.tu-dresden.de].

=== Examination ===
'''Diplom Informatik (PO 2025)'''
* {{ModuleLink|INF-25-Ma-BSem}}: ''Komplexe Leistung'' (50 hours)

The ''Komplexe Leistung'' (complex or multi-part examination) consists of a presentation incl. question-and-answet session (25 minutes) and a written report (approx. 5-8 pages).

=== Contact ===

In case of organizational questions, please send an e-mail to [mailto:studies_alg@mailbox.tu-dresden.de studies_alg@mailbox.tu-dresden.de].
}}

Bachelorseminar Algebraische und logische Grundlagen der Informatik (WS2026)

2026-09-15T11:30:18Z

Sascha Klüppelholz:

{{Vorlesung
|Title=Bachelorseminar
|Title_EN=Bachelor Seminar
|Research group=Algebraische und logische Grundlagen der Informatik
|Lecturers=Christel Baier
|Language=DE
|Term=WS
|Year=2026
|Module=INF-25-Ba-BaSe
|SWSLecture=0
|SWSExercise=4
|SWSPractical=0
|Description=Im Rahmen des Bachelorseminars wird ein Thema mit Bezug zu den aktuellen Projekten des Lehrstuhls bearbeitet. Einen Überblick finden Sie auf der [[Algebraische und logische Grundlagen der Informatik|Seite des Lehrstuhls]] im Tab ''Aktive Projekte''.

In der Regel sollte das Bachelorseminar in Kombination mit einer Bachelorarbeit am Lehrstuhl belegt werden. Es kann allerdings auch unabhängig davon belegt werden.

=== Anmeldung ===

Wenn Sie das Bachelorseminar an unserem Lehrstuhl belegen möchten, senden Sie eine E-Mail an [mailto:studies_alg@mailbox.tu-dresden.de studies_alg@mailbox.tu-dresden.de].

=== Prüfungsleistung ===
'''Bachelor Informatik (PO 2025)'''
* {{ModuleLink|INF-25-Ba-BaSe}}: Komplexe Leistung (50 Stunden)

'''Bachelor Angewandte Informatik (PO 2025)'''
* {{ModuleLink|INF-25-Ba-BaSe}}: Komplexe Leistung (50 Stunden)

Als Komplexe Leistung ist eine Präsentation inkl. Fragerunde (25 Minuten) sowie eine schriftliche Zusammenfassung (ca. 5-8 Seiten) vorgesehen.

=== Kontakt ===

Bei organisatorischen Fragen senden Sie eine E-Mail an [mailto:studies_alg@mailbox.tu-dresden.de studies_alg@mailbox.tu-dresden.de].
|Description_EN=As part of this course, you will work on a topic related to current research projects of the chair. An overview is given on the [[Algebraische und logische Grundlagen der Informatik|page of the chair]] under the tab ''Active projects''.

The Bachelor Seminar is intended to be taken in combination with a bachelor's thesis. However, it can also be taken independently of a thesis.

=== Registration ===

If you want to take the Bachelor Seminar with our chair, please send an e-mail to [mailto:studies_alg@mailbox.tu-dresden.de studies_alg@mailbox.tu-dresden.de].

=== Examination ===
'''Bachelor Informatik (PO 2025)'''
* {{ModuleLink|INF-25-Ba-BaSe}}: ''Komplexe Leistung'' (50 hours)

'''Bachelor Angewandte Informatik (PO 2025)'''
* {{ModuleLink|INF-25-Ba-BaSe}}: ''Komplexe Leistung'' (50 hours)

The ''Komplexe Leistung'' (complex or multi-part examination) consists of a presentation incl. question-and-answet session (25 minutes) and a written report (approx. 5-8 pages).

=== Contact ===

In case of organizational questions, please send an e-mail to [mailto:studies_alg@mailbox.tu-dresden.de studies_alg@mailbox.tu-dresden.de].
}}

Analyse eines Forschungsthemas: Algebraische und logische Grundlagen der Informatik (WS2026)

2026-09-15T11:28:44Z

Sascha Klüppelholz:

{{Vorlesung
|Title=Analyse eines Forschungsthemas
|Title_EN=Analysis of a Research Topic
|Research group=Algebraische und logische Grundlagen der Informatik
|Lecturers=Christel Baier
|Language=DE,EN
|Term=WS
|Year=2026
|Module=INF-25-Ma-AFT
|SWSLecture=0
|SWSExercise=0
|SWSPractical=40h
|UmfangAlternativ=Projekte (40 Stunden)
|Description=Im Rahmen der Veranstaltung wird ein Thema mit Bezug zu den aktuellen Projekten des Lehrstuhls bearbeitet. Einen Überblick finden Sie auf der [[Algebraische und logische Grundlagen der Informatik|Seite des Lehrstuhls]] im Tab ''Aktive Projekte''.

''Analyse eines Forschungsthemas'' kann in Kombination mit einer Abschlussarbeit belegt werden oder unabhängig davon.

=== Anmeldung ===

Wenn Sie ''Analyse eines Forschungsthemas'' an unserem Lehrstuhl belegen möchten, senden Sie eine E-Mail an [mailto:studies_alg@mailbox.tu-dresden.de studies_alg@mailbox.tu-dresden.de].

=== Prüfungsleistung ===
'''Diplom Informatik (PO 2025)'''
* {{ModuleLink|INF-25-Ma-AFT}}: Komplexe Leistung (80 Stunden)

Als Komplexe Leistung ist eine Präsentation inkl. Fragerunde (30 Minuten) sowie eine schriftliche Zusammenfassung (ca. 10 Seiten) vorgesehen.

=== Kontakt ===

Bei organisatorischen Fragen senden Sie eine E-Mail an [mailto:studies_alg@mailbox.tu-dresden.de studies_alg@mailbox.tu-dresden.de].
|Description_EN=As part of this course, you will work on a topic related to current research projects of the chair. An overview is given on the [[Algebraische und logische Grundlagen der Informatik|page of the chair]] under the tab ''Active projects''.

''Analysis of a Research Topic'' can be attended in combination with a thesis at the chair or separately.

=== Registration ===

If you want to take ''Analysis of a Research Topic'' with our Chair, please send an e-mail to [mailto:studies_alg@mailbox.tu-dresden.de studies_alg@mailbox.tu-dresden.de].

=== Examination ===
'''Diplom Informatik (PO 2025)'''
* {{ModuleLink|INF-25-Ma-AFT}}: ''Komplexe Leistung'' (80 hours)

The ''Komplexe Leistung'' (complex or multi-part examination) consists of a presentation incl. question-and-answet session (30 minutes) and a written report (approx. 10 pages).

=== Contact ===

In case of organizational questions, please send an e-mail to [mailto:studies_alg@mailbox.tu-dresden.de studies_alg@mailbox.tu-dresden.de].
}}

Analyse eines Forschungsthemas: Algebraische und logische Grundlagen der Informatik (WS2026)

2026-09-15T11:23:59Z

Sascha Klüppelholz:

{{Vorlesung
|Title=Analyse eines Forschungsthemas
|Title_EN=Analysis of a Research Topic
|Research group=Algebraische und logische Grundlagen der Informatik
|Lecturers=Christel Baier
|Language=DE,EN
|Term=WS
|Year=2026
|Module=INF-25-Ma-AFT
|SWSLecture=0
|SWSExercise=0
|SWSPractical=40h
|UmfangAlternativ=Projekte (40 Stunden)
|Description=Im Rahmen der Veranstaltung wird ein Thema mit Bezug zu den aktuellen Projekten des Lehrstuhls bearbeitet. Einen Überblick finden Sie auf der [[Algebraische und logische Grundlagen der Informatik|Seite des Lehrstuhls]] im Tab ''Aktive Projekte''.

''Analyse eines Forschungsthemas'' kann in Kombination mit einer Abschlussarbeit belegt werden oder unabhängig davon.

=== Anmeldung ===

Wenn Sie ''Analyse eines Forschungsthemas'' an unserem Lehrstuhl belegen möchten, senden Sie eine E-Mail an [mailto:studies_alg@mailbox.tu-dresden.de studies_alg@mailbox.tu-dresden.de].

=== Prüfungsleistung ===
'''Diplom Informatik (PO 2025)'''
* {{ModuleLink|INF-25-Ma-AFT}}: Komplexe Leistung (80 Stunden)

Als Komplexe Leistung ist eine Präsentation (30 Minuten) sowie eine schriftliche Zusammenfassung (ca. 10 Seiten) vorgesehen.

=== Kontakt ===

Bei organisatorischen Fragen senden Sie eine E-Mail an [mailto:studies_alg@mailbox.tu-dresden.de studies_alg@mailbox.tu-dresden.de].
|Description_EN=As part of this course, you will work on a topic related to current research projects of the chair. An overview is given on the [[Algebraische und logische Grundlagen der Informatik|page of the chair]] under the tab ''Active projects''.

''Analysis of a Research Topic'' can be attended in combination with a thesis at the chair or separately.

=== Registration ===

If you want to take ''Analysis of a Research Topic'' with our Chair, please send an e-mail to [mailto:studies_alg@mailbox.tu-dresden.de studies_alg@mailbox.tu-dresden.de].

=== Examination ===
'''Diplom Informatik (PO 2025)'''
* {{ModuleLink|INF-25-Ma-AFT}}: ''Komplexe Leistung'' (80 hours)

The ''Komplexe Leistung'' (complex or multi-part examination) consists of a presentation (30 minutes) and a written report (approx. 10 pages).

=== Contact ===

In case of organizational questions, please send an e-mail to [mailto:studies_alg@mailbox.tu-dresden.de studies_alg@mailbox.tu-dresden.de].
}}

Seminar Selected Topics in Logic and Verification (WS2026)

2026-09-15T11:20:03Z

Sascha Klüppelholz:

{{Vorlesung
|Title=Seminar „Selected Topics in Logic and Verification“
|Title_EN=Seminar “Selected Topics in Logic and Verification”
|Research group=Algebraische und logische Grundlagen der Informatik
|Lecturers=Christel Baier; Jakob Piribauer
|Language=EN
|Term=WS
|Year=2026
|Module=CMS-SEM, INF-25-Ma-FTK-Sem
|SWSLecture=0
|SWSExercise=2
|SWSPractical=0
|Description=
{{MissingTranslation|Language=de}}

In this seminar, a selection of research papers from the areas of logic and verification will be discussed. These papers range from classical topics in logic and automata theory to recent research, in particular in formal verification and model checking.

Dieses Seminar richtet sich in erster Linie an Studierende der Studiengänge Master Computer Science und Diplom Informatik.

=== Anmeldung ===

Für die Teilnahme ist eine Registrierung via Opal bis zum 19. Oktober erforderlich. Wir verlinken zum Opal-Kurs, sobald dieser eingerichtet ist.

=== Voraussetzungen ===

Es werden fundierte Kenntnisse in Theoretischer Informatik und Logik vorausgesetzt.

=== Termine ===

Alle fristgerecht in Opal registrierten Teilnehmer:innen werden per E-Mail über die Einführungsveranstaltung informiert. Anschließend wird allen Teilnehmer:innen je ein Thema und ein Betreuer zugeteilt. Danach wird das weitere Vorgehen individuell mit dem Betreuer besprochen.

Die geforderten Vorträge werden als Blockveranstaltung im Zeitraum Januar–März 2027 stattfinden. Die genauen Termine werden zu einem späteren Zeitpunkt bekanntgegeben.

Die schriftliche Ausarbeitung ist bis zum 28. Februar 2027 einzureichen.

=== Prüfungsleistung ===

'''Master Computer Science (PO 2025)'''
* {{ModuleLink|INF-25-Ma-FTK-Sem}}: Komplexe Leistung (40 Stunden)

'''Diplom Informatik (PO 2025)'''
* {{ModuleLink|INF-25-Ma-FTK-Sem}}: Komplexe Leistung (40 Stunden)

Als Komplexe Leistung ist ein Tafelvortrag (45 Minuten) sowie eine Mündliche Fragerunde (10 Minuten) vorgesehen.

'''Master Computational Modeling and Simulation'''
* {{ModuleLink|CMS-SEM}}:  Präsentation und  Seminararbeit

=== Kontakt ===

Bei organisatorischen Fragen senden Sie eine E-Mail an [mailto:studies_alg@mailbox.tu-dresden.de studies_alg@mailbox.tu-dresden.de].

|Description_EN=In this seminar, a selection of research papers from the areas of logic and verification will be discussed. These papers range from classical topics in logic and automata theory to recent research, in particular in formal verification and model checking.

This seminar is mainly intended for students enrolled in the Master Computer Science and Diplom Informatik programs.

=== Registration ===

Registration via Opal is required until October 19. We will link to the Opal course once it is set up.

=== Prerequisites ===

For the seminar, profound knowledge in theoretical computer science and logics is presumed.

=== Dates ===

All participants registered in Opal by the due date will be notified about the initital meeting by e-mail. Each participant will then be assigned a topic and a supervisor. After that, further proceedings are arranged individually between each participant and their supervisor.

Presentations will be held between Januar and March 2027. The specific dates will be announced later.

The seminar paper (Seminararbeit) is due by February 28, 2027.

=== Examination ===

'''Master Computer Science (PO 2025)'''
* {{ModuleLink|INF-25-Ma-FTK-Sem}}: ''Komplexe Leistung'' (40 hours)

'''Diplom Informatik (PO 2025)'''
* {{ModuleLink|INF-25-Ma-FTK-Sem}}: ''Komplexe Leistung'' (40 hours)

The ''Komplexe Leistung'' (complex or multi-part examination) consists of a black board presentation (45 minutes) and an oral question-and-answer session (10 minutes).

'''Master Computational Modeling and Simulation'''
* {{ModuleLink|CMS-SEM}}:  presentation and  seminar paper

=== Contact ===

In case of organizational questions, please send an e-mail to [mailto:studies_alg@mailbox.tu-dresden.de studies_alg@mailbox.tu-dresden.de].

}}

Seminar Games and Graphs (WS2026)

2026-09-15T11:17:34Z

Sascha Klüppelholz:

{{Vorlesung
|Title=Seminar „Games and Graphs“
|Title_EN=Seminar “Games and Graphs”
|Research group=Algebraische und logische Grundlagen der Informatik
|Lecturers=Christel Baier; Jakob Piribauer
|Language=EN
|Term=WS
|Year=2026
|Module=INF-25-Ma-FTK-Sem
|SWSLecture=0
|SWSExercise=2
|SWSPractical=0
|Description=
{{MissingTranslation|Language=de}}

The topic of this seminar are infinite-duration games that are played between two or more players on a graph structure. Such games can be used to model a wide range of multi-agent systems or as theoretical tools in areas like logic and complexity theory. Hence, they play an important role in theoretical computer science, in particular in verification and synthesis.
The topics of the seminar address various forms of these games with different objectives and properties and algorithms to solve them.

Many of the topics can be found in the book [https://arxiv.org/abs/2305.10546 “Games on graphs: From logic and automata to algorithms”] edited by Fijalkow et al. (2025).

=== Anmeldung ===

Für die Teilnahme ist eine Registrierung via Opal bis zum 19. Oktober erforderlich. Wir verlinken zum Opal-Kurs, sobald dieser eingerichtet ist.

=== Voraussetzungen ===

Es werden fundierte Kenntnisse in Theoretischer Informatik und Logik vorausgesetzt.

=== Termine ===

Alle fristgerecht in Opal registrierten Teilnehmer:innen werden per E-Mail über die Einführungsveranstaltung informiert. Anschließend wird allen Teilnehmer:innen je ein Thema und ein Betreuer zugeteilt. Danach wird das weitere Vorgehen individuell mit dem Betreuer besprochen.

Die geforderten Vorträge werden als Blockveranstaltung im Zeitraum Januar-März 2027 stattfinden. Die genauen Termine werden zu einem späteren Zeitpunkt bekanntgegeben.

Die schriftliche Ausarbeitung ist bis zum 28. Februar 2027 einzureichen.

=== Prüfungsleistung ===

'''Master Computer Science (PO 2025)'''
* {{ModuleLink|INF-25-Ma-FTK-Sem}}: Komplexe Leistung (40 Stunden)

'''Diplom Informatik (PO 2025)'''
* {{ModuleLink|INF-25-Ma-FTK-Sem}}: Komplexe Leistung (40 Stunden)

Als Komplexe Leistung ist ein Folienvortrag (25 Minuten) sowie eine Mündliche Fragerunde (15 Minuten) vorgesehen.

=== Kontakt ===

Bei organisatorischen Fragen senden Sie eine E-Mail an [mailto:studies_alg@mailbox.tu-dresden.de studies_alg@mailbox.tu-dresden.de].

|Description_EN=The topic of this seminar are infinite-duration games that are played between two or more players on a graph structure. Such games can be used to model a wide range of multi-agent systems or as theoretical tools in areas like logic and complexity theory. Hence, they play an important role in theoretical computer science, in particular in verification and synthesis.
The topics of the seminar address various forms of these games with different objectives and properties and algorithms to solve them.

Many of the topics can be found in the book [https://arxiv.org/abs/2305.10546 “Games on graphs: From logic and automata to algorithms”] edited by Fijalkow et al. (2025).
=== Registration ===

Registration via Opal is required until October 19. We will link to the Opal course once it is set up.

=== Prerequisites ===

For the seminar, profound knowledge in theoretical computer science and logics is presumed.

=== Dates ===

All participants registered in Opal by the due date will be notified about the initial meeting by e-mail. Each participant will then be assigned a topic and a supervisor. After that, further proceedings are arranged individually between each participant and their supervisor.

Presentations will be held between January and March 2027. The specific dates will be announced later.

The seminar paper (Seminararbeit) is due by February 28, 2027.

=== Examination ===

'''Master Computer Science (PO 2025)'''
* {{ModuleLink|INF-25-Ma-FTK-Sem}}: ''Komplexe Leistung'' (40 hours)

'''Diplom Informatik (PO 2025)'''
* {{ModuleLink|INF-25-Ma-FTK-Sem}}: ''Komplexe Leistung'' (40 hours)

The ''Komplexe Leistung'' (complex or multi-part examination) consists of a presentation (25 minutes) and an oral question-and-answer session (15 minutes).

=== Contact ===

In case of organizational questions, please send an e-mail to [mailto:studies_alg@mailbox.tu-dresden.de studies_alg@mailbox.tu-dresden.de].

}}

Proseminar Theoretische Informatik (WS2026)

2026-09-15T11:13:26Z

Sascha Klüppelholz:

{{Vorlesung
|Title=Proseminar „Theoretische Informatik“
|Title_EN=Proseminar “Theoretische Informatik”
|Research group=Algebraische und logische Grundlagen der Informatik
|Lecturers=Sascha Klüppelholz
|Language=DE
|Term=WS
|Year=2026
|Module=INF-25-Ba-WIA
|SWSLecture=0
|SWSExercise=2
|SWSPractical=0
|Description=Das Thema des Proseminars ist die Analyse von Algorithmen. Es werden u. a. Algorithmen aus den Büchern [https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/ „Introduction to Algorithms“] von Cormen, Leiserson, Rivest und Stein, [https://www-cs-faculty.stanford.edu/~knuth/gkp.html „Concrete Mathematics“] von Graham, Knuth und Patashnik sowie [https://diestel-graph-theory.com/german/index.html „Graphentheorie“] von Diestel betrachtet.

=== Anmeldung ===

Für die Teilnahme ist eine Registrierung [https://bildungsportal.sachsen.de/opal/auth/RepositoryEntry/55848075267 via Opal] bis zum 12. Oktober erforderlich.

=== Voraussetzungen ===

Neben dem Interesse an theoretischer Informatik setzt das Proseminar solide Kenntnisse in den Gebieten Algorithmen und Datenstrukturen sowie Mathematik im Umfang der ersten zwei Studiensemester voraus.

=== Termine ===

Die Auftaktveranstaltung findet voraussichtlich am 15. oder 16. Oktober statt. Details werden allen fristgerecht in Opal eingeschriebenen Teilnehmer:inne per E-Mail mitgeteilt. Anschließend wird allen Teilnehmer:innen je ein Thema und ein Betreuer zugeteilt. Das weitere Vorgehen wird individuell mit dem Betreuer besprochen.

Die Vorträge werden als Blockveranstaltung im Zeitraum Januar–März 2027 stattfinden. Termine werden später bekanntgegeben.

Die schriftliche Ausarbeitung ist bis zum 14. März 2027 einzureichen.

=== Prüfungsleistung ===

'''Bachelor Informatik (PO 2025)'''
* {{ModuleLink|INF-25-Ba-WIA}}: Komplexe Leistung (60 Stunden)

'''Bachelor Angewandte Informatik (PO 2025)'''
* {{ModuleLink|INF-25-Ba-WIA}}: Komplexe Leistung (60 Stunden)

'''Diplom Informatik (PO 2025)'''
* {{ModuleLink|INF-25-Ba-WIA}}: Komplexe Leistung (60 Stunden)

Als Komplexe Leistung ist ein Folienvortrag (25 Minuten) sowie eine Mündliche Fragerunde (15 Minuten) vorgesehen.

=== Kontakt ===

Bei organisatorischen Fragen senden Sie eine E-Mail an [mailto:studies_alg@mailbox.tu-dresden.de studies_alg@mailbox.tu-dresden.de].

|Description_EN=
{{MissingTranslation|Language=en}}

Das Thema des Proseminars ist die Analyse von Algorithmen. Es werden u. a. Algorithmen aus den Büchern [https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/ „Introduction to Algorithms“] von Cormen, Leiserson, Rivest und Stein, [https://www-cs-faculty.stanford.edu/~knuth/gkp.html „Concrete Mathematics“] von Graham, Knuth und Patashnik sowie [https://diestel-graph-theory.com/german/index.html „Graphentheorie“] von Diestel betrachtet.

=== Registration ===

Registration [https://bildungsportal.sachsen.de/opal/auth/RepositoryEntry/55848075267 via Opal] is required until October 12.

=== Prerequisites ===

Besides an interest in theoretical computer science, the ''Proseminar'' requires solid foundations in algorithms and data structures as well as mathematics as covered in the first two semesters of the study program.

=== Dates ===

The initial meeting will be held on October 15 or 16. All participants registered in Opal by the due date will be notified about the details by e-mail. Each participant will then be assigned a topic and a supervisor. After that, further proceedings are arranged individually between each participant and their supervisor.

The required presentations will be held en bloc between January and March 2027. The specific dates will be announced later.

The written paper is due by March 14, 2027.

=== Examination ===

'''Bachelor Informatik (PO 2025)'''
* {{ModuleLink|INF-25-Ba-WIA}}: ''Komplexe Leistung'' (60 hours)

'''Bachelor Angewandte Informatik (PO 2025)'''
* {{ModuleLink|INF-25-Ba-WIA}}: ''Komplexe Leistung'' (60 hours)

'''Diplom Informatik (PO 2025)'''
* {{ModuleLink|INF-25-Ba-WIA}}: ''Komplexe Leistung'' (60 hours)

The ''Komplexe Leistung'' (complex or multi-part examination) consists of a presentation (25 minutes) and an oral question-and-answer session (15 minutes).

=== Contact ===

In case of organizational questions, please send an e-mail to [mailto:studies_alg@mailbox.tu-dresden.de studies_alg@mailbox.tu-dresden.de].

}}

Proseminar Binäre Entscheidungsgraphen (WS2026)

2026-09-15T11:11:49Z

Sascha Klüppelholz:

{{Vorlesung
|Title=Proseminar „Binäre Entscheidungsgraphen“
|Title_EN=Proseminar “Binäre Entscheidungsgraphen”
|Research group=Algebraische und logische Grundlagen der Informatik
|Lecturers=Sascha Klüppelholz
|Language=DE
|Term=WS
|Year=2026
|Module=INF-25-Ba-WIA
|SWSLecture=0
|SWSExercise=2
|SWSPractical=0
|Description=Das Thema des Proseminars sind Binäre Entscheidungsgraphen (engl. ''binary decision diagrams'', kurz BDDs). Diese wurden erstmals von Lee und Akers zur Darstellung von Schaltfunktionen vorgestellt. Heutzutage werden verschiedene Varianten von ''ordered BDDs'' in zahlreichen Verifikationswerkzeugen und Model Checkern wie z. B. nuSMV oder Prism als Datenstruktur zur effizienten Speicherung und Analyse von Systemmodellen eingesetzt.

Die individuell zu bearbeitenden Seminarthemen befassen sich mit den theoretischen Grundlagen binärer Entscheidungsgraphen. Insbesondere sollen die wichtigsten Operatoren und Algorithmen auf BDDs vorgestellt und hinsichtlich ihrer theoretischen Komplexität untersucht werden.

=== Anmeldung ===

Für die Teilnahme ist eine Registrierung [https://bildungsportal.sachsen.de/opal/auth/RepositoryEntry/55848075268 via Opal] bis zum 12. Oktober erforderlich.

=== Voraussetzungen ===

Neben dem Interesse an theoretischer Informatik setzt das Proseminar solide Kenntnisse in den Gebieten Algorithmen und Datenstrukturen sowie Mathematik im Umfang der ersten zwei Studiensemester voraus.

=== Termine ===

Die Auftaktveranstaltung findet voraussichtlich am 15. oder 16. Oktober statt. Details werden allen fristgerecht in Opal eingeschriebenen Teilnehmer:inne per E-Mail mitgeteilt. Anschließend wird allen Teilnehmer:innen je ein Thema und ein Betreuer zugeteilt. Das weitere Vorgehen wird individuell mit dem Betreuer besprochen.

Die Vorträge werden als Blockveranstaltung im Zeitraum Januar–März 2027 stattfinden. Termine werden später bekanntgegeben.

Die schriftliche Ausarbeitung ist bis zum 14. März 2027 einzureichen.

=== Prüfungsleistung ===

'''Bachelor Informatik (PO 2025)'''
* {{ModuleLink|INF-25-Ba-WIA}}: Komplexe Leistung (60 Stunden)

'''Bachelor Angewandte Informatik (PO 2025)'''
* {{ModuleLink|INF-25-Ba-WIA}}: Komplexe Leistung (60 Stunden)

'''Diplom Informatik (PO 2025)'''
* {{ModuleLink|INF-25-Ba-WIA}}: Komplexe Leistung (60 Stunden)

Als Komplexe Leistung ist ein Folienvortrag (25 Minuten) sowie eine Mündliche Fragerunde (15 Minuten) vorgesehen.

=== Kontakt ===

Bei organisatorischen Fragen senden Sie eine E-Mail an [mailto:studies_alg@mailbox.tu-dresden.de studies_alg@mailbox.tu-dresden.de].

|Description_EN=
{{MissingTranslation|Language=en}}

Das Thema des Proseminars sind Binäre Entscheidungsgraphen (engl. ''binary decision diagrams'', kurz BDDs). Diese wurden erstmals von Lee und Akers zur Darstellung von Schaltfunktionen vorgestellt. Heutzutage werden verschiedene Varianten von ''ordered BDDs'' in zahlreichen Verifikationswerkzeugen und Model Checkern wie z. B. nuSMV oder Prism als Datenstruktur zur effizienten Speicherung und Analyse von Systemmodellen eingesetzt.

Die individuell zu bearbeitenden Seminarthemen befassen sich mit den theoretischen Grundlagen binärer Entscheidungsgraphen. Insbesondere sollen die wichtigsten Operatoren und Algorithmen auf BDDs vorgestellt und hinsichtlich ihrer theoretischen Komplexität untersucht werden.

=== Registration ===

Registration [https://bildungsportal.sachsen.de/opal/auth/RepositoryEntry/55848075268 via Opal] is required until October 12.

=== Prerequisites ===

Besides an interest in theoretical computer science, the ''Proseminar'' requires solid foundations in algorithms and data structures as well as mathematics as covered in the first two semesters of the study program.

=== Dates ===

The initial meeting will be held on October 15 or 16. All participants registered in Opal by the due date will be notified about the details by e-mail. Each participant will then be assigned a topic and a supervisor. After that, further proceedings are arranged individually between each participant and their supervisor.

The required presentations will be held en bloc between January and March 2027. The specific dates will be announced later.

The written paper is due by March 14, 2027.

=== Examination ===

'''Bachelor Informatik (PO 2025)'''
* {{ModuleLink|INF-25-Ba-WIA}}: ''Komplexe Leistung'' (60 hours)

'''Bachelor Angewandte Informatik (PO 2025)'''
* {{ModuleLink|INF-25-Ba-WIA}}: ''Komplexe Leistung'' (60 hours)

'''Diplom Informatik (PO 2025)'''
* {{ModuleLink|INF-25-Ba-WIA}}: ''Komplexe Leistung'' (60 hours)

The ''Komplexe Leistung'' (complex or multi-part examination) consists of a presentation (25 minutes) and an oral question-and-answer session (15 minutes).

=== Contact ===

In case of organizational questions, please send an e-mail to [mailto:studies_alg@mailbox.tu-dresden.de studies_alg@mailbox.tu-dresden.de].

}}

Advanced Logics (SS2025)

2025-06-26T09:06:57Z

Sascha Klüppelholz:

{{Vorlesung
|Title=Lecture “Advanced Logics”
|Research group=Algebraische und logische Grundlagen der Informatik
|Lecturers=Christel Baier; Jakob Piribauer
|Language=EN
|Term=SS
|Year=2025
|Module=CMS-LM-ADV, CMS-LM-MOC, INF-B-510, INF-B-520, INF-BAS6, INF-VERT6, MCL-AL
|SWSLecture=4
|SWSExercise=2
|SWSPractical=0
|Description=The purpose of this course is to study several extensions of classical propositional, first-order and second-order logic. We will concentrate on aspects of mathematical logic that are relevant for computer science, such as expressiveness, game-theoretic characterizations, deductive calculi, decision and transformation algorithms and computational complexity.

This lecture is in English.

=== Registration ===

Registration [https://bildungsportal.sachsen.de/opal/auth/RepositoryEntry/48422027272?29 via Opal] is required until April 30.

=== Prerequisites ===

For the course, basic knowledge in algorithms, complexity theory, automata theory and logic is presumed.

=== Dates ===
* Lecture: Thursdays and Fridays, 9:20–10:50, APB E005 (starting April 10)
* Tutorial: Thursdays, 11:10–12:40, APB E005 (starting April 17)

=== Creditability ===
'''Bachelor Informatik'''
* {{ModuleLink|INF-B-510}}: oral exam (30 minutes)
* {{ModuleLink|INF-B-520}}: oral exam (30 minutes)

'''Master Informatik'''
* {{ModuleLink|INF-BAS6}}: exam according to module description
* {{ModuleLink|INF-VERT6}}: exam according to module description

'''Diplom Informatik'''
* {{ModuleLink|INF-BAS6}}: exam according to module description
* {{ModuleLink|INF-VERT6}}: exam according to module description

'''Master Computational Logic'''
* {{ModuleLink|MCL-AL}}: exam according to module description

'''Master Computational Modeling and Simulation'''
* {{ModuleLink|CMS-LM-MOC}}: oral exam (30 minutes)
* {{ModuleLink|CMS-LM-ADV}}: oral exam (30 minutes)

=== Oral Exams ===
Appointments for the oral examination are made via our secretary's office. Please contact [[Andrea Kühn]] via email.

=== Contact ===

In case of organisational questions, please contact [[Sascha Klüppelholz]].
}}

Advanced Logics (SS2025)

2025-06-26T09:05:43Z

Sascha Klüppelholz:

{{Vorlesung
|Title=Lecture “Advanced Logics”
|Research group=Algebraische und logische Grundlagen der Informatik
|Lecturers=Christel Baier; Jakob Piribauer
|Language=EN
|Term=SS
|Year=2025
|Module=CMS-LM-ADV, CMS-LM-MOC, INF-B-510, INF-B-520, INF-BAS6, INF-VERT6, MCL-AL
|SWSLecture=4
|SWSExercise=2
|SWSPractical=0
|Description=The purpose of this course is to study several extensions of classical propositional, first-order and second-order logic. We will concentrate on aspects of mathematical logic that are relevant for computer science, such as expressiveness, game-theoretic characterizations, deductive calculi, decision and transformation algorithms and computational complexity.

This lecture is in English.

=== Registration ===

Registration [https://bildungsportal.sachsen.de/opal/auth/RepositoryEntry/48422027272?29 via Opal] is required until April 30.

=== Prerequisites ===

For the course, basic knowledge in algorithms, complexity theory, automata theory and logic is presumed.

=== Dates ===
* Lecture: Thursdays and Fridays, 9:20–10:50, APB E005 (starting April 10)
* Tutorial: Thursdays, 11:10–12:40, APB E005 (starting April 17)

=== Creditability ===
'''Bachelor Informatik'''
* {{ModuleLink|INF-B-510}}: oral exam (30 minutes)
* {{ModuleLink|INF-B-520}}: oral exam (30 minutes)

'''Master Informatik'''
* {{ModuleLink|INF-BAS6}}: exam according to module description
* {{ModuleLink|INF-VERT6}}: exam according to module description

'''Diplom Informatik'''
* {{ModuleLink|INF-BAS6}}: exam according to module description
* {{ModuleLink|INF-VERT6}}: exam according to module description

'''Master Computational Logic'''
* {{ModuleLink|MCL-AL}}: exam according to module description

'''Master Computational Modeling and Simulation'''
* {{ModuleLink|CMS-LM-MOC}}: oral exam (30 minutes)
* {{ModuleLink|CMS-LM-ADV}}: oral exam (30 minutes)

=== Oral Exams ===
Appointments for the oral examination are made via our secretariat, please contact [[Andrea Kühn]] via email.

=== Contact ===

In case of organisational questions, please contact [[Sascha Klüppelholz]].
}}

Advanced Logics (SS2025)

2025-06-26T09:05:15Z

Sascha Klüppelholz:

{{Vorlesung
|Title=Lecture “Advanced Logics”
|Research group=Algebraische und logische Grundlagen der Informatik
|Lecturers=Christel Baier; Jakob Piribauer
|Language=EN
|Term=SS
|Year=2025
|Module=CMS-LM-ADV, CMS-LM-MOC, INF-B-510, INF-B-520, INF-BAS6, INF-VERT6, MCL-AL
|SWSLecture=4
|SWSExercise=2
|SWSPractical=0
|Description=The purpose of this course is to study several extensions of classical propositional, first-order and second-order logic. We will concentrate on aspects of mathematical logic that are relevant for computer science, such as expressiveness, game-theoretic characterizations, deductive calculi, decision and transformation algorithms and computational complexity.

This lecture is in English.

=== Registration ===

Registration [https://bildungsportal.sachsen.de/opal/auth/RepositoryEntry/48422027272?29 via Opal] is required until April 30.

=== Prerequisites ===

For the course, basic knowledge in algorithms, complexity theory, automata theory and logic is presumed.

=== Dates ===
* Lecture: Thursdays and Fridays, 9:20–10:50, APB E005 (starting April 10)
* Tutorial: Thursdays, 11:10–12:40, APB E005 (starting April 17)

=== Creditability ===
'''Bachelor Informatik'''
* {{ModuleLink|INF-B-510}}: oral exam (30 minutes)
* {{ModuleLink|INF-B-520}}: oral exam (30 minutes)

'''Master Informatik'''
* {{ModuleLink|INF-BAS6}}: exam according to module description
* {{ModuleLink|INF-VERT6}}: exam according to module description

'''Diplom Informatik'''
* {{ModuleLink|INF-BAS6}}: exam according to module description
* {{ModuleLink|INF-VERT6}}: exam according to module description

'''Master Computational Logic'''
* {{ModuleLink|MCL-AL}}: exam according to module description

'''Master Computational Modeling and Simulation'''
* {{ModuleLink|CMS-LM-MOC}}: oral exam (30 minutes)
* {{ModuleLink|CMS-LM-ADV}}: oral exam (30 minutes)

[Oral Exams]
Appointments for the oral examination are made via our secretariat, please contact [[Andrea Kühn]] via email.

=== Contact ===

In case of organisational questions, please contact [[Sascha Klüppelholz]].
}}

Datei:54c6152f-374a-4032-8833-a191c72cff41.jpeg

2025-02-19T09:55:35Z

Sascha Klüppelholz:

Algebraische und logische Grundlagen der Informatik

2023-08-23T10:37:25Z

Sascha Klüppelholz:

{{Forschungsgruppe
|Name EN=Verification and formal quantitative Analysis
|Kurzname=CB
|Beschreibung DE=Die Forschungsgruppe Verifikation und formale quantitative Analyse beschäftigt sich mit der Modellierung, Spezifikation and Verifikation reaktiver Systeme, der quantitativen Analyse stochastischer Systeme sowie Probabilistic Model Checking. Die weitere Forschung umfasst Koordinationssprachen, die Kompatibilität von Komponenten, temporale und modale Logiken, Automaten über unendlichen Strukturen, Spieltheorie und die Verifikation von Systemen mit unendlichem Zustandsraum.
|Beschreibung EN=The research of the Verification and formal quantitative Analysis group mainly focuses on modeling, specification and verification of reactive systems as well as quantitative analysis of stochastic systems and probabilistic model checking. Other areas of interest include coordination languages, compatibility of components, temporal and modal logics, automata over infinite structures, game theory and verification of infinite-state systems.
|Forschungsgruppenleiter=Christel Baier
|Bild=L-UdrXJ98F4.jpg
|Ehemalige Forschungsgruppe=0
}}

Datei:L-UdrXJ98F4.jpg

2023-08-23T10:37:18Z

Sascha Klüppelholz:

Theoretische Informatik und Logik (SS2021)

2021-04-08T14:49:21Z

Sascha Klüppelholz:

{{Vorlesung
|Title=Theoretische Informatik und Logik
|Research group=Verifikation und formale quantitative Analyse; Wissensbasierte Systeme
|Lecturers=Markus Krötzsch
|Tutors=Sascha Klüppelholz; Maximilian Marx
|Term=SS
|Year=2021
|Lecture series=Theoretische Informatik und Logik
|Module=INF-B290, 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 (WS2020)|Formale Systeme]] können hilfreich sein.

==Termine==

Im Sommersemester 2021 findet die Lehrveranstaltung rein digital statt. Die Vorlesungen werden als Videoreihe auf YouTube veröffentlicht. Links finden sich unter [https://youtube.com/channel/UC0mGxSeFgs3iCNPrypD4Z5g/ diesem YouTube-Kanal].

Zudem werden einige Live-Sessions zur Konsultation angeboten. Diese werden aufgrund der großen Teilnehmerzahl jeweils über '''Zoom''' abgehalten. Die Einwahldetails finden sich im Bereich ''Links'' der '''[https://tud.link/3ua5 OPAL-Seite dieser Lehrveranstaltung]'''. Ein Login oder die Installation spezieller Software ist nicht erforderlich. Konsultationstermine sind wie folgt:

* Montag, 02.04.2021, 2.DS (09:20–10:50): Einführung und Willkommen



==Übungen==

Die Einschreibungen in die Übungsgruppen erfolgt über [https://tud.link/fvgh OPAL]. 

'''Bitte beachten Sie''': Für die Teilnahme an einer Übungsgruppe ist die Einschreibung in dieser Gruppe verpflichtend. Studierenden ohne Einschreibung kann die Teilnahme an einer selbstgewählten Übung nicht garantiert werden. Übungsleiter sind berechtigt, nicht eingeschriebene Studierende bei Überfüllung aus der Übung zu verweisen.

===Übungsblätter===

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

== Unterlagen ==

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

Alle Foliensätze der Vorlesungen können entsprechend den Lizensbedingungen von [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/TheoLog2018, CC BY 3.0 DE

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

Besonderen Dank gilt allen [https://github.com/knowsys/TheoLog/graphs/contributors Contributors], die Anmerkungen und Verbesserungen beigetragen haben: [[Daniel Borchmann]], [[Maximilian Marx]], [https://github.com/freeDom- Dominik (freeDom-)], [https://github.com/CniKKoR CniKKoR], [https://github.com/marcusrossel Marcus Rossel], [https://github.com/SchermulyM SchermulyM], [https://github.com/tidenhub David Tiede], [[Francesco Kriegel]], [https://github.com/RobertPeine Robert Peine], [https://github.com/chlewe Christian Lewe], [https://github.com/hobbeshunter Martin Wudenka], [https://github.com/eknoes Sönke (eknoes)], [https://github.com/freakyblue Jonny Seitz], [https://github.com/NWuensche Niklas Wünsche], und [https://github.com/FlorianUlbrich Florian Ulbrich]. (Stand Juli 2018; Ergänzungen sind willkommen.)

== Kontakt ==

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

Formale Systeme (WS2017)

2018-07-30T14:40:55Z

Sascha Klüppelholz:

{{Vorlesung
|Title=Formale Systeme
|Research group=Wissensbasierte Systeme
|Lecturers=Markus Krötzsch;
|Tutors=Sascha Klüppelholz; Maximilian Marx
|Term=WS
|Year=2017
|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.

== Termine ==

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

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

'''Achtung:''' Am Montag, dem 23.10.2017, findet keine Vorlesung statt.

== WIEDERHOLUNGSKLAUSUR ==
Die '''Wiederholungsklausur''' findet am Dienstag den 7. August 2018 um 11:10 in Raum HSZ/0003 im Hörsaalzentrum (Bergstr. 64) statt (ohne Gewähr, Änderungen werden vom Prüfungsamt bekanntgegeben).

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

* 13:00-13:15 A-B
* 13:15-13:30 C-D
* 13:30-13:45 E-F
* 13:45-14:00 G-G
* 14:00-14:15 H-J
* 14:15-14:30 K-K
* 14:30-14:45 K-K
* 14:45-15:00 L-L
* 15:00-15:15 M-Q
* 15:15-15:30 R-R
* 15:30-15:45 S-S
* 15:45-16:00 S-S
* 16:00-16:15 T-V
* 16:15-16:30 W-Z

== KLAUSUR ==
Die '''Klausur''' findet am 13. Februar 2018 um 9:20 im Hörsaalzentrum (Bergstr.
64) statt (ohne Gewähr, Änderungen werden vom Prüfungsamt bekanntgegeben).
Bitte beachten Sie die Aufteilung auf zwei Hörsäle:

* Nachnamen beginnend mit A-M: HSZ/AUDI/H (Audimax)
* Nachnamen beginnend mit N-Z: HSZ/0003/H

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

* 06.02.2018, 14-16:00 Uhr, E007
* 06.02.2018, 16-18:00 Uhr, E006

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

== Übungen ==

Die Einschreibungen in die Übungsgruppen erfolgt über [https://jexam.inf.tu-dresden.de JExam]. Sollten Sie keinen Zugang zu JExam haben schreiben Sie bitte eine kurze [mailto:sascha.klueppelholz@tu-dresden.de?subject=FS-Einschreibung Email].

'''Bitte beachten Sie''':
* Für die Teilnahme an einer Übungsgruppe ist die Einschreibung in dieser Gruppe '''verpflichtend'''. Studierenden ohne Einschreibung kann die Teilnahme an einer selbstgewählten Übung nicht garantiert werden. Übungsleiter sind berechtigt, nicht eingeschriebene Studierende bei Überfüllung aus der Übung zu verweisen.

===Übungsblätter===

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

===Musterklausur===

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

== 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/FormaleSysteme

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/FS2017, 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-fs1718 Anmeldeformular] ausgefüllt werden. '''Fast alle Fragen sollten auf diesem Weg gestellt werden.'''

Kommentare und Bug Reports können gern auch direkt über die entsprechenden Seiten auf github gepostet werden: https://github.com/mkroetzsch/FormaleSysteme
Alternativ können Hinweise zu Tippfehlern in den Vorlesungsfolien auch an die Mailingliste 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.

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

Andere Scripte scheinen zurzeit nicht (mehr) online verfügbar zu sein. Hinweise zu weiteren Links auf sinnvolle Materialien sind willkommen.

== 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=2017/10/09
|DS=DS3
|Download=FS2017-Vorlesung-01-overlay.pdf, FS2017-Vorlesung-01-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Grammatiken und die Chomsky-Hierarchie
|Room=HSZ/0003
|Date=2017/10/12
|DS=DS4
|Download=FS2017-Vorlesung-02-overlay.pdf, FS2017-Vorlesung-02-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Endliche Automaten
|Room=HSZ/0002
|Date=2017/10/16
|DS=DS3
|Download=FS2017-Vorlesung-03-overlay.pdf, FS2017-Vorlesung-03-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Nichtdeterministische endliche Automaten
|Room=HSZ/0003
|Date=2017/10/19
|DS=DS4
|Download=FS2017-Vorlesung-04-overlay.pdf, FS2017-Vorlesung-04-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Abschlusseigenschaften regulärer Sprachen
|Room=HSZ/0003
|Date=2017/10/26
|DS=DS4
|Download=FS2017-Vorlesung-05-overlay.pdf, FS2017-Vorlesung-05-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Reguläre Ausdrücke
|Room=HSZ/0002
|Date=2017/10/30
|DS=DS3
|Download=FS2017-Vorlesung-06-overlay.pdf, FS2017-Vorlesung-06-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Reguläre Ausdrücke (2)
|Room=HSZ/0003
|Date=2017/11/02
|DS=DS4
|Download=FS2017-Vorlesung-07-overlay.pdf, FS2017-Vorlesung-07-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Minimale Automaten
|Room=HSZ/0002
|Date=2017/11/06
|DS=DS3
|Download=FS2017-Vorlesung-08-overlay.pdf, FS2017-Vorlesung-08-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Minimale Automaten (2)
|Room=HSZ/0003
|Date=2017/11/09
|DS=DS4
|Download=FS2017-Vorlesung-09-overlay.pdf, FS2017-Vorlesung-09-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Grenzen regulärer Sprachen/Berechnungsprobleme
|Room=HSZ/0002
|Date=2017/11/13
|DS=DS3
|Download=FS2017-Vorlesung-10-overlay.pdf, FS2017-Vorlesung-10-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Von regulären zu kontextfreien Sprachen
|Room=HSZ/0003
|Date=2017/11/16
|DS=DS4
|Download=FS2017-Vorlesung-11-overlay.pdf, FS2017-Vorlesung-11-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Das Wortproblem kontextfreier Sprachen
|Room=HSZ/0002
|Date=2017/11/20
|DS=DS3
|Download=FS2017-Vorlesung-12-overlay.pdf, FS2017-Vorlesung-12-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Das Pumping Lemma kontextfreier Sprachen
|Room=HSZ/0003
|Date=2017/11/23
|DS=DS4
|Download=FS2017-Vorlesung-13-overlay.pdf, FS2017-Vorlesung-13-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Abschlusseigenschaften kontextfreier Sprachen
|Room=HSZ/0002
|Date=2017/11/27
|DS=DS3
|Download=FS2017-Vorlesung-14-overlay.pdf, FS2017-Vorlesung-14-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Kellerautomaten
|Room=HSZ/0003
|Date=2017/11/30
|DS=DS4
|Download=FS2017-Vorlesung-15-overlay.pdf, FS2017-Vorlesung-15-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Kellerautomaten und Typ-2-Grammatiken
|Room=HSZ/0002
|Date=2017/12/04
|DS=DS3
|Download=FS2017-Vorlesung-16-overlay.pdf, FS2017-Vorlesung-16-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Deterministische Typ-2-Sprachen / Entscheidungsprobleme
|Room=HSZ/0003
|Date=2017/12/07
|DS=DS4
|Download=FS2017-Vorlesung-17-overlay.pdf, FS2017-Vorlesung-17-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Turingmaschinen
|Room=HSZ/0002
|Date=2017/12/11
|DS=DS3
|Download=FS2017-Vorlesung-18-overlay.pdf, FS2017-Vorlesung-18-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Repetitorium 1
|Room=HSZ/0003
|Date=2017/12/14
|DS=DS4
|Download=FS2017-Repetitorium-01.pdf,FS2017-Repetitorium-01-slides.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Nichtdeterminismus und Unentscheidbarkeit
|Room=HSZ/0002
|Date=2017/12/18
|DS=DS3
|Download=FS2017-Vorlesung-19-overlay.pdf, FS2017-Vorlesung-19-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Typ-0- und Typ-1-Sprachen
|Room=HSZ/0003
|Date=2018/01/04
|DS=DS4
|Download=FS2017-Vorlesung-20-overlay.pdf, FS2017-Vorlesung-20-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Aussagenlogik
|Room=HSZ/0002
|Date=2018/01/08
|DS=DS3
|Download=FS2017-Vorlesung-21-overlay.pdf, FS2017-Vorlesung-21-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Äquivalenz und Normalformen
|Room=HSZ/0003
|Date=2018/01/11
|DS=DS4
|Download=FS2017-Vorlesung-22-overlay.pdf, FS2017-Vorlesung-22-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Logisches Schließen
|Room=HSZ/0002
|Date=2018/01/15
|DS=DS3
|Download=FS2017-Vorlesung-23-overlay.pdf, FS2017-Vorlesung-23-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Horn-Logik / Komplexität
|Room=HSZ/0003
|Date=2018/01/18
|DS=DS4
|Download=FS2017-Vorlesung-24-overlay.pdf, FS2017-Vorlesung-24-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NP-Vollständigkeit
|Room=HSZ/0002
|Date=2018/01/22
|DS=DS3
|Download=FS2017-Vorlesung-25-overlay.pdf, FS2017-Vorlesung-25-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Repetitorium 2
|Room=HSZ/0003
|Date=2018/01/25
|DS=DS4
|Download=FS2017-Repetitorium-02.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Zusammenfassung und Ausblick
|Room=HSZ/0002
|Date=2018/01/29
|DS=DS3
|Download=FS2017-Vorlesung-26-overlay.pdf, FS2017-Vorlesung-26-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Besprechung Musterklausur
|Room=HSZ/0003
|Date=2018/02/01
|DS=DS4
|Download=FS2017-Musterklausur-slides.pdf,
}}

Theoretische Informatik und Logik (SS2018)

2018-07-30T13:48:41Z

Sascha Klüppelholz:

{{Vorlesung
|Title=Theoretische Informatik und Logik
|Research group=Verifikation und formale quantitative Analyse; Wissensbasierte Systeme
|Lecturers=Markus Krötzsch;
|Tutors=Sascha Klüppelholz; Maximilian Marx;
|Term=SS
|Year=2018
|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 (WS2017)|Formale Systeme]] können hilfreich sein.

==Termine==

Die erste Vorlesung findet am Mittwoch, den 09.04.2018, statt. Weitere Termine sind jeweils:
* Montag, 2.DS (09:20–10:50) HSZ/0004
* Freitag, 3.DS (11:10–12:40) HSZ/0004

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

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

== Lernräume ==

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

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

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

==Übungen==

Die Einschreibungen in die Übungsgruppen erfolgt über [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.

===Übungsblätter===

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

* [[Medium:TheoLog18-uebung-01.pdf|1. Übungsblatt]]
* [[Medium:TheoLog18-uebung-02.pdf|2. Übungsblatt]]
* [[Medium:TheoLog18-uebung-03.pdf|3. Übungsblatt]]
* [[Medium:TheoLog18-uebung-04.pdf|4. Übungsblatt]]
* [[Medium:TheoLog18-uebung-05.pdf|5. Übungsblatt]]
* [[Medium:TheoLog18-uebung-06.pdf|6. Übungsblatt]], [[Medium:TheoLog18-uebung-06-03-musterloesung.pdf|Musterlösung für Aufgabe 3]]
* [[Medium:TheoLog18-uebung-07.pdf|7. Übungsblatt]]
* [[Medium:TheoLog18-repetitorium-01.pdf|1. Repetitorium]], [[Medium:Theolog2018-Repetitorium-01-Folien.pdf|Folien]]
* [[Medium:TheoLog18-uebung-08.pdf|8. Übungsblatt]]
* [[Medium:TheoLog18-uebung-09.pdf|9. Übungsblatt]]
* [[Medium:TheoLog18-uebung-10.pdf|10. Übungsblatt]]
* [[Medium:TheoLog18-uebung-11.pdf|11. Übungsblatt]]
* [[Medium:TheoLog18-uebung-12.pdf|12. Übungsblatt]]
* [[Medium:TheoLog18-repetitorium-02.pdf|2. Repetitorium]], [[Medium:Theolog2018-Repetitorium-02-Folien.pdf|Folien]]

===Musterklausur===

Als Prüfungsvorbereitung wird eine [[Medium:ThL18-musterklausur.pdf|Musterklausur]] zur Verfügung gestellt. Diese wird am 20.07. in der Vorlesungszeit vorgerechnet werden. [[Medium:Theolog2018-musterklausur-folien.pdf|Folien]]

== Unterlagen ==

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

Alle Foliensätze der Vorlesungen können entsprechend den Lizensbedingungen von [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/TheoLog2018, CC BY 3.0 DE

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

Besonderen Dank gilt allen [https://github.com/knowsys/TheoLog/graphs/contributors Contributors], die Anmerkungen und Verbesserungen beigetragen haben: [[Daniel Borchmann]], [[Maximilian Marx]], [https://github.com/freeDom- Dominik (freeDom-)], [https://github.com/CniKKoR CniKKoR], [https://github.com/marcusrossel Marcus Rossel], [https://github.com/SchermulyM SchermulyM], [https://github.com/tidenhub David Tiede], [[Francesco Kriegel]], [https://github.com/RobertPeine Robert Peine], [https://github.com/chlewe Christian Lewe], [https://github.com/hobbeshunter Martin Wudenka], [https://github.com/eknoes Sönke (eknoes)], [https://github.com/freakyblue Jonny Seitz], [https://github.com/NWuensche Niklas Wünsche], und [https://github.com/FlorianUlbrich Florian Ulbrich]. (Stand Juli 2018; Ergänzungen sind willkommen.)

== Kontakt ==

Fragen können am einfachsten in Vorlesung oder Übungsgruppe gestellt werden oder per Email an das Organisationsteam (siehe Links oben). Kommentare und Bug Reports können gern auch direkt über die entsprechenden Seiten auf github gepostet werden: https://github.com/knowsys/TheoLog
|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=2018/04/09
|DS=DS2
|Download=TheoLog2018-Vorlesung-01-overlay.pdf, TheoLog2018-Vorlesung-01-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Berechenbarkeit und Unentscheidbarkeit
|Room=HSZ/0004
|Date=2018/04/13
|DS=DS3
|Download=TheoLog2018-Vorlesung-02-overlay.pdf, TheoLog2018-Vorlesung-02-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=WHILE und LOOP
|Room=HSZ/0004
|Date=2018/04/16
|DS=DS2
|Download=TheoLog2018-Vorlesung-03-overlay.pdf, TheoLog2018-Vorlesung-03-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Das Halteproblem und Reduktionen
|Room=HSZ/0004
|Date=2018/04/20
|DS=DS3
|Download=TheoLog2018-Vorlesung-04-overlay.pdf, TheoLog2018-Vorlesung-04-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Satz von Rice/Postsches Korrespondenzproblem
|Room=HSZ/0004
|Date=2018/04/27
|DS=DS3
|Download=TheoLog2018-Vorlesung-05-overlay.pdf, TheoLog2018-Vorlesung-05-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Unentscheidbare Probleme formaler Sprachen
|Room=HSZ/0004
|Date=2018/04/30
|DS=DS2
|Download=TheoLog2018-Vorlesung-06-overlay.pdf, TheoLog2018-Vorlesung-06-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Einführung in die Komplexitätstheorie
|Room=HSZ/0004
|Date=2018/05/04
|DS=DS3
|Download=TheoLog2018-Vorlesung-07-overlay.pdf, TheoLog2018-Vorlesung-07-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Komplexitätsklassen / Effizienz / Reduktionen
|Room=HSZ/0004
|Date=2018/05/07
|DS=DS2
|Download=TheoLog2018-Vorlesung-08-overlay.pdf, TheoLog2018-Vorlesung-08-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NP und NP-Vollständigkeit
|Room=HSZ/0004
|Date=2018/05/11
|DS=DS3
|Download=TheoLog2018-Vorlesung-09-overlay.pdf, TheoLog2018-Vorlesung-09-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NP (2)
|Room=HSZ/0004
|Date=2018/05/14
|DS=DS2
|Download=TheoLog2018-Vorlesung-10-overlay.pdf, TheoLog2018-Vorlesung-10-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NL und PSpace
|Room=HSZ/0004
|Date=2018/05/18
|DS=DS3
|Download=TheoLog2018-Vorlesung-11-overlay.pdf, TheoLog2018-Vorlesung-11-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=PSpace-Vollständigkeit
|Room=HSZ/0004
|Date=2018/05/28
|DS=DS2
|Download=TheoLog2018-Vorlesung-12-overlay.pdf, TheoLog2018-Vorlesung-12-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Prädikatenlogik: Syntax und Semantik
|Room=HSZ/0004
|Date=2018/06/01
|DS=DS3
|Download=TheoLog2018-Vorlesung-13-overlay.pdf, TheoLog2018-Vorlesung-13-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Modelltheorie und logisches Schließen
|Room=HSZ/0004
|Date=2018/06/04
|DS=DS2
|Download=TheoLog2018-Vorlesung-14-overlay.pdf, TheoLog2018-Vorlesung-14-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Logisches Schließen
|Room=HSZ/0004
|Date=2018/06/08
|DS=DS3
|Download=TheoLog2018-Vorlesung-15-overlay.pdf, TheoLog2018-Vorlesung-15-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Logisches Schließen (2)
|Room=HSZ/0004
|Date=2018/06/11
|DS=DS2
|Download=TheoLog2018-Vorlesung-16-overlay.pdf, TheoLog2018-Vorlesung-16-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Repetitorium 1
|Room=HSZ/0004
|Date=2018/06/15
|DS=DS3
|Download=Theolog2018-Repetitorium-01-Folien.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Funktionen und Normalformen
|Room=HSZ/0004
|Date=2018/06/18
|DS=DS2
|Download=TheoLog2018-Vorlesung-17-overlay.pdf, TheoLog2018-Vorlesung-17-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Unifikation
|Room=HSZ/0004
|Date=2018/06/22
|DS=DS3
|Download=TheoLog2018-Vorlesung-18-overlay.pdf, TheoLog2018-Vorlesung-18-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Resolution
|Room=HSZ/0004
|Date=2018/06/25
|DS=DS2
|Download=TheoLog2018-Vorlesung-19-overlay.pdf, TheoLog2018-Vorlesung-19-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Resolution (2)
|Room=HSZ/0004
|Date=2018/06/29
|DS=DS3
|Download=TheoLog2018-Vorlesung-20-overlay.pdf, TheoLog2018-Vorlesung-20-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Endliche Modelle und Datenbanken
|Room=HSZ/0004
|Date=2018/07/02
|DS=DS2
|Download=TheoLog2018-Vorlesung-21-overlay.pdf, TheoLog2018-Vorlesung-21-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Datalog
|Room=HSZ/0004
|Date=2018/07/06
|DS=DS3
|Download=TheoLog2018-Vorlesung-22-overlay.pdf, TheoLog2018-Vorlesung-22-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Gödels Unvollständigkeitssätze
|Room=HSZ/0004
|Date=2018/07/09
|DS=DS2
|Download=TheoLog2018-Vorlesung-23-overlay.pdf, TheoLog2018-Vorlesung-23-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Gödel, Turing und der ganze Rest
|Room=HSZ/0004
|Date=2018/07/13
|DS=DS3
|Download=TheoLog2018-Vorlesung-24-overlay.pdf, TheoLog2018-Vorlesung-24-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Repetitorium 2
|Room=HSZ/0004
|Date=2018/07/16
|DS=DS2
|Download=TheoLog18-repetitorium-02-slides.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Besprechung Musterklausur
|Room=HSZ/0004
|Date=2018/07/20
|DS=DS3
|Download=Theolog2018-musterklausur-folien.pdf,
}}

Theoretische Informatik und Logik (SS2018)

2018-07-20T11:28:11Z

Sascha Klüppelholz:

{{Vorlesung
|Title=Theoretische Informatik und Logik
|Research group=Verifikation und formale quantitative Analyse; Wissensbasierte Systeme
|Lecturers=Markus Krötzsch;
|Tutors=Sascha Klüppelholz; Maximilian Marx;
|Term=SS
|Year=2018
|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 (WS2017)|Formale Systeme]] können hilfreich sein.

==Termine==

Die erste Vorlesung findet am Mittwoch, den 09.04.2018, statt. Weitere Termine sind jeweils:
* Montag, 2.DS (09:20–10:50) HSZ/0004
* Freitag, 3.DS (11:10–12:40) HSZ/0004

== Lernräume ==

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

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

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

==Übungen==

Die Einschreibungen in die Übungsgruppen erfolgt über [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.

===Übungsblätter===

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

* [[Medium:TheoLog18-uebung-01.pdf|1. Übungsblatt]]
* [[Medium:TheoLog18-uebung-02.pdf|2. Übungsblatt]]
* [[Medium:TheoLog18-uebung-03.pdf|3. Übungsblatt]]
* [[Medium:TheoLog18-uebung-04.pdf|4. Übungsblatt]]
* [[Medium:TheoLog18-uebung-05.pdf|5. Übungsblatt]]
* [[Medium:TheoLog18-uebung-06.pdf|6. Übungsblatt]], [[Medium:TheoLog18-uebung-06-03-musterloesung.pdf|Musterlösung für Aufgabe 3]]
* [[Medium:TheoLog18-uebung-07.pdf|7. Übungsblatt]]
* [[Medium:TheoLog18-repetitorium-01.pdf|1. Repetitorium]], [[Medium:Theolog2018-Repetitorium-01-Folien.pdf|Folien]]
* [[Medium:TheoLog18-uebung-08.pdf|8. Übungsblatt]]
* [[Medium:TheoLog18-uebung-09.pdf|9. Übungsblatt]]
* [[Medium:TheoLog18-uebung-10.pdf|10. Übungsblatt]]
* [[Medium:TheoLog18-uebung-11.pdf|11. Übungsblatt]]
* [[Medium:TheoLog18-uebung-12.pdf|12. Übungsblatt]]
* [[Medium:TheoLog18-repetitorium-02.pdf|2. Repetitorium]], [[Medium:Theolog2018-Repetitorium-02-Folien.pdf|Folien]]

===Musterklausur===

Als Prüfungsvorbereitung wird eine [[Medium:ThL18-musterklausur.pdf|Musterklausur]] zur Verfügung gestellt. Diese wird am 20.07. in der Vorlesungszeit vorgerechnet werden. [[Medium:Theolog2018-musterklausur-folien.pdf|Folien]]

== Unterlagen ==

Die vollständigen Foliensätze zur Vorlesung erscheinen spätestens kurz nach der Vorlesung online (siehe ''Termine und Unterlagen''). Weiterführende Literatur ist unter ''Literatur'' angegeben. Die Quellen der Vorlesungsfolien sind auf github verfügbar: https://github.com/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/TheoLog2018, CC BY 3.0 DE

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

== Kontakt ==

Fragen können am einfachsten in Vorlesung oder Übungsgruppe gestellt werden oder per Email an das Organisationsteam (siehe Links oben). Kommentare und Bug Reports können gern auch direkt über die entsprechenden Seiten auf github gepostet werden: https://github.com/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=2018/04/09
|DS=DS2
|Download=TheoLog2018-Vorlesung-01-overlay.pdf, TheoLog2018-Vorlesung-01-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Berechenbarkeit und Unentscheidbarkeit
|Room=HSZ/0004
|Date=2018/04/13
|DS=DS3
|Download=TheoLog2018-Vorlesung-02-overlay.pdf, TheoLog2018-Vorlesung-02-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=WHILE und LOOP
|Room=HSZ/0004
|Date=2018/04/16
|DS=DS2
|Download=TheoLog2018-Vorlesung-03-overlay.pdf, TheoLog2018-Vorlesung-03-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Das Halteproblem und Reduktionen
|Room=HSZ/0004
|Date=2018/04/20
|DS=DS3
|Download=TheoLog2018-Vorlesung-04-overlay.pdf, TheoLog2018-Vorlesung-04-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Satz von Rice/Postsches Korrespondenzproblem
|Room=HSZ/0004
|Date=2018/04/27
|DS=DS3
|Download=TheoLog2018-Vorlesung-05-overlay.pdf, TheoLog2018-Vorlesung-05-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Unentscheidbare Probleme formaler Sprachen
|Room=HSZ/0004
|Date=2018/04/30
|DS=DS2
|Download=TheoLog2018-Vorlesung-06-overlay.pdf, TheoLog2018-Vorlesung-06-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Einführung in die Komplexitätstheorie
|Room=HSZ/0004
|Date=2018/05/04
|DS=DS3
|Download=TheoLog2018-Vorlesung-07-overlay.pdf, TheoLog2018-Vorlesung-07-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Komplexitätsklassen / Effizienz / Reduktionen
|Room=HSZ/0004
|Date=2018/05/07
|DS=DS2
|Download=TheoLog2018-Vorlesung-08-overlay.pdf, TheoLog2018-Vorlesung-08-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NP und NP-Vollständigkeit
|Room=HSZ/0004
|Date=2018/05/11
|DS=DS3
|Download=TheoLog2018-Vorlesung-09-overlay.pdf, TheoLog2018-Vorlesung-09-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NP (2)
|Room=HSZ/0004
|Date=2018/05/14
|DS=DS2
|Download=TheoLog2018-Vorlesung-10-overlay.pdf, TheoLog2018-Vorlesung-10-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NL und PSpace
|Room=HSZ/0004
|Date=2018/05/18
|DS=DS3
|Download=TheoLog2018-Vorlesung-11-overlay.pdf, TheoLog2018-Vorlesung-11-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=PSpace-Vollständigkeit
|Room=HSZ/0004
|Date=2018/05/28
|DS=DS2
|Download=TheoLog2018-Vorlesung-12-overlay.pdf, TheoLog2018-Vorlesung-12-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Prädikatenlogik: Syntax und Semantik
|Room=HSZ/0004
|Date=2018/06/01
|DS=DS3
|Download=TheoLog2018-Vorlesung-13-overlay.pdf, TheoLog2018-Vorlesung-13-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Modelltheorie und logisches Schließen
|Room=HSZ/0004
|Date=2018/06/04
|DS=DS2
|Download=TheoLog2018-Vorlesung-14-overlay.pdf, TheoLog2018-Vorlesung-14-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Logisches Schließen
|Room=HSZ/0004
|Date=2018/06/08
|DS=DS3
|Download=TheoLog2018-Vorlesung-15-overlay.pdf, TheoLog2018-Vorlesung-15-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Logisches Schließen (2)
|Room=HSZ/0004
|Date=2018/06/11
|DS=DS2
|Download=TheoLog2018-Vorlesung-16-overlay.pdf, TheoLog2018-Vorlesung-16-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Repetitorium 1
|Room=HSZ/0004
|Date=2018/06/15
|DS=DS3
|Download=Theolog2018-Repetitorium-01-Folien.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Funktionen und Normalformen
|Room=HSZ/0004
|Date=2018/06/18
|DS=DS2
|Download=TheoLog2018-Vorlesung-17-overlay.pdf, TheoLog2018-Vorlesung-17-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Unifikation
|Room=HSZ/0004
|Date=2018/06/22
|DS=DS3
|Download=TheoLog2018-Vorlesung-18-overlay.pdf, TheoLog2018-Vorlesung-18-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Resolution
|Room=HSZ/0004
|Date=2018/06/25
|DS=DS2
|Download=TheoLog2018-Vorlesung-19-overlay.pdf, TheoLog2018-Vorlesung-19-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Resolution (2)
|Room=HSZ/0004
|Date=2018/06/29
|DS=DS3
|Download=TheoLog2018-Vorlesung-20-overlay.pdf, TheoLog2018-Vorlesung-20-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Endliche Modelle und Datenbanken
|Room=HSZ/0004
|Date=2018/07/02
|DS=DS2
|Download=TheoLog2018-Vorlesung-21-overlay.pdf, TheoLog2018-Vorlesung-21-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Datalog
|Room=HSZ/0004
|Date=2018/07/06
|DS=DS3
|Download=TheoLog2018-Vorlesung-22-overlay.pdf, TheoLog2018-Vorlesung-22-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Gödels Unvollständigkeitssätze
|Room=HSZ/0004
|Date=2018/07/09
|DS=DS2
|Download=TheoLog2018-Vorlesung-23-overlay.pdf, TheoLog2018-Vorlesung-23-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Gödel, Turing und der ganze Rest
|Room=HSZ/0004
|Date=2018/07/13
|DS=DS3
|Download=TheoLog2018-Vorlesung-24-overlay.pdf, TheoLog2018-Vorlesung-24-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Repetitorium 2
|Room=HSZ/0004
|Date=2018/07/16
|DS=DS2
|Download=TheoLog18-repetitorium-02-slides.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Besprechung Musterklausur
|Room=HSZ/0004
|Date=2018/07/20
|DS=DS3
}}

Datei:Theolog2018-musterklausur-folien.pdf

2018-07-20T11:28:01Z

Sascha Klüppelholz:

Datei:Theolog2018-Repetitorium-02-Folien.pdf

2018-07-20T11:27:25Z

Sascha Klüppelholz:

Theoretische Informatik und Logik (SS2018)

2018-07-20T11:25:18Z

Sascha Klüppelholz:

{{Vorlesung
|Title=Theoretische Informatik und Logik
|Research group=Verifikation und formale quantitative Analyse; Wissensbasierte Systeme
|Lecturers=Markus Krötzsch;
|Tutors=Sascha Klüppelholz; Maximilian Marx;
|Term=SS
|Year=2018
|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 (WS2017)|Formale Systeme]] können hilfreich sein.

==Termine==

Die erste Vorlesung findet am Mittwoch, den 09.04.2018, statt. Weitere Termine sind jeweils:
* Montag, 2.DS (09:20–10:50) HSZ/0004
* Freitag, 3.DS (11:10–12:40) HSZ/0004

== Lernräume ==

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

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

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

==Übungen==

Die Einschreibungen in die Übungsgruppen erfolgt über [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.

===Übungsblätter===

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

* [[Medium:TheoLog18-uebung-01.pdf|1. Übungsblatt]]
* [[Medium:TheoLog18-uebung-02.pdf|2. Übungsblatt]]
* [[Medium:TheoLog18-uebung-03.pdf|3. Übungsblatt]]
* [[Medium:TheoLog18-uebung-04.pdf|4. Übungsblatt]]
* [[Medium:TheoLog18-uebung-05.pdf|5. Übungsblatt]]
* [[Medium:TheoLog18-uebung-06.pdf|6. Übungsblatt]], [[Medium:TheoLog18-uebung-06-03-musterloesung.pdf|Musterlösung für Aufgabe 3]]
* [[Medium:TheoLog18-uebung-07.pdf|7. Übungsblatt]]
* [[Medium:TheoLog18-repetitorium-01.pdf|1. Repetitorium]], [[Medium:Theolog2018-Repetitorium-01-Folien.pdf|Folien]],
* [[Medium:TheoLog18-uebung-08.pdf|8. Übungsblatt]]
* [[Medium:TheoLog18-uebung-09.pdf|9. Übungsblatt]]
* [[Medium:TheoLog18-uebung-10.pdf|10. Übungsblatt]]
* [[Medium:TheoLog18-uebung-11.pdf|11. Übungsblatt]]
* [[Medium:TheoLog18-uebung-12.pdf|12. Übungsblatt]]
* [[Medium:TheoLog18-repetitorium-02.pdf|2. Repetitorium]]

===Musterklausur===

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

== 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/TheoLog2018, CC BY 3.0 DE

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

== Kontakt ==

Fragen können am einfachsten in Vorlesung oder Übungsgruppe gestellt werden oder per Email an das Organisationsteam (siehe Links oben). Kommentare und Bug Reports können gern auch direkt über die entsprechenden Seiten auf github gepostet werden: https://github.com/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=2018/04/09
|DS=DS2
|Download=TheoLog2018-Vorlesung-01-overlay.pdf, TheoLog2018-Vorlesung-01-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Berechenbarkeit und Unentscheidbarkeit
|Room=HSZ/0004
|Date=2018/04/13
|DS=DS3
|Download=TheoLog2018-Vorlesung-02-overlay.pdf, TheoLog2018-Vorlesung-02-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=WHILE und LOOP
|Room=HSZ/0004
|Date=2018/04/16
|DS=DS2
|Download=TheoLog2018-Vorlesung-03-overlay.pdf, TheoLog2018-Vorlesung-03-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Das Halteproblem und Reduktionen
|Room=HSZ/0004
|Date=2018/04/20
|DS=DS3
|Download=TheoLog2018-Vorlesung-04-overlay.pdf, TheoLog2018-Vorlesung-04-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Satz von Rice/Postsches Korrespondenzproblem
|Room=HSZ/0004
|Date=2018/04/27
|DS=DS3
|Download=TheoLog2018-Vorlesung-05-overlay.pdf, TheoLog2018-Vorlesung-05-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Unentscheidbare Probleme formaler Sprachen
|Room=HSZ/0004
|Date=2018/04/30
|DS=DS2
|Download=TheoLog2018-Vorlesung-06-overlay.pdf, TheoLog2018-Vorlesung-06-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Einführung in die Komplexitätstheorie
|Room=HSZ/0004
|Date=2018/05/04
|DS=DS3
|Download=TheoLog2018-Vorlesung-07-overlay.pdf, TheoLog2018-Vorlesung-07-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Komplexitätsklassen / Effizienz / Reduktionen
|Room=HSZ/0004
|Date=2018/05/07
|DS=DS2
|Download=TheoLog2018-Vorlesung-08-overlay.pdf, TheoLog2018-Vorlesung-08-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NP und NP-Vollständigkeit
|Room=HSZ/0004
|Date=2018/05/11
|DS=DS3
|Download=TheoLog2018-Vorlesung-09-overlay.pdf, TheoLog2018-Vorlesung-09-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NP (2)
|Room=HSZ/0004
|Date=2018/05/14
|DS=DS2
|Download=TheoLog2018-Vorlesung-10-overlay.pdf, TheoLog2018-Vorlesung-10-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NL und PSpace
|Room=HSZ/0004
|Date=2018/05/18
|DS=DS3
|Download=TheoLog2018-Vorlesung-11-overlay.pdf, TheoLog2018-Vorlesung-11-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=PSpace-Vollständigkeit
|Room=HSZ/0004
|Date=2018/05/28
|DS=DS2
|Download=TheoLog2018-Vorlesung-12-overlay.pdf, TheoLog2018-Vorlesung-12-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Prädikatenlogik: Syntax und Semantik
|Room=HSZ/0004
|Date=2018/06/01
|DS=DS3
|Download=TheoLog2018-Vorlesung-13-overlay.pdf, TheoLog2018-Vorlesung-13-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Modelltheorie und logisches Schließen
|Room=HSZ/0004
|Date=2018/06/04
|DS=DS2
|Download=TheoLog2018-Vorlesung-14-overlay.pdf, TheoLog2018-Vorlesung-14-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Logisches Schließen
|Room=HSZ/0004
|Date=2018/06/08
|DS=DS3
|Download=TheoLog2018-Vorlesung-15-overlay.pdf, TheoLog2018-Vorlesung-15-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Logisches Schließen (2)
|Room=HSZ/0004
|Date=2018/06/11
|DS=DS2
|Download=TheoLog2018-Vorlesung-16-overlay.pdf, TheoLog2018-Vorlesung-16-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Repetitorium 1
|Room=HSZ/0004
|Date=2018/06/15
|DS=DS3
|Download=Theolog2018-Repetitorium-01-Folien.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Funktionen und Normalformen
|Room=HSZ/0004
|Date=2018/06/18
|DS=DS2
|Download=TheoLog2018-Vorlesung-17-overlay.pdf, TheoLog2018-Vorlesung-17-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Unifikation
|Room=HSZ/0004
|Date=2018/06/22
|DS=DS3
|Download=TheoLog2018-Vorlesung-18-overlay.pdf, TheoLog2018-Vorlesung-18-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Resolution
|Room=HSZ/0004
|Date=2018/06/25
|DS=DS2
|Download=TheoLog2018-Vorlesung-19-overlay.pdf, TheoLog2018-Vorlesung-19-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Resolution (2)
|Room=HSZ/0004
|Date=2018/06/29
|DS=DS3
|Download=TheoLog2018-Vorlesung-20-overlay.pdf, TheoLog2018-Vorlesung-20-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Endliche Modelle und Datenbanken
|Room=HSZ/0004
|Date=2018/07/02
|DS=DS2
|Download=TheoLog2018-Vorlesung-21-overlay.pdf, TheoLog2018-Vorlesung-21-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Datalog
|Room=HSZ/0004
|Date=2018/07/06
|DS=DS3
|Download=TheoLog2018-Vorlesung-22-overlay.pdf, TheoLog2018-Vorlesung-22-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Gödels Unvollständigkeitssätze
|Room=HSZ/0004
|Date=2018/07/09
|DS=DS2
|Download=TheoLog2018-Vorlesung-23-overlay.pdf, TheoLog2018-Vorlesung-23-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Gödel, Turing und der ganze Rest
|Room=HSZ/0004
|Date=2018/07/13
|DS=DS3
|Download=TheoLog2018-Vorlesung-24-overlay.pdf, TheoLog2018-Vorlesung-24-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Repetitorium 2
|Room=HSZ/0004
|Date=2018/07/16
|DS=DS2
|Download=TheoLog18-repetitorium-02-slides.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Besprechung Musterklausur
|Room=HSZ/0004
|Date=2018/07/20
|DS=DS3
}}

Theoretische Informatik und Logik (SS2018)

2018-07-16T09:10:14Z

Sascha Klüppelholz:

{{Vorlesung
|Title=Theoretische Informatik und Logik
|Research group=Verifikation und formale quantitative Analyse; Wissensbasierte Systeme
|Lecturers=Markus Krötzsch;
|Tutors=Sascha Klüppelholz; Maximilian Marx;
|Term=SS
|Year=2018
|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 (WS2017)|Formale Systeme]] können hilfreich sein.

==Termine==

Die erste Vorlesung findet am Mittwoch, den 09.04.2018, statt. Weitere Termine sind jeweils:
* Montag, 2.DS (09:20–10:50) HSZ/0004
* Freitag, 3.DS (11:10–12:40) HSZ/0004

== Lernräume ==

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

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

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

==Übungen==

Die Einschreibungen in die Übungsgruppen erfolgt über [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.

===Übungsblätter===

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

* [[Medium:TheoLog18-uebung-01.pdf|1. Übungsblatt]]
* [[Medium:TheoLog18-uebung-02.pdf|2. Übungsblatt]]
* [[Medium:TheoLog18-uebung-03.pdf|3. Übungsblatt]]
* [[Medium:TheoLog18-uebung-04.pdf|4. Übungsblatt]]
* [[Medium:TheoLog18-uebung-05.pdf|5. Übungsblatt]]
* [[Medium:TheoLog18-uebung-06.pdf|6. Übungsblatt]], [[Medium:TheoLog18-uebung-06-03-musterloesung.pdf|Musterlösung für Aufgabe 3]]
* [[Medium:TheoLog18-uebung-07.pdf|7. Übungsblatt]]
* [[Medium:TheoLog18-repetitorium-01.pdf|1. Repetitorium]]
* [[Medium:TheoLog18-uebung-08.pdf|8. Übungsblatt]]
* [[Medium:TheoLog18-uebung-09.pdf|9. Übungsblatt]]
* [[Medium:TheoLog18-uebung-10.pdf|10. Übungsblatt]]
* [[Medium:TheoLog18-uebung-11.pdf|11. Übungsblatt]]
* [[Medium:TheoLog18-uebung-12.pdf|12. Übungsblatt]]
* [[Medium:TheoLog18-repetitorium-02.pdf|2. Repetitorium]], [[Medium:TheoLog18-repetitorium-02-slides.pdf|Foliensatz]],

===Musterklausur===

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

== 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/TheoLog2018, CC BY 3.0 DE

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

== Kontakt ==

Fragen können am einfachsten in Vorlesung oder Übungsgruppe gestellt werden oder per Email an das Organisationsteam (siehe Links oben). Kommentare und Bug Reports können gern auch direkt über die entsprechenden Seiten auf github gepostet werden: https://github.com/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=2018/04/09
|DS=DS2
|Download=TheoLog2018-Vorlesung-01-overlay.pdf, TheoLog2018-Vorlesung-01-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Berechenbarkeit und Unentscheidbarkeit
|Room=HSZ/0004
|Date=2018/04/13
|DS=DS3
|Download=TheoLog2018-Vorlesung-02-overlay.pdf, TheoLog2018-Vorlesung-02-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=WHILE und LOOP
|Room=HSZ/0004
|Date=2018/04/16
|DS=DS2
|Download=TheoLog2018-Vorlesung-03-overlay.pdf, TheoLog2018-Vorlesung-03-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Das Halteproblem und Reduktionen
|Room=HSZ/0004
|Date=2018/04/20
|DS=DS3
|Download=TheoLog2018-Vorlesung-04-overlay.pdf, TheoLog2018-Vorlesung-04-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Satz von Rice/Postsches Korrespondenzproblem
|Room=HSZ/0004
|Date=2018/04/27
|DS=DS3
|Download=TheoLog2018-Vorlesung-05-overlay.pdf, TheoLog2018-Vorlesung-05-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Unentscheidbare Probleme formaler Sprachen
|Room=HSZ/0004
|Date=2018/04/30
|DS=DS2
|Download=TheoLog2018-Vorlesung-06-overlay.pdf, TheoLog2018-Vorlesung-06-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Einführung in die Komplexitätstheorie
|Room=HSZ/0004
|Date=2018/05/04
|DS=DS3
|Download=TheoLog2018-Vorlesung-07-overlay.pdf, TheoLog2018-Vorlesung-07-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Komplexitätsklassen / Effizienz / Reduktionen
|Room=HSZ/0004
|Date=2018/05/07
|DS=DS2
|Download=TheoLog2018-Vorlesung-08-overlay.pdf, TheoLog2018-Vorlesung-08-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NP und NP-Vollständigkeit
|Room=HSZ/0004
|Date=2018/05/11
|DS=DS3
|Download=TheoLog2018-Vorlesung-09-overlay.pdf, TheoLog2018-Vorlesung-09-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NP (2)
|Room=HSZ/0004
|Date=2018/05/14
|DS=DS2
|Download=TheoLog2018-Vorlesung-10-overlay.pdf, TheoLog2018-Vorlesung-10-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NL und PSpace
|Room=HSZ/0004
|Date=2018/05/18
|DS=DS3
|Download=TheoLog2018-Vorlesung-11-overlay.pdf, TheoLog2018-Vorlesung-11-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=PSpace-Vollständigkeit
|Room=HSZ/0004
|Date=2018/05/28
|DS=DS2
|Download=TheoLog2018-Vorlesung-12-overlay.pdf, TheoLog2018-Vorlesung-12-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Prädikatenlogik: Syntax und Semantik
|Room=HSZ/0004
|Date=2018/06/01
|DS=DS3
|Download=TheoLog2018-Vorlesung-13-overlay.pdf, TheoLog2018-Vorlesung-13-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Modelltheorie und logisches Schließen
|Room=HSZ/0004
|Date=2018/06/04
|DS=DS2
|Download=TheoLog2018-Vorlesung-14-overlay.pdf, TheoLog2018-Vorlesung-14-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Logisches Schließen
|Room=HSZ/0004
|Date=2018/06/08
|DS=DS3
|Download=TheoLog2018-Vorlesung-15-overlay.pdf, TheoLog2018-Vorlesung-15-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Logisches Schließen (2)
|Room=HSZ/0004
|Date=2018/06/11
|DS=DS2
|Download=TheoLog2018-Vorlesung-16-overlay.pdf, TheoLog2018-Vorlesung-16-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Repetitorium 1
|Room=HSZ/0004
|Date=2018/06/15
|DS=DS3
|Download=Theolog2018-Repetitorium-01-Folien.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Funktionen und Normalformen
|Room=HSZ/0004
|Date=2018/06/18
|DS=DS2
|Download=TheoLog2018-Vorlesung-17-overlay.pdf, TheoLog2018-Vorlesung-17-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Unifikation
|Room=HSZ/0004
|Date=2018/06/22
|DS=DS3
|Download=TheoLog2018-Vorlesung-18-overlay.pdf, TheoLog2018-Vorlesung-18-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Resolution
|Room=HSZ/0004
|Date=2018/06/25
|DS=DS2
|Download=TheoLog2018-Vorlesung-19-overlay.pdf, TheoLog2018-Vorlesung-19-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Resolution (2)
|Room=HSZ/0004
|Date=2018/06/29
|DS=DS3
|Download=TheoLog2018-Vorlesung-20-overlay.pdf, TheoLog2018-Vorlesung-20-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Endliche Modelle und Datenbanken
|Room=HSZ/0004
|Date=2018/07/02
|DS=DS2
|Download=TheoLog2018-Vorlesung-21-overlay.pdf, TheoLog2018-Vorlesung-21-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Datalog
|Room=HSZ/0004
|Date=2018/07/06
|DS=DS3
|Download=TheoLog2018-Vorlesung-22-overlay.pdf, TheoLog2018-Vorlesung-22-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Gödels Unvollständigkeitssätze
|Room=HSZ/0004
|Date=2018/07/09
|DS=DS2
|Download=TheoLog2018-Vorlesung-23-overlay.pdf, TheoLog2018-Vorlesung-23-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Gödel, Turing und der ganze Rest
|Room=HSZ/0004
|Date=2018/07/13
|DS=DS3
|Download=TheoLog2018-Vorlesung-24-overlay.pdf, TheoLog2018-Vorlesung-24-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Repetitorium 2
|Room=HSZ/0004
|Date=2018/07/16
|DS=DS2
|Download=TheoLog18-repetitorium-02.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Besprechung Musterklausur
|Room=HSZ/0004
|Date=2018/07/20
|DS=DS3
|Download=ThL18-musterklausur.pdf,
}}

Datei:TheoLog18-repetitorium-02-slides.pdf

2018-07-16T09:09:56Z

Sascha Klüppelholz:

Datei:TheoLog18-repetitorium-02.pdf

2018-07-13T08:10:20Z

Sascha Klüppelholz:

Theoretische Informatik und Logik (SS2018)

2018-07-13T08:09:47Z

Sascha Klüppelholz:

{{Vorlesung
|Title=Theoretische Informatik und Logik
|Research group=Verifikation und formale quantitative Analyse; Wissensbasierte Systeme
|Lecturers=Markus Krötzsch;
|Tutors=Sascha Klüppelholz; Maximilian Marx;
|Term=SS
|Year=2018
|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 (WS2017)|Formale Systeme]] können hilfreich sein.

==Termine==

Die erste Vorlesung findet am Mittwoch, den 09.04.2018, statt. Weitere Termine sind jeweils:
* Montag, 2.DS (09:20–10:50) HSZ/0004
* Freitag, 3.DS (11:10–12:40) HSZ/0004

== Lernräume ==

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

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

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

==Übungen==

Die Einschreibungen in die Übungsgruppen erfolgt über [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.

===Übungsblätter===

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

* [[Medium:TheoLog18-uebung-01.pdf|1. Übungsblatt]]
* [[Medium:TheoLog18-uebung-02.pdf|2. Übungsblatt]]
* [[Medium:TheoLog18-uebung-03.pdf|3. Übungsblatt]]
* [[Medium:TheoLog18-uebung-04.pdf|4. Übungsblatt]]
* [[Medium:TheoLog18-uebung-05.pdf|5. Übungsblatt]]
* [[Medium:TheoLog18-uebung-06.pdf|6. Übungsblatt]], [[Medium:TheoLog18-uebung-06-03-musterloesung.pdf|Musterlösung für Aufgabe 3]]
* [[Medium:TheoLog18-uebung-07.pdf|7. Übungsblatt]]
* [[Medium:TheoLog18-repetitorium-01.pdf|1. Repetitorium]]
* [[Medium:TheoLog18-uebung-08.pdf|8. Übungsblatt]]
* [[Medium:TheoLog18-uebung-09.pdf|9. Übungsblatt]]
* [[Medium:TheoLog18-uebung-10.pdf|10. Übungsblatt]]
* [[Medium:TheoLog18-uebung-11.pdf|11. Übungsblatt]]
* [[Medium:TheoLog18-uebung-12.pdf|12. Übungsblatt]]
* [[Medium:TheoLog18-repetitorium-02.pdf|2. Repetitorium]]

===Musterklausur===

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

== 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/TheoLog2018, CC BY 3.0 DE

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

== Kontakt ==

Fragen können am einfachsten in Vorlesung oder Übungsgruppe gestellt werden oder per Email an das Organisationsteam (siehe Links oben). Kommentare und Bug Reports können gern auch direkt über die entsprechenden Seiten auf github gepostet werden: https://github.com/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=2018/04/09
|DS=DS2
|Download=TheoLog2018-Vorlesung-01-overlay.pdf, TheoLog2018-Vorlesung-01-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Berechenbarkeit und Unentscheidbarkeit
|Room=HSZ/0004
|Date=2018/04/13
|DS=DS3
|Download=TheoLog2018-Vorlesung-02-overlay.pdf, TheoLog2018-Vorlesung-02-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=WHILE und LOOP
|Room=HSZ/0004
|Date=2018/04/16
|DS=DS2
|Download=TheoLog2018-Vorlesung-03-overlay.pdf, TheoLog2018-Vorlesung-03-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Das Halteproblem und Reduktionen
|Room=HSZ/0004
|Date=2018/04/20
|DS=DS3
|Download=TheoLog2018-Vorlesung-04-overlay.pdf, TheoLog2018-Vorlesung-04-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Satz von Rice/Postsches Korrespondenzproblem
|Room=HSZ/0004
|Date=2018/04/27
|DS=DS3
|Download=TheoLog2018-Vorlesung-05-overlay.pdf, TheoLog2018-Vorlesung-05-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Unentscheidbare Probleme formaler Sprachen
|Room=HSZ/0004
|Date=2018/04/30
|DS=DS2
|Download=TheoLog2018-Vorlesung-06-overlay.pdf, TheoLog2018-Vorlesung-06-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Einführung in die Komplexitätstheorie
|Room=HSZ/0004
|Date=2018/05/04
|DS=DS3
|Download=TheoLog2018-Vorlesung-07-overlay.pdf, TheoLog2018-Vorlesung-07-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Komplexitätsklassen / Effizienz / Reduktionen
|Room=HSZ/0004
|Date=2018/05/07
|DS=DS2
|Download=TheoLog2018-Vorlesung-08-overlay.pdf, TheoLog2018-Vorlesung-08-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NP und NP-Vollständigkeit
|Room=HSZ/0004
|Date=2018/05/11
|DS=DS3
|Download=TheoLog2018-Vorlesung-09-overlay.pdf, TheoLog2018-Vorlesung-09-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NP (2)
|Room=HSZ/0004
|Date=2018/05/14
|DS=DS2
|Download=TheoLog2018-Vorlesung-10-overlay.pdf, TheoLog2018-Vorlesung-10-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NL und PSpace
|Room=HSZ/0004
|Date=2018/05/18
|DS=DS3
|Download=TheoLog2018-Vorlesung-11-overlay.pdf, TheoLog2018-Vorlesung-11-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=PSpace-Vollständigkeit
|Room=HSZ/0004
|Date=2018/05/28
|DS=DS2
|Download=TheoLog2018-Vorlesung-12-overlay.pdf, TheoLog2018-Vorlesung-12-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Prädikatenlogik: Syntax und Semantik
|Room=HSZ/0004
|Date=2018/06/01
|DS=DS3
|Download=TheoLog2018-Vorlesung-13-overlay.pdf, TheoLog2018-Vorlesung-13-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Modelltheorie und logisches Schließen
|Room=HSZ/0004
|Date=2018/06/04
|DS=DS2
|Download=TheoLog2018-Vorlesung-14-overlay.pdf, TheoLog2018-Vorlesung-14-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Logisches Schließen
|Room=HSZ/0004
|Date=2018/06/08
|DS=DS3
|Download=TheoLog2018-Vorlesung-15-overlay.pdf, TheoLog2018-Vorlesung-15-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Logisches Schließen (2)
|Room=HSZ/0004
|Date=2018/06/11
|DS=DS2
|Download=TheoLog2018-Vorlesung-16-overlay.pdf, TheoLog2018-Vorlesung-16-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Repetitorium 1
|Room=HSZ/0004
|Date=2018/06/15
|DS=DS3
|Download=Theolog2018-Repetitorium-01-Folien.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Funktionen und Normalformen
|Room=HSZ/0004
|Date=2018/06/18
|DS=DS2
|Download=TheoLog2018-Vorlesung-17-overlay.pdf, TheoLog2018-Vorlesung-17-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Unifikation
|Room=HSZ/0004
|Date=2018/06/22
|DS=DS3
|Download=TheoLog2018-Vorlesung-18-overlay.pdf, TheoLog2018-Vorlesung-18-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Resolution
|Room=HSZ/0004
|Date=2018/06/25
|DS=DS2
|Download=TheoLog2018-Vorlesung-19-overlay.pdf, TheoLog2018-Vorlesung-19-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Resolution (2)
|Room=HSZ/0004
|Date=2018/06/29
|DS=DS3
|Download=TheoLog2018-Vorlesung-20-overlay.pdf, TheoLog2018-Vorlesung-20-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Endliche Modelle und Datenbanken
|Room=HSZ/0004
|Date=2018/07/02
|DS=DS2
|Download=TheoLog2018-Vorlesung-21-overlay.pdf, TheoLog2018-Vorlesung-21-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Datalog
|Room=HSZ/0004
|Date=2018/07/06
|DS=DS3
|Download=TheoLog2018-Vorlesung-22-overlay.pdf, TheoLog2018-Vorlesung-22-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Gödels Unvollständigkeitssätze
|Room=HSZ/0004
|Date=2018/07/09
|DS=DS2
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Gödel, Turing und der ganze Rest
|Room=HSZ/0004
|Date=2018/07/13
|DS=DS3
}}

Theoretische Informatik und Logik (SS2018)

2018-07-10T08:12:24Z

Sascha Klüppelholz:

{{Vorlesung
|Title=Theoretische Informatik und Logik
|Research group=Verifikation und formale quantitative Analyse; Wissensbasierte Systeme
|Lecturers=Markus Krötzsch;
|Tutors=Sascha Klüppelholz; Maximilian Marx;
|Term=SS
|Year=2018
|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 (WS2017)|Formale Systeme]] können hilfreich sein.

==Termine==

Die erste Vorlesung findet am Mittwoch, den 09.04.2018, statt. Weitere Termine sind jeweils:
* Montag, 2.DS (09:20–10:50) HSZ/0004
* Freitag, 3.DS (11:10–12:40) HSZ/0004

== Lernräume ==

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

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

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

==Übungen==

Die Einschreibungen in die Übungsgruppen erfolgt über [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.

===Übungsblätter===

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

* [[Medium:TheoLog18-uebung-01.pdf|1. Übungsblatt]]
* [[Medium:TheoLog18-uebung-02.pdf|2. Übungsblatt]]
* [[Medium:TheoLog18-uebung-03.pdf|3. Übungsblatt]]
* [[Medium:TheoLog18-uebung-04.pdf|4. Übungsblatt]]
* [[Medium:TheoLog18-uebung-05.pdf|5. Übungsblatt]]
* [[Medium:TheoLog18-uebung-06.pdf|6. Übungsblatt]], [[Medium:TheoLog18-uebung-06-03-musterloesung.pdf|Musterlösung für Aufgabe 3]]
* [[Medium:TheoLog18-uebung-07.pdf|7. Übungsblatt]]
* [[Medium:TheoLog18-repetitorium-01.pdf|1. Repetitorium]]
* [[Medium:TheoLog18-uebung-08.pdf|8. Übungsblatt]]
* [[Medium:TheoLog18-uebung-09.pdf|9. Übungsblatt]]
* [[Medium:TheoLog18-uebung-10.pdf|10. Übungsblatt]]
* [[Medium:TheoLog18-uebung-11.pdf|11. Übungsblatt]]
* [[Medium:TheoLog18-uebung-12.pdf|12. Ü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/TheoLog2018, CC BY 3.0 DE

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

== Kontakt ==

Fragen können am einfachsten in Vorlesung oder Übungsgruppe gestellt werden oder per Email an das Organisationsteam (siehe Links oben). Kommentare und Bug Reports können gern auch direkt über die entsprechenden Seiten auf github gepostet werden: https://github.com/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=2018/04/09
|DS=DS2
|Download=TheoLog2018-Vorlesung-01-overlay.pdf, TheoLog2018-Vorlesung-01-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Berechenbarkeit und Unentscheidbarkeit
|Room=HSZ/0004
|Date=2018/04/13
|DS=DS3
|Download=TheoLog2018-Vorlesung-02-overlay.pdf, TheoLog2018-Vorlesung-02-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=WHILE und LOOP
|Room=HSZ/0004
|Date=2018/04/16
|DS=DS2
|Download=TheoLog2018-Vorlesung-03-overlay.pdf, TheoLog2018-Vorlesung-03-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Das Halteproblem und Reduktionen
|Room=HSZ/0004
|Date=2018/04/20
|DS=DS3
|Download=TheoLog2018-Vorlesung-04-overlay.pdf, TheoLog2018-Vorlesung-04-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Satz von Rice/Postsches Korrespondenzproblem
|Room=HSZ/0004
|Date=2018/04/27
|DS=DS3
|Download=TheoLog2018-Vorlesung-05-overlay.pdf, TheoLog2018-Vorlesung-05-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Unentscheidbare Probleme formaler Sprachen
|Room=HSZ/0004
|Date=2018/04/30
|DS=DS2
|Download=TheoLog2018-Vorlesung-06-overlay.pdf, TheoLog2018-Vorlesung-06-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Einführung in die Komplexitätstheorie
|Room=HSZ/0004
|Date=2018/05/04
|DS=DS3
|Download=TheoLog2018-Vorlesung-07-overlay.pdf, TheoLog2018-Vorlesung-07-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Komplexitätsklassen / Effizienz / Reduktionen
|Room=HSZ/0004
|Date=2018/05/07
|DS=DS2
|Download=TheoLog2018-Vorlesung-08-overlay.pdf, TheoLog2018-Vorlesung-08-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NP und NP-Vollständigkeit
|Room=HSZ/0004
|Date=2018/05/11
|DS=DS3
|Download=TheoLog2018-Vorlesung-09-overlay.pdf, TheoLog2018-Vorlesung-09-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NP (2)
|Room=HSZ/0004
|Date=2018/05/14
|DS=DS2
|Download=TheoLog2018-Vorlesung-10-overlay.pdf, TheoLog2018-Vorlesung-10-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NL und PSpace
|Room=HSZ/0004
|Date=2018/05/18
|DS=DS3
|Download=TheoLog2018-Vorlesung-11-overlay.pdf, TheoLog2018-Vorlesung-11-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=PSpace-Vollständigkeit
|Room=HSZ/0004
|Date=2018/05/28
|DS=DS2
|Download=TheoLog2018-Vorlesung-12-overlay.pdf, TheoLog2018-Vorlesung-12-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Prädikatenlogik: Syntax und Semantik
|Room=HSZ/0004
|Date=2018/06/01
|DS=DS3
|Download=TheoLog2018-Vorlesung-13-overlay.pdf, TheoLog2018-Vorlesung-13-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Modelltheorie und logisches Schließen
|Room=HSZ/0004
|Date=2018/06/04
|DS=DS2
|Download=TheoLog2018-Vorlesung-14-overlay.pdf, TheoLog2018-Vorlesung-14-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Logisches Schließen
|Room=HSZ/0004
|Date=2018/06/08
|DS=DS3
|Download=TheoLog2018-Vorlesung-15-overlay.pdf, TheoLog2018-Vorlesung-15-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Logisches Schließen (2)
|Room=HSZ/0004
|Date=2018/06/11
|DS=DS2
|Download=TheoLog2018-Vorlesung-16-overlay.pdf, TheoLog2018-Vorlesung-16-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Repetitorium 1
|Room=HSZ/0004
|Date=2018/06/15
|DS=DS3
|Download=Theolog2018-Repetitorium-01-Folien.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Funktionen und Normalformen
|Room=HSZ/0004
|Date=2018/06/18
|DS=DS2
|Download=TheoLog2018-Vorlesung-17-overlay.pdf, TheoLog2018-Vorlesung-17-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Unifikation
|Room=HSZ/0004
|Date=2018/06/22
|DS=DS3
|Download=TheoLog2018-Vorlesung-18-overlay.pdf, TheoLog2018-Vorlesung-18-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Resolution
|Room=HSZ/0004
|Date=2018/06/25
|DS=DS2
|Download=TheoLog2018-Vorlesung-19-overlay.pdf, TheoLog2018-Vorlesung-19-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Resolution (2)
|Room=HSZ/0004
|Date=2018/06/29
|DS=DS3
|Download=TheoLog2018-Vorlesung-20-overlay.pdf, TheoLog2018-Vorlesung-20-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Endliche Modelle und Datenbanken
|Room=HSZ/0004
|Date=2018/07/02
|DS=DS2
|Download=TheoLog2018-Vorlesung-21-overlay.pdf, TheoLog2018-Vorlesung-21-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Datalog
|Room=HSZ/0004
|Date=2018/07/06
|DS=DS3
|Download=TheoLog2018-Vorlesung-22-overlay.pdf, TheoLog2018-Vorlesung-22-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Gödels Unvollständigkeitssätze
|Room=HSZ/0004
|Date=2018/07/09
|DS=DS2
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Gödel, Turing und der ganze Rest
|Room=HSZ/0004
|Date=2018/07/13
|DS=DS3
}}

Datei:TheoLog18-uebung-12.pdf

2018-07-04T11:35:45Z

Sascha Klüppelholz:

Theoretische Informatik und Logik (SS2018)

2018-07-04T11:35:23Z

Sascha Klüppelholz:

{{Vorlesung
|Title=Theoretische Informatik und Logik
|Research group=Verifikation und formale quantitative Analyse; Wissensbasierte Systeme
|Lecturers=Markus Krötzsch;
|Tutors=Sascha Klüppelholz; Maximilian Marx;
|Term=SS
|Year=2018
|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 (WS2017)|Formale Systeme]] können hilfreich sein.

==Termine==

Die erste Vorlesung findet am Mittwoch, den 09.04.2018, statt. Weitere Termine sind jeweils:
* Montag, 2.DS (09:20–10:50) HSZ/0004
* Freitag, 3.DS (11:10–12:40) HSZ/0004

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

===Übungsblätter===

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

* [[Medium:TheoLog18-uebung-01.pdf|1. Übungsblatt]]
* [[Medium:TheoLog18-uebung-02.pdf|2. Übungsblatt]]
* [[Medium:TheoLog18-uebung-03.pdf|3. Übungsblatt]]
* [[Medium:TheoLog18-uebung-04.pdf|4. Übungsblatt]]
* [[Medium:TheoLog18-uebung-05.pdf|5. Übungsblatt]]
* [[Medium:TheoLog18-uebung-06.pdf|6. Übungsblatt]], [[Medium:TheoLog18-uebung-06-03-musterloesung.pdf|Musterlösung für Aufgabe 3]]
* [[Medium:TheoLog18-uebung-07.pdf|7. Übungsblatt]]
* [[Medium:TheoLog18-repetitorium-01.pdf|1. Repetitorium]]
* [[Medium:TheoLog18-uebung-08.pdf|8. Übungsblatt]]
* [[Medium:TheoLog18-uebung-09.pdf|9. Übungsblatt]]
* [[Medium:TheoLog18-uebung-10.pdf|10. Übungsblatt]]
* [[Medium:TheoLog18-uebung-11.pdf|11. Übungsblatt]]
* [[Medium:TheoLog18-uebung-12.pdf|12. Ü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/TheoLog2018, CC BY 3.0 DE

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

== Kontakt ==

Fragen können am einfachsten in Vorlesung oder Übungsgruppe gestellt werden oder per Email an das Organisationsteam (siehe Links oben). Kommentare und Bug Reports können gern auch direkt über die entsprechenden Seiten auf github gepostet werden: https://github.com/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=2018/04/09
|DS=DS2
|Download=TheoLog2018-Vorlesung-01-overlay.pdf, TheoLog2018-Vorlesung-01-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Berechenbarkeit und Unentscheidbarkeit
|Room=HSZ/0004
|Date=2018/04/13
|DS=DS3
|Download=TheoLog2018-Vorlesung-02-overlay.pdf, TheoLog2018-Vorlesung-02-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=WHILE und LOOP
|Room=HSZ/0004
|Date=2018/04/16
|DS=DS2
|Download=TheoLog2018-Vorlesung-03-overlay.pdf, TheoLog2018-Vorlesung-03-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Das Halteproblem und Reduktionen
|Room=HSZ/0004
|Date=2018/04/20
|DS=DS3
|Download=TheoLog2018-Vorlesung-04-overlay.pdf, TheoLog2018-Vorlesung-04-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Satz von Rice/Postsches Korrespondenzproblem
|Room=HSZ/0004
|Date=2018/04/27
|DS=DS3
|Download=TheoLog2018-Vorlesung-05-overlay.pdf, TheoLog2018-Vorlesung-05-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Unentscheidbare Probleme formaler Sprachen
|Room=HSZ/0004
|Date=2018/04/30
|DS=DS2
|Download=TheoLog2018-Vorlesung-06-overlay.pdf, TheoLog2018-Vorlesung-06-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Einführung in die Komplexitätstheorie
|Room=HSZ/0004
|Date=2018/05/04
|DS=DS3
|Download=TheoLog2018-Vorlesung-07-overlay.pdf, TheoLog2018-Vorlesung-07-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Komplexitätsklassen / Effizienz / Reduktionen
|Room=HSZ/0004
|Date=2018/05/07
|DS=DS2
|Download=TheoLog2018-Vorlesung-08-overlay.pdf, TheoLog2018-Vorlesung-08-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NP und NP-Vollständigkeit
|Room=HSZ/0004
|Date=2018/05/11
|DS=DS3
|Download=TheoLog2018-Vorlesung-09-overlay.pdf, TheoLog2018-Vorlesung-09-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NP (2)
|Room=HSZ/0004
|Date=2018/05/14
|DS=DS2
|Download=TheoLog2018-Vorlesung-10-overlay.pdf, TheoLog2018-Vorlesung-10-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NL und PSpace
|Room=HSZ/0004
|Date=2018/05/18
|DS=DS3
|Download=TheoLog2018-Vorlesung-11-overlay.pdf, TheoLog2018-Vorlesung-11-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=PSpace-Vollständigkeit
|Room=HSZ/0004
|Date=2018/05/28
|DS=DS2
|Download=TheoLog2018-Vorlesung-12-overlay.pdf, TheoLog2018-Vorlesung-12-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Prädikatenlogik: Syntax und Semantik
|Room=HSZ/0004
|Date=2018/06/01
|DS=DS3
|Download=TheoLog2018-Vorlesung-13-overlay.pdf, TheoLog2018-Vorlesung-13-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Modelltheorie und logisches Schließen
|Room=HSZ/0004
|Date=2018/06/04
|DS=DS2
|Download=TheoLog2018-Vorlesung-14-overlay.pdf, TheoLog2018-Vorlesung-14-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Logisches Schließen
|Room=HSZ/0004
|Date=2018/06/08
|DS=DS3
|Download=TheoLog2018-Vorlesung-15-overlay.pdf, TheoLog2018-Vorlesung-15-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Logisches Schließen (2)
|Room=HSZ/0004
|Date=2018/06/11
|DS=DS2
|Download=TheoLog2018-Vorlesung-16-overlay.pdf, TheoLog2018-Vorlesung-16-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Repetitorium 1
|Room=HSZ/0004
|Date=2018/06/15
|DS=DS3
|Download=Theolog2018-Repetitorium-01-Folien.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Funktionen und Normalformen
|Room=HSZ/0004
|Date=2018/06/18
|DS=DS2
|Download=TheoLog2018-Vorlesung-17-overlay.pdf, TheoLog2018-Vorlesung-17-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Unifikation
|Room=HSZ/0004
|Date=2018/06/22
|DS=DS3
|Download=TheoLog2018-Vorlesung-18-overlay.pdf, TheoLog2018-Vorlesung-18-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Resolution
|Room=HSZ/0004
|Date=2018/06/25
|DS=DS2
|Download=TheoLog2018-Vorlesung-19-overlay.pdf, TheoLog2018-Vorlesung-19-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Resolution (2)
|Room=HSZ/0004
|Date=2018/06/29
|DS=DS3
|Download=TheoLog2018-Vorlesung-20-overlay.pdf, TheoLog2018-Vorlesung-20-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Endliche Modelle und Datenbanken
|Room=HSZ/0004
|Date=2018/07/02
|DS=DS2
|Download=TheoLog2018-Vorlesung-21-overlay.pdf, TheoLog2018-Vorlesung-21-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Datalog
|Room=HSZ/0004
|Date=2018/07/06
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Gödels Unvollständigkeitssätze
|Room=HSZ/0004
|Date=2018/07/09
|DS=DS2
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Gödel, Turing und der ganze Rest
|Room=HSZ/0004
|Date=2018/07/13
|DS=DS3
}}

Datei:TheoLog18-uebung-11.pdf

2018-06-27T10:29:54Z

Sascha Klüppelholz:

Theoretische Informatik und Logik (SS2018)

2018-06-27T10:29:29Z

Sascha Klüppelholz:

{{Vorlesung
|Title=Theoretische Informatik und Logik
|Research group=Verifikation und formale quantitative Analyse; Wissensbasierte Systeme
|Lecturers=Markus Krötzsch;
|Tutors=Sascha Klüppelholz; Maximilian Marx;
|Term=SS
|Year=2018
|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 (WS2017)|Formale Systeme]] können hilfreich sein.

==Aktuelle Hinweise==
Aufgrund des Dies Academicus am 6. Juni werden zwei zusätzliche Übungstermine angeboten:

* Dienstag 05.06.2018, 6.DS, APB/3027
* Donnerstag 07.06.2018, 6.DS, APB/3027

Studierende aus den den betroffenen Mittwochs-Übungsgruppen haben darüber hinaus auch die Möglichkeit, auf eine der anderen in dieser Woche stattfindenen Übungsgruppen auszuweichen.

==Termine==

Die erste Vorlesung findet am Mittwoch, den 09.04.2018, statt. Weitere Termine sind jeweils:
* Montag, 2.DS (09:20–10:50) HSZ/0004
* Freitag, 3.DS (11:10–12:40) HSZ/0004

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

===Übungsblätter===

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

* [[Medium:TheoLog18-uebung-01.pdf|1. Übungsblatt]]
* [[Medium:TheoLog18-uebung-02.pdf|2. Übungsblatt]]
* [[Medium:TheoLog18-uebung-03.pdf|3. Übungsblatt]]
* [[Medium:TheoLog18-uebung-04.pdf|4. Übungsblatt]]
* [[Medium:TheoLog18-uebung-05.pdf|5. Übungsblatt]]
* [[Medium:TheoLog18-uebung-06.pdf|6. Übungsblatt]], [[Medium:TheoLog18-uebung-06-03-musterloesung.pdf|Musterlösung für Aufgabe 3]]
* [[Medium:TheoLog18-uebung-07.pdf|7. Übungsblatt]]
* [[Medium:TheoLog18-repetitorium-01.pdf|1. Repetitorium]]
* [[Medium:TheoLog18-uebung-08.pdf|8. Übungsblatt]]
* [[Medium:TheoLog18-uebung-09.pdf|9. Übungsblatt]]
* [[Medium:TheoLog18-uebung-10.pdf|10. Übungsblatt]]
* [[Medium:TheoLog18-uebung-11.pdf|11. Ü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/TheoLog2018, CC BY 3.0 DE

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

== Kontakt ==

Fragen können am einfachsten in Vorlesung oder Übungsgruppe gestellt werden oder per Email an das Organisationsteam (siehe Links oben). Kommentare und Bug Reports können gern auch direkt über die entsprechenden Seiten auf github gepostet werden: https://github.com/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=2018/04/09
|DS=DS2
|Download=TheoLog2018-Vorlesung-01-overlay.pdf, TheoLog2018-Vorlesung-01-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Berechenbarkeit und Unentscheidbarkeit
|Room=HSZ/0004
|Date=2018/04/13
|DS=DS3
|Download=TheoLog2018-Vorlesung-02-overlay.pdf, TheoLog2018-Vorlesung-02-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=WHILE und LOOP
|Room=HSZ/0004
|Date=2018/04/16
|DS=DS2
|Download=TheoLog2018-Vorlesung-03-overlay.pdf, TheoLog2018-Vorlesung-03-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Das Halteproblem und Reduktionen
|Room=HSZ/0004
|Date=2018/04/20
|DS=DS3
|Download=TheoLog2018-Vorlesung-04-overlay.pdf, TheoLog2018-Vorlesung-04-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Satz von Rice/Postsches Korrespondenzproblem
|Room=HSZ/0004
|Date=2018/04/27
|DS=DS3
|Download=TheoLog2018-Vorlesung-05-overlay.pdf, TheoLog2018-Vorlesung-05-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Unentscheidbare Probleme formaler Sprachen
|Room=HSZ/0004
|Date=2018/04/30
|DS=DS2
|Download=TheoLog2018-Vorlesung-06-overlay.pdf, TheoLog2018-Vorlesung-06-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Einführung in die Komplexitätstheorie
|Room=HSZ/0004
|Date=2018/05/04
|DS=DS3
|Download=TheoLog2018-Vorlesung-07-overlay.pdf, TheoLog2018-Vorlesung-07-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Komplexitätsklassen / Effizienz / Reduktionen
|Room=HSZ/0004
|Date=2018/05/07
|DS=DS2
|Download=TheoLog2018-Vorlesung-08-overlay.pdf, TheoLog2018-Vorlesung-08-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NP und NP-Vollständigkeit
|Room=HSZ/0004
|Date=2018/05/11
|DS=DS3
|Download=TheoLog2018-Vorlesung-09-overlay.pdf, TheoLog2018-Vorlesung-09-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NP (2)
|Room=HSZ/0004
|Date=2018/05/14
|DS=DS2
|Download=TheoLog2018-Vorlesung-10-overlay.pdf, TheoLog2018-Vorlesung-10-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NL und PSpace
|Room=HSZ/0004
|Date=2018/05/18
|DS=DS3
|Download=TheoLog2018-Vorlesung-11-overlay.pdf, TheoLog2018-Vorlesung-11-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=PSpace-Vollständigkeit
|Room=HSZ/0004
|Date=2018/05/28
|DS=DS2
|Download=TheoLog2018-Vorlesung-12-overlay.pdf, TheoLog2018-Vorlesung-12-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Prädikatenlogik: Syntax und Semantik
|Room=HSZ/0004
|Date=2018/06/01
|DS=DS3
|Download=TheoLog2018-Vorlesung-13-overlay.pdf, TheoLog2018-Vorlesung-13-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Modelltheorie und logisches Schließen
|Room=HSZ/0004
|Date=2018/06/04
|DS=DS2
|Download=TheoLog2018-Vorlesung-14-overlay.pdf, TheoLog2018-Vorlesung-14-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Logisches Schließen
|Room=HSZ/0004
|Date=2018/06/08
|DS=DS3
|Download=TheoLog2018-Vorlesung-15-overlay.pdf, TheoLog2018-Vorlesung-15-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Logisches Schließen (2)
|Room=HSZ/0004
|Date=2018/06/11
|DS=DS2
|Download=TheoLog2018-Vorlesung-16-overlay.pdf, TheoLog2018-Vorlesung-16-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Repetitorium 1
|Room=HSZ/0004
|Date=2018/06/15
|DS=DS3
|Download=Theolog2018-Repetitorium-01-Folien.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Funktionen und Normalformen
|Room=HSZ/0004
|Date=2018/06/18
|DS=DS2
|Download=TheoLog2018-Vorlesung-17-overlay.pdf, TheoLog2018-Vorlesung-17-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Unifikation
|Room=HSZ/0004
|Date=2018/06/22
|DS=DS3
|Download=TheoLog2018-Vorlesung-18-overlay.pdf, TheoLog2018-Vorlesung-18-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Resolution
|Room=HSZ/0004
|Date=2018/06/25
|DS=DS2
|Download=TheoLog2018-Vorlesung-19-overlay.pdf, TheoLog2018-Vorlesung-19-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Resolution / Endliche Modelle
|Room=HSZ/0004
|Date=2018/06/29
|DS=DS3
}}

Datei:TheoLog18-uebung-10.pdf

2018-06-21T07:30:26Z

Sascha Klüppelholz:

Theoretische Informatik und Logik (SS2018)

2018-06-21T07:30:06Z

Sascha Klüppelholz:

{{Vorlesung
|Title=Theoretische Informatik und Logik
|Research group=Verifikation und formale quantitative Analyse; Wissensbasierte Systeme
|Lecturers=Markus Krötzsch;
|Tutors=Sascha Klüppelholz; Maximilian Marx;
|Term=SS
|Year=2018
|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 (WS2017)|Formale Systeme]] können hilfreich sein.

==Aktuelle Hinweise==
Aufgrund des Dies Academicus am 6. Juni werden zwei zusätzliche Übungstermine angeboten:

* Dienstag 05.06.2018, 6.DS, APB/3027
* Donnerstag 07.06.2018, 6.DS, APB/3027

Studierende aus den den betroffenen Mittwochs-Übungsgruppen haben darüber hinaus auch die Möglichkeit, auf eine der anderen in dieser Woche stattfindenen Übungsgruppen auszuweichen.

==Termine==

Die erste Vorlesung findet am Mittwoch, den 09.04.2018, statt. Weitere Termine sind jeweils:
* Montag, 2.DS (09:20–10:50) HSZ/0004
* Freitag, 3.DS (11:10–12:40) HSZ/0004

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

===Übungsblätter===

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

* [[Medium:TheoLog18-uebung-01.pdf|1. Übungsblatt]]
* [[Medium:TheoLog18-uebung-02.pdf|2. Übungsblatt]]
* [[Medium:TheoLog18-uebung-03.pdf|3. Übungsblatt]]
* [[Medium:TheoLog18-uebung-04.pdf|4. Übungsblatt]]
* [[Medium:TheoLog18-uebung-05.pdf|5. Übungsblatt]]
* [[Medium:TheoLog18-uebung-06.pdf|6. Übungsblatt]], [[Medium:TheoLog18-uebung-06-03-musterloesung.pdf|Musterlösung für Aufgabe 3]]
* [[Medium:TheoLog18-uebung-07.pdf|7. Übungsblatt]]
* [[Medium:TheoLog18-repetitorium-01.pdf|1. Repetitorium]]
* [[Medium:TheoLog18-uebung-08.pdf|8. Übungsblatt]]
* [[Medium:TheoLog18-uebung-09.pdf|9. Übungsblatt]]
* [[Medium:TheoLog18-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/TheoLog2018, CC BY 3.0 DE

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

== Kontakt ==

Fragen können am einfachsten in Vorlesung oder Übungsgruppe gestellt werden oder per Email an das Organisationsteam (siehe Links oben). Kommentare und Bug Reports können gern auch direkt über die entsprechenden Seiten auf github gepostet werden: https://github.com/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=2018/04/09
|DS=DS2
|Download=TheoLog2018-Vorlesung-01-overlay.pdf, TheoLog2018-Vorlesung-01-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Berechenbarkeit und Unentscheidbarkeit
|Room=HSZ/0004
|Date=2018/04/13
|DS=DS3
|Download=TheoLog2018-Vorlesung-02-overlay.pdf, TheoLog2018-Vorlesung-02-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=WHILE und LOOP
|Room=HSZ/0004
|Date=2018/04/16
|DS=DS2
|Download=TheoLog2018-Vorlesung-03-overlay.pdf, TheoLog2018-Vorlesung-03-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Das Halteproblem und Reduktionen
|Room=HSZ/0004
|Date=2018/04/20
|DS=DS3
|Download=TheoLog2018-Vorlesung-04-overlay.pdf, TheoLog2018-Vorlesung-04-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Satz von Rice/Postsches Korrespondenzproblem
|Room=HSZ/0004
|Date=2018/04/27
|DS=DS3
|Download=TheoLog2018-Vorlesung-05-overlay.pdf, TheoLog2018-Vorlesung-05-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Unentscheidbare Probleme formaler Sprachen
|Room=HSZ/0004
|Date=2018/04/30
|DS=DS2
|Download=TheoLog2018-Vorlesung-06-overlay.pdf, TheoLog2018-Vorlesung-06-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Einführung in die Komplexitätstheorie
|Room=HSZ/0004
|Date=2018/05/04
|DS=DS3
|Download=TheoLog2018-Vorlesung-07-overlay.pdf, TheoLog2018-Vorlesung-07-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Komplexitätsklassen / Effizienz / Reduktionen
|Room=HSZ/0004
|Date=2018/05/07
|DS=DS2
|Download=TheoLog2018-Vorlesung-08-overlay.pdf, TheoLog2018-Vorlesung-08-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NP und NP-Vollständigkeit
|Room=HSZ/0004
|Date=2018/05/11
|DS=DS3
|Download=TheoLog2018-Vorlesung-09-overlay.pdf, TheoLog2018-Vorlesung-09-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NP (2)
|Room=HSZ/0004
|Date=2018/05/14
|DS=DS2
|Download=TheoLog2018-Vorlesung-10-overlay.pdf, TheoLog2018-Vorlesung-10-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NL und PSpace
|Room=HSZ/0004
|Date=2018/05/18
|DS=DS3
|Download=TheoLog2018-Vorlesung-11-overlay.pdf, TheoLog2018-Vorlesung-11-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=PSpace-Vollständigkeit
|Room=HSZ/0004
|Date=2018/05/28
|DS=DS2
|Download=TheoLog2018-Vorlesung-12-overlay.pdf, TheoLog2018-Vorlesung-12-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Prädikatenlogik: Syntax und Semantik
|Room=HSZ/0004
|Date=2018/06/01
|DS=DS3
|Download=TheoLog2018-Vorlesung-13-overlay.pdf, TheoLog2018-Vorlesung-13-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Modelltheorie und logisches Schließen
|Room=HSZ/0004
|Date=2018/06/04
|DS=DS2
|Download=TheoLog2018-Vorlesung-14-overlay.pdf, TheoLog2018-Vorlesung-14-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Logisches Schließen
|Room=HSZ/0004
|Date=2018/06/08
|DS=DS3
|Download=TheoLog2018-Vorlesung-15-overlay.pdf, TheoLog2018-Vorlesung-15-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Logisches Schließen (2)
|Room=HSZ/0004
|Date=2018/06/11
|DS=DS2
|Download=TheoLog2018-Vorlesung-16-overlay.pdf, TheoLog2018-Vorlesung-16-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Repetitorium 1
|Room=HSZ/0004
|Date=2018/06/15
|DS=DS3
|Download=Theolog2018-Repetitorium-01-Folien.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Funktionen und Normalformen
|Room=HSZ/0004
|Date=2018/06/18
|DS=DS2
|Download=TheoLog2018-Vorlesung-17-overlay.pdf, TheoLog2018-Vorlesung-17-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Unifikation
|Room=HSZ/0004
|Date=2018/06/22
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Resolution
|Room=HSZ/0004
|Date=2018/06/25
|DS=DS2
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Resolution / Endliche Modelle
|Room=HSZ/0004
|Date=2018/06/29
|DS=DS3
}}

Datei:TheoLog18-uebung-09.pdf

2018-06-15T13:58:23Z

Sascha Klüppelholz:

Theoretische Informatik und Logik (SS2018)

2018-06-15T13:58:06Z

Sascha Klüppelholz:

{{Vorlesung
|Title=Theoretische Informatik und Logik
|Research group=Verifikation und formale quantitative Analyse; Wissensbasierte Systeme
|Lecturers=Markus Krötzsch;
|Tutors=Sascha Klüppelholz; Maximilian Marx;
|Term=SS
|Year=2018
|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 (WS2017)|Formale Systeme]] können hilfreich sein.

==Aktuelle Hinweise==
Aufgrund des Dies Academicus am 6. Juni werden zwei zusätzliche Übungstermine angeboten:

* Dienstag 05.06.2018, 6.DS, APB/3027
* Donnerstag 07.06.2018, 6.DS, APB/3027

Studierende aus den den betroffenen Mittwochs-Übungsgruppen haben darüber hinaus auch die Möglichkeit, auf eine der anderen in dieser Woche stattfindenen Übungsgruppen auszuweichen.

==Termine==

Die erste Vorlesung findet am Mittwoch, den 09.04.2018, statt. Weitere Termine sind jeweils:
* Montag, 2.DS (09:20–10:50) HSZ/0004
* Freitag, 3.DS (11:10–12:40) HSZ/0004

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

===Übungsblätter===

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

* [[Medium:TheoLog18-uebung-01.pdf|1. Übungsblatt]]
* [[Medium:TheoLog18-uebung-02.pdf|2. Übungsblatt]]
* [[Medium:TheoLog18-uebung-03.pdf|3. Übungsblatt]]
* [[Medium:TheoLog18-uebung-04.pdf|4. Übungsblatt]]
* [[Medium:TheoLog18-uebung-05.pdf|5. Übungsblatt]]
* [[Medium:TheoLog18-uebung-06.pdf|6. Übungsblatt]], [[Medium:TheoLog18-uebung-06-03-musterloesung.pdf|Musterlösung für Aufgabe 3]]
* [[Medium:TheoLog18-uebung-07.pdf|7. Übungsblatt]]
* [[Medium:TheoLog18-repetitorium-01.pdf|1. Repetitorium]]
* [[Medium:TheoLog18-uebung-08.pdf|8. Übungsblatt]]
* [[Medium:TheoLog18-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/TheoLog2018, CC BY 3.0 DE

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

== Kontakt ==

Fragen können am einfachsten in Vorlesung oder Übungsgruppe gestellt werden oder per Email an das Organisationsteam (siehe Links oben). Kommentare und Bug Reports können gern auch direkt über die entsprechenden Seiten auf github gepostet werden: https://github.com/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=2018/04/09
|DS=DS2
|Download=TheoLog2018-Vorlesung-01-overlay.pdf, TheoLog2018-Vorlesung-01-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Berechenbarkeit und Unentscheidbarkeit
|Room=HSZ/0004
|Date=2018/04/13
|DS=DS3
|Download=TheoLog2018-Vorlesung-02-overlay.pdf, TheoLog2018-Vorlesung-02-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=WHILE und LOOP
|Room=HSZ/0004
|Date=2018/04/16
|DS=DS2
|Download=TheoLog2018-Vorlesung-03-overlay.pdf, TheoLog2018-Vorlesung-03-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Das Halteproblem und Reduktionen
|Room=HSZ/0004
|Date=2018/04/20
|DS=DS3
|Download=TheoLog2018-Vorlesung-04-overlay.pdf, TheoLog2018-Vorlesung-04-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Satz von Rice/Postsches Korrespondenzproblem
|Room=HSZ/0004
|Date=2018/04/27
|DS=DS3
|Download=TheoLog2018-Vorlesung-05-overlay.pdf, TheoLog2018-Vorlesung-05-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Unentscheidbare Probleme formaler Sprachen
|Room=HSZ/0004
|Date=2018/04/30
|DS=DS2
|Download=TheoLog2018-Vorlesung-06-overlay.pdf, TheoLog2018-Vorlesung-06-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Einführung in die Komplexitätstheorie
|Room=HSZ/0004
|Date=2018/05/04
|DS=DS3
|Download=TheoLog2018-Vorlesung-07-overlay.pdf, TheoLog2018-Vorlesung-07-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Komplexitätsklassen / Effizienz / Reduktionen
|Room=HSZ/0004
|Date=2018/05/07
|DS=DS2
|Download=TheoLog2018-Vorlesung-08-overlay.pdf, TheoLog2018-Vorlesung-08-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NP und NP-Vollständigkeit
|Room=HSZ/0004
|Date=2018/05/11
|DS=DS3
|Download=TheoLog2018-Vorlesung-09-overlay.pdf, TheoLog2018-Vorlesung-09-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NP (2)
|Room=HSZ/0004
|Date=2018/05/14
|DS=DS2
|Download=TheoLog2018-Vorlesung-10-overlay.pdf, TheoLog2018-Vorlesung-10-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NL und PSpace
|Room=HSZ/0004
|Date=2018/05/18
|DS=DS3
|Download=TheoLog2018-Vorlesung-11-overlay.pdf, TheoLog2018-Vorlesung-11-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=PSpace-Vollständigkeit
|Room=HSZ/0004
|Date=2018/05/28
|DS=DS2
|Download=TheoLog2018-Vorlesung-12-overlay.pdf, TheoLog2018-Vorlesung-12-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Prädikatenlogik: Syntax und Semantik
|Room=HSZ/0004
|Date=2018/06/01
|DS=DS3
|Download=TheoLog2018-Vorlesung-13-overlay.pdf, TheoLog2018-Vorlesung-13-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Modelltheorie und logisches Schließen
|Room=HSZ/0004
|Date=2018/06/04
|DS=DS2
|Download=TheoLog2018-Vorlesung-14-overlay.pdf, TheoLog2018-Vorlesung-14-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Logisches Schließen
|Room=HSZ/0004
|Date=2018/06/08
|DS=DS3
|Download=TheoLog2018-Vorlesung-15-overlay.pdf, TheoLog2018-Vorlesung-15-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Logisches Schließen (2)
|Room=HSZ/0004
|Date=2018/06/11
|DS=DS2
|Download=TheoLog2018-Vorlesung-16-overlay.pdf, TheoLog2018-Vorlesung-16-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Repetitorium 1
|Room=HSZ/0004
|Date=2018/06/15
|DS=DS3
|Download=Theolog2018-Repetitorium-01-Folien.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Funktionen und Normalformen
|Room=HSZ/0004
|Date=2018/06/18
|DS=DS2
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Unifikation
|Room=HSZ/0004
|Date=2018/06/22
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Resolution
|Room=HSZ/0004
|Date=2018/06/25
|DS=DS2
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Resolution / Endliche Modelle
|Room=HSZ/0004
|Date=2018/06/29
|DS=DS3
}}

Theoretische Informatik und Logik (SS2018)

2018-06-06T14:31:58Z

Sascha Klüppelholz:

{{Vorlesung
|Title=Theoretische Informatik und Logik
|Research group=Verifikation und formale quantitative Analyse; Wissensbasierte Systeme
|Lecturers=Markus Krötzsch;
|Tutors=Sascha Klüppelholz; Maximilian Marx;
|Term=SS
|Year=2018
|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 (WS2017)|Formale Systeme]] können hilfreich sein.

==Aktuelle Hinweise==
Aufgrund des Dies Academicus am 6. Juni werden zwei zusätzliche Übungstermine angeboten:

* Dienstag 05.06.2018, 6.DS, APB/3027
* Donnerstag 07.06.2018, 6.DS, APB/3027

Studierende aus den den betroffenen Mittwochs-Übungsgruppen haben darüber hinaus auch die Möglichkeit, auf eine der anderen in dieser Woche stattfindenen Übungsgruppen auszuweichen.

==Termine==

Die erste Vorlesung findet am Mittwoch, den 09.04.2018, statt. Weitere Termine sind jeweils:
* Montag, 2.DS (09:20–10:50) HSZ/0004
* Freitag, 3.DS (11:10–12:40) HSZ/0004

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

===Übungsblätter===

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

* [[Medium:TheoLog18-uebung-01.pdf|1. Übungsblatt]]
* [[Medium:TheoLog18-uebung-02.pdf|2. Übungsblatt]]
* [[Medium:TheoLog18-uebung-03.pdf|3. Übungsblatt]]
* [[Medium:TheoLog18-uebung-04.pdf|4. Übungsblatt]]
* [[Medium:TheoLog18-uebung-05.pdf|5. Übungsblatt]]
* [[Medium:TheoLog18-uebung-06.pdf|6. Übungsblatt]], [[Medium:TheoLog18-uebung-06-03-musterloesung.pdf|Musterlösung für Aufgabe 3]]
* [[Medium:TheoLog18-uebung-07.pdf|7. Übungsblatt]]
* [[Medium:TheoLog18-repetitorium-01.pdf|1. Repetitorium]]
* [[Medium:TheoLog18-uebung-08.pdf|8. Übungsblatt]]

== Unterlagen ==

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

Alle Foliensätze der Vorlesungen können entsprechend den Lizensbedingungen von [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/TheoLog2018, CC BY 3.0 DE

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

== Kontakt ==

Fragen können am einfachsten in Vorlesung oder Übungsgruppe gestellt werden oder per Email an das Organisationsteam (siehe Links oben). Kommentare und Bug Reports können gern auch direkt über die entsprechenden Seiten auf github gepostet werden: https://github.com/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=2018/04/09
|DS=DS2
|Download=TheoLog2018-Vorlesung-01-overlay.pdf, TheoLog2018-Vorlesung-01-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Berechenbarkeit und Unentscheidbarkeit
|Room=HSZ/0004
|Date=2018/04/13
|DS=DS3
|Download=TheoLog2018-Vorlesung-02-overlay.pdf, TheoLog2018-Vorlesung-02-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=WHILE und LOOP
|Room=HSZ/0004
|Date=2018/04/16
|DS=DS2
|Download=TheoLog2018-Vorlesung-03-overlay.pdf, TheoLog2018-Vorlesung-03-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Das Halteproblem und Reduktionen
|Room=HSZ/0004
|Date=2018/04/20
|DS=DS3
|Download=TheoLog2018-Vorlesung-04-overlay.pdf, TheoLog2018-Vorlesung-04-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Satz von Rice/Postsches Korrespondenzproblem
|Room=HSZ/0004
|Date=2018/04/27
|DS=DS3
|Download=TheoLog2018-Vorlesung-05-overlay.pdf, TheoLog2018-Vorlesung-05-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Unentscheidbare Probleme formaler Sprachen
|Room=HSZ/0004
|Date=2018/04/30
|DS=DS2
|Download=TheoLog2018-Vorlesung-06-overlay.pdf, TheoLog2018-Vorlesung-06-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Einführung in die Komplexitätstheorie
|Room=HSZ/0004
|Date=2018/05/04
|DS=DS3
|Download=TheoLog2018-Vorlesung-07-overlay.pdf, TheoLog2018-Vorlesung-07-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Komplexitätsklassen / Effizienz / Reduktionen
|Room=HSZ/0004
|Date=2018/05/07
|DS=DS2
|Download=TheoLog2018-Vorlesung-08-overlay.pdf, TheoLog2018-Vorlesung-08-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NP und NP-Vollständigkeit
|Room=HSZ/0004
|Date=2018/05/11
|DS=DS3
|Download=TheoLog2018-Vorlesung-09-overlay.pdf, TheoLog2018-Vorlesung-09-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NP (2)
|Room=HSZ/0004
|Date=2018/05/14
|DS=DS2
|Download=TheoLog2018-Vorlesung-10-overlay.pdf, TheoLog2018-Vorlesung-10-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NL und PSpace
|Room=HSZ/0004
|Date=2018/05/18
|DS=DS3
|Download=TheoLog2018-Vorlesung-11-overlay.pdf, TheoLog2018-Vorlesung-11-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=PSpace-Vollständigkeit
|Room=HSZ/0004
|Date=2018/05/28
|DS=DS2
|Download=TheoLog2018-Vorlesung-12-overlay.pdf, TheoLog2018-Vorlesung-12-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Prädikatenlogik: Syntax und Semantik
|Room=HSZ/0004
|Date=2018/06/01
|DS=DS3
|Download=TheoLog2018-Vorlesung-13-overlay.pdf, TheoLog2018-Vorlesung-13-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Modelltheorie und logisches Schließen
|Room=HSZ/0004
|Date=2018/06/04
|DS=DS2
|Download=TheoLog2018-Vorlesung-14-overlay.pdf, TheoLog2018-Vorlesung-14-print.pdf,
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Logisches Schließen
|Room=HSZ/0004
|Date=2018/06/08
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Logisches Schließen (2)
|Room=HSZ/0004
|Date=2018/06/11
|DS=DS2
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Repetitorium 1
|Room=HSZ/0004
|Date=2018/06/15
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Funktionen und Normalformen
|Room=HSZ/0004
|Date=2018/06/18
|DS=DS2
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Unifikation
|Room=HSZ/0004
|Date=2018/06/22
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Resolution
|Room=HSZ/0004
|Date=2018/06/25
|DS=DS2
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Resolution / Endliche Modelle
|Room=HSZ/0004
|Date=2018/06/29
|DS=DS3
}}

Datei:TheoLog18-uebung-08.pdf

2018-06-06T14:31:39Z

Sascha Klüppelholz:

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

2018-06-05T12:04:07Z

Sascha Klüppelholz: