| dbo:abstract
|
- L' algorisme de Las Vegas és un algorisme de computació de caràcter aleatori que no és aproximat: és a dir, o dona el resultat correcte, o informa que ha fallat. (ca)
- Algoritmus typu Las Vegas je v teoretické informatice označení pro takový pravděpodobnostní algoritmus, který vždy na konci vrátí správný výsledek, ovšem s malou pravděpodobností může běžet velmi dlouho a nebo i vyžadovat rozsáhlé zdroje, než skončí. Tím se liší od obecných algoritmů typu Monte Carlo, které mohou s malou pravděpodobností vrátit špatný výsledek. Na obecný algoritmus typu Monte Carlo lze obvykle algoritmus typu Las Vegas převést omezením zdrojů (např. času), po jejichž vyčerpání vrátí algoritmus náhodný výsledek. Koncept algoritům typu Las Vegas pojmenoval v roce 1979 maďarský matematik při zkoumání grafových izomorfismů. (cs)
- Ein Las-Vegas-Algorithmus ist ein randomisierter Algorithmus, der immer ein korrektes Ergebnis liefert, wenn er terminiert. Der Begriff wurde 1979 von László Babai im Zusammenhang mit Graphenisomorphie als eine Variante von Monte-Carlo-Algorithmen eingeführt. Es gibt zwei Definitionen für Las-Vegas-Algorithmen und ihre Zeitkomplexität:
* Wenn die Zufallsbits nur Einfluss auf die Vorgehensweise des Algorithmus haben, liefert der Las-Vegas-Algorithmus immer ein korrektes Ergebnis, wenn er terminiert.Die Zeitkomplexität ist in diesem Fall abhängig von einer Zufallsvariable. Ein bekanntes Beispiel ist der Random-Quicksort-Algorithmus, der sein Pivotelement zufällig wählt, dessen Ausgabe aber immer sortiert ist.
* Wenn das Ergebnis der Berechnung eines Algorithmus mit einer Wahrscheinlichkeit korrekt ist und der Algorithmus zugleich mit einer Wahrscheinlichkeit kein Ergebnis liefert, dann ist es ein Las-Vegas-Algorithmus. (de)
- Un algoritmo tipo Las Vegas es un algoritmo de computación de carácter aleatorio (random) que no es aproximado: es decir, da el resultado correcto o informa que ha fallado. (es)
- In computing, a Las Vegas algorithm is a randomized algorithm that always gives correct results; that is, it always produces the correct result or it informs about the failure. However, the runtime of a Las Vegas algorithm differs depending on the input. The usual definition of a Las Vegas algorithm includes the restriction that the expected runtime be finite, where the expectation is carried out over the space of random information, or entropy, used in the algorithm. An alternative definition requires that a Las Vegas algorithm always terminates (is effective), but may output a symbol not part of the solution space to indicate failure in finding a solution. The nature of Las Vegas algorithms makes them suitable in situations where the number of possible solutions is limited, and where verifying the correctness of a candidate solution is relatively easy while finding a solution is complex. Las Vegas algorithms are prominent in the field of artificial intelligence, and in other areas of computer science and operations research. In AI, stochastic local search (SLS) algorithms are considered to be of Las Vegas type. SLS algorithms have been used to address NP-complete decision problems and NP-hard combinatorial optimization problems. However, some systematic search methods, such as modern variants of the Davis–Putnam algorithm for propositional satisfiability (SAT), also utilize non-deterministic decisions, and can thus also be considered Las Vegas algorithms. (en)
- En informatique, un algorithme de Las Vegas est un type d'algorithme probabiliste qui donne toujours un résultat correct ; son caractère aléatoire lui donne de meilleures performances temporelles en moyenne. Comme le suggère David Harel dans son livre d'algorithmique, ainsi que Motvani et Raghavan, le tri rapide randomisé est un exemple paradigmatique d'algorithme de Las Vegas. Quand le problème que l'algorithme résout possède plusieurs solutions, sur une même donnée, comme c'est le cas pour le tri d'un tableau qui contient des clés équivalentes, l'algorithme de Las Vegas peut retourner l'une ou l'autre de ces solutions, et il le fait de façon non prévisible. (fr)
- ラスベガス法（ラスベガスほう、英: Las Vegas algorithm）は、間違った解を返さない乱択アルゴリズムを指す。すなわち、解を返すときは常に正しく、正しい解が求められない場合は失敗を通知する。換言すれば、ラスベガス法は答え（解）については賭けをせず、計算に使用するリソース量についてのみ賭けをする。さらに平均実行時間が入力長の多項式関数で押さられるようなラスベガス法は効率的(efficient)であるという。ラスベガス法の単純な例にランダム化されたクイックソートがある。ピボット値をランダムに選択するクイックソートではソート結果は常に正しい。一般に無作為な情報に対してラスベガス法を使う際には、定義上、実行時間の上限を設けることが多い。 (ja)
- Em computação, um algoritmo de Las Vegas é um algoritmo aleatório que devolve sempre resultados corretos; isto é, ele produz sempre o resultado correto ou informa sobre a falha. Em outras palavras, um algoritmo de Las Vegas não aposta com a corretude do resultado; ele aposta somente com os recursos usados para a computação. Um exemplo simples é o algoritmo aleatório quicksort, onde o pivô é escolhido aleatoriamente, mas o resultado é sempre ordenado. A usual definição de um algoritmo de Las Vegas inclui a restrição de que o tempo de execução esperado tem sempre que ser finito, quando a estimativa é calculada em um espaço de informações aleatórias, ou entropia, utilizados no algoritmo. Uma definição alternativa requer que um algoritmo de Las Vegas pare sempre que seja eficaz, mas ele pode dar como saída um símbolo que não faz parte do espaço de solução para indicar a falha em encontrar uma solução. Os algoritmos de Las Vegas foram introduzidos por László Babai , em 1979, sob o contexto do problema do isomorfismo de grafos, como um dual dos Algoritmos de Monte Carlo. Os algoritmos de Las Vegas podem ser utilizados em situações onde o número de soluções possíveis é relativamente limitada, e onde verificar a corretude de uma solução candidata é relativamente fácil, enquanto realmente calcular uma solução é complexo. O nome refere-se à cidade de Las Vegas, Nevada, que é bem conhecida nos Estados Unidos como um ícone dos jogos de azar. (pt)
- Em computação, um algoritmo Las Vegas é um algoritmo randômico que sempre retorna resultados corretos; isto é, ele sempre produz o resultado correto ou informa sobre a falha. Em outras palavras, um algoritmo de Las Vegas não aposta com a corretude do resultado; ele aposta somente com os recursos usados para a computação. Um exemplo simples é o algoritmo randômico quicksort, onde o pivô é escolhido aleatoriamente, mas o resultado é sempre ordenado. A usual definição de um algoritmo Las Vegas inclui a restrição de que o tempo de execução esperado tem sempre que ser finito, quando a estimativa é calculada em um espaço de informações aleatórias, ou entropia, utilizados no algoritmo. Uma definição alternativa requer que um algoritmo Las Vegas sempre pare(que seja eficaz), mas ele pode dar como saída um símbolo que não faz parte do espaço de solução para indicar a falha em encontrar uma solução. Os algoritmos Las Vegas foram introduzidos por László Babai, em 1979, sob o contexto do problema do isomorfismo de grafos, como um dual dos . Os algoritmos Las Vegas podem ser utilizados em situações onde o número de soluções possíveis é relativamente limitada, e onde verificar a corretude de uma solução candidata é relativamente fácil, enquanto realmente calcular uma solução é complexo. O nome refere-se à cidade de Las Vegas, Nevada, que é bem conhecida nos Estados Unidos como um ícone dos jogos de azar. (pt)
- Лас-Вегас — вид вероятностного алгоритма (см. также Алгоритмы Монте-Карло). Идея алгоритма Лас-Вегаса состоит в следующем. Если у нас есть некий вероятностный алгоритм , который с определенной вероятностью дает верный результат, и существует возможность алгоритмически проверить результат алгоритма на корректность (скажем, с помощью алгоритма ), то можно выполнять алгоритм до тех пор, пока проверка не установит, что результат верен. Выполнить алгоритм с результатом до тех пор, пока не будет истиной. Название этому принципу было дано с одной стороны как намек на метод Монте-Карло. С другой стороны это название намекает на «метод выигрыша в казино», которое схоже с процессом работы алгоритма — «если я буду играть ещё и ещё, я когда-нибудь обязательно выиграю». Следует заметить, что алгоритм Лас-Вегаса гарантирует получение правильного результата. Алгоритм работает за конечное, но не детерминированное время. Можно указать только вероятность получения результата за заданное время. Примером алгоритма, относящегося к классу Лас-Вегас, является алгоритм сортировки Bogosort: данные, которые нужно отсортировать, перемешиваются случайным образом, и затем проверяется, оказались ли они расположенными в нужном порядке. В случае неудачи перемешивание многократно повторяется вплоть до достижения желаемого порядка. (ru)
- Лас-Вегас — увипадковлений алгоритм, що завжди повертає правильний результат; тобто, він завжди видає правильний результат або повідомляє про збій. Інакше кажучи, Лас-Вегас не грається із правильністю результату, а лише з ресурсами використовними для обчислень. Єдиною відмінністю між запусками на одних вхідних даних є час виконання, який може бути необмеженим, але очікуваний час виконання завжди обмежений. Простим прикладом є увипадковлене швидке сортування, де опірний елемент вибирають випадковим чином, але результат завжди правильний. Алгоритм Лас-Вегаса представив Ласло Бабай у 1979, у контексті проблеми визначення чи два графи ізоморфні, як сильнішу версію алгоритму Монте-Карло. Алгоритм Лас-Вегаса можна використати в ситуаціях коли число можливих розв'язків порівняно обмежене і перевірка правильності кандидата в розв'язки порівняно проста тоді коли обчислення розв'язку складне. Ім'я покликається до міста Лас-Вегас у штаті Невада, яке добре відоме своїм ігорним бізнесом. (uk)
- 在电脑运算中，拉斯维加斯算法是一种永远给出正确解的随机化算法；也就是说，它总是给出正确结果，或是返回失败。 换言之，拉斯维加斯算法不赌结果的正确性，而是赌运算所用资源。一个简单的例子是随机快速排序，他的中心点虽然是随机选择的，但排序结果永远一致。 (zh)
|
| rdfs:comment
|
- L' algorisme de Las Vegas és un algorisme de computació de caràcter aleatori que no és aproximat: és a dir, o dona el resultat correcte, o informa que ha fallat. (ca)
- Un algoritmo tipo Las Vegas es un algoritmo de computación de carácter aleatorio (random) que no es aproximado: es decir, da el resultado correcto o informa que ha fallado. (es)
- ラスベガス法（ラスベガスほう、英: Las Vegas algorithm）は、間違った解を返さない乱択アルゴリズムを指す。すなわち、解を返すときは常に正しく、正しい解が求められない場合は失敗を通知する。換言すれば、ラスベガス法は答え（解）については賭けをせず、計算に使用するリソース量についてのみ賭けをする。さらに平均実行時間が入力長の多項式関数で押さられるようなラスベガス法は効率的(efficient)であるという。ラスベガス法の単純な例にランダム化されたクイックソートがある。ピボット値をランダムに選択するクイックソートではソート結果は常に正しい。一般に無作為な情報に対してラスベガス法を使う際には、定義上、実行時間の上限を設けることが多い。 (ja)
- 在电脑运算中，拉斯维加斯算法是一种永远给出正确解的随机化算法；也就是说，它总是给出正确结果，或是返回失败。 换言之，拉斯维加斯算法不赌结果的正确性，而是赌运算所用资源。一个简单的例子是随机快速排序，他的中心点虽然是随机选择的，但排序结果永远一致。 (zh)
- Algoritmus typu Las Vegas je v teoretické informatice označení pro takový pravděpodobnostní algoritmus, který vždy na konci vrátí správný výsledek, ovšem s malou pravděpodobností může běžet velmi dlouho a nebo i vyžadovat rozsáhlé zdroje, než skončí. Tím se liší od obecných algoritmů typu Monte Carlo, které mohou s malou pravděpodobností vrátit špatný výsledek. Na obecný algoritmus typu Monte Carlo lze obvykle algoritmus typu Las Vegas převést omezením zdrojů (např. času), po jejichž vyčerpání vrátí algoritmus náhodný výsledek. (cs)
- Ein Las-Vegas-Algorithmus ist ein randomisierter Algorithmus, der immer ein korrektes Ergebnis liefert, wenn er terminiert. Der Begriff wurde 1979 von László Babai im Zusammenhang mit Graphenisomorphie als eine Variante von Monte-Carlo-Algorithmen eingeführt. Es gibt zwei Definitionen für Las-Vegas-Algorithmen und ihre Zeitkomplexität: (de)
- In computing, a Las Vegas algorithm is a randomized algorithm that always gives correct results; that is, it always produces the correct result or it informs about the failure. However, the runtime of a Las Vegas algorithm differs depending on the input. The usual definition of a Las Vegas algorithm includes the restriction that the expected runtime be finite, where the expectation is carried out over the space of random information, or entropy, used in the algorithm. An alternative definition requires that a Las Vegas algorithm always terminates (is effective), but may output a symbol not part of the solution space to indicate failure in finding a solution. The nature of Las Vegas algorithms makes them suitable in situations where the number of possible solutions is limited, and where ver (en)
- En informatique, un algorithme de Las Vegas est un type d'algorithme probabiliste qui donne toujours un résultat correct ; son caractère aléatoire lui donne de meilleures performances temporelles en moyenne. Comme le suggère David Harel dans son livre d'algorithmique, ainsi que Motvani et Raghavan, le tri rapide randomisé est un exemple paradigmatique d'algorithme de Las Vegas. (fr)
- Em computação, um algoritmo Las Vegas é um algoritmo randômico que sempre retorna resultados corretos; isto é, ele sempre produz o resultado correto ou informa sobre a falha. Em outras palavras, um algoritmo de Las Vegas não aposta com a corretude do resultado; ele aposta somente com os recursos usados para a computação. Um exemplo simples é o algoritmo randômico quicksort, onde o pivô é escolhido aleatoriamente, mas o resultado é sempre ordenado. A usual definição de um algoritmo Las Vegas inclui a restrição de que o tempo de execução esperado tem sempre que ser finito, quando a estimativa é calculada em um espaço de informações aleatórias, ou entropia, utilizados no algoritmo. Uma definição alternativa requer que um algoritmo Las Vegas sempre pare(que seja eficaz), mas ele pode dar como (pt)
- Em computação, um algoritmo de Las Vegas é um algoritmo aleatório que devolve sempre resultados corretos; isto é, ele produz sempre o resultado correto ou informa sobre a falha. Em outras palavras, um algoritmo de Las Vegas não aposta com a corretude do resultado; ele aposta somente com os recursos usados para a computação. Um exemplo simples é o algoritmo aleatório quicksort, onde o pivô é escolhido aleatoriamente, mas o resultado é sempre ordenado. A usual definição de um algoritmo de Las Vegas inclui a restrição de que o tempo de execução esperado tem sempre que ser finito, quando a estimativa é calculada em um espaço de informações aleatórias, ou entropia, utilizados no algoritmo. Uma definição alternativa requer que um algoritmo de Las Vegas pare sempre que seja eficaz, mas ele pode d (pt)
- Лас-Вегас — вид вероятностного алгоритма (см. также Алгоритмы Монте-Карло). Идея алгоритма Лас-Вегаса состоит в следующем. Если у нас есть некий вероятностный алгоритм , который с определенной вероятностью дает верный результат, и существует возможность алгоритмически проверить результат алгоритма на корректность (скажем, с помощью алгоритма ), то можно выполнять алгоритм до тех пор, пока проверка не установит, что результат верен. Выполнить алгоритм с результатом до тех пор, пока не будет истиной. (ru)
- Лас-Вегас — увипадковлений алгоритм, що завжди повертає правильний результат; тобто, він завжди видає правильний результат або повідомляє про збій. Інакше кажучи, Лас-Вегас не грається із правильністю результату, а лише з ресурсами використовними для обчислень. Єдиною відмінністю між запусками на одних вхідних даних є час виконання, який може бути необмеженим, але очікуваний час виконання завжди обмежений. Простим прикладом є увипадковлене швидке сортування, де опірний елемент вибирають випадковим чином, але результат завжди правильний. (uk)
|
