Název:

Algoritmy

Zkratka:IAL
Ak.rok:2005/2006
Semestr:letní
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:50150035
Garant:Honzík Jan M., prof. Ing., CSc. (UIFS)
Přednášející:Honzík Jan M., prof. Ing., CSc. (UIFS)
Cvičící:Cvrček Daniel, doc. Ing., Ph.D. (UITS)
Čech Vladimír, Ing. (UIFS)
Křena Bohuslav, Ing., Ph.D. (UITS)
Lukáš Roman, 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:
  Základní charakteristika podle ECTS:

Seznámit se základy dokazování správnosti programů a se základními principy složitosti algoritmů. Seznámit se základními abstraktními datovýni typy a strukturami a to především: seznamy, zásobník, fronta, pole, graf, binární strom, vyhledávací tabulka. Naučit se je implementovat a používat. Seznámit se s principy dynamického přidělování paměti. Naučit se rekurzívní a nerekurzívní zápisy základních algoritmů. Naučit se vytvářet a analyzovat známé algoritmy vyhledávání a řazení.

Anotace:
  Přehled základních datovýsh 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ů.
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:
  Vědomosti a dovednosti orientované na předmět:
  • Student porozumí smyslu správnosti programů a naučí se dokazovat správnost jednoduchých a základních algoritmů. 
  • Porozumí smyslu složitosti programů a naučí se stanovit složitost jednoduchých a základních 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.
  • 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í.
  • Seznámí se se základními odbornými termíny předmětu v jazyce anglickém.

     

Dovednosti, znalosti a kompetence obecné:
  
  • Student se naučí řešit jednoduché problémy v týmu formou projektu.
  • Naučí se vytvářet dokumentaci malého projektu a obhájit výsledky problému řešeného formou projektu před veřejností
Osnova přednášek:
 
  • 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í
  • Známé motody řazení polí, řazení souborů.
  • Rekurze, algoritmy s návratem.
  • Dokazování správnosti programů, tvorba dokázaných programů.
Osnova ostatní - projekty, práce:
 
  • Domácí úlohy řešené samostatně
  • Projekt s miniobhajobou max. pětice studentů.
Literatura referenční:
 
  • Honzík, J., Hruška, T., Máčel, M.: Vybrané kapitoly z programovacích technik, Ed.stř.VUT Brno,1991.
  • Knuth, D.: The Art of Computer programming, Vol.1,2,3. Addison Wesley, 2001
  • Wirth, N.: Alorithms+Data Structures=Programs, Prentice Hall, 1997
  • Horovitz, Sahni: Fundamentals of Data Structures.
  • Amsbury, W: Data Structures: From Arrays to Priority Queues. Prentice Hall, 2001
  • Cormen, T.H., Leiserson, Ch.E., Rivest, R.L.: Introduction to Algorithms. 1998
  • 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
Literatura studijní:
 
  • Honzík, J., Hruška, T., Máčel, M.: Vybrané kapitoly z programovacích technik, Ed.stř.VUT Brno,1991.
  • Knuth, D.: The Art of Computer programming, Vol.1,2,3. Addison Wesley, 1968
  • Wirth, N.: Alorithms+Data Structures=Programs, Prentice Hall, 1997
  • Horovitz, Sahni: Fundamentals of Data Structures. Prentice- Hall,Inc. 2001,
  • Amsbury, W: Data Structures: From Arrays to Priority Queues. Prentice Hall, 2001
  • Cormen, T.H., Leiserson, Ch.E., Rivest, R.L.: Introduction to Algorithms. 2002
  • 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
Průběžná kontrola studia:
  
  • Opravované domácí úlohy - 20 bodů
  • Půlsemestrální písemná zkouška - 15 bodů
  • Hodnocený projekt s obhajobou - 15 bodů
  • Závěrečná písemná zkouška - 50 bodů
  • Podmínka zápočtu: min. 15 bodů získaných v průběhu semestru
  • Hranice pro úspěšnou zkoušku podle pravidel ECTS - 50 bodů
Podmínky zápočtu:
  
  • 15 bodů (z 50 možných) získaných v průběhu semestru za půlsemestrální zkoušku, domácí úlohy a projekt
 

Vaše IPv4 adresa: 54.81.220.239