Randomized algorithm (original) (raw)
Pravděpodobnostní (náhodnostní) algoritmy jsou nedeterministické algoritmy, které se snaží najít řešení rychleji nebo řešení těžko řešitelných problémů, často tzv. NP-úplných problémů. Pravděpodobnostní algoritmus se může náhodně rozhodovat mezi různými možnostmi jak pokračovat. Pro stejný vstup může dávat takový algoritmus různé výsledky, které mohou být dokonce nesprávné. Mnohdy se tedy na daném vstupu spustí pravděpodobnostní algoritmus vícekrát, aby se s větší pravděpodobností dospělo ke správnému výsledku.
| Property | Value |
|---|---|
| dbo:abstract | الخوارزمية العشوائية هي خوارزمية توظف درجة عشوائية كجزء من منطقها. تستخدم الخوارزمية عادةً البتات العشوائية بشكل موحد كمدخل مساعد لتوجيه سلوكها، على أمل تحقيق أداء جيد في «الحالة المتوسطة» على جميع الخيارات الممكنة للبت العشوائي. بشكل رسمي، سيكون أداء الخوارزمية متغيرًا عشوائيًا تحدده البتات العشوائية؛ وبالتالي إما وقت التشغيل، أو الإخراج (أو كليهما) هي متغيرات عشوائية. على المرء أن يميز بين الخوارزميات التي تستخدم المدخلات العشوائية بحيث تنتهي دائمًا بالإجابة الصحيحة، ولكن عندما يكون وقت التشغيل المتوقع محدودًا (خوارزميات لاس فيجاس، مثال ذلك والتي هي ترتيب سريع) ، والخوارزميات التي لها فرصة من إنتاج نتيجة غير صحيحة (خوارزميات مونتي كارلو، ومثال على ذلك خوارزمية مونتي كارلو ل MFAS ) أو فشل لإنتاج نتيجة إما عن طريق التأشير إلى فشل أو فشل في إنهاء.في الحالة الثانية، الأداء العشوائي والإخراج العشوائي، فإن مصطلح «الخوارزمية» لإجراء ما هو موضع شك إلى حد ما. في حالة المخرجات العشوائية، لم تعد فعالة بشكل رسمي. ومع ذلك، في بعض الحالات، تكون الخوارزميات الاحتمالية هي الوسيلة العملية الوحيدة لحل مشكلة ما.في الممارسة الشائعة، يتم تقريب الخوارزميات العشوائية باستخدام مولد رقم عشوائي زائف بدلاً من مصدر حقيقي للبتات العشوائية؛ مثل هذا التنفيذ قد ينحرف عن السلوك النظري المتوقع. (ar) Un algorisme probabilista (o probabilístic) és un algorisme que basa el seu resultat en la presa d'algunes decisions a l'atzar, de tal manera que, de mitjana, obté una bona solució al problema plantejat per a qualsevol distribució de les dades d'entrada. És a dir, al contrari que un algorisme determinista, a partir d'uns mateixes dades es poden obtenir diferents solucions i, en alguns casos, solucions errònies. Hi ha diversos tipus d'algorismes probabilístics depenent del seu funcionament, es poden distingir: * Algorismes numèrics, que proporcionen una solució aproximada del problema. * Algorismes de Monte Carlo, que poden donar la resposta correcta o resposta errònies (amb probabilitat baixa). * Algorismes de Las Vegas, que mai no donen una resposta incorrecta: o bé donen la resposta correcta o informen de la decisió. (ca) Pravděpodobnostní (náhodnostní) algoritmy jsou nedeterministické algoritmy, které se snaží najít řešení rychleji nebo řešení těžko řešitelných problémů, často tzv. NP-úplných problémů. Pravděpodobnostní algoritmus se může náhodně rozhodovat mezi různými možnostmi jak pokračovat. Pro stejný vstup může dávat takový algoritmus různé výsledky, které mohou být dokonce nesprávné. Mnohdy se tedy na daném vstupu spustí pravděpodobnostní algoritmus vícekrát, aby se s větší pravděpodobností dospělo ke správnému výsledku. (cs) Hazardigita algoritmo aŭ probableca algoritmo estas algoritmo kiu uzas iun gradon de hazardon kiel parto de sia logiko. En komuna praktiko, ĉi tio signifas ke la maŝino realiganta la algoritmon havas atingon al . Por ĉi tiuj algoritmoj la estas tipe malverŝajna kaj tiel povas esti ignorita. (eo) Ein randomisierter Algorithmus (auch stochastischer oder probabilistischer Algorithmus) ist ein Algorithmus, der versucht, durch die Wahl von zufälligen Zwischenergebnissen zu einem (im Mittel) guten bzw. näherungsweise korrekten Ergebnis zu gelangen. Er bildet somit das Gegenstück zum deterministischen Algorithmus. Es wird dabei nicht verlangt, dass ein randomisierter Algorithmus immer effizient eine richtige Lösung findet. Randomisierte Algorithmen sind in vielen Fällen einfacher zu verstehen, einfacher zu implementieren und effizienter als deterministische Algorithmen für dasselbe Problem. Ein Beispiel, das dies zeigt, ist der AKS-Primzahltest, der zwar deterministisch ist, aber viel ineffizienter und viel schwieriger zu implementieren als beispielsweise der Primzahltest von Solovay und Strassen. (de) En algorithmique, un algorithme probabiliste, ou algorithme randomisé, est un algorithme qui utilise une source de hasard. Plus précisément le déroulement de l’algorithme fait appel à des données tirées au hasard. Par exemple à un certain point de l’exécution, on tire un bit 0 ou 1, selon la loi uniforme et si le résultat est 0, on fait une certaine action A et si c'est 1, on fait une autre action. On peut aussi tirer un nombre réel dans l'intervalle [0,1] ou un entier dans un intervalle [i..j]. Les algorithmes probabilistes sont étudiés car ils sont souvent plus simples à analyser et très souvent plus rapides. (fr) Un algoritmo probabilista (o probabilístico) es un algoritmo que basa su resultado en la toma de algunas decisiones al azar, de tal forma que, en promedio, obtiene una buena solución al problema planteado para cualquier distribución de los datos de entrada. Es decir, al contrario que un algoritmo determinista, a partir de unos mismos datos se pueden obtener distintas soluciones y, en algunos casos, soluciones erróneas. Existen varios tipos de algoritmos probabilísticos dependiendo de su funcionamiento, pudiéndose distinguir: * Algoritmos numéricos, que proporcionan una solución aproximada del problema. * Algoritmos de Montecarlo, que pueden dar la respuesta correcta o respuesta erróneas (con probabilidad baja). * Algoritmos de Las Vegas, que nunca dan una respuesta incorrecta: o bien no encuentran la respuesta correcta e informan del fallo. (es) A randomized algorithm is an algorithm that employs a degree of randomness as part of its logic or procedure. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performance in the "average case" over all possible choices of random determined by the random bits; thus either the running time, or the output (or both) are random variables. One has to distinguish between algorithms that use the random input so that they always terminate with the correct answer, but where the expected running time is finite (Las Vegas algorithms, for example Quicksort), and algorithms which have a chance of producing an incorrect result (Monte Carlo algorithms, for example the Monte Carlo algorithm for the MFAS problem) or fail to produce a result either by signaling a failure or failing to terminate. In some cases, probabilistic algorithms are the only practical means of solving a problem. In common practice, randomized algorithms are approximated using a pseudorandom number generator in place of a true source of random bits; such an implementation may deviate from the expected theoretical behavior and mathematical guarantees which may depend on the existence of an ideal true random number generator. (en) 확률적 알고리즘(probabilistic algorithm) 또는 무작위 알고리즘(randomized algorithm)은 난수를 발생시켜 진행과정을 결정하는 알고리즘이다. 난수를 발생시키는 과정은 흔히 '동전을 던진다'고 표현하며, 실제로는 를 사용한다. 알고리즘의 성능을 평균적으로 향상시키기 위해 난수를 사용한다. 난수를 사용하기 때문에 알고리즘의 성능은 확률변수이며, 확률변수의 기댓값이 실제로 원하는 성능이다. 알고리즘 성능의 최악의 경우는 일어날 확률이 극히 작기 때문에 대부분 무시한다. (ko) Un algoritmo randomizzato è un algoritmo che include un certo grado di casualità nella sua logica. Tipicamente l'algoritmo utilizza variabili aleatorie come input ausiliario per guidare il suo comportamento con l'obiettivo di ottenere, in media, buone prestazioni. Le prestazioni dell'algoritmo, inclusi il tempo di esecuzione o l'output, saranno a loro volta casuali. In base all'utilizzo che viene fatto delle variabili casuali, l'algoritmo può essere progettato per restituire sempre la risposta corretta, a scapito del tempo di calcolo, o per prevedere anche che il risultato calcolato possa essere errato con una certa probabilità (algoritmo Monte Carlo). Gli algoritmi randomizzati sono particolarmente utili di fronte a utenti malevoli, e quindi ampiamente utilizzati con applicazioni crittografiche; in questi casi, tuttavia, sono necessari accorgimenti per evitare che i numeri pseudo-casuali vengano predetti, rendendo l'algoritmo sostanzialmente deterministico. Un tipico esempio di algoritmo randomizzato è il quicksort . In alcuni casi, gli algoritmi probabilistici sono l'unico mezzo pratico per risolvere un problema . (it) 乱択アルゴリズム（らんたくアルゴリズム）、ランダム・アルゴリズム（英: randomized algorithm）または確率的アルゴリズム（かくりつてきアルゴリズム、（英: probabilistic algorithm）は、その論理の一部に無作為性を導入したアルゴリズムである。通常のアルゴリズムでは自然数を順番にあてはめるような決定的な部分で、乱数による非決定的な選択を入れることで、「平均的に」よい性能を実現することを目的とすることがある。形式的には、乱択アルゴリズムの性能はランダムビット列で決定される確率変数となる。その期待値を期待実行時間と呼ぶ。最悪の場合に関して「無視できる」ほどに低い確率であることが、一般に、この類のアルゴリズムが効果的である要件となる。 (ja) Algorytm probabilistyczny albo randomizowany to algorytm, który do swojego działania używa losowości. W praktyce oznacza to, że implementacja takiego algorytmu korzysta przy obliczeniach z generatora liczb losowych. Główną zaletą algorytmów probabilistycznych w porównaniu z deterministycznymi jest działanie zawsze w „średnim przypadku”, dzięki czemu „złośliwe" dane wejściowe nie wydłużają jego działania. Formalnie efektywność takiego algorytmu jest zmienną losową określoną na przestrzeni możliwych losowych ciągów. Wartość oczekiwana takiej zmiennej nazywana jest oczekiwanym czasem działania. Przypadek pesymistyczny jest zwykle na tyle mało prawdopodobny, że można go pominąć w analizie. (pl) Вероятностный алгоритм — алгоритм, предусматривающий обращение на определённых этапах своей работы к генератору случайных чисел с целью получения экономии во времени работы за счёт замены абсолютной достоверности результата достоверностью с некоторой вероятностью. (ru) Um algoritmo probabilístico é um algoritmo que utiliza a probabilidade como parte de sua lógica. Na prática, isso significa que a máquina que implementa o algoritmo deve acessar um gerador de números pseudo-aleatórios. O algoritmo utiliza bits aleatórios como um guia para o seu comportamento. Diferente dos algoritmos convencionais, um algoritmo probabilístico, dada uma mesma sequência de entrada, não necessariamente leva a um mesmo estado final. (pt) Увипадковлений алгоритм (англ. randomized algorithm) — це алгоритм, який використовує елемент випадковості як частину своєї логіки. Алгоритм зазвичай використовує рівномірно випадкові біти як допоміжний вхід для спрямування своєї поведінки в надії досягнення хорошої швидкодії в середньому серед усіх можливих виборів випадкових бітів. Формально, швидкодією алгоритму буде випадкова величина визначена випадковими бітами; отже або швидкодія, або вихід (або і те, і те) є випадковими величинами. Потрібно розрізняти алгоритми, що використовують випадковий вхід для зменшення очікуваного часу виконання або об'єму використаної пам'яті, але завжди видають правильний вислід у обмежений відтинок часу, і ймовірнісні алгоритми (англ. probabilistic algorithms), які, залежно від випадкового входу, можуть видати некоректний вислід або зазнати невдачі в його отриманні (Алгоритм Лас-Вегаса), повідомивши про провал або через неможливість завершення. У другому випадку, випадкового виконання і випадкового виходу, використання терміну «алгоритм» під питанням. У разі випадкового виходу, формально це вже не алгоритм.Однак, у деяких випадках, ймовірнісні алгоритми є єдиним практичним способом розв'язання проблеми. Практично, увипадковлений алгоритм моделюють із використанням генератора псевдовипадкових чисел замість дійсно випадкових біт; таке втілення може відхилятись від очікуваної в теорії поведінки. (uk) 随机化算法（randomized algorithm），是这样一种算法，在算法中使用了随机函数，且随机函数的返回值直接或者间接的影响了算法的执行流程或执行结果。就是将算法的某一步或某几步置于运气的控制之下，即该算法在运行的过程中的某一步或某几步涉及一个随机决策，或者说其中的一个决策依赖于某种随机事件。 (zh) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Single_run_of_Karger’s_Mincut_algorithm.svg?width=300 |
| dbo:wikiPageExternalLink | https://www.springer.com/de/book/9783642551970 http://portal.acm.org/citation.cfm%3Fid=234313.234327 |
| dbo:wikiPageID | 495383 (xsd:integer) |
| dbo:wikiPageLength | 26736 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1083506589 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Prisoner's_dilemma dbr:Probabilistic_Turing_machine dbr:Quantum_computer dbr:Quicksort dbr:Robert_M._Solovay dbr:Eli_Upfal dbr:Monte_Carlo_algorithm dbr:NP_(complexity) dbr:Method_of_conditional_probabilities dbr:Principle_of_deferred_decision dbr:Probabilistic_analysis_of_algorithms dbr:Primality_test dbr:Bogosort dbr:Bounded-error_probabilistic_polynomial dbr:Algorithm dbc:Randomized_algorithms dbr:Approximate_counting_algorithm dbr:Jon_Kleinberg dbr:Cyber-physical_system dbr:Volker_Strassen dbr:Decision_problem dbr:Delaunay_triangulation dbr:Deterministic_algorithm dbr:Introduction_to_Algorithms dbr:Thomas_H._Cormen dbr:Worst-case_complexity dbr:Computer_software dbr:Conditional_probability dbr:Count–min_sketch dbr:Cryptographically_secure_pseudo-random_number_generator dbr:Cryptography dbr:Analysis_of_algorithms dbr:Clifford_Stein dbr:Monte_Carlo_method dbr:Convex_hull dbr:Probabilistic_roadmap dbr:Zoltán_Füredi dbr:Pseudorandom dbr:Communication_complexity dbr:Competitive_analysis_(online_algorithm) dbr:Complexity_class dbr:Computational_complexity_theory dbr:Computational_geometry dbr:Éva_Tardos dbr:P_(complexity) dbr:Michael_Mitzenmacher dbr:Karger's_algorithm dbr:Las_Vegas_algorithm dbr:AKS_primality_test dbr:Cut_(graph_theory) dbr:Expander_graph dbr:Number_theory dbr:PSPACE dbr:Pairwise_independence dbr:Discrepancy_theory dbr:Graph_theory dbr:Pseudorandom_number_generator dbr:Random dbr:Randomness dbr:Atlantic_City_algorithm dbr:Attacker dbr:HyperLogLog dbr:Solovay–Strassen_primality_test dbr:Prime_number dbr:Array_data_structure dbc:Analysis_of_algorithms dbr:Charles_E._Leiserson dbr:Big_O_notation dbr:Edge_contraction dbr:ZPP_(complexity) dbr:Disperser dbr:Square_root dbr:Embedded_systems dbr:Polynomial_time dbr:Miller–Rabin_primality_test dbr:RP_(complexity) dbr:Rajeev_Motwani dbr:Random-access_machine dbr:Chemical_reaction_network dbr:Markov's_inequality dbr:Turing_machine dbr:Uniform_distribution_(discrete) dbr:IP_(complexity) dbr:Imre_Bárány dbr:Pocklington's_algorithm dbr:Universal_hashing dbr:Randomized_algorithms_as_zero-sum_games dbr:Primitive_recursive dbr:Pessimistic_estimator dbr:Big_Theta_notation dbr:Minimum_feedback_arc_set dbr:Ronald_L._Rivest dbr:Randomized_incremental_construction dbr:File:Contraction_vertices.jpg dbr:File:Single_run_of_Karger’s_Mincut_algorithm.svg |
| dbp:wikiPageUsesTemplate | dbt:Citation dbt:Cite_journal dbt:Main dbt:Math dbt:Mvar dbt:Reflist dbt:Short_description dbt:Tmath dbt:Isbn dbt:Math_proof dbt:Probabilistic dbt:Abs dbt:Mset dbt:Distinguish-redirect dbt:Math_theorem |
| dct:subject | dbc:Randomized_algorithms dbc:Analysis_of_algorithms |
| gold:hypernym | dbr:Algorithm |
| rdf:type | owl:Thing dbo:Software yago:WikicatStochasticAlgorithms yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Event100029378 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:YagoPermanentlyLocatedEntity yago:Rule105846932 yago:WikicatAlgorithms yago:WikicatRandomizedAlgorithms |
| rdfs:comment | Pravděpodobnostní (náhodnostní) algoritmy jsou nedeterministické algoritmy, které se snaží najít řešení rychleji nebo řešení těžko řešitelných problémů, často tzv. NP-úplných problémů. Pravděpodobnostní algoritmus se může náhodně rozhodovat mezi různými možnostmi jak pokračovat. Pro stejný vstup může dávat takový algoritmus různé výsledky, které mohou být dokonce nesprávné. Mnohdy se tedy na daném vstupu spustí pravděpodobnostní algoritmus vícekrát, aby se s větší pravděpodobností dospělo ke správnému výsledku. (cs) Hazardigita algoritmo aŭ probableca algoritmo estas algoritmo kiu uzas iun gradon de hazardon kiel parto de sia logiko. En komuna praktiko, ĉi tio signifas ke la maŝino realiganta la algoritmon havas atingon al . Por ĉi tiuj algoritmoj la estas tipe malverŝajna kaj tiel povas esti ignorita. (eo) 확률적 알고리즘(probabilistic algorithm) 또는 무작위 알고리즘(randomized algorithm)은 난수를 발생시켜 진행과정을 결정하는 알고리즘이다. 난수를 발생시키는 과정은 흔히 '동전을 던진다'고 표현하며, 실제로는 를 사용한다. 알고리즘의 성능을 평균적으로 향상시키기 위해 난수를 사용한다. 난수를 사용하기 때문에 알고리즘의 성능은 확률변수이며, 확률변수의 기댓값이 실제로 원하는 성능이다. 알고리즘 성능의 최악의 경우는 일어날 확률이 극히 작기 때문에 대부분 무시한다. (ko) 乱択アルゴリズム（らんたくアルゴリズム）、ランダム・アルゴリズム（英: randomized algorithm）または確率的アルゴリズム（かくりつてきアルゴリズム、（英: probabilistic algorithm）は、その論理の一部に無作為性を導入したアルゴリズムである。通常のアルゴリズムでは自然数を順番にあてはめるような決定的な部分で、乱数による非決定的な選択を入れることで、「平均的に」よい性能を実現することを目的とすることがある。形式的には、乱択アルゴリズムの性能はランダムビット列で決定される確率変数となる。その期待値を期待実行時間と呼ぶ。最悪の場合に関して「無視できる」ほどに低い確率であることが、一般に、この類のアルゴリズムが効果的である要件となる。 (ja) Algorytm probabilistyczny albo randomizowany to algorytm, który do swojego działania używa losowości. W praktyce oznacza to, że implementacja takiego algorytmu korzysta przy obliczeniach z generatora liczb losowych. Główną zaletą algorytmów probabilistycznych w porównaniu z deterministycznymi jest działanie zawsze w „średnim przypadku”, dzięki czemu „złośliwe" dane wejściowe nie wydłużają jego działania. Formalnie efektywność takiego algorytmu jest zmienną losową określoną na przestrzeni możliwych losowych ciągów. Wartość oczekiwana takiej zmiennej nazywana jest oczekiwanym czasem działania. Przypadek pesymistyczny jest zwykle na tyle mało prawdopodobny, że można go pominąć w analizie. (pl) Вероятностный алгоритм — алгоритм, предусматривающий обращение на определённых этапах своей работы к генератору случайных чисел с целью получения экономии во времени работы за счёт замены абсолютной достоверности результата достоверностью с некоторой вероятностью. (ru) Um algoritmo probabilístico é um algoritmo que utiliza a probabilidade como parte de sua lógica. Na prática, isso significa que a máquina que implementa o algoritmo deve acessar um gerador de números pseudo-aleatórios. O algoritmo utiliza bits aleatórios como um guia para o seu comportamento. Diferente dos algoritmos convencionais, um algoritmo probabilístico, dada uma mesma sequência de entrada, não necessariamente leva a um mesmo estado final. (pt) 随机化算法（randomized algorithm），是这样一种算法，在算法中使用了随机函数，且随机函数的返回值直接或者间接的影响了算法的执行流程或执行结果。就是将算法的某一步或某几步置于运气的控制之下，即该算法在运行的过程中的某一步或某几步涉及一个随机决策，或者说其中的一个决策依赖于某种随机事件。 (zh) الخوارزمية العشوائية هي خوارزمية توظف درجة عشوائية كجزء من منطقها. تستخدم الخوارزمية عادةً البتات العشوائية بشكل موحد كمدخل مساعد لتوجيه سلوكها، على أمل تحقيق أداء جيد في «الحالة المتوسطة» على جميع الخيارات الممكنة للبت العشوائي. بشكل رسمي، سيكون أداء الخوارزمية متغيرًا عشوائيًا تحدده البتات العشوائية؛ وبالتالي إما وقت التشغيل، أو الإخراج (أو كليهما) هي متغيرات عشوائية. (ar) Un algorisme probabilista (o probabilístic) és un algorisme que basa el seu resultat en la presa d'algunes decisions a l'atzar, de tal manera que, de mitjana, obté una bona solució al problema plantejat per a qualsevol distribució de les dades d'entrada. És a dir, al contrari que un algorisme determinista, a partir d'uns mateixes dades es poden obtenir diferents solucions i, en alguns casos, solucions errònies. Hi ha diversos tipus d'algorismes probabilístics depenent del seu funcionament, es poden distingir: (ca) Un algoritmo probabilista (o probabilístico) es un algoritmo que basa su resultado en la toma de algunas decisiones al azar, de tal forma que, en promedio, obtiene una buena solución al problema planteado para cualquier distribución de los datos de entrada. Es decir, al contrario que un algoritmo determinista, a partir de unos mismos datos se pueden obtener distintas soluciones y, en algunos casos, soluciones erróneas. Existen varios tipos de algoritmos probabilísticos dependiendo de su funcionamiento, pudiéndose distinguir: (es) Ein randomisierter Algorithmus (auch stochastischer oder probabilistischer Algorithmus) ist ein Algorithmus, der versucht, durch die Wahl von zufälligen Zwischenergebnissen zu einem (im Mittel) guten bzw. näherungsweise korrekten Ergebnis zu gelangen. Er bildet somit das Gegenstück zum deterministischen Algorithmus. Es wird dabei nicht verlangt, dass ein randomisierter Algorithmus immer effizient eine richtige Lösung findet. Randomisierte Algorithmen sind in vielen Fällen einfacher zu verstehen, einfacher zu implementieren und effizienter als deterministische Algorithmen für dasselbe Problem. Ein Beispiel, das dies zeigt, ist der AKS-Primzahltest, der zwar deterministisch ist, aber viel ineffizienter und viel schwieriger zu implementieren als beispielsweise der Primzahltest von Solovay und (de) A randomized algorithm is an algorithm that employs a degree of randomness as part of its logic or procedure. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performance in the "average case" over all possible choices of random determined by the random bits; thus either the running time, or the output (or both) are random variables. (en) En algorithmique, un algorithme probabiliste, ou algorithme randomisé, est un algorithme qui utilise une source de hasard. Plus précisément le déroulement de l’algorithme fait appel à des données tirées au hasard. Par exemple à un certain point de l’exécution, on tire un bit 0 ou 1, selon la loi uniforme et si le résultat est 0, on fait une certaine action A et si c'est 1, on fait une autre action. On peut aussi tirer un nombre réel dans l'intervalle [0,1] ou un entier dans un intervalle [i..j]. (fr) Un algoritmo randomizzato è un algoritmo che include un certo grado di casualità nella sua logica. Tipicamente l'algoritmo utilizza variabili aleatorie come input ausiliario per guidare il suo comportamento con l'obiettivo di ottenere, in media, buone prestazioni. Le prestazioni dell'algoritmo, inclusi il tempo di esecuzione o l'output, saranno a loro volta casuali. Un tipico esempio di algoritmo randomizzato è il quicksort . In alcuni casi, gli algoritmi probabilistici sono l'unico mezzo pratico per risolvere un problema . (it) Увипадковлений алгоритм (англ. randomized algorithm) — це алгоритм, який використовує елемент випадковості як частину своєї логіки. Алгоритм зазвичай використовує рівномірно випадкові біти як допоміжний вхід для спрямування своєї поведінки в надії досягнення хорошої швидкодії в середньому серед усіх можливих виборів випадкових бітів. Формально, швидкодією алгоритму буде випадкова величина визначена випадковими бітами; отже або швидкодія, або вихід (або і те, і те) є випадковими величинами. (uk) |
| rdfs:label | خوارزمية عشوائية (ar) Algorisme probabilístic (ca) Pravděpodobnostní algoritmus (cs) Randomisierter Algorithmus (de) Hazardigita algoritmo (eo) Algoritmo probabilista (es) Algorithme probabiliste (fr) Algoritmo randomizzato (it) 乱択アルゴリズム (ja) 확률적 알고리즘 (ko) Randomized algorithm (en) Algoritmo probabilístico (pt) Algorytm probabilistyczny (pl) Вероятностный алгоритм (ru) 随机化算法 (zh) Увипадковлений алгоритм (uk) |
| owl:differentFrom | dbr:Algorithmic_randomness |
| owl:sameAs | freebase:Randomized algorithm yago-res:Randomized algorithm wikidata:Randomized algorithm dbpedia-ar:Randomized algorithm http://bn.dbpedia.org/resource/সম্ভাবনাভিত্তিক_অ্যালগোরিদম dbpedia-ca:Randomized algorithm dbpedia-cs:Randomized algorithm dbpedia-de:Randomized algorithm dbpedia-eo:Randomized algorithm dbpedia-es:Randomized algorithm dbpedia-fa:Randomized algorithm dbpedia-fr:Randomized algorithm dbpedia-he:Randomized algorithm dbpedia-it:Randomized algorithm dbpedia-ja:Randomized algorithm dbpedia-ko:Randomized algorithm dbpedia-pl:Randomized algorithm dbpedia-pt:Randomized algorithm dbpedia-ru:Randomized algorithm dbpedia-sr:Randomized algorithm dbpedia-th:Randomized algorithm dbpedia-uk:Randomized algorithm dbpedia-zh:Randomized algorithm https://global.dbpedia.org/id/4mPpa |
| prov:wasDerivedFrom | wikipedia-en:Randomized_algorithm?oldid=1083506589&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Contraction_vertices.jpg wiki-commons:Special:FilePath/Single_run_of_Karger’s_Mincut_algorithm.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Randomized_algorithm |
| is dbo:wikiPageRedirects of | dbr:Probabalistic_algorithm dbr:Probabilistic_complexity_theory dbr:Derandomization dbr:Probabilistic_complexity dbr:Probabilistic_computational_complexity dbr:Derandomisation dbr:Randomised_algorithm dbr:Randomized_algorithms dbr:Computational_complexity_of_randomized_algorithms dbr:Random_algorithm dbr:Random_computation dbr:Randomized_complexity dbr:Randomized_computation dbr:Probabilistic-Complexity_Theory dbr:Probabilistic_algorithm dbr:Probabilistic_algorithms |
| is dbo:wikiPageWikiLink of | dbr:Probabalistic_algorithm dbr:Probabilistic_Turing_machine dbr:Santosh_Vempala dbr:Element_distinctness_problem dbr:Elementary_Number_Theory,_Group_Theory_and_Ramanujan_Graphs dbr:List_of_algorithm_general_topics dbr:List_of_complexity_classes dbr:List_of_computability_and_complexity_topics dbr:List_of_computer_scientists dbr:Monte_Carlo_algorithm dbr:Morris_worm dbr:Method_of_successive_substitution dbr:Stochastic_computing dbr:Principle_of_deferred_decision dbr:Probabilistic_complexity_theory dbr:Primality_test dbr:Bayesian_network dbr:Bogosort dbr:David_Karger dbr:Algorithm dbr:Algorithmic_Geometry dbr:Algorithmic_paradigm dbr:Anna_Karlin dbr:Approximate_computing dbr:Approximate_counting_algorithm dbr:Perfect_hash_function dbr:Derandomization dbr:Deterministic_algorithm dbr:Deutsch–Jozsa_algorithm dbr:Domination_analysis dbr:Integer_factorization dbr:Interpolation_attack dbr:Predicate_transformer_semantics dbr:Pseudorandom_generator dbr:♯P dbr:Computing_the_permanent dbr:Count–min_sketch dbr:Matching_(graph_theory) dbr:Matroid_parity_problem dbr:Maximum_cardinality_matching dbr:Maximum_cut dbr:McEliece_cryptosystem dbr:Generalized_minimum-distance_decoding dbr:One-way_function dbr:Probable_prime dbr:Science_and_technology_in_Spain dbr:Freivalds'_algorithm dbr:Game_theory dbr:Greatest_common_divisor dbr:Bounding_sphere dbr:Bramble_(graph_theory) dbr:Consensus_(computer_science) dbr:Cross-entropy_method dbr:Dana_Ron dbr:Sauer–Shelah_lemma dbr:Work_stealing dbr:Miklós_Simonovits dbr:Probabilistic_complexity dbr:Probabilistic_computational_complexity dbr:Anna_C._Gilbert dbr:Berlekamp–Rabin_algorithm dbr:Leonid_Khachiyan dbr:Ski_rental_problem dbr:Competitive_analysis_(online_algorithm) dbr:Complexity_class dbr:Computational_complexity_theory dbr:Computational_geometry dbr:Embedded_software dbr:Emo_Welzl dbr:Derandomisation dbr:PCP_theorem dbr:Partition_problem dbr:Permanent_(mathematics) dbr:Planar_separator_theorem dbr:Probabilistically_checkable_proof dbr:Markov_Chains_and_Mixing_Times dbr:Maximum_satisfiability_problem dbr:BPP_(complexity) dbr:Agreeable_subset dbr:Time_complexity dbr:Data_compression dbr:Game_tree dbr:Hash_function dbr:Head-of-line_blocking dbr:K-edge-connected_graph dbr:Karger's_algorithm dbr:Karloff–Zwick_algorithm dbr:Las_Vegas_algorithm dbr:Linear_programming_relaxation dbr:Local_differential_privacy dbr:Probabilistic_encryption dbr:Schreier–Sims_algorithm dbr:Roomba dbr:AFL_Premiership_2007 dbr:Euclidean_minimum_spanning_tree dbr:Factorization_of_polynomials_over_finite_fields dbr:Fermat_primality_test dbr:Angelika_Steger dbr:Balls_into_bins_problem dbr:Centerpoint_(geometry) dbr:Differential_privacy dbr:Differentially_private_analysis_of_graphs dbr:Edmonds–Pruhs_protocol dbr:Farthest-first_traversal dbr:Isolation_lemma dbr:Kenneth_L._Clarkson dbr:Kinetic_triangulation dbr:Asymptotic_computational_complexity dbr:Atlantic_City_algorithm dbr:Baillie–PSW_primality_test dbr:Counting_points_on_elliptic_curves dbr:Jeffrey_Vitter dbr:Solovay–Strassen_primality_test dbr:Aanderaa–Karp–Rosenberg_conjecture dbr:Chernoff_bound dbr:Alan_M._Frieze dbr:LP-type_problem dbr:Lagrange's_four-square_theorem dbr:Blow-up_lemma dbr:Theil–Sen_estimator dbr:Directed_acyclic_graph dbr:Average-case_complexity dbr:Averaging_argument dbr:Azuma's_inequality dbr:Boolean_satisfiability_algorithm_heuristics dbr:Polynomial-time_approximation_scheme dbr:Sorting_algorithm dbr:Fermat_pseudoprime dbr:Fine-grained_reduction dbr:Greedy_randomized_adaptive_search_procedure dbr:In-place_algorithm dbr:Indeterminacy_in_concurrent_computation dbr:Miller–Rabin_primality_test dbr:Omer_Reingold dbr:Capacitated_minimum_spanning_tree dbr:RP_(complexity) dbr:Randomised_algorithm dbr:Randomized_algorithms dbr:Ravindran_Kannan dbr:System_on_a_chip dbr:With_high_probability dbr:Indeterminacy_in_computation dbr:Uwe_Schöning dbr:Expected_linear_time_MST_algorithm dbr:Exponential_backoff dbr:Computational_complexity_of_randomized_algorithms dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:List_of_unsolved_problems_in_computer_science dbr:Lovász_local_lemma dbr:Low_(complexity) dbr:Reservoir_sampling dbr:Random_permutation dbr:Point_location dbr:Gibbs_sampling dbr:Universal_hashing dbr:NP-completeness dbr:Randomization dbr:Self-balancing_binary_search_tree dbr:Set_balancing dbr:Nondeterministic_algorithm dbr:Randomized_algorithms_as_zero-sum_games dbr:Raimund_Seidel dbr:Stochastic_optimization dbr:Word_RAM dbr:Outline_of_computer_programming dbr:P_versus_NP_problem dbr:Pseudorandom_permutation dbr:Property_testing dbr:Radon's_theorem dbr:Random_number_generation dbr:Rapidly-exploring_random_tree dbr:Yao's_principle dbr:Skip_list dbr:Smallest-circle_problem dbr:Random_algorithm dbr:Random_computation dbr:Randomized_complexity dbr:Randomized_computation dbr:Probabilistic-Complexity_Theory dbr:Probabilistic_algorithm dbr:Probabilistic_algorithms |
| is foaf:primaryTopic of | wikipedia-en:Randomized_algorithm |
