Algoritmy a dátové štruktúry

Oznam

Prednášajúci:Milan Vojvoda
Cvičiaci:Milan Vojvoda
Martin Bečka
Martin Nehéz
Linky:IS Sylabus
Vyučovanie
Kategória predmetu:,

Upozornenie

—

Organizácia
Podmienky
Oznamy
Viac

Organizácia predmetu

Link na vyučovanie: Vyučovanie

Predmet je členený do nasledujúcich aktivít:

  • Prednášky: 2 hodiny týždenne podľa rozvrhu
  • Cvičenie: 2 hodiny týždenne podľa rozvrhu
  • Samostatné domáce štúdium
Konzultácie:

Konzultačné hodiny po dohode mailom

Plán semestra

  1. Greedy algoritmy.
  2. Dynamické programovanie I. (Rod cutting)
  3. Dynamické programovanie II. (Matrix chain multiplication, Optimal binary search tree)
  4. Dynamické programovanie III. (Knapsack, TSP)
  5. Dynamické programovanie IV. (Longest common substring, subsequence, edit distance)
  6. Kompresné algoritmy (Huffman, RLE, LZW)
  7. Amortizačná analýza
  8. SAT, 2-SAT, 3-SAT, k-clauses 2-SAT
  9. AVL-stromy
  10. Aproximačné algoritmy I.
  11. Aproximačné algoritmy II.

Podmienky absolvovania

Počas semestra budú 2 zadania, každé za 15 bodov. Študenti musia odovzdané zadania odprezentovať v termíne po dohode s cvičiacimi, musia byť schopní zodpovedať otázky ohľadom odovzdaného riešenia a svoje riešenie obhájiť.

Písomka/test počas semestra za 22 bodov.

Aktivita a riešenie úloh počas cvičení 8 bodov. Počas cviční budú zadané úlohy za body. Ich riešenie a odovzdanie by malo prebiehať na cvičeniach.

Na získanie zápočtu je potrebné získať zo zadaní a z cvičení spolu aspoň 30 bodov.

Záverečná skúška bude za 40 bodov.

Záverečné hodnotenie bude podľa platnej klasifikačnej stupnice FEI STU.

Literatúra
  • Cormen, T.H., Leiserson, C.E., Rivest, R.R., Stein, C.: Introduction to Algorithms. 2nd edition, MIT Press, 2003.
  • Sedgewick, R., Wayne, K.: Algorithms. 4th edition. Addison-Wesley, 2011.