Moodle FEL ČVUT
Datové struktury a algoritmy
Tento předmět se nenachází v Moodle. Na jeho domovskou stránku se můžete dostat pomocí tlačítka "Stránka kurzu (mimo Moodle)" vpravo (pokud existuje).
Datové struktury a algoritmy A7B36DSA
| Kredity | 6 |
| Semestry | zimní |
| Zakončení | zápočet a zkouška |
| Jazyk výuky | čeština |
| Rozsah výuky | 2P+2S |
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
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í.
- 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
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
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)
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í.
Za správnost dat zodpovídá:
Studijní Informační Systém (KOS)