Kursüberblick

Personal

Kurs-Koordinator:

Peter Riegler

Kurstitel

Theoretische Informatik

Vorlesungstermine

Eine Vorlesung ist jener Vorgang, bei dem die Notizen des Lehrers zu Notizen des Schülers werden, ohne dass sie den Geist der beiden passieren. (Mortimer J. Adler)

Dieser Kurs ist keine Vorlesung im traditionellen Sinn! Die Zeiten, in denen Professoren in der Lehrveranstaltung Bücher vorlesen mussten, sind eigentlich seit der Erfindung des Buchdrucks vorbei. Unsere Treffen im Hörsaal dienen nicht der Erstvermittlung des Stoffes, sondern der Klärung Ihrer Fragen. Die Erstvermittlung erfolgt durch Ihr Selbststudium mittels zur Verfügung gestellter Lehrtexte und begleitender Übungen.

Bzgl. Termine siehe http://www.ostfalia.de/cms/de/i/termine_plaene.html

Sprechstunden

siehe http://public.rz.fh-wolfenbuettel.de/~riegler/

Bezüglich Fragen zu elektronischen Übungsaufgaben, verwenden Sie bitte das online-Diskussionsforum im Kurs. Klicken Sie dazu auf die Sprechblase direkt unterhalb der Übungsaufgabe. So wird jeweils unmittelbar der richtige Kontext hergestellt.

Für direkte Nachrichten an mich verwenden Sie bitte ebenfalls das kursinterne E-mail-System. Verwendenen Sie in jedem Fall für Ihre Nachricht eine treffende Formulierung in der Betreff-Zeile, nicht einfach "Theoretische Informatik" oder "Vorlesung". Sie tragen damit dazu bei, dass ich Ihre Anfrage zügig beantworten kann, denn ich bekomme täglich sehr viele E-mail-Nachrichten.
Beachten Sie, dass ich fachliche Fragen und Fragen von allgemeinem Interesse für alle Kursteilnehmer nur im Rahmen der online-Foren beantworten werde. Ein anderes Vorgehen wäre unökonomisch und unfair.

Prüfungsinformationen

Während dieses Kurses sollen Sie die Fähigkeiten erwerben, die Sie im Dokument "Lernziele" beschrieben finden. Die Prüfungsaufgaben der Klausur überprüfen das Erreichen dieser Lernziele. Details zu den Prüfungsmodalitäten werden in der ersten Lehrveranstaltung bekanntgegeben.

Einzig erlaubtes Hilfsmittel für die Klausur: Zwei DIN A4-Blätter handgeschriebene Notizen. Ein Blatt hat zwei Seiten.

Die nachfolgende Auflistung nennt sehr detailliert fachliche Ziele der Veranstaltung, nicht jedoch überfachliche und andere Lernzeile (siehe Lernziel-Dokument). Die Auflistung dient hier vorrangig der Beschreibung der Inhalte der Veranstaltung.

Formale Sprachen
- Begriffe Alphabet, Wort, Sprache, leeres Wort definieren können.
- Alphabetpotenzen, Wortkonkatenationen, Wortpotenzen, Transpositionen sicher bestimmen können.
- Sprachoperationen Komplement, Konkatenation, Potenz, Kleene-Abschluss, Differenz, Vereinigung, Durchschnitt, Transposition sicher auf gegebene Sprachen anwenden können.
- Algebraische Eigenschaften dieser Sprachoperationen kennen.
- Sprachen nach der in der Informatik gebräuchlichen Sprachtypisierung klassifizieren können.
- Die in der Informatik gebräuchliche Sprachtypisierung erklären können.
- Akzeptierende Maschinenart zu einem gegebenen Sprachtypus angeben können.
- Zu jedem Sprachtypus charakteristische Beispielsprachen benennen können.
- Schlüssig begründen können, zu welchem Sprachtypus eine gegebene Sprache gehört.
- Pumping Lemmata für reguläre bzw. kontextfreie Sprachen kennen.
- Pumping Lemmata anwenden können, um zu begründen, dass eine Sprache nicht regulär bzw. kontextfrei ist.
- Abgeschlossenheitseigenschaften von Sprachen anwenden können.

