460-2003/03 – 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í2015/2016Rok zrušení2019/2020
Určeno pro fakultyFEIUrčeno pro typy studiabakalářské
Výuku zajišťuje
Os. čís.JménoCvičícíPřednášející
ABD006 Ing. Hussam Abdulla, Ph.D.
Rozsah výuky pro formy studia
Forma studiaZp.zak.Rozsah
prezenční Klasifikovaný zápočet 2+2
kombinovaná Klasifikovaný zápočet 10+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. 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

Realizace a obhajoba projektu. Programování jednoduchých aplikací na cvičeních.

E-learning

Další požadavky na studenta

U studentů se předpokládá znalost středoškolské matematiky a uživatelská znalost počítačů.

Prerekvizity

Kód předmětuZkratkaNázevPovinnost
460-2001 ALG I Algoritmy I Povinná

Korekvizity

Předmět nemá žádné korekvizity.

Osnova předmětu

Náplň přednášek Úvodní přednáška - organizační záležitosti, souhrn nutných znalostí z předmětu Algoritmy I Lineární datové struktury - abstraktní datové struktury, zásobník, fronta, seznam Dynamická alokace paměti - pointery, operátory reference, dereference, alokování a dealokování paměti Spojová implementace lineárních datových struktur - využití OOP a dynamicky alokovaných struktur Grafy - základní pojmy, graf jako datová struktura, možnosti implementace grafu Algoritmy průchodů grafem - průchod grafu do hloubky a do šířky, aplikace průchodu grafem Binární vyhledávací stromy I - základní pojmy, vyhledávání Binární vyhledávací stromy II - vkládání, rušení vrcholů, průchody stromem Vyvážené a vícecestné stromy - AVL-stromy, red-black stromy. B-stromy Hašování - hašovací tabulky, metody řešení kolizí Vyhledávání v textu - vyhledávání jednoho a více vzorků, elementární lexikální analýza textu Jednoduchý překladač - překlad aritmetických a logických výrazů, postfixová notace a její interpretace pomocí zásobníku Techniky řešení problémů - rozděl a panuj, žravý algoritmus, dynamické programování Náplň počítačových cvičení Opakování z předmětu Algoritmy I Implementace zásobníku, fronty, seznamu v poli Dynamická alokace paměti Spojová implementace seznamu Grafy, možnosti implementace grafů Průchody grafem Binární stromy Využití hašovacích tabulek Vyhledávání v textu Překladač založený na rekurzivním sestupu Náplň projektů Zadání projektů budou směřovat ke zvládnutí OOP.

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.FormaJazyk výuky Konz. stř.RočníkZLTyp povinnosti
2019/2020 (B2660) Počítačové systémy pro průmysl 21. století P angličtina Ostrava 1 povinný stu. plán
2019/2020 (B2647) Informační a komunikační technologie P angličtina Ostrava 1 povinný stu. plán
2019/2020 (B2647) Informační a komunikační technologie K angličtina Ostrava 1 povinný stu. plán
2018/2019 (B2660) Počítačové systémy pro průmysl 21. století P angličtina Ostrava 1 povinný stu. plán
2018/2019 (B3973) Automobilové elektronické systémy P angličtina Ostrava 1 povinný stu. plán
2018/2019 (B2647) Informační a komunikační technologie P angličtina Ostrava 1 povinný stu. plán
2018/2019 (B2647) Informační a komunikační technologie K angličtina Ostrava 1 povinný stu. plán
2017/2018 (B2647) Informační a komunikační technologie P angličtina Ostrava 1 povinný stu. plán
2017/2018 (B2647) Informační a komunikační technologie K angličtina Ostrava 1 povinný stu. plán
2017/2018 (B2660) Počítačové systémy pro průmysl 21. století P angličtina Ostrava 1 povinný stu. plán
2017/2018 (B3973) Automobilové elektronické systémy P angličtina Ostrava 1 povinný stu. plán
2016/2017 (B2647) Informační a komunikační technologie P angličtina Ostrava 1 povinný stu. plán
2016/2017 (B2647) Informační a komunikační technologie K angličtina Ostrava 1 povinný stu. plán
2016/2017 (B2660) Počítačové systémy pro průmysl 21. století P angličtina Ostrava 1 povinný stu. plán
2015/2016 (B2647) Informační a komunikační technologie P angličtina Ostrava 1 povinný stu. plán
2015/2016 (B2647) Informační a komunikační technologie K angličtina Ostrava 1 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
V - ECTS - bc. 2018/2019 prezenční angličtina volitelný odborný 401 - Studijní oddělení FEI stu. blok
V - ECTS - bc. 2017/2018 prezenční angličtina volitelný odborný 401 - Studijní oddělení FEI stu. blok
V - ECTS - bc. 2016/2017 prezenční angličtina volitelný odborný 401 - Studijní oddělení FEI stu. blok
V - ECTS - bc. 2015/2016 prezenční angličtina volitelný odborný 401 - Studijní oddělení FEI stu. blok