Algorithmen-, Rekursions- und Komplexitätstheorie

Es wird nun doch noch ein 9. (Sonder)prüfungstermin am 8.Juli angeboten (siehe Prüfungstermine, unten)
Ergebnisse zur 8. Vorlesungsprüfung vom 15.06.05 [ hier]
Einsichtnahme:
in den Sprechstunden, d.h., jeweils Montag 10:30-12:30 (sofern nicht vorlesungsfrei)
bei Chris Fermüller
oder nach Vereinbarung, per Email an chrisf@logic.at
Kopien der Overhead-Folien zu den ersten 2-3 Vorlesungseinheiten als [ Postscript-Datei ] und als [ PDF-Datei ]
Einige ausgewählte zusätzliche Folien aus der Vorlesung sind als [ JPEG-Dateien ] zugäglich.

* zum SS2003 (oder früheren Semestern) *

Ältere Prüfungsergebnisse:

Geben Sie Ihre Matrikelnummer ein und klicken Sie auf "Suchen", um Ergebnisse von Prüfungen und Tests abzufragen (ohne Matrikelnummer erhalten Sie eine Aufstellung der vorhandenen Ergebnislisten).

Matrikelnummer:
Angaben zur 4. Vorlesungsprüfung vom 28.1.03 als [ Postscript-Datei ] und als [ PDF-Datei ]
Angaben zur 3. Vorlesungsprüfung vom 2.12.02 als [ Postscript-Datei ] und als [ PDF-Datei ]
Angaben und Lösungen zum 2. Test (SS 2002) als [ Postscript-Datei ] und als [ PDF-Datei ]
Angaben und Lösungen zur 1. Vorlesungsprüfung (SS 2002) (17.6.02) als [ Postscript-Datei] und als [ PDF-Datei]
Einige weitere zusätzliche Folien zur Vorlesung sind als [ JPEG-Dateien ] zugänglich.
Angaben und Lösungen zum 1. Test (SS 2002) als [ Postscript-Datei ] und als [ PDF-Datei ]

Leitfragen zum Inhalt der Lehrveranstaltung

Was ist ein "Algorithmus"?
Was heißt: ein Problem ist (prinzipiell) algorithmisch lösbar?
Gibt es eine maschinenunabhängige Charakterisierung?
Welche mathematische Grundkonzepte gibt es hierfür?
Was kann man über nicht-lösbare Probleme sagen?
Wie zeigt man, dass ein konkretes Problem unlösbar ist?
Welche "natürlichen" Klassen und Hierachien ergeben sich,
wenn man Probleme nach ihrer Lösungskomplexität ordnet?

Stichworte zum Inhalt (für Cognoscenti):

Turingmaschinen, Registermaschinen, ein allgemeines Maschinenmodell, Simulation von Maschinen, (partiell-)rekursive Funktionen, Hauptsatz der Berechenbarkeit (Turing-berechenbar = RM-berechenbar = partiell rekursiv), Church'sche These, universelle Programme und Gödelnummerierungen, rekursive Aufzählbarkeit und (Un-)Entscheidbarkeit, Reduktion von Problemen, Rekursionstheorem, Grundbegriffe der (strukturellen) Komplexitätstheorie

Vorlesungs- und Übungstermine

Die Lehrveranstaltung hat im SS 2004 zum letzten mal stattgefunden.
Siehe den Äquivalenzkatalog zum Diplomstudium Informatik (881) für Informationen zu alternativ absolvierbaren Lehrveranstaltungen.

Vorlesungsunterlagen

Das Vorlesungsskriptum zum SS2004 ist gegenüber den Vorjahren (nahezu) unverändert.
Es hat etwas über 100 Seiten und kostet 8.- EURO.
Restexemplare sind zu den Sekretariatszeiten am Institut erhältlich.
Kopien der Overhead-Folien zu den ersten 2-3 Vorlesungseinheiten als [ Postscript-Datei ] und als [ PDF-Datei ]
Einige ausgewählte zusätzliche Folien aus der Vorlesung sind als [ JPEG-Dateien ] zugäglich.

