teaching:ads11920_prednaska
Rozdíly
Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
Obě strany předchozí revizePředchozí verzeNásledující verze | Předchozí verze | ||
teaching:ads11920_prednaska [2020/03/10 15:29] – 04-pred Martin Koutecky | teaching:ads11920_prednaska [2020/05/26 15:25] (aktuální) – prubeh-zkousky Martin Koutecky | ||
---|---|---|---|
Řádek 13: | Řádek 13: | ||
| 3. 3.| Pokračování DFS: topologické číslování; | | 3. 3.| Pokračování DFS: topologické číslování; | ||
| 10. 3.| Nejkratší cesty: Dijkstrův algoritmus pořádně; obecný relaxační algoritmus; Bellman-Ford umí detekovat záporný cyklus; Floyd-Warshall umí spočítat matici vzdáleností **[L 6.1-6.4]**| | | 10. 3.| Nejkratší cesty: Dijkstrův algoritmus pořádně; obecný relaxační algoritmus; Bellman-Ford umí detekovat záporný cyklus; Floyd-Warshall umí spočítat matici vzdáleností **[L 6.1-6.4]**| | ||
- | | 17. 3.| //Plán: minimální kostry | + | | 17. 3.| Minimální kostry: Jarníkův (Primův, Dijkstrův) algoritmus, Borůvkův algoritmus, Kruskalův algoritmus, keříková struktura Union-Find |
+ | | 24. 3.| Stromové datové struktury: binární vyhledávací stromy, AVL-stromy | ||
+ | | 31. 3.| $(a, | ||
+ | | 7. 4.| rekapitulace LLRB, amortizace, úvod do hešování **[L 9.1-9.2; 11.3]** [[https://stream.cuni.cz/ | ||
+ | | 14. 4.| Hešování s otevřenou adresací, univerzální hešování **[L 11.3-11.4]**, | ||
+ | https:// | ||
+ | | 21. 4.| Rozděl a panuj - úvod, kuchařková věta, násobení dlouhých čísel **[L 10]**, [[https:// | ||
+ | | 28. 4.| Rozděl a panuj - hledání medánu v lineárním čase; úvod do dynamického programování **[L 10.6-10.9, L 12.1-12.2]** [[https:// | ||
+ | | 5. 5.| Dynamické programování - Editační vzdálenost; | ||
+ | |||
+ | {{page> | ||
+ | |||
+ | {{ : | ||
+ | |||
+ | ===== Zkouška ADS 1 / 2020 ===== | ||
+ | |||
+ | Na zkoušce budou zadány | ||
+ | |||
+ | - Dva příklady na algoritmy či datové struktury z přednášky | ||
+ | - Dvě úlohy podobné těm ze cvičení | ||
+ | |||
+ | === Hodnocení === | ||
+ | |||
+ | **Na 3** stačí znát definice a algoritmy a nechat se dostrkat k řešení aspoň jedné úlohy (nebo ji vyřešit neefektivně). | ||
+ | |||
+ | **Na 2** je potřeba umět řešit úlohy s nápovědou, | ||
+ | |||
+ | **Na 1** je potřeba i rozbor algoritmů (správnost a složitost včetně důkazů tvrzení) a umět řešit úlohy víceméně samostatně (ale nápověda typu “tady se hodí použít vyhledávací strom” je na jedničku stále v pořádku). | ||
+ | |||
+ | === Okruhy === | ||
+ | |||
+ | **Pozor**, okruhy níže // | ||
+ | |||
+ | * BFS, DFS a jejich klasifikace hran | ||
+ | * Aplikace DFS: topologické třídění, | ||
+ | * Dijkstrův algoritmus | ||
+ | * Bellman-Fordův algoritmus | ||
+ | * Floyd-Warshallův algoritmus — půltéma | ||
+ | * Jarníkův algoritmus | ||
+ | * Borůvkův algoritmus | ||
+ | * Kruskalův algoritmus + Union-Find pomocí keříků | ||
+ | * BVS obecně | ||
+ | * AVL stromy | ||
+ | * $(a, | ||
+ | * Červeno-černé stromy | ||
+ | * Hešování s přihrádkami | ||
+ | * Hešování s otevřenou adresací | ||
+ | * Univerzální hešování | ||
+ | * Kuchařková věta, rozbor algoritmu rozděl a panuj pomocí stromu rekurze | ||
+ | * Násobení dlouhých čísel pomocí rozděl a panuj; Strassenův algoritmus (idea) | ||
+ | * LinearSelect | ||
+ | * QuickSort v průměrném případě | ||
+ | * Editační vzdálenost | ||
+ | * Dolní odhady: binární vyhledávání, | ||
+ | |||
- | {{page> |
teaching/ads11920_prednaska.1583850548.txt.gz · Poslední úprava: 2020/03/10 15:29 autor: Martin Koutecky