Logo ČVUT
ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE
STUDIJNÍ PLÁNY
2018/2019

Algoritmizace

Přihlášení do KOSu pro zápis předmětu Zobrazit rozvrh
Kód Zakončení Kredity Rozsah Jazyk výuky
B4B33ALG Z,ZK 6 2p+2c česky
Korekvizita:
Bezpečnost práce v elektrotechnice pro bakaláře (BEZB)
Základní školení BOZP (BEZZ)
Předmět nesmí být zapsán současně s:
Algorithms (AE4B33ALG)
Algorithms (BE5B33ALG)
Přednášející:
Daniel Průša, Marko Genyk-Berezovskyj (gar.)
Cvičící:
Daniel Průša, Marko Genyk-Berezovskyj (gar.), Ondřej Hubáček, Vladimír Kunc, Oleg Ostashchuk, Jindřich Prokop
Předmět zajišťuje:
katedra kybernetiky
Anotace:

Cílem předmětu je schopnost samostatné implementeca různých variant zálkadních úloh informatiky. Hlavní témata jsou algoritmy řazení a vyhledávání a jim odpovídající datové struktury. Důraz je kladen na algoritmický aspekt úloh a efektivitu praktického řešení.

Požadavky:

Programování 1

Osnova přednášek:

1. Řád růstu funkcí, asymptotická složitost algoritmu

2. Rekurze, složitost rekurentních algoritmů, mistrovská věta

3. Stromy, binární stromy, prohledávání s návratem

4. Fronta, graf, průchod stromem/grafem do šířky/hloubky

5. Vyhledávani v poli, binární vyhledávací stromy

6. AVL a B- stromy

7. Řazení, Insert Sort, SelectionSort, Bubble Sort, QuickSort

8. Řazení, Merge Sort, Halda, Heap Sort

9. Řazení, Radix sort, Counting Sort, Bucket Sort

10. Dynamické programování, struktura optimálního řešení, odstranění rekurze, optimální BVS

11. Dynamické programování, nejdelší společná podposloupnost, optimální násobení matic, problém batohu

12. Hashing, otevřené a zřetězené tabulky, double hashing

13. Hashing, srůstající tabulky, univerzální hashování,

14. Řazení vícedimenzionálních dat, porovnání řadících algoritmů

Osnova cvičení:

1. Řád růstu funkcí, asymptotická složitost algoritmu

2. Rekurze, složitost rekurentních algoritmů, mistrovská věta

3. Stromy, binární stromy, prohledávání s návratem

4. Fronta, graf, průchod stromem/grafem do šířky/hloubky

5. Vyhledávani v poli, binární vyhledávací stromy

6. AVL a B- stromy

7. Řazení, Insert Sort, SelectionSort, Bubble Sort, QuickSort

8. Řazení, Merge Sort, Halda, Heap Sort

9. Řazení, Radix sort, Counting Sort, Bucket Sort

10. Hashing, otevřené a zřetězené tabulky, double hashing

11. Hashing, srůstající tabulky, univerzální hashování,

12. Dynamické programování, struktura optimálního řešení, odstranění rekurze, optimální BVS

13. Dynamické programování, nejdelší společná podposloupnost, optimální násobení matic, problém batohu

14. Řazení vícedimenzionálních dat, porovnání řadících algoritmů

Cíle studia:

Cílem je schopnost samostatné implementace různých variant základních úloh informatiky. Hlavní témata jsou algoritmy řazení a vyhledávání a jim odpovídající datové struktury. Důraz je kladen na algoritmický aspekt úloh a efektivitu praktického řešení.

Studijní materiály:

[1] T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein: Introduction to Algorithms, 3rd ed., MIT Press, 2009,

[2] S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani: Algorithms, Mcgraw-Hill Higher Education, 2006,

[3] Pavel Töpfer: Algoritmy a programovací techniky, Prometheus Praha 1995, 2. vydání 2007

[4] Robert Sedgewick: Algoritmy v C, části 1-4, SoftPress, Praha, 2003

Poznámka:

Rozsah výuky v kombinované formě studia: 14p+6c

Další informace:
https://cw.fel.cvut.cz/b181/courses/b4b33alg/start
Rozvrh na zimní semestr 2018/2019:
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
místnost KN:E-310

09:15–10:45
(přednášková par. 1
paralelka 106)

Karlovo nám.
Lab K310 Linux
místnost KN:E-310
Ostashchuk O.
11:00–12:30
(přednášková par. 1
paralelka 105)

Karlovo nám.
Lab K310 Linux
Út
místnost KN:E-230
Kunc V.
12:45–14:15
(přednášková par. 1
paralelka 104)

Karlovo nám.
Laboratoř PC
místnost KN:E-230
Kunc V.
16:15–17:45
(přednášková par. 1
paralelka 101)

Karlovo nám.
Laboratoř PC
místnost KN:E-230

18:00–19:30
(přednášková par. 1
paralelka 102)

Karlovo nám.
Laboratoř PC
St
místnost KN:E-230
Hubáček O.
09:15–10:45
(přednášková par. 1
paralelka 103)

Karlovo nám.
Laboratoř PC
Čt

místnost KN:E-107
Genyk-Berezovskyj M.
Průša D.

11:00–12:30
(přednášková par. 1)
Karlovo nám.
Zengerova posluchárna K1
místnost KN:E-327
Genyk-Berezovskyj M.
14:30–16:00
(přednášková par. 1
paralelka 107)

Karlovo nám.
Solarium K327
místnost KN:E-327
Prokop J.
12:45–14:15
(přednášková par. 1
paralelka 108)

Karlovo nám.
Solarium K327
Rozvrh na letní semestr 2018/2019:
Rozvrh není připraven
Předmět je součástí následujících studijních plánů:
Platnost dat k 20. 6. 2019
Aktualizace výše uvedených informací naleznete na adrese http://bilakniha.cvut.cz/cs/predmet4682306.html