Programování 2

Sylabus

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

- 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, mergesort, quicksort

- složitost problému třídění

- přihrádkové třídění

- vnější třídění

- reprezentace dat v paměti - alokace paměti, garbage collector

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

- spojový seznam

- 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šovací tabulka

- reprezentace grafu

- prohledávání grafu, základní grafové algoritmy

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

Předpokládají se vstupní znalosti v rozsahu předmětu NMIN111 Programování 1.

Anotace

Základní kurz programování pro 1. ročník bakalářského studia matematických studijních programů. Obsahem kursu je programování v jazyce Python, metody návrhu algoritmů a tvorby programů.

Předpokládají se vstupní znalosti v rozsahu předmětu NMIN111 Programování 1, na který tento předmět přímo navazuje.