pojmy

• nejdelší neklesající podposloupnost
• dynamické programování
• minimální kostry

Prezentace

cv9.pdf

Domácí úlohy

vanoce_ukol.pdf

Cvičení vedl Tung Anh Vu v učebně TH:A-1455.

řešené úlohy

• Dáno $n$ měst označených čísly $1, . . . , n$, z každého vedou cesty pouze do měst s vyšším číslem, cesty jsou jednosměrné. Kolika způsoby se lze dostat z města $1$ do města $n$?
• Kolika možnostmi lze vydláždit mřížku velikosti $2 × n$ dlaždičkami $1 × 2$ a $2 × 1$? A co čtverci $2 × 2$, kterým chybí jeden roh?
• Je dán řetězec. Jak ho rozřezat na co nejmenší počet bloků takových, že každý blok tvoří palindrom?
• Na vstupu je strom $T$. Vymyslete algoritmus, který v něm hledá nejdelší cestu. A co když jsou hrany vážené?

Na 10. cvičení se bude psát semestrální test. Ukázkový semestrální test najdete zde.

pojmy

• hešování
  • hešovací tabulka, funkce
  • kolizní pár
  • otevřená adresace
• rozděl a panuj
  • problém hanojských věží

řešené úlohy

• vybírání náhodného řádku v souboru na jeden průchod
• kdy použít hešovací tabulku
• ukázky jednoduchých hešovacích funkcí
• hledání kolizí hešovacích funkcí
• hešování řetězců
• příklad na otevřenou adresaci
• optimalita algoritmu hanojských věží
• úprava problému hanojských věží - zákaz přesunu mezi A a B

Prezentace

cv8.pdf

pojmy

• pravděpodobnostní prostor, jev, pravděpodobnost
• náhodná veličina, střední hodnota, čekání na náhodný jev

řešené úlohy

• náhodné číslo z intervalu pomocí instrukce randombit
• procvičování výpočtu pravděpodobnosti (sčítací a násobící princip)
• výpočet střední hodnoty jednoduchého experimentu
• střední počet použití instrukce randombit při generování náhodného čísla z intervalu
• generování náhodné permutace
• složitost v průměrném případě, složitost generování náhodné permutace přes umisťování do přihrádek

Prezentace

cv7.pdf

pojmy

• amortizovaná složitost
• binomiální halda
• binární vyhledávací strom

řešené úlohy

• Simulace fronty pomocí dvou zásobníků
• Analýza nafukovacího pole účetní metodou, varianty nafukování
• Binomiální strom $B_k$ má v $i$-té vrstvě $k \choose i$ vrcholů
• Operace DecreaseKey, Delete a IncreaseKey pro binomiální haldu
• Procházení BVS v $\mathcal O(1)$ paměti

Prezentace

cv6.pdf

pojmy

• Compare-And-Exchange model
• řazení
• binární halda

řešené úlohy

• řazení
  • vážení kuliček
  • dolní mez počtu porovnání při hledání minima
  • jak při řazení minimalizovat počet prohození
  • hledání $\lfloor \sqrt n\rfloor$ nejmenších prvků v čase $\mathcal O(n)$
  • řazení pole, ve kterém pouze $k \ll n$ prvků je na špatné pozici
  • řazení řetězců
• binární halda
  • minimální a maximální počet prvků v haldě dané výšky
  • nalezení $k$ nejmenších prvků v poli v čase $\mathcal O(n \log k)$

Prezentace

cv5.pdf

pojmy

• kostra grafu
• topologické uspořádání

řešené úlohy

• Hledání nejkratší cesty ve sklepení se zámky a klíči - varianta s jedním typem klíče.
• Hledání nejkratší vážené cesty v grafu hranově ohodnoceném váhami $0,1$.
• Kolik koster má $K_{2,n}$?
• Pro každou hranu mimo kostru lze najít takovou hranu v kostře, že jejich výměnou nerozbiji kostru.
• Maximální počet hran v DAGu.
• Jednoznačnost topologického uspořádání - nutná a postačující podmínka.

Prezentace

cv4.pdf

pojmy

• stromy
• iterativní do hloubky
• prohledávání do šířky

řešené úlohy

• Strom maximálního stupně D má alespoň D listů
• Existence stromů pro každý soubor stupňů, který se sečte na $2n-2$.
• Úpravy DFS a BFS.
• Hledání nejkratší cesty ve sklepení se zámky a klíči - varianta s jedním typem klíče.

Prezentace

cv3.pdf

pojmy

• matematická indukce na grafech
• prohledávání do hloubky a do šířky
• stromy

řešené úlohy

• graf obsahující kružnici obsahuje také indukovanou kružnici
• minimální počet hran v grafu o $n$ vrcholech a $c$ komponentách
• bipartitnost grafu
• modifikace DFS
• úloha s přeléváním vody

Prezentace

cv3.pdf

Řešení 2. úkolu

cv2_ukol.pdf

pojmy

• isomorfizmus, automorfizmus
• $k$-regulární grafy
• cesta v grafu
• podgraf, indukovaný podgraf
• souvislost grafu, souvislé komponenty

řešené úlohy

• izomorfismus na $n-k$-regulárních grafech, testování izomorfismu
• izomorfismus grafů a jejich doplňků
• počet automorfismů na $K_n$ po odstarnění některých hran
• minimální počet hran aby byl graf souvislý
• neexistence nesouvislého grafu s nesouvislým doplňkem
• počítání podgrafů a indukovaných podgrafů úplného grafu
• je $n$-regulární graf na $2n$ vrcholech souvislý?

Prezentace

cv2.pdf

Řešení 1. úkolu

cv1_ukol.pdf

pojmy

• asymptotická složitost
• základní grafové pojmy (graf, stupeň, doplněk grafu, soubor stupňů)
• princip sudosti

řešené úlohy

• dvojice se zadaným součtem v uspořádaném poli
• analýza složitosti na hvězdičkách
• úlohy na princip sudosti
• existence grafů daných vlastností (dle počtu vrcholů a hran, souboru stupňů)
• za domácí úkol důkaz věty o izomorfismu grafů a jejich doplňků

Prezentace

cv1.pdf