Popis předmětu - B6B36DSA
Přehled studia |
Přehled oborů |
Všechny skupiny předmětů |
Všechny předměty |
Seznam rolí |
Vysvětlivky
Návod
| B6B36DSA | Datové struktury a algoritmy | ||
|---|---|---|---|
| Role: | P | Rozsah výuky: | 2P+3C+3D |
| Katedra: | 13136 | Jazyk výuky: | |
| Garanti: | Richta K. | Zakončení: | Z,ZK |
| Přednášející: | Richta K. | Kreditů: | 6 |
| Cvičící: | Drchal J., Nagyová I., Richta K. | Semestr: | L |
Webová stránka:
https://cw.fel.cvut.cz/wiki/courses/b6b36dsa/startAnotace:
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.Cíle studia:
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.Osnovy přednášek:
| 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 |
Osnovy cvičení:
| 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 |
Literatura:
| [1] | Cormen, T. H. - Leiserson, C. E. - Rivest, R. L. - Stein, C.: Introduction to Algorithms, 3rd ed., MIT Press, 2009. |
Požadavky:
Znalost programování a matematiky v rozsahu předmětů z předchozích ročníků, schopnost exaktního myšlení.Předmět je zahrnut do těchto studijních plánů:
| Plán | Obor | Role | Dop. semestr |
| BPSIT | Před zařazením do oboru | P | 4 |
| BPSIT_2021 | Před zařazením do oboru | 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 |
| Stránka vytvořena 22.12.2024 05:50:33, semestry: L/2024-5, Z/2025-6, Z/2024-5, 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) |