Navigation Forschung Lehre Personen Publikationen Kontakt   Formale Grundlagen der Informatik 1 Veranstalter Zeit/Ort Inhalt Literatur Links Wir freuen uns über Kommentare und Hinweise zu diesen Seiten.

18.050 Vorlesung: Formale Grundlagen der Informatik 1 Sommersemester 2008 Veranstalter Christopher Habel, Matthias Jantzen Zeit/Ort Di 10-12 Phil A, Do 8-10 Phil D Aktuelles 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) Einleitung (Version vom 08.04.08)(.pdf) Sprachen und Grammatiken (Version vom 08.04.08)(.pdf) Teil 1: Logik (Habel) Aussagenlogik: Syntax (Version vom 08.04.08)(.pdf) Aussagenlogik: Semantik (Version vom 16.04.07)(.pdf) Aussagenlogik: Normalformen (Version vom 23.04.07)(.pdf) Aussagenlogik: Folgerung (Version vom 26.04.07)(.pdf) Aussagenlogik: Deduktion (Version vom 03.05.07)(.pdf) Hornformeln (Version vom 08.05.07)(.pdf) Resolution (Version vom 14.05.07)(.pdf) Prädikatenlogik (Version vom 14.05.07)(.pdf) Prädikatenlogik: Normalformen (Version vom 21.05.07)(.pdf) Prädikatenlogik: Resolution (Version vom 04.06.07)(.pdf) Teil 2: Automaten und Berechenbarkeit (Jantzen) Einführung und Motivation (06.07.08)(.pdf) Endlicher Automat, Potenzautomat (06.07.08)(.pdf) NFA, Pumping-Lemma, reguläre Ausdrücke (06.07.08)(.pdf) Normalformen (06.07.08)(.pdf) Pumping, Abschlusseigenschaften, Entscheidbarkeit, Kellerautomat (06.07.08) (.pdf) Deterministischer Kellerautomat, andere Chomsky Grammatiken (06.07.08)(.pdf) Turingmaschinen (06.07.08)(.pdf) Berechenbarkeit, Turingmaschinen und kontextsensitive Grammatiken (06.07.08)(.pdf) Entscheidbarkeit, Gödelisierung, Halteproblem (06.07.08)(.pdf) Varianten der Turingmaschinen, Berechenbarkeitsdefinitionen(06.07.08) (.pdf) Komplexität (06.07.08) (.pdf) NP-Vollständigkeit (06.07.08)(.pdf) NP-Vollständigkeit (Fortsetzung) (06.07.08)(.pdf) Links Hinweise zu den Übungen zu FGI 1 sind hier zu finden.