Algorithmen und Komplexität

Modulnummer:

1101630

Leistungspunkte:

6 ECTS

Lehrveranstaltungen:

  • Vorlesung Algorithmen und Komplexität (3 SWS)
  • Übung Algorithmen und Komplexität (1 SWS)

Prüfung:

Klausur (90 min) oder mündliche Prüfung (20 min)

Prüfungsvorleistungen:

Lösen von Übungsaufgaben

Inhalt:

Algorithmen:

  • Problem-, Algorithmusbegriff (RAM als Standardmodell des Algorithmenentwurfs)
  • Korrektheit, Zeitkomplexität im logarithmischen und uniformen Kostenmaß, O-Notation
  • Lehrbuchbeispiel Maximum-Sum-Contiguous-Subarray in Theorie und Praxis (Brute-Force, mit Preprocessing, Teile und Herrsche, Range-Tree, Greedy)
  • Lehrbuchbeispiel Longest-Common-Subsequence (Brute-Force, Dynamic Programming)
  • Schematische Einführung der Entwurfsmuster und darin genutzter Datenstrukturen:
    • Dynamische Programmierung (an Beispielen Rucksackproblem und TSP)
    • Greedy (am Beispiel MST mit jeweils Union Find und Fibonacci Heap)
    • Teile und Herrsche (am Beispiel Matrix-Multiplikation)

Komplexität:

  • Allgemeine untere Schranken mit Kreuzungsfolgen
  • Zeithierarchiesatz
  • Komplexitätsklassen P, NP und EXP
  • Turingreduktionen, Optimierungs- und Entscheidungsvarianten wichtiger Probleme  
  • Nicht-Deterministische Charakterisierung von NP
  • Das Problem P != NP
  • NP-Vollständigkeit, Polynomialzeitreduktion, Satz von Cook
  • Starke NP-Vollständigkeit, NP-Intermediate
  • Orakelklassen, Grenzen der Diagonalisierung
  • co-NP und dessen Beziehung zu NP, Polynomielle Hierarchie