Die Mathe-Redaktion - 24.10.2019 07:36 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte / Top 15
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
Listenpunkt? im neuen Schwätz
ListenpunktWerde Mathe-Millionär!
ListenpunktFormeleditor fedgeo
Schwarzes Brett
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden. Mitglieder können den Matheplanet-Newsletter bestellen, der etwa alle 2 Monate erscheint.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 178 Gäste und 5 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von matroid
Mathematik » Kombinatorik & Graphentheorie » Ranking von Rennpferden
Thema eröffnet 2019-09-03 18:19 von
cramilu
Druckversion
Druckversion
Antworten
Antworten
Seite 2   [1 2]   2 Seiten
Autor
Kein bestimmter Bereich Ranking von Rennpferden
cramilu
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 09.06.2019
Mitteilungen: 103
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.40, vom Themenstarter, eingetragen 2019-09-17


@haribo:
Nach Karnevalslogik steht das zehnte Pferd wahrscheinlich im Flur.
Mit "ikea" assoziiere ich im Moment eher einen Apfelschimmel (kein vergammeltes Obst!), der hinter einer kunterbunten Villa friedlich neben einem Limonadenbaum grast ;)

###

Für n=4 habe ich inzwischen mein "ausgelostes Ranking" eingekürzt:
15>11>7>4>2>1>13>10>16>9>6>3>12>8>5>14

Drei verschiedene Erstrunden-Zusammensetzungen und die sich daraus ergebenden Rennen der Zweit- sowie der Drittplatzierten habe ich geprüft:

[A]R1(1;2;3;4) / [A]R2(5;6;7;8) / [A]R3(9;10;11;12) / [A]R4(13;14;15;16) /
[A]R5(2;6;10;13) / [A]R6(1;8;9;16) ; nach 6 Rennen 76 von 120 Aussagen

[B]R1(1;5;9;13) / [B]R2(2;6;10;14) / [B]R3(3;7;11;15) / [B]R4(4;8;12;16) /
[B]R5(10;11;13;16) / [B]R6(6;7;9;12) ; nach 6 Rennen 72 von 120 Aussagen

[C]R1(1;8;9;16) / [C]R2(2;7;10;15) / [C]R3(3;6;11;14) / [C]R4(6,7;13,16) /
[C]R5(6,7;13;16) / [C]R6(2;3;9;12) ; nach 6 Rennen 80(!) von 120 Aussagen

Das Zwischenergebnis hat mich in seiner Streuung von 76 plus/minus 4 Aussagen nach 6 Rennen  nicht überrascht. Nach 5 Rennen à la Kitaktus mussten es schon 60 sein, und das sechste Rennen musste weitere 6 unmittelbare Aussagen liefern. Dass sich je nach Erstrundenkonstellation dann 6, 10 oder 14 weitere Aussagen ableiten lassen, scheint passend. Nach 6 Rennen fehlen demnach im bislang ungünstigsten Fall 48 Aussagen auf die 120. Sich diese rein kombinatorisch in 6 oder 7 Rennen "herbei-zu-erkenntnissen", halte ich mit algorithmischer Unterstützung für durchaus machbar.

Die "reinere" Kitaktus-Strategie mit fünf Rennen und zwei Separationsrennen werde ich als nächstes prüfen. Bin gespannt, wieviele Aussagen mehr nach dann 7 Rennen zu gewinnen sind...

Übernächste Prüfung als "Zwischenschritt":
n=3 und zweite Runde mit Rennen der Erstrundensieger, -zweiten und -dritten...
Da interessiert mich auch noch die Aussagenmenge!

###

Für n=5 hatte ich "mein Ranking" ursprünglich wie folgt ausgelost:
15>22>24>19>11>17>7>4>2>1>13>10>16>23>18>9>6>21>3>25>12>8>5>14>20

Die erste Erstrundenzusammensetzung mit anschließendem Rennen der Drittplatzierten à la Kitaktus und zwei weiteren Separationsrennen (siehe no.37) ergab inzwischen...

R1(1;2;3;4;5) / R2(6;7;8;9;10) / R3(11;12;13;14;15)
R4(16;17;18;19;20) / R5(21;22;23;24;25) // R6(1;9;13;16;23) ;
"c3"=16, "a4"=3, "a5"=5, "b4"=12, "b5"=14, "d1"=22, "d2"=24, "e1"=7, "e2"=10 ;
R7(3;5;12;14;16) / R8(7;10;16;22;24) ; nach 8 Rennen 200 von 300 Aussagen

Das befriedigt mich [noch] nicht!
Mit der Strategie einer ersten Runde und hernach Rennen der Erstrundensieger, -zweiten usw. hatte ich ja zuvor bei bislang 7 Konstellationen nach dann 10 Rennen jeweils stets zwischen 256 und 259 Aussagen finden können...
Allerdings habe ich kurz vor Mittag noch eine Art "Gegenprobe" gemacht:
Gleiches Ranking, gleiche Erstkonstellation für die erste Runde, und hernach nur weitere drei(!) Rennen, nämlich Erstrundendritte, -zweite und -vierte. Ergab sage und schreibe 244(!) Aussagen. Dreimal gegengeprüft!
Entweder hatte ich da "Konstellationsdusel", oder mir sind bei meinen vorherigen 7 Versuchen jeweils einige ableitbare Aussagen entgangen. Also zurück ans Reißbrett ;)

###

