Název:

Algoritmy

Zkratka:IALe
Ak.rok:2011/2012
Semestr:zimní
Studijní plán:
ProgramOborRočníkPovinnost
IT-BC-1HBCH-volitelný
IT-BC-3BIT2.povinný
IT-MGR-1HMGH-volitelný
Vyučovací jazyk:angličtina
Kredity:5 kreditů
Ukončení:zápočet+zkouška (písemná)
Výuka:
hod./sempřednáškasem./cvičenílab. cvičenípoč. cvičeníjiná
Rozsah:3900130
 zkouškatestycvičenílaboratořeostatní
Body:51140035
Garant:Honzík Jan M., prof. Ing., CSc., UIFS
Přednášející:Honzík Jan M., prof. Ing., CSc., UIFS
Masařík Karel, Ing., Ph.D., UIFS
Cvičící:Křena Bohuslav, Ing., Ph.D., UITS
Masařík Karel, 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:
Seznámit se s principy metod dokazování správnosti programů a s tvorby dokázaných programů. Seznámit se základními principy složitosti algoritmů. Seznámit se s principy dynamického přidělování paměti. Seznámit se základními abstraktními datovými typy a strukturami, naučit se je implementovat a používat.  Naučit se rekurzívní a nerekurzívní zápisy základních algoritmů. Naučit se 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 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. ZNALOSTI A KOMPETENCE V ZÁKLADECH PROGRAMOVÁNÍ (C, Pascal aj.) BUDOU NA ZAČÁTKU VÝUKY PŘEZKOUŠENY. NEDOSTATEČNÉ ZNALOSTI POVEDOU KE ZRUŠENÍ PŘÉDMĚTU !!!
  • 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 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.
  • 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í.
Dovednosti, znalosti a kompetence obecné:
  • Student se nučí 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
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ávácí 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:
  1. Dvě domácí úlohy
  2. Projekt s miniobhajobou skupiny studentů.
  3. Pozn. pro rok 2009 změna - projekt zrušen
Literatura referenční:
  1. Honzík, J., Hruška, T., Máčel, M.: Vybrané kapitoly z programovacích technik, Ed.stř.VUT Brno,1991.
  2. Knuth, D.: The Art of Computer programming, Vol.1,2,3. Addison Wesley, 1968
  3. Wirth, N.: Alorithms+Data Structures=Programs, Prentice Hall, 1976
  4. Horovitz, Sahni: Fundamentals of Data Structures.
  5. Amsbury, W: Data Structures: From Arrays to Priority Queues.
  6. Cormen, T.H., Leiserson, Ch.E., Rivest, R.L.: Introduction to Algorithms.
  7. Aho A.V., Hoppcroft J.E., Ullman J.D.: Data Structures and Algorithms.
  8. Kruse, R.L.: Data Structures and Program Design. Prentice- Hall,Inc. 1984
  9. Baase, S.: Computer Algorithms - Introduction to Design and Analysis. Addison Wesley, 1998
  10. Sedgewick,R.:Algoritmy v C. (Základy. Datové struktury. Třídění. Vyhledávání.) Addison Wesley 1998. Softpress 2003.
Literatura studijní:
  1. Honzík, J., Hruška, T., Máčel, M.: Vybrané kapitoly z programovacích technik, Ed.stř.VUT Brno,1991.
  2. Knuth, D.: The Art of Computer programming, Vol.1,2,3. Addison Wesley, 1968
  3. Wirth, N.: Alorithms+Data Structures=Programs, Prentice Hall, 1976
  4. Horovitz, Sahni: Fundamentals of Data Structures.
  5. Amsbury, W: Data Structures: From Arrays to Priority Queues.
  6. Cormen, T. H., Leiserson, Ch.E., Rivest, R.L.: Introduction to Algorithms.
  7. Aho A.V., Hoppcroft J.E., Ullman J.D.: Data Structures and Algorithms.
  8. Kruse, R.L.: Data Structures and Program Design. Prentice- Hall,Inc. 1984
  9. 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ů
  • Změna pro rok 2009:
  • Dvě opravované domácí úlohy - 20 bodů
  • Půlsemestrální písemná zkouška - 18 bodů
  • Účast na přednášce - 1 bod za 1 účast (max 11 bodů)
  • Prémiový bod za aktivitu - 1 bod
  • Závěrečná písemná zkouška - 50 bodů
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í.