456-0521/01 – Základy algoritmizace (ZAL)

Garantující katedraKatedra informatikyKredity6
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í1999/2000Rok zrušení2008/2009
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.
DVO26 doc. Mgr. Jiří Dvorský, Ph.D.
GAJ03 doc. Ing. Petr Gajdoš, Ph.D.
HLA168 Ing. Lukáš Hlaváček
CHO247 Ing. Peter Chovanec, Ph.D.
KRO183 Ing. Martin Krolikowski
MIN01 Ing. Marian Mindek, Ph.D.
OH140 RNDr. Eliška Ochodková, Ph.D.
PLA06 doc. Ing. Jan Platoš, Ph.D.
SIK107 Ing. Rostislav Sikora
VYM036 Ing. Michal Výmola
Rozsah výuky pro formy studia
Forma studiaZp.zak.Rozsah
prezenční Zápočet a zkouška 2+2
kombinovaná Zápočet a zkouška 2+2

Cíle předmětu vyjádřené dosaženými dovednostmi a kompetencemi

Cílem předmětu je uvést studenta do základů algoritmů třídění, vyhledávání a základních datových struktur. Posluchač by měl být schopen vyjádřit algoritmus ve formě zdrojového textu programu. Student bude schopen psát jednoduché programy pomocí OOP s využitím datových struktur.

Vyučovací metody

Anotace

Předmět je určen pro studenty prvního ročníku prezenčního studia. V předmětu se studenti seznámí se základními algoritmy pro třídění, vyhledávání v datech a v textu. Dále jsou probírány elementární datové struktury. Studenti si osvojí základní pojmový aparát, schopnost algoritmicky myslet a vybudují fundamenty mentální báze znalostí, což je nezbytný předpoklad pro další studium informatiky. Nemalý důraz je kladen na praktickou implementaci probíraných algoritmů a datových struktur.

Povinná literatura:

Studijní opora (skripta) pro ZAL Wirth, N.: Algoritmy a štruktúry údajov, Alfa, Bratislava 1989. Sedgewick R.: Algoritmy v C, části 1-4, SoftPress, Praha, 2003 Existuje i v anglické verzi, náročná, ale vynikající kniha. Wróblewski P.: Algoritmy. Datové struktury a programovací techniky, Computer Press, Praha 2003

Doporučená literatura:

Topfer, P.: Algoritmy a programovací techniky, Prometheus, Praha 1995. Virius, M.: Základy algoritmizace, ČVUT Praha, 1997, skripta. Honzík, J. a kolektiv: Programovací techniky, VUT Brno, 1987, skripta. Harel, D.: Algorithmics, The Spirits of Computing, Addison-Wesley Publishing Company, 1993. Sedgewick, R.: Algorithms in C++, Addison-Wesley Publishing Company, 1992. Wood, D.: Data Structures, Algorithms and Performance, Addison-Wesley Publishing Company, 1993. Cormen, Leiserson, Rievest: Introduction to Algorithms, MIT Press, 2001. Obecně jakákoliv učebnice jazyka Java.

Forma způsobu ověření studijních výsledků a další požadavky na studenta

Podmínky udělení zápočtu: Za zápočet je možné získat maximálně 40 bodů. Zápočet je udělen na základě testu z programování a semestrálního projektu. Za test z programování je nutné získat aspoň 5 bodů, za projekt aspoň 16. Celkem minimálně 21 bodů. Za písemnou zkoušku je možné získat 60 bodů, minimálně 30 bodů.

E-learning

Další požadavky na studenta

Prerekvizity

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

Korekvizity

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

Osnova předmětu

Přednášky: Úvodní přednáška, organizační záležitosti, seznámení se z předmětem Pojem algoritmu a složitosti algoritmu Lineární datové struktury - zásobník, fronta, seznam Třídění I. Třídění II. Binární vyhledávací stromy I. Binární vyhledávací stromy II. Binární vyhledávací stromy - vyvážené varianty apod. Hašování Pokročilé datové struktury - skip-list, splay stromy Vyhledávání řetězců I. Vyhledávání řetězců II. Projekty: V průběhu semestru bude zpracován semestrální projekt. Počítačové laboratoře: Opakování konstrukcí jazyka Java, řešení elementárních příkladů Algoritmy vyhledávání v poli Implementace zásobníku, fronty, seznamu Implementace třídících algoritmů I Implementace třídících algoritmů II, implementace s využitím rozhraní Comparable Implementace binárních vyhledávacích stromů Binární vyhledávací stromy - využití Binární vyhledávací stromy (vyvážené varianty), ukázka práce, částečná implementace Hašování - implementace jednoduché hašovací tabulky, testování hašovacích funkcí Práce s vyhladávacími algoritmy (pattern matching) V průběhu počítačových cvičení studenti zpracovávají zápočtové testy a konzultují se cvičícími své semestrální projekty.

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

