Detail předmětu
Algoritmy
IAL Ak. rok 2013/2014 zimní semestr 5 kreditů
Přehled základních datových struktur a jejich použití. Principy dynamického přidělování paměti. Specifikace abtraktních datových typů (ADT). Specifikace a implementace ADT: seznamy, zásobník, fronta, množina, pole, vyhledávací tabulka, graf, binární strom. Algoritmy nad binárním stromem. Vyhledávání: sekvenční, v neseřazeném a seřazeném poli, vyhledávání se zarážkou, binární vyhledávání, binární vyhledávácí strom, vyvážený strom (AVL). Vyhledávání v tabulkách s rozptýlenými položkami. Řazení, principy, řazení bez přesunu položek, řazení podle více klíčů. Nejznámější metody řazení: Select-sort, Bubble-sort, Heap-sort, Insert-sort a jeho varianty, Shell-sort, Quick sort v rekurzívní a nerekurzívní notaci, Merge-sort, List-merge-sort, Radix-sort. Sekvenční metody řazení. Rekurze a algoritmy s návratem. Vyhledávání podřetězců v textu. Dokazování programů, tvorba dokázaných programů.
5 kreditů, t.j. cca 125-150 hodin představuje studijní zátěž:
- 39 hodin přednášek
- 26 hodin 2 domácí úlohy
- 35 hodin práce na projektu
- 20 hodin průběžné studium
- 30 hodin příprava na půlsemestrální a závěrečnou zkoušku
Garant předmětu
Jazyk výuky
Zakončení
Rozsah
- 39 hod. přednášky
- 13 hod. projekty
Zajišťuje ústav
Získané dovednosti, znalosti a kompetence z předmětu
- Student porozumí významu metod dokazování správnosti programů a s tvorby dokázaných programů.
- 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 a používat.
- Seznámí se s principy dynamického přidělování paměti a naučí se je používat na modelovém systému.
- Naučí se rekurzívní a nerekurzívní zápisy základních algoritmů.
- 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
Cíle předmětu
Student porozumí principům metod dokazování správnosti programů (Witrh) a tvorby dokázaných programů (Dijkstra) a znalosti bude schopen používat při tvorbě programů. Student porozumí základním principům složitosti algoritmů a bude je schopen využít při tvorbě programů. Student porozumí principům dynamického přidělování paměti a naučí se je používat na modelovém systému. Student porozumí základním abstraktním datovým typům a strukturami, naučí se je implementovat a používat. Studen se naučí rekurzívní a nerekurzívní zápisy základních algoritmů a bude schopen je využívat při tvorbě programů. Student se naučí se vytvářet a analyzovat algoritmy vyhledávání a řazení.
Doporučené prerekvizity
- Základy programování (IZP)
Požadované prerekvizitní znalosti a dovednosti
- Znalost základů programování v procedurálně orientovaném programovacím jazyce.
- Středoškolské znalosti z matematiky
Literatura studijní
- Honzík, J., Hruška, T., Máčel, M.: Vybrané kapitoly z programovacích technik, Ed.stř.VUT Brno,1991.
Literatura referenční
- Knuth, D.: The Art of Computer programming, Vol.1,2,3. Addison Wesley, 1968
- Wirth, N.: Alorithms+Data Structures=Programs, Prentice Hall, 1976
- Horovitz, Sahni: Fundamentals of Data Structures.
- Amsbury, W: Data Structures: From Arrays to Priority Queues.
- Cormen, T.H., Leiserson, Ch.E., Rivest, R.L.: Introduction to Algorithms.
- Aho A.V., Hoppcroft J.E., Ullman J.D.: Data Structures and Algorithms.
- Kruse, R.L.: Data Structures and Program Design. Prentice- Hall,Inc. 1984
- Baase, S.: Computer Algorithms - Introduction to Design and Analysis. Addison Wesley, 1998
- Sedgewick,R.:Algoritmy v C. (Základy. Datové struktury. Třídění. Vyhledávání.) Addison Wesley 1998. Softpress 2003.
Osnova přednášek
- Základy algoritmického jazyka. Přehled datových struktur. Abstraktní datový typ a jeho specifikace.
- Specifikace, implementace a použití ADT seznam.
- Specifikace, implementace a použití ADT zásobník, fronta. Vyčíslení výrazů s použitím zásobníku.
- ADT pole, množina, graf, binární strom.
- Algoritmy nad binárním stromem.
- Vyhledávání, sekvenční, v poli, binární vyhledávání.
- Binární vyhledávácí stromy, AVL strom.
- Vyhledávání v tabulkách s rozptýlenými položkami.
- Řazení, principy, bez přesunu, s vícenásobným klíčem.
- Známé metody řazení polí I
- Známé metody řazení polí II, řazení souborů.
- Rekurze, algoritmy s návratem.
- Dokazování správnosti programů, tvorba dokázaných programů.
Průběžná kontrola studia
- 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í.
Metody vyučování
Výuka předmětu je realizována formou: Přednáška - 3 vyučovací hodiny týdně, Projekty - 1 vyučovací hodina týdně.
Kontrolovaná výuka
- Opravované 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ě 20 body. V opačném případě bude zkouška hodnocena 0 body.
Zařazení předmětu ve studijních plánech