ČeskyEnglish

Popis předmětu - A4B33ALG

Přehled studia | Přehled oborů | Všechny skupiny předmětů | Všechny předměty | Seznam rolí | Vysvětlivky               Návod
A4B33ALG Algoritmizace Rozsah výuky:2+2c
Garanti:Genyk-Berezovskyj M. Role:P,V Zakončení:Z,ZK
Vyučující:Genyk-Berezovskyj M.
Zodpovědná katedra:13133 Kreditů:6 Semestr:L

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

Cíle studia:

Semester project consists from empirical evaluation of searching and sorting algorithms, comparison of iterative and recursive algorithms and debugging of graphical output of selected algorithms of linear algebra and mathematical analysis. Three phases of supervision associated to constituted subtask of project with closing demonstration and defense

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

Osnovy 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

Literatura:

[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

Požadavky:

Programování 1

Poznámka:

Rozsah výuky v kombinované formě studia: 14p+6c
URL: http://cw.felk.cvut.cz/doku.php/courses/a4b33alg/start

Webová stránka:

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

Klíčová slova:

Asymptotická složitost, rekurzivní algoritmy, binární stromy, vyhledávání, rozptylovací tabulky, řazení, dynamické programování.

Předmět je zahrnut do těchto studijních plánů:

Plán Obor Role Dop. semestr
BPOI2 Informatika a počítačové vědy P 2
BPOI_BO Před zařazením do oboru P 2
BPOI1 Počítačové systémy P 2
BPOI3 Softwarové systémy P 2
BPKYR_BO Před zařazením do oboru V 2
BPKYR3 Systémy a řízení V 2
BPKYR2 Senzory a přístrojová technika V 2
BPKYR1 Robotika V 2
BPKME5 Komunikace a elektronika V 2
BPKME4 Síťové a informační technologie V 2
BPKME3 Aplikovaná elektronika V 2
BPKME1 Komunikační technika V 2
BPKME2 Multimediální technika V 2
BPKME_BO Před zařazením do oboru V 2
BPEEM_BO Před zařazením do oboru V 2
BPEEM1 Aplikovaná elektrotechnika V 2
BPEEM2 Elektrotechnika a management V 2
BKSIT Před zařazením do oboru V 2
BPSTMMI Manažerská informatika V 2
BPSTMWM Web a multimedia V 2
BPSIT Před zařazením do oboru V 2
BPSTMSI Softwarové inženýrství V 2
BPSTM_BO Před zařazením do oboru V 2
BPSTMIS Inteligentní systémy (bakalářský, dobíhající pro nástupní ročníky před 2013) V 2
BIS(ECTS) Inteligentní systémy (bakalářský, dobíhající pro nástupní ročníky před 2013) V 2
BSI(ECTS) Softwarové inženýrství V 2
BMI(ECTS) Manažerská informatika V 2
BWM(ECTS) Web a multimedia V 2


Stránka vytvořena 22.9.2017 17:47:52, semestry: L/2016-7, Z,L/2017-8, Z/2018-9, připomínky k informační náplni zasílejte správci studijních plánů Návrh a realizace: I. Halaška (K336), J. Novák (K336)
Za obsah odpovídá: doc. Ing. Ivan Jelínek, CSc.