Požadavky ke zkoušce z předmětu
PRG030 Programování I.
zimní semestr 1. ročníku bakalářského
studijního programu Informatika školní rok 2003/2004
Zkouška má praktickou, písemnou a ústní část. Organizuje se společně pro všechny paralelky.
Získání zápočtu není podmínkou pro skládání zkoušky.
Praktický test u počítače
Složení testu je podmínkou připuštění studenta k dalším dvěma částem zkoušky.
Na složení testu má student tři pokusy. Počet pokusů, které student ke složení testu potřeboval,
nemá vliv na výsledek zkoušky, opakované skládání testu není opravnou zkouškou.
Test se neznámkuje, hodnotí se jen udělal - neudělal. V případě, že program vytvořený při testu je
buď velmi pěkný nebo hodně nešikovný, sdělí to zkoušející studentovi. K této informaci bude
přihlédnuto, bude-li známka z písemné a ústní části zkoušky "nerozhodná".
Výsledky praktického testu se nezapisují do zkušební zprávy, jsou evidovány u zkoušejících.
Při testu má student prokázat, že ovládl základy algoritmizace
a praktické dovednosti nutné k odladění programu na počítači.
Během 3 hodin musí student samostatně sestavit
a odladit na počítači program řešící středně obtížnou úlohu. Pracuje se v prostředí Borland Pascal 7.0.
Úlohy jsou formulovány tak, aby nevyžadovaly použítí "pokročilejších" částí jazyka Pascal
(dynamicky alokované proměnné, datové soubory, objektové programování).
Student musí svůj program předvést, vysvětlit jeho funkci,
případně být schopen ho v reálném čase jednoduše modifikovat.
Hodnotí se nejen funkčnost vytvořeného programu, ale i to, jak je program navržen a naprogramován.
Není při tom vyžadována (časová) optimalizace algoritmu - stačí, není-li algorimus "vysloveně hloupý".
Vzhledem k omezenému času se nepožaduje, aby byl program komentován (i když komentáře
vytvářené současně s programemem mohou práci na programu podstatně zjednodušit).
Spolu s programem musí student předat zkoušejícímu i dostatečný počet testovacích dat
(pokud je vstup/výstup
programu ze/do souboru pak tyto soubory na disku, pokud program komunikuje z konzole, pak papír,
na který opsal
vyzkoušené vstupy a jim odpovídající výstupy), na kterých funkčnost programu testoval.
Součástí hodnocení výkonu studenta je i návrh testovacích dat. Data by měla program
vyzkoušet jak v typických tak i v anomálních situacích. Správnost výsledku by měla být nějak jednoduše
a na programu nezávisle ověřitelná.
Při návrhu programu myslete na to, aby jeho spuštění netrvalo zbytečně dlouho.
Pokud je např. při každém spuštění programu zadat 20 čísel z klávesnice,
můžete tak při opakovaném spuštění programu ztratit neúnosně mnoho času.
Pokud zkoušející zjistí, že předávaný program nefunguje správně, může studentovi dát možnost
program opravit, zpravidla však student nedostane takovou možnost více než jednou.
Při práci na testu nejsou povoleny žádné pomůcky.
Případné potřebné informace o detailech programovacího jazyka student může zjistit z helpu Borland Pascalu.
Pro úspěšné složení testu jsou potřeba m.j. následující znalosti:
- Znalost programovacího jazyka Pascal, resp. Borland Pascal v rozsahu:
jednoduché a strukturované datové typy (čísla, znaky, typ boolean, pole, záznamy, množiny, znakové řetězce),
jednoduché a strukturované příkazy (:=, if, while, repeat, for, case, with),
práce s textovými soubory, procedury a funkce, separátní překlad a programové jednotky - unity,
lokalita identifikátorů, předávání parametrů, rekurze.
- Aktivní znalost integrovaného prostředí Borland Pascal verze 7.0.
(editor, překlad, výpočet, trasování, breakponty, sledování hodnot proměnných (watches) atd.).
- Ovládnutí konkrétních jednoduchých algoritmů a programovacích technik, např. :
- Eukleidův algoritmus
- Eratosthenovo síto
- Hornerovo schéma
- práce v pozičních číselných soustavách
- aritmetika s vyšší přesností ("dlouhá čísla")
- algoritmy vyhledávání v poli (binární, zarážka)
- maticové operace a jejich implementace
- použití rekurze
- backtracking (prohledávání do hloubky)
- algoritmus vlny (prohledávání do šířky)
- konstrukce minimální ekvivalence zadané (některými) dvojicemi ekvivalentních prvků
Na znalost jazyka či konkrétních algoritmů můžete být při praktickém testu tázáni
pouze v souvislosti s řešenou úlohou.
Na praktický test i na zkoušku se studenti zapisují ve fakultním informačním systému.
Přečtěte si podrobnější pokyny pro přihlašování.
Písemná část a ústní část zkoušky
Písemná část a ústní část zkoušky se konají zpravidla v jeden den. Klasifikují se společně.
Jak již bylo řečeno, klasikaci může ovlivnit i informace o velmi dobrém či nepříliš dobrém praktickém testu.
Písemná část zkoušky
Studenti mají během 50 minut vyřešit jednodnochou úlohu na práci s ukazateli
a spojovými datovými strukturami. Úlohy nejsou algoritmicky náročné.
Ústní část
V ústní části zkoušky se požadují znalosti programovacího jazyka a algoritmů podle
níže uvedeného seznamu.
Tento seznam bude upřesněn do konce prosince, kdy bude jasné,
co skutečně odpředneseme. Nic podstatného do něj však nepřibyde,
může dojít nanejvýš k přesnějšímu vymezení jednotlivých okruhů.
Na předtermínech platí požadavky v této verzi.
- Programovací jazyk Pascal
(implementace Borland Pascal - nejde přitom o detaily, ale o principy)
- datové typy a reprezentace jejich hodnot v paměti
rozdíl mezi typem integer a real, pole, záznam, záznam s variantami, znakový řetězec,
množina, výčtový typ, inicializované proměnné (strukturované konstanty)
- předávání parametrů podprogramům
předávání parametrů hodnotou a
odkazem (princip, rozdíly, použití), procedurální parametry
- rekurze
přímá a nepřímá rekurze,
direktiva forward, výhody a nevýhody použití rekurze
- práce s textovými soubory
assign, různé způsoby otevření souboru - reset, rewrite, append,
formátování textového výstupu
- modularita
unity, interfaceová a
implementační část, uses, překlad Make a Build, standardní unity
- staticky a dynamicky alokované proměnné
obsazení paměti a paměťová omezení, typ ukazatel, konstanta
nil, způsoby alokace a uvolňování dynamicky alokovaných proměnných (New –
Dispose, GetMem – FreeMem, Mark - Release)
- Algoritmy a programovací techniky
- efektivita algoritmů
asymptotická složitost, nejlepší, průměrný a
nejhorší případ, konkrétní odhady složitosti jednoduchých algoritmů, složitost
problému
- rekurze
rekurzivní formulace
algoritmů, efektivita rekurzivních programů a její zvyšování, odstranění
rekurze použitím zásobníku
- prohledávání do hloubky a do šířky
backtracking, algoritmus vlny,
ořezávání, heuristiky
- dynamické programování, metoda "rozděl a panuj”
princip metod, příklady použití
- vnitřní třídění
konkrétní třídicí algoritmy a horní odhad jejich složitosti
- třídění přímým výběrem, přímé zatřiďování, bublinkové třídění,
quicksort, třídění sléváním, heapsort
- lineární spojové seznamy
různé typy seznamů - obousměrné, s hlavou, cyklické, základní operace se seznamy,
implementace zásobníku a fronty, práce s dlouhými čísly a polynomy
- stromy
binární stromy, obecné stromy a
jejich různé reprezentace, binární vyhledávací stromy a operace s nimi,
průchody binárním stromem a jejich souvislost s algebraickými notacemi.
- aritmetické výrazy
algoritmy na vyhodnocení výrazu zapsaného v různých notacích - infix, prefix, postfix,
převody mezi různými algebraickými notacemi
- grafy
základní grafové pojmy, způsoby reprezentace grafu v programu,
programová realizace vybraných grafových algoritmů
- použití generátoru pseudonáhodných čísel
(nikoli jeho konstrukce)