Popis předmětu - B4B33ALG
Přehled studia |
Přehled oborů |
Všechny skupiny předmětů |
Všechny předměty |
Seznam rolí |
Vysvětlivky
Návod
Webová stránka:
https://cw.fel.cvut.cz/wiki/courses/B4B33ALG
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
Poznámka:
Rozsah výuky v kombinované formě studia: 14p+6c |
Klíčová slova:
Asymptotická složitost, rekurzivní algoritmy, binární stromy, vyhledávání, rozptylovací tabulky, řazení, dynamické programování.
Předmět je zahrnut do těchto studijních plánů:
Stránka vytvořena 27.7.2024 17:50:58, semestry: L/2024-5, L/2023-4, Z/2024-5, Z/2023-4, připomínky k informační náplni zasílejte správci studijních plánů |
Návrh a realizace: I. Halaška (K336), J. Novák (K336) |