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:	2+2s
Garanti:	Richta K.	Role:	P	Zakončení:	Z,ZK
Vyučující:	Richta K.
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
BPSTMSI	Softwarové inženýrství	P	3
BPSTMWM	Web a multimedia	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
BSI(ECTS)	Softwarové inženýrství	P	3

---

Stránka vytvořena 25.9.2017 17:47:25, semestry: L/2016-7, Z,L/2017-8, Z/2018-9, 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)