Grundlagen der theoretischen Informatik

Vorschlag R. Valk, M. Jantzen, C. Habel, D. Moldt, B. Farwer, C. Eschenbach vom 6.11.2003

Modul Theorie 1:

1. Formale Sprachen
   • Grammatiktypen
   • Automaten incl. Turingmaschinen
   • Entscheidbarkeit
2. Logik
   • mit der Perspektive: Logik als Formale Sprache
   • Semantik / Interpretation und semantische Begriffe (Tautologie, Äquivalenz, Folgerbarkeit)
   • Aussagenlogik und Prädikatenlogik
   • Reduktion gegenüber F1: Beweisverfahren/Resolution

Achtung: Das Curricularteam schlägt eine weiteres Pflichtmodul Theoretische Informatik vor

---

Vorschlag Jantzen

Umfang: 4 SWS Vorlesung + 2 SWS Übung

Voraussetzungen: Diskrete Mathematik

Präambel:

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. Auf die Nutzung mathematischer Begriffe und Modelle aus dem Pflichtmodul Diskrete Mathematik, wie auch die Berücksichtigung der Bezüge zur Anwendung beziehungsweise dem Ausbau dieser Konzepte, wie sie insbesondere im Pflichtmodul Algorithmen und Datenstrukturen bzw. dem Wahlpflichtmodul Logikprogrammierung vorkommt, wird Wert gelegt. Die Logik bildet die Grundlage für eine formale Semantik von sprachlichen Beschreibungen und Anweisungen in Programmier-, Spezifikations- und Repräsentationssprachen. Das Gebiet Automatentheorie behandelt einfache mathematische Modelle, die dem Computer und Algorithmen zu Grunde liegen. In dem Teilgebiet Formalen Sprachen wird der prinzipielle, strukturelle Aufbau von Programmier- und Spezifikationssprachen untersucht. Die Theorie der Berechenbarkeit untersucht die Abgrenzung zwischen effektiv Ausführbarem und prinzipiell niemals Möglichem. Die Komplexitätstheorie fragt danach, welchen rechnerischen Aufwand die Lösung gewisser Problem erfordert.

Lernziele

• Methoden der (strukturellen) Mathematik für informatische Probleme anwenden zu können,
• Definitionsprinzipien und Beweistechniken kennen zu lernen und diese in unterschiedlichen Bereichen anwenden zu k?nnen,
• formale Konzepte der Modellierung kennen- und einsetzen zu lernen,
• Determinismus und Nicht-Determinismus als fundamentale und nützliche Begriffe zu verstehen,
• die Grenzen der prinzipiellen M?glichkeiten mit Hilfe von theoretisch fundierten Aussagen benennen und einschätzen zu können.

Lehrinhalte

Aus F1 + F2 + F3 mit wesentlichen Verschiebungen in andere Module (in Klammern mit Angabe des Verschiebeziels. Diese Information soll in der Endfassung nicht mehr enthalten sein und die Beschreibung vereinheitlicht und geglättet werden):

(aus ex F 1: - Logik)

• Einführung in die Aussagenlogik: wohlgeformte Ausdrücke, Wahrheitswerte, Wahrheitstafeln, Belegungsfunktion
• Grundkonzepte der Semantik: Allgemeingültigkeit, Unerfüllbarkeit, Erfüllbarkeit und Folgerung
• nur nötigster Teil von: Beweistheorie und Ableitungssysteme für die Aussagenlogik: Schlussregeln, modus ponens,
• Normalformen, Literale und Klauseln,
• Syntax der Prädikatenlogik erster Stufe: Charakterisierung wohlgeformter Ausdrücke, Quantoren und Quantorenskopus, freie und gebundene Variablen, geschlossene Formeln

(Beziehung zwischen Semantik und Beweisverfahren , Vollständigkeit und Korrektheit von Beweisverfahren, Resolutionsverfahren, Hornklauseln Semantik der Prädikatenlogik: Modell, Interpretation, Allgemeingültigkeit, Unerfüllbarkeit, Erfüllbarkeit, Folgerung Kalkülbegriff, Ableitungssysteme und mechanisches Beweisen in der Prädikatenlogik: Normalformen, Skolemisierung, Resolutionsverfahren der Prädikatenlogik, Unifikation, allgemeinster Unifikator, Resolutionsverfahren, Beziehung zwischen Semantik und Ableitungssystemen ex F1 -> WPM Logikprogrammierung)

(aus ex F2: - Automaten und Formale Sprachen)

• Anwendungen der Beweismethoden, die teilweise im Modul Diskrete Mathematik vorgekommen sein sollen: Schubfachprinzip, Beweis durch Gegenbeispiel, indirekter Beweis, Induktion, Diagonalisierung, strukturelle Induktion
• Modelle einfacher Automaten: endlicher Automat, endlicher Transduktor, Kellerautomat,Determinismus versus Nichtdeterminismus
• Definitions- und Spezifikationsmethoden: Induktive und rekursive Definitionen über Mengen, Relationen, Funktionen, formale Sprachen, Operatoren, transitive Hüllen, Graphen und Bäume
• Rationale Ausdrücke, Syntaxdiagramme, reguläre und kontextfreie Chomsky-Grammatiken, Ableitungsbegriff, Ableitungs- und Syntaxbaum, Eigenschaften kontextfreier Sprachen, Grenzen der Ausdrucksfähigkeit
• Höhere Grammatiken: Chomsky Typ-0 und Typ-1 Grammatiken, Normalformen, Chomsky-Hierarchie (ex F3)
• Grundlagen kontextfreier Syntaxanalyse: Syntaxanalyse für deterministische und nicht-deterministische Grammatiken, top-down und bottom-up Verfahren

(aus ex F 3 - Berechenbarkeit und Komplexität)

• Entscheidbarkeit und Berechenbarkeit: primitiv rekursive und allgemein-rekursive Funktionen, Register- und Turing-Maschine als allgemeine, formale und besonders kompakte Algorithmusdefinition, Halteproblem und andere unentscheidbare Fragen
• Konkrete Komplexitätstheorie: Landausche Notation,
• Strukturelle Komplexitätstheorie: Darstellung von Problemen als Mengen, Zeit- und Platzkomplexitätsklassen, Beschleunigungs- und Kompressions-Sätze, Reduktionsbegriff, NP-Vollständigkeit
• Einfache Analyseverfahren konkreter Algorithmen: binäres Teilen, rekursive bzw. Teile und Herrsche Verfahren, Backtracking,.

(Grundlegende Entwurfstechniken: rekursive Algorithmen (z.B. Suchen, transitive Hüllen), Greedy-Methode (z.B. spannende Bäume), Teile und Herrsche (z.B. Sortieren, kürzeste Wege), dynamische Programmierung (z.B. Rundreiseproblem, lineare Optimierung), Backtracking und Branch and Bound ex F3 -> WPM Algorithmen und Datenstrukturen)

Literatur

U. Schöning: Logik für Informatiker, Spektrum (1995),

U. Schöning: Theoretische Informatik - kurzgefasst, Spektrum (2001),

Ingo Wegener . Theoretische Informatik -- eine algorithmische Einführung, B.G. Teubner Verlag, (1999),

J.E. Hopcroft/R. Motwani/J.D. Ullman: Einführung in die Automatentheorie, formale Sprachen und Komplexitätstheorie, Addison Wesley - Pearson Studium (2002),

K.R. Reischuk: Komplexitätstheorie, B.G. Teubner Verlag, (1999).

-- WolfgangMenzel -- 24 Sep 2003