Prednášky ADS1, LS 2018/19, Ut 10:40

Prednasky budou (dle moznosti) synchronizovany s druhou ceskou a s anglickou paralelkou s ohledem na poradi probiranych temat.

Přednáška se nekoná 14.5. (P13, předposlední týden semestru)
Slajdy (a tudíž jejich čísla) se budou průběžně měnit.


P1 19.2.2019
Slajdy 1-6
Úvod, asymptotická složitost ("velke" O, Omega, Theta, "male" o, omega)

P2 26.2. 
Slajdy 33-36+, před topol. prohl.
Reprezentace grafů, prohledávání do hloubky a do šířky

P3 5.3. 
Slajdy 37-40
Topologické třídění, silně souvislé komponenty, kondenzace grafu 

P4 12.3.
Slajdy 41, 51-53, 42
Min cesty: úvod, relaxace hrany; min.c. pro DAG, aplikace PERT; Dijkstrův alg, myšlenka alg. a myšlenka haldy.
(Důkaz a haldy příště) ; Viterbiho alg. jsem přeskočil/nestihl

P5 19.3.
Slajdy 42-48
Min. cesty: Dijkstra - důkaz+haldy, Bellmanův, Floydův-Warshallův rychle
D.s. Halda pro Dijkstru, složitost Dijkstry pomocí pole a binární haldy
(binomiální haldy jsem vynechal; fibonacciho jsou spomenuté, aby vědeli, 
jak se to zrychlí)

P6 26.3.
Slajdy 49-50,55-57
Min cesty dokončení: Floyd-Warshall, nasobeni matic
Min. kostry úvod, Kruskalův alg. a D.s. Union-Find (2 implementace), věta o řezu rychle

P7 2.4.
Slajdy 57-59, 7-9
Dokončení min. koster, řezové lemma, Jarníkův alg., zmínka o hladových alg.
Dynamické množiny a binární vyhledávací stromy

P8 9.4.
Slajdy 10-22; nove slajdy - pridane obrazky
Cerveno-cerne stromy, AVL rychle

P9 16.4. 
Slajdy 23-27, 75-79
B-stromy. Rozdel a panuj, úvod, substituční metoda

P10 23.4. 
Slajdy 82-90
Rozděl a panuj, Master Theorem, hlavní myšlenka důkazu, aplikace: Strassen, násobení dlouhých čísel

P11 30.4.
Slajdy 88-93, precislovano, pridane obrazky
Třídění: dolní odhad, prumerny pripad quicksortu, randomizovany quicksort.
Třídění pomocí adresace klíčů: Radixsort, prihradkove vicepruchodove (Counting sort priste)

P12 7.5.
Slajdy 94, 28-33  (pridam i slajdy v poradi probiranych temat)
Counting sort. Hasovani, s retizky.

P13x 14.5. Nekoná se

P14 21.5.2019
Slajdy 33-40 (slajdy preusporadam podle projitych temat)
Hasovani: otevřené hašování, univerzální hašování, zvětšování tabulek. 
(Na LUP nedošlo.)


--- Bylo dříve:

Prednášky ADS1, LS 2016/17, Pa 12:20

Prednasky budou (dle moznosti) synchronizovany s druhou ceskou paralelkou s ohledem na poradi probiranych temat.


P1 24.2.
Slajdy 1-6
Uvod, asymptoticka  slozitost.

P2  3.3.
Slajdy 7, 22-27
Vyhledavani v dynamickych mnozinach - uvod; hasovani s retizky.

P3 10.3.
Slajdy 27-32, 60
Hasovani s otevrenou adresaci, univerzalni hasovani.
Uvod do rozdel a panuj.

P4 17.3.
Slajdy 60-73.
Rozdel a panuj: substitucni metoda, kucharka/Master theorem, Strassenuv alg., nasobeni 
dlouhych cisel.

P5 24.3.
Slajdy 74-79, +65
Trideni. 

P6 31.3.
Slajdy 33-38.
Grafove alg.: DFS, BFS, topol. trideni, uvod SSK.

P7 7.4.
Slajdy 38-43.
SSK. Nejkratsi cesty, Dijkstra, jeste haldy.

Px 14.4. Velikonoce.

P8 21.4. 
Slajdy 43-48, 51-53.
Haldy, dalsi alg. pro nejkratsi cesty: Bellman-Ford, DAG/Topol. pruchod.

P9 28.4.
Slajdy 48-51. (7,)8-9.
Vsechny cesty: nasobeni matic, Floyd-Warshall. Stromy, BVS.

P10 5.5. 
Slajdy 10-15, obrazky z anglickych slajdu
Navic: prumerna hloubka BVS - idea. Cerveno-cerné stromy. AVL stromy: úvod, insert.

P11 12.5. 
Slajdy 15-21
AVL dokonceni. B-stromy.

P12 19.5. 
Slajdy 55-59
Kostry.

P13 26.5. Plan:
Slajdy 80-89
LUP rozklad.