About: Randomized algorithm     Goto   Sponge   NotDistinct   Permalink

An Entity of Type : yago:Event100029378, within Data Space : dbpedia.org associated with source document(s)
QRcode icon
http://dbpedia.org/describe/?url=http%3A%2F%2Fdbpedia.org%2Fresource%2FRandomized_algorithm

A randomized algorithm is an algorithm that employs a degree of randomness as part of its logic. 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 bits. Formally, the algorithm's performance will be a random variable determined by the random bits; thus either the running time, or the output (or both) are random variables.

AttributesValues
rdf:type
rdfs:label
  • خوارزمية عشوائية
  • Algorisme probabilístic
  • Pravděpodobnostní algoritmus
  • Randomisierter Algorithmus
  • Hazardigita algoritmo
  • Algoritmo probabilista
  • Randomized algorithm
  • Algorithme probabiliste
  • 乱択アルゴリズム
  • 확률적 알고리즘
  • Algoritmo probabilístico
  • Вероятностный алгоритм
  • Увипадковлений алгоритм
  • 随机化算法
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.
  • 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.
  • 乱択アルゴリズム(らんたくアルゴリズム、英: Randomized algorithm、ランダム・アルゴリズム)または確率的アルゴリズム(かくりつてき-、英: Probabilistic algorithm)は、その論理の一部に無作為性を導入したアルゴリズムである。通常のアルゴリズムでは自然数を順番にあてはめるような決定的な部分で、乱数による非決定的な選択を入れることで、「平均的に」よい性能を実現することを目的としている。形式的には、乱択アルゴリズムの性能はランダムビット列で決定される確率変数となる。その期待値を「期待実行時間; expected runtime」と呼ぶ。最悪の場合に関して「無視できる」ほどに低い確率であることが、一般に、この類のアルゴリズムが効果的である要件となる。
  • 확률적 알고리즘(probabilistic algorithm) 또는 무작위 알고리즘(randomized algorithm)은 난수를 발생시켜 진행과정을 결정하는 알고리즘이다. 난수를 발생시키는 과정은 흔히 '동전을 던진다'고 표현하며, 실제로는 를 사용한다. 알고리즘의 성능을 평균적으로 향상시키기 위해 난수를 사용한다. 난수를 사용하기 때문에 알고리즘의 성능은 확률변수이며, 확률변수의 기댓값이 실제로 원하는 성능이다. 알고리즘 성능의 최악의 경우는 일어날 확률이 극히 작기 때문에 대부분 무시한다.
  • 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.
  • Вероятностный алгоритм — алгоритм, предусматривающий обращение на определённых этапах своей работы к генератору случайных чисел с целью получения экономии во времени работы за счёт замены абсолютной достоверности результата достоверностью с некоторой вероятностью.
  • 随机化算法(randomized algorithm),是这样一种算法,在算法中使用了随机函数,且随机函数的返回值直接或者间接的影响了算法的执行流程或执行结果。就是将算法的某一步或某几步置于运气的控制之下,即该算法在运行的过程中的某一步或某几步涉及一个随机决策,或者说其中的一个决策依赖于某种随机事件。
  • الخوارزمية العشوائية هي خوارزمية توظف درجة عشوائية كجزء من منطقها. تستخدم الخوارزمية عادةً البتات العشوائية بشكل موحد كمدخل مساعد لتوجيه سلوكها ، على أمل تحقيق أداء جيد في "الحالة المتوسطة" على جميع الخيارات الممكنة للبت العشوائي. بشكل رسمي ، سيكون أداء الخوارزمية متغيرًا عشوائيًا تحدده البتات العشوائية ؛ وبالتالي إما وقت التشغيل ، أو الإخراج (أو كليهما) هي متغيرات عشوائية.
  • 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:
  • 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
  • A randomized algorithm is an algorithm that employs a degree of randomness as part of its logic. 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 bits. Formally, the algorithm's performance will be a random variable determined by the random bits; thus either the running time, or the output (or both) are random variables.
  • 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].
  • 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:
  • Увипадковлений алгоритм (англ. randomized algorithm) — це алгоритм, який використовує елемент випадковості як частину своєї логіки. Алгоритм зазвичай використовує рівномірно випадкові біти як допоміжний вхід для спрямування своєї поведінки в надії досягнення хорошої швидкодії в середньому серед усіх можливих виборів випадкових бітів. Формально, швидкодією алгоритму буде випадкова величина визначена випадковими бітами; отже або швидкодія, або вихід (або і те, і те) є випадковими величинами.
differentFrom
foaf:isPrimaryTopicOf
dct:subject
Wikipage page ID
Wikipage revision ID
Link from a Wikipage to another Wikipage
Faceted Search & Find service v1.17_git51 as of Sep 16 2020


Alternative Linked Data Documents: PivotViewer | iSPARQL | ODE     Content Formats:       RDF       ODATA       Microdata      About   
This material is Open Knowledge   W3C Semantic Web Technology [RDF Data] Valid XHTML + RDFa
OpenLink Virtuoso version 08.03.3321 as of Jun 2 2021, on Linux (x86_64-generic-linux-glibc25), Single-Server Edition (61 GB total memory)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2021 OpenLink Software