Algoritmizace
Kód | Zakončení | Kredity | Rozsah | Jazyk výuky |
---|---|---|---|---|
A4B33ALG | Z,ZK | 6 | 2P+2C | česky |
- Garant předmětu:
- Přednášející:
- Cvičící:
- Předmět zajišťuje:
- katedra kybernetiky
- Anotace:
-
Výuka algoritmizace probíhá tak, aby byla minimálně závislá na
programovacím jazyku, nicméně cvičená a přednášená v Javě. Výklad
datových struktur, základních algoritmů, funkcí, rekurze,
iterace. Stromy. Řazení a vyhledávání. Dynamické programování. Student je schopen aktivně
sestavovat algoritmy netriviálních úloh a hodnotit jejich efektivitu.
Výsledek studentské ankety předmětu je zde: http://www.fel.cvut.cz/anketa/aktualni/courses/A4B33ALG
- 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. 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ů
- Osnova cvičení:
-
1. Vstupní test, zopakování základů práce ve vývojovém prostředí, příklady na procedury, parametry, jednoduchá třída, zadání semestrální práce.
2. Práce s jednorozměrnými poli,
3. Řazení a hledání v jednorozměrných polích
4. Práce s vícerozměrnými poli
5. Zpracování textu, řetězce
6. Zjišťování časové a paměťové náročnosti algoritmů
7. Sekvenční soubory
8. Implementace abstraktních datových typů
9. Rekurze a iterace
10. Spojové struktury, lineární spojové seznamy, obecné spojové seznamy
11. Konstrukce stromů, hledání ve stromech
12. Test, konzultace k semestrální úloze
13. Základní algoritmy úloh lineární algebry a geometrie, matematické analýzy
14. Zápočet
- Cíle studia:
- 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
[5] Jakub Černý: Základní grafové algoritmy, KAM MFF, 2010, online publikace
- Poznámka:
-
Rozsah výuky v kombinované formě studia: 14p+6c
- Další informace:
- http://cw.felk.cvut.cz/doku.php/courses/a4b33alg/start
- Pro tento předmět se rozvrh nepřipravuje
- Předmět je součástí následujících studijních plánů: