# Programování II pro matematiky ## Teoretické cvičení 12 **19. 5. 2021** Martin Mareš a Tomáš Karella --- ## Plán cvičení - Opakování - Řešení domácích úkolů - On-line kvíz - Příklady --- ### Opakování - graf - Matice sousednosti - Je vhodná pro malé grafy s velkým množstvím hran
--- ### Opakování - graf - Seznam následníků
--- ### Opakování - graf - Seznam hran
--- ### Opakování - graf - Matice incidence - (vhodné pro grafy, které mají více hran než vrcholů)
--- ### Opakování - BFS vs DFS
--- ### Domácí úkol - slova Máme rozsáhlý soubor s textem délky $N$ slov, který se nám nevejde do paměti počítače. Máme pak druhá rozsáhlý soubor, kde na každém řádku máme všechny gramatické tvary téhož slova („synonyma“). Tyto skupiny (tzn. řádky) jsou navzájem disjunktní, soubor obsahuje celkem $M$ slov. První slovo na každém řádku = základní tvar (vypisuje se na výstup). Ani druhý soubor se nevejde do do vnitřní paměti počítače. Najděte algoritmus, který nalezne nejčastějších 100 slov (bez ohledu na gramatický tvar použitý v textu). Nalezená slova vypište v základním tvaru. Snažte se omezit množství čtení a zápisů na disk. Zapište váš algoritmus v nějakém pseudokódu a krátce popište svoje řešení. Určete časovou složitost v závislosti na $M$ a $N$. --- #### Operace na FS: - Soubor otevřeme na: čtení / zápis / přidávání na konec - S otevřeným souborem umíme: číst znak / zapsat znak / přesunout se na jinou pozici (přesun není triviální operace a neumíme vkládat do souboru) #### K časové složitosti - soubory se nevejdou do paměti → $n$ řádově $10^9$ - časová složitost $\mathcal{O}(n^2)$ vstupně/výstupních operací → $10^{18}$ operací - rychlost procesoru $10^9$ op/s ve vnitřní paměti, ale jen $10^7$ op/s vstupně/výstupních operací - tedy doba výpočtu $10^{11}$ sekund = **3000 let** - časová složitost $\mathcal{O}(n \log(n))$ vstupně/výstupních operací → $6 \cdot 10^{10}$ operací - tedy doba výpočtu 6000 sekund = **2 hodiny** --- ### Domácí úkol - halda - Vlastnosti haldy jsou určené invarianty, algoritmus by je měl dodržovat - Při odebírání minima (maxima) do kořene přesunujeme poslední prvek z haldy (nejpravější prvek ve nejspodnější hladině). - Přesouvání synů do kořene vždy nefunguje. Zkuste pak ve skupinkách vymyslet protipříklad. --- ### Organizační záležitosti - Zbývají nám ještě dvě celá cvičení do konce akademického roku - Pokud budeme navrhovat známku, tak interně od nás dostanete dvě známky: - Za teoretické cvičení - Za praktické cvičení - Výsledná známka bude jejich průměr (přihlédneme k aktivitě na cvičeních a k domácím úkolům) --- ### Kvíz https://quizizz.com/admin/quiz/60a5196aed842b001edd03bf/startV4 --- ### Příklady (1) Zapište následující graf pomocí všech reprezentací:
Určete pro všechny reprezentace prostorovou složitost pro uložení $N$ vrcholů a $M$ hran. Určete časovou složitost pro následující operace: - Je mezi `x` a `y` hrana? - Vypsání všech následovníků vrcholu `x`. - Přidání hrany nebo vrcholu do grafu. --- ## Příklady (2) Máme načtený graf, který má $N$ vrcholů a $M$ hran. Najděte algoritmus a určete jeho časovou a prostorovou složitost. Promyslete, jak se algoritmus bude lišit pokud bude reprezentován pomocí matice sousednosti a seznamu následníků. 1. Nalezněte vrchol, který má nejvíce následovníků. 2. Určete kolik má daný graf komponent souvislosti. 3. Určete jestli daný graf obsahuje cyklus. 4. Jaký je vztah mezi počtem vrcholů a počtem hran? 5. Je-li $A$ matice sousednosti grafu, co popisuje matice $A^2$? A co $A^k$? (Mocniny matic definujeme takto: $A^1=A$, $A^{k+1}=A^kA$.) 6. Upravte BFS tak, aby pro každý dosažitelný vrchol zjistilo, kolik do něj vede nejkratších cest z počátečního vrcholu. Zachovejte lineární časovou složitost. 7. Jakou časovou složitost by DFS mělo, pokud bychom graf reprezentovali maticí sousednosti?