===== Zadání =====
4. Metody tvorby náhodnostních algoritmů a jejich ilustrace na příkladech
===== Vypracování =====
==== Klíčové pojmy ====
Náhodnostní algoritmy
* během výpočtu dělají náhodná rozhodnutí <= výsledek závisí jak na vstupu, tak na náhodném žetězci bitů
* často jednodušší a účinější než determ. alg.
* kvantové výpočty jsou vesměs randomizované
** Pravděpodobnostní rozdělení **
** Náhodná proměnná **
** Očekávaná hodnota **
==== Klasifikace náhodnostních algoritmů ====
=== Podle umístění pravděpodobnosti ===
== I. model ==
Náhodnostní algoritmus chápeme jako pravděpodobnostní rozdělení nad množinou deterministických algoritmů {A_i,p_i}_i=1..n
Pro vstupní instanci se náhodně vybere strategie A_i
Příklady:
- Problém rovnosti
- MAX-SAT
== II. model ==
Náhodnostní algoritmus modelujeme nedeterministickým algoritmem s pravděpodobnostním rozdělením nad nedeterministickými volbami.
Příklad:
- RQUICKSORT
=== Podle typu a velikosti chyby ===
== Las Vegas ==
Pr(A(x)=F(X)) = 1
== Las Vegas s odpovědí nevím ==
Pr(A(x)=F(X)) >= 1/2
Pr(A(x)=nevim) = 1- Pr(A(x)=F(X))
Příklad:
- Problém rovnosti několika dvojic řetězců
== Monte Carlo s jednosměrnou chybou - 1MC ==
- použitelné pro rozhodovací problémy
Pr(A(x)=1)>=1/2
Pr(A(x)=0)=1
1MC* - hodnota Pr(A(x)=1) se s rostoucí délkou x limitně blíží 1
Příklad:
- Problém rovnosti
== Monte Carlo s ohraničenou chybou - 2MC ==
Pr(A(x)=F(X)) >= 1/2 + e
== Monte Carlo s neohraničenou chybou - MC ==
Pr(A(x)=F(X)) >= 1/2
=== Pravděpodobnostní algoritmy pro optimalizační úlohy ===
- jako střední hodnotu chápeme aproximativní poměr algoritmu
- nezávislé opakování běhu algoritmu použijeme na získání řešení lepší kvality
Příklady:
- Minimální řez (kontrakcí vrcholů)
- Řešení kolizí
- MAX-SAT
==== Pravděpodobnostní složitostní třídy ====
== RP (Random Polynomial Time)==
Jazyk L je v RP pokud existuje NTS M takový, že:
* => Pr(A(x) akceptuje) >= 1/2
* => Pr(A(x) akceptuje) = 0
(Monte Carlo acceptance)
co-RP:
* => Pr(A(x) akceptuje) = 1
* => Pr(A(x) akceptuje) <= 1/2
== ZPP (Zero-error Probabilistic Polynomial Time)==
RP průnik co-RP
(Las Vegas acceptance)
== PP (Probabilistic Polynomial Time) ==
Jazyk L je v PP pokud existuje NTS M takový, že:
* => Pr(A(x) akceptuje) > 1/2
* => Pr(A(x) akceptuje) <= 1/2
== BPP (Bounded-error Probabilistic Polynomial Time) ==
Jazyk L je v BPP pokud existuje NTS M takový, že:
* => Pr(A(x) akceptuje) >= 3/4
* => Pr(A(x) akceptuje) < 3/4
(Acceptance by majority)
==== Metody tvorby náhodnostních algoritmů ====
- časté kombinování více metod
=== Eliminace protihráčů (Foiling the adversary) ===
- v podstatě metoda vyhýbání se nejhorším případům
- nalezení takové množiny algoritmů, že pro každý vstup většina z nich efektivně spočítá správný výsledek
- za náhodnostní algoritmus je bráno náhodnostní rozložení deterministických algoritmů
== Game Tree evolution ==
== RQUICKSORT ==
== Problém rovnosti ==
- množina deterministivkých algoritmů je určená množinou prvočísel
=== Metoda svědků (Abundance of Witnesses) ===
- Vhodný pro rozhodovací problémy, kdy nás zajímá, či daný vstup má určitou vlastnost (např. jestli je prvočíslo)
- Svědek y pro vstup x a problém P je informace, se kterou můžeme vyřešit problém P pro vstup x efektivněji
- Nalezením množiny, kde nejméně 1/2 prvků jsou svědkové a náhodným výběrem z ní vybereme svědka s rozumnou pravděpodobností.
Pro použití metody potřebujeme úlohy splňující podmínky:
- existence svědka
- efektivní konstrukce kandidáta + test
- množina kandidátů bohatá na svědky
== Test prvočíselnosti==
Rabin-Miller
=== Fingerprinting ===
- je účinější pracovat s malými haši velkých objektů (2 řetězce jsou pravděpodobně identické, pokud jsou jejich haše identické)
== Rozhodování příslušnosti v množině ==
== Problém rovnosti ==
=== Náhodné vzorkování (Random sampling) ===
- neumíme efektivně hledat objekty daných vlastností, ale víme, že je jich hodně
- pokud je na množině dostatečně mnoho objektů, které hledáme, náhodné vzorkování na této množině vede k nalezení vhodných objektů s velkou pravděpodobností.
== Grafové a geometrické algoritmy ==
=== Náhodné zaokrouhlování (Random rounding)===
- těžce řešitelný optimalizační problém je převeden na snáze řešitelný zvýšením prostoru řešení
- výsledky nového problému slouží k vytvoření náhodnostního algoritmu k řešení původního problému
- využití lineárního programování
== Wiring Problem ==
== MAX SAT==
=== Amplifikace ===
- snížení pravděpodobnosti chybné odpovědi za cenu zvýšení časové složitosti
- opakujeme výpočet na vstupu NEZÁVISLE k-krát za sebou
== Minimální řez ==
=== Derandomizace ===
- efektivní náhodnostní algoritmus převedeme na deterministický, většinou simulováním všech možných behů náhodnostního algoritmu
== MAX-SAT ==
=== Náhodné procházky - Markov Chains ===
== Grafové problémy ==
===== Předměty =====
* [[https://is.muni.cz/auth/predmet/fi/IV111|IV111 Pravděpodobnost v informatice]]
* [[https://is.muni.cz/auth/predmet/fi/IA101|IA101 Algoritmika pro těžké problémy]]
* [[https://is.muni.cz/auth/predmet/fi/IA062|IA062 Randomized Algorithms and Computations]]