b6b36dsa -- Datové struktury a algoritmy

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 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. 01
2. 25.2. Techniky návrhu algoritmů. 02
3. 4.3. Složitost algoritmů. 03
4. 11.3. Základy řazení. 04
5. 18.3. Pokročilé řazení. 05
6. 25.3. Randomizované algoritmy. 06
7. 1.4. 1.Test příklad a řešeni
8. 8.4. Abstraktní datové typy I. 08
9. 15.4. Odpadá, svátek
10. 22.4. Abstraktní datové typy II. Stromy 10a 10b
11. 29.4. Vyhledávání. B-stromy. 11a 11b
12. 6.5. Dynamické programování. 13
13. 13.5. 2.Test příklad a řešeni
14. 20.5. NP-úplnost a ostatní. 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 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í 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í příklad a řešeni

Materiály

Další odkazy

Odkaz na stránky předmětu Introduction to Algorithms z Open Courseware MIT

Introduction to Algorithms on MIT

Odkaz na stránky předmětu Introduction to Algorithms z Open Courseware MIT (2011)

Introduction to Algorithms on MIT (2011)

courses/b6b36dsa/start.txt · Last modified: 2022/04/04 15:36 by richta