Algorithmen und Komplexitätstheorie

  1. Vorlesung:

    Algorithmen und Komplexitätstheorie

  1. LV-Leiter:
    Univ.-Prof. DDipl.-Ing. Dr. Stefan Rass
    Termin:
    Di, 08:30-10:00, S.2.42
    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: 02.03.2020
  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:
    Mi, 8:30-10:00, N.1.04; für laufende Infos, siehe ZEUS-Webseite)
    Vorbesprechung am 09.03.2020
    Ablauf:
    LV-Modalitäten, ZEUS-Webseite
    Kreuzellisten:
    je 50% der Beispiele auf den Übungsblättern 1-6 und 7-12