Subject description - BD6B36DSA
Summary of Study |
Summary of Branches |
All Subject Groups |
All Subjects |
List of Roles |
Explanatory Notes
Instructions
Web page:
https://cw.fel.cvut.cz/wiki/courses/bd6b36dsa/start
Anotation:
Předmět slouží pro seznámení se složitostí algoritmů a metodami jejího odhadu. Probírají se zde základy matematické indukce, rekurzivních algoritmů, typické příklady datových struktur, algoritmy řazení a vyhledávání. Jako doplněk pak NP-úplnost a související problémy.
Study targets:
Cílem předmětu je naučit studenty počítat odhady složitostí algoritmů, dokazovat tvrzení matematickou indukcí, umět porovnat složitosti různých řešení a orientovat se v NP-úplnosti a souvisejících problémech.
Course outlines:
1. | | Matematická indukce a rekurentní rovnice - základy |
2. | | Složitost algoritmů, horní, dolní, průměrný odhad, rekurze, složitost rekurentních algoritmů |
3. | | Metody řešení problémů |
4. | | Pravděpodobnostní analýza a randomizované algoritmy |
5. | | Typické příklady datových struktur, zásobník, fronta, pole, seznam |
6. | | Nelineární datové struktury, stromy, grafy |
7. | | Grafové algoritmy. |
8. | | Rozptylování, randomizované algoritmy |
9. | | Metody asociativního řazení, porovnání metod a implementací |
10. | | Řazení v lineárním čase |
11. | | Metody vyhledávání |
12. | | Binární vyhledávací stromy, AVL-stromy, RB-stromy, B-stromy |
13. | | Dynamické programování |
14. | | Základy NP-úplnosti |
Exercises outline:
1. | | Úvod |
2. | | Růst funkcí |
3. | | Rozděl a panuj |
4. | | Pravděpodobnostní analýza a randomizované algoritmy |
5. | | Třídění haldou a quicksort |
6. | | Třídění v lineárním čase, mediány a další statistické veličiny |
7. | | Písemný test |
8. | | Elementární datové struktury, rozptylování |
9. | | Binární vyhledávací stromy |
10. | | Grafové algoritmy |
11. | | Dynamické programování |
12. | | Amortizovaná analýza |
13. | | B-stromy |
14. | | NP-úplnost |
Literature:
[1] | | Cormen, T. H. - Leiserson, C. E. - Rivest, R. L. - Stein, C.: Introduction to Algorithms, 3rd ed., MIT Press, 2009. |
Requirements:
Znalost programování a matematiky v rozsahu předmětů z předchozích ročníků, schopnost exaktního myšlení.
Subject is included into these academic programs:
Page updated 29.3.2024 11:55:13, semester: Z/2024-5, Z,L/2023-4, Send comments about the content to the Administrators of the Academic Programs |
Proposal and Realization: I. Halaška (K336), J. Novák (K336) |