|
Veranstalter
|
|
Christopher Habel,
Matthias Jantzen
|
|
Zeit/Ort
|
|
Di 14-16 Phil D,
Do 10-12 ESA A
|
|
Inhalt
|
|
Die Modellierung und Analyse von Problemen sowie die Beurteilung gefundener Lösungen
sind grundlegende Bestandteile der Informatik. Das Modul Grundlagen der Theoretischen
Informatik beschäftigt sich auf mathematischer Basis mit Abstraktionen, Modellbildungen und
Verfahren zur Beschreibung und Analyse von Algorithmen und Prozessen. Formale Methoden
spielen in der Informatik die Rolle eines "Denkzeugs", mit dem der
(abstrakte) Kern einer Sache knapp und präzise beschrieben werden kann. Wesentliche
Hilfsmittel zur Modellierung von Problemen sind Kalküle, insbesondere logische Kalküle,
formale Sprachen, Grammatiken und Automaten. Dadurch werden Modelle und Problemlösungen
einer mathematischen Analyse zugänglich. Die ausführliche Modulbeschreibung findet sich im
Studienführer unter IP8
Die Vorlesung umfasst drei Themenbereiche:
- Grundlegende Begriffe, Notationsformen und Strukturen werden formal definiert und
an Beispielen erläutert.
- Logik: Logikkalküle sind Grundlage für eine formale Semantik von sprachlichen
Beschreibungen, wie auch von Anweisungen in Programmier-, Spezifikations-, und
Repräsentationssprachen. Die syntaktischen Beschreibungen ergeben Formale Sprachen,
die über andere Erzeugungsmechanismen auch in dem dritten Themenbereich behandelt
werden.
- Automatentheorie, Formale Sprachen und Berechenbarkeit: Automaten dienen als
einfache mathematische Modelle von Computern oder auch Algorithmen. Mit Formalen
Sprachen wird der prinzipielle, strukturelle Aufbau von Programmier- und
Spezifikationssprachen beschrieben. Die Theorie der Berechenbarkeit untersucht, in
Verbindung mit der formalen Beschreibung von Komplexität, die Abgrenzung zwischen
effektiv Ausführbarem und prinzipiell niemals Möglichem.
|
|
Literatur
|
|
- Vossen, Gottfried & Witt, Kurt-Ulrich (2006). Grundkurs Theoretische
Informatik. Vieweg Verlag
- Spies, Marcus (2003). Einführung in die Logik. Werkzeuge für Wissensrepräsentation
und Wissensmanagement. Spektrum, Akademischer Verlag
- Schöning, Uwe (2000). Logik für Informatiker. Spektrum, Akademischer Verlag
- Sipser, Michael (2006). Introduction to the Theory of Computation, Thomson Course
Technology, Parts One and Two
|
|
Folien
|
|
Teil 0: Einführung, Sprachen und Grammatiken (Habel)
Teil 1: Logik (Habel)
Teil 2: Automaten und Berechenbarkeit (Jantzen) (Letztes Update: 07.07.09)
- Einführung und Motivation (.pdf)
- Endlicher Automat, Potenzautomat (korrigierte Version vom 15.06.09) (.pdf)
- Konfiguration eines NFA, epsilon-NFA, Pumping-Lemma, reguläre Ausdrücke (korrigierte Version vom 22.06.09) (.pdf)
- Normalformen kontextfreier Grammatiken (korrigierte Version vom 19.06.09) (.pdf)
- Pumping, Abschlusseigenschaften, Entscheidbarkeit und Kellerautomat (korrigierte Version vom 19.06.09) (.pdf)
- Deterministischer Kellerautomat, andere Chomsky Grammatiken (korrigierte Version vom 22.06.09) (.pdf)
- Turingmaschinen (korrigierte Version vom 24.06.09) (.pdf)
- Berechenbarkeit, Turingmaschinen und kontextsensitive Grammatiken (korrigierte Version vom 07.07.09) (.pdf)
- Entscheidbarkeit, Gödelisierung, Halteproblem (korrigierte Version vom 26.06.09) (.pdf)
- Varianten der Turingmaschinen, Berechenbarkeitsdefinitionen (korrigierte Version vom 26.06.09) (.pdf)
- Komplexität (korrigierte Version vom 07.07.09) (.pdf)
- Landau-Notation, Komplexitätsklassen (korrigierte Version vom 07.07.09) (.pdf)
- NP-Vollständigkeit (korrigierte Version vom 26.06.09) (.pdf)
- Überblick (.pdf)
|
|
Links
|
|
- Hinweise zu den Übungen zu FGI 1 sind hier zu finden.
- Informationen zu den Saalübungen von M. Duvigneau sind hier zu finden.
|
