NMIN112 Programování 2
Předmět navazuje na seminář NMIN111 Programování 1 ze zimního semestru, ve kterém jsme se seznámili se základy programování v programovacím jazyce Python. Obsahem předmětu Programování 2 je rozšíření a praktické procvičení znalostí a dovedností potřebných při návrhu a tvorbě programů. Přednáška bude věnována zejména problematice algoritmického návrhu programů – tedy seznámení se základními algoritmy, datovými strukturami a programovacími technikami s ohledem na efektivitu vytvářených programů. Na cvičeních vedle toho doplníme a procvičíme znalosti programovacího jazyka Python.
Přednáška probíhá pro všechny společně každý týden v úterý odpoledne v obvyklém rozsahu dvou vyučovacích hodin v posluchárně N1. Přednáška je pro každou studijní skupinu doplněna dvěma dvouhodinovými cvičeními týdně. Jedno cvičení je teoretické, bude sloužit k procvičení učiva z přednášky a k přípravě na zkoušku. Druhé cvičení je praktické u počítačů, bude věnováno výuce dalších prostředků programovacího jazyka Python a praktickému procvičení návrhu a ladění programů. Cvičení se budou konat v počítačových učebnách N8, N10 a N11.
Sylabus
- algoritmus, časová a prostorová složitost
- asymptotická složitost algoritmů
- složitost
problému
- dělitelnost čísel, Eukleidův algoritmus
- test prvočíselnosti, prvočíselný rozklad, Eratosthenovo síto
- rozklad čísla na cifry
- aritmetika s vyšší přesností („dlouhá čísla“)
- práce s polynomy, Hornerovo schéma
- poziční
číselné soustavy
- vyhledávání v poli (sekvenční, binární, zarážka)
- řazení čísel v poli - přímé metody, heapsort, quicksort, mergesort
- určení k-tého nejmenšího prvku (quickselect)
- dolní odhad
složitosti problému třídění
- přihrádkové metody třídění
- vnější třídění
- reprezentace dat v paměti
- zásobník, fronta, halda, slovník
- spojový seznam a operace v něm
- rekurze -
princip, příklady, efektivita
- binární a obecný strom - reprezentace, průchod, použití
- notace aritmetického výrazu - vyhodnocení, převody
- binární vyhledávací strom, princip vyvažování
- hešování, hešovací tabulka
- reprezentace grafu v programu
- prohledávání grafu, 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“
- dynamické programování
- další metody návrhu efektivních algoritmů
Prezentace z přednášek
- aktuálně vždy po přednášce na webu přednášejícího (často rozšířené a
doplněné oproti přednášce)
- ukázkové programy v Pythonu
Pavel Töpfer: Algoritmy a programovací techniky
- Prometheus Praha 1995, 2. vydání 2007
- učebnice přímo určená pro základní kurz algoritmizace a programování
- starší text, programové ukázky jsou proto 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 pouze jako e-knihu na https://www.prometheus-eknihy.cz/
Martin Mareš, Tomáš Valla: Průvodce labyrintem algoritmů
- CZ.NIC Praha 2017
- 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 algoritmizace a programování na http://ksp.mff.cuni.cz/kucharky/
Dokumentace jazyka Python
Mark Pilgrim: Ponořme se do Pythonu 3
- rozsáhlá učebnice programovacího jazyka Python 3, v českém překladu
- volně dostupná na webu http://diveintopython3.py.cz/index.html
Odkazy na další studijní materiály najdete na webu https://python.cz/zacatecnici/
Zápočet a zkouška
Předmět NMIN112 Programování 2 je zakončen zápočtem a zkouškou. Přesné podmínky a časové termíny pro získání zápočtu vám sdělí váš cvičící, který také zápočet uděluje. Vždy se požaduje pravidelná aktivní účast na cvičeních, splnění zadaných domácích úkolů z teoretické i praktické části cvičení, úspěšné absolvování praktického zápočtového testu a vypracování zápočtového programu.
Zkouška má povinnou písemnou a doplňkovou ústní část. Předpokládají se znalosti v rozsahu výše uvedeného sylabu, schopnost uplatnit je při řešení úloh a znalost programování v jazyce Python. Předchozí získání zápočtu není podmínkou pro účast na zkoušce.