Call me Algorithmensammelsurium

Ich habe eben meine Algorithmik-Prüfung mit ’ner 2 bestanden. Mein Prof meinte, ich hätte ja über einige Fragen sehr lange nachdenken müssen, aber er hat mich gleich mit der ersten Frage eiskalt erwischt. Nicht, dass ich nicht wüsste, was eine amortisierte Analyse ist – nur war es mir so grundlegend, dass ich nicht davon ausging, dass er sich auf dieses Thema so einschießt. Es war nämlich nicht so, dass ansonsten keine Algorithmen durch genommen worden wären:

  • Tiefensuche in Graphen – Struktur-Analyse:
    • Zusammenhangskomponente
    • Bizusammenhangskomponte
    • Starke Zusammenhangskomponente
    • Tarjan’s Algorithmus
    • Bipartite Färbung
    • Topologische Sortierung im DAG
  • Breitensuche im Graphen
  • Kürzeste Pfade im Graphen (mittels Relaxation)
    • Bellmann-Ford
    • Kürzeste Pfade im DAG
    • Dijkstra-Algorithmus
  • Kürzeste Pfade zwischen allen Knoten (All-Pairs)
    • All Pairs über Anzahl Kanten
    • Faster All Pairs
    • Floyd-Warshall
    • Johnson’s Algorithmus
  • Flüsse
    • Ford-Fulkerson
    • Edmund-Karp
    • Dinic
    • Generischer Push-Algorithmus
    • Relabel-To-Front Push Algorithmus
  • Matching
    • Maximales bipartites Matching
      • Ford-Fulkerson
      • Dinic
    • Maximal gewichtetes bipartites Matching
      • Ungarische Methode
      • Edmund-Karp
    • Maximales Matching in beliebigen Graphen
    • Maximales Matching in beliebigen gewichteten Graphen
  • Datenstrukturen
    • Suchbaum
    • Splay-Tree
    • Heap
    • Binomial Heap
    • Fibonacci Heap
  • Matrizen
    • Matrix Multiplikation
    • Strassen Algorithmus
    • LUP-Zerlegung
    • Kleinste Quadrate
  • Dynamische Programmierung
    • Matrixkettenmultiplikation
  • Lineare Programmierung
    • Simplex Algorithmus
    • Ganzzahlige Programmierung – Branch & Bound
  • Geometrische Algorithmik
    • Scan Line
      • Vertikale Sichtbarkeit
      • Liniensegment Schnittproblem
    • Konvexe Hülle
      • Graham’s Scan
      • Gift Wrapping
    • Dichteste Punte
      • Naiver Algorithmus: Teste alle Punkte mit allen anderen
      • Divide & Conquer – Algorithmus
    • Geometrische Datenstrukturen
      • Quad-Tree
      • kD-Tree
      • Intervall Baum
    • Voronoi Diagramm
      • Divide & Conquer – Algorithmus
    • Delaunay-Triangulierung
      • Guibas Algorithmus
    • Kleinste umschließende Kreise
      • Naiver Algorithmus
      • beschränkter „kleinste umschließende Kreise“-Algorithmus
      • Linearzeit Algorithmus
      • Minidisk-Algorithmus
      • Minidisk mit Move-to-Front
splaytree
Splay Tree - Selbstausrichtender Baum

Generell ist das schon ein spannendes Thema. Wer ein Gefühl dafür bekommen möchte, was sich hinter so einem Algorithmus verbirgt, sollte sich mal diese Beschreibung eines Algorithmus aus dem Problembereich „Kleinste umschließende Kreise“ angucken.

Interessant ist auch der Splay Tree (siehe Abbildung rechts). Hier handelt es sich um einen Suchbaum, der sich selbst ausrichtet. Wenn du bspw. den Begriff „Buch“ suchst, wird „Buch“ nach oben in die Wurzel geschoben. Wenn du das nächste Mal wieder „Buch“ suchst, ist es oben im Baum und es kann schnell darauf zugegriffen werden. Oftgesuchte Begriffe sind also oben und schnell verfügbar, während seltengesuchte Begriffe unten sind.

Also alles faszinierend: Nur wenn du über soo viele Dinge geprüft wirst, kannst du noch so viel üben – das übersteigt einfach deine Speicherkapazität und dann muss man halt nachdenken… ;-)

Jetzt heißt es: format c:\ *g*

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert

Diese Website verwendet Akismet, um Spam zu reduzieren. Erfahre mehr darüber, wie deine Kommentardaten verarbeitet werden.