Algoritmizace

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

URL: http://cw.felk.cvut.cz/doku.php/courses/a4b33alg/start

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