u, 08 Jan 2009 06:16:52 GMT Server: Apache X-Powered-By: PHP/5.2.4-2ubuntu5wm1 Cache-Control: private, s-maxage=0, max-age=0, must-revalidate Content-Language: cs Vary: Accept-Encoding,Cookie X-Vary-Options: Accept-Encoding;list-contains=gzip,Cookie;string-contains=cswikiToken;string-contains=cswikiLoggedOut;string-contains=cswiki_session;string-contains=centralauth_Token;string-contains=centralauth_Session;string-contains=centralauth_LoggedOut Last-Modified: Tue, 02 Dec 2008 13:57:32 GMT Content-Length: 19011 Content-Type: text/html; charset=utf-8 X-Cache: MISS from sq33.wikimedia.org X-Cache-Lookup: MISS from sq33.wikimedia.org:3128 X-Cache: MISS from knsq24.knams.wikimedia.org X-Cache-Lookup: MISS from knsq24.knams.wikimedia.org:3128 X-Cache: MISS from knsq30.knams.wikimedia.org X-Cache-Lookup: MISS from knsq30.knams.wikimedia.org:80 Via: 1.0 sq33.wikimedia.org:3128 (squid/2.6.STABLE21), 1.0 knsq24.knams.wikimedia.org:3128 (squid/2.6.STABLE21), 1.0 knsq30.knams.wikimedia.org:80 (squid/2.6.STABLE21) Connection: close

Pravděpodobnostní algoritmy

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.

[editovat] 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í.

[editovat] Poznámky

Pravděpodobnostní algoritmy jsou většinou jednoduché, avšak analýza jejich časové složitosti je často náročná.

Tento článek o algoritmu nebo datové struktuře je příliš stručný nebo neobsahuje důležité informace. Pomozte Wikipedii tím, že jej vhodně rozšíříte.

Kategorie: Algoritmy

 

u, 08 Jan 2009 06:16:52 GMT Server: Apache X-Powered-By: PHP/5.2.4-2ubuntu5wm1 Cache-Control: private, s-maxage=0, max-age=0, must-revalidate Content-Language: cs Vary: Accept-Encoding,Cookie X-Vary-Options: Accept-Encoding;list-contains=gzip,Cookie;string-contains=cswikiToken;string-contains=cswikiLoggedOut;string-contains=cswiki_session;string-contains=centralauth_Token;string-contains=centralauth_Session;string-contains=centralauth_LoggedOut Last-Modified: Tue, 02 Dec 2008 13:57:32 GMT Content-Length: 19011 Content-Type: text/html; charset=utf-8 X-Cache: MISS from sq33.wikimedia.org X-Cache-Lookup: MISS from sq33.wikimedia.org:3128 X-Cache: MISS from knsq24.knams.wikimedia.org X-Cache-Lookup: MISS from knsq24.knams.wikimedia.org:3128 X-Cache: MISS from knsq30.knams.wikimedia.org X-Cache-Lookup: MISS from knsq30.knams.wikimedia.org:80 Via: 1.0 sq33.wikimedia.org:3128 (squid/2.6.STABLE21), 1.0 knsq24.knams.wikimedia.org:3128 (squid/2.6.STABLE21), 1.0 knsq30.knams.wikimedia.org:80 (squid/2.6.STABLE21) Connection: close

Pravděpodobnostní algoritmy v jiných jazycích: বাংলা, Deutsch, English, Esperanto, Español, Français, עברית, 日本語, 한국어, Polski, Português, ไทย, 中文

Tento článek je převzat z české wikipedie - otevřené encyklopedie, originální článek naleznete na adrese: „http://cs.wikipedia.org/wiki/Pravd%C4%9Bpodobnostn%C3%AD_algoritmy“
Stránka byla naposledy upravena v Stránka byla naposledy editována 9. 7. 2008 v 14:50.
Veškerý text je dostupný za podmínek GNU Free Documentation License (Autorské právo pro podrobnosti).

Další služby: Portál | Katalog | Hledej | Zprávy | Počasí | Kurzy | Práce | Slovník | TV | Online hry | Java hry | SMS | Loga a melodie | Chat | Fórum | Kontakt | Set-top-boxy