Inhalt

Einleitung und Auffrischung  

• Einleitendes Beispiel
• Was sind ,,kombinatorische`` Algorithmen?
• Maschinenmodelle
• Komplexitätsmaße
  • Probleme und Funktionen
  • Wachstumsverhalten von Funktionen
  • Rekursionsgleichungen
    • Multiplikatoren
    • Charakteristisches Polynom
    • Erzeugendenfunktionen
    • Transformation des Definitions- bzw. Wertebereichs
• Höhere Datenstrukturen
  • Grundlegende Operationen
  • Suchbäume, balancierte Bäume
    • Höhenbalancierte Bäume
      • (a,b)-Bäume
      • Rot-Schwarz-Bäume
  • Binäre Suchbäume
    • Natürliche binäre Suchbäume
    • Höhenbalancierte binäre Suchbäume (AVL-Bäume)
  • Hashing
    • Grundlagen
    • Chainingverfahren
    • Hashing mit offener Adressierung
    • Universelles Hashing
    • Perfektes Hashing
  • Priority Queues
    • Binomial Queues (binomial heaps)
    • Fibonacci-Heaps
      • Die Datenstruktur
      • Amortisierte Kostenanalyse für Fibonacci-Heaps
  • Sich selbst organisierende Datenstrukturen
    • Motivation
    • Sich selbst organisierende lineare Listen
      • Sich selbst organisierende Binary Keys
      • Splay-Trees als Suchbäume
        • Einleitung
        • Die Splaying-Operation
        • Amortisierte Kostenanalyse der Splay-Operation
        • Wörterbuchoperationen in Splay-Trees
    • Weitere Arten von Datenstrukturen
  • Radix-basierte Priority-Queue
    • Buckets
      • 1-Level-Backets
      • 2-Level-Buckets
      • k-Level-Buckets
    • Von-Ende-Boas-PQ
    • Radix-Heaps
  • Union-Find-Datenstrukturen
    • Motivation
    • Union-Find-Datenstruktur
      • Intrees
      • Gewichtete Union (erste Verbesserung)
      • Pfad-Kompression mit gewichteten Union (zweite Verbesserung)
      • Erweiterung
• Selektieren und Sortieren
  • Einleitung
  • Der Blum-Floyd-Pratt-Rivest-Tarjan Selektions-Algorithmus
  • Randomisierter-Median-Algorithmus
  • Der Schönhage-Paterson-Pippenger-Median-Algorithmus
  • Eine untere Schranke für die Medianbestimmung
  • Eine bessere untere Schranke
  • Untere Schranke für (vergleichbasiertes) Sortieren
  • Bucketsort im Schnitt
  • Quicksort
• Minimale Spannbäume
  • Grundlagen
  • Traversierung von Graphen
    • DFS-Algorithmus
    • DFS-Algorithmus
  • Minimale Spannbäume
    • Konstruktion von minimalen Spannbäumen
    • Generischer minimaler Spannbaum-Algorithmus
  • Kruskals Algorithmus
  • Prim's Algorithmus, erste Variante
  • Prim's Algorithmus, zweite Variante
• Kürzeste Pfade
  • Grundlegende Begriffe
  • Das single-source-shortest-path-Problem
    • Dijkstra's Algorithmus
    • Dikstra's Algorithmus mit Radix-Heaps
    • Bellman-Ford-Algorithmus
  • Floyd's Algorithmus für das All-pairs-shortest-path-Problem
  • Digraphen mit negativen Kantengewichten
    • Grundsätzliches
    • Modifikation von Bellman-Ford-Algorithmus
    • Modifikation von Floyd's-Algorithmus
    • Der Algorithmus von Johnson
  • Zusammenfassung
  • Transitive Hülle
    • Min-Plus-Matrix-Produkt und Min-Plus-Transitive Hülle
    • Boolesche Matrixmuliplikation und Transitive Hülle
    • Der 4-Russen-Algorithmus für Boolesche Matrixmultiplikation
    • Transitive Hülle und DFS
  • Ein besserer Algorithmus für das All-pairs-shortest-distance (bzw. paths)-Problem in ungewichteten Digraphen
  • Ein Algorithmus für die transitive Hülle in Digraphen mit linearer erwarteter Laufzeit
  • Matrizenmultiplikation à la Strassen
• Matchings in Graphen
  • Grundlagen
  • Matchings maximaler Kardinalität in bipartiten Graphen
• Literatur
• Über dieses Dokument ...