Algorithmen und Komplexitätstheorie

  1. Vorlesung:

    Algorithmen und Komplexitätstheorie

  1. LV-Leiter:
    Univ.-Prof. DDipl.-Ing. Dr. Stefan Rass
    Termin:
    Mi, 12:00-14:00, I.0.43
    Beschreibung:
    Aufbauend auf der Einführung in die theoretische Informatik setzt dieser LV fort mit der Betrachtung von Design-Prinzipien für schnelle bzw. effiziente Algorithmen. Die Betrachtung liegt hierbei auf den Komplexitätsmaßen Zeit und Platz, sowie deren Wechselwirkungen. Wir analysieren ausgewählte Algorithmen im Hinblick auf deren Komplexität und betrachten allgemeine Prinzipien und Vorgehensweisen für deren Konstruktion.
    Ablauf:
    LV-Modalitäten, ZEUS-Webseite
    Aktuelles:
    Beginn der Lehrveranstaltung: 03.10.2017

    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:
    I.0.43 (u.a., genaue Infos: siehe ZEUS-Webseite)
    Vorbesprechung am 04.10.2017
    Ersatztermin: 21.12.2017, 10-12 Uhr, E.2.05 (LV am 13.12.2017 fällt aus)
    Ablauf:
    LV-Modalitäten, ZEUS-Webseite
    Kreuzellisten:
    je 50% der Beispiele auf den Übungsblättern 1-6 und 8-12