Brute - odevzdávací systém Popis předmětu na FEL Rozvrh na FEL

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.

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.

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 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 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

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

Pro rychlé přiblížení lze použít i zdroj: Wróblewski Piotr: Algoritmy, Computer Press, ISBN: 978-80-251-4126-7, 2015

Terminologii ale používáme dle Cormena.

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)