4. wie kann ich mathematisch diese werte verifizieren?

wie kann ich mathematisch diese werte verifizieren?

  • O

    also, ich hab für den bundeswettbewerb informatik ein paar aufgaben gelöst unter anderem diese:

    man hat einen würfel mit den maßen 20x20x20, der würfel besteht aus feldern, die genau 1x1x1 groß sind, und nur 2 zustände haben: "gefüllt" oder "leer".
    die chance dass ein feld gefüllt ist, nenn ich mal p,der wert ist variabel.

    die aufgabe war nun herauszufinden, ob es irgendeinen weg von oben durch den würfel nach unten gibt.(ein seitlicher eintritts- /austrittspunkt zählt nicht).
    Die bedingen sind dabei: ein weg existiert nur, wenn 2 felder eine seite gemeinsam haben, und beide "leer" sind.

    nun zum problem: im zweiten teil der aufgabe soll man eine art gesetzmäßigkeit finden, bzw einen schluss ziehen, ich hab dafür an die 33000 tests gemacht, die werte sind aber so komisch, dass ich sie erstmal mathematisch beweisen muss, aber nicht weis wie.

    zum test, ich hab jeweils 3x 1000 tests für je einen p-wert gemacht, im folgenden stehen die ergenisse in der form: wert von p|weg existiert| weg existiert nicht (zb 10|10|9900 heisst: bei einem p von 10 wurde 10mal der weg gefunden,990mal aber nicht).

    0|1000|0 0|1000|0 0|1000|0
    100|0|1000 100|0|1000 100|0|1000
    dies sind die placebo tests

    nun die richtigen:
    10|1000|0 10|1000|0 10|1000|0
    20|1000|0 20|1000|0 20|1000|0
    30|1000|0 30|1000|0 30|1000|0
    40|1000|0 40|1000|0 40|1000|0
    50|1000|0 50|1000|0 50|1000|0
    60|1000|0 60|1000|0 60|1000|0
    70|57|943 10|53|947 10|51|949
    80|0|1000 80|0|1000 80|0|1000
    90|0|1000 90|0|1000 90|0|1000

    man sieht, dass bis 70% immer ein weg gefunden wird(hab ich mehrere male überprüft), bei 70% es dann aber abrupt dreht, und dann bis zum ende nie ein weg gefunden wird.

    kann man das mathematisch beweisen? könnte das in etwa stimmen?

    0
  • M

    nun,... also, die aufgabe will ich auch noch lösen 🙂

    erstmal: wie du siehst, bis 60% findet er immer einen Weg, ab 80% nie mehr einen. d.h. zwischen 60% und 80% passiert am meisten, wies aussieht. Daher würde ich mal jetzt zB zwischen 60% und 80% in 1%-Schritten aufwärts gehen, und mir den Graphen dann erstmal skizzieren, zB Wege gehen durch in abhängigkeit von p.
    DAnn kommt irgendne kurve raus, vielleicht kann man damit was anfangen

    0
  • M

    Maxi schrieb:

    erstmal: wie du siehst, bis 60% findet er immer einen Weg, ab 80% nie mehr einen.

    Sollte die "obere Schranke" ab der keine Wege mehr gefunden werden nicht höher liegen?
    Ich denke bis zu einer Nicht-Füllung von 1/400 der Würfel müsste ein Weg möglich sein, da der Weg mit den wenigsten Löchern wohl der ist, wenn gerade von oben nach unten Löcher in einer Reihe sind. 1/400 = 0,25% ... d.h. bis zu einer Füllung von 99,75% sollte ein Weg möglich sein. (1/400 da 20 von 20*20*20 möglichen Löchern vorhanden sein müssen)

    Genauso die "untere Schranke" ab der eine Blockierung möglich ist.
    Ich würde hier ansetzen, dass für eine Blockade mindestens eine Füllung mit 400 Würfeln notwendig ist, d.h. es funktioniert ab dann, wenn eine "Ebene" komplett belegt ist und die hat eben 400 Würfel. Da der Gesamtwürfel insgesamt 20*20*20 Würfel hat, wäre eine Blockade ab einer Füllung von 1/20 möglich, d.h. ab einer Füllung von 5%.

    0
  • M

    ja, es ist theoretisch möglich, dass bei 400 geschlossenen Kästchen kein weg durckgeht. Aber auch bei 400 geschlossenen ist es mögluch, dass da wasser durchkommt, die müssen ja nciht auf einer ebene liegen. Die füllung wird ja für jeden kleinen würfel zufällig bestimmt, deswegen kann das schon richtig sein, mit dem duchgang der flüssigkeit, aber genau weiß ichs auch cnith. wenn ich mein proggi geschrieben habe, dann werd ichs vielleicht auch mla posten

    0
  • O

    ich glaub immer mehr an einen fehler im algorithmus, so abrupt kann sich das nicht ändern(und diese werte sind bis auf jene mit p=70 konstant), es gibt zwischendurch keinen ausreisser
    //edit zwischen 61 und 75% spielen sich die veränderungen ab..

    0
  • M

    was ist bei dir p?
    ist p die wahrscheinloichkeit ob kästchen voll ist, oder ist es die wahrscheinlichkeit, ob kästchen leer ist?

    bei mir ist p die Wahrscheinlichkeit, ob das kästchen leer ist.
    Da hab ich genau bei 30% fast ne endlosschleife in der rekursion, also, der rödelt da zT ewig, um nen Durchbruch zu finden. bei anderen Werten geht es relativ schnell. Da ist wohl irgendwas bei 30% (bzw. 70% andersrum gesehen)

    0
  • J

    eine ganz kleine Idee zum Berechnen der Wahrscheinlichkeit:

    P(es gibt Weg bis Ebene t) = P(Es gibt Weg bis Ebene t | Es gibt Weg von bis Ebene t-1)*P(es gibt Weg bis Ebene t-1)

    Wobei P(a|b): Wahrscheinlichkeit von a, falls b eingetreten ist. Ich vermute die Formeln werden sehr eklig, aber mit einem vernünftigen Programm müßte sich das ganze dennoch lösen lassen.

    MfG Jester

    0
  • O

    @maxi laut aufgabenstellung ist p die wahrscheinlichkeit, dass voll^^
    @jester ich glaub, ich hab deinen post nicht verstanden^^

    @maxi kommt denn bei dir auch so ein wertbild raus?

    0
  • C
    Mod

    Jester schrieb:

    P(es gibt Weg bis Ebene t) = P(Es gibt Weg bis Ebene t | Es gibt Weg von bis Ebene t-1)*P(es gibt Weg bis Ebene t-1)

    Die Aufgabenstellung gestattet auch Umwege, also Wege die über kurze Abschnitte in die Gegenrichtung führen. IMHO beachtet deine Formel das nicht.

    0
  • M

    ich bin mir nicht ganz sicher, ob das wasser auch nach oben fließen kann, zZ benutz ich nur die Richtungen rechts links vorne hinten und unten. nach oben fließt es noch ncith. Aber es kommt ein ähnlches Wertbild raus. Ich weiß nciht genau, ob das in der Aufgabenstellung steht, dass es auch na h oben fließt, wenn ja, dann könnte ich das noch schnell einbauen.

    0
  • J

    cd9000 schrieb:

    Jester schrieb:

    P(es gibt Weg bis Ebene t) = P(Es gibt Weg bis Ebene t | Es gibt Weg von bis Ebene t-1)*P(es gibt Weg bis Ebene t-1)

    Die Aufgabenstellung gestattet auch Umwege, also Wege die über kurze Abschnitte in die Gegenrichtung führen. IMHO beachtet deine Formel das nicht.

    Doch. Wenn man nicht bis Ebene t-1 kam, dann kann man auch nicht bis Ebene t kommen. Egal welchen Zick-Zack-Weg man wählt.

    0
  • M

    ja...
    und wie berechne ich P(Es gibt Wege bis ebene t, wenn es wege bis ebene t-1 gibt)?

    0
  • J

    Soll ich jetzt hier die Lösung bauen?

    Vielleicht nützt das ja auch garnix, aber es ist ein Ansatz um das ganze etwas runzertubrechen. Man muß immer nur noch die nächste Ebene dazunehmen und nichtmehr den ganzen Würfel auf einmal anschaun...

    Aber Du hast's richtig erkannt... das ist der Knackpunkt. Aber das ist auch viel kleiner, vielleicht kann man das mit dem Rechner komplett berechnen?

    MfG Jester

    0
  • M

    wie schon in dem tollen access violation post im c++ forum geschildert solltet ihr bei eurer rekursion die bereits besuchten felder als bereits besucht markieren dann vermeidet ihr endlosschleifen...

    0
  • J

    @muhkuhmasta: hast Du den Thread schon gelesen?

    0
  • O

    muhkuhs chau mal in deinen thread, da steht was intressantes für dich^^

    @maxi die aufgabenstellung erlaubt ein beliebiges wasserfließen 🙂

    @jester, so wie ich dich verstanden hab, willst du so eine art rekursion erzeugen, und dich in ihr schrittweise nach unten bewegen? das geht aber nicht, wenn das wasser wieder 2-3 felder nach oben fließt.

    0
  • M

    ich versuchs mal auszurechnen...

    also, Schicht 0:
    20*20 Felder, es Besteht demzufolge, wenn p die Wahrscheinlichkeit ist, dass ein Kästchen leer ist:

    die Wahrscheinlichkeit, dass ein Kästchen voll ist ist demnach 1-p

    Jedes 1/p. Kästchen ist leer (durchschnittlich), d.h. in jeder Schicht sind 20*20/(1/p)=20*20p leer. Diese sind irgendwo verteilt.
    um in die zweite Schicht zu kommen, muss ein leeres Kästchen in Schicht 2 unter einem leeren Kästchen in Schicht 1 sein.
    Jedes Kästchen hat 20*20 mögliche Positionen. Die Chance, dass es eine bestimmte Position hat, ist also 1/(20*20). Die Chance, dass eins von 20*20*p Kästchen an einer bestimmten Position ist, ist also 20*20*p/20*20 = p. In der Schicht darüber haben ist auch die Chance p, dass eins von 20*20*p kästchen eine ganz bestimmte Poisiton hat. Nun gibt es 20*20*p positionen die leer sind auf der oberen und 20*20    p die leer sind auf der unteren Schicht.
    Ist jetzt die Chance, dass es mindestens eine Position gibt, wo zwei leer kästchen übereinander liegen p1*p2?
    Das wäre dann also p1*p2=20*20*p*20*20*p = 204*p2

    Ich weiß jetzt ncizht ob das stimmt, ich kenn mich in stahastik/statistik so gut wie gar nciht aus. Außerdem berechnet man damit ja nur die Chance, dass zwei Kästchen übereinander liegen, um nach unten zu kommen. Es wird aber nciht beachtet, ob man überhaupt vom eintrittsloch zum austrittsloch gelangt...
    also ist die rechnung eigentlichb sinnlos

    0
  • M

    also ich hab mal mit meinem programm gerechnet. bei allen werten unter 69% käse kam praktisch immer wasser durch, dann sank die wahrscheinlichkeit immer schneller, bis zu so 76%. ab da verringerte sich die abnahme bis dann bei 84% nur noch 0,04% wasserdurchlässig waren

    0
  • O

    wieviele tests?
    //edit muhkuh ich verweise dich nochmal auf den thread im c++ teil 🙂

    0
  • M

    ne menge (5*2^16 ungefähr)

    //edit pro pozentsatz 😃 ... ich hab fast ne stunde rechnen lassen

    0
Anmelden zum Antworten