Fragen zu Algorithmen, deren Verhalten nicht nur durch ihre Eingabe, sondern auch durch eine Zufallszahlenquelle bestimmt wird.
Ich habe zwei Möglichkeiten, eine Liste von Elementen in zufälliger Reihenfolge zu erstellen und möchte feststellen, ob sie gleichermaßen fair (unvoreingenommen) sind. Die erste Methode, die ich verwende, besteht darin, die gesamte Liste der Elemente zu erstellen und sie dann zu mischen (z. B. eine...
Generische Sortieralgorithmen verwenden im Allgemeinen einen Datensatz zum Sortieren und eine Komparatorfunktion, mit der zwei einzelne Elemente verglichen werden können. Wenn der Komparator eine Ordnungsrelation¹ ist, ist die Ausgabe des Algorithmus eine sortierte Liste / ein sortiertes Array. Ich...
Angenommen, wir haben eine Blackbox fff die wir abfragen und zurücksetzen können. Wenn wir zurückgesetzt fff , wird der Zustand fSfSf_S von fff ist an einem Element festgelegt gleichmäßig zufällig aus dem Satz gewählt {0,1,...,n−1}{0,1,...,n−1}\{0, 1, ..., n - 1\} wobei nnn fest ist und für...
PP\mathsf{P}kkkP T I M E ( f ( n ) )DTIME(nk)⊊PTIME(nk)DTIME(nk)⊊PTIME(nk)\mathsf{DTIME}(n^k) \subsetneq \mathsf{PTIME}(n^k)PTIME(f(n))PTIME(f(n))\mathsf{PTIME}(f(n)) die Menge von Sprachen, die durch ein randomisiertes TM mit konstant begrenztem (einseitigem oder zweiseitigem) Fehler in Schritten...
Der Ramer-Douglas-Peucker-Algorithmus zur Leitungsvereinfachung hat die Worst-Case- Laufzeit O ( n2)O(n2)O(n^2) . Für geeignet verteilte zufällige Eingaben wurde eine Laufzeitkomplexität von erwartet . In 2D gibt es andere Algorithmen mit der Laufzeitkomplexität ungünstigsten Fall , die genau...
Wie kann bei einem vorgespannten seitigen Die eine Zufallszahl im Bereich gleichmäßig erzeugt werden? Die Wahrscheinlichkeitsverteilung der Würfelflächen ist nicht bekannt. Es ist lediglich bekannt, dass jede Fläche eine Wahrscheinlichkeit ungleich Null aufweist und dass die
In ihrem Buch Randomized Algorithms , Motwani Raghavan und öffnet die Einführung mit einer Beschreibung ihrer Funktion RandQS - Randomisierte quicksort - wobei der Schwenk, zum Unterteilen des Satzes in zwei Teile verwendet wird , wird nach dem Zufallsprinzip ausgewählt. Ich habe seit einiger Zeit...
Sie und ein Freund haben sich während eines Konzerts gegenseitig verloren, und keiner ist sich sicher, welcher von Ihnen weiter vorne ist. Formal ist jede auf einer ganzzahligen Koordinate und kann nur auf eine höhere Koordinate zugehen oder an Ort und Stelle bleiben. Angenommen, Sie und Ihr Freund...
Der randomisierte Auswahlalgorithmus lautet wie folgt: Eingabe: Ein Array aus (der Einfachheit halber eindeutigen) Zahlen und einer ZahlAAAnnnk∈[n]k∈[n]k\in [n] Ausgabe: Das Element "Rang " von (dh das Element in Position wenn sortiert wurde)kkkAAAkkkAAA Methode: Wenn es ein Element in , geben Sie...
Aus Wikipedia über randomisierte Algorithmen Man muss unterscheiden zwischen Algorithmen , die die Zufallseingabe verwenden, um die erwartete Laufzeit oder den Speicherbedarf zu verringern, aber immer mit einem korrekten Ergebnis in einem begrenzten Zeitraum enden, und probabilistischen Algorithmen...
Ich habe dieses Buch für meine Klasse Randomized Algorithms gelesen . In diesem Buch gibt es einen ganzen Abschnitt, der sich mit der Ermittlung des Medians eines Arrays durch Zufallsauswahl befasst und zu einem effizienteren Algorithmus führt. Jetzt wollte ich wissen, ob es neben einer...
Alice, eine Studentin, hat in den nächsten Wochen eine Menge Hausaufgaben. Jede Hausaufgabe dauert genau einen Tag. Jeder Punkt hat auch eine Frist und einen negativen Einfluss auf ihre Noten (eine reelle Zahl voraussetzen, Bonuspunkte nur für die Annahme der Vergleichbarkeit), wenn sie die Frist...
Betrachten Sie eine Folge von nnn Flips einer unbefangenen Münze. Sei HiHiH_i der absolute Wert des Überschusses der Anzahl von Köpfen über Schwänzen, die in den ersten iii Flips gesehen wurden. Definiere H=maxiHiH=maxiHiH=\text{max}_i H_i . Zeigen Sie, dass E[Hi]=Θ(i√)E[Hi]=Θ(i)E[H_i]=\Theta (...
Der übliche einfache Algorithmus zum Finden des Medianelements in einem Array mit n Zahlen ist:AAAnnn Probe - Elemente von A mit Ersatz in Bn3/4n3/4n^{3/4}AAABBB Sortiere und finde den Rang | B | ± √BBB ElementelundrvonB.|B|±n−−√|B|±n|B|\pm \sqrt{n}lllrrrBBB Stellen Sie sicher, dass sich und r auf...
Bei der Arbeit wurde ich beauftragt, einige Typinformationen über eine dynamische Sprache abzuleiten. Ich schreibe Folgen von Anweisungen in verschachtelte letAusdrücke um, wie folgt: return x; Z => x var x; Z => let x = undefined in Z x = y; Z => let x = y in Z if x then T else F; Z =>...
Inspiriert von dieser Frage, bei der der Fragesteller wissen möchte, ob sich die Laufzeit ändert, wenn der in einem Standardsuchalgorithmus verwendete Komparator durch einen fairen Münzwurf ersetzt wird, und auch von Microsofts prominentem Versagen, einen einheitlichen Permutationsgenerator zu...
Ich bin verwirrt darüber, wie PP und BPP definiert sind. Nehmen wir an , ist die charakteristische Funktion für eine Sprache L . M ist die probabilistische Turingmaschine. Sind die folgenden Definitionen korrekt: B P P = { L : P r [ χ ( x ) ≠ M ( x ) ] ≥ 1χχ\chiLL\mathcal{L} P P = { L : P r [ χ ( x...
Randomisierte meldepflichtige Heaps haben eine Operation "Meld", mit der wir dann alle anderen Operationen definieren, einschließlich Einfügen. Die Frage ist, wie hoch ist die erwartete Höhe dieses Baums mit Knoten?nnn Satz 1 von Gambin und Malinkowski, Randomized Meldable Priority Queues...
Von den Beweisen durch die probabilistische Methode wird oft gesagt, dass sie nicht konstruktiv sind. Ein Beweis durch eine probabilistische Methode entwirft jedoch tatsächlich einen randomisierten Algorithmus und verwendet ihn zum Nachweis der Existenz. Zitiert aus Seite 103 der randomisierten...
In einem Graphen wir den folgenden Prozess aus:G(V,E)G(V,E)G(V,E) Anfangs sind alle Knoten in ungefärbt.VVV Während es in ungefärbte Knoten gibt, führt jeder ungefärbte Knoten Folgendes aus: VVV Wählt eine zufällige reelle Zahl aus und sendet sie an alle Nachbarn. Vergleicht seine Nummer mit der...