Lukáš Ondráček
Katedra teoretické informatiky a matematické logiky
ondracek@ktiml.mff.cuni.cz
Pracovna S207 (Malá Strana, 2. patro)
zpět na seznam předmětů

Cvičení z Datových struktur 1, úterý 15:40 v S6 přes Zoom, ZS 2021/2022

V zimním semestru 2021/2022 vedu cvičení k předmětu NTIN066, Datové struktury 1.

Zápočet je možné získat za řešení domácích úkolů podle pravidel na samostatné stránce.
Úkoly budou zadávány prostřednictvím systému ReCodEx, vždy se začátkem cvičení,
krátce před zadáním bude k dispozici také kostra řešení v gitovém repozitáři.

Účast na cvičení je nepovinná.
Cvičení slouží hlavně jako prostor pro dotazy.
Dále se na něm budou zadávat úkoly (vše potřebné je i online),
ukazovat jejich řešení (vzorové kódy jsou po termínu v ReCodExu)
a příp. řešit příklady k procvičení látky z přednášky -- ty ale nemají přímý vliv na zisk zápočtu.

Od 30. 11. 2021 cvičení probíhá distančně přes zoom, bližší informace byly rozeslány mailem.
Procvičované příklady zde budu sepisovat včetně řešení.

\( \def\cO{\mathcal{O}} \def\cH{\mathcal{H}} \def\cU{\mathcal{U}} \def\LCP{\mathrm{LCP}} \def\reals{\mathbb{R}} \)
Rozbalit všechna řešení a ostatní skryté části níže.

4. 1. 2022

Zkuste si ve hře The Deadlock Empire střídavě krokovat kódy více vláken tak, aby došlo k nějaké nechtěné situaci -- souběžné vykonání kritické sekce, deadlock, zacyklení, porušení assertu, ... Jiné příklady nejsou, od minulého cvičení se nekonala žádná přednáška. Poslední cvičení tak můžeme věnovat dotazům.

21. 12. 2021

Příklady:

14. 12. 2021

Přiklady:

7. 12. 2021

Úkol není, deadline pro hash_experiment se posouvá na tři týdny od zadání. Pro univerzalitu a nezávislost hešovacích funkcí používáme rozšíření značení z přednášky.
Parametr $c>0$ je vždy reálný a $k≥1$ přirozený. Systém hešovacích funkcí $\cH$ z univerza $\cU$ do množiny přihrádek $[m]$ je Na přednášce se implicitně pracuje s přesnou univerzalitou/nezávislostí (c=1). Ve skriptech se implicitně používá přibližná univerzalita/nezávislost (c libovolné), $c$-přibližná univerzalita se tam označuje jako $c$-univerzalita a $c$-přibližná $k$-nezávislost jako $(k,c)$-nezávislost.
Příklady:
  1. Dokažte, že pokud je $\cH$ $c$-přibližně 2-nezávislý, pak je i $c$-přibližně univerzální.
    Z definice 2-nezávislosti nás zajímají jen případy, kdy dojde ke kolizi: $∀x_1,x_2∈\cU, x_1\ne x_2, ∀a∈[m]: Pr_{h∈\cH}[h(x_1) = a \land h(x_2) = a] ≤ c/m^2$. Sečteme pravděpodobnost kolize ve všech přihrádkách: $Pr_{h∈\cH}[h(x_1) = h(x_2)] = \sum_{a∈[m]} Pr_{h∈\cH}[h(x_1) = a \land h(x_2) = a] ≤ m\cdot c/m^2 = c/m$.
  2. Dokažte, že pokud je $\cH$ $c$-přibližně $k$-nezávislý pro $k>1$, pak je i $c$-přibližně $(k-1)$-nezávislý.
    Stejně jako v předchozím příkladu sečteme přes možné výběry jedné z přihrádek: $∀x_1, \dots, x_k ∈ \cU$ navzájem různá a $∀a_1, \dots, a_{k-1} ∈ [m]:$ $\;\;\;Pr_{h∈\cH}[h(x_1) = a_1 \land \dots \land h(x_{k-1}) = a_{k-1}] =$ $\;\;\;=\sum_{a_k∈[m]} Pr_{h∈\cH}[h(x_1) = a_1 \land \dots \land h(x_k) = a_k] ≤ m\cdot c/m^k = c/m^{k-1}$.
  3. Mějme systém $\cH_1 = \{h(x) = x\}$ o jedné funkci, kterou je identita (tedy $\cU = [m]$). Je $\cH_1$ $c$-přibližně univerzální pro nějaké $c$? Je $\cH_1$ $c$-přiblizně $k$-nezávislý pro nějaká $k$ a $c$?
    U různých prvků nemůže nastat kolize, systém je univerzální pro libovolnou konstantu $c$: $∀x,y∈\cU, x\ne y: Pr_{h∈\cH_1}[h(x) = h(y)] = 0 ≤ c/m$ pro lib. $c$. Každý prvek má pevně danou přihrádku, systém tak není ani 1-nezávislý pro žádnou konstantu $c$: $∀x∈\cU, ∃a∈[m]: Pr_{h∈\cH_1}[h(x) = a] = 1 > c/m$ pro lib. pevně zvolené $c$ a dostatečně velké $m$.
  4. Mějme systém $\cH_2 = \{h_a(x) = a\mid a∈[m]\}$ všech konstantních funkcí. Dokažte, že $\cH_2$ je (přesně) 1-nezávislý? Dokažte, že $\cH_2$ není ani přibližně 2-nezávislý ani přibližně univerzální.
    Je 1-nezávislý: $∀x∈\cU, ∀a∈[m]: Pr_{h∈\cH_2}[h(x) = a] = 1/m$. Není 2-nezávislý, protože výběrem přihrádky pro libovolný prvek máme určenou přihrádku i pro všechny ostatní: $∀x,y∈\cU, x\ne y, ∀a∈[m]: Pr_{h∈\cH_2}[h(x) = a \land h(y) = a] = Pr_{h∈\cH_2}[h(x) = a] = 1/m > c/m^2$ pro lib. pevně zvolené $c$ a dostatečně velké $m$. Není univerzální, protože kolize dvou prvků nastane vždy: $∀x,y∈\cU, x\ne y: Pr_{h∈\cH_2}[h(x) = h(y)] = 1 > c/m$ pro lib. pevně zvolené $c$ a dostatečně velké $m$.

