Fakulta informačních technologií VUT v Brně

Detail předmětu

Algoritmy

IAL Ak. rok 2019/2020 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 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

Garant předmětu

Zástupce garanta předmětu

Jazyk výuky

česky

Zakončení

zápočet+zkouška (písemná)

Rozsah

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

Bodové hodnocení

51 zkouška, 14 půlsemestrální test, 35 projekty

Zajišťuje ústav

Přednášející

Cvičící

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

Cíle předmětu

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í. Student porozumí principům metod dokazování správnosti programů (Wirth) a tvorby dokázaných programů (Dijkstra) a znalosti bude schopen používat při tvorbě programů.

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.

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.
  • Mareš, M., Valla, T.: Průvodce labyrintem algoritmů. CZ.NIC, 2017. ISBN 978-80-88168-19-5. http://pruvodce.ucw.cz/

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

  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ů.

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ě 24 body. V opačném případě bude zkouška hodnocena 0 body.

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.

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í.

Rozvrh

DenTypTýdnyMístn.OdDoPSKSkupInfo
Útpřednáškavýuky E104 E105 E112 15:0017:50 2BIB 3BIT xx
Stpřednáškavýuky E104 E105 E112 14:0016:50 2BIA 3BIT xx

Zařazení předmětu ve studijních plánech

  • Program BIT, 2. ročník, povinný
  • Program IT-BC-3, obor BIT, 2. ročník, povinný
Nahoru