Universität / IfI-HomePage / A&S-HomePage


Automaten und Sprachen

Lehrangebot Sommersemester 1996


Überblick über die Lehrveranstaltungen Sommersemester 1996


Automaten und Formale Sprachen

Gerber, S.

Teilnehmerkreis:
obligatorisch für Dipl.Inf. 2. Semester Grundstudium, Magister-HF ab 5.Semester

Übersicht:

  1. Semiotische Grundbegriffe

  2. Endliche Automaten

  3. Grammatiken und Formale Sprachen

  4. Chomsky-Hierarchie

  5. Reguläre Sprachen und endliche Automaten

  6. Kontextfreie Sprachen und Kellerautomaten

  7. Aufzählbare und entscheidbare Sprachen

  8. Entscheidungsprobleme

Literatur(Auswahl):

Erwartete Vorkenntnisse: Vorlesung Mengentheoretisch-algebraische Grundlagen aus Grundkurs Theoretische Informatik

Scheinvergabe: Lösung von Übungsaufgaben

Sonstiges: Skript-Neufassung in Vorbereitung


Formale Semantik

Hartwig, R.

Teilnehmerkreis:
obligatorisch für Informatikstudenten und Magisterstudenten mit Hauptfach Informatik im Hauptstudium und für Lehramtskandidaten im 4. Semester, wahlobligatorisch und empfohlen für alle Studenten mit Nebenfach Informatik

Übersicht:

In der Vorlesung werden verschiedene Methoden der Semantikdefinition von Programmiersprachen gegenübergestellt. Je nach dem Ziel der formalen Semantik-beschreibung sind unterschiedliche Methoden zweckmäßig. Ausführlich werden die operationale Methode und die denotationale Methode der Semantikdefinition behandelt. Weitere Methoden wie z.B. die algebraische Semantik oder die axiomatische Semantik werden nur in ihrem Ansatz behandelt. Sie sind Gegenstand anderer Vorlesungen (u.a. desselben Lesenden).

Gliederung:

1. Einführung
- Syntax, Semantik und Pragmatik von Programmiersprachen
- Methoden der Semantikdefinition
2. Operationale Semantik
- Eine abstrakte Maschine
- Semantikdefinition für eine Beispielprogrammiersprache
- Semantik eines Beispielprogramms
3. Denotationale Semantik
- Syntaktische und semantische Bereiche
- Fixpunktgleichungen
- Vollständige Halbordnungen und Fixpunktsatz
- Vollständige Halbordnungen und denotationale Semantik

Alle vorgestellten Methoden werden an Hand von Beispielen demonstriert.

Literatur:

Erwartete Vorkenntnisse: Kenntnis einer höheren Programmiersprache, mengentheoretisch-algebraische Grundkenntnisse

Scheinvergabe: nach Vorlesungsbesuch, evtl. abschließendes Einzelgespräch (Testat)


Funktionale Programmierung I

Gerber, S.

Teilnehmerkreis:
Wahloblig. Vorlesung in den Schwerpunkten Theoretische und Praktische Informatik, Lehramt ab 4.Semester, Magister-HF im Hauptstudium

Übersicht:

1.   Funktionales Paradigma
1.1. Grundkonzepte
1.2. Funktionale Sprachen

2. Funktionale Berechnungsmodelle 2.1. Lambda-Kalkül 2.2. Term- und Graphersetzungssysteme 2.3. Algebraische Spezifikation

3. Implementierungen 3.1. Miranda 3.2. Clean

Literatur (Auswahl):

Erwartete Vorkenntnisse : Vorlesungen des Grundkurses Theoretische und Praktische Informatik

Scheinvergabe: Mündliche Prüfung bzw. Praktische Übungen

Sonstiges: Skript soll erstellt werden


Grundlagen der Programmverifikation

Hartwig, R.

Teilnehmerkreis:
Studenten der Informatik und Mathematik im Hauptstudium, die sich für Fragen der Theoretischen Informatik interessieren

Übersicht:

Die Computerprogrammierung ist eine "exakte Wissenschaft" in dem Sinne, daß alle Eigenschaften eines Programms prinzipiell rein deduktiv aus dem Programmtext abgeleitet werden können. Im Widerspruch dazu steht allerdings die Praxis des Experimentierens mit "fertigen" Programmen ("Testphase"), um diese fehlerfrei (?) zu machen. Notwendig sind exakte Methoden der Programmdokumentation und Programmverifikation. Notwendig ist eine Programmiermethodologie, die sich auf Beweise - nicht auf das Testen - von Programmeigenschaften stützt.

Die Vorlesung führt in dazugehörige mathematische Grundlagen ein und stellt den Anschluß an die Literatur auf diesem Gebiet her.

Wesentliche Stichworte zum Inhalt der Vorlesung sind:

Korrektheit von Programmen, Axiomatische Semantik, HOARE-Logik, asserted programs, Prädikattransformer, COOK-Vollständigkeit.

Gliederung:

  1. Einleitung: allgemeiner Kalkülbegriff, grundlegende Begriffe und Bezeichnungen

  2. Formale Theorien für Programmiersprachen: Programmspezifikationen und Beweissysteme Beispiele

  3. HOARE-Logik für while-Programme: Geradeausprogramme, Vorbedingung, Nachbedingung, Ausdrucksfähigkeit, FLOYDsches Vorwärts-Zuweisungsaxiom, Behandlung der Iteration

  4. Ausblick: Indizierte Variablen, Blockstruktur

Literatur:

Erwartete Vorkenntnisse: Kenntnis einer höheren Programmiersprache Grundkenntnisse der mathematischen Logik

Teilnahmeschein: nach Vorlesungsbesuch

Sonstiges: Nach Abschluß der Vorlesung können interessierte Hörer das Vorlesungsskript erhalten.


Petri-Netze

Gerber, S.

Teilnehmerkreis:
Wahloblig. Kernvorlesung zur Theoretischen Informatik im HS Informatik-Diplom, Empfohlen für Magister-HF ab 5.Semester

Übersicht:

1.   Grundbegriffe
1.1. Bedingungen und Ereignisse
1.2. Systeme, Prozesse und Netze

2. Netz-Theorie 2.1. Automaten und Petri-Netze 2.2. Lebendigkeit, Sicherheit, Deadlocks 2.3. Netz-Sprachen

3. Anwendungen 3.1. Produktionssysteme 3.2. Schaltwerke 3.3. Kommunikationsnetze

Literatur(Auswahl):

Erwartete Vorkenntnisse: Grundkurs Theoretische Informatik einschließlich Automaten und Formale Sprachen

Scheinvergabe: Mündliche Prüfung

Sonstiges: Skript in Vorbereitung


09.04.1996