Datové struktury a algoritmy

Vztahy:

Předmět B6B36DSA může při kontrole studijních plánů nahradit předmět A7B36DSA

Předmět je ekvivalentní s BD6B36DSA .

Garant předmětu:

Karel Richta

Přednášející:

Karel Richta

Cvičící:

Jan Drchal, Ingrid Nagyová, Karel Richta

Předmět zajišťuje:

katedra počítačů

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.

Požadavky:

Znalost programování a matematiky v rozsahu předmětů z předchozích ročníků, schopnost exaktního myšlení.

Osnova 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

Osnova 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

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.

Studijní materiály:

[1] Cormen, T. H. - Leiserson, C. E. - Rivest, R. L. - Stein, C.: Introduction to Algorithms, 3rd ed., MIT Press, 2009.

Poznámka:

Další informace:

https://cw.fel.cvut.cz/wiki/courses/b6b36dsa/start

Rozvrh na zimní semestr 2024/2025:

Rozvrh není připraven

Rozvrh na letní semestr 2024/2025:

	06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Po
Út
St	místnost KN:E-126 Nagyová I. 14:30–16:00 (přednášková par. 1 paralelka 103) Karlovo nám. Trnkova posluchárna K5místnost KN:E-126 Nagyová I. 16:15–17:45 (přednášková par. 1 paralelka 104) Karlovo nám. Trnkova posluchárna K5
Čt
Pá	místnost FS_KN:A-214 Richta K. 12:45–14:15 (přednášková par. 1) Karlovo nám. Posluchárna FS A:214 - záp.místnost KN:E-128 Drchal J. 16:15–17:45 (přednášková par. 1 paralelka 101) Karlovo nám. Cvičebna K3 místnost KN:E-107 Richta K. 12:45–14:15 (přednášková par. 1) Karlovo nám. Zengerova posluchárna K1místnost KN:E-128 Drchal J. 14:30–16:00 (přednášková par. 1 paralelka 102) Karlovo nám. Cvičebna K3 místnost KN:E-301 Richta K. 12:45–14:15 (přednášková par. 1) Karlovo nám. Šrámkova posluchárna K9

Předmět je součástí následujících studijních plánů:

• Softwarové inženýrství a technologie (povinný předmět programu)
• Softwarové inženýrství a technologie - specializace Enterprise systémy (povinný předmět programu)
• Softwarové inženýrství a technologie - specializace Technologie pro multimédia a virtuální realitu (povinný předmět programu)
• Softwarové inženýrství a technologie - specializace Business informatics (povinný předmět programu)
• Softwarové inženýrství a technologie - specializace Technologie internetu věcí (povinný předmět programu)
• Softwarové inženýrství a technologie - společný 1. ročník (povinný předmět programu)