Algorithmus (Wiegen)
-
LinuxC_newbie schrieb:
Ist es also klüger die Größe der kleinsten Gruppe möglichst groß zu wählen?
Jo, klar! Für den Algo mit dem billigsten Worst-Case must die Waage die im nächsten Schritt zu prüfende Gruppe (egal, ob sie RINKS, LECHTS oder GLEICH sagt) so klein wie möglich machen.
Das leuchte ein, oder?
-
Das verstehe ich nicht.
Was ist an 35-35-30
besser als an
49-49-2?
Denn dann ist doch der best-case dafür schlechter?
-
LinuxC_newbie schrieb:
Das verstehe ich nicht.
Was ist an 35-35-30
besser als an
49-49-2?
49-49-2
Falls die Waage GLEICH sagt, haste im zweiten Zug gewonnen, lecker.Falls die Waage LINKS oder RECHTS sagt, haste im zweiten noch N=49 zu lösen statt nur N=35.
Es fühlt sich doch gleich mal so an, daß N=35 bestimmt nicht länger dauert als N=49.
-
Dafür ist ja aber auch der best-case deutlich schlechter - oder zählt das nicht?
-
LinuxC_newbie schrieb:
Dafür ist ja aber auch der best-case deutlich schlechter - oder zählt das nicht?
Das zählt erstmal nicht.
Erstmal den Worst-Case analysieren.Typischerweise sind bei Teile-Und-Herrsche-Algorithmen mit Zufallsdaten der Worst-Case und der Average-Case nur um 1 entfernt. Davon gehe ich hier auch mal aus.
Wir beide können den allerbesten Algo für den Worst-Case zusammenfrickeln. Interessant wäre noch der Average-Case.
Es gibt nämlich zwei Sorten von Kunden:
a) Der Zocker, der will, daß sein Game möglichst nicht ruckelt. Er braucht den billigsten Worst-Case. Gamecoder optimieren den Worst-Case.
b) Der Sysadmin, der unglaubliche Mengen an Daten durchnudelt und am nächsten morgen die Ergebnisse anschaut. Ihm ist der Average-Case wichtig. Null Problemo, wenn mal ein blöder Datensatz rumzickt.
Zum Glück hat sich SeppJ angeboten, dann den Average-Case zu berechnen. (Puh, Glück gehabt.) Naja, er hat ihn überhaupt erst ins Spiel gebracht, obwohl die Aufgebenstellung deutlich vom Worst-Case redet.
-
LinuxC_newbie schrieb:
Dafür ist ja aber auch der best-case deutlich schlechter - oder zählt das nicht?
Uns interessiert erst einmal nur der Mittelwert und der Worst Case. Bubblesort hat auch einen tollen Best Case, trotzdem ist das ein mit Absicht schlecht gemachtes Sortierverfahren.
-
Zum Glück hat sich SeppJ angeboten, dann den Average-Case zu berechnen. (Puh, Glück gehabt.) Naja, er hat ihn überhaupt erst ins Spiel gebracht, obwohl die Aufgebenstellung deutlich vom Worst-Case redet.
Morgen! Heute ist zu spät. Außerdem will ich erst einmal vom Threadersteller den Algorithmus sehen.
volkard schrieb:
b) Der Sysadmin, der unglaubliche Mengen an Daten durchnudelt und am nächsten morgen die Ergebnisse anschaut. Ihm ist der Average-Case wichtig. Null Problemo, wenn mal ein blöder Datensatz rumzickt.
Da steckt der Teufel im Details. Falls der Worst Case zu schlecht ist, dann bekommt auch der Sysadmin Probleme. Es gibt eine Denial of Service Attacke, bei der ein Angreifer einem Serverprogramm gezielt einen (an sich gültigen) Datensatz gibt, der dann in dem Programm zu einem besonders schlechten Worst Case führt überproportional Rechenzeit pro Anfrage verbraucht. So wird der Server mit wenigen Anfragen lahmgelegt.
Ja, das ist ein anderer Sysadmin, als der, den du meintest.
-
Nebenher: Irgenwann mal gelesen, vermutlich von Martin Gardner, und aus freier Erinnerung bestimmt fürchterlich entstellt.
Nach dem Giftmord auf einer größeren Party wissen wir:
Es gibt viele benutze Gläser. Eins davon hatte Gift drin. Dessen Fingerabdrücke brauchen wir! Die Gift-Analyse einer Probe kostet viel Geld. Deswegen schütten wir gerne Mikrotropfen von Gläsern zur Analyse zusammen, um dann Mischungen aus Gläsern zu analysieren. Die Gift-Analyse ist voll genau, sobald eines der beteiligten Gläsern Gift drin hatte, schlägt er gut aus.
Es wurde eine Mathe-Prof herbeigeholt mit dem Auftrag, die maximalen Ausgaben für die Gift-Analyse bei optimalem Vorgehen vorher zu berechnen und das hatte man vor dem Analysieren dann von der Buchhaltung auch absegnen lassen.Und er führete dann auch natürlich das Vorgehen. Der Prof nahm ein willkürliches Glas und sagte "Untersucht das mal". Empörung, weil er anscheinend keine Zusammenschütt-Strategie angestebt hatte! Er aber sagte "Nee, ist nicht schlimm, wir werden sicher nicht deswegen mehr Untersuchungen bezahlen müssen als nötig".
Der Detektiv erinnert sich genau, daß es nicht weniger als 100 und nicht mehr als 200 Gläser gab.a) Wieviele Gläser waren es?
b) Wieviele Untersuchungen wären durchschnittlich eingespart worden, wenn der Mathe-Prof den Auftrag gehabt hätte, die zu erwartenden Kosten zu minimieren?
-
So grob über den Daumen gepeilt würde ich schätzen
a) 129
b) 121/129 ≈ 0.938
-
Eine von mir irgendwann aufgeschnappte Variation der Aufgabe:
Wir verfügen über 8 Münzen, die identisch aussehen und alle gleich schwer sind, mit Ausnahme von einer Münze, die ein anderes Gewicht (schwerer oder leichter) hat als die anderen. Weiterhin verfügen wir über eine Balkenwaage, mit der eine Gruppe von Münzen mit einer anderen Gruppe verglichen werden kann. Die Waage kippt auf die Seite mit dem meisten Gewicht, bei Gleichheit kippt sie auf eine zufällige Seite. Was ist die kleinste Anzahl Wägungen, mit denen die andersartige Münze eindeutig bestimmt werden kann?
-
LinuxC_newbie schrieb:
Im besten Fall muss man nur ein Mal wiegen, im schlechtesten Fall muss man vier Mal wiegen.
Für den 'schlechtesten' Fall komme ich auf drei mal wiegen.
