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

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

Předmět B4B33ALG nesmí být zapsán, je-li v témže semestru zapsán anebo již dříve absolvován předmět AE4B33ALG (vztah je symetrický)

Předmět B4B33ALG může při kontrole studijních plánů nahradit předmět BE5B33ALG

Podmínkou zápisu na předmět B4B33ALG je, že student si nejpozději ve stejném semestru zapsal příslušný počet předmětů ze skupiny BEZBM

Předmět B4B33ALG nesmí být zapsán, je-li v témže semestru zapsán anebo již dříve absolvován předmět BE5B33ALG (vztah je symetrický)

Garant předmětu:
Marko Genyk-Berezovskyj
Přednášející:
Marko Genyk-Berezovskyj, Daniel Průša
Cvičící:
Jakub Dupák, Roland Fritsch, Marko Genyk-Berezovskyj, Jiří Němeček, Daniel Průša, Pavel Šindler
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/wiki/courses/B4B33ALG
Rozvrh na zimní semestr 2023/2024:
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
Šindler P.
11:00–12:30
(přednášková par. 1
paralelka 105)

Karlovo nám.
Lab K310 Linux
Út
místnost KN:E-132
Šindler P.
11:00–12:30
(přednášková par. 1
paralelka 102)

Karlovo nám.
Laboratoř PC
místnost KN:E-230
Němeček J.
16:15–17:45
(přednášková par. 1
paralelka 101)

Karlovo nám.
Laboratoř PC
místnost KN:E-230
Dupák J.
12:45–14:15
(přednášková par. 1
paralelka 104)

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

07:30–09:00
(přednášková par. 1
paralelka 106)

Karlovo nám.
Laboratoř PC
místnost KN:E-230
Šindler P.
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
Fritsch R.
14:30–16:00
(přednášková par. 1
paralelka 107)

Karlovo nám.
Solarium K327
místnost FS_KN:A-214
Genyk-Berezovskyj M.
Průša D.

11:00–12:30
(přednášková par. 1)
Karlovo nám.
Posluchárna FS A:214 - záp.
místnost KN:E-327
Fritsch R.
12:45–14:15
(přednášková par. 1
paralelka 108)

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