Pravděpodobnostní algoritmus: Porovnání verzí
Smazaný obsah Přidaný obsah
m r2.7.1) (Robot: Přidávám fa:الگوریتمهای تصادفی |
m Bot: Odstranění 16 odkazů interwiki, které jsou nyní dostupné na Wikidatech (d:q583461) |
||
| Řádek 16: | Řádek 16: | ||
[[Kategorie:Algoritmy]] |
[[Kategorie:Algoritmy]] |
||
[[bn:সম্ভাবনাভিত্তিক অ্যালগোরিদম]] |
|||
[[ca:Algorisme probabilístic]] |
|||
[[de:Randomisierter Algorithmus]] |
|||
[[en:Randomized algorithm]] |
|||
[[eo:Hazardigita algoritmo]] |
|||
[[es:Algoritmo probabilista]] |
|||
[[fa:الگوریتمهای تصادفی]] |
|||
[[fr:Algorithme probabiliste]] |
|||
[[he:אלגוריתם אקראי]] |
|||
[[ja:乱択アルゴリズム]] |
|||
[[ko:확률적 알고리즘]] |
|||
[[pl:Algorytm probabilistyczny]] |
|||
[[pt:Algoritmo probabilístico]] |
|||
[[th:ขั้นตอนวิธีแบบสุ่ม]] |
|||
[[uk:Увипадковлений алгоритм]] |
|||
[[zh:随机化算法]] |
|||
Verze z 8. 3. 2013, 18:57
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.
Varianty pravděpodobnostních algoritmů
- Výpočetní strom je binární, v každém uzlu se provede hod mincí.
- V každém výpočetním uzlu je definováno pravděpodobnostní rozložení na hranách.
- Na začátku se vybere náhodně deterministický algoritmus, který provede výpočet.
Všechny tři varianty jsou ekvivalentní.
Poznámky
Pravděpodobnostní algoritmy jsou většinou jednoduché, avšak analýza jejich časové složitosti je často náročná.