Ach ja - zur Fallunterscheidung à la Kitaktus/Cramilu für n=5:
Für R7(a4;a5;b4;b5;c3) und R8(c3;d1;d2;e1;e2) sind nach meiner Auswertung jeweils 30 unterschiedliche Rennausgänge möglich; insgesamt also ganze 900, wo es bei n=3 bloße sechs waren!
In  36 Fällen sind 16 Pferde schneller als "c3" und  8 langsamer.
In  72 Fällen sind 15 Pferde schneller als "c3" und  9 langsamer.
In 108 Fällen sind 14 Pferde schneller als "c3" und 10 langsamer.
In 144 Fällen sind 13 Pferde schneller als "c3" und 11 langsamer.
In 180 Fällen sind 12 Pferde schneller als "c3" und auch 12 langsamer.
In 144 Fällen sind 11 Pferde schneller als "c3" und 13 langsamer.
In 108 Fällen sind 10 Pferde schneller als "c3" und 14 langsamer.
In  72 Fällen sind  9 Pferde schneller als "c3" und 15 langsamer.
In  36 Fällen sind  8 Pferde schneller als "c3" und 16 langsamer.
Diese Fallunterscheidungen werden dann wohl unausweichlich "ein echter Hammer" :(



  Profil  Quote  Link auf diesen Beitrag Link
cramilu
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 09.06.2019
Mitteilungen: 103
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.41, vom Themenstarter, eingetragen 2019-09-17


Kitaktus, eine kurze Nachfrage:

Würdest Du Deine Strategie bezüglich n>3 eher darin sehen, nach der ersten Runde genau ein(!) Rennen von "Erstrundenmittleren" durchzuführen, oder eher darin, alle außer(!) denen der Erstrundensieger und der Erstrundenletzten?

Im ersteren Fall entfällt zwar das "Notationsfiasko", aber für größere n ufern die Fallunterscheidungen aus.
Im zweiteren Fall ist der Anteil gewonnener Aussagen an deren Gesamtmenge höher (wie auch die Anzahl an Rennen), aber es entsteht zumindest ein "Notationsdilemma".



  Profil  Quote  Link auf diesen Beitrag Link
cramilu
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 09.06.2019
Mitteilungen: 103
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.42, vom Themenstarter, eingetragen 2019-09-17


Grund meiner Nachfrage bei Kitaktus:

n=2 ; insgesamt 6 paarweise Aussagen ;
nach 3 Rennen (Erstrundensieger) 4 Aussagen von 6 oder 8/12 ;
"trotzdem" insgesamt 5 Rennen für Gesamtranking erfoderlich

n=3 ; insgesamt 36 paarweise Aussagen ;
nach 4 Rennen (Erstrundenzweite) 21(!) Aussagen von 36 oder 7/12 ;
"schön": insgesamt höchstens 9 Rennen erfoderlich

n=4 ; insgesamt 120 paarweise Aussagen ;
nach 5 Rennen (Erstrundenzweite) 60 Aussagen von 120 oder 6/12 ;
nur noch 50% - insgesamt 12(?) oder 13(?) Rennen erforderlich

n=5 ; insgesamt 300 paarweise Aussagen ;
nach 6 Rennen (Erstrundendritte) nur(!) 140 Aussagen von 300 oder 7/15 ;
weniger als 50% - insgesamt 15(?) oder 16(?) Rennen erfoderlich

n=6 ; insgesamt 630 paarweise Aussagen ;
nach 7 Rennen (Erstrundendritte) ??? Aussagen von 630 oder ???/??? ;
sicher unter 50% - insgesamt ??? Rennen erforderlich
[noch zu klären]



  Profil  Quote  Link auf diesen Beitrag Link
weird
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.10.2009
Mitteilungen: 4972
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.43, eingetragen 2019-09-17


2019-09-17 16:20 - cramilu in Beitrag No. 41 schreibt:
Kitaktus, eine kurze Nachfrage:

Würdest Du Deine Strategie bezüglich n>3 eher darin sehen, nach der ersten Runde genau ein(!) Rennen von "Erstrundenmittleren" durchzuführen, oder eher darin, alle außer(!) denen der Erstrundensieger und der Erstrundenletzten?

Im ersteren Fall entfällt zwar das "Notationsfiasko", aber für größere n ufern die Fallunterscheidungen aus.
Im zweiteren Fall ist der Anteil gewonnener Aussagen an deren Gesamtmenge höher (wie auch die Anzahl an Rennen), aber es entsteht zumindest ein "Notationsdilemma".

Meine Meinung dazu ist, dass man für $n=4$ noch vor dem Rennen, welches der Nebendiagonale in der Matrix *) entspricht, das Rennen mit den Pferden der 3.Zeile durchführen sollte. Dafür gibt es m.E. zwei gute Gründe:

1. Man bracht vermutlich tatsächlich noch ein weiteres Rennen, da  sonst die Zahl der Einfälle zu groß ist. Um wie schon für $n=3$ die "Dualisierungsmethode" (=Vertauschen von Gewinnern und Verlieren, dann eine schon betrachtete Methode anwenden und dann wieder Rücktauschen) anwenden zu können, würde sich da die 3.Zeile der Matrix anbieten, da sie die Symmetrie zumindestens weitestgehend wieder herstellt, wenn vielleicht auch nicht zu 100% in Hinblick auf die noch zu wählende Referenzzeile.

2. Es kann, wie bereits erwähnt sein, dass ein Pferd der dritten Zeile besser geeignet als b3 ist, als "mittleres Referenzpferd" zu fungieren. Dann müsste man die Spalten der Matrix nach der 3.Zeile ausrichten und anschließend erst das Rennen machen, welches der dann ev. neuen Nebendiagonale entspricht.

