I.ročník magisterského a bakalářského studia matematiky -
školní rok 2002/2003
Definitivní verze.
Zkouška má písemnou a ústní cást.
V písemné části studenti řeší dvě úlohy:
V první úloze technického charakteru je úkolem napsat
jednoduchou proceduru nebo program v Pascalu.
Jde převážně o zvládnutí práce se spojovými strukturami.
V této části se posuzuje se i syntaktická správnost programu.
Druhá úloha je náročnější.
Součástí jejího řešení je přesnější formulace problému na základě jeho obecného vymezení.
Studenti nemusí programovat detailně celou úlohu.
Požaduje se návrh algoritmu, vhodné rozdělení úlohy na menší části,
návrh jejich komunikace, volba hlavních datových struktur
a naprogramování několika nejpodstatnějších podprogramů.
Požadovaná míra přiblížení ke "skutečnému programu" se liší podle zadané úlohy a obvykle bude
při zadávání úlohy upřesněna. Součástí kompetencí studentů, které se v písemné části zkoušky
prověřují, je i schopnost krického pohledu na zadání úlohy (např. poznat které součásti zadání
jsou pro volbu řešení podstatné a které ne, resp. jaké další údaje musí program získat ze vstupu,
aby mohl úlohu správně a efektivně vyřešit).
Pri hodnocení písemné části zkoušky má větší váhu druhá úloha.
V ústní části zkoušky
zkoušející nejprve společně se studentem opraví úlohy z písemné části
formou diskuse nad zvolenými rešeními.
Po studentovi se požaduje vysvětlení, proč zvolil právě tento způsob řešení
a schopnost zvážit přednosti a nedostatky způsobů alternativních.
Kromě toho se u ústní části požadují tyto znalosti:
Programovací jazyk Pascal:
(pokud není řečeno jinak, máme na mysli implementaci Borland Pascal verze 7
nebo novější - nejde přitom o detaily, ale o princip)
datové typy a reprezentace jejich hodnot v paměti
(rozdíl mezi typem integer a real, pole, záznam,
záznam s variantami, množina, znakové řetězce, strukturované konstanty)
způsoby předávání parametrů podprogramům, procedurální parametry v Borland Pascalu
rekurse - přímá a nepřímá, direktiva forward
práce se soubory
(textové, datové, sekvenční a přímý prístup k souboru,
assign, různé způsoby otevření - reset, rewrite, append)
modularita
(unity, interfaceová a implementační část, klausule uses, MAKE a BUILD)
staticky a dynamicky alokované proměnné, typ ukazatel, organizace paměti
objektové programování, principy a realizace v Borland Pascalu
(zapouzdření;
dědičnost; statické a virtuální metody; implementace
virtuálních metod - existence VMT tabulky, konstruktor, destruktor;
veřejné a soukromé atributy objektů, abstraktní metody a objekty, funkce typeof, přetypování)
Efektivita algoritmů a její měření
asymptotická složitost, nejlepší, průměrný a nejhorší případ, konkrétní odhady jednoduchých algoritmů
Algoritmy vnitřního třídění, míry složitosti, dolní odhad složitosti úlohy,
konkrétní třídící algoritmy (přihrádkové třídění, třídění výběrem, přímé a binární zatřiďování,
bublinkové třídění, quicksort a jeho optimalizace, heapsort), horní odhad jejich složitosti
Hledání k-tého prvku
(první prvek, druhý prvek, n prvních prvků z n*n prvků, použití haldy, rozdělování „a la quicksort“,
lineární algoritmus)
Vnější třídění
rozdíl od úlohy vnitřního třídění,
typické algoritmy (přirozené slučování, polyfázové slučování, zvětšování běhu
předběžným předtříděním např.pomocí haldy)
Lineární spojové seznamy
různé typy (dvousměrné, hlava, ocas), základní operace se seznamy
Průchod grafem do hloubky a šířky
Transitivní (reflexivní a symetrický) uzávěr, faktorová množina.
Reprezentace čísel v paměti, doplňkový kód, zaokrouhlovací chyba, aritmetické operace,
absolutní a relativní chyba.
Stromy
reprezentace stromu (lesa) pomocí binárního stromu, binární stromy,
binární vyhledávací stromy a operace s nimi, průchody binárním stromem
a jejich souvislost s algebraickými notacemi, postavení dokonale
vyváženého stromu z rostoucí posloupnosti,
AVL-stromy a operace s nimi,
optimální vyhledávací strom.
Metody reprezentace grafu a programová realizace základních grafových algoritmu:
Hledání nejkratší cesty (Dijkstrův algoritmus a jeho modifikace, Floydův alg.),
hledání minimální kostry grafu, hledání komponent souvislosti, algoritmus topologického trídení
Použití generátoru pseudonáhodných čísel
(nikoli jeho konstrukce)
Vyčíslení hodnoty aritmetického výrazu, převody mezi různými algebraickými notacemi
Hašování
hašovací tabulka, hašovací funkce, kolise a některé metody jejich řešení