Algorithmen und Komplexitätstheorie

  1. Vorlesung:

    Algorithmen und Komplexitätstheorie

  1. LV-Leiter:
    Univ.-Prof. DDipl.-Ing. Dr. Stefan Rass
    Termin:
    Di, 09:30-11:00, V.1.01
    Ablauf:
    LV-Modalitäten, ZEUS-Webseite
    Downloads
    RM-Simulator
    Aktuelles:
    Beginn der Lehrveranstaltung: 06.10.2015, 10:00, V.1.01

    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, HS 4 (genaue Infos: siehe ZEUS-Webseite)
    Vorbesprechung am 15.10.2015
    Tutorium:
    622.505 (Fabian Schober): MO 14:00-16:00, E.1.42, ZEUS LV-Seite
    Ablauf:
    LV-Modalitäten