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/02/18 12:42] – Martin Koutecky | teaching:ads11920_prednaska [2020/05/26 15:25] (aktuální) – prubeh-zkousky Martin Koutecky | ||
---|---|---|---|
Řádek 10: | Řádek 10: | ||
^ datum ^ co se přednášelo [zdroj] ^ | ^ datum ^ co se přednášelo [zdroj] ^ | ||
| 18. 2.| Hledání nejbohatšího úseku. Snaha o definici algoritmu. Von Neumannův výpočetní model, Ǒčková notace ($\mathcal{O}, | | 18. 2.| Hledání nejbohatšího úseku. Snaha o definici algoritmu. Von Neumannův výpočetní model, Ǒčková notace ($\mathcal{O}, | ||
- | | 25. 2.| // | + | | 25. 2.| Základní grafové algoritmy: |
+ | | 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]**| | ||
+ | | 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 **[L 8]** [[https:// | ||
+ | | 31. 3.| $(a, | ||
+ | | 7. 4.| rekapitulace LLRB, amortizace, úvod do hešování **[L 9.1-9.2; 11.3]** [[https:// | ||
+ | | 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://stream.cuni.cz/ | ||
+ | | 5. 5.| Dynamické programování - Editační vzdálenost; | ||
{{page> | {{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í, | ||
+ | |||
+ | |||
+ | |||
+ | |||
+ |
teaching/ads11920_prednaska.1582026130.txt.gz · Poslední úprava: 2020/02/18 12:42 autor: Martin Koutecky