Vorlesung Ausgewählte Kapitel der Komplexitätstheorie

Sommersemester 2005

PD Dr.rer.nat.habil. Karl-Heinz Niggl

(Sprechzeiten: Mittwoch, 11-13 Uhr)

Ausgewählte Kapitel der Komplexitätstheorie

Vorlesung

Dienstag, 11:00 Uhr-12:30 Uhr, ZHS 201

Die Zusatzübung findet wie gewünscht am Mittwoch,dem 1.6.05, in der Zeit von 15⁰⁰ bis 16³⁰ im Raum Sr Oe 404 statt.

Beginn: 5. April 2005

Für: Studierende der Informatik und Mathematik im Hauptstudium

Scheinerwerb: Fachgespräch

Voraussetzungen: Kenntnisse in Komplexitätstheorie (Vorlesung im 5.Semester) sind hilfreich, aber nicht notwendig;mathematisches Verständnis

Inhalt:

Stack- und Loop-Programme und ihre Komplexität

Literatur

( wird schrittweise ergänzt)

Dokumente zur Vorlesung

Stackprogramme:
Stackprogramme, μ-Maß, Beschränkungstheorem und BASE BOUNDING für Core-Programme, RANK REDUCTION, FLATTENING, BOUNDING; Thm: CHARACTERISTERUNG

Rekursion mit Parametersubstitution

Die Ackermannschen Zweige:
Monotonie-Eigenschaften, Abschätzung, Wachstum und Anfangsfälle

LOOP-Programme:
LOOP-Programme nach Meyer/Ritschie
Beispiele und Lemma: Primitiv rekursive Funktionen sind LOOP-berechenbar

Induktive Definitionen

Übungsblätter

Übungsblatt 3
(Besprechung: 05.07.2005)

Übungsblatt 2

Übungsblatt 1