Questions sur les algorithmes dont le comportement est déterminé non seulement par son entrée mais aussi par une source de nombres aléatoires.
J'ai deux façons de produire une liste d'articles dans un ordre aléatoire et je voudrais déterminer s'ils sont également équitables (sans biais). La première méthode que j'utilise est de construire la liste complète des éléments puis de faire un shuffle dessus (disons un shuffle de Fisher-Yates)....
Les algorithmes de tri génériques prennent généralement un ensemble de données à trier et une fonction de comparaison qui peut comparer deux éléments individuels. Si le comparateur est une relation d'ordre¹, la sortie de l'algorithme est une liste / tableau trié. Je me demande si les algorithmes de...
Supposons que nous ayons une boîte noire que nous pouvons interroger et réinitialiser. Lorsque nous réinitialisons , l'état de est défini sur un élément choisi uniformément au hasard dans l'ensemble où est fixe et connu pour donné . Pour interroger , un élément (la supposition) de est fourni, et la...
Y a-t-il des problèmes dans qui ont des algorithmes randomisés dépassant les limites inférieures des algorithmes déterministes? Plus concrètement, connaissons-nous des pour lesquels ? Ici \ mathsf {PTIME} (f (n)) signifie l'ensemble des langages décidables par une MT aléatoire avec une erreur...
L' algorithme Ramer-Douglas-Peucker pour la simplification de ligne a le pire cas d' exécution . Pour des entrées aléatoires convenablement réparties, il s'est attendu à une complexité d'exécution O ( n log n ) . En 2D, il existe d'autres algorithmes avec la pire complexité d'exécution O ( n log n...
Dans leur livre Randomized Algorithms , Motwani et Raghavan ouvrent l'introduction avec une description de leur fonction RandQS - Randomized quicksort - où le pivot, utilisé pour partitionner l'ensemble en deux parties, est choisi au hasard. J'ai accumulé mes cerveaux (certes un peu sous-alimentés)...
Étant donné un dé biaisé de côté , comment générer uniformément un nombre aléatoire dans la plage ? La distribution de probabilité des faces du dé n'est pas connue, tout ce que l'on sait, c'est que chaque face a une probabilité non nulle et que la distribution de probabilité est la même sur tous...
Vous et un ami vous êtes perdus sur la ligne à un concert, et vous ne savez pas lequel d'entre vous est plus avancé. Formellement, chacun a une coordonnée entière et ne peut marcher que vers une coordonnée plus élevée ou rester en place. En supposant que vous et votre ami suivez exactement le même...
L'algorithme de sélection aléatoire est le suivant: Entrée: un tableau de nombres (distincts, pour simplifier) et un nombren k ∈ [ n ]AAAnnnk∈[n]k∈[n]k\in [n] Sortie: le " élément de rang " de A (c'est-à-dire celui en position k si A a été trié)A k AkkkAAAkkkAAA Méthode: S'il y a un élément dans...
De Wikipedia sur les algorithmes randomisés Il faut distinguer les algorithmes qui utilisent l'entrée aléatoire pour réduire le temps d'exécution prévu ou l'utilisation de la mémoire, mais qui se terminent toujours par un résultat correct dans un laps de temps limité, et les algorithmes...
J'ai lu ce livre pour ma classe, Randomized Algorithms. Dans ce livre en particulier, il existe une section entière dédiée à la recherche de la médiane d'un tableau à l'aide de la sélection aléatoire, ce qui conduit à un algorithme plus efficace. Maintenant, je voulais savoir s'il existe des...
Alice, une étudiante, a beaucoup de devoirs au cours des prochaines semaines. Chaque devoir lui prend exactement une journée. Chaque élément a également une date limite et un impact négatif sur ses notes (supposez un nombre réel, des points bonus pour ne supposer que la comparabilité), si elle...
Considérons une séquence de nnn flips d'une pièce non biaisée. Soit HiHiH_i la valeur absolue de l'excédent du nombre de têtes sur les queues vu dans les premiers iii flips. Définissez H=maxiHiH=maxiHiH=\text{max}_i H_i . Montrer que E[Hi]=Θ(i√)E[Hi]=Θ(i)E[H_i]=\Theta ( \sqrt{i}...
L'algorithme simple habituel pour trouver l'élément médian dans un tableau de n nombres est:UNEAAnnn Echantillon des éléments de A , avec remplacement en Bn3 / 4n3/4n^{3/4}UNEAABBB Triez et trouvez le rang | B | ± √BBB élémentsletrdeB|B|±n−−√|B|±n|B|\pm \sqrt{n}lllrrrBBB Vérifier que et r sont de...
Au travail, j'ai été chargé de déduire des informations de type sur un langage dynamique. Je réécris des séquences d'instructions en imbriquéeslet expressions , comme ceci: 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 => if x then...
Inspiré par cette question dans laquelle le demandeur veut savoir si le temps d'exécution change lorsque le comparateur utilisé dans un algorithme de recherche standard est remplacé par un coin-flip équitable, et aussi l' échec de Microsoft pour écrire un générateur de permutation uniforme, ma...
Je suis confus quant à la façon dont PP et BPP sont définis. Supposons χχ\chi est la fonction caractéristique d'un langage LL\mathcal{L} . M être la machine de Turing probabiliste. Les définitions suivantes sont-elles correctes: P P = { L : P r [ χ ( x ) ≠ M ( x ) ] >...
Les tas soudables randomisés ont une opération "fusion", que nous utilisons ensuite pour définir toutes les autres opérations, y compris l'insertion. La question est, quelle est la hauteur attendue de cet arbre à nnn nœuds? Le théorème 1 de Gambin et Malinkowski, Randomized Meldable Priority Queues...
Étant donné un graphique , où . Qu'est - ce qu'un algorithme rapide pour générer la collection de toutes les listes de quartier 2-hop de tous les nœuds .G = ( V, E)g=(V,E)G = (V,E)| V| =n|V|=n|V| = nVVV Naïvement, vous pouvez le faire en . Avec la puissance des matrices, vous pouvez le faire avec...
Sur un graphique G(V,E)G(V,E)G(V,E), nous effectuons le processus suivant: Initialement, tous les nœuds VVV sont incolores. Bien qu'il existe des nœuds non colorés dans VVV, chaque nœud non coloré effectue les opérations suivantes: Sélectionne un nombre réel aléatoire et l'envoie à tous ses...