Předměty

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.

Poslední úprava: Töpfer Pavel, doc. RNDr., CSc. (16.09.2019)

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.

Poslední úprava: G_M (24.04.2012)

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

Poslední úprava: Töpfer Pavel, doc. RNDr., CSc. (11.10.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

Poslední úprava: Töpfer Pavel, doc. RNDr., CSc. (30.09.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 ú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.

Poslední úprava: Töpfer Pavel, doc. RNDr., CSc. (02.05.2020)

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

stromy, grafy, průchody stromem a grafem

binární vyhledávací stromy, operace, vyvážené stromy

aritmetické notace, vyhodnocení aritmetického výrazu

dynamické programování

programová realizace základních grafových algoritmů (souvislost grafu, Dijkstrův algoritmus, minimální kostra, bipartitnost, topologické třídění)

základy objektového programování

Předpokládají se vstupní znalosti v rozsahu předmětu NMIN101 Programování 1.

Poslední úprava: Töpfer Pavel, doc. RNDr., CSc. (16.09.2019)

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.

Poslední úprava: Töpfer Pavel, doc. RNDr., CSc. (11.10.2017)