Korrekturen zur aktuellen Ausgabe des Vorlesungsskriptums (SS 2004)

S. 37, Beispiel 5.8 1): zwischen "(0,1)" und D(mü minus)" fehlt das Zeichen für "ist nicht Element von"
S. 64, letzter Absatz: "nü(x)" ist jeweils durch "nü^-1(x)" [Umkehrfunktion von nü] zu ersetzen
S. 73, letzte Zeile: "lambda m [sigma(m,x)]" -> "lambda x [sigma(m,x)]"
S. 75, 4. Zeile im Beweis von Satz 9.4: "y aus N" -> "y aus N^n"

Korrekturen zu älteren Ausgaben des Vorlesungsskriptums

S. 20, Zeile "(H_2)" Ende: es fehlt "nü" unter der Klammer
S. 25, Beispiel 3.3, Zeile "4)" ganz am Ende: "...BuB^omega" -> "...B^omega"
S. 27, vorletzte Zeile: "s'(2)=2" -> "s'(2)=3"
S. 33, Ergänzung zu Definition 5.1: "x" steht für ein Tupel von einzelnen Zahlen "(x_1,..,x_i,..,x_n)"
S. 36, letzte Zeile von Beispiel 5.5: "Pr(1," -> "Pr(C^0_1,"
S. 36, Beispiel 5.6 a): "min1 = Pr(C^1_0,I^2_1)" -> "min1 = Pr(C^0_0,I^2_1)"
S. 36, Beispiel 5.6 b): "x minuspunkt 0 = 0" -> "x minuspunkt 0 = x"
S. 37, Beispiel 5.8 1): zwischen "(0,1)" und D(mü minus)" fehlt das Zeichen für "ist nicht Element von"
S. 50 unten: vor "pi(rho_w)" fehlt ein Programmstück, das unter Verwendung von pi(f) die Eingabetuppel (x,r) in (x,0,f(x),r) umsetzt
S. 64, ab "Die Übersetzung ..." bis zum Ende der Seite: Ersetze "nü" jeweils durch "nü^-1" (ausser es steht bereits "nü^-1")
S. 68, mitte: "Res" -> "ReS"
S. 73, letzte Zeile: "lambda m [sigma(m,x)]" -> "lambda x [sigma(m,x)]"
S. 74, drittletze Zeile: "sigma^n_1 sigma^1_n" -> "sigma^1_n sigma^n_1"
S. 75, 4. Zeile im Beweis von Satz 9.4: "y aus N" -> "y aus N^n"
S. 80, drittletze Zeile: Streiche das Negationszeichen vor "T(m,k_1,k_2)"
S. 81, Ergänzung zu Definition 10.2:
Entscheidbare Mengen nennt man auch rekursiv. (Wie z.B. am Ende des Beweises von Satz 10.3.)
S. 82, letzte Zeile "f(x)=1" -> "g(x)=1"
S. 85, Beispiel 10.3, dritte Zeile: `g(x,y)=0' -> `g(x,y) ungleich 0'
S. 85 und 86, (Hinweis auf) Satz 10.5: "10.3.1" -> "10.5.1", "10.3.2" -> "10.5.2"
S. 88, vorletzte Zeile im Beweis von Satz 10.7: 'T(x,x,y)' -> 'T(x,x,z)'
S. 88 und 89, jeweils oben (Beginn des Beweises): "Satz 10.4" -> "Satz 10.6"
S. 92, Beispiel 11.4: das zweite "h" in "h(sigma^2_1(x,y),h(x,y minuspunkt 1))" sollte "h_1" heissen
S. 93, zweite Zeile: "phi^(3)_u(i)(x,phi^(2)_i(y minuspunkt 1))" -> "phi^(3)_u(i)(x,y,phi^(2)_i(x,y minuspunkt 1))"
S. 97, Tippfehler im Absatz nach Definition 12.1:
"Man kann durch ein Diagonalverfahren (ähnlich wie beim Beweis der Unentscheidbarkeit ......... (Entscheidungsprobleme)"

Melden Sie weitere gefundene Fehler bitte an chrisf@logic.at
(Ich danke Christian Ploninger, Anton Michlmayr und insbesonders Lorenz Froihofer.)

