Zkouška

Termíny a místa konání

Zapisujte se do rozpisu zkoušek, nezapisujte se do KOSu.

Rozpis zkoušek

Organizace

Zkouška má teoretickou část a praktickou programovací část.
V teoretické části obdrží adept několik otázek a připraví si na ně písemnou osnovu odpovědi, případně odpověď detailnější, pokud to konkrétní otázka vyžaduje. Své odpovědi probrere s examinátorem, který určí konečné hodnocení. Na každou otázku je nutno odpovědět s alepoň 50% úspěšností. Kdo na některou otázku odpoví s menší než 50% úspěšností, dostane otázku doplňující, kterou musí zodpovědět převážně správně. Když se mu to podaří, je jeho odpověď na původní otázku hodnocena jako úspěšná z 50%. Jinak je celá teoretická část hodnocena jako neúspěšná.
V teoretické části nelze požívat žádné další materiály, tištěné ani elektronické.

V praktické části řeší adept jednu úlohu podobným způsobem jako semestrální programovací úlohy. Úloha má 10 testovacích souborů a adeptovo řešení musí fungovat správně a dostatečně rychle alespoň na 5 z nich. Zkouška trvá 4 hodiny, první půlhodina je povinně vyhrazena vlastní analýze úlohy, programovat lze pak začít až po uplynutí 30 minut od začátku zkoušky.
V praktické části (a pouze v ní) je povoleno používat přinesené tištěné nebo elektronické materiály. Věnujte své přípravě na tuto část zkoušky patřičnou pozornost a uvažte, co všechno můžete potřebovat během analýzy a kódování úlohy, vyhnete se tak nadbytečnému stresu při zkoušce.

Postupná účast
Posluchači mohou chodit na teoretickou a praktickou část zkoušky v různých dnech, obě části nejsou spolu časově vázány. Celkově ale platí pravidlo o maximálně dvou nebo třech termínech zkoušky, to jest každý posluchač se může účastnit nejvýše dvou nebo tří termínů teoretické části a dvou nebo tří termínů praktické části. O počtu dvou nebo tří možných termínů se rozhoduje individuálně podle stávajících studijních předpisů (článek 10, odst. 4. Studijního a zkušebního řádu ČVUT).

Obsluha počítače a dalších zařízení během praktické části zkoušky

• Každý účastník pracuje na vlastním přineseném počítači, automatická provozuschopnost školních počítačů, pokud v učebně budou, není zaručena, je nutno ji domluvit předem s alespoň týdenním předstihem.
• Během prvních dvou hodin zkoušky musí být počítač odpojen od všech sítí.
• Při práci s počítačem mohou být spuštěny pouze následující aplikace: Souborový manažer, vývojové prostředí (Eclipse, Netbeans, IntelliJ, apod.) případně samostatný překladač a debugger, prohlížeč pdf/doc souborů, systémová konzole, textový editor při práci v C/C++, kalkulačka.
• Dále může být (a pro odevzdávání musí být) spuštěn webový prohlížeč. Ve webovém (a rovněž pdf/doc apod.) prohlížeči lze zobrazovat pouze lokální stránky na disku/discích vlastního počítače a dále pouze stránky a informace z domény cw.felk.cvut.cz/upload/, to jest obsah stránek se školním upload systémem.
• Jiné aplikace, které mohou mít indviduální podpůrný charakter (např. tabulkový kalkulátor, grafický editor apod.), lze spouštět pouze po konzultaci a schválení examinátorem.
• Mobilní telefony a další výpočetní prostředky kromě vlastního počítače musí být během zkoušky vypnuty.
• Během zkoušky nelze poslouchat reprodukovanou hudbu nebo se připojovat na zvukový výstup počítače nebo jiného zařízení.
• Během zkoušky je k dispozici učitelský počítač, kde lze po domluvě v individuálních případech dohledávat případné nutné informace na webu, např. podrobnosti o nejasných chybových hlášeních překladače/GUI, apod.
• Kromě dohodnutých výjimek nelze spouštět na vlastním stroji další aplikace mimo zde uvedené či na místě dohodnuté, nelze prohlížet jiné webové stránky, importovat informace z webu nebo obsluhovat jiná výpočetní zařízení. Překročení těchto mantinelů bude chápáno jako pokus o obcházení pravidel zkoušky a bude postihováno podle uvážení examinátorů, přinejmenším však ztrátou termínu zkoušky.

Dodatečná minimální náprava
Kdo neuspěje v praktické části zkoušky a potom dodatečně doma zjistí, že nezdar byl způsoben triviální chybou v rozsahu cca 1-2 řádků kódu, například přehlédnutou opačnou nerovností v kritickém místě, chybou +/-1 v indexaci pole, nepřesnou inicializací apod., může většinou dodatečně uspět s určitou menší penalizací. Nutnou podmínkou úspěchu v takovém případě je, aby byl chybný kód odevzdán do upload systému před koncem zkoušky a aby oprava byla triviální rozsahem i koncepcí. Opravený kód musí fungovat a splňovat ostatní pravidla zkoušky. Examinátor pak rozhodne o finálním výsledku této části zkoušky.

Bodování a klasifikace
Sčítají se body získané za řešení domácích úloh v semestru, za programovací část a za teoretickou část zkoušky.
1. Ze semestru je nutno získat alespoň 8 bodů za domácí programovací úlohy.
2. Z programovací části zkoušky je nutno získat alespoň 5 bodů z maximálně možných 10, počet bodů odpovídá počtu správně zpracovaných testovacích souborů.
3. Z teoretické části zkoušky je nutno získat alespoň 8 bodů z maximálně možných 16, examinátor jednotlivé otázky interně ohodnotí vhodným počtem bodů a podle toho ocení výkon adepta.

 
Výsledné body  Známka  
=============  ======
      < 21 b.    F 
21 b. - 25 b.    E 
26 b. - 30 b.    D  
31 b. - 34 b.    C 
35 b. - 38 b.    B 
39 b. - 42 b.    A

(DSA)

Základní diskrétní posloupnosti a řady
Základní kombinatorika
Důkaz indukcí

řád růstu funkce, asymptotická složitost , O-Theta-Omega notace
Složitost rekurzivních algoritmů, strom rekurze, Substituční metoda, Master theorem (česky Mistrovská metoda či také Mistrovská věta)

Rekurze
Technika „rozděl a panuj“

Zásobník (Stack)
Fronta (Queue)

Strom
průchody I norder, Preorder Postorder
Orientované a neorientované grafy, jejich reprezentace v počítači

Binární hledání (Binary-Search)
Interpolační vyhledávání
binární vyhledávací strom (BVS)
AVL strom (AVL tree)
B-stromy (B-trees)

Halda

Stabilita řazení
Řadící algoritmy: Insert-Sort, Selection-Sort, Quick-Sort, Merge-Sort, Heap-Sort, Radix-Sort, Counting-Sort

Rozptylování - Hashing

Algoritmy Dynamického programování : Řetězové násobení matic, Optimální binární vzhledávací strom, Nejdelší společná podposloupnost