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.
Last update: doc. RNDr. Pavel Töpfer, CSc. (16.09.2019)
Přednáška pro posluchače bakalářského studia matematiky, kteří tento předmět úspěšně neabsolvovali v prvním
roce svého studia. Obsahem kursu je programování v jazyce Pascal, metody návrhu algoritmů a tvorby programů.
Předpokládají se vstupní znalosti v rozsahu předmětu NMIN101 Programování 1, na který tento předmět přímo
navazuje.
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. (02.05.2020)
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 ú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.
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.
Last update: doc. RNDr. Pavel Töpfer, CSc. (16.09.2019)
1. Programovací jazyk Pascal
modulární programování, unity
typ ukazatel, dynamicky alokované proměnné
objektové programování
2. Algoritmy a programování
halda, heapsort
rekurzivní třídění (quicksort, mergesort)
přihrádkové třídění (bucketsort, radixsort)
dolní odhad složitosti problému třídění
hledání k-tého nejmenšího prvku (quickselect)
vnější třídění
dynamicky alokované proměnné, dynamické datové struktury
lineární spojové seznamy a operace s nimi, druhy lineárních spojových seznamů
použití lineárních spojových seznamů - zásobník a fronta, dlouhá čísla, polynomy