Was ich mich bei der ganzen Sache auch frage ist, ob die vermutlich optimale(?) Lösung der Aufgabe für $n=3$ von Kitaktus hier nicht für $n=4$ angewandt werden kann, indem man mit max. 9 Versuchen das Ranking der 3x3 Pferde in der "rechten oberen Ecke" der Matrix feststellt und dann versucht die Pferde in der 1.Spalte und der 4. Zeile der Matrix darin "einzusortieren", über die man dann ja auch schon eine ganze Menge weiß. Das wäre aber dann ein komplett neuer Ansatz, den ich noch nicht wirklich gründlich durchdacht habe.

*) Wenn ich hier und im Folgenden von Matrix spreche, so meine ich immer sowas wie die Matrix $A$ aus #31, wobei die endgültige Reihung der Spalten, also die Benennung mit a,b,c,d, allerdings erst feststeht, nachdem man sich auf eine "Referenzzeile" dafür geeinigt hat, also dann nach dem 5. oder 6.Rennen, je nachdem.



  Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 2122
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.44, eingetragen 2019-09-17


spannender ansatz, erfordert aber ganz neues nachdenken, denn dann sortierst du ja erstmal 3x3 pferde aber mit jetzt 4 startern bei jedem rennen... kannst also kitaktus 3x3 strategie gar nicht anwenden?
haribo



  Profil  Quote  Link auf diesen Beitrag Link
weird
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.10.2009
Mitteilungen: 4972
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.45, eingetragen 2019-09-17


2019-09-17 18:00 - haribo in Beitrag No. 44 schreibt:
spannender ansatz, erfordert aber ganz neues nachdenken, denn dann sortierst du ja erstmal 3x3 pferde aber mit jetzt 4 startern bei jedem rennen... kannst also kitaktus 3x3 strategie gar nicht anwenden?
haribo

Kann ich schon: Drei Pferde wähle ich i.d.R. so aus, wie dies einem 3x3-Auswahl für die "rechte oberen Ecke" in dem 4x4-Raster entsprechen würde, das vierte Pferd dann normalerweise passend in der 1.Spalte bzw. 4.Zeile. Wenn also z.B. die 3 ersten Pferde alle in der gleichen Zeile oder Spalte der Matrix liegen, dann wird es sich normalerweise wohl anbieten, dass man auch das 4.Pferd in dieser Zeile bzw. Spalte wählt. Es gibt aber darüber hinaus in der 3x3-Strategie Fälle, wo ein 4.Pferd sehr gelegen kommt, z.B. wenn das "mittlere Pferd" des 3x3-Bereichs im Ranking genau 4 Pferde oberhalb und 4 Pferde unterhalb hat, wo dann jeweils ein Rennen ausreicht um die restlichen Fälle für den 3x3-Bereich abzuklären. Im Detail müsste man sich aber das alles wohl noch etwas genauer ansehen.



  Profil  Quote  Link auf diesen Beitrag Link
Ex_Senior
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.46, eingetragen 2019-09-17


2019-09-03 21:29 - cyrix in Beitrag No. 12 schreibt:
Zum allgemeinen Fall liefert für große <math>n</math> die untere Schranke sowas wie mindestens <math>(2+o(1)) n</math> benötigte Rennen und die entsprechend verallgemeinerte Strategie entsprechend Beitrag No. 5, in der in je zwei aufeinanderfolgenden Rennen insgesamt die <math>\sqrt{2n}</math> Nächstplatzierten identifiziert werden, läuft auf sowas wie <math>(\sqrt{2}+o(1)) n^{\tfrac{3}{2}}</math> hinaus.

Da ist noch eine Lücke... ;)

Ein bisschen kleiner bekommt man die Lücke via divide-et-impera:

Gegeben sei ein Schema <math>S</math> zum Lösen des Problems für <math>n\times n</math>-Pferde, wobei in jedem Rennen <math>n</math> Pferde gegeneinander antreten können. Dabei seien die <math>n^2</math> Pferde von 1 bis <math>n^2</math> (in beliebiger Reihenfolge) durchnummeriert. Die Anzahl der benötigten Rennen sei mit <math>R(n)</math> bezeichnet.

Wir geben nun im Folgenden einen Plan für <math>2n\times 2n</math>-Pferde an, wobei in jedem Rennen $<math>2n</math> Pferde gegeneinander antreten können. Dabei seien die <math>4n^2</math> Pferde mit <math>A_1</math> bis <math>D_{n^2}</math> (in irgendeiner Reihenfolge) bezeichnet.

Zuerst arbeiten wir das Schema für <math>n\times n</math> Pferde wie folgt ab: Treten in einem Rennen gemäß <math>S</math> die Pferde <math>a</math>, <math>b</math>, <math>\dots</math> gegeneinander an, so im entsprechenden neuen Rennen die Pferde <math>A_a</math>, <math>A_b</math>, <math>\dots</math>, <math>B_a</math>, <math>B_b</math>, <math>\dots</math>. Es werden also in dem Rennen mit <math>2n</math> Pferden zwei Rennen zu je <math>n</math> Pferden simuliert.

Nach <math>R(n)</math> solchen Rennen ist das Schema <math>S</math> einmal abgearbeitet, und man hat für alle Pferde der Gruppe <math>A</math> sowie die der Gruppe <math>B</math> innerhalb ihrer jeweiligen Gruppe sortiert. Mit weiteren <math>R(n)</math> Rennen kann man dies analog für die Gruppen <math>C</math> und <math>D</math> erhalten.

