Název:

Algoritmy

Zkratka:IAL
Ak.rok:2018/2019
Semestr:zimní
Studijní plán:
ProgramObor/
specializace
RočníkPovinnost
IT-BC-3BIT2.povinný
Vyučovací jazyk:čeština
Kredity:5 kreditů
Ukončení:zápočet+zkouška (písemná)
Výuka:
hod./sempřednáškasem./cvič.lab. cvič.poč. cvič.jiná
Rozsah:3900013
 zkouškatestycvičenílaboratořeostatní
Body:51140035
Garant:Honzík Jan M., prof. Ing., CSc. (UIFS)
Zástupce garanta:Křena Bohuslav, Ing., Ph.D. (UITS)
Přednášející:Burgetová Ivana, Ing., Ph.D. (UIFS)
Honzík Jan M., prof. Ing., CSc. (UIFS)
Křena Bohuslav, Ing., Ph.D. (UITS)
Cvičící:Burgetová Ivana, Ing., Ph.D. (UIFS)
Honzík Jan M., prof. Ing., CSc. (UIFS)
Hranický Radek, Ing. (UIFS)
Jeřábek Kamil, Ing. (UIFS)
Křena Bohuslav, Ing., Ph.D. (UITS)
Křivka Zbyněk, Ing., Ph.D. (UIFS)
Fakulta:Fakulta informačních technologií VUT v Brně
Pracoviště:Ústav informačních systémů FIT VUT v Brně
Prerekvizity: 
Základy programování (IZP), UIFS
Navazující:
Principy programovacích jazyků a OOP (IPP), UIFS
Seminář C++ (ICP), UITS
Seminář Java (IJA), UITS
Seminář VHDL (IVH), UPSY
Nahrazuje:
Algoritmy a datové struktury (ADS), UIFS
 
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 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í.
Anotace:
  Přehled základních datových struktur a jejich použití. Principy dynamického přidělování paměti. Specifikace abstraktní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ávací 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 rekurzivní a nerekurzivní 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
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
Získané dovednosti, znalosti a kompetence z předmětu:
  
  • Student porozumí významu metod dokazování správnosti programů a 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 rekurzivní a nerekurzivní zápisy základních algoritmů.
  • Naučí se vytvářet a analyzovat algoritmy vyhledávání a řazení.
Dovednosti, znalosti a kompetence obecné:
  
  • 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
Proč je předmět vyučován:
  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.
Osnova přednášek:
 
  1. Základy algoritmického jazyka. Přehled datových struktur. Abstraktní datový typ a jeho specifikace.
  2. 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. ADT pole, množina, graf, binární strom.
  5. Algoritmy nad binárním stromem.
  6. Vyhledávání, sekvenční, v poli, binární vyhledávání.
  7. Binární vyhledávací stromy, AVL strom.
  8. Vyhledávání v tabulkách s rozptýlenými položkami.
  9. Řazení, principy, bez přesunu, s vícenásobným klíčem.
  10. Známé metody řazení polí I
  11. Známé metody řazení polí II, řazení souborů.
  12. Rekurze, algoritmy s návratem.
  13. Dokazování správnosti programů, tvorba dokázaných programů.
Osnova ostatní - projekty, práce:
 
  • Dvě domácí úlohy
  • Projekt s miniobhajobou skupiny studentů.
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.
Literatura studijní:
 
  • Honzík, J., Hruška, T., Máčel, M.: Vybrané kapitoly z programovacích technik, Ed.stř.VUT Brno,1991.
  • Mareš, M., Valla, T.: Průvodce labyrintem algoritmů. CZ.NIC, 2017. ISBN 978-80-88168-19-5. http://pruvodce.ucw.cz/
Kontrolovaná výuka:
  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.
Průběžná kontrola studia:
  
  • 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.
Podmínky zápočtu:
  
  • 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í.

 

Vaše IPv4 adresa: 52.200.130.163