Datové struktury a algoritmy

B151 - Zimní 15/16
Toto je tzv. shluknutý kurz. Skládá se z několika samostatných předmětů, které sdílejí výukové materiály, úkoly, testy apod. Níže si můžete zobrazit informace o jednotlivých předmětech tvořících tento shluk.

Datové struktury a algoritmy - A7B36DSA

Hlavní kurz
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í.
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í.

Datové struktury a algoritmy - AD7B36DSA

Kredity 6
Semestry zimní
Zakončení zápočet a zkouška
Jazyk výuky čeština
Rozsah výuky 14KP+6KC
Anotace
Složitost a správnost algoritmu; sekvence; rozptylování (asociativní pole); třídění a hledání; prioritní fronty; setříděné sekvence; generická optimalizace, softwarově-inženýrský pohled na algoritmizaci. \\Výsledek studentské ankety předmětu je zde: http://www.fel.cvut.cz/anketa/aktualni/courses/AD7B36DSA
Cíle studia
Cílem předmětu DSA je:
- naučit studenty knihovničku fundamentálních algoritmů,
- naučit studenty tyto algoritmy adekvátně přizpůsobovat,
- naučit studenty rozpoznávat situace, ve kterých se tyto algoritmy dají s úspěchem použít,
- naučit studenty analyzovat efektivitu algoritmů,
- naučit studenty formálně uvažovat o správnosti algoritmů a
- procvičit exaktní myšlení a vyjadřování.
Osnovy přednášek
1. Časová složitost
2. Správnost algoritmu
3. Průměrná složitost
4. Randomizované algoritmy
5. Sekvence
6. Hashování
7. Třídění a hledání
8. Prioritní fronty
9. Setříděné sekvence
10. Generická optimalizace
11. Softwarově-inženýrský přístup k algoritmizaci
Osnovy cvičení
1. Časová složitost
2. Správnost algoritmu
3. Průměrná složitost
4. Randomizované algoritmy
5. Sekvence
6. Hashování
7. Třídění a hledání
8. Prioritní fronty
9. Setříděné sekvence
10. Generická optimalizace
11. Softwarově-inženýrský přístup k algoritmizaci
Literatura
1. K. Mehlhorn, P. Sanders: Algorithms and Data Structures: The Basic Toolbox
2. K. Weihe: A Software Engineering Perspective on Algorithmics
3. Webová stránka předmětu: http://ocw.cvut.cz/moodle/course/view.php?id=471 (klíč: dsa)
Požadavky
Základní znalost programování, schopnost exaktního myšlení.