Nun besitzt man vier sortierte Gruppen zu je <math>n^2</math> Pferden. Lässt man in einem Rennen aus jeder Gruppe die ersten <math>\frac{n}{2}</math> gegeneinander antreten, dann erhält man mit diesem ersten zusätzlichen Rennen die ersten <math>\frac{n}{2}</math> Pferde des Gesamtrankings. Durch Nachrücken innerhalb einer jeweiligen Gruppe erhält man analog für jedes weitere solche zusätzliche Rennen die jeweils nächsten <math>\frac{n}{2}</math> Positionen des Gesamtrankings, sodass man nach <math>8n</math> zusätzlichen Rennen dieses vollständig kennt.

Wir erhalten also die Rekursion <math>R(2n)=2R(n)+8n</math>, die auf <math>R(n)=(4+o(1))\cdot n\log n</math> führt, wobei hier der binäre Logarithmus gemeint ist.

Das ist schon mal nur noch logarithmisch und nicht mehr polynomiell vom Optimum entfernt. ;)

Cyrix



  Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6051
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.47, eingetragen 2019-09-18


Ich habe einen Merge-Sort-Ansatz untersucht.
Der Einfachheit halber sei $N=2^k$, $k\geq 1$.

Zunächst sortieren wir in $N$ Rennen $N$ Gruppen mit jeweils $N$ Pferden.
Jetzt folgen $k$ Merge-Runden.
In der i-ten Runde nehmen wir je zwei sortierte Gruppen mit jeweils $N\cdot 2^{i-1}$ Pferden. Von diesen Paaren gibt es $N/2^i$ Paare.
Um zwei sortierte Gruppen zu einer zu sortieren (="mergen") nimmt man jeweils die schnellsten noch nicht endgültig sortierten $N/2$ Pferde aus beiden Gruppen und lässt sie in einem Rennen antreten.
Die $N/2$ schnellsten Pferde dieses Rennens sind garantiert auch die schnellsten Pferde beider Gruppen(*).
Nach $2^{i+1}-2$ solchen Rennen stehen die ersten $(2^{i+1}-2)\cdot N/2 = (2^{i}-1)\cdot N$ Platzierungen fest. Die restlichen $N$ Pferde sortiert man in einem weiteren Rennen. Es sind also genau $2^{i+1}-1$ Rennen.
Zum mergen aller $N/2^i$ Paare braucht man in der i-ten Runde also $N\cdot (2^{i+1}-1)/2^i =N\cdot (2-1/2^i)$ Rennen.
Nach der k-ten Runde sind alle Gruppen zu einer zusammengemerged, alle Pferde sind also sortiert.
Dafür waren $2k\cdot N - N(1/2+1/4+...+1/2^k) = (2k-1+1/2^k))N = (2\log_2{N}-1)N+1$ Rennen. Dazu kommen noch die $N$ Rennen vom Anfang.

Fazit: Für $N=2^k$ kann man $N^2$ Pferde in $2N\log_2{N}+1$ Rennen sortieren.

Für $N=4$ sind das 17 Rennen. Für $N=8$ sind es 49 Rennen.

Wenn ich keinen Fehler gemacht habe, ist das asymptotisch um den Faktor 2 schneller als cyrix' Ansatz.



(*) In vielen Fällen kann man mehr als $N/2$ Platzierungen exakt bestimmen, aber wenn alle Pferde der einen Gruppe schneller sind, als alle Pferde der anderen Gruppe, dann kennt man nur $N/2$ Platzierungen.



  Profil  Quote  Link auf diesen Beitrag Link
Ex_Senior
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.48, eingetragen 2019-09-18


Schöne Variante, über die ich mal kurz (und offensichtlich nicht lang genug) auch mal nachgedacht hatte. :)

Jetzt ist die Frage, ob es wirklich nicht schneller als in <math>\Theta(n\log n)</math> geht, sprich, ob man eine bessere untere Schranke hinbekommt...

Cyrix



  Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6051
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.49, eingetragen 2019-09-18


Ich bin mir sicher, dass es schneller geht. Ich weiß aber nicht, ob man mehr als einen konstanten Faktor noch herausholen kann.

Ich denke gerade über Szenarien nach wie: "Kann man zwei sortierte Achtergruppen mit sechs Vierer-Vergleichen sortieren?"



  Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6051
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.50, eingetragen 2019-09-19


Nachtrag:

Im in Beitrag #47 beschriebenen Verfahren werden stets _zwei_ sortierte Gruppen gemergt.
In Beitrag #46 werden jeweils _vier_ Gruppen gemischt(*).
Macht das einen Unterschied?

Ich betrachte folgende Situation:
Es gibt $2$, $g\geq 1$ Gruppen, mit jeweils $2^l$, $l\geq 1$ Pferden. In einem Rennen können gleichzeitig $2^k$, $l\geq k\geq g$ Pferde antreten.
Verglichen werden:
a) Es werden nacheinander je zwei Gruppen gemischt.
b) Es werden gleichzeitig alle $2^g$ Gruppen gemischt.

Zu a) In jedem Rennen treten je $2^{k-1}$ Pferde aus jeder Gruppe an, von denen mindestens $2^{k-1}$ exakt einsortiert werden. Beim letzten Rennen werden alle $2^k$ Pferde exakt sortiert, so dass man ein Rennen spart.
Für zwei Gruppen braucht man demnach $2^{l+1-(k-1)}-1$ Rennen.
Für alle $2^g$ Gruppen sind es zusammen $2^{l+2-k+g-1}-2^{g-1}=2^{l+g+1-k}-2^{g-1}$ Rennen.
Danach haben wir es mit $2^{g-1}$ Gruppen zu tun, die jeweils die Länge $2^{l+1}$ haben. Der Aufwand dafür beträgt $2^{l+g+1-k}-2^{g-2}$ Rennen.
Nach insgesamt $g$ solchen Runden haben wir alle Pferde sortiert und dafür
$g\cdot 2^{l+g+1-k}-2^{g-1}-2^{g-2}-\dots 2^{g-g} = g\cdot 2^{l+g+1-k}-2^{g}+1$ Rennen gebraucht.
Das ist die Verallgemeinerung der Idee in #47 mit $g=k=l$.

