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://alg.fel.cvut.cz/
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, Selection Sort, Bubble Sort, Quick Sort |
| 8. | | Řazení, Merge Sort, Halda, Heap Sort, Radix sort, Counting Sort |
| 9. | | Dynamické programování, struktura optimálního řešení, odstranění rekurze, tabelace, maximální cesta v DAG |
| 10. | | Dynamické programování, nejdelší společná podposloupnost, optimální násobení matic |
| 11. | | Dynamické programování, optimální BVS, 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. | | Hledání mediánu, řazení vícedimenzionálních dat |
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, Selection Sort, Bubble Sort, Quick Sort |
| 8. | | Řazení, Merge Sort, Halda, Heap Sort, Radix sort, Counting Sort |
| 9. | | Dynamické programování, struktura optimálního řešení, odstranění rekurze, tabelace, maximální cesta v DAG |
| 10. | | Dynamické programování, nejdelší společná podposloupnost, optimální násobení matic |
| 11. | | Dynamické programování, optimální BVS, 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. | | Hledání mediánu, řazení vícedimenzionálních dat |
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 18.4.2026 17:50:22, semestry: L/2027-8, Z/2025-6, L/2028-9, L/2026-7, Z/2027-8, L/2029-30, L/2025-6, Z/2028-9, Z/2026-7, 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) |