Diskusní fórum Výsledky Popis předmětu na FEL Rozvrh na FEL

Předměty B6B36DSA a BD6B36DSA mají společné stránky.

Během semestru bude zadáno 6 domácích úkolů. Zadání úkolů je vyvěšeno na stránkách předmětu a budou se odevzdávat do odevzdávacího systému (Squeezer nebo Upload Systém), kde budou automaticky hodnoceny.

Pro získání zápočtu je nutné úspěšně a včas odevzdat nejméně 5 domácích úkolů (získat alespoň 5 bodů). Úlohy je třeba odevzdat v každém případě, pokud jsou odevzdány v zadaném termínu, postačí odevzdat jen 5 úkolů. Pozdní odevzdání bude odevzdání penalizováno nutností odevzdat i šestý úkol.

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.

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 při zkoušce nezohledňuje.

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 v semestru se bude psát na přednášce v pátek 31.3. 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ň 5 bodů. Pokrývá následující témata:

1. Rekurze
2. Asymptotická složitost kódu
3. Množiny omikron, omega a theta
4. Správnost kódu, invarianty
5. Složitost algoritmů

Zadání a stručný náznak řešení

Druhý test v semestru se bude psát na přednášce v pátek 12.5. 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ň 5 bodů. Témata příkladů:

1. Randomizované algoritmy
2. Důkaz pomocí matematické indukce (např. důkaz funkčnosti procedury Partition začínající v učebnici na straně 171),
3. Kombinatorika, pravděpodobnost (např. výpočet složitost bucket sortu začínající v učebnici na straně 202),
4. Formalizace přirozeného jazyka (např. definice výběru n-tého prvku (selection problem) v učebnici na straně 213),
5. Počítání (např. analýza počtu kroků řazení vkládáním začínající v učebnici na straně 26) a
6. Programování (zjevné, doporučujeme zopakovat si zejména práci se spojovými strukturami).

Částečné zadání a řešení

Naposledy změněno: Pondělí, 15. leden 2018, 19:20

Cormen Thomas H. et al.: Introduction to Algorithms, 3rd Edition, MIT Press, 2009