Zu b)
Aus jeder Gruppe treten $2^{k-g}$ Pferde an. Die besten $2^{k-g}$ Pferde dieses Rennens sind korrekt sortiert. Damit hätte man nach $2^{g+l-(k-g)}$ Rennen alle Pferde sortiert. Da man aber die letzten $2^g$ Rennen zum Sortieren der letzten $2^{k-g}\cdot 2^g=2^k$ Pferde zu einem einzigen Rennen zusammenfassen kann, spart man $2^g-1$ Rennen.
Zum vollständigen Sortieren sind also $2^{2g+l-k}-2^g+1$ Rennen nötig.

Vergleich von a) und b)
Wir schauen uns die Differenz aus a) und b) an:
$g\cdot 2^{l+g+1-k}-2^{g}+1 - (2^{2g+l-k}-2^g+1) = g\cdot 2^{l+g+1-k} - 2^{2g+l-k} = (2^{g+l-k})\cdot(2g - 2^{g})$.
Für $g=1$ und $g=2$ ist die Differenz $0$, für alle größeren $g$ ist die Differenz negativ (unabhängig von $k$ und $l$).

Dass es für $g=1$ keinen Unterschied macht, ist klar, beide Verfahren sind dann identisch. Die Gleicheit für $g=2$ sagt aber aus: Ob man vier Gruppen in zwei Stufen paarweise mischt, oder alle vier auf einmal, macht keinen Unterschied.


Warum schreibe ich das überhaupt?

Sortiert man vier Gruppen gleichzeitig zusammen, so entsteht weiteres Verbesserungspotential. Die Idee ist nicht neu, denn es ist die Kernidee des Ausgangsproblems: Treten 5 Pferde gleichzeitig an, so kann man in zwei aufeinanderfolgenden Rennen nicht nur die besten zwei Pferde aus fünf sortierten Fünfergruppen bestimmen, sondern die besten drei.

Auf den ersten Blick hilft das nicht weiter. Man braucht fünf Gruppen, die man zusammenmischt, damit der Trick funktioniert und nicht nur vier.
Auf den zweiten Blick geht es aber doch.
Wir betrachten folgende Situation:
Wir wollen vier Gruppen mischen und es können acht Pferde gleichzeitig antreten.
Wir nehmen aus jeder Gruppe die zwei besten Pferde und lassen sie gegeneinander antreten. Wir nennen die Gruppen A, B, C und D, wobei A1,...,D1 jeweils der Gruppenerste und A2,...,D2 der Gruppenzweite sind.
O.B.d.A. sei A1 > B1 > C1 > D1 (">"  im Sinne von "schneller als").
Sind die beiden besten Pferde dieses Rennens selbst Gruppen-Erste gewesen (also A1 und B1), so sind mindestens die ersten drei Pferde des Rennens korrekt sortiert.
Andernfalls sind A1 und A2 die beiden schnellsten Pferde.
Wer kommt dann für die Plätze 3-5 in Frage?
Das sind A3, A4 und A5, außerdem die drei nächst-schnellsten Pferde des ersten Rennens. Dazu gehören mit Sicherheit B1 und C1 und außerdem D1, B2 oder C2. Dazu kommt ggf. noch ein weiteres Pferd: B3, wenn B2 schneller war als C1.
Wir sehen also: Mit zwei aufeinanderfolgenden Rennen können in jedem Fall _fünf_ und nicht nur vier Pferde korrekt sortiert werden.
Für N=8 reduziert das die Zahl der notwendigen Rennen von 49 auf 44.

Wie groß die Einsparung ist, wenn nicht nur 8 sondern bspw. 16, oder allgemein $2^k$ Pferde gleichzeitig laufen können, muss ich mir noch in Ruhe überlegen (und aufschreiben).
Ich denke bei N=16 kann man in den ersten beiden Rennen zusammen 10 Pferde korrekt sortieren und wahrscheinlich bekommt man auch allgemein eine Beschleunigung um den Faktor 5/4 hin.


(*) Merge-Sort ("Misch-Sortieren") ist eine gängige Fachbezeichnung für Sortierverfahren, die zunächst kleinerer Gruppen sortieren und dann mehrere sortierte Gruppen (meist zwei) zu _einer_ sortierten Gruppe zusammen-"mischen". Ich möchte für diesen Vorgang im Weiteren den Begriff "mischen" verwenden. In der informellen Fachsprache wird häufig von "mergen" und "gemergt/gemerged" gesprochen, also der englische Begriff wie ein deutsches Verb verwendet. Das möchte ich aus sprachästhetischen Gründen vermeiden.



  Profil  Quote  Link auf diesen Beitrag Link
cramilu
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 09.06.2019
Mitteilungen: 103
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.51, vom Themenstarter, eingetragen 2019-09-23


Na, Ihr seid ja schon voll in der Grundlagentheorie ;)

Ich kann bislang weiterhin bloß mit meinen "Aussagensammlungen" beitragen...

###

n=3

"Ranking-Auslosung": 7>4>2>1>9>6>3>8>5
freie "erste Runde" mit verschiedenen Auswahl-Konstellationen
"zweite Runde" mit Rennen der Erstrundensieger, Erstrundenzweiten, Erstrundenletzten
NEUN verschiedene Konstellationen für "erste Runde" durchgeprüft...

