MK's wiki

Tato stránka je pouze pro čtení. Můžete si pouze prohlédnout zdrojový kód, ale ne ho měnit. Zeptejte se správce, pokud si myslíte, že něco není v pořádku.
====== Přednáška z Algoritmů a datových struktur I 2019/20 ======

Přednáším Diskrétní matematiku ([[https://is.cuni.cz/studium/predmety/index.php?id=94f10a35af9ff69aeb38eb9166a34c3c&tid=&do=predmet&kod=NTIN060&skr=2019&fak=11320|NTIN060]]) každé úterý v 10:40 v učebně S11.

Pokud se mnou chcete cokoliv probrat, jste vítáni v mé pracovně S326 na Malé Straně. Případně napište e-mail na adresu ''koutecky+ads1@iuuk.mff.cuni.cz'' a/nebo uveďte v předmětu text ''[ADS1]''.

V druhé paralelce přednáší [[http://ktiml.mff.cuni.cz/~hric/vyuka.htm#Alg|Jan Hric]], přednášku se budeme snažit udržovat synchronní.

{{tablelayout?colwidth="100px,-"&rowsHeaderSource=1&rowsVisible=100&float=left}}
^ 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}, \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. 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