Abteilung Formale Konzepte

Universität Stuttgart
Institut für Informatik
Breitwiesenstr. 20/22
D-70565 Stuttgart
 Lageplan
Stadtplan
Abteilung
Institut
Fakultät
Universität

Vorlesung: Theoretische Informatik III (ST)

Pflichtveranstaltung, 4. Semester (ST)
Vorlesung3V+1Ü
Dozenten:Claus
Termine:Mo08.30 bis 10.00in V20.02
Fr08.30 bis 10.00in 1.034 14-tg.

Beschreibung

Im Mittelpunkt stehen Semantik und Komplexität und deren Bedeutung für praktische Probleme..
  1. Einfache Berechnungsmodelle: Turingmaschinen (Wiederholung), Registermaschinen, k-Band-Turingmaschinen, wechselseitige Simulation.
  2. Komplexitätsklassen: Konstanten, Hierarchiesätze, wichtige Klassen.
  3. Vollständigkeit: Reduzierbarkeit, hart, vollständig, SAT, SAT(3), Clique, HC, TSP, Rucksack, Färbung, Beweise durch Reduktionen, PSPACE.
  4. Operationale Semantik: Die Sprache IMP, Transitionssysteme, Schrittsemantik, Ergebnissemantik.
  5. Denotationale Semantik: semantische Bereiche und Funktionen, Fixpunktsatz, Äquivalenz zur operationalen Semantik.
  6. Axiomatische Semantik: Zusicherungen, Gültigkeit, Regelsystem nach Hoare, schwächste Vorbedingung.
  7. Ergänzungen: Compilersemantik, paralleles Sortieren, großes Beispiel.

Anmerkungen

Der Stoff wird aus Beispielen heraus entwickelt.

Voraussetzungen

Logik und Theorie für Softwaretechnik I

Wichtiges

Die Literatur ist wegen der Breite des Stoffes recht verstreut in verschiedenen Lehrbüchern zu finden.

Literatur

Ingo Wegener: Theoretische Informatik Teubner-Verlag, 1993
Impressum
Last modified: Wed May 5 17:54:31 MET DST 1999