Algoritmy a datové strukury I (NTIN060)

Jan Hubička, hubicka@kam.mff.cuni.cz

Konzultace po dohodě emailem (nejlépe ve středu nebo pátek na MS, 3. patro). Do subjektu emailů pište "ADS2018".

Odpřednesená látka
23. února
Úvod, literatura, příklad různých řešení problému hledání nejdelší rostoucí podposloupnosti a diskuze jejich časové složitosti. Model výpočtu teoreticky i prakticky, elementární operace, velké O.
1. března
Definice výpočetního modelu RAM. časová a prostorová složitost. Příklad implementace a analýzy selectsort. benchmark k ukazce z prednášky, běh benchmarku na Ryzenu, assembler s vysvětlením
8. března
Průchod do šířky (BFS) - algoritmus, časová složitost, důkaz správnosti, použití na hledání nejkratšich cest. Průchod do houbky (DFS) - úvod, typy hran v DFS stromu.
15. března
DFS, klasifikace hran, aplikace: hledání mostů v grafu, topologické třídění.
22. března
Aplikace topologického třídění, komponenty silné souvislosti. (zaskakuje Radim Hušek).
29. března
Velikonoce
6. dubna
Djskruv algoritmus na hledani nejkratisu cest. Bellman-Ford.
13. dubna
Minimální kostry: Jarníkův a Borůvkův algoritmus. Krusalův algoritmus. Datová struktura pro union-find.
20. dubna
Binární vyhledávací stromy, AVL stromy
28. dubna
(a,b)-stromy: definice, operace insert a delete. Insert s preventivním štěpením pro (a,2b)-stromy. LLRB-stromy jako varianta k (2,4)-stromům. Implementace insertu.
4. května
Rozděl a panuj: mergesort, násobení čísel v čase O(nlog23) (Karatsuba-Ofman), Kuchařková věta (master theorem), Strassen's algorithm for matrix multiplication (vzorec)
11. května
Více o kuchařkové větě. QuickSelect - randomizovaná a náhodná volba pivota. Analýza aplikací lemmatu o džbánu. Vyhledávání k-tého prvku v lineárním čase.
Plán posledních dvou přednášek
QuickSort a analýza časové složitosti v průměrném případě. Dolní odhad na počet porovnání třídicího algoritmu. Přihrádkové třídění. Heshování s přihrádkami. Výběr heshovacích funkcí. Dynamická relokace tabulek a amortizace. Univerzální hashování. Hashování s otevřenou adresací.

Odkazy