Prednášky ADS1, LS 2019/20, Ut 12:20 S3 Prednasky budou (dle moznosti) synchronizovany s druhou ceskou a s anglickou paralelkou s ohledem na poradi probiranych temat. Slajdy (a tudíž jejich čísla) se budou průběžně měnit. (Nový sylabus a nová akreditace LS 19/2020.) (26.5.2020) Prednasky (P7-P14, P5, P6) jsou v Moodlu. P1 18.2.2020 Slajdy 1-6 Úvod, porovnávání algoritmů, asymptotická složitost ("velke" O, Omega, Theta, "male" o, omega) P2 25.2. Slajdy 6-12, před topol. prohl. Reprezentace grafů, prohledávání do hloubky a do šířky, detekce mostů P3 3.3.2020 Slajdy 13-18 Topologické třídění, silně souvislé komponenty, kondenzace grafu. Úvod do min. cest., relaxace hrany. P4 10.3.2019 Slajdy 19-27 Min cesty: úvod, relaxace hrany; min.c. pro DAG, aplikace PERT; Dijkstrův alg (PLA 6.2), myšlenka haldy (PLA 4.2, po konstrukci haldy, s. 88). (Viterbiho alg. jsem přeskočil/nestihl) P5 17.3. Slajdy 29-33 Min. cesty: Bellmanův alg. (PLA 6.3), algoritmy "násobení matic" a Floydův-Warshallův alg. (PLA 6.4) (Floydův-Warshallův alg. bude také u dynamického programování) P6 24.3. Slajdy 34-39 Min. kostry úvod (PLA 7), Jarnikův alg. a věta o řezu (PLA 7.2), Borůvkův alg. (PLA 7.3), poznámky k hladovým algorimům. (přeskočeno: Kruskalův alg. 39-41 (PLA 7.4) a D.s. Union-Find (2 implementace) - přeskočeno, zatím, uvidíme podel času) P7 31.3. Slajdy 42-45,47,54-64 Dynamické množiny a binární vyhledávací stromy (PLA 8.1). Rotace (47). AVL stromy (PLA 8.2). B-stromy (varianta (a,b)-stromů), implementace (PLA 8.3). P8 7.4. Slajdy 65-68+. (a,b)-stromy a jejich vztah k červeno-černým stromům (dokončení) Hašování. Řešení kolizí zřetězením, volba hašovacích funkcí (PLA 11.3). P9 14.4. Slajdy 69-77 Hašování: Otevřené adresování (PLA 11.4), univerzální hašování (PLA 11.5, část). Změna velikosti tabulek (PLA 9.1 část/idea). P10 21.4. Slajdy 78-86,(87) Rozděl a panuj (PLA 10): úvod Rozděl a panuj: substituční metoda, master teorem (10.4) P11 28.4. Slajdy 88-95 část Rozděl a panuj, aplikace: Nasobeni matic - Strassenův alg. (PLA 10.5), rychlé násobení dlouhých čísel (PLA 10.3) (Alg. pro hledání mediánu (PLA 10.8) neplanuju ukazovat, i kdyz jeho rekurzivní vztah jsem pouzil jako příklad v substituční metodě) Dynamické programování, úvod: Fibonacciho čísla (PLA 12.1) P12 5.5. Slajdy 95-97, 30-32 Dynamické programování (PLA 12), opakovani: Floydův-Warshallův alg. (PLA 6.4), editacni vzdalenost (podle PLA 12.3). P13 12.5. Slajdy 104-107 DP: optimální vyhledávací strom (podle PLA 12.4) Třídění: Dolni odhad složitosti třídění (PLA 3.3), průměrný případ quicksortu. P14 19.5. Třídění: randomizovaný quicksort (PLA 11.2 část) a randomizace, Další třídicí alg. (PLA 3.4): radix-sort, counting-sort P5 on-line: Ut 26.5. 12:20 Slajdy 29-33 Zopakování algoritmů pro min. cestu: pro DAG, Dijkstrův alg. Min. cesty: Bellmanův alg. (PLA 6.3), algoritmy "násobení matic" a Floydův-Warshallův alg. (PLA 6.4) (Floydův-Warshallův alg. bude také u dynamického programování) P6 on-line: Ut 2.6. 12:20 Slajdy 34-39 Kostry. Jarníkův alg. Věta o řezu. Borůvkův alg. (Nepřednášen (volitelný) Kruskalův alg., včetně union-find struktury) Plán Odpřednášeno [1] http://pruvodce.ucw.cz/ Martin Mareš, Tomáš Valla, Průvodce labyrintem algoritmů, 2017 CZ.NIC, z.s.p.o., ISBN 978-80-88168-19-5 - v textu zkratka "PLA", s čísly kapitol --------------------------------------------------------------------- ... 2019: P11 28.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 5.5. Slajdy 94, 28-33 (pridam i slajdy v poradi probiranych temat) Counting sort. Hasovani, s retizky. P13 12.5. ... P14 19.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. --- Bylo dříve: 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.) -- 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.