Übungsablauf

Vorrechnen und Besprechen von Beispielen durch den Vortragenden.
Keine Anwesenheitspflicht.

Übungsunterlagen

Das Übungsskriptum zum SS2004 ist gegenüber dem Vorjahr unverändert
Es enthält, unter anderem, so gut wie alle für die Übungstests und die Vorlesungsprüfung relevanten alten Test- und Prüfungsbeispiele
Es hat etwas mehr als 90 Seiten und kostet 7.- EURO
Restexemplare sind zu den Sekretariatszeiten am Institut erhältlich.

Korrekturen zum Übungsskriptum des SS 2002

S. 13, Aufgabe 1.29: Ersetze `URM^2_1' durch `URM^1_1'
S. 30, Aufgabe 2.23: Ersetze `x' durch `n' in der Definition von alpha
S. 33, Aufgabe 2.42: Ergänze: `In Abweichung von Definition 5.5 des Vorlesungsskriptums kann dabei der Operator "mu" auch auf nicht-totale Funktionen anwendet werden.'
S. 36, Aufgabe 2.59: 'E(minus , I^3_1,I^3_3)' -> 'E(minus ; I^3_1,I^3_3)'
S. 37, Aufgabe 2.61: Ergänze: `Sie dürfen - in Abweichung von Definition 5.4 des Vorlesungsskriptums - dabei den Operator Pr auch auf nicht-totale Funktionen anwenden.'
S. 39, Aufgabe 2.73 und S. 92 (Lösung zu 2.73): In der Definition von h sind `undefiniert' und `3' zu vertauschen.
S. 55, Lösung zu 1.12 b): `x<2' -> `y<2' und 'x sonst' -> `y sonst'
S. 65, Lösung zu 1.50 hat einige Tippfehler:
Zeile 19 (zweite Hauptschleife) des Programms: `t3' -> `t4'
Zeile 21: `t4' -> `t5'
Zeile 23: `S1' -> `S2'
Zeile 24: `3^2b' -> `9y'
S. 66, Lösung zu 1.51, 5. Zeile des Programms: `t_5' -> `t_1'
S. 75, Lösung zu 1.67 b), Programm Sim(ord_ijk): vor `goto True' fehlt `while not t_hk do S_hk;'
ausserdem ist auch h ein anfangs leeres Hilfsregister
S. 76, Programm Sim(t_i): Sprungmarken False und True sind vertauscht
S. 91, Lösung zu 2.67, drittletzte Zeile: `...+ n - 1' -> `...+ (n - 1)'
S. 92, siehe Korrektureintrag zu Seite S.39, oben

Dank an Markus Bauer, Anton Michlmayr, Roman Morawek, Julia Ogris und Claus Scheiblauer.

Melden Sie weitere gefundene Fehler bitte an chrisf@logic.at

Lernbehelf: Simulationsprogramme

Es gibt zahlreiche Simulatoren zu unterschiedlichen Versionen von Turingmaschinen im Internet.
Folgende Simulationsprogramme - für Registermaschinen (RM) bzw. Turingmaschinen (TM) - wurden speziell für diese Lehrveranstaltung von Studenten im Rahmen von Praktika entwickelt.

TM- und RM-Maschinensimulatoren:

Partiell rekursive Funktionsausdrücke:

'PRIMOP' ein Programm zur Auswertung von Definitionen partiell rekursiver Funktionen(wie in der Vorlesung):

Beurteilung

Vorlesung

Die Beurteilung erfolgt aufgrund einer schriftlichen Prüfung. Für eine positive Note sind 25 der maximal 55 Punkte erforderlich.
Der Notenschlüssel:

00-24 Punkte: nicht genügend
25-32 Punkte: genügend
33-41 Punkte: befriedigend
42-49 Punkte: gut
50-55 Punkte: sehr gut

Übung

Die Beurteilung erfolgt aufgrund zweier schriftlicher Tests, bei denen jeweils 50 Punkte erreichbar sind. Für eine positive Note sind in Summe 51 der insgesamt 100 Punkte erforderlich.
Der Notenschlüssel:

