Datové struktury a algoritmy

Podmínkou zápisu předmětu je dřívější úspěšné absolvování předmětů:

Logika (A7B01LOG)
Matematická analýza (A7B01MAA)
Pravděpodobnost a statistika (A7B01PST)

Předmět nesmí být zapsán současně s:

Datové struktury a algoritmy (Y36DSA)

Předmět je náhradou za:

Datové struktury a algoritmy (Y36DSA)

Přednášející:

Michal Píše (gar.)

Cvičící:

Michal Píše (gar.), Miroslav Čepek, Jan Drchal, Marko Genyk-Berezovskyj, Miroslav Šnorek

Předmět zajišťuje:

katedra počítačů

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.

Požadavky:

Znalost programování a matematiky v rozsahu prvního ročníku, schopnost exaktního myšlení.

Osnova 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

Osnova 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

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

Studijní materiály:

1. Cormen et al.: Introduction to Algorithms, 3rd edition

2. Webová stránka předmětu: http://edux.feld.cvut.cz/courses/A7B36DSA/

Poznámka:

Rozvrh na zimní semestr 2011/2012:

	06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Po
Út	místnost KN:A-108 Drchal J. 07:30–09:00 (přednášková par. 1 paralelka 101) Karlovo nám. Cvičebna -BUFETmístnost KN:A-108 Drchal J. 09:15–10:45 (přednášková par. 1 paralelka 102) Karlovo nám. Cvičebna -BUFETmístnost KN:A-108 Píše M. 11:00–12:30 (přednášková par. 1 paralelka 103) Karlovo nám. Cvičebna -BUFETmístnost KN:E-107 Píše M. 12:45–14:15 (přednášková par. 1) Karlovo nám. Zengerova posluchárna K1místnost KN:A-108 Genyk-Berezovskyj M. 16:15–17:45 (přednášková par. 1 paralelka 104) Karlovo nám. Cvičebna -BUFETmístnost KN:A-108 Genyk-Berezovskyj M. 18:00–19:30 (přednášková par. 1 paralelka 105) Karlovo nám. Cvičebna -BUFET
St	místnost 07:30–09:00 (přednášková par. 1 paralelka 106) místnost KN:A-108 Drchal J. 09:15–10:45 (přednášková par. 1 paralelka 107) Karlovo nám. Cvičebna -BUFETmístnost KN:A-108 Drchal J. 11:00–12:30 (přednášková par. 1 paralelka 108) Karlovo nám. Cvičebna -BUFETmístnost 12:45–14:15 (přednášková par. 1 paralelka 109) místnost 14:30–16:00 (přednášková par. 1 paralelka 110) místnost 16:15–17:45 (přednášková par. 1 paralelka 111) místnost 18:00–19:30 (přednášková par. 1 paralelka 112)
Čt	místnost 07:30–09:00 (přednášková par. 1 paralelka 113) místnost KN:A-108 Čepek M. 09:15–10:45 (přednášková par. 1 paralelka 114) Karlovo nám. Cvičebna -BUFETmístnost KN:A-108 Čepek M. 11:00–12:30 (přednášková par. 1 paralelka 115) Karlovo nám. Cvičebna -BUFETmístnost 12:45–14:15 (přednášková par. 1 paralelka 116) místnost 14:30–16:00 (přednášková par. 1 paralelka 117) místnost 16:15–17:45 (přednášková par. 1 paralelka 118)
Pá

Rozvrh na letní semestr 2011/2012:

Rozvrh není připraven

Předmět je součástí následujících studijních plánů:

• Manažerská informatika (STM-A7B-přechodné) (povinný předmět programu)
• Softwarové inženýrství (STM-A7B-přechodné) (povinný předmět programu)
• Inteligentní systémy (STM-A7B-prechodné) (povinný předmět programu)
• Web a multimedia (STM-A7B-přechodné) (povinný předmět programu)
• Inteligentní systémy (STM-A7B) (povinný předmět programu)
• Manažerská informatika (STM-A7B) (povinný předmět programu)
• Softwarové inženýrství (STM-A7B) (povinný předmět programu)
• Web a multimedia (STM-A7B) (povinný předmět programu)