Obě strany předchozí revizePředchozí verzeNásledující verze | Předchozí verze |
teaching:ads11920_prednaska [2020/05/05 15:29] – prednaska 5.5. Martin Koutecky | teaching:ads11920_prednaska [2020/05/26 15:25] (aktuální) – prubeh-zkousky Martin Koutecky |
---|
| 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.| 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}}| | | 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.| Plán: 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)]]| | | 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)]]| | | 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)]]| | | 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.| Plán: Hešování s otevřenou adresací, univerzální hešování **[L 11.3-11.4]**, [[ | | 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)]]| | 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 **[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)]]| | | 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)]]| | | 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/Administrace/Video/DocumentAttachments/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]**//| | | 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 |
| |
| |
| |
| |
{{page>teaching:bits:zdroje_ads1}} | |