Programování 2 - NMIN112

• Anglický název: Programming 2
• Zajišťuje: Katedra softwaru a výuky informatiky (32-KSVI)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2022
• Semestr: letní
• E-Kredity: 8
• Rozsah, examinace: letní s.:2/4, Z+Zk [HT]
• Počet míst: neomezen
• Minimální obsazenost: neomezen
• 4EU+: ne
• Virtuální mobilita / počet míst pro virtuální mobilitu: ne
• Stav předmětu: vyučován
• Jazyk výuky: čeština
• Způsob výuky: prezenční
• Garant: doc. RNDr. Pavel Töpfer, CSc.
• Vyučující: RNDr. Martin Holub, Ph.D.; RNDr. Peter Kvasnička; Mgr. Martin Mareš, Ph.D.; RNDr. Martin Pergel, Ph.D.; Mgr. Klára Pešková, Ph.D.; Mgr. Jan Střeleček; Mgr. Jiří Šejnoha; doc. RNDr. Pavel Töpfer, CSc.
• Třída: 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
• Kategorizace předmětu: Informatika > Programování
• Korekvizity : NMIN111
• Neslučitelnost : NMTD104, NPRG062
• Je neslučitelnost pro: NMIN102, NMTD104, NPRG062
• Je záměnnost pro: NMTD104, NMIN102
• Ve slož. prerekvizitě: NPRG041, NPRG041, NPRX041

Anotace

čeština

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: Töpfer Pavel, doc. RNDr., CSc. (17.02.2020)

angličtina

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.

Poslední úprava: Töpfer Pavel, doc. RNDr., CSc. (17.02.2020)

Podmínky zakončení předmětu

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

Poslední úprava: Töpfer Pavel, doc. RNDr., CSc. (01.01.2024)

Literatura

• 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

Poslední úprava: Töpfer Pavel, doc. RNDr., CSc. (16.02.2020)

Požadavky ke zkoušce

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.

Poslední úprava: Töpfer Pavel, doc. RNDr., CSc. (02.05.2020)

Sylabus

čeština

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

Poslední úprava: Töpfer Pavel, doc. RNDr., CSc. (16.02.2020)

angličtina

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

Poslední úprava: Töpfer Pavel, doc. RNDr., CSc. (18.05.2022)