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/start

Anotace:

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_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
BPSIT Před zařazením do oboru P 4


Stránka vytvořena 28.3.2024 09:53:46, semestry: Z,L/2023-4, 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)