460-2001/07 – Algoritmy I (ALG I)

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í
		Jazyk výuky	čeština
Rok zavedení	2023/2024	Rok zrušení
Určeno pro fakulty	FEI	Určeno pro typy studia	bakalářské

Výuku zajišťuje
Os. čís.	Jméno	Cvičící	Přednášející
DOH089	Ing. Pavel Dohnálek, Ph.D.
DVO26	doc. Mgr. Jiří Dvorský, Ph.D.
KOT06	Ing. Martin Kot, Ph.D.
LUB0020	Ing. Tomáš Luber
VRO0018	Ing. David Vronka

Rozsah výuky pro formy studia
Forma studia	Zp.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

Seznámit studenty se technikami řešení problémů pomocí algoritmů. Po absolvování předmětu bude student schopen: definovat a popsat vybrané techniky řešení problémů pomocí algoritmů, demonstrovat tyto techniky na ukázkových problémech využívat tyto techniky pro řešení jiných problémů, pracovat s kombinacemi několika technik dohromady.

Vyučovací metody

Přednášky
Cvičení (v učebně)

Anotace

Tento předmět je jedním z úvodních kurzů programování. Předmět si klade za cíl seznámit studenty s technikami, strategiemi, řešení problémů pomocí algoritmů. Probírané algoritmy a datové struktury budou demonstrovány v jazyce C++. Studenti jsou vedeni k analýze algoritmizovaných problémů a k syntéze řešení z menších celků.

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. Vypracování několika domácích úkolů.

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ětu	Zkratka	Název	Povinnost
460-2052	UPR	Úvod do programování	Doporučená
460-2054	FPR	Funkcionální programování	Doporučená

Korekvizity

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

Osnova předmětu

Algoritmus. Strategie řešení problémů pomocí algoritmů. Významné typy řešených problémů. Analýza složitosti algoritmů. Strategie řešení problémů hrubou silou. Třídění výběrem, bublinové třídění. Sekvenční vyhledávání. Konvexní obal množiny bodů. Nalezení nejbližší dvojice bodů. Strategie řešení úplným prohledáváním. Problém obchodního cestujícího. Problém batohu. Průchody grafem. Strategie řešení sniž a vyřeš. Třídění vkládáním. Generování permutací a podmnožin. Vyhledávání půlením intervalu. Nalezení mediánu. Interpolační vyhledávání. Vyhledávání a vkládání do binárního vyhledávacího stromu. Strategie řešení rozděl a panuj. QuickSort. MergeSort. Konvexní obal množiny bodů. Nalezení nejbližší dvojice bodů. Náplň cvičení Analýza složitosti iterativních algoritmů. Analýza složitosti rekurzivních algoritmů. Implementace konvexního obalu množiny bodů. Implementace hledání dvojice nejbližších bodů. Problém obchodního cestujícího - experimenty s úplným prohledáváním. Využití průchodů grafem. Implementace algoritmů pro generování permutací a podmnožin. Experimenty s vyhledáváním půlením intervalu, interpolačním vyhledáváním. Nalezení mediánu. Implementace binárního vyhledávacího stromu. Implementace řešení strategií řešení rozděl a panuj.

Podmínky absolvování předmětu

Prezenční forma (platnost od: 2023/2024 zimní semestr)

Název úlohy	Typ úlohy	Max. 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	1
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. Účast na cvičeních - Rozsah účasti na cvičeních si student na začátku semestru dohodne s garantem předmětu.

Zobrazit historii

Kombinovaná forma (platnost od: 2023/2024 zimní semestr)

Název úlohy	Typ úlohy	Max. 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	1
Obhajoba projektu	Projekt	30	15	1
Závěrečná písemná práce	Písemka	40	21	2

Výskyt ve studijních plánech

Akademický rok	Program	Zaměření	Forma	Jazyk výuky	Konz. stř.	Ročník	Typ povinnosti
2025/2026	(B0613A140014) Informatika	TZI	K	čeština	Ostrava	1	povinný	stu. plán
2025/2026	(B0613A140014) Informatika	TZI	P	čeština	Ostrava	1	povinný	stu. plán
2024/2025	(B0613A140014) Informatika	TZI	P	čeština	Ostrava	1	povinný	stu. plán
2024/2025	(B0613A140014) Informatika	TZI	K	čeština	Ostrava	1	povinný	stu. plán
2023/2024	(B0613A140014) Informatika	TZI	K	čeština	Ostrava	1	povinný	stu. plán
2023/2024	(B0613A140014) Informatika	TZI	P	čeština	Ostrava	1	povinný	stu. plán

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

Název bloku	Akademický rok	Forma studia	Jazyk výuky	Ročník	Z	L	Typ bloku	Vlastník bloku

Hodnocení Výuky

2023/2024 letní