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í
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.