===== 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:
   * <math>x \in L </math> => Pr(A(x) akceptuje) >= 1/2
   * <math>x \notin L </math> => Pr(A(x) akceptuje) = 0
(Monte Carlo acceptance)

co-RP:
   * <math>x \in L </math> => Pr(A(x) akceptuje) = 1
   * <math>x \notin L </math> => 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:
   * <math>x \in L </math> => Pr(A(x) akceptuje) > 1/2
   * <math>x \notin L </math> => Pr(A(x) akceptuje) <= 1/2


== BPP (Bounded-error Probabilistic Polynomial Time) ==
Jazyk L je v BPP pokud existuje NTS M takový, že:
   * <math>x \in L </math> => Pr(A(x) akceptuje) >= 3/4
   * <math>x \notin L </math> => 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]]