Algorithmenaufgabe

Wissenschaft Informatik
#1

Hallo Leute,

hab da mal eine Frage zur ne aufgabe wo ich nicht durchsteige…

ALso. Sei B ein randomisierter Algorithmus für ein Problem, der zu jedem Zeitpunkt entweder die richtige Ausgabe oder ein „?“ ausgibt. Die erwartete Zahl von Schritten bis das richtige Ergebnis ausgegebn wird sei n^2.
Angenommen man kann den Algo. B jeweils zu einem beliebigen Zeitpunkt, anhalten, sein Ergebnis auslesen und diese Schritte unabhängig wiederholen. Wie kann man daraus einen randomisierten Algo. B’ konsturieren der mit möglichst großer Wahrscheinlichkeit das richtige Ergebnis nach n^3 Schritten ausgibt?

grüße, nadine.

#2

Moin

Lass mich raten: „Grundlagen der Programmierung“ ?

ALso. Sei B ein randomisierter Algorithmus für ein Problem,
der zu jedem Zeitpunkt entweder die richtige Ausgabe oder ein
„?“ ausgibt. Die erwartete Zahl von Schritten bis das richtige
Ergebnis ausgegebn wird sei n^2.

Im Klartext: nach n^2 hat er entweder raus oder es kommt wahrscheinlich nix gutes raus.

Wie kann man daraus einen
randomisierten Algo. B’ konsturieren der mit möglichst großer
Wahrscheinlichkeit das richtige Ergebnis nach n^3 Schritten
ausgibt?

Einfach: Lass B A starten und nach n^2 Schritten abbrechen. Lies das Ergebniss aus. Ist es richtig: Abbruch, ist es „?“: nochmal von vorne.

Nach n-mal A ausführen (Was insgesamt n^3 entspricht) sollte A das richtige gefunden haben (oder A ist zu doff dafür…)

cu

#3

hallo,

ja das ist sozusage eine einführung:smile:
man soll das irgendwie mit der markoffungleichung lesen…geht das denn?
grüße

#4

Moin

ja das ist sozusage eine einführung:smile:

Ach, dann hast du den Spass noch vor dir.

man soll das irgendwie mit der markoffungleichung lesen…geht
das denn?

sorry, da kann ich dir nicht mehr helfen. markoff sagt mir gar nichts.

cu