Try   HackMD

ADS úlohy D - Rovnováha

Předpokládám, že o stromu nevím nic, měl bych jej tak nejprve redukovat a nikoli přestavovat za běhu. Tedy:

  1. Strom přeměním na spojový seznam
  2. Ze spojového seznamu udělám vyvážený vyhledávací strom.

Jak na to, mám-li omezenou paměť? Pravděpodobně budu muset při každém kroku prvky umazávat.

1.

Plánuju-li udělat spojový seznam, pak by umazání šlo provést v konstantním (a celkově lineárním) čase; jdu-li doleva (hledám nejmenší vrchol), ten bude určitě list. Druhý nejmenší vrchol bude jeho otec, a zde již mohou nastávat problémy. Předpokládám-li však, že se nějak chytře dokážu dostat "nahoru", mohu se pouze vrátit do otce a přepojit jej.

Tím pádem vždy pouze umazávám vrchol s

1 synem nebo žádným.

Předtím, než daný prvek smažu, jej samozřejmě zapíšu do spojového seznamu.

2.

Jakmile mám daný spojový seznam, musím z něj udělat vyvážený vyhledávací strom. To lze snadno v případě, je-li počet prvků roven

2k−1 (takže třeba
7 prvků), v takovém případě bude prostřední kořenem a zbydou mi dva podstromy, které musím zkontstruovat.

Má-li levý podstrom

n2 prvků, pak pravý podstrom bude začínat na
n−1−n2-tém prvku spojového seznamu.

Vzhledem k této skutečnosti (pamatuji si, kde začnu dělat nový strom) také nemusím prvky uchovávat, při konstrukci stromu je mohu rovnou mazat.

Tedy např. pro 8 prvků:

  1. Udělám strom z 1-4,6-8 a kořenem bude 5
  2. Udělám strom z 1-2,4 a kořenem bude 3
  3. Udělám strom z 1, kořenem bude 2
  4. Kořenem je 2, nemám pravý podstrom, vracím se zpět
  5. Kořenem je 3, napojím pravý podstrom
  6. Kořenem pravého postromu je 4, vracím se zpět

…

Při každém takovém volání musím vrátit kořen.

Bohužel, nevím, zdali je akové rekurzivní volání povoleno (pokud s tím přehazuji i prvky), zřejmě by se to nevlezlo do paměti.

Last changed by 
 
Daar543
0
71

Read more

ADS úlohy E - podobne

Nejprve je potřeba si rozmyslet, zda přidání dalšího prvku na konec posloupnosti ovlivní dosavadní posloupnosti: Budu-li postupovat v posloupnosti od konce do začátku, mohu najít první číslo, jehož rozdíl s posledním číslem přesáhne toleranci ($k$). Pro další výpočty pak mi stačí uvažovat pouze úsek napravo od tohoto čísla. Zároveň je však potřeba si uvědomit, že i předposlední číslo již vyhradilo jakýsi úsek, ve kterém má smysl zkoumat podposloupnosti - budu se tak zabývat kratším z těchto úseků. Nyní vezmu následující situaci: mám posloupnost $P$ s finálním prvkem $P_{n+1}$, pro nějž je zarážka na pozici $s_1$. Jelikož se jedná o první zarážku, celá posloupnost od $0$ do $n$ je platná a tuto posloupnost nelze rozšířit zleva ani zprava. Označím tak $t_0=n$ a $s_0=0$, což znamená, že podposloupnost má délku $t_0 - s_0$. Dále, mezi $P_{s+1}$ a $P_{n+1}$ nevznikla žádná zarážka, a tak mohu postup opakovat (jako bych opět počítal od nuly), dokud nevznikne další zarážka.

Jun 18, 2020
ADS úlohy E - Matsoucin

Vím-li, jak efektivně uzávorkovat $n$ matic, pomůže mi to k tomu, abych věděl, jak uzávorkovat $n+1$ matic? Příklad: součin délky 4+1: $ABCDE=(ABCD)(E)=(ABC)(DE)=(AB)(CDE)=(A)(BCDE)$ Z něj je vidět, že nemohu postupovat tak, že zjistím uzávorkování pro první matice, přidám k nim další a pak provedu triviální výpočet. Musím postupovat slučováním - nejprve zjistím složitost pro všechny součiny délky 2, pak délky 3... Dále je vidět, že pro hledání složitosti násobení $n+1$ matic musím provést $n+1$ porovnání pro danou posloupnost. Vytvořím si tak následující tabulku: $\begin{pmatrix}A & B & C & D & E \ AB & BC & CD & DE \ ABC & BCD & CDE \ ABCD & BCDE \ ABCDE\end{pmatrix}$

Jun 16, 2020
ADS úlohy E - prank

Permutaci čísel zde budu označovat jako řetězec. Je-li na posledních $p$ pozicích řetězce rostoucí posloupnost, pak prvek těsně před touto posloupností se změní až v $p!$-té následující permutaci. Aby se totiž na pozicích od $n-p$ do $n-1$ (indexuji od nuly) změnila posloupnost na klesající, budou se muset vystřídat všechny permutace na těchto pozicích - od lexikograficky první do lexikograficky poslední. Jak toto pomůže při sestavování dané permutace? Příklad (pořadí, řetězec): $0: 123$ $1: 132$ $2: 213$ $3: 231$ $4: 312$

Jun 13, 2020
Lineární algebra 2 DÚ - sada 8

1. 1) Jedná se o zobrazení z $R^1$ do $R$. Linearita násobení: $(\alpha x * y)=(x * \alpha y)=(\alpha x y) = \alpha(x * y)$. Linearita sčítání: $((x+z)y)=(xy+zy)=(xy)+(zy)$ (a obdobně $(x(z+y))$). Matice zobrazení: $\begin{pmatrix} 1 \end{pmatrix}$ 2) Linearita násobení: Násobení $\alpha x$ (nebo $\alpha y$) vynásobí $\alpha$ každou složku vektoru $x$. Tím pádem $a(\alpha x,y)= \alpha x_1 y_1 + 2 \alpha x_2 y_1 + 3 \alpha x_2 y_2 = \alpha(x_1 y_1 + 2x_2 y_1 + 3 x_2 y_2) = \alpha a (x,y)$. Tentýž výsledek produkuje i $a(x,\alpha y)$, jelikož násobení je komutativní.

Jun 5, 2020
Read more from Daar543
Published on HackMD