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.

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.

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 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á 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í 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ů. 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í 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)

Příklady dynamického programování