Algoritmizace

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

Rozvrh není připraven

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)