Pojmy

Algoritmus -
Program -
Vstupní podmínka - vstupy, pro které je algoritmus definovaný, značí se $\phi$
Výstupní podmínka - výstup, který má funkce vrátit pro vstup, splňující vstupní podmínku, značí se $\psi$
Konvergence - program pro vstup splňující vstupní podmínku skončí
Parciálně korektní - pro každý vstup, který splňuje vstupní podmínku a který zároveň skončí, splňuje výstupní podmínku
Totálně korektní - pro každý vstup splňující podmínku program skončí a výstup splňuje výstupní podmínku
Statické datové struktury
Dynamické datové struktury

Najdi nejkratší hamiltonovský cyklus

korektní algoritmus: prozkoumej každý z n! cyklů grafu a vyber nejkratší
algoritmus je korektní, protože prověří všechny možnosti
složitost algoritmu je úměrná počtu všech Hamiltonovských cyklů a algoritmus je proto nepoužitelný již pro velmi malé grafy

Časová a prostorová složitost

přesná časová jednotka
- závislé na hardware, nastavení pc, …
- přesný čas
podle počtu elementárních operací
- nezávislé na hardware, kompletní informace
- ,,nekonečná“ tabulka, ,,neporovnatelnost“ algoritmu
pro počet operací pro danou skupinu vstupů (největší počet operací, pro vstupu seskupené podle délky)

časová složitost výpočtu je součet cen všech vykonaných operací
časová složitost algoritmu je funkce délky vstupu
- složitost v nejhorším případě: maximální délka výpočtu na vstupu délky n
- složitost v nejlepším případě: minimální délka výpočtu na vstupu délky n
- průměrná složitost: průměr složitostí výpočtů na všech vstupech délky n

složitost = časová složitost v nejhorším případě

$f \in O(g)$ znamená, že $C \cdot g(n)$ je horní hranicí pro $f(n)$
$f \in \Omega (g)$ znamená, že $C \cdot g(n)$ je dolní hranicí pro $f(n)$
$f \in \Theta (g)$ znamená, že $C_1 \cdot g(n)$ je horní hranicí pro $f(n)$ a $C_2 \cdot g(n)$ je dolní hranicí pro $f(n)$
$f, g$ jsou funkce, $f, g : \N \rarr \N$
$C, C_1, C_2$ jsou konstanty nezávislé na $n$

$f \in O(g)$ právě když existují kladné konstanty $n_0$ a $c$ takové, že pro všechna $n \geq n_0$ platí $f(n) \le cg(n)$
zápis $f \in O(g)$ vs zápis $f = O(g)$ (historické důvody; druhý zápis je špatně)
funkce $f$ neroste asymptoticky rychleji než funkce $g$
alternativní definice $f \in O(g)$ právě když $\limsup_{n \to \infty} \frac{f(n)}{g(n)} < \infty$

$f \in \Omega (g)$ právě když existují kladné konstanty $n_0$ a $c$ takové, že pro všechna $n \ge n_0$ platí $f(n) \ge cg(n)$
funkce $f$ neroste asymptoticky pomaleji než funkce $g$

$f \in \Theta (g)$ právě když existují kladné konstanty $n_0, c_1 a c_2$ takové, že pro všechna $n \ge n_0$ platí $c_1g(n) \le f(n) \le c_2g(n)$
funkce $f$ a $g$ rostou asymptoticky stejně rychle

$\Theta$ Notace -příklad

Vstupní podmínka:
ze všech možných vstupů pro daný algoritmus vymezuje ty vstupy, pro které je algoritmus definován
Výstupní podmínka:
pro každý vstup daného algoritmu splňující vstupní podmínku určuje, jak má vypadat výsledek odpovídající danému vstupu

algoritmus je (totálně) korektní jestliže pro každý vstup splňující vstupní podmínku výpočet skončí a výsledek splňuje výstupní podmínku
úplnost (konvergence):
pro každý vstup splňující podmínku výpočet skončí
částečná korektnost (parciální korektnost):
pro každý vstup, který splňuje vstupní podmínku a výpočet na něm skončí, výstup splňuje výstupní podmínku

analyzujeme efekt jednotlivých operací
analýza efektu cyklu (nejtěžší část)
- invariant cyklu: tvrzení, které platí před vykonáním a po vykonání každé iterace cyklu

inicializace: invariant je platný před začátkem vykonávání cyklu
iterace: jestliže invariant platí před iterací cyklu, zůstává v platnosti i po vykonání iterace
ukončení: cyklus skončí a po jeho ukončení platný invariant garantuje požadovaný efekt cyklu

Statické datové struktury Dynamické datové struktury