======= 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/1453 | 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.B222/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**.
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 8 otázek, každá je hodnocena 0 až 5-ti body (celkem tedy 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ů:
* za domácí úkoly (až 40 bodů),
* za testy v semestru (až 20 bodů),
* za zkoušku (až 40 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ň 30 bodů. Na první termín zkoušky mohou i ti, kteří ještě nemají opravený 2. test a nemají za něj body, vše se dořeší na místě.
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 2022/2023 =====
^ Týden ^ Datum ^ Téma ^ Průsvitky ^
| **1.** | 24.2. | Úvod do problematiky. | {{:courses:b6b36dsa:dsa-1-úvod.pdf|01}} |
| **2.** | 3.3. | Techniky návrhu algoritmů. | {{:courses:b6b36dsa:DSA-2-TechnikyNávrhuAlgoritmů.pdf|02}} |
| **3.** | 10.3. | Složitost algoritmů. | {{:courses:b6b36dsa:DSA-3-SložitostAlgoritmů.pdf|03}} |
| **4.** | 17.3. | Základy řazení. | {{:courses:b6b36dsa:DSA-4-Řazení.pdf|04}} |
| **5.** | 24.3. | Pokročilé řazení. | {{:courses:b6b36dsa:DSA-7-PokrocileRazeni.pdf|05}} |
| **6.** | 31.3. | Randomizované algoritmy. | {{:courses:b6b36dsa:DSA-5-Randomized.pdf|06}} | /* {{:courses:b6b36dsa:DSA-5a-Priklady.pdf| Příklady }} */
| **7.** | 7.4. | //Odpadá, svátek// | -- |
| **8.** | 14.4. | **1.Test** | {{:courses:b6b36dsa:1-test-2018-04-06-reseny.pdf | příklad a řešeni}} |
| **9.** | 21.4. | Abstraktní datové typy I. | {{:courses:b6b36dsa:DSA-8-AbstrakniDatoveTypy.pdf | 08}} |
| **10.** | 28.4. | Abstraktní datové typy II. Stromy | {{:courses:b6b36dsa:DSA-9-AbstraktniDatoveTypyII.pdf | 09}} {{:courses:b6b36dsa:DSA-9-Stromy.pdf | 10}} |
| **11.** | 5.5. | Vyhledávání. B-stromy. | {{:courses:b6b36dsa:DSA-10-vyhledavani.pdf |11a}} {{:courses:b6b36dsa:DSA-11-PokrocileVyhledavani.pdf |11b}} |
| **12.** | 12.5. | Dynamické programování. | {{:courses:b6b36dsa:DSA-12-DynamickeProgramovani.pdf|13}} |
| **13.** | 19.5. | NP-úplnost a ostatní. | {{:courses:b6b36dsa:DSA-13-NP-Uplnost.pdf|14}} |
| **14.** | 26.5. | **2.Test** | {{:courses:b6b36dsa:2-test-2018-05-11-reseny.pdf| příklad a řešeni}} |
/* | **14.** | 26.5. | | | */
===== 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.
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á 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) ]]
{{ :courses:b6b36dsa:dynamicke_programovani_priklady.pdf | Příklady dynamického programování}}