SubjectsSubjects(version: 953)
Course, academic year 2023/2024
   Login via CAS
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 -
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.
Last update: Töpfer Pavel, doc. RNDr., CSc. (22.11.2023)
Course completion requirements - Czech

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

Last update: Töpfer Pavel, doc. RNDr., CSc. (22.11.2023)
Literature - Czech
  • 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

Last update: Töpfer Pavel, doc. RNDr., CSc. (22.11.2023)
Requirements to the exam - Czech

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.

Last update: Töpfer Pavel, doc. RNDr., CSc. (22.11.2023)
Syllabus -
  • 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.

Last update: Töpfer Pavel, doc. RNDr., CSc. (18.05.2022)
 
Charles University | Information system of Charles University | http://www.cuni.cz/UKEN-329.html