[[https://www.fel.cvut.cz/cz/education/rozvrhy-ng.B201/public/html/predmety/46/82/p4682306.html|Rozvrh na FEL]] [[https://www.fel.cvut.cz/cz/education/rozvrhy-ng.B201/public/html/paralelky/P46/82/par4682306.1.html|Posluchači ALG]] [[https://cw.felk.cvut.cz/brute/|Odevzdávací systém BRUTE]] [[https://cw.felk.cvut.cz/forum/forum-1671.html|Diskusní fórum]] ====== ALG - cvičení ====== ===== Provoz v semestru ===== **Distanční výuka**\\ Výuka od 21. září do odvolání bude probíhat distančně pomocí nástroje Big Blue Button. Před každým cvičením obdržíte na email odkaz, pomocí nějž se připojíte. Do zlepšení situace nebude studentům umožněn vstup do budov ČVUT s výjimkou kolejí a menz. Prezence v době distanční výuky bude nahrazena odevzdáváním úloh ze cvičení vypracovaných v malých skupinkách (nebo i jednotlivě). Pravidla pro vypracovávání skupinových prací ze cvičení: ^ Paralelka ^ Podmínky ^ Vypracovat úlohy ^ Termín odevzdání ^ | 105 | Práce v 1-4členných skupinách | dořešte stavbu {{:courses:b4b33alg:obvs.jpg?linkonly|optimálního BVS}} (příklad 13b), poslední odrážku úlohy 19 z [[https://cw.fel.cvut.cz/b201/_media/courses/a4b33alg/cvi11.pdf|Prezentace 11]] a úlohy 15a a 15b z [[https://cw.fel.cvut.cz/b201/_media/courses/a4b33alg/cvi12.pdf|Prezentace 12]] | 16. 12. 23:59 [[mailto:peckama2@fel.cvut.cz?subject=ALG%20reseni|e-mailem]] | **Programovací úlohy**\\ Semestr obsahuje 8 domácích programovacích úloh sumárně ohodnocených 24 body, z čehož je k získání zápočtu nutno získat alespoň 13 bodů. Úlohy jsou zadávány a řešení vyhodnocována prostřednictvím [[https://cw.felk.cvut.cz/brute//|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. * Akceptované řešení úlohy je takové, které správně spočte výsledky na alespoň 8 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. * Úlohy lze odevzdat i po termínu, za každý započatý týden prodlení je však při hodnocení odečten jeden bod. * Individuálně se lze domlouvat o posunutí termínu s předstihem v odůvodněných případech (nemoc, zahraniční cesta apod). * Otázky týkající se domácích uloh i dalších událostí během semestru je vhodné řešit pomocí [[https://cw.felk.cvut.cz/forum/forum-1671.html|diskusního fóra ALG]]. **Termíny a hodnocení domácích úloh **\\ zadání -- odevzdání 1. 25.9. -- 18.10. ( Asymptotic complexity ) 2. 9.10. -- 1.11. ( Recursion/Backtrack ) 3. 16.10. -- 8.11. ( Tree search ) 4. 30.10. -- 22.11. ( Graph search ) 5. 6.11. -- 29.11. ( BST processing ) 6. 13.11. -- 13.12. ( Divide and conquer ) 7. 27.11. -- 27.12. ( Dynamic Programming ) 8. 11.12. -- 10.1. ( Dynamic Programming ) Správně spočtených 10 z 10 testovacích případů ... 3 body Správně spočtených 9 z 10 testovacích případů ... 2 body Správně spočtených 8 z 10 testovacích případů ... 1 bod Správně spočtených 7 nebo méně testovacích případů ... 0 bodů Pozdní odevzdání ... -1 bod za každý započatý týden zpoždění. V BRUTE u úloh vidíte počet správně vyřešených zadání (minus penalizaci za pozdní odevzdání), ne finální počet bodů podle výše uvedeného přepočtu. Finální počet bodů za úlohu spočítáme až u zkoušky, a je roven max(0, body v BRUTE - 7). **Zápočet**\\ Kromě minima 13 z možných 24 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: [[help:common:plagiaty_opisovani| Plagiáty]].\\ **Upload systém**\\ Komunikace s upload systémem je popsána v oddílu [[courses:b4b33alg:upload_system| 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í -- {{:courses:a4b33alg:cviceni_-_slozitost_-_tabulka.pdf| pdf}} \\ ^ Cvičení ^ Prezentace I ^ Prezentace II ^ Kódy ^ Další materiály ^ | **1.** | {{:courses:a4b33alg:cviceni01upd.pdf| pdf}} | | | {{:courses:b4b33alg:alg_seminar_00_answers_and_simulations.pdf| s pár řešeními}} | | **2.** | {{:courses:a4b33alg:cviceni02upd.pdf|pdf}} | {{:courses:a4b33alg:cviceni1resene.pdf|pdf}} | | {{:courses:a4b33alg:a4b33alg_s01_solutions.pdf| řešené příklady}} | | **3.** | {{:courses:a4b33alg:cviceni03upd.pdf| pdf}} | {{:courses:a4b33alg:cviceni2resene.pdf| pdf}} | | | | **4.** | {{:courses:a4b33alg:cviceni04upd.pdf| pdf}} | {{:courses:a4b33alg:cviceni3resene.pdf| pdf}} | {{:courses:a4b33alg:cviceni3code.zip| zip}} | [[https://drive.google.com/file/d/0BzquKNBhMIVuMlE5OXRCYnVNMVk|kódy cv. po 11:00]]| | **5.** | {{:courses:a4b33alg:cv05stromgrafnosol.pdf|pdf2}} | {{:courses:a4b33alg:cviceni4resene.pdf| pdf}} | {{:courses:a4b33alg:cviceni4problem5.zip| zip}} | [[http://akidsheart.com/math/mathgames/leapfrog.htm|simulace 1]], [[http://www.learn4good.com/games/puzzle/boat.htm|simulace 2]], {{:courses:a4b33alg:a4b33alg_s04_collections1.pdf|kolekce}}, [[https://drive.google.com/file/d/0BzquKNBhMIVucTR2cTUzV1FORmc/view|kódy cv. po 11:00]] | | **6.** | {{:courses:a4b33alg:cviceni07upd.pdf|pdf}}, {{:courses:a4b33alg:cviceni_05.pdf|pdf}} | {{:courses:a4b33alg:cviceni5resene.pdf| pdf}} | {{:courses:a4b33alg:cviceni5code.zip| zip}} |[[https://drive.google.com/file/d/1FC-c9nUnRNhSBF_bVsdkMZzKCjsJDRP4/view|kódy cv. út 12:45, 16:15]] | | **7.** | {{:courses:a4b33alg:cv06_2017_avl.pdf| pdf }} {{:courses:b4b33alg:cv06_2017_avl.pptx| pptx }} | {{:courses:a4b33alg:cviceni7resene.pdf| pdf}} | {{:courses:a4b33alg:cviceni7code.zip| zip}}, {{:courses:a4b33alg:tree.java|řešeni}} | | | **8.** | {{:courses:a4b33alg:cviceni05upd.pdf| pdf}} | {{:courses:a4b33alg:cviceni8resene.pdf| pdf}} | {{:courses:a4b33alg:cviceni8code.zip| zip}}, {{:courses:b4b33alg:cv8.py| python}} | | | **9.** | {{:courses:a4b33alg:cviceni_09x.pdf| pdf}} a {{:courses:a4b33alg:cviceni_10x.pdf| pdf}} a {{:courses:a4b33alg:cv10sorty3.docx| docx }} | {{:courses:a4b33alg:cviceni9.pdf| pdf}} | {{:courses:b4b33alg:cv9.py| python}} | | | **10.** | {{:courses:a4b33alg:cv10.pdf| pdf}}, rozšířená v {{:courses:a4b33alg:cv10.doc| doc.}} | {{:courses:a4b33alg:cviceni10resene.pdf| pdf}} | {{:courses:a4b33alg:cviceni10code.zip| zip}}, {{:courses:a4b33alg:dynamicprogramming.java|řešeni}} | | | **11.** | {{:courses:a4b33alg:cvi11.pdf| pdf}} plus {{:courses:a4b33alg:protosli11.docx| protoslidy}} | {{:courses:a4b33alg:cviceni11.pdf| pdf}} | {{:courses:a4b33alg:main.java| DP pro LCS}} | | | **12.** | {{:courses:a4b33alg:cvi12.pdf| pdf}} | | **13.** | {{:courses:a4b33alg:cviceni_12.pdf| pdf}} | {{:courses:a4b33alg:cviceni12resene.pdf| pdf}} | {{:courses:b4b33alg:hashmaps.py| kódy zřetězeného hashování}} | | | **14.** | TBD | ===== Referenční řešení domácích úloh ===== - {{ :courses:b4b33alg:boats.java |boats.java}} - {{ :courses:b4b33alg:agents.java |agents.java}} - {{ :courses:b4b33alg:univnet.java |univnet.java}} - {{ :courses:b4b33alg:robocom.java |robocom.java}} ===== Úlohy k procvičování a zkoušce ===== **Řád růstu funkcí a asymptotická složitost**\\ Bez řešení {{:courses:a4b33alg:a_complex_alg_unsol.pdf|}} a s řešením {{:courses:a4b33alg:a_complex_alg.pdf|}} \\ **Rekurze**\\ Bez řešení {{:courses:a4b33alg:b_recur_alg_unsol.pdf|}} a s řešením {{:courses:a4b33alg:b_recur_alg.pdf|}}\\ **Stromy, průchod stromy**\\ Bez řešení {{:courses:a4b33alg:c_treestq_alg_unsol.pdf|}} a s řešením {{:courses:a4b33alg:c_treestq_alg.pdf|}} \\ **Vyhledávací stromy**\\ Bez řešení {{:courses:a4b33alg:d_bst_avl_b_alg_unsol.pdf|}} a s řešením {{:courses:a4b33alg:d_bst_avl_b_alg.pdf|}} \\ **Řazení**\\ Bez řešení {{:courses:a4b33alg:e_sort_alg_unsol.pdf|}} a s řešením {{:courses:a4b33alg:e_sort_alg.pdf|}} \\ **Hash (rozptylovací tabulky)**\\ Bez řešení {{:courses:a4b33alg:f_hash_alg_unsol.pdf|}} a s řešením {{:courses:a4b33alg:f_hash_alg.pdf|}} \\ **Dynamické programování**\\ Bez řešení {{:courses:a4b33alg:g_dynpgm_alg_unsol.pdf|}} a s řešením {{:courses:a4b33alg:g_dynpgm_alg.pdf|}} \\