30. 11. 2021

Budete-li se učit ze skript Martina Mareše, tak pozor na to, že používá trochu jinou definici univerzality a nezávislosti. Příklady:
  1. Ukažte, že v hešovací tabulce velikosti $m=n^2$ s $n$ prvky dojde ke kolizi s pravděpodobností maximálně $1/2$, předpokládáme-li zcela náhodnou hešovací funkci.
    $Pr[\text{kolize}] = Pr[∃i\ne j∈[n]: h(i)=h(j)] \le {n\choose 2}\cdot {1\over m} \le {n^2\over 2}\cdot {1\over n^2} = {1\over 2}$
  2. Spočítejte jaký nejmenší počet lidí $n$ se musí sejít, aby byla pravděpodobnost aspoň 1/2, že někteří dva z nich mají narozeniny ve stejný den. Předpokládejte $m=365$ dní v roce s rovnoměrným rozdělením pravděpodobnosti, že neznámý člověk bude mít ten den narozeniny. Překvapivě malý výsledek se označuje jako narozeninový paradox.
    Spočítejte nejprve pro konkrétní $n$ pravděpodobnost, že nenastane kolize; dosazováním poté najděte správnou hodnotu. Z přesného vzorce nemusí být vidět, jakou hodnotu $n$ zvolit, zkuste k němu spočítat jednodušší horní odhad.
    $n=23$
    Pravděpodobnost, že nenastane kolize pro konkrétní $n$, je $p_n = 1 \cdot \left(1-{1\over m}\right) \cdot \left(1-{2\over m}\right) \cdots \left(1-{n-1\over m}\right)$; postupně pronásobujeme pravděpodobnosti, že následující člověk nezpůsobí kolizi. Pro zjištění přibližného $n$ odhadneme pravděpodobnost následovně: $p_n\le 1 \cdot e^{-{1\over m}} \cdot e^{-{2\over m}} \cdots e^{-{n-1\over m}} = e^{-{1\over m}(1 + 2 + \cdots + n-1)} = e^{-{n(n-1)\over 2m}} \le e^{-{(n-1)^2\over 2m}}$. Pravděpodobnost omezíme $1/2$: $e^{-{(n-1)^2\over 2m}} \le 1/2$ $-{(n-1)^2\over 2m} \le \ln{1/2}$ $(n-1)^2 \ge 2m\ln{2}$ $n \ge \sqrt{m\ln{4}} + 1 \approx 23.5$ Podmínku tedy určitě splňuje skupina 24 lidí, dosazením do přesného vzorce zjistíme, že i 23, ale 22 už ne: $p_n = {m\over m} \cdot {m-1\over m} \cdot {m-2\over m} \cdots {m-n+1\over m} = {m!\over (m-n)!\cdot m^n}$, $p_{23} \approx 0.49,$ $p_{22} \approx 0.52.$

23. 11. 2021

Cvičení se koná přes zoom, příklady nakonec nejsou, takže půjde spíš o konzultace.

16. 11. 2021

