Poslední úprava: doc. RNDr. Pavel Töpfer, CSc. (17.02.2020)
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.
Poslední úprava: doc. RNDr. Pavel Töpfer, CSc. (17.02.2020)
The second part of basic course of programming for first-year students of mathematics. The course covers
programming in Python, basic algorithms and data structures and practical program design and debugging.
The knowledge of the course NMIN111 Programming 1 is expected.
Podmínky zakončení předmětu
Poslední úprava: doc. Mgr. Petr Kaplický, Ph.D. (30.05.2019)
Předmět je zakončen zápočtem a zkouškou. K získání zápočtu se požaduje:
aktivní účast na cvičení spočívající obvykle v řešení úkolů (programů) v termínech stanovených cvičícím (ať už na cvičení nebo doma),
vypracování zápočtového programu a jeho odevzdání do termínu stanoveného cvičícím.
Povaha těchto požadavků neumožňuje vypsat opravné termíny. Vyučující stanoví podmínky, za nichž student může nahradit chybějící domácí úkoly nebo opakovaně odevzdat zápočtový program po odstranění nalezených závad.
Zkouška má písemnou a ústní část. Na složení zkoušky má student tři pokusy (jeden řádný a dva opravné termíny).
Literatura
Poslední úprava: doc. RNDr. Pavel Töpfer, CSc. (16.02.2020)
Pavel Töpfer: Algoritmy a programovací techniky, Prometheus Praha 1995, 2. vyd. 2007, https://www.prometheus-eknihy.cz/
Martin Mareš, Tomáš Valla: Průvodce labyrintem algoritmů, CZ.NIC Praha 2017, volně ke stažení na http://pruvodce.ucw.cz/
Programátorské kuchařky KSP, volně ke stažení na http://ksp.mff.cuni.cz/kucharky/
John V. Guttag, Introduction to Computation and Programming Using Python: With Application to Understanding Data, 2nd ed.,, MIT Press, Cambridge, MA 2016
Allen B. Downey, Think Python: How to Think Like a Computer Scientist, 2nd ed., O'Reilly Media, Sebastopol, CA 2015
Požadavky ke zkoušce
Poslední úprava: doc. RNDr. Pavel Töpfer, CSc. (02.05.2020)
Zkouška má povinnou písemnou a nepovinnou ústní část. Požadují se znalosti programovacího jazyka a algoritmů v rozsahu sylabů přednášek NMIN111 a NMIN112. Součástí písemné části zkoušky je vyřešení několika menších úloh, v nichž je úkolem návrh efektivního algoritmu, volba vhodných datových struktur, zapsání algoritmu ve tvaru funkce v Pythonu, odhad časových a paměťových nároků navrženého algoritmu.
K účasti na zkoušce není nutné předchozí získání zápočtu.
Sylabus
Poslední úprava: doc. RNDr. Pavel Töpfer, CSc. (16.02.2020)
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í
