9.2 Randomizace a její využití

1 Úvod 2 Grafy 3 Stromy 4 Kostry 5 Základní grafové algoritmy 6 Nejkratší cesty v ohodnocených grafech 7 Složitost 8 Haldy 9 Randomizace 9.1 Pravděpodobnost 9.2 Randomizace a její využití 9.3 Hešování 10 Řazení 11 Dynamické programování Index Literatura

9.2 Randomizace a její využití

9.2.1 Randomizovaný výpočetní model

Definice 9.6 (Randomizovaný výpočetní model)

Randomizovaný výpočetní model je výpočetní model RAM doplněný o novou instrukci $X := \text{random}(Y, Z)$, která vygeneruje náhodné celé číslo z intervalu $\langle Y, Z \rangle$ a uloží ho do $X$

Všechny hodnoty z tohoto intervalu jsou stejně pravděpodobné a volba je nezávislá na předchozích voláních.

Poznámka 9.2

Jaké vlastnosti může mít (rozhodovací) algoritmus využívající náhodné bity během svého výpočtu?

Pracuje vždy správně, ale celková doba výpočtu je závislá na náhodných bitech.
Celková doba výpočtu je nezávislá na náhodných bitech, ale algoritmus může občas odpovědět nevím (nebo se může občas „mýlit“)

9.2.2 Kontrola násobení matic

Příklad 9.7

Mějme (racionální) matice $A, B$ tvaru $n \times n$.

Naleznout matici $C = A \cdot B$:

Lze „školním algoritmem“ pomocí $O(n^3)$ aritmetických operací,
Lze Strassenovým algoritmem (1969) pomocí $O(n^{\log 7}) ≈ O(n^{2.807})$ aritmetických operací,
Lze pomocí $O(n^{\omega})$ aritmetických operací, kde $\omega < 2.371339$.

Pokročilé algoritmy se vyplatí jen pro opravdu velké matice.

Otázka 9.1

Jak si ale můžeme být jistí, že je výsledek správně?

Mějme (racionální) matice $A, B, C$ tvaru $n \times n$.

Chceme ověřit, že platí $C = A \cdot B$:

\begin{algorithm}
\begin{algorithmic}
\FUNCTION {VerifyMM}{$A$, $B$, $C$}
    \STATE Zvol náhodný vektor $x \in \{0, 1\}^n$
    \STATE $y = A \cdot (B \cdot x)$
    \STATE $z = Cx$
    \IF {$z$ == $y$}
        \RETURN "$C = A \cdot B$"
    \ENDIF
    \RETURN "$C \neq A \cdot B$"
\ENDFUNCTION\end{algorithmic}
\end{algorithm}

Věta 9.3

Algoritmus VerifyMM vykoná $O(n^2)$ aritmetických operací.

Pokud:

$C = A \cdot B$, algoritmus jistě odpoví „$C = A \cdot B$“
$C \neq A \cdot B$, pak algoritmus odpoví „$C \neq A \cdot B$“ s pravděpodobností alespoň $\frac{1}{2}$

Zobrazit důkaz

Pokud $C = A \cdot B$, pak pro všechna $x \in \{0, 1\}^n$ platí $Cx = A \cdot Bx$.

Předpokládejme, že $C \neq A \cdot B$. Položme $D = (C − AB)$.

Chceme ukázat, že pro libovolnou nenulovou matici $D$ a náhodný vektor $x \in \{0, 1\}^n$ platí $\mathbf{P}[Dx \neq 0] \ge \frac{1}{2}$

Buď $d_{i,j} \neq 0$ a označme $y = D \cdot x$. Tvrdíme, že $\mathbf{P}[y_i \neq 0] \ge \frac{1}{2}$Máme

\begin{equation*} y_i = d_{i,1}x_1 + d_{i,2}x_2 + … + d_{i,n}x_n = d_{i,j}x_j + S \end{equation*}

Volíme $x$ po složkách. Předpokládejme, že $x_j$ volíme jako poslední.

Před posledním hodem je hodnota $S$ zafixovaná a nezávisí na $x_j$.

Nyní $y_i = S$ nebo $y_i = S + d_{i,j}$. Alespoň jedna z těchto hodnot je nenulová (a každou vrátíme s pravděpodobností $1/2$).

$\square$

Pozorování 9.4

Pravděpodobnost $1/2$ ale není mnoho!

Pro zvýšení pravděpodobnosti správné odpovědi lze spustit algoritmus vícekrát.

Pokud VerifyMM spuštěný $50\times$ odpoví „$C = A \cdot B$“, pak

\begin{equation*} P[C \neq A \cdot B] \le (1/2)^50 < 10^{−15} \end{equation*}

To je pro praktické výpočty postačující a složitost algoritmu zůstává $O(n^2)$.

Otázka 9.2

Pokud pro vstup VerifyMM platí $C \neq A \cdot B$, kolkrát musíme v průměru algoritmus spustit, než dostaneme korektní odpověď?

Zobrazit odpověď

$\mathbf{E}[T] = 1/p = \frac{1}{\frac{1}{2}} = 2$