ADS

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

ADS


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, front, prioritná front, 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ť.

MIT

  1. analýza algoritmov, insert sort, merge sort, správnosť algoritmov
  2. asymptotická notácia, rekurzia, Substitution, Master theorem
  3. rozdeľuj&panuj: Strassen, Fibonacci, Polynomial Multiplication,
  4. Quicksort, Randomized Algorithms
  5. Heapsort, Dynamic Sets, Priority Queues
  6. Linear-time Sorting: Lower Bounds, Counting Sort, Radix Sort
  7. Order Statistics, Median
  8. Applications of Median, Bucketsort
  9. Hashing, Hash Functions
  10. Universal Hashing, Perfect Hashing
  11. Binary Search Trees, Tree Walks
  12. Relation of BSTs to Quicksort, Analysis of Random BST
  13. Red-black Trees, Rotations, Insertions, Deletions
  14. 2-3 Trees, B-trees
  15. Augmenting Data Structures, Dynamic Order Statistics, Interval Trees
  16. Skip Lists
  17. Range Trees
  18. Amortized Algorithms, Table Doubling, Potential Method
  19. Competitive Analysis: Self-organizing Lists
  20. Competitive Analysis: Ski Rental, Randomized Competitive Algorithm
  21. Dynamic Programming, Longest Common Subsequence
  22. Greedy Algorithms, Minimum Spanning Trees
  23. Shortest Paths I: Properties, Dijkstra's Algorithm, Breadth-first Search
  24. Shortest Paths II: Bellman-Ford, Linear Programming, Difference Constraints
  25. Graph Searching: Depth-first Search, Topological Sort, DAG Shortest Paths
  26. Shortest Paths III: All-pairs Shortest Paths, Matrix Multiplication, Floyd-Warshall, Johnson

témy

  • zložitosť
  • halda, heap sort
  • rozdeľuj a panuj
  • dynamické programovanie
  • pažravé algoritmy
  • slovníky, množiny, asociatívne pole
  • hešovacie tabuľky
  • vyvážené vyhľadávacie stromy
  • grafové algoritmy