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

Předmět je zahrnut do těchto studijních plánů:

Plán Obor Role Dop. semestr
BMI(ECTS) Manažerská informatika P 3
BPSTMMI Manažerská informatika P 3
BSI(ECTS) Softwarové inženýrství P 3
BPSTMWM Web a multimedia P 3
BPSTMSI Softwarové inženýrství P 3
BPSTMIS Inteligentní systémy (bakalářský, dobíhající pro nástupní ročníky před 2013) P 3
BWM(ECTS) Web a multimedia P 3
BIS(ECTS) Inteligentní systémy (bakalářský, dobíhající pro nástupní ročníky před 2013) P 3

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)
Za obsah odpovídá: doc. Ing. Ivan Jelínek, CSc.