Předmět má studenty seznámit s matematickými aplikacemi v informatice, zejména v oblastech ukládání čísel, numerické stability a výpočetní složitostí algoritmů, využití teorie grafů při vyhledávání a databázových operacích nebo aplikacemi výrokového a predikátového počtu; cvičení doplní teoretické p
Předmět má studenty seznámit s matematickými aplikacemi v informatice, zejména v oblastech ukládání čísel, numerické stability a výpočetní složitostí algoritmů, využití teorie grafů při vyhledávání a databázových operacích nebo aplikacemi výrokového a predikátového počtu; cvičení doplní teoretické poznatky úlohami v jazyce Python.
Po úspěšném absolvování budou studenti schopni implementovat vybrané algoritmy v jazyce Python a porozumět jejich matematické podstatě, problémům spojeným s časovým trváním výpočtů a vlivu zaokrouhlovacích chyb na výsledek získaný výpočtem na počítači.
• Ukládání čísel v počítači. Limity výpočetní přesnosti, zaokrouhlovací chyby. • Algoritmy. Pojem algoritmu, zápis pomocí pseudokódu. • Časová a paměťová náročnost algoritmů. Landauova notace (velké O), porovnání růstu některých běžných funkcí. • Iterativní versus rekurzivní algoritmy. Vybrané algoritmy typu rozděl a panuj. Dynamické programování. • Základní datové struktury: pole, spojový seznam, fronta, zásobník, operace na těchto strukturách. • Metody třídění. Klasifikace třídicích algoritmů, jejich časová a paměťová náročnost. Vybrané třídicí algoritmy a jejich implementace. • Binární kořenové stromy, vyhledávací stromy. 2-3-4 strom, optimální vyhledávací strom, Huffmanův strom, halda. • Vybrané numerické algoritmy, jejich výpočetní složitost a přesnost. • Využití grafů pro reprezentaci reálných úloh. Nalezení nejkratší cesty a minimální kostry. • Teoretická východiska algoritmizace. Výroková a predikátová logika, automaty. Korektnost algoritmu. • Úvod do teorie výpočetní složitosti. Třídy složitosti, populární příklady NP-úplných úloh.
Základní:
Doporučená příprava:
Používej Markdown: ## Nadpis, **tučně**, `kód`, - odrážky, > citace