4. Metody tvorby náhodnostních algoritmů a jejich ilustrace na příkladech

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

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:

1. Problém rovnosti
2. MAX-SAT

Náhodnostní algoritmus modelujeme nedeterministickým algoritmem s pravděpodobnostním rozdělením nad nedeterministickými volbami.
Příklad:

1. RQUICKSORT

Pr(A(x)=F(X)) = 1

Pr(A(x)=F(X)) >= 1/2
Pr(A(x)=nevim) = 1- Pr(A(x)=F(X))

Příklad:

1. Problém rovnosti několika dvojic řetězců

- 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:

1. Problém rovnosti

Pr(A(x)=F(X)) >= 1/2 + e

Pr(A(x)=F(X)) >= 1/2

- 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:

1. Minimální řez (kontrakcí vrcholů)
2. Řešení kolizí
3. MAX-SAT

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

RP průnik co-RP
(Las Vegas acceptance)

Jazyk L je v PP pokud existuje NTS M takový, že:

• ⇒ Pr(A(x) akceptuje) > 1/2
• ⇒ Pr(A(x) akceptuje) ⇐ 1/2

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)

- časté kombinování více metod

- 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ů

- množina deterministivkých algoritmů je určená množinou prvočísel

- 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:

1. existence svědka
2. efektivní konstrukce kandidáta + test
3. množina kandidátů bohatá na svědky

Rabin-Miller

- 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é)

- 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í.

- 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í

- 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

- efektivní náhodnostní algoritmus převedeme na deterministický, většinou simulováním všech možných behů náhodnostního algoritmu

• IV111 Pravděpodobnost v informatice
• IA101 Algoritmika pro těžké problémy
• IA062 Randomized Algorithms and Computations