460-2003/04 – 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íPovinnostvolitelný odborný
Ročník2Semestrzimní
Jazyk výukyčeš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.
FAL0046 Ing. Jan Faltýnek
FAS01 Ing. Radoslav Fasuga, Ph.D.
MAC0463 Ing. Michael Machů
Rozsah výuky pro formy studia
Forma studiaZp.zak.Rozsah
prezenční Klasifikovaný zápočet 2+2
kombinovaná Klasifikovaný zápočet 14+0

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á 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

Kombinovaná forma (platnost od: 2019/2020 zimní semestr)
Název úlohyTyp úlohyMax. počet bodů
(akt. za podúlohy)		Min. počet bodůMax. počet pokusů
Klasifikovaný zápočet Klasifikovaný zápočet 100 (100) 51 3
        Průběžná aktivita Jiný typ úlohy 30  15 2
        Obhajoba projektu Projekt 30  15 1
        Závěrečná písemná práce Písemka 40  21 2
Rozsah povinné účasti: Účast na cvičeních je povinná a je kontrolována. S rozsahem povinné účastí seznámí studenty garant předmětu na začátku semestru.

Zobrazit historii

Podmínky absolvování předmětu a účast na cvičeních v rámci ISP: Podmínky absolvování předmětu - Splnění všech povinných úkolů v individuálně dohodnutých termínech.

Zobrazit historii

Výskyt ve studijních plánech

Akademický rokProgramObor/spec.Spec.ZaměřeníFormaJazyk výuky Konz. stř.RočníkZLTyp povinnosti
2023/2024 (B0613A140014) Informatika TZI K čeština Ostrava 2 povinný stu. plán
2023/2024 (B0613A140014) Informatika TZI P čeština Ostrava 2 povinný stu. plán
2023/2024 (B0541A170008) Výpočetní a aplikovaná matematika P čeština Ostrava 2 volitelný odborný stu. plán
2023/2024 (B0541A170008) Výpočetní a aplikovaná matematika K čeština Ostrava 2 volitelný odborný stu. plán
2022/2023 (B0613A140014) Informatika TZI K čeština Ostrava 2 povinný stu. plán
2022/2023 (B0613A140014) Informatika TZI P čeština Ostrava 2 povinný stu. plán
2022/2023 (B0541A170008) Výpočetní a aplikovaná matematika K čeština Ostrava 2 volitelný odborný stu. plán
2022/2023 (B0541A170008) Výpočetní a aplikovaná matematika P čeština Ostrava 2 volitelný odborný stu. plán
2021/2022 (B0613A140014) Informatika TZI P čeština Ostrava 2 povinný stu. plán
2021/2022 (B0613A140014) Informatika TZI K čeština Ostrava 2 povinný stu. plán
2021/2022 (B0541A170008) Výpočetní a aplikovaná matematika P čeština Ostrava 2 volitelný odborný stu. plán
2021/2022 (B0541A170008) Výpočetní a aplikovaná matematika K čeština Ostrava 2 volitelný odborný stu. plán
2021/2022 (B2660) Počítačové systémy pro průmysl 21. století P čeština Ostrava 1 povinný stu. plán
2020/2021 (B0613A140014) Informatika TZI K čeština Ostrava 2 povinný stu. plán
2020/2021 (B0613A140014) Informatika TZI P čeština Ostrava 2 povinný stu. plán
2020/2021 (B2660) Počítačové systémy pro průmysl 21. století P čeština Ostrava 1 povinný stu. plán
2020/2021 (B2647) Informační a komunikační technologie P čeština Ostrava 1 povinný stu. plán
2020/2021 (B2647) Informační a komunikační technologie K čeština Ostrava 1 povinný stu. plán
2020/2021 (B0541A170008) Výpočetní a aplikovaná matematika P čeština Ostrava 2 volitelný odborný stu. plán
2020/2021 (B0541A170008) Výpočetní a aplikovaná matematika K čeština Ostrava 2 volitelný odborný stu. plán
2019/2020 (B0541A170008) Výpočetní a aplikovaná matematika P čeština Ostrava 2 volitelný odborný stu. plán
2019/2020 (B0541A170008) Výpočetní a aplikovaná matematika K čeština Ostrava 2 volitelný odborný stu. plán
2019/2020 (B0613A140014) Informatika TZI P čeština Ostrava 2 povinný stu. plán
2019/2020 (B0613A140014) Informatika TZI K čeština Ostrava 2 povinný 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



2022/2023 zimní
2021/2022 zimní
2020/2021 zimní