|
Veranstalter
|
|
Carola Eschenbach,
Michael Köhler-Bußmeier
|
|
Zeit/Ort
|
|
Mo 12-14 Erzwiss H,
Di 08-10 Audimax 2
|
|
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.
|
| Vorgehen |
|
Vorlesung; Die Veranstaltung legt großes Gewicht auf das Erlernen des Umgangs mit
formalen Methoden. Aus diesem Grund kommt den Übungen eine besondere Bedeutung zu. Die
erfolgreiche Teilnahme an den Übungen ist Voraussetzung für die Zulassung zur
studienbegleitenden Abschlussprüfung (Klausur). (siehe auch 64-051). |
|
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
|
|
Zu Semesterbeginn finden sich hier noch die Unterlagen des vergangenen Semesters.
Da die Veranstaltung in diesem Semester etwas anders als zuvor organisiert wird, wird es
im Laufe des Semesters Veränderungen geben. Zu gegebener Zeit werden wir die geänderten
Foliensätze hier zur Verfügung stellen.
Teil Automaten-1: (Köhler-Bußmeier)
Teil Logik (Eschenbach)
- Logik: Gesamter Foliensatz 2auf1(.pdf) 4auf1(.pdf) (13.4.11)
- Logik: Themenliste (.pdf)
- Errata und Ergänzungen zum Logik-Teil
(.pdf) (2.6.11)
- Logik: Einleitung (.pdf) (13.4.11)
- Aussagenlogik: Syntax (.pdf) (6.5.11)
- Aussagenlogik: Semantik (.pdf) (6.5.11)
- Aussagenlogik: Normalformen (.pdf) (6.5.11)
- Aussagenlogik: Folgerung (.pdf) (6.5.11)
- Aussagenlogik: Deduktion (.pdf) (13.5.11)
- Aussagenlogik: Hornformeln (.pdf) (13.5.11)
- Aussagenlogik: Resolution (.pdf) (16.5.11)
- Prädikatenlogik (.pdf) (20.5.11)
- Prädikatenlogik: Normalformen (.pdf) (31.5.11, Ergänzungen vor allem am Ende)
- Prädikatenlogik: Resolution (.pdf) (2.6.11)
Teil Automaten-2: (Köhler-Bußmeier)
-
Deterministischer Kellerautomat, andere Chomsky Grammatiken
(.pdf)
- Turingmaschinen
(.pdf)
- Turingmaschinen: Aufzählbarkeit
(.pdf)
- Entscheidbarkeit, Gödelisierung, Halteproblem
(.pdf)
- Komplexitätstheorie
(.pdf)
- Berechenbarkeit
(.pdf)
- Abschlussfolien
(.pdf)
|
|
Links
|
|
|
