Abyste předmět úspěšně zakončili, musíte:
1. Získat zápočet:
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ů:
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.
Týden | Datum | Téma | Průsvitky |
---|---|---|---|
1. | 24.2. | Úvod do problematiky. | 01 |
2. | 3.3. | Techniky návrhu algoritmů. | 02 |
3. | 10.3. | Složitost algoritmů. | 03 |
4. | 17.3. | Základy řazení. | 04 |
5. | 24.3. | Pokročilé řazení. | 05 |
6. | 31.3. | Randomizované algoritmy. | 06 |
7. | 7.4. | Odpadá, svátek | – |
8. | 14.4. | 1.Test | příklad a řešeni |
9. | 21.4. | Abstraktní datové typy I. | 08 |
10. | 28.4. | Abstraktní datové typy II. Stromy | 09 10 |
11. | 5.5. | Vyhledávání. B-stromy. | 11a 11b |
12. | 12.5. | Dynamické programování. | 13 |
13. | 19.5. | NP-úplnost a ostatní. | 14 |
14. | 26.5. | 2.Test | příklad a řešeni |
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)