Kombinovaná forma (platnost od: 1960/1961 letní semestr, platnost do: 2008/2009 letní semestr)
Název úlohyTyp úlohyMax. počet bodů
(akt. za podúlohy)
Min. počet bodů
Zápočet a zkouška Zápočet a zkouška 100 (100) 51
        Zápočet Zápočet 20 (20) 0
                Písemka Písemka 20  0
        Zkouška Zkouška 80 (80) 0
                Písemná zkouška Písemná zkouška 80  0
Rozsah povinné účasti:

Zobrazit historii

Výskyt ve studijních plánech

Akademický rokProgramObor/spec.Spec.FormaJazyk výuky Konz. stř.RočníkZLTyp povinnosti
2008/2009 (B2646) Informační technologie (1103R021) Počítačová matematika P čeština Ostrava 1 povinný stu. plán
2008/2009 (B2646) Informační technologie (1103R021) Počítačová matematika K čeština Ostrava 1 povinný stu. plán
2008/2009 (B2647) Informační a komunikační technologie (1103R031) Výpočetní matematika P čeština Ostrava 1 povinný stu. plán
2008/2009 (B2647) Informační a komunikační technologie (2601R013) Telekomunikační technika P čeština Ostrava 1 povinný stu. plán
2008/2009 (B2647) Informační a komunikační technologie (2612R025) Informatika a výpočetní technika P čeština Ostrava 1 povinný stu. plán
2008/2009 (B2647) Informační a komunikační technologie (2612R059) Mobilní technologie P čeština Ostrava 1 povinný stu. plán
2008/2009 (B2647) Informační a komunikační technologie P čeština Ostrava 1 povinný stu. plán
2008/2009 (B2647) Informační a komunikační technologie (1103R031) Výpočetní matematika K čeština Ostrava 1 povinný stu. plán
2008/2009 (B2647) Informační a komunikační technologie (2601R013) Telekomunikační technika K čeština Ostrava 1 povinný stu. plán
2008/2009 (B2647) Informační a komunikační technologie (2612R025) Informatika a výpočetní technika K čeština Ostrava 1 povinný stu. plán
2008/2009 (B2647) Informační a komunikační technologie (2612R059) Mobilní technologie K čeština Ostrava 1 povinný stu. plán
2008/2009 (B2647) Informační a komunikační technologie K čeština Ostrava 1 povinný stu. plán
2007/2008 (B2646) Informační technologie (1103R021) Počítačová matematika P čeština Ostrava 1 povinný stu. plán
2007/2008 (B2646) Informační technologie (1103R021) Počítačová matematika K čeština Ostrava 1 povinný stu. plán
2007/2008 (B2646) Informační technologie (2612R025) Informatika a výpočetní technika P čeština Ostrava 1 povinný stu. plán
2007/2008 (B2646) Informační technologie (2612R025) Informatika a výpočetní technika K čeština Ostrava 1 povinný stu. plán
2007/2008 (B2646) Informační technologie (2612R059) Mobilní technologie P čeština Ostrava 1 povinný stu. plán
2007/2008 (B2646) Informační technologie (2612R059) Mobilní technologie K čeština Ostrava 1 povinný stu. plán
2007/2008 (B2647) Informační a komunikační technologie (1103R031) Výpočetní matematika P čeština Ostrava 1 povinný stu. plán
2007/2008 (B2647) Informační a komunikační technologie (2601R013) Telekomunikační technika P čeština Ostrava 1 povinný stu. plán
2007/2008 (B2647) Informační a komunikační technologie (2612R025) Informatika a výpočetní technika P čeština Ostrava 1 povinný stu. plán
2007/2008 (B2647) Informační a komunikační technologie (2612R059) Mobilní technologie P čeština Ostrava 1 povinný stu. plán
2007/2008 (B2647) Informační a komunikační technologie (1103R031) Výpočetní matematika K čeština Ostrava 1 povinný stu. plán
2007/2008 (B2647) Informační a komunikační technologie (2601R013) Telekomunikační technika K čeština Ostrava 1 povinný stu. plán
2007/2008 (B2647) Informační a komunikační technologie (2612R025) Informatika a výpočetní technika K čeština Ostrava 1 povinný stu. plán
2007/2008 (B2647) Informační a komunikační technologie (2612R059) Mobilní technologie K čeština Ostrava 1 povinný stu. plán
2006/2007 (B2646) Informační technologie (1103R021) Počítačová matematika P čeština Ostrava 1 povinný stu. plán
2006/2007 (B2646) Informační technologie (1103R021) Počítačová matematika K čeština Ostrava 1 povinný stu. plán
2006/2007 (B2646) Informační technologie (2612R025) Informatika a výpočetní technika P čeština Ostrava 1 povinný stu. plán
2006/2007 (B2646) Informační technologie (2612R025) Informatika a výpočetní technika K čeština Ostrava 1 povinný stu. plán
2006/2007 (B2646) Informační technologie (2612R059) Mobilní technologie P čeština Ostrava 1 povinný stu. plán
2006/2007 (B2646) Informační technologie (2612R059) Mobilní technologie K čeština Ostrava 1 povinný stu. plán
2006/2007 (B2647) Informační a komunikační technologie (1103R031) Výpočetní matematika P čeština Ostrava 1 povinný stu. plán
2006/2007 (B2647) Informační a komunikační technologie (2601R013) Telekomunikační technika P čeština Ostrava 1 povinný stu. plán
2006/2007 (B2647) Informační a komunikační technologie (2612R025) Informatika a výpočetní technika P čeština Ostrava 1 povinný stu. plán
2006/2007 (B2647) Informační a komunikační technologie (2612R059) Mobilní technologie P čeština Ostrava 1 povinný stu. plán
2006/2007 (B2647) Informační a komunikační technologie (1103R031) Výpočetní matematika K čeština Ostrava 1 povinný stu. plán
2006/2007 (B2647) Informační a komunikační technologie (2601R013) Telekomunikační technika K čeština Ostrava 1 povinný stu. plán
2006/2007 (B2647) Informační a komunikační technologie (2612R025) Informatika a výpočetní technika K čeština Ostrava 1 povinný stu. plán
2006/2007 (B2647) Informační a komunikační technologie (2612R059) Mobilní technologie K čeština Ostrava 1 povinný stu. plán
2005/2006 (B2646) Informační technologie (1103R021) Počítačová matematika P čeština Ostrava 1 povinný stu. plán
2005/2006 (B2646) Informační technologie (2612R025) Informatika a výpočetní technika P čeština Ostrava 1 povinný stu. plán
2005/2006 (B2646) Informační technologie (2612R025) Informatika a výpočetní technika K čeština Ostrava 1 povinný stu. plán
2005/2006 (B2646) Informační technologie (1103R021) Počítačová matematika K čeština Ostrava 1 povinný stu. plán
2005/2006 (B2646) Informační technologie (2612R059) Mobilní technologie P čeština Ostrava 1 povinný stu. plán
2005/2006 (B2646) Informační technologie (2612R059) Mobilní technologie K čeština Ostrava 1 povinný stu. plán
2004/2005 (B2646) Informační technologie (1103R021) Počítačová matematika P čeština Ostrava 1 povinný stu. plán
2004/2005 (B2646) Informační technologie (2612R025) Informatika a výpočetní technika P čeština Ostrava 1 povinný stu. plán
2004/2005 (B2646) Informační technologie (2612R025) Informatika a výpočetní technika K čeština Ostrava 1 povinný stu. plán
2004/2005 (B2646) Informační technologie (1103R021) Počítačová matematika K čeština Ostrava 1 povinný stu. plán
2004/2005 (B2646) Informační technologie (2612R059) Mobilní technologie P čeština Ostrava 1 povinný stu. plán
2004/2005 (B2646) Informační technologie (2612R059) Mobilní technologie K čeština Ostrava 1 povinný stu. plán
2003/2004 (B2646) Informační technologie (1103R021) Počítačová matematika P čeština Ostrava 1 povinný stu. plán
2003/2004 (B2646) Informační technologie (2612R025) Informatika a výpočetní technika P čeština Ostrava 1 povinný stu. plán
2003/2004 (B2646) Informační technologie (2612R025) Informatika a výpočetní technika K čeština Ostrava 1 povinný stu. plán
2003/2004 (B2646) Informační technologie (1103R021) Počítačová matematika 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