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 [hodiny/týden]
• Počet míst: neomezen
• Minimální obsazenost: neomezen
• Virtuální mobilita / počet míst: 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.
• 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, NPRX041

Anotace

čeština

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.

angličtina

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

čeština

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í

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

angličtina

Poslední úprava: 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.