Teoretické základy informatiky - vypracované státnicové okruhy

1. Pojem algoritmus a jeho složitost
Definice algoritmu, časová a paměťová složitost, příklady

Definice algoritmu
- popis určitého postupu, návodu, posloupnost kroků, které vedou k řešení úlohy
- hromadný, deterministický, rezultantní, elementární a finitivní

Složitost
- ukazuje trend růstu času (paměti) s rostoucí vstupní množinou
- závislost doby výpočtu (velikosti paměti) potřebné pro výpočet na počtu zpracovávaných údajů
- časová významnější, než paměťová - vzhledem k dnešním pamětem počítačů
Exponenciální
- prakticky využita pro ochranu šifrováním, jinak nelze reálně použít
Asymptotická - odhad
- zajímá nás hlavně chování funkce pro dostatečně velkou množinu, ne absolutní rychlost
- Ο (horní odhad), Ω (dolní odhad), Θ notace
- Často používáme řády funkcí, př. logaritmická složitost O (log n)
- Nejhorší, průměrná, přesná (na imaginárním počítači)

Optimalizace
- Vyjmutí přes cyklus, optimalizace těla cyklu, využíván předchozích výsledků, využívání cache

Metody návrhu algoritmu
Neexistuje všeobecný návod pro tvorbu algoritmů, jedná se o tvořivý proces → nelze automatizovat.
Existují však známé strategie (abstrakce, dekompozice) a paradigmata pro jejich tvorbu.

Postup
1. Formulace problému + definice vstupních a výstupních dat
2. Stanovení cíle
3. Volba strategie
4. Navržení postupu
5. Zápis vytvořených postupů
6. Ověření správnosti

Klasifikace algoritmu
- Podle implementace
o Rekurzivní vs. iterační, Sériové vs. paralelní, Deterministické vs. náhodné, Přesné vs. přibližné
- Podle paradigmatu
o Rozděl a panuj, Sniž a panuj, Žravé metody, Redukce, Dynamické programování, Heuristické algoritmy