Programming 2 - NMIN112

• Title: Programování 2
• Guaranteed by: Department of Software and Computer Science Education (32-KSVI)
• Faculty: Faculty of Mathematics and Physics
• Actual: from 2022
• Semester: summer
• E-Credits: 8
• Hours per week, examination: summer s.:2/4, C+Ex [HT]
• Capacity: unlimited
• Min. number of students: unlimited
• 4EU+: no
• Virtual mobility / capacity: no
• State of the course: taught
• Language: Czech
• Teaching methods: full-time
• Teaching methods: full-time
• Guarantor: doc. RNDr. Pavel Töpfer, CSc.
• Class: M Bc. FM; M Bc. FM > Povinné; M Bc. FM > 1. ročník; M Bc. MMIB; M Bc. MMIB > Povinné; M Bc. MMIB > 1. ročník; M Bc. MMIT; M Bc. MMIT > Povinné; M Bc. OM; M Bc. OM > Povinné; M Bc. OM > 1. ročník
• Classification: Informatics > Programming
• Co-requisite : NMIN111
• Incompatibility : NMTD104, NPRG062
• Is incompatible with: NMIN102, NMTD104, NPRG062
• Is interchangeable with: NMTD104, NMIN102
• In complex pre-requisite: NPRG041, NPRG041, NPRX041

Annotation

English

Last update: 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.

Czech

Last update: 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.

Course completion requirements

Last update: doc. RNDr. Pavel Töpfer, CSc. (01.01.2024)

Předmět je zakončen zápočtem a zkouškou. K získání zápočtu se požaduje:

• aktivní práce na cvičeních,

• získání alespoň 70% bodů za domácí úkoly zadávané průběžně na teoretickém cvičení,

• získání alespoň 70% bodů za domácí úkoly zadávané průběžně na praktickém cvičení,

• úspěšné absolvování závěrečného praktického testu z programování,

• vypracování zápočtového programu včetně písemné dokumentace.

Povaha těchto požadavků neumožňuje vypsat opravné termíny.

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

Literature

Last update: 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

Requirements to the exam

Last update: 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.

Syllabus

English

Last update: doc. RNDr. Pavel Töpfer, CSc. (18.05.2022)

• algorithm, time and space complexity

• divisibility of numbers, Euclid algorithm

• prime number test, Eratosthenes sieve

• decomposition of numbers into digits

• higher precision arithmetic ("long numbers")

• Horner's scheme, positional number systems

• searching algorithms (sequential, binary, breakpoint)

• sorting - direct methods, heapsort, mergesort, quicksort

• complexity of the sorting problem

• bucket sorting

• external sorting

• data representation in memory - memory allocation, garbage collector

• stack, queue, dictionary, heap

• linked list

• recursion - principle, examples, complexity

• binary and general tree

• arithmetic notation - evaluation, conversions

• binary search tree, balancing principle

• hash table

• data representation of graphs

• graph searching, basic graph algorithms

• DFS and BFS in state space

• backtracking acceleration methods - cutting, heuristics

• game programming, minimax algorithm

• Divide and Conquer method

• dynamic programming

Knowledge in the scope of the lecture NMIN111 Programming 1 is expected.

Czech

Last update: 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í

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