[[http://www.feld.cvut.cz/cz/education/rozvrhy-ng.B231/public/html/predmety/46/82/p4682306.html|Rozvrh na FEL]] [[https://fel.cvut.cz/cz/education/rozvrhy-ng.B231/public/html/predmety/46/82/fsl-p4682306.html|Posluchači ALG]] [[https://cw.felk.cvut.cz/brute/|Odevzdávací systém BRUTE]] [[https://cw.felk.cvut.cz/forum/forum-1851.html|Diskusní fórum]] ====== ALG - cvičení ====== ===== Provoz v semestru ===== **Podmínky zápočtu**\\ Kromě minima 12 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]].\\ **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ň 12 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-1851.html|diskusního fóra ALG]]. * Odevzdávání a vyhodnocování úloh v brute lze si vykoušet a nacvičit pomocí jednoduché, cvičné a [[https://cw.felk.cvut.cz/brute/data/ae/release/2021z_b4b33alg/alg_cz_2021z/evaluation/input.php?task=trivialtraining|neklasifikované úlohy]]. Řešitelé obeznámení s brute mohou tuto úlohu klidně vynechat. **Termíny a hodnocení domácích úloh **\\ zadání -- odevzdání 1. 29.9. -- 22.10. ( Asymptotic complexity ) 2. 13.10. -- 12.11. ( Recursion/Backtrack ) 3. 20.10. -- 19.11. ( Tree search ) 4. 27.10. -- 26.11. ( Graph search ) 5. 3.11. -- 10.12. ( BST processing ) 6. 10.11. -- 17.12. ( AVL processing ) 7. 1.12. -- 31.12. ( Dynamic Programming ) 8. 8.12. -- 14.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í), ale 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). **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}} \\ FEL YouTube [[https://youtube.com/playlist?list=PLQL6z4JeTTQliSUyfcOQAFYukq2QHcS0w|playlist ALGoritmizace]] s postprocesovanými záznamy ze cvičení ZS 2021/22.\\ ^ Cvičení ^ Prezentace I ^ Prezentace II ^ Kódy ^ Další materiály (včetně VIDEO)^ | **1.** | {{:courses:a4b33alg:cviceni01upd.pdf| pdf}} | | | {{:courses:b4b33alg:alg_seminar_00_answers_and_simulations.pdf| s pár řešeními}} [[https://youtu.be/0lLlrTA30-g|ALGcvic01_priklady-TCH.mp4]] | | **2.** | {{:courses:a4b33alg:cviceni02upd.pdf|pdf}} | {{:courses:a4b33alg:cviceni1resene.pdf|pdf}} | | {{:courses:a4b33alg:a4b33alg_s01_solutions.pdf| řešené příklady}} [[https://youtu.be/LwcsxM1yWuY|ALGcvic02_ProgramatorskeOkenko_TCH102.mp4]] [[https://youtu.be/Qxlo6fsb7Ls|ALGcvic02_priklady-TCH101.mp4]] | | **3.** | {{:courses:a4b33alg:cviceni03upd.pdf| pdf}} | {{:courses:a4b33alg:cviceni2resene.pdf| pdf}} | | [[https://youtu.be/BqrCRs7VM2o|ALGcvic03_priklady-TCH101.mp4]] | | **4.** | {{:courses:a4b33alg:cviceni04upd.pdf| pdf}} | {{:courses:a4b33alg:cviceni3resene.pdf| pdf}} | {{:courses:a4b33alg:cviceni3code.zip| zip}},{{ :courses:b4b33alg:tree.java |řešení}} | [[https://drive.google.com/file/d/0BzquKNBhMIVuMlE5OXRCYnVNMVk|kódy cv. po 11:00]] [[https://youtu.be/BqrCRs7VM2o|ALGcvic04_priklady-TCH101.mp4]]| | **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]] [[https://youtu.be/NEiXHSjvy08|ALGcvic05_ProgramatorskeOkenko_TCH102.mp4]] [[https://youtu.be/7SC0-61ZBm8|ALGcvic05_priklady-TCH101a102.mp4]] | | **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]] [[https://youtu.be/wiyBC7F6NLo|ALGcvic06_priklady-TCH101.mp4]] [[https://youtu.be/q5NVo0rc8Nw|ALGcvic06_DomaciUkoly_3-4_TCH101.mp4]] | | **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}} | [[https://youtu.be/wLh2CBXcscQ|ALGcvic07_priklady-TCH101a102.mp4]] | | **8.** | {{:courses:a4b33alg:cviceni05upd.pdf| pdf}} | {{:courses:a4b33alg:cviceni8resene.pdf| pdf}} | {{:courses:a4b33alg:cviceni8code.zip| zip}}, {{:courses:b4b33alg:cv8.py| python}} | [[https://youtu.be/BMrA3L7r4MA|ALGcvic08_ProgramatorskeOkenko_TCH101.mp4]] [[https://youtu.be/oLYAXSViW_o|ALGcvic08_priklady-TCH102.mp4 ]]{{ :courses:b4b33alg:cv_opakovani_3_az_8.pdf | opakovani}} | | **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}} | [[https://youtu.be/OKkcD-1ygw4|ALGcvic09_priklady-TCH101a102.mp4]] | | **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}} | [[https://youtu.be/dZ5OuuDUmf4|ALGcvic10_priklady-TCH101a102.mp4]] [[https://youtu.be/qC2NwarIPUM|ALGcvic10a11_DomaciUkol_7_TCH101a102.mp4]] | | **11.** | {{:courses:a4b33alg:cvi11.pdf| pdf}} plus {{:courses:a4b33alg:protosli11.docx| protoslidy}} | {{:courses:a4b33alg:cviceni11.pdf| pdf}} | {{:courses:a4b33alg:main.java| DP pro LCS}} | [[https://youtu.be/eWstoAyku60|ALGcvic11_priklady-TCH101a102.mp4]] | | **12.** | {{:courses:a4b33alg:cvi12.pdf| pdf}} | | | [[https://youtu.be/V8X7m95wy3g|ALGcvic12_priklady-TCH101a102.mp4]] | | **13.** | {{:courses:a4b33alg:cviceni_12.pdf| pdf}} | {{:courses:a4b33alg:cviceni12resene.pdf| pdf}} | {{:courses:b4b33alg:hashmaps.py| kódy zřetězeného hashování}} | [[https://youtu.be/NYo7YgVr5QM|ALGcvic13_priklady-MV105.mp4]] [[https://youtu.be/nQaArLE1eas|ALGcvic13_DomaciUkoly_6a8_TCH101a102.mp4]] [[https://youtu.be/wNO4IVdLXpg|ALGcvic13_priklady-TCH102.mp4]] | | **14.** | TBD | ===== Ú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|}} \\