SubjectsSubjects(version: 849)
Course, academic year 2019/2020
   Login via CAS
Programming 2 - NMIN102
Title in English: Programování 2
Guaranteed by: Department of Software and Computer Science Education (32-KSVI)
Faculty: Faculty of Mathematics and Physics
Actual: from 2019
Semester: summer
E-Credits: 5
Hours per week, examination: summer s.:2/2 C+Ex [hours/week]
Capacity: unlimited
Min. number of students: unlimited
State of the course: not taught
Language: Czech
Teaching methods: full-time
Guarantor: RNDr. Martin Pergel, Ph.D.
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 : NMIN101
Incompatibility : NMIN112
Interchangeability : NMIN112
Is co-requisite for: NMIN201
Is incompatible with: NPRG030
In complex pre-requisite: NPRG041, NPRX041
Annotation -
Last update: G_M (24.04.2012)
The second part of basic course of programming for students of mathematics. Beside programming in Pascal it covers the main problems of algorithm and program design.
Course completion requirements - Czech
Last update: doc. RNDr. Pavel Töpfer, CSc. (11.10.2017)

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. (30.09.2017)
  • P.Töpfer: Algoritmy a programovací techniky, Prometheus Praha 1995, 2. vyd. 2007
  • N.Wirth: Algorithms + Data Structures = Programs , Prentice Hall Englewood Cliffsů; New Jersey 1975
  • slovenský překlad N. Wirth: Algoritmy a štruktúry údajov, Alfa, Bratislava 1989
  • I.Libicher, P.Töpfer: Od problému k algoritmu a programu, Grada Praha 1992

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

Zkouška zahrnuje učivo z obou semestrů základního kursu programování, tzn. z předmětů NMIN101 a NMIN102. K účasti na zkoušce není nutné předchozí získání zápočtu. Zkouška má písemnou a ústní část.

V písemné části studenti řeší dvě úlohy. V první úloze technického charakteru je úkolem napsat jednoduchý program, proceduru nebo funkci v Pascalu, posuzuje se i syntaktická správnost zápisu. Úlohy jsou zaměřeny na zvládnutí práce s dynamickými datovými strukturami. Druhá úloha je rozsáhlejší, součástí jejího řešení je i přesnější formulace problému na základě obecného slovního zadání. Studenti nemusí programovat detailně celou úlohu, požaduje se návrh efektivního algoritmu, vhodné rozdělení úlohy na menší části, návrh jejich vzájemné komunikace, volba hlavních datových struktur, zapsání nejpodstatnějších částí algoritmu ve formě programu nebo stačí i vhodného pseudokódu a hrubý odhad časových a paměťových nároků výsledného programu.

V ústní části zkoušky se požadují znalosti programovacího jazyka a algoritmů v rozsahu sylabů přednášek NMIN101 a NMIN102. Součástí zkoušky je také rozbor úloh z písemné části zkoušky formou diskuse nad zvolenými řešeními. Předpokládá se schopnost zvážit přednosti a nedostatky různých alternativních způsobů řešení.

Syllabus -
Last update: doc. RNDr. Pavel Töpfer, CSc. (11.10.2017)
1. Programming language Pascal
  • modular programming, units
  • pointer, dynamic allocation variables
  • object programming

2. Algorithms and programming

  • heaps and heap operations
  • recursive sorting (quicksort, mergesort)
  • bucketsort, radixsort
  • finding of the k-th smallest element (quickselect)
  • external sorting (file sorting)
  • dynamic data structures
  • linked list operations
  • using of linked lists - stack and queue, long numbers, polynoms
  • trees, graphs, basic algorithm on them
  • binary search trees, opearations, balanced binary trees (AVL trees)
  • multiway trees (B-trees)
  • arithmetic notations, representing and evaluating arithmetic expressions
  • dynamic programming
  • basic graph algorithms

Input knowledge according to the course NMIN101 Programming 1 is expected.

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