[informatik-bonn] Re: InfoIII

  • From: Sebastian Bothe <sbothe@xxxxxx>
  • To: informatik-bonn@xxxxxxxxxxxxx
  • Date: Sun, 2 Feb 2003 17:25:02 +0100

On Saturday 01 February 2003 19:53, you wrote:
> On Sat, Feb 01, 2003 at 11:27:05AM +0100, Sebastian Bothe wrote:
>
> Hallo,
>
> >   Also sind es wohl die Grenzen des Arrays und genau die rechte Mitte,
> > bis zu einem bestimmten Punkt der Teilungen- Aber so ganz klar ist mir
> > dieses Muster nicht. Ich meine wie kann ich das möglichst ohne
> > ausprobieren herausfinden?
>
> Das Muster entsteht dadurch, da die einzige "Handlungmöglichkeit"
> des Algorithmus darin besteht, die linke bzw rechte Schranke in
> Richtung der aktuellen Mitte zu verschieben und damit
> das Intervall zu verkleinern.
> Dann ist eigentlich recht eindeutig, wenn man sich mal vorstellt
> wie die Schranken im Intervall wandern.
  Also ihr könnt mich ja jetzt für blöd verkaufen, aber ich finde das ist 
überhaupt nicht klar. Aber um es mal anders als Blum zu machen, zu dem 
Beispiel aus der Übungsaufgabe- Das Array hat Einträge von 1..20 . Die 
Elemente für die BinSearch maximale Zeit braucht waren hier 1,6,11,16,20. 
Offensichtlich handelt es sich dabei um die Ränder des Array und weiterhin 
fällt auf, daß die anderen immer Abstand 5 haben also genau log_2(20) 
aufgerundet.. Das es am "längsten" dauert die Ränder zu bekommen ist intuitiv 
relativ klar- Dann bei 11 handelt es sich genau um die Mitte der ersten 
Teilung. Bei 6 und 16 um die Mitte der zweiten Teilung, je nachdem, ob das 
Element links oder rechts von 11 liegt. Das es am längsten dauert nun diese 
"Mitten" zu finden kann ich mir so halbwegs auch erklären, aber wieso genau 
bis zu dieser Teilungstiefe?
  Machen wir die Frage noch konkreter- Nehmen wir an, ich habe ein Array, daß 
viel größer ist, also sagen wir 100 Elemente- Dann wäre also log_2(100) 
aufgerundet 7- Nun wähle ich schonmal die "Ränder" des Array, die maximale 
Zeit brauchen. Danach ergänze ich um alle mit Abstand 7, also ist die 
Suchzeit maximal für x={1,8,15,22,29,36,43,50,57,64,71,78,85,92,99,100} ?? 
Ist das korrekt und wieso oder wieso nicht?

>
> > Noch etwas anderes, wie kann man eigentlich den Algo BinäreSuche vom Blum
> > retten? So erfüllt der ja nicht die Laufzeitkriterien..
>
> Wieso? Es geht doch um asymptotische Laufzeiten....
Nein in seinem Buch schreibt er, daß binäre Suche maximal log_2(n) aufergundet 
Schleifendurchläufe braucht- Das ist doch dann die exakte Laufzeit- Und das 
stimmt so sicher nicht, wenn man ein Element links außerhalb des arrays 
wählt- Das haben wir in den Übungsaufgaben ja gesehen- Da kamen auf einmal 6 
Schleifendurchläufe raus, obwohl log(20) auferundet=5 ist..
>
> > Sorry, natürlich hast Du Recht! Ich meinte Aufgabe5 ebenfalls von Zettel
> > 2. Hierfür haben wir keine Punkte bekommen und etwas gutes fällt mir dazu
> > auch nicht ein. Hat das jemand geschafft, oder hat jemand die
> > "Musterlösung" aus der Gruppe mitgeschrieben?
>
> Sinngemäß:
>
> Gesucht: z
> x:=n
> y:=1
>
> while (F_1[x] > z) do
>   x--
> od
>
> while (x>0) do
>   while (F_2[y]+F_1[x] < z) do
>     y++
>   od
>
>   if (F_2[y]+F_1[x] == z)
>     gefunden
>   fi
>   x--
> od
>
Probier ich gleich mal in Ruhe aus.. schonmal vielen Dank!
> Bye, Lutz


Other related posts: