Logo ČVUT
ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE
STUDIJNÍ PLÁNY
2018/2019

Datové struktury a algoritmy

Předmět není vypsán Nerozvrhuje se
Kód Zakončení Kredity Rozsah Jazyk výuky
A7B36DSA Z,ZK 6 2+2s česky
Podmínkou zápisu předmětu je dřívější úspěšné absolvování předmětů:
Logika (A7B01LOG)
Matematická analýza (A7B01MAA)
Pravděpodobnost a statistika (A7B01PST)
Přednášející:
Cvičící:
Předmět zajišťuje:
katedra počítačů
Anotace:

Růst funkcí. Rozděl a panuj. Pravděpodobnostní analýza a randomizované algoritmy. Třídění haldou a quicksort. Třídění v lineárním čase, mediány a další statistické veličiny. Elementární datové struktury, rozptylování. Binární vyhledávací stromy. Dynamické programování. Amortizovaná analýza. B-stromy. NP-úplnost.

Výsledek studentské ankety předmětu je zde: http://www.fel.cvut.cz/anketa/aktualni/courses/A7B36DSA

Požadavky:

Znalost programování a matematiky v rozsahu prvního ročníku, schopnost exaktního myšlení.

Osnova přednášek:

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. První test

7. Třídění v lineárním čase, mediány a další statistické veličiny

8. Elementární datové struktury, rozptylování

9. Binární vyhledávací stromy

10. Druhý test

11. Dynamické programování

12. Amortizovaná analýza

13. B-stromy

14. NP-úplnost

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. První test

7. Třídění v lineárním čase, mediány a další statistické veličiny

8. Elementární datové struktury, rozptylování

9. Binární vyhledávací stromy

10. Druhý test

11. Dynamické programování

12. Amortizovaná analýza

13. B-stromy

14. NP-úplnost

Cíle studia:

Vaším cílem v předmětu DSA bude:

- naučit se knihovničku fundamentálních algoritmů,

- naučit se tyto algoritmy adekvátně přizpůsobovat,

- naučit se rozpoznávat situace, ve kterých se tyto algoritmy dají s úspěchem použít,

- naučit se analyzovat efektivitu algoritmů,

- naučit se formálně uvažovat o správnosti algoritmů a

- procvičit si exaktní myšlení a vyjadřování.

Studijní materiály:

1. Cormen et al.: Introduction to Algorithms, 3rd edition

2. Webová stránka předmětu: https://moodle.fel.cvut.cz/course/view.php?id=7 (klíč: dsa)

Poznámka:
Další informace:
https://moodle.fel.cvut.cz/courses/A7B36DSA
Pro tento předmět se rozvrh nepřipravuje
Předmět je součástí následujících studijních plánů:
Platnost dat k 26. 3. 2019
Aktualizace výše uvedených informací naleznete na adrese http://bilakniha.cvut.cz/cs/predmet1392106.html