[[http://www.fel.cvut.cz/cz/education/rozvrhy-ng.B172/public/html/predmety/12/57/p12579904.html|Rozvrh na FEL]] [[https://www.fel.cvut.cz/cz/education/rozvrhy-ng.B172/public/html/paralelky/P12/57/par12579904.1.html|Posluchači ALG]] [[https://cw.felk.cvut.cz/brute/|Odevzdávací systém BRUTE]] [[https://cw.felk.cvut.cz/forum/forum-1489.html|Diskusní fórum]] V letním semestru 2017/2018 jsou přednášky a cvičení organizovány společně s předmětem [[https://cw.fel.cvut.cz/wiki/courses/b6b36dsa/start| DSA (odkaz)]]. \\ Domácí úlohy, zápočet a zkouška probíhají podle pravidel ALG popsaných na těchto stránkách ALG. ====== Zkouška ====== **Termíny a místa konání** \\ Zapisujte se do rozpisu zkoušek, nezapisujte se do KOSu. [[https://docs.google.com/spreadsheets/d/1G4uoUc_YGmJ3_YGH_nqCxttvPO4OSfnVr3WvbD_nBcY/edit?usp=sharing| 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 ---- ==== Témata LS 2018, společná s DSA ==== ([[https://cw.fel.cvut.cz/wiki/courses/b6b36dsa/start|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\\