Algoritmizace
| Kód | Zakončení | Kredity | Rozsah | Jazyk výuky |
|---|---|---|---|---|
| B4B33ALG | Z,ZK | 6 | 2P+2C | česky |
- 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ý)
- Předmět je ekvivalentní s AE4B33ALG,A4B33ALG .
- Garant předmětu:
- Daniel Průša
- Přednášející:
- Robert Pěnička, Daniel Průša
- Cvičící:
- Jiří Němeček, Robert Pěnička, 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, Selection Sort, Bubble Sort, Quick Sort
8. Řazení, Merge Sort, Halda, Heap Sort, Radix sort, Counting Sort
9. Dynamické programování, struktura optimálního řešení, odstranění rekurze, tabelace, maximální cesta v DAG
10. Dynamické programování, nejdelší společná podposloupnost, optimální násobení matic
11. Dynamické programování, optimální BVS, 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. Hledání mediánu, řazení vícedimenzionálních dat
- 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, Selection Sort, Bubble Sort, Quick Sort
8. Řazení, Merge Sort, Halda, Heap Sort, Radix sort, Counting Sort
9. Dynamické programování, struktura optimálního řešení, odstranění rekurze, tabelace, maximální cesta v DAG
10. Dynamické programování, nejdelší společná podposloupnost, optimální násobení matic
11. Dynamické programování, optimální BVS, 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. Hledání mediánu, řazení vícedimenzionálních dat
- 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://alg.fel.cvut.cz/
- Rozvrh na zimní semestr 2025/2026:
-
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 St Čt Pá - Rozvrh na letní semestr 2025/2026:
- 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)
- 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 2025 (povinný předmět programu)
- Otevřená informatika - Internet věcí 2025 (povinný předmět programu)
- Otevřená informatika - Software 2025 (povinný předmět programu)
- Otevřená informatika - Počítačové hry a grafika 2025 (povinný předmět programu)