ARTP - 09 - Markovova nerovnosť. Náhodné pochôdzky. SAT.

Zhrnutie prednášky

Prednáška porovnáva Las Vegas a Monte Carlo algoritmy a ukazuje, ako sa Las Vegas algoritmus dá premeniť na Monte Carlo: spustí sa len na K krokov a ak nedobehne, vráti sa náhodne tipnutá odpoveď. Chybu pomáha odhadnúť Markovova nerovnosť, ktorú prednáška dokazuje z definície strednej hodnoty: pre nezápornú náhodnú premennú platí P(X ≥ c·μ) ≤ 1/c. Pri K rovnom dvojnásobku strednej hodnoty času je tak pravdepodobnosť chyby najviac 1/2. Druhá časť sa venuje problému SAT, teda splniteľnosti formúl v konjunktívnom normálnom tvare. 3-SAT je NP-ťažký, kým 2-SAT je riešiteľný v polynomiálnom čase. Začína sa výklad Papadimitriouovho náhodného algoritmu, ktorý vychádza z náhodného priradenia a opravuje nesplnené klauzuly.

• - Las Vegas algoritmy dávajú vždy správny výsledok, ich čas behu je náhodný.
• - Monte Carlo algoritmy majú obmedzený čas behu, ale môžu s malou pravdepodobnosťou dať chybnú odpoveď.
• - Las Vegas algoritmus sa premení na Monte Carlo ukončením po K krokoch a tipnutím odpovede.
• - Markovova nerovnosť: pre X ≥ 0 a c > 1 platí P(X ≥ c·E[X]) ≤ 1/c.
• - Pri K = 2·E[T] je pravdepodobnosť neukončenia, a teda chyby, najviac 1/2.
• - SAT je NP-ťažký, 2-SAT je riešiteľný deterministicky v čase O(n + m).
• - Náhodný algoritmus pre SAT začína náhodným priradením a vyberá nesplnenú klauzulu.

Zhrnutie pripravené s pomocou AI z prepisu videa.