Rozdíly

Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.

--- teaching:ads11920_prednaska [2020/02/27 15:19] – plán Martin Koutecky
+++ teaching:ads11920_prednaska [2020/05/26 13:25] (aktuální) – prubeh-zkousky Martin Koutecky
@@ Řádek 11: / Řádek 11: @@
 | 18. 2.| Hledání nejbohatšího úseku. Snaha o definici algoritmu. Von Neumannův výpočetní model, Ǒčková notace ($\mathcal{O}, \mathcal{o}, \Omega, \omega$), výpočetní model RAM **[L 1.1, 2]**|
 | 25. 2.| Základní grafové algoritmy: prohledávání do šířky (BFS), prohledávání do hloubky (DFS) na neorientovaném grafu, detekce mostů, DFS na orientovaném grafu **[L 5.1-5.6]**|
-| 3. 2.| //Plán na další 2 přednášky: pokračování DFS: tranzitivní uzávěr, topologické číslování; detekce komponent silné souvislosti v lineárním čase; nejkratší cesty **[L 5.7-6.4]**//|
+| 3. 3.| Pokračování DFS: topologické číslování; detekce komponent silné souvislosti v lineárním čase; úvod do nejkratších cest **[L 5.7-6.1]**|
+| 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  **[L 7.1-7.4]**, [[https://stream.cuni.cz/cs/Detail/3329|video přednášky]], {{ :teaching:ads11920:kostry_prednaska.pdf |"zápis" z přednášky}}|
+| 24. 3.| Stromové datové struktury: binární vyhledávací stromy, AVL-stromy **[L 8]** [[https://stream.cuni.cz/cs/Detail/3507|video přednášky]], [[https://cunicz-my.sharepoint.com/:o:/g/personal/63735541_cuni_cz/EgHZ50r_8PVJmdyiKhlSnsoBr1koI1loAthyZ2kTeyjsRQ?e=bkanMC|zápis z přednášky (OneNote)]]|
+| 31. 3.| $(a,b)$-stromy, červeno-černé stromy **[L 8]**[[https://stream.cuni.cz/cs/Detail/3779|video přednášky]], [[https://cunicz-my.sharepoint.com/:o:/g/personal/63735541_cuni_cz/EgHZ50r_8PVJmdyiKhlSnsoBr1koI1loAthyZ2kTeyjsRQ?e=bkanMC|zápis z přednášky (OneNote)]]|
+| 7. 4.| rekapitulace LLRB, amortizace, úvod do hešování **[L 9.1-9.2; 11.3]** [[https://stream.cuni.cz/cs/Detail/4070|video přednášky]], [[https://cunicz-my.sharepoint.com/:o:/g/personal/63735541_cuni_cz/EgHZ50r_8PVJmdyiKhlSnsoBr1koI1loAthyZ2kTeyjsRQ?e=bkanMC|zápis z přednášky (OneNote)]]|
+| 14. 4.| Hešování s otevřenou adresací, univerzální hešování **[L 11.3-11.4]**, [[
+https://stream.cuni.cz/cs/Detail/4279|video přednášky]], [[https://cunicz-my.sharepoint.com/:o:/g/personal/63735541_cuni_cz/EgHZ50r_8PVJmdyiKhlSnsoB3OsgQAyUXxTRt5BeNqVVWw?e=D4S5Fv|zápis z přednášky (OneNote)]]|
+| 21. 4.| Rozděl a panuj - úvod, kuchařková věta, násobení dlouhých čísel **[L 10]**, [[https://stream.cuni.cz/cs/Detail/4569|video z přednášky]] [[https://cunicz-my.sharepoint.com/:o:/g/personal/63735541_cuni_cz/EgHZ50r_8PVJmdyiKhlSnsoB3OsgQAyUXxTRt5BeNqVVWw?e=D4S5Fv|zápis z přednášky (OneNote)]]|
+| 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/cs/Detail/4766|video z přednášky]], [[https://cunicz-my.sharepoint.com/:o:/g/personal/63735541_cuni_cz/EgHZ50r_8PVJmdyiKhlSnsoB3OsgQAyUXxTRt5BeNqVVWw?e=D4S5Fv|zápis z přednášky (OneNote)]]|
+| 5. 5.| Dynamické programování - Editační vzdálenost; dolní odhady na třídění; quicksort v průměrném případě [[https://stream.cuni.cz/cs/Detail/4937|video z přednášky]], [[https://cunicz-my.sharepoint.com/:o:/g/personal/63735541_cuni_cz/EgHZ50r_8PVJmdyiKhlSnsoB3OsgQAyUXxTRt5BeNqVVWw?e=D4S5Fv|zápis z přednášky (OneNote)]] **[L 12.3, 3.3, 11.2]**|
 {{page>teaching:bits:zdroje_ads1}}
+{{ :teaching:zkouska.pdf |Okruhy, průběh zkoušky. (PDF)}}
+===== 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, případně na ně najít méně efektivní algoritmus. Pokud jsme na přednášce o algoritmech vyslovovali nějaká tvrzení, je třeba znát aspoň zhruba jejich znění.
+**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 //nepředstavují// konkrétní příklady na algoritmy či datové struktury. Je zřejmé, že některé okruhy níže jsou širší a některé užší. Pokud ale budete mít přehled o všech tématech níže, nic na zkoušce by vás nemělo zaskočit.
+  * BFS, DFS a jejich klasifikace hran
+  * Aplikace DFS: topologické třídění, detekce SSK
+  * 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,b)$-stromy
+  * Č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í, třídění v srovnávacím modelu