Příklady:
  1. Ukázat, že LRU není kompetitivní s OPT, mají-li stejnou paměť.
  2. Spočítat I/O složitost rekurzivního násobení matic.
    Matice dělíme na čtvrtiny a rekurzivně provádíme pronásobení příslušných podmatic s přičtením výsledku do cílové matice -- veškeré přístupy do paměti se tak dějí až na nejnižší vrstvě. Předpokládáme vysokou cache (M ∈ O(B^2)). Zaostříme na úroveň rekurze, kde se nám vlezou do paměti všechny tři matice. S vysokou keší má každá rozměr Θ(√M)×Θ(√M). Celkem máme na této úrovni Θ((N/√M)^2) podmatic a každou zpracováváme Θ(N/√M)-krát; jako při násobení matice o rozměrech Θ(N/√M)×Θ(N/√M). Načtení jednoho řádku podmatice nás stojí O(√M/B). Vysoká cache nám mj. zajistí, že je to aspoň jeden blok, takže nepotřebujeme aditivní jedničku. Špatné zarovnání vyřešíme dvojnásobnou konstantou v O. Načtení jedné podmatice nás pak vyjde na O(M/B). Celkem dostaneme I/O složitost O((N/√M)^3 ⋅ M/B) = O(N^3/(B√M)), nevlezou-li se do paměti všechny matice najednou; jinak odpovídá složitost sekvenčnímu čtení. Za předpokladu vysoké keše tedy máme složitost O(N^3/(B√M) + N^2/B + 1). (Sekvenční přístup zároveň potřebujeme pro počáteční vynulování cílove matice.)

9. 11. 2021

Příklady:
  1. Spočítat časovou a I/O složitost rekurzivního transponování, když v každém kroku rekurze provedeme zvlášť prohození podmatic a rekurzivní transpozici.
  2. Spočítat I/O složitost merge sortu, kde máme vždy v jednom poli za sebou setřízené posloupnosti a po dvojicích je sléváme do posloupností dvojnásobné délky ve druhém poli. (Základem je tedy cyklus, ne rekurze.)
  3. Spočítat I/O složitost (a časovou) k-cestného merge sortu. Ten narozdíl od předchozího algoritmu slévá vždy k posloupností současně a pro výběr minima používá k-prvkovou haldu. Předpokládáme M ≥ 2k⋅B, aby se nám do paměti vlezla halda i potřebné části rozečtených posloupností.

2. 11. 2021

Cvičení se prezenčně nekoná; ve stejném čase je možnost konzultací přes zoom, bližší informace rozeslány mailem (napište pokud nedošel).

26. 10. 2021

Ukázána varianta (a,b)-stromu, která má hodnoty i ve vnitřních vrcholech (každý klíč je ve stromě jen jednou), viz skripta Martina Mareše. Příklady:
  1. Provést zadané operace na daném (2,3)-stromu.
  2. Jaký je potenciál splay stromu, který je cesta?
  3. Jaký je potenciál splay stromu, který je úplný binární strom hloubky k.

19. 10. 2021

Pro účely cvičení a úkolu zavedena naivní implementace splay stromů, která provádí jen jednoduché rotace. Příklady:
  1. Navrhnout posloupnost operací, která vytvoří strom lineární hloubky v naivní i standardní implementaci.
  2. Navrhnout posloupnost k operací s celkovou složitostí Ω(kn) v naivní implementaci. Co se stane při použití stejné posloupnosti ve standardní implementaci?
  3. Navrhnout operace split a join s logaritmickou amortizovanou složitostí. Split ve vrcholu strom rozdělí na strom se všemi menšími prvky a strom se zbylými prvky. Join dvou stromů, z nichž jeden má všechny prvky menší než každý prvek ve druhém, tyto stromy spojí do jednoho.
  4. Navrhnout alternativní implementaci insert/delete využívající split/join.

12. 10. 2021

Ukázali jsme si, jak funguje operace splay a kdy ji použít. Amortizovanou logaritmickou složitost jsem jen zmínil bez důkazu. Dvojrotace je možné poskládat ze dvou jednoduchých rotací, jen pozor na jejich pořadí. Rotace je lepší vztáhnout k hranám -- rotování konkrétní hrany je jednoznačná (a možná i intuitivnější) operace narozdíl od rotování vrcholu nebo ve vrcholu, kde potřebujeme znát i směr. Příklady:
  1. Provést splay v daném stromě.
  2. Amortizace delete v líně vyvažovaných stromech.
  3. Složitost projití celého binárního stromu pomocí funkce následníka.

5. 10. 2021

Úvodní informace. Příklady:
  1. Úprava natahovacího pole, aby se umělo i zmenšovat.
  2. Amortizovaná složitost binárního inkrementování (v počtu překlopených bitů).