Algoritmy

• 39 hod. přednášky
• 13 hod. projekty

• 51 bodů závěrečná zkouška (písemná část)
• 14 bodů půlsemestrální test (písemná část)
• 35 bodů projekty

• Porozumí základním principům a významu složitosti algoritmů.
• Seznámí se se základními abstraktními datovými typy a strukturami, naučí se je implementovat.
• Naučí se rekurzivní a nerekurzivní zápisy základních algoritmů.
• Seznámí se s různými variantami vyhledávacích tabulek a porozumí jejich vlastnostem.
• Naučí se vytvářet a analyzovat algoritmy vyhledávání a řazení.
• Student se naučí odborné terminologii v českém i anglickém jazyce.
• Student se naučí vytvářet malé projekty v malém týmu.
• Student se naučí prezentaci a obhajobě výsledků v malém projektu.
• Student porozumí významu metod dokazování správnosti programů a tvorby dokázaných programů.

Student porozumí základním principům složitosti algoritmů a bude je schopen využít při tvorbě programů. Student porozumí základním abstraktním datovým typům a strukturám, naučí se je implementovat a používat. Student se naučí  rekurzivní a nerekurzivní zápisy základních algoritmů a bude schopen je využívat při tvorbě programů. Student se naučí vytvářet a analyzovat algoritmy vyhledávání a řazení. Student porozumí základním algoritmům pro vyhledávání v textu a základním grafovým algoritmům. Student se seznámí s rekurzivním způsobem řešení problémů a se základy dynamického programování. Student porozumí principům metod dokazování správnosti programů a znalosti bude schopen používat při tvorbě programů.

Téměř všechny počítačové programy při své činnosti potřebují ukládat data. Studenti se v tomto předmětu seznámí s datovými strukturami, které se v praxi používají nejčastěji a také s jejich vlastnostmi. To jim později umožní vybrat datovou strukturu nejvhodnější pro daný účel. Studenti se také seznámí s algoritmy, které jsou s danými datovými strukturami spojeny a naučí se je analyzovat a hodnotit prostřednictvím asymptotické časové složitosti.

• Základy programování (IZP)

• Znalost základů programování v procedurálně orientovaném programovacím jazyce.
• Středoškolské znalosti z matematiky.

• Mareš, M., Valla, T.: Průvodce labyrintem algoritmů, CZ.NIC, 2017, ISBN 978-80-88168-19-5, http://pruvodce.ucw.cz/
• Honzík, J., Hruška, T., Máčel, M.: Vybrané kapitoly z programovacích technik, Ed. stř. VUT Brno, 1991
• Cormen, T.H., Leiserson, Ch.E., Rivest, R.L.: Introduction to Algorithms, Cambridge: MIT Press, 2009
• Knuth, D.: The Art of Computer programming, Vol.1,2,3. Addison Wesley, 1968
• Wirth, N.: Alorithms+Data Structures=Programs, Prentice Hall, 1976
• Aho A.V., Hoppcroft J.E., Ullman J.D.: Data Structures and Algorithms, Addison Wesley, 1983
• Baase, S.: Computer Algorithms - Introduction to Design and Analysis. Addison Wesley, 1998
• Sedgewick,R.:Algoritmy v C, Addison Wesley 1998, Softpress 2003

1. Přehled datových struktur. Časová složitost algoritmů.
2. Abstraktní datový typ a jeho specifikace. Specifikace, implementace a použití ADT seznam.
3. Specifikace, implementace a použití ADT zásobník, fronta. Vyčíslení výrazů s použitím zásobníku.
4. Algoritmy nad binárním stromem.
5. Vyhledávání, sekvenční, v poli, binární vyhledávání, binární vyhledávací stromy, AVL strom.
6. Stromy s více klíči ve vrcholech. Vyhledávání v tabulkách s rozptýlenými položkami.
7. Řazení, principy, bez přesunu položek, s vícenásobným klíčem.
8. Známé metody řazení polí I
9. Známé metody řazení polí II.
10. Rekurze a dynamické programování.
11. Způsoby hodnocení časové složitosti algoritmů.
12. Grafové algoritmy.
13. Dokazování správnosti programů.

• Dvě domácí úlohy - implementace operací vybraných ADT.
• Projekt s miniobhajobou skupiny studentů.

• Domácí úlohy - 20 bodů
• Půlsemestrální písemná zkouška - 14 bodů
• Hodnocený projekt s obhajobou - 15 bodů
• Závěrečná písemná zkouška - 51 bodů; Pro získání bodů ze závěrečné písemné zkoušky je nutné zkoušku vypracovat tak, aby byla hodnocena nejméně 24 body. V opačném případě bude zkouška hodnocena 0 body.

Pokud v průběhu semestru student onemocní nebo se vyskytne jiná překážka ve studiu, je třeba tuto překážku řádně ohlásit a doložit. Pak k ní lze přihlédnout a přizpůsobit jí hodnocení:

• U domácí úlohy může student požádat příslušného učitele o přiměřené prodloužení termínu pro odevzdání domácí úlohy.
• Pokud se student nemohl zúčastnit půlsemestrální zkoušky, může svého přednášejícího požádat, aby body za půlsemestrální zkoušku byly odvozeny od bodového zisku u prvního termínu zkoušky, kterého se zúčastní. Podmínkou pro přistoupení k tomuto termínu zkoušky je zisk alespoň 14 bodů za domácí úlohy a projekt.
• Pokud se student nemůže zúčastnit obhajoby projektu a ostatní členové týmu s tím vysloví souhlas, může získat za obhajobu stejný počet bodů jako na obhajobě přítomní členové týmu.

• získání minimálně 20 bodů za semestr

Pokud bude odhaleno plagiátorství nebo nedovolená spolupráce na projektech či domácích úlohách, zápočet nebude udělen a dále bude zváženo zahájení disciplinárního řízení.