4.6.2015 10:00 Mareš

Dnes dopoledne bylo zadání následující:

1. QuickSort - popsat fungování, časovou složitost (best, worst, avg.)

2. Komponenty silné souvislosti - popsat + algoritmus pro hledání komponent (i s důkazem)

3. Představte si, že máte šifrovací mřížku, tj. standardní transpoziční šifru. Jedná se v podstatě o permutace $\pi$ na $\left\lbrace 1, \dots N \right\rbrace$, opakované šifrování je pak skládání ($k$ složení je $\pi^k$). Najděte takové minimální $k > 0$, aby $\pi ^ k = \text{id}$ (nezakódovaný text).

4. Máme skoro setříděnou posloupnost (každý prvek, je nejvýše ve vzdálenosti $d$ od správné polohy), vymyslete algoritmus pro její dotřídění