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, 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.

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. Řešení:
    • 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ů).