Algoritmizace

Vztahy:

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

Marko Genyk-Berezovskyj, Jiří Němeček, Daniel Průša, Jan Ševic, Pavel Šindler, Peter Vataščin

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 2024/2025:

	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 Ševic J. 11:00–12:30 (přednášková par. 1 paralelka 105) Karlovo nám. Lab K310 Linux
Út	místnost KN:E-132 Němeček J. 11:00–12:30 (přednášková par. 1 paralelka 102) Karlovo nám. Laboratoř PCmístnost KN:E-230 Ševic J. 16:15–17:45 (přednášková par. 1 paralelka 101) Karlovo nám. Laboratoř PC místnost KN:E-230 Němeček J. 12:45–14:15 (přednášková par. 1 paralelka 104) Karlovo nám. Laboratoř PC
St	místnost KN:E-230 Šindler P. 07:30–09:00 (přednášková par. 1 paralelka 106) Karlovo nám. Laboratoř PCmístnost KN:E-230 Šindler P. 09:15–10:45 (přednášková par. 1 paralelka 103) Karlovo nám. Laboratoř PC
Čt
Pá	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 K1místnost KN:E-327 Vataščin P. 14:30–16:00 (přednášková par. 1 paralelka 107) Karlovo nám. Solarium K327 místnost KN:E-327 Šindler P. 12:45–14:15 (přednášková par. 1 paralelka 108) Karlovo nám. Solarium K327

Rozvrh na letní semestr 2024/2025:

Rozvrh není připraven

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

• Otevřená informatika - Informatika a počítačové vědy 2016 (povinný předmět programu)
• Otevřená informatika - Internet věcí 2016 (povinný předmět programu)
• Otevřená informatika - Software 2016 (povinný předmět programu)
• Otevřená informatika - Počítačové hry a grafika 2016 (povinný předmět programu)
• Otevřená informatika - před rozřazením do oborů (povinný předmět programu)
• Lékařská elektronika a bioinformatika (povinně volitelný předmět)
• Otevřená informatika - před rozřazením do specializací (povinný předmět programu)
• Otevřená informatika - Základy umělé inteligence a počítačových věd 2018 (povinný předmět programu)
• Otevřená informatika - Internet věcí 2018 (povinný předmět programu)
• Otevřená informatika - Software 2018 (povinný předmět programu)
• Otevřená informatika - Počítačové hry a grafika 2018 (povinný předmět programu)