Dies ist eine statische Kopie unseres alten Forums. Es sind keine Interaktionen möglich.
This is a static copy of our old forum. Interactions are not possible.

Zypressen Hügel

Junior Schreiberling

  • "Zypressen Hügel" started this thread

Posts: 244

Date of registration: Dec 22nd 2001

1

Sunday, November 10th 2002, 7:44pm

D&A, Übung 3

hi. können mir mal die "echten" informatiker hier bestätigen, dass sich aufgabe 1 nicht lösen lässt, weder mit monoton listen noch mit streng monotonen listen...

nur, damit ich die restlichen zehn prozent dieses wochenendes mit ruhigem gewissen verbringen kann...
Man kann auch ohne Spass Alkohol haben 8)
  • Send private message

Joachim

Guru

  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

2

Sunday, November 10th 2002, 7:53pm

Quoted

Original von Zypressen Hügel
können mir mal die "echten" informatiker hier bestätigen, dass sich aufgabe 1 nicht lösen lässt, weder mit monoton listen noch mit streng monotonen listen...
Ich weiß zwar nicht, ob ich ein "echter" Informatiker bin, aber in der ersten Aufgabe habe ich an einem Spezialfall (alle Listenelemente bis auf Maximum und Minimum gleich groß) versucht zu zeigen, daß man diesen meiner Meinung nach nicht mit einem Algorithmus der Laufzeit O(log n) abhandeln kann.
The purpose of computing is insight, not numbers.
– Richard Hamming, 1962
  • Send private message

Zypressen Hügel

Junior Schreiberling

  • "Zypressen Hügel" started this thread

Posts: 244

Date of registration: Dec 22nd 2001

3

Sunday, November 10th 2002, 8:18pm

hab ich auch so gezeigt.

allerdings habe ich auch anhand zweier streng monotoner Listen

L1={2,3,20,1,4,5,6,7,8,9,10,11,12,13,14,15} und
L2={2,3,4,5,6,7,8,9,10,11,12,13,20,1,14,15}

zeigen können, dass die aufgabe selbst bei strenger monotonie nicht lösbar sein kann, da es keinen anhaltspunkt bei einem wie auch immer gearteten divide&conquer-verfahren geben muss, anhand dessen man die näher zu untersuchende partition der listen bestimmen kann.

irgendwie kann man sich zu jedem verfahren ein gegenbeispiel basteln, das alles wieder kaputtmacht...

Man kann auch ohne Spass Alkohol haben 8)
  • Send private message

MAX

Senior Schreiberling

  • "MAX" is male

Posts: 822

Date of registration: Dec 11th 2001

Location: Hannover

4

Sunday, November 10th 2002, 9:42pm

naja

Mit einem rekursiven Aufruf ist natürlich nichts getan. Aber was ist wenn man zwei rekursive Aufrufe derart max(liste,i,mitte) und max(liste,mitte+1,j) hinereinander aufruft. Dann ist doch gewährleistet, dass kein Bereich der Liste verlorengeht. Also ich wage zu behaupten, dass das noch in O(log(n)) möglich ist.
mfg
MAX
  • Send private message

Joachim

Guru

  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

5

Sunday, November 10th 2002, 10:28pm

Quoted

Original von MAX
Mit einem rekursiven Aufruf ist natürlich nichts getan. Aber was ist wenn man zwei rekursive Aufrufe derart max(liste,i,mitte) und max(liste,mitte+1,j) hinereinander aufruft.
Ich gehe jetzt mal davon aus, daß du mit i und j den Anfang bzw. das Ende der Liste meinst.

Quoted

Dann ist doch gewährleistet, dass kein Bereich der Liste verlorengeht.
Das ist ja gerade das Problem. Es *muß* ein Teil der Liste verloren gehen, wenn man auf eine Laufzeit von O(log n) kommen will.

Erklär' doch bitte mal, wie du es geschafft hast.
The purpose of computing is insight, not numbers.
– Richard Hamming, 1962
  • Send private message

MAX

Senior Schreiberling

  • "MAX" is male

Posts: 822

Date of registration: Dec 11th 2001

Location: Hannover

6

Sunday, November 10th 2002, 10:44pm

Ich habe es leider nicht geschaft, aber

