Algorithmentheorie 01 - Einleitung Prof. Dr. Th. Ottmann
Tobias Lauer
Algorithmentheorie 01 - Einleitung Prof. Dr. Th. Ottmann
Tobias Lauer
Organisatorisches
Vorlesung: Mo. 14 - 16 Uhr, HS 00-036, Geb.101
Do. 14 - 16 Uhr, HS 00-036, Geb.101
alle 14 Tage
Übungen: Do. 14 - 16 Uhr alle 14 Tage (erster Termin: 9. November)
Einteilung und Räume werden noch bekanntgegeben.
Termin- und Themenübersicht auf Kurs-Website:
http://ad.informatik.uni-freiburg.de/lehre/ws0607/algtheo/
Organisatorisches
Klausur: Teilnahmevoraussetzungen:
- 50% der Übungsaufgaben bearbeitet und abgegeben
- 1-mal in den Übungen vorgerechnet
Bonus bei bestandener Klausur:
Verbesserung um
- 1/3 Notenstufe, wenn 50% der Übungspunkte erzielt
- 2/3 Notenstufe, wenn 80% der Übungspunkte erzielt
Literatur
Th. Ottmann, P. Widmayer:
Algorithmen und Datenstrukturen
4. Auflage, Spektrum Akademischer Verlag, Heidelberg, 2002
Th. Cormen, C. Leiserson, R. Rivest, C. Stein:
Introduction to Algorithms,
Second Edition, MIT Press, 2001
Originalliteratur
Genauere Angaben zum Thema werden jeweils auf der
Kurs-Seite im Web veröffentlicht
Algorithmen und Datenstrukturen
Entwurfsprinzipien und Analysetechniken für Algorithmen
Divide and Conquer
Greedy Prinzip
Dynamische Programmierung
Randomisierung
Amortisierte Analyse
Divide and Conquer „Teile und herrsche“
lat. „divide at impera“
Das Divide-and-Conquer Prinzip
Auffrischung: Quicksort
Formulierung und Analyse des Prinzips
Geometrisches Divide-and-Conquer
Closest-Pair
Segmentschnitt
Voronoi-Diagramm
Fast Fourier Transformation
Quicksort: Sortieren durch Teilen
Quick(Fl) v Quick(Fr) F Fl < v v Fr > v v function Quick (F : Folge) : Folge;
{liefert zu unsortierter Folge F die sortierte}
begin
if |F| ≤ 1
Quick := F
else { wähle Pivotelement v aus F;
teile F in Fl mit Elementen < v
und in Fr mit Elementen > v
Quick := }
end;
Formulierung des D&C Prinzips
Divide-and-Conquer Verfahren zur Lösung eines
Problems der Größe n 1. Divide:
n > c: Teile das Problem in k Teilprobleme der Größe n1,...,nk auf (k 2)
n c: Löse das Problem direkt
2. Conquer:
Löse die k Teilprobleme auf dieselbe Art (rekursiv)
3. Merge:
Füge die k berechneten Teillösungen zu einer Gesamtlösung zusammen
Analyse
T(n): Maximale Anzahl von Schritten, um ein Problem
der Größe n zu lösen
T(n) =
Spezialfall: k = 2, n1 = n2 = n/2
Divide- und Mergeaufwand : DM(n)
T(1) = a
T(n) = 2∙T(n/2) + DM(n)
Geometrisches Divide-and-Conquer
Closest Pair Problem:
Bestimme für eine Menge S von n Punkten ein Paar mit
minimaler Distanz (bzw. bestimme die minimale Distanz)
Divide-and-Conquer Ansatz
1. Divide : Teile S in zwei gleichgroße Mengen Sl und Sr
2. Conquer: dl = mindist(Sl) dr = mindist(Sr )
3. Merge: dlr = min {d(pl ,pr) | pl Sl , pr Sr }
return min {dl , dr ,dlr } Sr Sl S dl dlr dr
Divide-and-Conquer Ansatz
1. Divide : Teile S in zwei gleichgroße Mengen Sl und Sr
2. Conquer: dl = mindist(Sl) dr = mindist(Sr )
3. Merge: ? Sr Sl S dl dr
Divide-and-Conquer Ansatz
Sr Sl S p d d = min {dl , dr } 1. Divide : Teile S in zwei gleichgroße Mengen Sl und Sr
2. Conquer: dl = mindist(Sl) dr = mindist(Sr )
3. Merge: dlr = min {d(pl ,pr) | pl Sl , pr Sr }
return min {dl , dr ,dlr }
Berechnung von dlr :
Merge-Schritt
Betrachte nur Punkte im Abstand d von der Mittellinie,
gemäß aufsteigenden y-Koordinaten
Betrachte zu jedem Punkt p alle Punkte q mit y-Abstand
höchstens d; es gibt maximal 7 solche Punkte
Merge-Schritt
d d d d d = min { dl , dr } p S Sl Sr p1 p3 p4 p2
Implementierung
Sortiere Eingabepunkte anfangs einmal gemäß steigenden
x-Koordinaten O(n log n)
Sind Teilprobleme Sl , Sr gelöst, so erzeuge Liste der Punkte in S gemäß steigenden y-Koordinaten (Mergesort)
Laufzeit (Divide-and-Conquer)
Rate Lösung durch wiederholtes Einsetzen
Verifiziere durch Induktion
Lösung: O(n log n)
Comments