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

18.004 Vorlesung: Formale Grundlagen der Informatik 1 Sommersemester 2007 Veranstalter Christopher Habel Zeit/Ort Di 10-12 Phil A, Do 8-10 Phil D Aktuelles KVV-Eintrag 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. (ca. 29,90 Euro) Spies, Marcus (2003). Einführung in die Logik. Werkzeuge für Wissensrepräsentation und Wissensmanagement. Spektrum, Akademischer Verlag. (ca. 20,50 Euro) Schöning, Uwe (2000). Logik für Informatiker. Spektrum, Akademischer Verlag. (ca. 20,00 Euro). Folien Einführung (neue Version vom 16.04.07)(.pdf) Sprachen und Grammatiken (neue Version vom 16.04.07)(.pdf) Aussagenlogik: Syntax (neue Version vom 16.04.07)(.pdf) Aussagenlogik: Semantik (neue Version vom 16.04.07)(.pdf) Aussagenlogik: Normalformen (neue Version vom 23.04.07)(.pdf) Aussagenlogik: Folgerung (neue Version vom 26.04.07)(.pdf) Aussagenlogik: Deduktion (neue Version vom 03.05.07)(.pdf) Hornformeln (neue Version vom 08.05.07)(.pdf) Resolution (Neue Version vom 14.05.07)(.pdf) Prädikatenlogik (Vorversion vom 14.05.07)(.pdf) Prädikatenlogik: Normalformen (Vorversion vom 21.05.07)(.pdf) Prädikatenlogik: Resolution (Vorversion vom 04.06.07)(.pdf) Endliche Automaten (Erweiterte Version vom 19.06.07)(.pdf) Kontextfreie Grammatiken und Kellerautomaten (Version vom 28.06.07)(.pdf) Abschlusseigenschaften (Version vom 03.07.07)(.pdf) Turingmaschinen (Version vom 10.07.07)(.pdf) Komplexität (Version vom 12.07.07)(.pdf) ERRATA(.pdf)