• Forschung
• Lehre
  • Rückschau
  • Qualifikationsarbeiten
• Personen
• WSV Publikationen
• WSV Kontakt

Formale Grundlagen der Informatik 1

• Veranstalter
• Zeit/Ort
• Inhalt
• Literatur
• Links

64-050 Vorlesung: Formale Grundlagen der Informatik 1
Sommersemester 2010

Veranstalter
	Christopher Habel, Matthias Jantzen
Zeit/Ort
	Mo 12-14 ESA A, Di 08-10 Audimax 1
Aktuelles
	Klausurterminseite des Studienbüro Informatik Die zweite Klausur findet am Donnerstag den 7.10.2010 ebenfalls im Audimax 1 statt. Einlass um 9:15, Beginn 9:30.
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 18.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
	Teil 0: Einführung, Sprachen und Grammatiken (Habel) Einleitung (.pdf) Sprachen und Grammatiken (.pdf) Teil 1: Logik (Habel) Aussagenlogik: Syntax (.pdf) Aussagenlogik: Semantik (.pdf) Aussagenlogik: Normalformen (.pdf) Aussagenlogik: Folgerung (.pdf) Aussagenlogik: Deduktion (.pdf) Hornformeln (.pdf) Resolution (.pdf) Prädikatenlogik (.pdf) Prädikatenlogik: Normalformen (.pdf) Prädikatenlogik: Resolution (.pdf) Teil 2: Automaten, Formale Sprachen, Berechenbarkeit und Komplexität (Jantzen) Endliche Automaten (korrigierte Version vom 28.06.2010) (.pdf) Kontextfreie bis Typ-1 Sprachen (korrigierte Version vom 28.06.2010) (.pdf) Turingmaschine und Entscheidbarkeit (korrigierte Version vom 28.06.2010) (.pdf) Berechenbarkeit und Komplexitaet (Version vom 04.07.2010) (.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.