SubjectsSubjects(version: 953)
Course, academic year 2023/2024
   Login via CAS
Programming 2 - NMIN112
Title: Programování 2
Guaranteed by: Department of Software and Computer Science Education (32-KSVI)
Faculty: Faculty of Mathematics and Physics
Actual: from 2022
Semester: summer
E-Credits: 8
Hours per week, examination: summer s.:2/4, 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.
Class: 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
Classification: Informatics > Programming
Co-requisite : NMIN111
Incompatibility : NMTD104, NPRG062
Is incompatible with: NMIN102, NMTD104, NPRG062
Is interchangeable with: NMTD104, NMIN102
In complex pre-requisite: NPRG041, NPRG041, NPRX041
Annotation -
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.
Last update: Töpfer Pavel, doc. RNDr., CSc. (17.02.2020)
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 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).

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

Last update: Töpfer Pavel, doc. RNDr., CSc. (02.05.2020)
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 NMIN111 Programming 1 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