Grundstudiumsvorlesung im SoSe 2005
18.001 Formale Grundlagen der Informatik 2 (F2)

   Matthias Jantzen

2st. Di 10 - 12 Phil A
Lernziel:
Übergeordnete Lernziele des Zyklus sind:
  • Methoden der (strukturellen) Mathematik für informatische Probleme anwenden zu können.
  • Definitionsprinzipien und Beweistechniken kennenzulernen und diese in unterschiedlichen Bereichen anwenden zu können.
  • Formale Konzepte der Modellierung kennenzulernen und zum Einsatz zu bringen.
  • die Grenzen der prinzipiellen Möglichkeiten mithilfe von theoretisch fundierten Aussagen benennen und einschätzen zu können.
  • Kennenlernen und vertraut werden mit grundlegenden formalen Konzepten und Methoden, die für fast alle Teilgebiete der Informatik wichtig sind.
  • Erwerben und Einüben der einfachsten Standardhilfsmittel für Beschreibung, Analyse, Entwurf und Bewertung von Problemen und deren Lösung.
Inhalt:
Die Vorlesungsreihe Formale Grundlagen der 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. Erst auf der Basis eines sauberen theoretischen Fundaments wird es möglich, solche Beschreibungen zu formulieren und deren Analysen vorzunehmen. Auf Bezüge zur Anwendung dieser Konzepte, wie sie insbesondere in anderen Veranstaltungen des Grundstudiums vorkommen, wird Wert gelegt. Die Veranstaltung Informatik F2 (Automaten und Formale Sprachen) ist nach Änderung des Rahmenstudienplans durch Modifikation aus der ehemals im ersten Semester angebotenen Veranstaltung F1 (Automaten und Kalküle) hervorgegangen. Sie benutzt die in M1 und F1 (Logik) gelehrten Konzepte und erläutert und vertieft sie in den Anwendungsbeispielen:
  • Definitions- und Spezifikationsmethoden: Mengen, Relationen, Funktionen, formale Sprachen, Operatoren, transitive Hüllen, Graphen, Bäume, induktive und rekursive Definition
  • Beweismethoden und -techniken: das Schubfachprinzip, Beweis durch Gegenbeispiel, Induktionsprinzip, indirekte Beweise, Diagonalisierungen, strukturelle Induktion

In der Vorlesung werden folgende Themen behandelt:

  • Modelle einfacher Automaten: endlicher akzeptierender Automat, endlicher Transduktor, Kellerautomat, Determinismus versus Nichtdeterminismus
  • Grundformen der formalen Syntax von Programmiersprachen: Rationale Ausdrücke, reguläre und kontextfreie Grammatiken, Syntaxdiagramme, Ableitungsbegriff, Ableitungs- und Syntaxbaum, Eigenschaften regulärer Mengen und kontextfreier Sprachen, Grenzen ihrer Ausdrucksfähigkeit
  • Grundlagen der Syntaxanalyse: Analyse allgemeiner kontextfreier Grammatiken, Bottom-up Syntaxanalyse, Deterministischer Kellerautomat und LR(k)-Grammatik, Top-down Syn taxanalyse und LL-Grammatiken, Verfahren des rekursiven Abstiegs
Stell. im Studienplan:
Grundstudium
Voraussetzungen:
Teilnahme an den Übungen, die Übungsscheine werden bewertet .
Vorgehen:
Vorlesung mit 1-std. Übungen (Vorl.-Nr. 18.002). Zur Vorlesung wird ein Skript verteilt, das abschnittsweise über die F2-Übungsgruppen erhältlich sein wird. Die Veranstaltung wird gleichzeitig für den Studiengang Wirtschaftsinformatik der Universität Hamburg im Grundstudium angeboten.
Literatur:
Peters: Einführung in mathematische Methoden der Informatik (B.I. Wissenschaftsverlag, Mannheim, 1974),
Schöning: Theoretische Informatik - kurz gefaßt (2. Aufl., Spektrum Akad. Verlag, Heidelberg, Berlin, 1995),
Wegener: Theoretische Informatik (B.G. Teubner, Stuttgart, 1993),
Zobel: Diskrete Strukturen - Eine Angewandte Algebra für Informatiker (B.I. Wissenschaftsverlag, Mannheim, 1987), Floyd/Beigel: Die Sprache der Maschinen (Intern. Thomson Publ., Bonn, Albany, 1996),
Hopcroft/Ullman: Introduction to Automata Theory, Languages, and Computation (Addison-Wesley 1979),
Broy: Informatik-Eine grundlegende Einführung, Band 2 (Springer 1998),
Aho/Sethi/Ullman: Compilers-Principles, Techniques and Tools (Addison-Wesley 1986),
Periodizität:
jährlich zum SS
Eignung:
Geeignet für Lehramtsstudierende, Nebenfachstudierende.
Stichworte:
Endlicher Automat, Kellerautomat, Nichtdeterminismus, reguläre Menge, rationaler Ausdruck, kontextfreie Grammatik, LR(k)-Grammatik, formale Sprache, Ableitungsbaum,