======= 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/1587 | 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://intranet.fel.cvut.cz/cz/education/rozvrhy-ng.B232/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ů]]), * projít písemným testem v semestru, tj. získat alespoň 10 bodů z možných 20-ti, * případně získat body za aktivitu a 2. **Úspěšně absolvovat** kombinovanou (tzn. písemnou + ústní) **zkoušku**. Podmínka absolvování zkoušky je nutná pro úspěšné absolvování předmětu, a to samozřejmě i v případě, že v průběhu semestru získáte více než 50 bodů. Na zkoušce se píše písemný test, který obsahuje několik bodovaných otázek (celkem až 40 bodů). Povinné minimum je 20 bodů. Vyhrazený čas je zpravidla 80 minut. Po odevzdání vyplněných testů je cca 1 hodina věnována na opravy a poté začíná případná ústní zkouška. K nahlédnutí budou testy a jejich výsledky. Celkové hodnocení se spočítá jako součet bodů. ^ Část ^ Maximum bodů ^ Požadované minimum ^ | [[courses:b6b36dsa:ukoly:|Domácí úkoly]] | 45 | 20 | | Kontrolní test | 20 | 10 | | Bonusové body za aktivitu | 6 | | | Písemný zkouškový test | 40 | 20 | ^ celkem ^ 111 ^ 50 ((50 bodů odpovídá hodnocení E - dostatečně.)) ^ Výsledná známka se řídí běžnou bodovou tabulkou: ^ Známka ^ Bodové rozmezí ^ Slovní \\ hodnocení ^ | A | 90 a více | výborně | | B | 80 - 89 | velmi dobře | | C | 70 - 79 | dobře | | D | 60 - 69 | uspokojivě | | E | 50 - 59 | dostatečně | | F | méně než 50| nedostatečně | 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ň 30 bodů. 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 penalizace za pozdní odevzdání Vám nedovolí získat požadované minimum bodů. ====== Přednášky ====== [[courses:b6b36dsa:prednasky|Přednášky]] ===== 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ň 5 bodů z každého). Úlohy je třeba odevzdat v každém případě. Pozdní odevzdání bude penalizováno. 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]]. ===== Test v semestru ===== V semestru se bude psát **jeden test**. Testem je nutné úspěšně projít, jinak ztrácíte nárok na zápočet. Test se bude psát na přednášce v pátek dle aktuální situace. Na úspěšný průchod testem bude potřeba získat alespoň **10 bodů**. Pokrývá látku, která byla odpřednášena a probrána na cvičeních před termínem testu. V případě neúspěchu v testu bude organizován jeden náhradní termín! Pokud ani zde neuspějete, ztrácíte nárok na zápočet. Ukázka testu: {{ :courses:b6b36dsa:test_reseny.pdf | příklad a řešeni}} /* ==== 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á látku, která byla odpřednášena a probrána na cvičeních před termínem testu (doplněno 19.4.2023). , např. 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-reseny-2022.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ů. Pokrývá látku, která byla odpřednášena a probrána na cvičeních od začátku semestru (doplněno 10.5.2023). , např. následující témata: * 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-reseny-2022.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 | 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 | Introduction to Algorithms on MIT (2011) ]] [[https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/ | Introduction to Algorithms on MIT (2020) ]] {{ :courses:b6b36dsa:dynamicke_programovani_priklady.pdf | Příklady dynamického programování}}