460-2003/05 – Algoritmy II (ALG II)

Garantující katedraKatedra informatikyKredity5
Garant předmětudoc. Mgr. Jiří Dvorský, Ph.D.Garant verze předmětudoc. Mgr. Jiří Dvorský, Ph.D.
Úroveň studiapregraduální nebo graduálníPovinnostpovinný
Ročník1Semestrletní
Jazyk výukyangličtina
Rok zavedení2019/2020Rok zrušení
Určeno pro fakultyFEIUrčeno pro typy studiabakalářské
Výuku zajišťuje
Os. čís.JménoCvičícíPřednášející
DVO26 doc. Mgr. Jiří Dvorský, Ph.D.
Rozsah výuky pro formy studia
Forma studiaZp.zak.Rozsah
prezenční Klasifikovaný zápočet 2+2

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:

LEVITIN, Anany. Introduction to the Design and Analysis of Algorithms. 3rd ed. Boston: Pearson, 2012. ISBN 978-0-13-231681-1. CORMEN, Thomas H. Introduction to algorithms. 2nd ed. Cambridge, Mass.: MIT Press, 2001. ISBN 02-620-3293-7. SEDGEWICK, Robert. Algoritmy v C. Praha: SoftPress, 2003. ISBN 80-864-9756-9. WRÓBLEWSKI, Piotr. Algoritmy. Brno: Computer Press, 2015. ISBN 978-80-251-4126-7. WIRTH, N. Algoritmy a štruktúry údajov, Alfa, Bratislava 1989. Studijní opora (skripta), dostupné na stránkách garanta předmětu, www.cs.vsb.cz/dvorsky

Doporučená literatura:

STROUSTRUP, Bjarne. C++ programovací jazyk. Praha: Softwarové Aplikace a Systémy, 1997. ISBN 80-901-5072-1. VIRIUS, Miroslav. Pasti a propasti jazyka C++. 2., aktualiz. a rozš. vyd. Brno: CP Books, 2005. ISBN 80-251-0509-1. SCHILDT, Herbert. Nauč se sám C++: [poznej, vyzkoušej, používej]. Praha: SoftPress, 2001. ISBN 80-864-9713-5. ECKEL, Bruce. Myslíme v jazyku C++. Praha: Grada, 2000. Knihovna programátora (Grada). ISBN 80-247-9009-2.

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á absolvování předmětu Algoritmy I a dle základní znalost jazyka C++ a středoškolské matematiky.

Prerekvizity

Kód předmětuZkratkaNázevPovinnost
460-2001 ALG I Algoritmy I Povinná
460-2055 OOP Objektově orientované programování Doporučená

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

Podmínky absolvování jsou definovány pouze pro konkrétní verzi předmětu a formu studia

Výskyt ve studijních plánech

Akademický rokProgramObor/spec.Spec.ZaměřeníFormaJazyk výuky Konz. stř.RočníkZLTyp povinnosti
2024/2025 (B0613A140010) Informatika TZI P angličtina Ostrava 2 povinný stu. plán
2023/2024 (B0613A140010) Informatika TZI P angličtina Ostrava 2 povinný stu. plán
2023/2024 (B0541A170009) Výpočetní a aplikovaná matematika P angličtina Ostrava 2 volitelný odborný stu. plán
2022/2023 (B0613A140010) Informatika TZI P angličtina Ostrava 2 povinný stu. plán
2022/2023 (B0541A170009) Výpočetní a aplikovaná matematika P angličtina Ostrava 2 volitelný odborný stu. plán
2021/2022 (B0613A140010) Informatika TZI P angličtina Ostrava 2 povinný stu. plán
2021/2022 (B0541A170009) Výpočetní a aplikovaná matematika P angličtina Ostrava 2 volitelný odborný stu. plán
2020/2021 (B0613A140010) Informatika TZI P angličtina Ostrava 2 povinný stu. plán
2020/2021 (B2647) Informační a komunikační technologie P angličtina Ostrava 1 povinný stu. plán
2020/2021 (B0541A170009) Výpočetní a aplikovaná matematika P angličtina Ostrava 2 volitelný odborný stu. plán
2019/2020 (B0613A140010) Informatika TZI P angličtina Ostrava 2 povinný stu. plán
2019/2020 (B0541A170009) Výpočetní a aplikovaná matematika P angličtina Ostrava 2 volitelný odborný stu. plán

Výskyt ve speciálních blocích

Název blokuAkademický rokForma studiaJazyk výuky RočníkZLTyp blokuVlastník bloku

Hodnocení Výuky

Předmět neobsahuje žádné hodnocení.