Algoritmy I

Typ studia	bakalářské
Jazyk výuky	angličtina
Kód	460-2001/08
Zkratka	ALG I
Název předmětu česky	Algoritmy I
Název předmětu anglicky	Algorithms I
Kreditů	5
Garantující katedra	Katedra informatiky
Garant předmětu	doc. Mgr. Jiří Dvorský, Ph.D.

Subject syllabus

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.

Literature

LEVITIN, Anany. Introduction to the Design and Analysis of Algorithms. 3rd ed. Boston: Pearson, 2012. .
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. .
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

Advised literature

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.

zpět na vyhledávání