AM PROBLEMATISCHSTEN z.B. "erste Runde" R1=(1;4;7), R2=(2;5;8), R3=(3;6;9)
- nach "zweiter Runde" lediglich 29 von 36 Vergleichsaussagen ableitbar
+ In JEDEM FALL ließ sich meine Aussagentabelle mit lediglich DREI weiteren Rennen füllen!

Fazit:
Mit dieser "Strategie" braucht man auch höchstens NEUN Rennen,
ABER selbstredend ist die von Kitaktus systematischer und effizienter, weil sie im Mittel eine Anzahl erforderlicher Rennen deutlich unter neun liefert! Außerdem erspart man sich die Aussagentabelle ;)

###

n=4

"Ranking-Auslosung": 15>11>7>4>2>1>13>10>16>9>6>3>12>8>5>14
freie "erste Runde" mit verschiedenen Auswahl-Konstellationen
"zweite Runde" mit Rennen der Erstrundensieger usw.
SIEBEN verschiedene Konstellationen für die "erste Runde" durchgeprüft...

AM PROBLEMATISCHSTEN z.B.
"erste Runde" R1=(1;8;9;16), R2=(2;7;10;15), R3=(3;6;11;14), R4=(4;5;12;13)
- nach "zweiter Runde" lediglich 97 von 120 Vergleichsaussagen ableitbar
- teils "wild unregelmäßige" Lücken in Aussagentabelle
- mindestens(!) FÜNF weitere Rennen erforderlich, u.U. sogar SECHS
- insgesamt damit nach dieser "Strategie" bis zu 14 Rennen erforderlich

Fazit:
Für n=4 ist diese Strategie noch keinesfalls zufriedenstellend!

In Anlehnung an Kitaktus scheint aktuelle die Strategie mit einem fünften Rennen der Erstrundenzweiten und hernach Konzentration auf "a2"(!) am effizientesten!
R6=(a2;b1;c1;d1) "klärt" die grobe Einordnung der zunächst DREI unbestimmten Gäule.
Für dessen Ausgang gibt es 24 Möglichkeiten...
In 6 Fällen gewinnt "a2". Dann sind "a1" und "a2" die beiden schnellsten Gäule, und für die 14(!) langsameren sind weitere Rennen erforderlich.
In 6 Fällen wird "a2" Letzter. Dann reicht ein R7=(a1;b1;c1;d1) zur Sortierung der vier schnelleren Rösslein untereinander, und für die 11(!) langsameren brauchts weitere Rennen.
In 6 Fällen wird "a2" Vorletzter. Dann reicht ein Dreierrennen zur Sortierung der drei schnelleren Rösslein untereinander, und für die 12(!) langsameren werden weitere Rennen nötig.
In 6 Fällen wird "a2" Zweiter. Dann kann man später im Sortierungsrennen (a1;[b1/c1/d1];...) zwei weitere Pferdchen von den langsameren mitlaufen lassen, um zu einem geeigneten Zeitpunkt vor weiteren Rennen wenigstens eine Art Vorentscheidung zu erhalten. Für die dann 13(!) langsameren Klepper sind weitere Rennen erforderlich - mit dem zuvor genannten "Vorentscheidungs-Bonus"...

Hier bin ich aktuell mitten in der 24-Er-Fallunterscheidung.
Hoffnung: 13(!) Rennen reichen...
Ich werde mich beizeiten mit neuesten Erkenntnissen melden ;)



  Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6051
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.52, eingetragen 2019-09-23


@cramilu:

Ich muss dir leider mitteilen, dass cyrix und ich das Thema hier bis auf weiteres nicht weiter verfolgen werden.
Cyrix hat den Matheplaneten komplett verlassen und ich habe mich selbst auf "inaktiv" gesetzt.
Das ist bedauerlich, da dieser Faden einige schöne Ideen hervorgebracht hat. Aber leider ist er das Opfer einer Entwicklung, die sich schon seit langer Zeit abgezeichnet hat.



  Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 2122
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.53, eingetragen 2019-09-25


hallo kitaktus, hallo cyrix,

1. nachdenken über schöne ideen ist freiwillig, macht aber mehr spass wenn es einen höherleveligen austausch darüber gibt... insofern seid euch bitte nicht zu schade eure entscheidung bei gelegenheit zu relativieren

2. es gibt natürlich ein leben ausserhalb des matheplaneten, sozusagen planet-B, aber hier werdet ihr vermisst

haribo



  Profil  Quote  Link auf diesen Beitrag Link
cramilu
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 09.06.2019
Mitteilungen: 103
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.54, vom Themenstarter, eingetragen 2019-09-25


Cyrix und Kitaktus,

ich schließe mich uneingeschränkt dem an, was haribo sagt!

Ihr werdet nicht nur vermisst, sondern gebraucht.
In der wehrhaften Aufrichtigkeit gegen die Trolle, nämlich.

Liebe Grüße,
Cramilu



  Profil  Quote  Link auf diesen Beitrag Link
Delastelle
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 17.11.2006
Mitteilungen: 1349
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.55, eingetragen 2019-09-26 23:29


Hallo,

ich muss bei Rennpferden auch an Mathematiker denken;
Mathematiker sind wie Rennpferde auch manchmal etwas empfindlich - aber zu erstaunlichen Höchstleistungen fähig.

Zur Aufgabe:
ich weiß nicht, ob es Verallgemeinerungen von Sortiernetzen gibt.
Ein einfaches Sortiernetz sortiert z.B. 2^n Zahlen der Reihenfolge nach.
Dabei besteht der kleinste Sortiervorgang aus einem Input: 2 Zahlen, Output: 2 Zahlen sortiert.

