Algoritmizace

B232 - Letní 23/24
Tento předmět se nenachází v Moodle. Na jeho domovskou stránku se můžete dostat pomocí tlačítka "Stránka kurzu (mimo Moodle)" vpravo (pokud existuje).

Algoritmizace - B4B33ALG

Kredity 6
Semestry zimní
Zakončení zápočet a zkouška
Jazyk výuky čeština
Rozsah výuky 2P+2C
Anotace
Cílem předmětu je schopnost samostatné implementeca různých variant zálkadních úloh informatiky. Hlavní témata jsou algoritmy řazení a vyhledávání a jim odpovídající datové struktury. Důraz je kladen na algoritmický aspekt úloh a efektivitu praktického řešení.
Cíle studia
Cílem je schopnost samostatné implementace různých variant základních úloh informatiky. Hlavní témata jsou algoritmy řazení a vyhledávání a jim odpovídající datové struktury. Důraz je kladen na algoritmický aspekt úloh a efektivitu praktického řešení.
Osnovy přednášek
1. Řád růstu funkcí, asymptotická složitost algoritmu
2. Rekurze, složitost rekurentních algoritmů, mistrovská věta
3. Stromy, binární stromy, prohledávání s návratem
4. Fronta, graf, průchod stromem/grafem do šířky/hloubky
5. Vyhledávani v poli, binární vyhledávací stromy
6. AVL a B- stromy
7. Řazení, Insert Sort, SelectionSort, Bubble Sort, QuickSort
8. Řazení, Merge Sort, Halda, Heap Sort
9. Řazení, Radix sort, Counting Sort, Bucket Sort
10. Dynamické programování, struktura optimálního řešení, odstranění rekurze, optimální BVS
11. Dynamické programování, nejdelší společná podposloupnost, optimální násobení matic, problém batohu
12. Hashing, otevřené a zřetězené tabulky, double hashing
13. Hashing, srůstající tabulky, univerzální hashování,
14. Řazení vícedimenzionálních dat, porovnání řadících algoritmů

Osnovy cvičení
1. Řád růstu funkcí, asymptotická složitost algoritmu
2. Rekurze, složitost rekurentních algoritmů, mistrovská věta
3. Stromy, binární stromy, prohledávání s návratem
4. Fronta, graf, průchod stromem/grafem do šířky/hloubky
5. Vyhledávani v poli, binární vyhledávací stromy
6. AVL a B- stromy
7. Řazení, Insert Sort, SelectionSort, Bubble Sort, QuickSort
8. Řazení, Merge Sort, Halda, Heap Sort
9. Řazení, Radix sort, Counting Sort, Bucket Sort
10. Hashing, otevřené a zřetězené tabulky, double hashing
11. Hashing, srůstající tabulky, univerzální hashování,
12. Dynamické programování, struktura optimálního řešení, odstranění rekurze, optimální BVS
13. Dynamické programování, nejdelší společná podposloupnost, optimální násobení matic, problém batohu
14. Řazení vícedimenzionálních dat, porovnání řadících algoritmů
Literatura
[1] T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein: Introduction to Algorithms, 3rd ed., MIT Press, 2009,

[2] S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani: Algorithms, Mcgraw-Hill Higher Education, 2006,

[3] Pavel Töpfer: Algoritmy a programovací techniky, Prometheus Praha 1995, 2. vydání 2007

[4] Robert Sedgewick: Algoritmy v C, části 1-4, SoftPress, Praha, 2003


Požadavky
Programování 1