MK's wiki

Uživatelské nástroje

Nástroje pro tento web

Historie:
teaching:ads11920_prednaska

Rozdíly

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

Odkaz na výstup diff

Obě strany předchozí revizePředchozí verze
Následující verze		Předchozí verze
teaching:ads11920_prednaska [2020/03/03 16:02] – 03-prednaska Martin Kouteckyteaching:ads11920_prednaska [2020/05/26 15:25] (aktuální) – prubeh-zkousky Martin Koutecky
Řádek 12: Řádek 12:
 | 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]**| | 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. 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]**| | 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.| //Plán: pokračování v nejkratších cestách **[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.| 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}} {{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
 +
 +
 +
 +
 +
teaching/ads11920_prednaska.1583247729.txt.gz · Poslední úprava: 2020/03/03 16:02 autor: Martin Koutecky