Prednášky ADS1, LS 2021/22, Ct 10:40, N1 Streamuje se, nahrává se - bude dostupné (přes Moodle na stream.cuni.cz). - odkaz na kapitolu PLA [1] znamená, kde příslušnou látku najdete; neznamená to, že jsem prednášel podle knižky PLA P1 17.2.2022 Slajdy 1-6 Měření složitostí algoritmů, RAM stroj, O-notace. /bez příkladu(6) P2 24.2.2022 Slajdy 7-11+ Reprezentace grafů, prohledávání do hloubky a do šířky. Def. mostu. P3 3.3.2022 Slajdy 12-17 Detekce mostů. Topologické třídění, silně souvislé komponenty, kondenzace grafu. P4 10.3.2022 Slajdy 18-28 Nejkratší cesty: úvod, relaxace hrany; n.c. pro DAG, aplikace PERT; Dijkstrův alg (PLA 6.2), haldy a složitost Dijkstrova alg. (PLA 4.2). (Viterbiho alg. jsem přeskočil) P5 17.3.2022 Slajdy 29-33 Nejkratší cesty 2: Bellmanův-Fordův alg., maticové alg: Floyd-Warshall a násobení matic. Tranzitivní uzávěr grafu. P6 24.3.2022 Slajdy 34-39(-42) 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. (Kruskalův alg. stručně) P7 31.3.2022 Slajdy 43-51 Datové struktury: BVS, AVL-stromy P8 7.4.2022 Slajdy 52-64 Nejdřív B-stromy, vztah k a-b stromům, pak Červeno-černé stromy, vztah k B-stromům. P9 14.4. Slajdy 65-71 Hašování. Řešení kolizí zřetězením, volba hašovacích funkcí (PLA 11.3). Otevřené adresování: metody. P10 21.4. Slajdy 71-78 Hašování: Otevřené adresování - analýza (PLA 11.4), univerzální hašování (PLA 11.5, část) pomocí skal. součinu. Změna velikosti tabulek (PLA 9.1 část/idea). Rozděl a panuj (PLA 10): úvod. P11 28.4. Slajdy 79-88,92-93 Rozděl a panuj: substituční metoda, master teorem (PLA 10.4) Násobení dlouhých čísel (PLA 10.3). P12 5.5. Slajdy 88-91,94-100 Nové slajdy pro editační vzdálenost. Násobeni matic - Strassenův alg. (PLA 10.5) Dynamické programování (PLA 12): úvod, základní techniky. Opakování: Fib. čísla (PLA 12.1), alg. Floyd-Warshall (PLA 6.4). Editační vzdálenost (PLA 12.3). P13 12.5. Slajdy 101-104, 109-110 Nové slajdy pro optimální vyhledávací strom. Dynamické programování: optimální vyhledávací strom (PLA 12.4). Třídění: Dolní odhad složitosti třídění (PLA 3.3). P14 19.5. Slajdy 110-117 Třídění: průměrný případ quicksortu, randomizovaný quicksort (PLA 11.2 část) a randomizace. QuickSelect a "k-tý prvek" lineárně. plán: odpřednášeno (Další třídicí alg. (PLA 3.4): radix-sort, counting-sort - bylo na Algoritmizaci) (Dynamické programování, když zbude čas.) ---- ..Px: Volitelné témy: (2022: 14 přednášek) červeno-černé stromy: ANO komponenty souvislosti, lineárně: ANO Floydův-Warshallův algoritmus: ANO Kruskalův algoritmus a datová struktura pro Union-Find: NE (2022: velmi stručně) hledání mediánu v lin. čase v nejhorším případě: možná medián lineárně, následně QuickSelect, "rychlý" Quicksort optimální vyhledávací stromy (DP): ANO --- Minulá (moje) přednáška: Prednášky ADS1, LS 2019/20, Ut 12:20 S3 Covid: od P5 online 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 podle č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 (PLA 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; - odkaz na kapitolu PLA znamená, kde příslušnou látku najdete; neznamená to, že jsem prednášel podle knižky PLA [2] http://mj.ucw.cz/vyuka/dsnotes/ds.pdf Poznámky k Datovým strukturám