00-50 Punkte: nicht genügend
51-63 Punkte: genügend
64-76 Punkte: befriedigend
77-89 Punkte: gut
90-100 Punkte: sehr gut

Beim Nachtragstest kann einer oder beide Tests wiederholt oder nachgemacht werden. Zur Teilnahme sind alle StudentInnen berechtigt, unabhängig davon, ob sie bei keinem, einem oder beiden der regulären Tests bereits angetreten sind. Zur Berechnung der Endnote wird das jeweils bessere Ergebnis in jedem der beiden Stoffgebiete (1./2.Test) herangezogen. Es gibt nur einen Nachtragsteststermin (siehe Testtermine).

Prüfungstermine (VO)

zum SS 2004 (oder früheren Semstern)

1. Termin: war Mittwoch, 30. Juni 2004, 10:30-12:30
2. Termin: war Mittwoch, 20. Oktober 2004, 15:00-17:00
3. Termin: war Freitag, 26. November 2005, 15:15-17:15
4. Termin: war Freitag, 21. Jänner, 15:00-17:00
5. Termin: war Donnerstag, 3. Februar 2005, 11:00-13:00
6. Termin: war am Donnerstag, 24. März 2005, 11:00-13:00
7. Termin: war am Freitag, 15. April, 2005, 11:00-13:00
8. Termin: war am Mittwoch, 15. Juni 2005, 15:00-17:00
9. Termin: ist am Freitag, 8. Juli 2005, 11:00-13:00
Anmeldung (per Mail an chrisf@logic.at) unbedingt erforderlich!
Ort: Seminarraum E185/2

Sämtliche Unterlagen dürfen verwendet werden.

Lichtbildausweis mitbringen!

Testtermine (UE)

1. Test: war Mittwoch, 21.4.2004, 14:45 - 15:45
2. Test: war Dienstag, 29. Juni, 2004, 12:45-13:45
Nachtragstest (1. und 2. Test): war Freitag, 22. Oktober, 12:15-14:15,

Für die Tests ist keine Anmeldung erforderlich.

Sämtliche Unterlagen dürfen verwendet werden.

Lichtbildausweis mitbringen!

Hinweis zur Zeugnisausstellung

zur Übung

Die Ausstellung des Übungszeugnisses erfolgt grundsätzlich erst nach dem Nachtragstest (im Herbst) (Ausnahme: "sehr gut" schon vor Nachtragstest.)
Wenn Sie das Zeugnis schon davor (unmittelbar nach der Einsichtnahme zum 2. Test) benötigen, so teilen Sie dies bitte rechtzeitig (per email an Chris Fermüller) mit.

zur Vorlesung

Die Zeugnisaustellung erfolgt grundsätzlich nach der jeweiligen Einsichtnahme zum Prüfungstermin.
Wenn Sie das Zeugnis besonders rasch benötigen, so teilen Sie dies bitte rechtzeitig (per email an Chris Fermüller) mit.

Begleitlektüre

Es gibt unzählige Lehrbücher zum Themengebiet; zumeist in englischer Sprache. Voraussetzungsniveau, Notationen und Auswahl der präsentierten Resultate unterscheiden sich jedoch oft erheblich vom Skriptum.

Ein als Begleitlektüre und zur Vertiefung brauchbares, leicht zugängliches und (leider sehr) deutsches Buch ist:

Schnorr, Claus P.: Rekursive Funktionen und ihre Komplexität
Stuttgart : Teubner, 1974. - 191 S.
Leitfäden der angewandten Mathematik und Mechanik 24,
Teubner Studienbücher : Informatik
Literaturverz. S. [185] - 188 ISBN 3-519-02322-9 (1974)

5 Exemplare in der Lehrbuchsammlung der TU-Bibliothek vorhanden (Signatur: 0400 Fh Lb / MAT:034 SCHNORR / 98706 I.24).
Weitere Exemplare in anderen Bereichen der Bibliothek. (Siehe Online-Katalog der TUB.)

(Das Buch ist beim Verlag nicht mehr lieferbar)