Algorithmen und Komplexitätstheorie

  1. Vorlesung:

    Algorithmen und Komplexitätstheorie

  1. LV-Leiter:
    Univ.-Prof. DDipl.-Ing. Dr. Stefan Rass
    Termin:
    Di, 10:00-12:00, I.0.44
    Ablauf:
    LV-Modalitäten, ZEUS-Webseite
    Downloads
    RM-Simulator
    Aktuelles:
    Beginn der Lehrveranstaltung: 04.10.2016, 10:00, I.0.44

    Zugangscodes werden in der 1. VO-Einheit bekannt gegeben.

  1. Kapitel

    1. Organisatorisches
    2. Einführung und Überblick
    3. Rekursive Algorithmen
    4. Zahlen- und Matrizenmultiplikation
    5. Greedy-Algorithmen und Matroide
    6. Deterministische Komplexitätsklassen
    7. Nichtdeterministische Komplexitätsklassen
    8. Die Klasse NP
    9. Reduktionen und Vollständigkeit
    10. Orakel-Turingmaschinen und polynomiale Hierarchie
    11. Approximationsalgorithmen
    12. Probabilistische Algorithmen und Komplexitätsklassen
    13. Interaktive Beweissysteme
    14. Schaltkreiskomplexität
    15. Anhang: Turing-Maschinen


  1. Praktikum:

    Algorithmen und Komplexitätstheorie

  1. LV-Leiter:
    Univ.-Prof. DDipl.-Ing. Dr. Stefan Rass
    Termin:
    622.102: MI 12:00-13:30, V.1.07 und HS 4 (genaue Infos: siehe ZEUS-Webseite)
    Vorbesprechung am 05.10.2016
    Die Einheit am 11.01.2017 fällt aus (Besprechung der Beispiele in der LV-Einheit am 18.01.2017)
    Tutorium:
    622.105 (Christian Sitter): DO 08:30-10:00, I.2.57, ZEUS LV-Seite
    PR-Klausur
    gleiche Klausur (gleicher Termin) wie für die VO
    Ablauf:
    LV-Modalitäten
    Kreuzellisten:
    je 50% der Beispiele auf den Übungsblättern 1-6 und 7-12