SubjectsSubjects(version: 901)
Course, academic year 2021/2022
  
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 2019 to 2021
Semester: summer
E-Credits: 8
Hours per week, examination: summer s.:2/4 C+Ex [hours/week]
Capacity: unlimited
Min. number of students: unlimited
Virtual mobility / capacity: no
State of the course: taught
Language: Czech
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
Is incompatible with: NMIN102, NPRG062
Is interchangeable with: NMIN102
In complex pre-requisite: NPRG041, NPRX041
Annotation -
Last update: 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.
Course completion requirements - Czech
Last update: 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).

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

Requirements to the exam - Czech
Last update: 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.

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

 
Charles University | Information system of Charles University | http://www.cuni.cz/UKEN-329.html