Subject description - B6B36DSA
Summary of Study |
Summary of Branches |
All Subject Groups |
All Subjects |
List of Roles |
Explanatory Notes
Instructions
| B6B36DSA | Data Structures and Algorithms | ||
|---|---|---|---|
| Roles: | P | Extent of teaching: | 2P+3C+3D |
| Department: | 13136 | Language of teaching: | |
| Guarantors: | Richta K. | Completion: | Z,ZK |
| Lecturers: | Drchal J., Richta K. | Credits: | 6 |
| Tutors: | Drchal J., Kubr J., Prokop Y., Rektoris M., Richta K. | Semester: | L |
Web page:
https://cw.fel.cvut.cz/wiki/courses/b6b36dsa/startAnotation:
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:| Program | Branch | Role | Recommended semester |
| BPSIT_2021 | Common courses | P | 4 |
| BPSIT4_2021 | Technologie internetu věcí | P | 4 |
| BPSIT3_2021 | Business informatics | P | 4 |
| BPSIT2_2021 | Technologie pro multimédia a virtuální realitu | P | 4 |
| BPSIT1_2021 | Enterprise systémy | P | 4 |
| BPSIT | Common courses | P | 4 |
| Page updated 15.3.2025 07:51:49, semester: Z/2024-5, L/2025-6, L/2024-5, Z/2025-6, Send comments about the content to the Administrators of the Academic Programs | Proposal and Realization: I. Halaška (K336), J. Novák (K336) |