3. Teile und Herrsche

komplizierte Aufgabe in einfachere Teilaufgaben teilen,
lösen und wieder zusammensetzen
divide'n'conquer / Teile und Herrsche
- Teilen oft trivial
- Herrschen meist einfach
- mischen (reassemblieren) oft schwierig
Beispiel: Konvexe Hülle
- Aufgabe: Gegeben ist eine Punktwolke, gesucht ist die Teilmenge der Punkte, die die konvexe Hülle bilden
- INPUT: Punktemenge S Í Â²:
  - x(p₁) < x(p₂) ... < x(p_n) also sortiert nach x-Werten
  - p_i ÎS
- OUTPUT: Obere Hülle (S)
  - Ansatz: Teilen in obere und untere konvexe Hülle
  - man braucht für das Gesamtproblem auch die untere konvexe Hülle
  - diese kann man jedoch analog zur Bestimmung der oberen erhalten
- Idee des Vorgehens
  - →etwa mittig Teilen & konvexe Hüllen der Teile bestimmen
  - → Gleitgerade
  - Vereinigen der konvexen Hüllen
- 1 if |S|<5 { OUTPUT Ergebnis von Brute-Force-Ansatz; EXIT; }
  2 Berechne UH(S1), UH(S2) parallel
  3 berechne obere Tangente
  4 bereite OUTPUT vor
  - sei S₁ = {p₁, ..., p_n/2}
- Analyse:
  - T(n) = T( n ) + a log n
    
    2
    - a log n ist Zeit für Schritt 3 (obere Tangente)
    - Frage: wie machen?
    - Lösung für Schritt 3 ist die binäre Suche nach möglichen Tangenten
    - Voraussetzung: Computer kann Uhrzeigersinn und Gegenuhrzeigersinn unterscheiden:
      - Uhrzeigersinn
      - Gegenuhrzeigersinn
    - Definitionen
      - konkav
      - reflex
      - tangential
    - Binäre suche gestaltet sich folgendermaßen:
      - aus den (nach x-Werten) geordneten Teilarrays für die linke und rechte Hälfte
        wird jeweils das mittlere Element gewählt
      - jenachdem, welcher der Fälle eintritt, kann die eine oder andere Hälfte des Array verworfen werden
      - mögliche Fälle:
        die Punkte auf den roten Linie können bei der binären Suche übergangen werden
      - Spezialfall konkav konkav:
        
        q₁ und q₂ sind die aktuell betrachteten Punkte,
        die gesuchten Punkte sind p₁ und p₂
        
        p₁ liegt im roten Bereich
        
        wäre p₂ im grünen Bereich, würde u noch weiter nach oben wandern →grün entfällt
        
        2 Fälle:
        
        p links von schwarzer Gerade; u>v → grün entfällt
        
        p rechts von schwarzer Gerade; u<v → rot entfällt
    - Bemerkung: Dieses Resultat nutzt bei "Herrsche" keine Parallelität aus
    - Man kann parallele Techniken bei der Suche nach (p₁, p₂) anwenden - Idee:
      - alle Prozessoren vergleichen ihren Wert mit dem des gesuchten Punktes
      - eine Teilmenge stellt fest, dass der gesuchte Punkt links ist; die andere dass er rechts ist.
      - an der Grenze: Vertiefung der Suche
      - →Merge geht in O(1)
      - →Rekurrenz wre dann T(n) = T( n ) + O(1)
        
        2
  - → T(n) = O(log² n)
    - Begründung: der Aufrufbaum der Rekursion hat die Tiefe log n
    - auf jeder Ebene des Rekursionsbaumes wird a·log n Zeit gebraucht
  - →W(n) ≤ 2W( n ) + O(n) →W(n) = O(n log n)
    
    2

T(n) = T(	n	) + a log n
	2

→Rekurrenz wre dann T(n) = T(	n	) + O(1)
	2

→W(n) ≤ 2W(	n	) + O(n) →W(n) = O(n log n)
	2