Kartenspiel zufällig sortieren < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Ein Kartenspiel von n (durchnummerierten) Karten soll sortiert werden. Betrachten Sie dazu folgenden naiven Algorithmus:
1. Mische das Kartenspiel zufällig.
2.Überprüfe, ob das Kartenspiel nun sortiert ist. Falls "ja", dann ist man fertig. Falls "nein", dann gehe zu Zeile 1.
Nehmen Sie an, dass das Mischen einem gleichverteilten Zufallsexperiment entspricht.
Außerdem sei eine Abfolge "Mischen und Überprüfen" eine Operation.
a)....
b)Es sei N die Anzahl der Atome im Weltall (verwenden Sie den Wert
N = [mm] 10^{77}). [/mm] Der Sortieralgorithmus werde nun auf N vielen (!!!) Superrechnern, die jeweils N mal (!!!) so schnell seien wie heutige Rechner (mit [mm] 10^{9} [/mm] Operationen pro Sekunde) parallelisiert. Gehen Sie davon aus, dass die Rechner die Arbeit optimal untereinander verteilen können.
Wir sind bereit, das komplette Alter des Universums (= [mm] 10^{10} [/mm] Jahre) auf das Ergebnis des Sortierverfahrens zu warten. Berechnen Sie, wie groß das Kartenspiel sein darf, damit obiger Algorithmus in dieser erwarteten Zeit hält. |
Hey,
habe ein Problem bei der obigen Aufgabe, denn entweder ich habe irgendeinen Murks zusammengerechnet, oder ich muss die Fakultätsfunktion umkehren, wo ich nicht weiß wie das geht - in jedem Fall brauche ich Hilfe :D Hoffe das Unterforum passt soweit.
Zunächst ist noch zu sagen, dass in a) die erwartete Anzahl von Operationen des Algorithmus mit n! ausgerechnet wurde.
(Erwartungswert geometrische Verteilung mit Erfolgswahrscheinlichkeit 1/n!)
So nun habe ich folgende Rechnung angestellt:
Zeit S auf einem Rechner: S = [mm] \bruch{n! Operationen}{N*10^{9} Operationen/Sekunde} [/mm] = [mm] \bruch{n!}{N*10^{9}} [/mm] Sekunden
Zeit P auf N Rechnern in Sekunden somit: P_sec = S/N = [mm] \bruch{\bruch{n!}{N*10^{9}}}{N} [/mm] = [mm] \bruch{n!}{N^{2}*10^{9}} [/mm] Sekunden.
Das ganze dann in Jahre umgerechnet(1 Tag = 86400 Sekunden, vereinfacht auf 365 Tage / Jahr):
P_year = [mm] \bruch{\bruch{n!}{N^{2}*10^{9}}}{365*86400} [/mm] Jahre =
[mm] \bruch{n!}{N^{2}*10^{9}*365*86400} [/mm] Jahre.
Der Spaß soll nun [mm] \le [/mm] als [mm] 10^{10} [/mm] Jahre dauern, d.h. P_year [mm] \le 10^{10}. [/mm] => n! [mm] \le 10^{10}*N^{2}*10^{9}*365*86400
[/mm]
So und das ist der Punkt, wo ich nicht weiterkomme:
Habe ich da Blödsinn gerechnet, oder muss ich hier irgendwie die Fakultätsfunktion umkehren? Wenn ja - wie?
Danke euch schonmal.
PS: Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 19:07 Fr 24.10.2014 | | Autor: | felixf |
Moin!
> Ein Kartenspiel von n (durchnummerierten) Karten soll
> sortiert werden. Betrachten Sie dazu folgenden naiven
> Algorithmus:
> 1. Mische das Kartenspiel zufällig.
> 2.Überprüfe, ob das Kartenspiel nun sortiert ist. Falls
> "ja", dann ist man fertig. Falls "nein", dann gehe zu Zeile
> 1.
> Nehmen Sie an, dass das Mischen einem gleichverteilten
> Zufallsexperiment entspricht.
> Außerdem sei eine Abfolge "Mischen und Überprüfen" eine
> Operation.
>
> a)....
>
> b)Es sei N die Anzahl der Atome im Weltall (verwenden Sie
> den Wert
> N = [mm]10^{77}).[/mm] Der Sortieralgorithmus werde nun auf N
> vielen (!!!) Superrechnern, die jeweils N mal (!!!) so
> schnell seien wie heutige Rechner (mit [mm]10^{9}[/mm] Operationen
> pro Sekunde) parallelisiert. Gehen Sie davon aus, dass die
> Rechner die Arbeit optimal untereinander verteilen
> können.
> Wir sind bereit, das komplette Alter des Universums (=
> [mm]10^{10}[/mm] Jahre) auf das Ergebnis des Sortierverfahrens zu
> warten. Berechnen Sie, wie groß das Kartenspiel sein darf,
> damit obiger Algorithmus in dieser erwarteten Zeit hält.
Na immerhin ist dieser Algorithmus in ![[]](/images/popup.gif) NP 
> Hey,
> habe ein Problem bei der obigen Aufgabe, denn entweder ich
> habe irgendeinen Murks zusammengerechnet, oder ich muss die
> Fakultätsfunktion umkehren, wo ich nicht weiß wie das
> geht - in jedem Fall brauche ich Hilfe :D Hoffe das
> Unterforum passt soweit.
> Zunächst ist noch zu sagen, dass in a) die erwartete
> Anzahl von Operationen des Algorithmus mit n! ausgerechnet
> wurde.
> (Erwartungswert geometrische Verteilung mit
> Erfolgswahrscheinlichkeit 1/n!)
![[ok]](/images/smileys/ok.gif "[ok]")
> So nun habe ich folgende Rechnung angestellt:
> Zeit S auf einem Rechner: S = [mm]\bruch{n! Operationen}{N*10^{9} Operationen/Sekunde}[/mm]
> = [mm]\bruch{n!}{N*10^{9}}[/mm] Sekunden
> Zeit P auf N Rechnern in Sekunden somit: P_sec = S/N =
> [mm]\bruch{\bruch{n!}{N*10^{9}}}{N}[/mm] = [mm]\bruch{n!}{N^{2}*10^{9}}[/mm]
> Sekunden.
>
> Das ganze dann in Jahre umgerechnet(1 Tag = 86400 Sekunden,
> vereinfacht auf 365 Tage / Jahr):
> P_year = [mm]\bruch{\bruch{n!}{N^{2}*10^{9}}}{365*86400}[/mm] Jahre
> =
> [mm]\bruch{n!}{N^{2}*10^{9}*365*86400}[/mm] Jahre.
>
> Der Spaß soll nun [mm]\le[/mm] als [mm]10^{10}[/mm] Jahre dauern, d.h.
> P_year [mm]\le 10^{10}.[/mm] => n! [mm]\le 10^{10}*N^{2}*10^{9}*365*86400[/mm]
Genau. Und $N$ selber kannst du auch noch einsetzen.
> So und das ist der Punkt, wo ich nicht weiterkomme:
> Habe ich da Blödsinn gerechnet, oder muss ich hier
> irgendwie die Fakultätsfunktion umkehren? Wenn ja - wie?
> Danke euch schonmal.
Nun, einmal kannst du mit einem passenden Programm (Maple z.B., oder auch mit Python, da du dort einfach so mit beliebig grossen Ganzzahlen rechnen kannst) recht schnell solange Werte für $n$ einsetzen, bis $n!$ grösser als die rechte Seite ist. Das geht ziemlich schnell, da die Fakultätsfunktion sehr stark ansteigt.
Allgemeiner kannst du die Stirlingformel verwenden, um $n!$ abzuschätzen. Die dadurch entstehende approximative Ungleichung ist aber (auch wenn man so tut, als wenn sie genau stimmen würde) auch nicht so viel einfacher auflösbar. Am einfachsten geht es numerisch. Aber da kannst du auch gleich Werte für $n$ in die exakte Fakultätsfunktion einsetzen.
LG Felix
PS: $n < 120$.
|
|
|
|
