Popis předmětu - A7B36DSA
Přehled studia |
Přehled oborů |
Všechny skupiny předmětů |
Všechny předměty |
Seznam rolí |
Vysvětlivky
Návod
Výsledek studentské ankety předmětu je zde: A7B36DSA
A7B36DSA | Datové struktury a algoritmy | Rozsah výuky: | 2P+2S | ||
---|---|---|---|---|---|
Garanti: | Role: | P | Jazyk výuky: | CS | |
Vyučující: | Zakončení: | Z,ZK | |||
Zodpovědná katedra: | 13136 | Kreditů: | 6 | Semestr: | Z |
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: A7B36DSA
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í.Osnovy 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 |
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. | 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 |
Literatura:
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) |
Požadavky:
Znalost programování a matematiky v rozsahu prvního ročníku, schopnost exaktního myšlení.Webová stránka:
https://moodle.fel.cvut.cz/courses/A7B36DSAPředmět je zahrnut do těchto studijních plánů:
Stránka vytvořena 12.12.2019 15:50:31, semestry: Z,L/2020-1, L/2018-9, Z,L/2019-20, 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) |