Falls es auch Sortiernetze mit k Eingaben, als kleinstem Input (Einzelsortiervorgang) gibt, könnte es auch Literatur zur Sortierung von 25 Pferden mit 5er Sortierungen geben.

Viele Grüße
Ronald

Edit:
en.wikipedia.org/wiki/Sorting_network
Edit2:
Optimal Sorting Networks:
fed-Code einblenden

(aus Wikipdia/Englisch)

Dort klafft eine Lücke zwischen besten bekannten Sortiernetzen und theoretischen Schranken.
Wohl auch für n = 25.



  Profil  Quote  Link auf diesen Beitrag Link
cramilu
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 09.06.2019
Mitteilungen: 103
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.56, vom Themenstarter, eingetragen 2019-09-27 23:11


Hallo Delastelle,

und willkommen beim Thema ;)

Zitate "[...], könnte es auch Literatur zur Sortierung von 25 Pferden mit 5er Sortierungen geben." und "Dort klafft eine Lücke [...]".

Der einschlägige Wikipedia-Satz "Despite the simplicity of sorting nets, their theory is surprisingly deep and complex." zeigt wohl die Richtung auf: Is nich mit Literatur! Ich hatte selber ausführlich zu dem Thema gegoggelt, bevor ich es eröffnet habe. Ähnlich wie bei haribos und meinem anderen derzeitigen geistigen Steckenpferd hier, "16 auf einen Streich" - siehe dort.

Manchmal ist es kaum zu fassen, dass sich auch im 21. Jahrhundert noch eigentlich simpel anmutende kombinatorische Fragestellungen auftun, zu denen selbst Fachinformatiker wie einer meiner Ex-Profs keine einschlägige ausführliche wissenschaftliche Quelle kennen oder selbst nach Beratung mit Fachkollegen aufspüren können.

Aber dafür gibts ja dann den MP ;)



  Profil  Quote  Link auf diesen Beitrag Link
Delastelle
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 17.11.2006
Mitteilungen: 1349
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.57, eingetragen 2019-09-27 23:34


Hallo cramilu!

Für 2er Vergleiche(Rennen mit nur 2 Pferden) müsste der Vergleich mit Sortiernetzen stimmen.
Dort scheint aber auch noch viel nicht gelöst zu sein.
Oder anders gesagt: wieviele 2er Vergleiche bei 25 Rennpferden gebraucht werden ist ziemlich unklar.

Bei vielleicht 100.000 Mathematikern auf der Welt kann ich mir aber vorstellen, dass schon jemand auf so ein Thema gestoßen ist. Ich wüßte aber auch nicht, was ich außer "generalization sorting network" suchen sollte. Eine Suche in mathematischen (Online oder CD-ROM) Datenbanken könnte wenigstens einen Anhaltspunkt liefern wieviele Artikel zu "sorting network" existieren!

Vielleicht ist das Problem auch bekannter wenn man 25 Autos oder 25 Hunde verwendet :-).

Ich hatte vor Jahren mal ein wenig mit Sortiernetzwerken zu tun. Dabei kann man z.B. die fünftgrößte von 10 Zahlen auch mathematisch umschreiben - dies kann einen Anhaltspunkt darauf liefern, wieviele 2er oder 5er Rennen/Vergleiche nötig sind um die x.größte Zahl zu ermitteln.

Viele Grüße
Ronald



  Profil  Quote  Link auf diesen Beitrag Link
haegar90
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 18.03.2019
Mitteilungen: 114
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.58, eingetragen 2019-09-27 23:44


Sei $\mathbb{E}:=\lbrace a,b,c,d....x,y,z\rbrace$ die Menge der Elemente $a...z$ mit der Anzahl $\#\mathbb{E}=26$ und sei mit $">,<"$ das relative Verhältnis zueinander ausgedrückt. Dann gilt O.B.d.A. $\lbrace (a>b>c>d>....>x>y)\leq z\rbrace$, wobei $z$ das größte Element von allen Verglichenen nach jedem Vergleich sein soll und die Reihenfolge aller übrigen 25 Elemente mit möglichst wenigen Vergleichen entsprechend der Aufgabenstellung zu bestimmen ist.
Vergleich 1 Übersicht Beispiel
Um die größten drei zu bestimmen sind sieben Vergleiche nötig.
.	.	.	a	b 	c	d	e	f	g	h	i	j	k	l	m	n	o	p	q	r	s	t	u	v	w	x	y	z	.	.	.	.	.	.
1	.	.	a	b 	c	d	e	.	.	.	.	.	.	.	Bsp.: z=c	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.
2	.	.	.	.	.	.	z	f	g	h	i	.	.	.	.	.	.	Bsp.: z=h	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.
3	.	.	.	.	.	.	.	.	.	.	z	j	k	l	m	.	.	.	.	.	Bsp.: z=m	.	.	.	.	.	.	.	.	.	.	.	.	.
4	.	.	.	.	.	.	.	.	.	.	.	.	.	.	z	n	o	p	q	.	.	.	.	.	Bsp.: z=p	.	.	.	.	.	.	.	.	.
5	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	z	r	s	t	u	.	.	.	.	.	Bsp.: z=t	.	.	.	.	.
6	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	z	v	w	x	y	.	.	.	.	.	Bsp.: z=t	.
7	.	.	.	v*	p*	w*	n*	m*	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.
Auswertung	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.
c>a>b>d>e	.	.	.	.	.	.	a	b	d	e	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.
h>c>a>b>d>e	.	.	.	.	.	.	c	a	b	d	e	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.
h>f>g>i	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.
m>h>c>a>b>d>e	.	.	.	.	.	.	h	c	a	b	d	e	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.
m>f>g>i	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.
m>j>k>l	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.
p>n>o>q	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.
p>m>h>c>a>b>d>e	.	.	.	.	.	.	m	h	c	a	b	d	e	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.
t>r>s>u	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.
t>p>m>h>c>a>b>d>e	.	.	.	.	.	t	p*	m*	h	c	a	b	d	e	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.
t>v>w>x>y	.	.	.	.	.	v*	n*	j	f	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.
.	.	.	.	.	.	w*	o	k	g	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.
.	.	.	.	.	.	x	q	l	i	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.
.	.	.	.	.	.	y	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.
 

