Warning
This page is located in archive. Go to the latest version of this course pages.

Rozvrh na FEL Posluchači ALG Odevzdávací systém BRUTE Diskusní fórum

ALG - cvičení

Provoz v semestru

Programovací úlohy
Semestr obsahuje 8 domácích programovacích úloh sumárně ohodnocených 16 body, z čehož je k získání zápočtu nutno získat alespoň 8 bodů. Úlohy jsou zadávány a řešení vyhodnocována prostřednictvím odevzdávacího systému BRUTE.

  • Každá úloha implementuje některé téma přednášky, toto téma může být pouze dílčí částí úlohy. K řešení může být někdy vhodné nastudovat samostatně některý z dalších běžných algoritmů neprobíraných v přednáškách ALG (např. minimální kostry, nejkratší cesty apod.)
  • Akceptované řešení úlohy je takové, které správně spočte výsledky na alespoň 9 z 10 testovacích souborů.
  • Řešení musí být také efektivně naprogramováno, každý datový soubor má stanovený časový limit, do nějž musí být data zpracována a vypsán výsledek. Limit je většinou dvojnásobek času, za který soubor zpracuje autorské referenční řešení v Javě. Limit se zaokrouhluje nahoru na celé sekundy, typicky nepřekračuje 5-10 vteřin.
  • Termíny úloh je třeba dodržet, lze je prodloužit pouze individuálně v odůvodněných případech (nemoc, zahraniční cesta apod).
  • Individuálně se lze domlouvat o posunutí termínu, když o to student s předstihem požádá.
  • Otázky týkající se domácích uloh i dalších událostí během semestru je vhodné řešit pomocí diskusního fóra ALG.

Termíny a hodnocení domácích úloh

   zadání -- odevzdání         
1.   6.10. -- 26.10.   ( Asymptotic complexity )       
2.  13.10. --  2.11.   ( Recursion/Backtrack )       
3.  27.10. -- 16.11.   ( Graph search )       
4.   3.11. -- 23.11.   ( Graph search )       
5.  10.11. -- 30.11.   ( BST processing )       
6.  17.11. -- 6.12.    ( AVL processing )     
7.   8.12. --  4.1.    ( Dynamic Programming )      
8.  15.12. -- 11.1.    ( Dynamic Programming )
         
Správně spočtených 10 z 10 testovacích případů     ... 2 body
Správně spočtených 9 z 10 testovacích případů      ... 1 bod
Správně spočtených 8 nebo méně testovacích případů ... 0 bodů

Zápočet
Kromě minima 8 z možných 16 bodů za řešení úloh je ke získání zápočtu nezbytná pravidelná docházka do cvičení s max. 2 neomluvenými absencemi. Předpokládáme, že posluchači se vyvarují odevzdávání plagiátů a seznámí se s pravidly uvedenými na společné stránce: Plagiáty.

Upload systém
Komunikace s upload systémem je popsána v oddílu Upload System.
Každou úlohu doprovází sada neveřejných testovacích souborů a sada veřejných souborů se správnými výsledky. Veřejné soubory jsou uloženy v odevzdávacím systému a systém spouští řešitelovu úlohu pokaždé rovněž na těchto datech a vrací řešiteli kompletní výstup jeho řešení na STDOUT a STDERR pro každý veřejný soubor. Veřejné soubory jsou součástí zadání úlohy a jejich obsah je podobný obsahu testovacích souborů a poskytuje tak další příležitost k účinnému ladění. Počet testovacích a veřejných souborů není pevně určen a pro různé úlohy se může lišit, zejména veřejné soubory mohou z trénovacích důvodů zcela chybět.

Materiály na cvičení

Tabulka s porovnáním složitostí – pdf

Cvičení Prezentace I Prezentace II Kódy Další materiály
1. pdf pdf jednoduché pomocné výpočty: pdf, řešené příklady
2. pdf pdf
3. pdf pdf zip kódy cv. út 12:45, st 9:15
4. pdf2 pdf zip simulace 1, simulace 2, kolekce, kódy cv. út 12:45
5. pdf, pdf pdf zip kódy cv. út 12:45, pá 12:45
6. pdf pptx pdf zip, řešeni
7. pdf pdf zip
8. pdf a pdf a docx pdf
9. Není přednáška, opakování témat 1.-5. Některé náměty: zde, pdf
10. pdf, rozšířená v doc. pdf zip, řešeni
11. pdf plus protoslidy pdf DP pro LCS
12. pdf
13. Odpadá - rektorský den
14. pdf pdf

Úlohy k procvičování a zkoušce

Řád růstu funkcí a asymptotická složitost
Bez řešení a_complex_alg_unsol.pdf a s řešením a_complex_alg.pdf
Rekurze
Bez řešení b_recur_alg_unsol.pdf a s řešením b_recur_alg.pdf
Stromy, průchod stromy
Bez řešení c_treestq_alg_unsol.pdf a s řešením c_treestq_alg.pdf
Vyhledávací stromy
Bez řešení d_bst_avl_b_alg_unsol.pdf a s řešením d_bst_avl_b_alg.pdf
Řazení
Bez řešení e_sort_alg_unsol.pdf a s řešením e_sort_alg.pdf
Hash (rozptylovací tabulky)
Bez řešení f_hash_alg_unsol.pdf a s řešením f_hash_alg.pdf
Dynamické programování
Bez řešení g_dynpgm_alg_unsol.pdf a s řešením g_dynpgm_alg.pdf

courses/b4b33alg/cviceni.txt · Last modified: 2017/11/10 11:16 by kuncvlad