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ů

 

 

Studijní materiály

 

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

https://docs.python.org/3/

 

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.