Popis předmětu - B4B33ALG

Přehled studia | Přehled oborů | Všechny skupiny předmětů | Všechny předměty | Seznam rolí | Vysvětlivky               Návod
B4B33ALG Algoritmizace
Role:PV, P Rozsah výuky:2P+2C
Katedra:13133 Jazyk výuky:CS
Garanti:Genyk-Berezovskyj M. Zakončení:Z,ZK
Přednášející:Genyk-Berezovskyj M., Průša D. Kreditů:6
Cvičící:Osob je mnoho Semestr:Z

Webová stránka:

https://cw.fel.cvut.cz/wiki/courses/B4B33ALG

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í.

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í.

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

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

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

Požadavky:

Programování 1

Poznámka:

Rozsah výuky v kombinované formě studia: 14p+6c

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
BPOI_BO_2018 Před zařazením do oboru P 3
BPOI4_2018 Počítačové hry a grafika P 3
BPOI3_2018 Software P 3
BPOI2_2018 Internet věcí P 3
BPOI1_2018 Základy umělé inteligence a počítačových věd P 3
BPBIO_2018 Před zařazením do oboru PV 5
BPOI1_2016 Informatika a počítačové vědy P 3
BPOI_BO_2016 Před zařazením do oboru P 3
BPOI4_2016 Počítačové hry a grafika P 3
BPOI3_2016 Software P 3
BPOI2_2016 Internet věcí P 3

Stránka vytvořena 8.10.2024 17:50:55, semestry: L/2023-4, L/2024-5, Z/2025-6, Z/2024-5, 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. RNDr. Veronika Sobotíková, CSc.