Computer programming for descriptive geometry II - NMTD104

• Title: Programování pro deskriptivní geometrii II
• Guaranteed by: Department of Mathematics Education (32-KDM)
• Faculty: Faculty of Mathematics and Physics
• Actual: from 2022
• Semester: summer
• E-Credits: 4
• Hours per week, examination: summer s.:2/2, 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.; doc. RNDr. Antonín Slavík, Ph.D.
• Co-requisite : NMTD103
• Incompatibility : NMIN112, NMUG104
• Interchangeability : NMIN112, NMUG104
• Is incompatible with: NMUG104, NMIN112
• Is interchangeable with: NMUG104

Annotation

English

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

Czech

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

Course completion requirements

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

Literature

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

Requirements to the exam

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

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

Czech

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