V. Suchen

• in sortierten Listen
• Problem
  • geht seriell in Θ(log n) Zeit mit
    • binäre Suche
  • EREW: Mit p EREW-Prozessoren ist Ω (log n - log p) Time die zugehörige Schranke nach unten
  • → nicht besser als seriell
• einzig interessanter Fall:
  • CREW
  • p Prozessoren
  • Voraussetzung für INPUT = paarweise verschiedene Elemente

  • arbeitet in \ceil{	log(n+1)	} Zeit
    	log(p+1)

    • Kruskal hat 1983 bewiesen, dass diese Grenze scharf ist, also nicht zu unterschreiten
• T_S(n, p) sei die entsprechende Rechenzeit (Anzahl der Vergleichsschritte)
  die notwendig und hinreichend sind, um mit p Prozessoren n Elemente zu durchsuchen
• Lemma:
  • mit k Schritten lassen sich [(p+1)^k-1] Elemente durchsuchen
  • Beweis:
    • Induktionsanfang: k=1
      • // (p+1)¹-1 = p Elemente
    • Induktionsvoraussetzung: " i ≤ k-1 Þ Induktionsbehauptung für i=k
    • 
      
      Prozessoren werden auf die (äquidistanten) roten Elemente angesetzt
      (p+1) Abschnitte
      • findet einer das gesuchte Element → Abbruch
      • sonst:
        • Prozessoren, die größere Zahl haben, als gesuchtes Element: entfernen der links liegenden Elemente
        • Prozessoren, die kleinere Zahl haben, als gesuchtes Element: entfernen der rechts liegenden Elemente
      • → Verringern der Liste → iterierte Anwendung
    • formal: für j=1,...,p betrachten wir die Elemente, die mit j(p+1)^k-1 markiert sind.
    • nach Induktionsvoraussetzung genügen (k-1) Schritte, um die verbliebenen Elemente
      der grün markierten Liste zu durchsuchen, denn dort befinden sich nur (p+1)^k-1-1 Elemente

    • denn:	n-p	= ((p+1)k - 1) p = (p+1)k-1 - p+1 = (p+1)k-1-1 p+1 p+1
      	p+1

    • dieses Argument ist fortsetzbar: nach 2 Schritten: (p+1)^k-2-1 usw.
    • es folgt: Mit k Schritten lassen sich (p+1)^k-1 Elemente durchsuchen
  • Beispiel
    • X = [2,3,5,8,12,14,16,17,18,20,25,28,30,35,40]
    • p=3
    • k=2
    • (p+1)^k = 4²-1 = 15
    • X = [2,3,5,8,12,14,16,17,18,20,25,28,30,35,40]
      • fett: gesuchtes Element
      • rot: Prozessoren im ersten Schritt
      • unterstrichen: diese Elemente werden rausgeworfen
  • nachgerechnet:
    • im k-ten = letzten Schritt werden p Elemente durchsucht
    • im (k-1)-ten Schritt werden (p+1)p + p Elemente durchsucht
    • im (k-2)-ten Schritt werden (p+1)[(p+1)p+p] + p = (p+1)²p + (p+1)p + p Elemente durchsucht
    • im (k-3)-ten Schritt werden (p+1)[(p+1)²p + (p+1)p + p] + p = (p+1)³p + (p+1)²p + (p+1)p + p Elemente durchsucht

    • in allen k Schritten zusammen können damit p + Σ

      k-1 i=1

      (p+1)kp = pΣ

      k-1 i=0

      (p+1)k Elemente abgedeckt werden

    • es gilt Σ	n i=0	qi =	qn+1-1
      			q-1

    • Þ mit k Schritten können p	(p+1)k-1	= p (p+1)k-1 = (p+1)k-1 Elemente durchsucht werden p
      	p+1-1

• Algorithmus
  • INPUT: X, sortiert, paarweise verschiedene Elemente s
  • OUTPUT: Index des gesuchten Elements (falls existent, sonst 0)
  • begin
  • m=0

  • k=\ceil{	log (n+1)	}
    	log (p+1)

  • while (Liste nicht ausgeschöpft) do
    • for i=1 to p pardo
      • if x_i(p+1)^k+1=s
        • m = Index dieses Elements
        • return m
      • if x_i(p+1)^k-1<s then
        • remove Elemente links davon
      • if x_i(p+1)^k-1>s then
        • remove Elemente rechts davon
    • k=k-1

• Aus dem Lemma folgt:	log(n+1)	Schritte reichen,
  	log(p+1)

  um n Elemente mit p Prozessoren zu durchsuchen
  • es reicht wenn (p+1)^k-1 ≥ n
  • → (p+1)^k ≥ n+1
  • → log(p+1)^k = k·log(p+1) ≥ log(n+1)

  • → k ≥ \ceil{	log(n+1)	}
    	log(p+1)

  • Theorem: TS(n,p) = \ceil{	log(n+1)	}
    	log(p+1)

  • Beweis:
    • Dieser Wert ist hinreichend (oben bewiesen)
    • Dieser Wert ist notwendig (= Theorem von Kruskal)
      • Aussage in etwa: dieser Algorithmus funktioniert, darüber
        hinaus gilt, dass kein anderer Algorithmus schneller sein kann!
      • Beweis:
        • 
          
          Jeder Algorithmus mit p Prozessoren kann in einem Schritt nur p Elemente durchsuchen
        • für n>p muss es mindestens einen Abschnitt nicht durchsuchter Elemente geben

        • Größe des Abschnitts: ≥ \ceil{	n-p	} ≥ n-p = n+1 - p+1 = n+1 - 1 p+1 p+1 p+1 p+1
          	p+1

        • Allgemein gilt: nach k Schritten bleibt mindestens ein undurchsuchter Rest der Länge	n+1	-1
          	(p+1)k

        • Vollständig durchsucht ist die Folge dann, wenn der Rest leer ist,

          also wenn	n+1	-1 ≤ 0 ↔ log(n+1) ≤ k·log(p+1) ↔\ceil{ log (n+1) } ≤ k log(p+1)
          	(p+1)k