460-2003/02 – 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ýukyčeština
Rok zavedení2013/2014Rok 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í
BIE0026 Ing. Martin Bielik
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
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 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.

Další studijní materiály

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á
460-2055 OOP Objektově orientované programování Doporučená

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

Prezenční forma (platnost od: 2013/2014 zimní semestr, platnost do: 2019/2020 letní 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ý test znalostí Jiný typ úlohy 20  10
        Obhajoba projektu Projekt 40  21
        Závěrečná písemná práce Písemka 40  20
Rozsah povinné účasti: Student musí splnit všechny definované úlohy alespoň za minimální počet bodů.

Zobrazit historii

Podmínky absolvování předmětu a účast na cvičeních v rámci ISP:

Zobrazit historii

Výskyt ve studijních plánech

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

Hodnocení Výuky



2019/2020 letní
2018/2019 letní
2017/2018 letní
2016/2017 letní
2015/2016 letní
2014/2015 letní
2013/2014 letní