ADS

Z Pascal
Prejsť na: navigácia, hľadanie

Misof

  • Potreba efektívnych algoritmov.
  • Analýza algoritmov. Meranie veľkosti vstupu. Časová zložitosť ako funkcia veľkosti vstupu. Asymptotická časová zložitosť. O-notácia.
  • Triedenia (heapsort, quicksort, radixsort)-
  • Abstraktné dátové štruktúry: zásobník, fronta, prioritná fronta, množina, asociatívne pole.
  • Konkrétne dátové štruktúry: halda, binárny strom, hašovacia tabuľka. Vyvažované vyhľadávacie stromy.
  • Vzťah háld, stromov a triedenia.
  • Pažravé algoritmy.
  • Základy dynamického programovania.
prednášky
  1. Povinná byrokracia na úvod. Stable marriage problem. Ukážka ťažkých problémov ako zdôvodnenie potreby efektívnych algoritmov.
  2. Asymptotická časová zložitosť. O-notácia. Rôzne dobré horné odhady zložitosti.
  3. Triedenie MergeSort. Časová zložitosť rekurzívnych funkcií. Master theorem.
  4. Rekapitulácia master theorem. Amortizovaná časová zložitosť.
  5. Zásobník, fronta. Implementácie pomocou poľa pevnej veľkosti a spájaných zoznamov. Pole premennej veľkosti (vector, deque). Neefektívne spôsoby implementácie prioritnej fronty.
  6. Binárna halda: vlastnosť haldy, vkladanie, výber maxima. Výroba haldy v lineárnom čase. Triedenie HeapSort. Ukážka binomickej haldy.
  7. Mergesort deliaci na n/4 a zvyšok. QuickSort. Náhodná voľba pivota. Binárne vyhľadávanie a binárne vyhľadávacie stromy, vkladanie a výber prvkov.
  8. TreeSort. Vyvážené stromy. Vyvažovanie AVL stromov. Odhad hĺbky vyváženého stromu.
  9. Half-open intervaly a iterátory. Usporiadané asociatívne pole. Vylepšené stromy: v každom podstrome si pamätáme hĺbku a veľkosť.
  10. Binárne vyhľadávanie a invarianty. Dolný odhad zložitosti binárneho vyhľadávania. Dolný odhad zložitosti triedenia porovnávaním. Vzťah háld, stromov a triedenia.
  11. Koreň a maximum spojitej funkcie: binárne a ternárne vyhľadávanie. Triedenie v čase lepšom ako O(n log n): BucketSort / CountSort.
  12. RadixSort. Generovanie rovnomerne náhodných čísel.
  13. Náhodné (aj nie úplne náhodné) preusporiadanie poľa. Náhodný sampling.
  14. Iterovanie cez všetky kombinatorické objekty (podmnožiny, permutácie, kombinácie a variácie pevnej veľkosti).
  15. Pažravé algoritmy (nákup zlata, zastávky, výber prednášok, platenie mincami).
  16. Hešovanie. Kolízie a narodeninový paradox. Riešenie kolízií zreťazením.
  17. Univerzálne hešovanie. Perfektné hešovanie.
  18. Memoizácia a dynamické programovanie: Fibonacciho čísla, najdlhšia spoločná vybraná podpostupnosť
  19. Memoizácia a dynamické programovanie: najdlhšia rastúca podpostupnosť, problém batoha
  20. Memoizácia a dynamické programovanie: problém batoha s cenami, medián ako optimálne miesto stretnutia, optimálne rozmiestnenie zastávok.
  21. Prepojenie viacerých dátových štruktúr. Bonus: dátové štruktúry využívajúce náhodu (Bloomov filter, skiplist, treap).
  22. Euklidov algoritmus: implementácia, časová zložitosť, rozšírenie. Eratostenovo sito.
  23. Detekcia cyklu v postupnosti. Konverzia racionálneho čísla na zlomok. Poradná zložitosť.