NPRG062 Algoritmizace

 

Obsahem předmětu jsou základy algoritmizace - seznámení se základními algoritmy, datovými strukturami, programovacími technikami a postupy užívanými při návrhu programů.

 

Výuka je vedena na bázi programovacího jazyka Python. Programovací jazyk ovšem není předmětem výuky, je využíván pouze jako prostředek pro zápis algoritmů. Výklad a procvičení jazyka Python je obsahem souběžně vyučovaného předmětu NPRG030 Programování 1.

 

Přednáška probíhá v obvyklém rozsahu dvou vyučovacích hodin týdně. Je doplněna jednohodinovým cvičením (v různých časech a s různými cvičícími - podle studijních skupin).

 

Sylabus předmětu

 

- algoritmus, časová a paměťová složitost

- asymptotická složitost algoritmů

- složitost problému
- dělitelnost čísel, Eukleidův algoritmus
- test prvočíselnosti, Eratosthenovo síto
- rozklad čísla na cifry
- aritmetika s vyšší přesností („dlouhá čísla“)
- Hornerovo schéma, poziční číselné soustavy
- algoritmy vyhledávání v poli (sekvenční, binární, zarážka)
- třídění čísel v poli - přímé metody, heapsort, quicksort, mergesort
- složitost problému třídění
- třídění počítáním, přihrádkové třídění, radixsort
- vnější třídění

- zásobník, fronta, slovník, halda

- spojový seznam
- rekurze – princip, příklady, efektivita
- binární a obecný strom – reprezentace, průchod stromem, použití
- binární vyhledávací strom, princip vyvažování
- hešovací tabulka
- notace aritmetického výrazu – vyhodnocení, převody
- reprezentace grafu
- průchod grafu do hloubky a do šířky, základní grafové algoritmy
- rekurzivní generování

- prohledávání stavového prostoru do hloubky a do šířky
- metody zrychlení backtrackingu – ořezávání, heuristiky
- programování her, algoritmus minimaxu
- metoda Rozděl a panuj

- další metody návrhu algoritmů – předvýpočet, hladový algoritmus, memoizace, dynamické programování

 

Studijní materiály

 

Prezentace z přednášek
- aktuálně vždy po přednášce v kurzu Algoritmizace na Moodlu https://dl1.cuni.cz/course/view.php?id=8186 (přístupové heslo se dozvíte na první přednášce, příp. na cvičení)

- publikované prezentace budou často rozšířené a doplněné oproti tomu, co se skutečně promítalo na přednášce

- navíc ukázkové programy v Pythonu z přednášek (zdrojové kódy)

Pavel Töpfer: Algoritmy a programovací techniky

- vydal Prometheus Praha 1995, 2. vydání 2007
- učebnice přímo určená pro základní kurz algoritmizace a programování

- je staršího data, takže programové ukázky jsou v Pascalu, ale jsou dobře srozumitelné

- tištěná učebnice je vyprodaná, ale je k zapůjčení v knihovnách

- nyní lze koupit jako e-knihu na https://www.prometheus-eknihy.cz/


Martin Mareš, Tomáš Valla: Průvodce labyrintem algoritmů

- vydal CZ.NIC Praha 2017

- programové ukázky v dobře srozumitelném pseudokódu

- větší rozsah výuky, než zahrnuje naše přednáška

- text ve formátu pdf zdarma na http://pruvodce.ucw.cz/ a na https://knihy.nic.cz/  

 

Programátorské kuchařky KSP

- krátké studijní texty k jednotlivým tématům z algoritmizace a programování

- volně k dispozici na http://ksp.mff.cuni.cz/kucharky/

 

 

Zápočet a zkouška

 

Předmět NPRG062 Algoritmizace je zakončen zápočtem a zkouškou. Přesné podmínky pro získání zápočtu stanovuje cvičící, který také zápočet uděluje. Požaduje se pravidelná aktivní účast na cvičeních a splnění zadaných domácích úkolů.

 

Zkouška má standardně povinnou písemnou a volitelnou ústní část. Předpokládají se znalosti v rozsahu výše uvedeného sylabu a schopnost jejich aplikace při řešení zadaných úloh. Další podrobnosti a ukázka úloh z loňského roku jsou k dispozici v kurzu Moodle. Nutnou podmínkou pro přihlášení ke zkoušce je předchozí získání zápočtu.