Grammatiken
- Definierende Elemente einer Grammatik benennen können.
- Beschreiben können, welche Konzepte bei der Sprachbeschreibung durch Automaten bzw. Grammatiken (und bei regulären Sprachen zusätzlich durch reguläre Ausdrücke) jeweils im Vordergrund stehen.
- Gegebene Worte einer Sprache aus der sie beschreibenden Grammatik ableiten können.
- Die definierenden Besonderheiten von regulären, kontextfreien und kontextsensitiven Grammatiken benennen können.
- Eine gegebene Grammatik korrekt klassifizieren können (regulär, kontextfrei etc.)
- Konkrete Beispiele zu regulären, kontextfreien, kontextsensitiven Grammatiken benennen können.
- Konkrete Beispiele für Sprachen nennen können, die
/ regulär, aber nicht kontextfrei
/ kontextfrei, aber nicht regulär
/ deterministisch kontextfrei, aber nicht kontextsensitiv
/ kontextsensitiv, aber nicht deterministisch kontextfrei
/ kontextsensitiv, aber nicht kontextfrei
/ nicht kontextsensitiv
sind.
- Parse-Bäume zu gegebenen Ableitungen skizzieren können.
- Sprache, die durch eine Grammatik generiert wird, als Menge formulieren können.

Reguläre Ausdrücke
- Definierende Elemente von regulären Ausdrücken benennen können.
- Endlichen Automaten zu gegebenen regulären Ausdruck konstruieren können.
- Von einem endlichen Automaten erkannte Sprache durch regulären Ausdruck beschreiben können.

Automaten
- Definierende Elemente von endlichen Automaten, Kellerautomaten, Turing Maschinen benennen können.
- Unterschied zwischen Determinismus und Nichtdeterminismus erklären können.
- Erklären können, wie nichtdeterministischer Automat arbeitet.
- An formaler Automatenspezifikation erkennen können, welche Art von Automat vorliegt.
- An formaler Automatenspezifikation erkennen können, ob Automat deterministisch oder nichtdeterministisch ist.
- Beschreiben können, wodurch für eine gegebene Automatenart eine Konfiguration definiert wird.
- Formal den Begriff der von einer Automatenart erkannten Sprachklasse definieren können.
- Formal den Begriff der Äquivalenz von Automaten definieren können.
- Übergangsgraphen eines Automaten aus gegebener Übergangsfunktion skizzieren können.
- Übergangsfunktion eines Automaten aus gegebenen Übergangsgraphen konstruieren können.
- Zusammenhang zwischen (Nicht-)Determinismus und Übergangsfunktion eines Automaten erkläutern können.
- Konfigurationsfolgen angeben können.
- Erkennende endliche Automaten bzw. Kellerautomaten zu gegebener Sprache konstruieren können.

Endliche Automaten
- Komplexität von DFAs und NFAs angeben können.
- NFAs in DFAs konvertieren können.
- Reguläre Ausdrücke in NFAs umwandeln können.
- FAs in reguläre Ausdrücke umwandeln können.
- Minimalautomaten konstruieren können.

Kellerautomaten (Push Down Automata)
- Definierende Elemente von Kellerautomaten benennen können.
- Erklären können, warum Kellerautomaten kontextfreie Sprachen erkennen.

Turing-Maschine
- Bedeutung von Turing-Maschinen bzgl. Berechenbarkeit benennen können.
- Terminierungsarten von Turing-Maschinen benennen können und deren Unterschiede erklären können.
- Gemeinsamkeiten von allgemeinen Turing-Maschinen mit und Unterschiede zu linear beschränkten Automaten benennen und erklären können.
- Aussage der Churchen Hypothese wiedergeben können.
- Zusammenhang zwischen Algorithmusbegriff und Turing-Maschinen erklären können.

Entscheidbarkeit
- Begriff Entscheidbarkeit definieren können.
- Zusammenhang zwischen Entscheidbarkeit und Turing Maschinen erklären können.
- Beispiele für entscheidbare und nichtentscheidbare Sprachen benennen können.

Lehrbuch

Die Lehrveranstaltung basiert auf
Michael Sipser: Introduction to the Theory of Computation, Thomson Course Technology (zweite Auflage oder höher)
Dieses Buch sollten Sie sich also besorgen.

Zur Ergänzung empfehle ich
R. Socher: Theoretische Grundlagen der Informatik, Fachbuchverlag Leipzig
und den Klassiker
Hopcroft, Motwani, Ullman: Introduction to Automata Theory, Languages, and Computation, Addison Wesley