======= b6b36dsa -- Datové struktury a algoritmy ======= /*[[https://cw.felk.cvut.cz/forum/forum-1769.html|Diskusní fórum]]*/ [[https://cw.felk.cvut.cz/brute/teacher/course/1320 | Brute - odevzdávací systém ]] [[http://www.fel.cvut.cz/cz/education/bk/predmety/31/30/p3130306.html|Popis předmětu na FEL]] [[https://fel.cvut.cz/cz/education/rozvrhy-ng/public/html/predmety/31/30/p3130306.html|Rozvrh na FEL]] --------------- ====== Požadavky pro absolvování předmětu ====== Abyste předmět úspěšně zakončili, musíte: 1. Získat zápočet: * přečíst (a pochopit) kapitoly (kromě sekcí označených hvězdičkou) 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 15, 17, 18 a 34 z učebnice T. Cormen et al.: Introduction to Algorithms, * vypracovat 4 domácí úkoly (viz [[courses:b6b36dsa:ukoly:start|popis domácích úkolů]]), * případně získat body za aktivitu, * projít dvěma testy v semestru (body se Vám budou počítat u zkoušky) a 2. Úspěšně absolvovat kombinovanou (tzn. písemnou + ústní) zkoušku. Celkové hodnocení se spočítá jako součet bodů za zkoušku (až 50 bodů), bodů za testy v semestru (až 20 bodů), bodů za domácí úkoly (12 až 24 bodů) a případných bodů za aktivitu (až 6 bodů). Stupnice pro známky není určena striktně, vychází z poměrného hodnocení, aby se zohlednily rozdíly mezi těžšími a lehčími příklady, které se ve zkouškovém testu vyskytly. Pokud Vám Vaše hodnocení nevyhovuje, můžete se přihlásit na ústní zkoušku, musíte ale počítat s tím, že Vám ústní zkouška může známku vylepšit, ale i zhoršit. Pro hodnocení A,B a E je ústní zkouška zpravidla povinná. Pro hodnocení A je nutno získat za domácí úkoly alespoň 20 bodů. Upozornění: Počítejte s tím, že strategie získávání bodů musí být soustavné řešení úkolů. Pokud si necháte jejich řešení na konec semestru, je možné, že je nestačíte splnit a to nebudeme při rozhodování o získání zápočtu brát v úvahu. ====== Přednášky ====== ===== Plán přednášek LS 2021/2022 ===== ^ Týden ^ Datum ^ Téma ^ Průsvitky ^ | **1.** | 18.2. | Úvod do problematiky. | {{:courses:b6b36dsa:dsa-1-úvod.pdf|01}} | | **2.** | 25.2. | Techniky návrhu algoritmů. | {{:courses:b6b36dsa:DSA-2-TechnikyNávrhuAlgoritmů.pdf|02}} | | **3.** | 4.3. | Složitost algoritmů. | {{:courses:b6b36dsa:DSA-3-SložitostAlgoritmů.pdf|03}} | | **4.** | 11.3. | Základy řazení. | {{:courses:b6b36dsa:DSA-4-Řazení.pdf|04}} | | **5.** | 18.3. | Pokročilé řazení. | {{:courses:b6b36dsa:DSA-7-PokrocileRazeni.pdf|05}} | | **6.** | 25.3. | Randomizované algoritmy. | {{:courses:b6b36dsa:DSA-5-Randomized.pdf|06}} | /* {{:courses:b6b36dsa:DSA-5a-Priklady.pdf| Příklady }} */ | **7.** | 1.4. | **1.Test** | {{:courses:b6b36dsa:1-test-2018-04-06-reseny.pdf | příklad a řešeni}} | | **8.** | 8.4. | Abstraktní datové typy I. | {{:courses:b6b36dsa:DSA-8-AbstrakniDatoveTypy.pdf | 08}} | | **9.** | 15.4. | //Odpadá, svátek// | -- | | **10.** | 22.4. | Abstraktní datové typy II. Stromy | {{:courses:b6b36dsa:DSA-9-AbstraktniDatoveTypyII.pdf | 10a}} {{:courses:b6b36dsa:DSA-9-Stromy.pdf | 10b}} | | **11.** | 29.4. | Vyhledávání. B-stromy. | {{:courses:b6b36dsa:DSA-10-vyhledavani.pdf |11a}} {{:courses:b6b36dsa:DSA-11-PokrocileVyhledavani.pdf |11b}} | | **12.** | 6.5. | Dynamické programování. | {{:courses:b6b36dsa:DSA-12-DynamickeProgramovani.pdf|13}} | | **13.** | 13.5. | **2.Test** | {{:courses:b6b36dsa:2-test-2018-05-11-reseny.pdf| příklad a řešeni}} | | **14.** | 20.5. | NP-úplnost a ostatní. | {{:courses:b6b36dsa:DSA-13-NP-Uplnost.pdf|14}} | ===== Domácí úkoly ===== Během semestru budou zadány 4 domácí úkoly. Zadání úkolů je vyvěšeno na stránkách předmětu a budou se odevzdávat do odevzdávacího systému (BRUTE), kde budou automaticky hodnoceny. Pro získání zápočtu je nutné úspěšně a včas odevzdat všechny domácí úkoly (a získat alespoň 3 body z každého). Úlohy je třeba odevzdat v každém případě. Pozdní odevzdání bude penalizováno. Upozornění: práce na domácích úkolech je samostatná. Studenti, kterým odhalíme duplicitní řešení, automaticky ztrácí nárok na zápočet a hrozí jim disciplinární řízení. Samozřejmě je normální (a žádoucí) o domácích úlohách diskutovat s kolegy, nicméně kód si musí každý napsat sám. Další informace o domácích úkolech najdete v sekci [[courses:b6b36dsa:ukoly:start|Domácí úkoly]]. ===== Testy v semestru ===== Tento rok se budou psát dva testy v semestru. Oběma musíte projít, jinak ztrácíte nárok na zápočet. Celkový počet příkladů vyřešených v testech v semestru se zohledňuje při zkoušce. Každý test můžete opakovat pouze jednou! Pokud neuspějete u obou testů tak ztrácíte nárok na zápočet. ==== První test ==== První test v semestru se bude psát na přednášce v pátek dle aktuální situace. Bude mít pět příkladů hodnocených 0-2 body (2 body - zcela správně, 1 bod - částečně správně). Na úspěšný průchod bude potřeba získat alespoň 6 bodů. Pokrývá následující témata: * Rekurze * Asymptotická složitost kódu * Množiny omikron, omega a theta * Správnost kódu, invarianty * Složitost algoritmů Zadání a stručný náznak řešení {{:courses:b6b36dsa:1-test-2018-04-06-reseny.pdf | příklad a řešeni}} ==== Druhý test ==== Druhý test v semestru se bude psát na přednášce dle aktuální situace. Opět bude mít pět příkladů hodnocených 0-2 body (2 body - zcela správně, 1 bod - částečně správně). Na úspěšný průchod bude potřeba získat alespoň 6 bodů. Témata příkladů: * Randomizované algoritmy * Důkaz pomocí matematické indukce (např. důkaz funkčnosti procedury Partition začínající v učebnici na straně 171), * Kombinatorika, pravděpodobnost (např. výpočet složitost bucket sortu začínající v učebnici na straně 202), * Formalizace přirozeného jazyka (např. definice výběru n-tého prvku (selection problem) v učebnici na straně 213), * Počítání (např. analýza počtu kroků řazení vkládáním začínající v učebnici na straně 26) a * Programování (zjevné, doporučujeme zopakovat si zejména práci se spojovými strukturami). Částečné zadání a řešení {{:courses:b6b36dsa:2-test-2018-05-11-reseny.pdf | příklad a řešeni}} ===== Materiály ===== [[http://ressources.unisciel.fr/algoprog/s00aaroot/aa00module1/res/%5BCormen-AL2011%5DIntroduction_To_Algorithms-A3.pdf|Cormen Thomas H. et al.: Introduction to Algorithms, 3rd Edition, MIT Press, 2009]] Pro rychlé přiblížení lze použít i zdroj: [[https://www.albatrosmedia.cz/tituly/16513034/algoritmy/ | Wróblewski Piotr: Algoritmy, Computer Press, ISBN: 978-80-251-4126-7, 2015]] Terminologii ale používáme dle Cormena. ==== Další odkazy ==== Odkaz na stránky předmětu Introduction to Algorithms z Open Courseware MIT [[https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures | Introduction to Algorithms on MIT ]] Odkaz na stránky předmětu Introduction to Algorithms z Open Courseware MIT (2011) [[https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/ | Introduction to Algorithms on MIT (2011) ]]