[ LVAs 185/2 | Abteilung 185/2 | Institut 185 | Informatik | TU Wien | Server home page ]

Algorithmen-, Rekursions- und Komplexitätstheorie

Vorlesung (185.845, 2 stündig) & Übung (185.834, 1 stündig)

Vortragender: Chris Fermüller

Letzte Änderung: 20/6/2005 (CF)

Anregungen, Beschwerden und Fragen bitte an chrisf@logic.at.

Auf dieser Seite finden Sie

  • Aktuelles
  • Inhalt der LVA (Leitfragen, Stichworte)
  • verwandte LVAs
  • Vorlesungs- und Übungstermine
  • Vorlesungsunterlagen
  • Korrekturen zum Vorlesungsskriptum
  • Übungsablauf
  • Übungsunterlagen
  • Lernbehelf: Simulationsprogramme
  • Korrekturen zum Übungsskriptum
  • Beurteilung
  • Prüfungstermine (VO)
  • Testtermine (UE)
  • Hinweis zur Zeugnisausstellung
  • Hinweise zur Begleitlektüre

  • Aktuelles

    *** zum SS2004 ***


    *** zum SS2003 (oder früheren Semestern) ***


    Leitfragen zum Inhalt der Lehrveranstaltung

    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

    Verwandte und weiterführende LVAs:

    Siehe den Äquivalenzkatalog zum Diplomstudium Informatik (881) für Informationen zu alternativ absolvierbaren Lehrveranstaltungen.

    Vorlesungs- und Übungstermine


    Vorlesungsunterlagen


    Korrekturen zur aktuellen Ausgabe des Vorlesungsskriptums (SS 2004)

    Korrekturen zu älteren Ausgaben des Vorlesungsskriptums

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

    Übungsablauf


    Übungsunterlagen


    Korrekturen zum Übungsskriptum des SS 2002

    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:


    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)

    Sämtliche Unterlagen dürfen verwendet werden.

    Lichtbildausweis mitbringen!


    Testtermine (UE)

    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:

    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)


    [ LVAs 185/2 | Abteilung 185/2 | Institut 185 | Informatik | TU Wien | Server home page ]