Falls das so passt wären nach sieben Rennen die drei schnellsten Pferde ermittelt, egal wie die Rennen unter den gegebenen Bedingungen ausgehen. Sechs Rennen, nach denen das schnellste Pferd gefunden ist, ein Vergleichsrennen* für die weiteren Plätze.
Dies ist für mich jetzt auch erst einmal eine Annäherung an die Fragestellung überhaupt. Ggf. ist so aber prinzipiell auch das Ranking der 25 Pferde herbeizuführen.


-----------------
Gruß haegar90



  Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6051
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.59, eingetragen 2019-09-28 10:59


Kurze Anmerkung:

Beim Sortieren mit 2er-Vergleichen ist die informationstheoretische untere Schranke: $\log_2{n!}$.
Für die Komplexität von Mergesort $M(n)$ gilt:
$M(1)=0, M(2)=1, M(2n)=2M(n)+2n-1, M(2n+1)=M(n)+M(n+1)+2n$.
Mit dem Mastertheorem kann man das auch auflösen (zumindest bis auf konstante Faktoren).

Viel Platz ist zwischen beiden Schranken dann nicht mehr.

Die Besonderheit von Sortiernetzen ist m.E., dass man hier viele Vergleiche parallelisiert und schaut, wie stark das das Sortieren beschleunigt.
Wäre vielleicht auch hier eine interessante Frage:
Wenn man 5 Rennbahnen hat und jeweils 5 Rennen mit 5 Pferden gleichzeitig durchführen kann, wie viele Runden braucht man dann?



  Profil  Quote  Link auf diesen Beitrag Link
Delastelle
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 17.11.2006
Mitteilungen: 1349
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.60, eingetragen 2019-09-28 15:33


Hallo,

ich habe zum Thema auch jemanden befragt;
als Literaturtip habe ich bekommen:
Richard Beigel/John Gill "Sorting n Objects with a k-Sorter"
und
Tony T.Lee "Generalized Recursive Sorting Networks"

Ich hoffe diese Literatur ist hilfreich.

Viele Grüße
Ronald

Edit: noch ein mitgelieferter Link (passt das zum Thema?)
en.wikipedia.org/wiki/K-way_merge_algorithm
Edit2: noch etwas Literatur:
De-Lei Lee and Kenneth E.Batcher
"A Multiway Merge Sorting Network"



  Profil  Quote  Link auf diesen Beitrag Link
cramilu
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 09.06.2019
Mitteilungen: 103
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.61, vom Themenstarter, eingetragen 2019-10-03 01:04


Hallo beisammen...

ich bin immer noch bei meinen 24-Er-Fallunterscheidungen für n=4 und R6=(a2;b1;c1;d1). Dauert halt...

@Delastelle:
Ich fürchte, das k-Sorting führt zu weit über den konkreten Kern dieses Threads hinaus. Im Beigel-Artikel "sorting n objects with a k-sorter" studiere ich gerade Abschnitt 8, "average case for k=3" daraufhin, ob sich Kitaktus' Strategie da irgendwie herausentwickeln lässt...

@haegar90:
Deine Annäherung ist goldrichtig! Der Ausgang Deines Vergleichsrennens* liefert mit dem dabei Drittplatzierten einen der Kandidaten für den insgesamt Viertschnellsten. Dafür kommen aus den vorherigen Rennen auch nur weitere vier in Betracht, so dass ein achtes Rennen eindeutig den Viertschnellsten liefert. Analog dazu kann man dann für die langsamsten Pferde vorgehen und so mit elf Rennen die vier schnellsten und die vier langsamsten kennen. Wieviele weitere Rennen man hernach benötigt, um die verbleibenden 17 Gäule zu sortieren, über die man ja aus den ersten elf Rennen auch schon manches ableiten kann, ist eine gute Frage und bereits seit vor einigen Beiträgen Teil meiner weiteren Überlegungen ;)

@Kitaktus:
Die Frage nach der Parallelisierbarkeit in "Runden" ist sicher spannend. Für n=2 mit mindestens 5 Rennen für das Gesamtranking wären es schon drei. Für n=3 mit Deiner Musterstrategie wären es mindestens drei, aber eher mehr, weil die Besetzung einer nächsten Runde ja stets vom Ausgang ggf. nur eines einzigen vorherigen Rennens abhängt. Die Frage würde sich wohl ändern müssen in "Welcher Grad an Parallelisierung ist von einem erforderlichen Entscheidungsrennen bis zum nächsten möglich?" Oder: Man vernachlässigt ggf. nach minimaler Rennenzahl optimierte Überlegungen und stellt solche von Vornherein für minimale Rundenzahlen an. Das ergäbe aber  einen anderen Thread, oder? ;)



  Profil  Quote  Link auf diesen Beitrag Link
cramilu hat die Antworten auf ihre/seine Frage gesehen.
Seite 2Gehe zur Seite: 1 | 2  
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2019 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]