Ein Algorithmus gefunden, der in einem linearen Feld (Liste) das Maximum findet. Dieser Algorithmus nützt das Devide-and-Conquer Verfahren.
Pascal Notation:

Source code

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

procedure max(var a: feld; i,j : integer; var m: integer);
var m1,m2,mitte : integer;

begin
  if i = j then m:=a[i]
  else if i = j - 1 then
    begin
      if a[i] < a[j] then m:=a[j]
      else m:=a[i]
    end
  else
    begin
      mitte:=(i+j) div 2;
      max(a,i,mitte,m1);
      max(a,mitte+1,j,m2);
      if m1 < m2 then m:=m2
      else m:=m1
    end
end;


Wie gesagt, den Algorithmus habe ich selbst nicht geschrieben(erfunden), aber er scheint mir ziemlich geeignet für dieses Problem zu sein. Besonders, dass hier (meiner Meinung nach) durch doppelte Rekursion gewährleistet ist, dass nichts verlorengeht.
mfg
MAX
  • Send private message

Joachim

Guru

  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

7

Sunday, November 10th 2002, 11:19pm

Quoted

Original von MAX
Ein Algorithmus gefunden, der in einem linearen Feld (Liste) das Maximum findet. Dieser Algorithmus nützt das Devide-and-Conquer Verfahren.
Habe mir den Algorithmus mal angeschaut. Hier nochmal kurz eine Beschreibung der Funktionsweise:

Wenn das zu prüfende Intervall nur einen Wert enthält:
-> diesen Wert zurückliefern

Wenn das zu prüfende Intervall nur zwei Werte enthält:
-> beide Werte vergleichen und den größeren der beiden zurückliefern

Sonst:
-> über Rekursion das Maximum der ersten Intervallhälfte bestimmen
-> über Rekursion das Maximum der zweiten Intervallhälfte bestimmen
-> beide Werte vergleichen und den größeren der beiden zurückliefern



Folgende Skizze illustiert das am Beispiel von Zypressen Hügel (s. o.): Skizze

Wie man sieht, benötigt man immer noch etwa n Vergleiche, damit ergibt sich ein Laufzeitverhalten von O(n). Logarithmisch zu n verhält sich nur die Anzahl der Rekursionsebenen.
The purpose of computing is insight, not numbers.
– Richard Hamming, 1962
  • Send private message

Zypressen Hügel

Junior Schreiberling

  • "Zypressen Hügel" started this thread

Posts: 244

Date of registration: Dec 22nd 2001

8

Monday, November 11th 2002, 8:25am

ich stimme joachim zu, denn diese idee habe ich auch schon mal gehabt und komme zu dem gleichen ergebnis wie joachim...

Man kann auch ohne Spass Alkohol haben 8)
  • Send private message

np

Junior Schreiberling

Posts: 155

Date of registration: Oct 23rd 2002

9

Monday, November 11th 2002, 9:47am

Entschuldigung.

Da Ihr ja sowieso schon so weit seit, hier nochmal der Hinweis, dass es eigentlich "im besten Fall O(log n)" in der Aufgabe heißen muss. Irgendwie häufen sich in letzter Zeit die Tippfehler in den Zetteln, aber ich gelobe Besserung!

Der Algorithmus von Max ist auf dem richtigen Weg, man muss nur zeigen, dass er im besten Fall O(log n) läuft.

Nochmals Entschuldigung.

Niklas
  • Send private message

MAX

Senior Schreiberling

  • "MAX" is male

Posts: 822

Date of registration: Dec 11th 2001

Location: Hannover

10

Monday, November 11th 2002, 5:40pm

achso....

na dann ist klar. Es ist also ehe die Frage, welche Voraussetzungen gegeben sein müssen(bezogen auf die Liste), damit man O(log n) im besten Fall hat. Oder???
mfg
MAX
  • Send private message

np

Junior Schreiberling

Posts: 155

Date of registration: Oct 23rd 2002

11

Tuesday, November 12th 2002, 8:25am

Quoted

Original von MAX
Es ist also eher die Frage, welche Voraussetzungen gegeben sein müssen(bezogen auf die Liste), damit man O(log n) im besten Fall hat. Oder???

Ich würde es so formulieren: Gibt es einen Algorithmus, der (zumindest manchmal) O(log n) liefert, aber nie schlechter ist, als O(n)?
  • Send private message