Počet kreditů 6
Vyučováno v Zimní
Rozsah výuky 2P+2C
Garant předmětu
Přednášející
Cvičící

Cílem předmětu je schopnost samostatné implementeca různých variant zálkadních úloh informatiky. Hlavní témata jsou algoritmy řazení a vyhledávání a jim odpovídající datové struktury. Důraz je kladen na algoritmický aspekt úloh a efektivitu praktického řešení.

Programování 1

Cílem je schopnost samostatné implementace různých variant základních úloh informatiky. Hlavní témata jsou algoritmy řazení a vyhledávání a jim odpovídající datové struktury. Důraz je kladen na algoritmický aspekt úloh a efektivitu praktického řešení.

  1. Řád růstu funkcí, asymptotická složitost algoritmu
  2. Rekurze, složitost rekurentních algoritmů, mistrovská věta
  3. Stromy, binární stromy, prohledávání s návratem
  4. Fronta, graf, průchod stromem/grafem do šířky/hloubky
  5. Vyhledávani v poli, binární vyhledávací stromy
  6. AVL a B- stromy
  7. Řazení, Insert Sort, SelectionSort, Bubble Sort, QuickSort
  8. Řazení, Merge Sort, Halda, Heap Sort
  9. Řazení, Radix sort, Counting Sort, Bucket Sort
  10. Dynamické programování, struktura optimálního řešení, odstranění rekurze, optimální BVS
  11. Dynamické programování, nejdelší společná podposloupnost, optimální násobení matic, problém batohu
  12. Hashing, otevřené a zřetězené tabulky, double hashing
  13. Hashing, srůstající tabulky, univerzální hashování,
  14. Řazení vícedimenzionálních dat, porovnání řadících algoritmů


  1. Řád růstu funkcí, asymptotická složitost algoritmu
  2. Rekurze, složitost rekurentních algoritmů, mistrovská věta
  3. Stromy, binární stromy, prohledávání s návratem
  4. Fronta, graf, průchod stromem/grafem do šířky/hloubky
  5. Vyhledávani v poli, binární vyhledávací stromy
  6. AVL a B- stromy
  7. Řazení, Insert Sort, SelectionSort, Bubble Sort, QuickSort
  8. Řazení, Merge Sort, Halda, Heap Sort
  9. Řazení, Radix sort, Counting Sort, Bucket Sort
  10. Hashing, otevřené a zřetězené tabulky, double hashing
  11. Hashing, srůstající tabulky, univerzální hashování,
  12. Dynamické programování, struktura optimálního řešení, odstranění rekurze, optimální BVS
  13. Dynamické programování, nejdelší společná podposloupnost, optimální násobení matic, problém batohu
  14. Řazení vícedimenzionálních dat, porovnání řadících algoritmů

[1] T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein: Introduction to Algorithms, 3rd ed., MIT Press, 2009,

[2] S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani: Algorithms, Mcgraw-Hill Higher Education, 2006,

[3] Pavel Töpfer: Algoritmy a programovací techniky, Prometheus Praha 1995, 2. vydání 2007

[4] Robert Sedgewick: Algoritmy v C, části 1-4, SoftPress, Praha, 2003


Rozvrh předmětu
Po
Út
St
Čt
PřednáškyCvičení