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