Home
Curriculum Vitae
Informatik 2
Informatik 4
Effiziente Algorithmen
Seminar Effiziente Algorithmen
Fortgeschrittenenpraktikum Effiziente Algorithmen
Oberseminar
Cpp
Links
Zunächst ein paar Bilder von Prominenten. Von links nach rechts: Geroge Dantzig, Joseph B. Kruskal, Abu Jafar Muhammad ibn Musa al-Khwarizmi (Darstellung auf sowjetischer Briefmarke), Edsger Wybe Dijkstra.
Hier sind noch mal einige Algorithmen der Vorlesung kurz als Übersicht. Bei Algorithmen auf Graphen und Digraphen bzw. gerichteten Graphen beizeichnet in der Laufzeitkomplexität dabei n die Anzahl der Knoten bzw. Punkte, m die Anzahl der Kanten bzw. Bögen.
| Algorithmus | Problem | Grundidee | Laufzeitkomplexität |
|---|---|---|---|
|
Depth-First-Search (Tiefensuche) |
Suchprobleme, Zusammenhangskomponenten, Kreise | Rekursives Durchlaufen von Graphen in die Tiefe, was durch rekursive Implementierung bzw. durch einen Stack realisierbar ist. | O [ n + m ] |
|
Breadth-First-Search (Breitensuche) |
Suchprobleme, Zusammenhangskomponenten, Kreise | Rekursives Durchlaufen von Graphen in die Breite, was durch eine Warteschlange realisierbar ist. | O [ n + m ] |
| Topologische Sortierung | Finden einer topologischen Sortierung, falls sie existiert, sonst Feststellung, daß sie nicht existiert. | Rekursives Einsortieren eines Knoten mit In-Degree Null und Erzeugung einer topologischen Sortierung für den Restgraphen. Falls kein Knoten mit In-Degree Null existiert, aber noch nicht alle Knoten topologisch einsortiert sind, so besitzt der Graph einen gerichteten Kreis. | O [ n + m ] |
| Kruskal | Minimal spannender Baum | Sortiere Kanten nach nichtabsteigenden Gewichten. Iteriere über Kanten in dieser Reihenfolge. Erzeugt eine Kante einen Kreis, verwerfe sie, andernfalls akzeptiere sie. Der Kreistest wird durch Verwaltung der Zusammenhangskomponenten realisiert. | O [ m * log n ] |
| Prim | Minimal spannender Baum | Starte mit einem Knoten als Zusammenhangskomponente. Suche leichteste Kante, die die Zusammenhangskomponente verläßt und akzeptiere sie. | O [ n * m ] |
| Prim mit Array closest | Minimal spannender Baum | Idee wie bei Prim. Benutze ein Array zur Verwaltung des nächsten Nachbarn jedes Knotens, um die Suche der leichtesten verlassenden Kante zu realisieren. | O [ n * n ] |
| Sollin | Minimal spannender Baum | Starte mit leerem Graphen. Suche für jede Zusammenhangskomponente die kürzeste Kante, die sie verläßt und akzeptiere sie. Bestimme danach wieder die Zusammenhangskomponenten. Iteriere dieses Verfahren, bis der Graph zusammenhängend ist. | O [ m * log n ] |
| Dijkstra | Kürzeste Weglängen (single-source) | Voraussetzung ist, daß alle Kantengewichte positiv sind. Benutze dynamische Programmierung ausgehend vom Startknoten, um eine Lösung für die Bellman-Gleichungen zu errechnen. Diese ist in diesem Fall eindeutig. | O [ n * n ] |
| Bellman-Ford-Moore | Kürzeste Weglängen (single-source) | Voraussetzung ist, daß keine Kreise mit negativer Länge auftreten. Benutze dynamische Programmierung ausgehend vom Startknoten, um eine Lösung für die Bellman-Gleichungen zu errechnen. Dabei erlaube immer mehr Kanten in den kürzesten Wegen. | O [ n * n * n ] |
| Floyd-Warshall | Kürzeste Weglängen (all-pairs) | Dynamische Programmierung, iteratives zulassen von immer mehr Zwischenknoten. Nach der Terminierung kann abgelesen werden, ob es Kreise negativer Länge gibt. | O [ n * n * n ] |
