Programování pro deskriptivní geometrii II - NMTD104

• Anglický název: Computer programming for descriptive geometry II
• Zajišťuje: Katedra didaktiky matematiky (32-KDM)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2022
• Semestr: letní
• E-Kredity: 4
• Rozsah, examinace: letní s.:2/2, 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í
• Způsob výuky: prezenční
• Garant: doc. RNDr. Pavel Töpfer, CSc.; doc. RNDr. Antonín Slavík, Ph.D.
• Korekvizity : NMTD103
• Neslučitelnost : NMIN112, NMUG104
• Záměnnost : NMIN112, NMUG104
• Je neslučitelnost pro: NMUG104, NMIN112
• Je záměnnost pro: NMUG104

Anotace

čeština

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

Základní kurz programování pro 1. ročník bakalářského studia. 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 NMTD103 Programování pro deskriptivní geometrii I, na který tento předmět přímo navazuje.

angličtina

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

The second part of basic course of programming for first-year students. The course covers programming in Python, basic algorithms and data structures and practical program design and debugging. The knowledge of the course NMTD103 Computer programming for descriptive geometry I is expected.

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

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

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 cvičení,

• vypracování zápočtového programu.

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

Literatura

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

• 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. (22.11.2023)

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 NMTD103 a NMTD104. 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. Ústní část sestává z diskuze nad písemnou částí a případně z odpovědí na otázky vycházející ze sylabu.

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

• 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 NMTD103 Programování pro deskriptivní geometrii I.

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 NMTD103 Computer programming for descriptive geometry I is expected.