460-2003/04 – Algoritmy II (ALG II)
| Garantující katedra | Katedra informatiky | Kredity | 5 |
| Garant předmětu | doc. Mgr. Jiří Dvorský, Ph.D. | Garant verze předmětu | doc. Mgr. Jiří Dvorský, Ph.D. |
| Úroveň studia | pregraduální nebo graduální | Povinnost | volitelný odborný |
| Ročník | 2 | Semestr | zimní |
| | Jazyk výuky | čeština |
| Rok zavedení | 2019/2020 | Rok zrušení | |
| Určeno pro fakulty | FEI | Určeno pro typy studia | bakalářské |
Cíle předmětu vyjádřené dosaženými dovednostmi a kompetencemi
Cílem předmětu je seznámit studenty s objektově orientovaným programováním a rozvinout znalosti studentů do oblasti datových struktur. Po absolvování předmětu bude student schopen:
analyzovat zadaný problém z pozice OOP,
vytvořit a odladit program C++ s využitím OOP,
využívat binární stromy a hašovací tabulky,
posoudit efektivitu zvoleného řešení daného problému.
Vyučovací metody
Přednášky
Cvičení (v učebně)
Anotace
Tento předmět je pokračováním předmětu Algoritmy I. V tomto kurzu bude kombinován výklad objektově orientovaného programování s představením dalších často používaných datových struktur - binárních stromů a hašovacích tabulek. OOP je chápáno spíše směrem ke zvládnutí implementace nejrůznějších tabulek, seznamů s operacemi vkládání, následného vyhledávání a rušení elementů, než směrem k návrhu komplexnějších systémů. Tento cíl bude naplněn v kurzech zabývajících se softwarovým inženýrstvím.
Povinná literatura:
Doporučená literatura:
Další studijní materiály
Forma způsobu ověření studijních výsledků a další požadavky na studenta
Podmínky udělení zápočtu
Realizace a obhajoba projektu.
Programování jednoduchých aplikací na cvičeních.
Účast na cvičeních.
E-learning
Další požadavky na studenta
U studentů se předpokládá základní znalost jazyka C++ a středoškolské matematiky.
Prerekvizity
Korekvizity
Předmět nemá žádné korekvizity.
Osnova předmětu
Strategie řešení transformuj a vyřeš. Předtřídění dat. Gaussova eliminační metoda. AVL stromy.
Strategie řešení změnou reprezentace. Halda a třídění haldou. Hornerovo pravidlo. Výpočet mocniny.
Strategie řešení redukcí problému. Redukce na grafové problémy.
Záměna paměťové a časové složitosti (Space-time trade-off). Hašování. B-stromy.
Dynamické programování. Problém batohu. Floydův algoritmus.
Hladové algoritmy. Primův algoritmus. Dijkstrův algoritmus. Huffmanovo kódování.
Strategie řešení iterativním zlepšováním. Simplexová metoda.
Meze možností algoritmického řešení problémů. P, NP a NP-úplné problémy.
Prohledávání s návratem. Problém osmi dam.
Aproximační algoritmy pro NP-těžké problémy.
Náplň cvičení
Gaussova eliminační metoda. AVL stromy.
Implementace haldy, třídění haldou.
Hašovací tabulky.
B-tromy.
Dynamické programování. Floydův algoritmus
Hladové algoritmy. Primův algoritmus. Dijkstrův algoritmus.
Huffmanovo kódování.
Simplexová metoda.
Prohledávání s návratem. Problém osmi dam.
Aproximační algoritmy pro NP-těžké problémy.
Podmínky absolvování předmětu
Výskyt ve studijních plánech
Výskyt ve speciálních blocích
Hodnocení Výuky