- Titel: Algorithmentechnik
- Autor: Robert Görke and Steffen Mecke
- Organisation: UNI KARLSRUHE
- Seitenzahl: 170
Inhalt
- Inhaltsverzeichnis
- Abbildungsverzeichnis
- Algorithmenverzeichnis
- Grundlagen
- Worst-case- und Average-case-Laufzeit
- Beispiel
- Beispiel
- Beispiel
- Untere Schranken für Laufzeiten
- Untere Schranke für Sortieren
- Untere Schranke für Berechnung der konvexen Hülle
- Amortisierte Analyse
- Beispiel von Stackoperationen
- Die Ganzheitsmethode
- Die Buchungsmethode
- Die Potentialmethode
- Divide-and-Conquer Verfahren und das Prinzip der Rekursion
- Ein Beispiel aus der Informatik-Grundvorlesung
- Rekursionsabschätzungen
- Die Substitutionsmethode
- Die Iterationsmethode
- Der Aufteilungs-Beschleunigungssatz (Meistermethode, Master-Theorem)
- Grundlegende Datenstrukturen für Operationen auf Mengen
- Union-Find
- Drei Ansätze
- Die Laufzeit von Union-Find
- Bemerkungen
- Anwendungsbeispiele für Union-Find
- Der Algorithmus von Kruskal für MST
- Das Offline-Min-Problem
- Äquivalenz endlicher Automaten
- Priority Queues oder Heaps
- Heapify
- Makeheap
- Prozedur Delete
- Prozedur Sift-Up
- Prozedur Insert
- Sortierverfahren Heapsort
- Alternative Bottom-Up-Heapify
- Aufspannende Bäume minimalen Gewichts
- Einführung
- Das MST-Problem
- Motivation
- Die Färbungsmethode von Tarjan
- Grüne Regel
- Rote Regel.
- Färbungsinvariante
- Der Algorithmus von Kruskal
- Der Algorithmus von Prim
- Implementation des Algorithmus von Prim
- Greedy–Verfahren und Matroide
- Schnitte in Graphen und Zusammenhang
- Schnitte minimalen Gewichts
- Der Algorithmus von Stoer & Wagner
- Flussprobleme und Dualität
- Grundlagen
- Problemstellung
- Bestimmung maximaler Flüsse („Max Flow“)
- Ford-Fulkerson-Algorithmus (1962)
- Der Algorithmus von Edmonds und Karp (1972)
- Der Algorithmus von Goldberg und Tarjan (1988)
- Anwendungsbeispiel
- Kreisbasen minimalen Gewichts
- Kreisbasen
- Das Kreismatroid
- Der Algorithmus von Horton
- Der Algorithmus von de Pina (1995)
- Beispiel zum Algorithmus von de Pina
- Korrektheit des Algorithmus von de Pina
- Effiziente Berechnung eines Zertifikats für MCB
- Lineare Programmierung
- Geometrische Repräsentation von LPs
- Algorithmen zur Lösung von LPs
- Approximationsalgorithmen
- Approximationsalgorithmen mit relativer Gütegarantie
- Das allgemeine Knapsack Problem
- Bin Packing (Optimierungsversion)
- Approximationsschemata
- Ein PAS für Multiprocessor Scheduling
- Asymptotische PAS für Bin Packing
- Ein APAS für Bin Packing
- AFPAS für Bin Packing
- Randomisierte Algorithmen
- Grundlagen der Wahrscheinlichkeitstheorie I
- Randomisierte MinCut-Algorithmen
- Ein einfacher Monte Carlo-Algorithmus für MinCut
- Ein effizienterer randomisierter MinCut-Algorithmus
- Grundlagen der Wahrscheinlichkeitstheorie II
- Das Maximum Satisfiability Problem
- Der Algorithmus Random Sat
- Das MaxCut-Problem
- Ein Randomisierter Algorithmus für MaxCut
- Relaxierung von IQP
- Parallele Algorithmen
- Das PRAM Modell
- Komplexität von parallelen Algorithmen
- Die Komplexitätsklassen
- Parallele Basisalgorithmen
- Broadcast
- Berechnung von Summen
- Berechnung von Präfixsummen
- List Ranking
- Binäroperationen einer partitionierten Menge mit K Prozessoren
- Zusammenhangskomponenten
- Modifikation zur Bestimmung eines MST
- Der Algorithmus
- Reduzierung der Prozessorenzahl auf n2log2 n
- ParallelSelect
- Das Scheduling-Problem
- Parametrisierte Algorithmen
- Parametrisierte Komplexitätstheorie (Exkurs)
- Grundtechniken zur Entwicklung parametrisierter Algorithmen
Vorschau
Universit¨t Karlsruhe a Fakult¨t f¨r Informatik a u
Algorithmentechnik
Skript zur Vorlesung von Prof. Dorothea Wagner, Karlsruhe, Wintersemester 08/09 Stand: 19. November 2008
1 16 2 14 4 8 8 2 9 4 10 1 5 7 6 9 3 10 7 3
Skript erstellt von Robert G¨rke und Steffen Mecke o Fakult¨t f¨r Informatik a u Universit¨t Karlsruhe a
Basierend auf den Vorlesungsnotizen von Dorothea Wagner und dem Skript der Vorlesung Algorithmen und Datenstrukturen“ aus Konstanz ”
Inhaltsverzeichnis
Inhaltsverzeichnis Abbildungsverzeichnis Algorithmenverzeichnis 0 Grundlagen 0.1 Worst-case- und Average-case-Laufzeit . . . . . . . . . . . . . . . . . . . . . . . . . 0.1.1 0.1.2 0.1.3 0.2 0.2.1 0.2.2 0.3 0.3.1 0.3.2 0.3.3 0.3.4 0.4 0.4.1 0.4.2 0.4.3 0.4.4 0.4.5 Beispiel: Worst-case-Laufzeit von Finde Maximum . . . . . . . . . . . . . Beispiel: Average-case-Laufzeit von Finde Maximum . . . . . . . . . . . . Beispiel: Average-case-Laufzeit von Quicksort . . . . . . . . . . . . . . . . Untere Schranke f¨r Sortieren . . . . . . . . . . . . . . . . . . . . . . . . . . u Untere Schranke f¨r Berechnung der konvexen H¨lle . . . . . . . . . . . . . u u Beispiel von Stackoperationen . . . . . . . . . . . . . . . . . . . . . . . . . . Die Ganzheitsmethode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Die Buchungsmethode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Die Potentialmethode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Ein Beispiel aus der Informatik-Grundvorlesung . . . . . . . . . . . . . . . 1 5 7 1 1 1 2 3 4 4 4 5 6 7 7 7 9 9 10 11 12 12 19 19 19 24 28 29
Untere Schranken f¨r Laufzeiten . . . . . . . . . . . . . . . . . . . . . . . . . . . . u
Amortisierte Analyse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Divide-and-Conquer Verfahren und das Prinzip der Rekursion . . . . . . . . . . . . Rekursionsabsch¨tzungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . a Die Substitutionsmethode . . . . . . . . . . . . . . . . . . . . . . . . . . . . Die Iterationsmethode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Der Aufteilungs-Beschleunigungssatz (Meistermethode, Master-Theorem) .
1 Grundlegende Datenstrukturen fur Operationen auf Mengen ¨ 1.1 Union-Find . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1.1 1.1.2 1.1.3 1.2 Drei Ans¨tze . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . a Die Laufzeit von Union-Find . . . . . . . . . . . . . . . . . . . . . . . . . . Bemerkungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .