Algoritmy a datové struktury

Základní informace

Ideálním kontaktem na mě je e-mail.

Přednášky

Informace možno naleznouti na stránce Martina Mareše.

Pravidla udělení zápočtu

Do indexu se Vám podepíši, pokud ziskáte alespoň polovinu (=100) bodů z domácích úkolů.

Zadání ze cvičení

Co je to algoritmus a problémy ála programování
Bezprostřední následovník a předchůdce v BVS, odvození insert do AVL stromů a malý rozbor (zbytek doma) pro delete z AVL stromů
(a,b)-stromy insert a delete, vlevo naklonene C-C stromy (left-leaning R-B trees), příklady insertu/deletu
rekurence a kuchařka
rozděl a panuj
Dolní odhad na složitost obecného merge (vyvážených/AVL/(a,b)/...) stromů; dosažitelnost a počet sledů v grafu; umocňování matic a čísel obecně; násobení matic na RAMu s lib. dlouhými slovy.

Domácí úkoly

Pravidla

Účast na cvičení není povinná. Zápočet je za zisk 100 bodů z domácích úloh případného zápočtového programu či práce. Domácích úloh bude vypsáno za cca 170 bodů, zveřejněny jsou vždy níže na stránce. Na odevzdání za plný počet bodů máte 14 dní od zadání, finální termín odevzdání je konec výuky v letním semestru (konec května) krom několika posledních sérií.

Domácí úlohy odevzdávejte emailem nejlépe jako čistý text či jako PDF. Neposílejte mi fotky ručně psaného textu, ale dobře nafocené obrázky jsou v pořádku. Pokud nechcete být uvedeni ve veřejné tabulce bodů či preferujete přezdívku (nechcete třeba být vyhledatelní), napište to ke každému vašemu řešení.

U každého úkolu uvádějte paměťovou a časovou složitost. Na používaná fakta/věty/pojmy/... uvádějte reference či důkazy.

Zápočtový program za cca 30 bodů (dle obtížnosti a kvality splnění) je implementace nějaké varianty datové struktury či algoritmu z přednášky. Jazyk je omezen jen schopnostmi cvičícího (tedy C, C++, Python, C#, Java, Pascal, Haskell, Lisp a další jsou OK), implementace musí být funkčí a obsahovat krátký popis (co a jak je implementováno) a testovací data či testovací kód (knihovna tedy nemusí řešit načítání dat ze souboru a pod.). Pokud bude téma složitější, může být práce jen teoretická (pseudokód).

Termín na domluvení programu je do 14. června, termín odevzdání hotové verze pak konec června. Ostatní domácí úlohy mají až na výjimky termín do konce května.

První sada (26.02.)

(6 bodu) Navrhnete algoritmus, který pocte pocet inverzí zadané permutace $p$, tedy "dvojic ve špatném pořadí": $\{(a,b)|a< b, p(a) > p(b)\}$.
(6 bodu) Najdete v posloupnosti nejdelsi usek, v nemz se zadna hodnota neopakuje.
(8 bodu) Jak v lepším než lineárncase najít medián sjednocení dvou setridených posloupnost?
(Vstup je zadan jako už nctená pole jen kectení, nebo jako orakulum ktere umi vratit k-ty prvek z dane vstupni posloupnosti.)
Hint o rekurzi na k-tý nejmenší.

Druhá sada (05.03.)

(9 bodů) Vymyslete algoritmus, který v lineárním čase přebuduje vyhledávací strom na dokonale vyvážený (pro každý vrchol platí, že počet prvků v jeho levém a pravém podstromě se liší nanejvýs o jeden prvek). Má to ale háček, máte jen tolik paměti kolik je velikost stromu a k tomu konstantní prostor navíc.
(6 bodů) Dostanete dva BVS. V prvním jsou hodnoty menší než v druhém. Navrhněte algoritmus, který je spojí do jednoho. (Mea culpa: Mělo se jednat o AVL stromy.)

třetí sada (12.03.)

(5 bodů) Mějme rekurzivní algoritmus pracující v čase $T(n)$ na datech velikosti $n$. Jeho rekurence je popsána jako: $$ T(n) = k \cdot T(n/k) + c\cdot k\cdot n $$
- Odvoďte uzavřenou formulku pro funkci $T(n) = f(c,k,n)$ a zapište ve velké-O notaci.
- Kdybyste měli k dispozici tři verze tohoto algoritmu, pracující s $k = 2,3$ nebo $4$, který byste si vybrali?
(6 bodů) Odvoďte uzavřenou formulku pro funkci $T(n)$ a zapište ve velké-O notaci, Pro funkci zadanou rekurentní rovnicí: $$ T(n) = \frac{2}{n} \cdot (T(0) + · · · + T(n − 1)) + c $$ kde $T(0) = 0$.

Čtvrtá sada (19.03.)

(8 bodů) Úloha min-strom. Minimový binární strom $M(a)$ pro zadanou posloupnost $a=(a_1\dots a_n)$ bez opakujících se prvků je definován takto:
Buď $a_i$ minimální prvek $a=(a_1\dots a_n)$; pak kořen $M(a)$ je $a_i$, jeho levý podstrom je $M(a_1\dots a_{i-1})$ a pravý podstrom $M(a_{i+1}\dots a_n)$. $M(\emptyset)$ je prázdný strom.
Pro zadanou posloupnost postavte minimový strom v čase $O(n)$.
(5 +4 bodů) Úloha na dráty. Dostali jste nádherný $n$-žilový kabel, ale protože jste barvoslepí, nevíte, který drát z levého konce kabelu je spojený se kterým na pravém konci. Levé i pravé konce si tedy očíslujete, připravíte si zdroj nízkého napětí a zkoušečku nízkého napětí a pustíte se do práce.
Jedna operace je připojení napětí na jeden z vodičů vlevo, odpojení napětí z vodiče vlevo, a zkouška jednoho vodiče vpravo, zda je pod napětím. Vlevo může být připojeno i více vodičů najednou, vpravo testujete vodiče po jednom. Cílem je zjistit, které vodiče jsou spojené (vždy jeden vlevo s jedním vpravo) a minimalizovat při tom počet operací (asymptoticky, tedy v $O$-notaci). Jde to řádově lépe než v $O(n^2)$.
Další 4 body získáte za důkaz, že to řádově rychleji zjistit nelze, tedy že je tolik měření potřeba. Správná dolní mez je lepší než $\Omega(n)$.
(5 bodů) Tříděná majorita. Na cvičeních jsme si ukazovali, jak naleznout majoritu i pro setříděný případ. Bylo by pěkné zjistit, že rychleji už toto není možné zjistit (myšleno rychleji než v čase $O(\log n)$). Pro plný počet by tento důkaz měl být jasný a úplný.

Pátá sada

(7 bodů) Ukažte, jak upravit vyhledávací strom (například AVL), aby navíc uměl efektivně provádět operaci $mezi(x,y)$, která odpoví, kolik vrcholů stromu leží v intervalu $[x,y]$ (kde $x$ a $y$ nemusí být ve stromě přítomny). Složitost všech operací včetně této by měla být $O(hloubka)$.
(8 bodů) Šrouby a matice Máme $n$ různě velkých šroubů a $n$ odpovídajících matic (existuje mezi nimi párování). Umíme pro dvojici (šroub, matice) rozlišit stavy "pasují", "šroub moc velký" a "šroub moc malý". Šrouby mezi sebou navzájem nelze porovnávat, totéž platí o maticích. Vymyslete, jak šrouby s maticemi co nejrychleji spárovat, pokud je dostanete náhodně zamíchané, v čase průměrně $O(nlog(n))$ randomizovaně.
(5 bodů) Mějme $b$ barviček (řekněme, že je máme očíslované $1,2, \ldots, b$), $n$ různých velikostí disků, od každé velikosti právě $b$ exemplářů – tedy nám to vychází tak, že od každé velikosti disku a barvy máme právě jeden exemplář. Disky jsou, jak už tomu tak v Hanoi bývá, umístěny na tyčce (říkejme ji kupříkladu první) a úkolem je přemístit na jinou (říkejme ji třetí) za pomoci jedné odkládací.
Otázkou je kolik přesunů potřebujeme.

Šestá sada

(7 bodů) Mějme souvislý graf $G$. Jak graf ostříhat, tedy v jakém pořadí můžeme postupně (po jednom) smazat všechny jeho vrcholy tak, aby byl po každém kroku mazání graf stále souvislý?
Miřte na složitost $O(n+m)$ nebo velmi blízkou a rozeberte, jestli je to pro možné udělat pro každý souvislý graf nebo ukažtě nějaký, kde to nepůjde.
(10 bodů) Olga Opatrná najala Láďu Lenocha, aby ji pro daný neorientovaný graf $G=(V,E)$, vrchol $s\in V$ a nezáporné celočíselné váhy hran $w(u,v)$ (kde $w(u,v)=w(v,u)$) spočítal nejkratší cesty z vrcholu $s$ do všech ostatních vrcholů. Konkrétně má Láďa spočíst dvě funkce: $d(v)$ má být délka nejkratší cesty z $s$ do $v$ (nebo $\infty$, pokud taková není), a $\pi(v)$ má být předposlední vrchol na nějaké nejkratší cestě z $s$ do $v$ (nebo $\NIL$, pokud taková není).
Olga ale moc nevěří Láďově pečlivosti, a tak si chce výsledky ověřit, což se jí zdá jednodušší, než si je spočíst sama. Konkrétně ověří následující podmínky:
1. $d(s)=0$
2. $\pi(s)=\NIL$
3. $\forall (u,v)\in E: d(v) \leq d(u) + w(u, v)$
4. $\forall v\in V: \pi(v)\neq\NIL\Rightarrow d(v) = d(\pi(v)) + w(\pi(v),v)$
5. $\forall v\in V, v\neq s: d(v) < \infty \Rightarrow \pi(v) \neq \NIL$
Jak může Láďa Olze dát data $d$ a $\pi$, která nejsou korektní podle Olžina zadání, ale splňují tyto ověřovací podmínky?
Konkrétně: najděte takový graf, funkci $w$, vrchol $s$ a funkce $d$ a $\pi$, nebo ještě lépe popište takové případy obecněji. Za druhé upravte či doplňte podmínky tak, aby už každé řešení splňující tyto podmínky popisovalo nejkratší vzdálenosti a cesty.

Sedmá sada

(9 bodů) Najděte v zadaném stromě housenku na co nejvíce vrcholech. Housenka je podgraf, který se skládá z cesty na jejímž každém vrcholu jsou až čtyři listy (nožičky), ale můžou tam být i vrcholy bez nožiček. Není to totéž, co nejdelší cesta, protože nejde o housenku co nejdelší, ale na největším počtu vrcholů (tedy i s nožičkami). Řešení by mělo být v $O(n)$.
(8 bodů) Na jedné šachovnici $N\times N$ žil byl kulhavý kůň. To je je šachová figurka, která v sudém tahu táhne jako jezdec, v lichém jako pěšec (o 1 dopředu, vždy stejným směrem). Jak pro zadaná dvě políčka najít nejkratší cestu kulhavým koněm?

Osmá sada

(9 bodů) Orientovaný graf $G = (V,E)$ je polosouvislý, pokud pro každé dva vrcholy $u,v\in V$ existuje orientovaná cesta z $u$ do $v$ nebo orientovaná cesta z $v$ do $u$. Navrhněte algoritmus, který zjistí, jestli je graf $G$ polosouvislý. Dokažte jeho správnost a určete jeho časovou složitost.
(9 bodů) Každý poštovní holub, je-li vypuštěn se zprávou, s ní doletí jen na jedno místo, které je pro konkrétního holuba pevné. Ve spolku pěstitelů holubů má každý člen holuby, kteří mohou doručit zprávu k několika dalším členům. Svolat všepěstitelské setkání je možné jen tak, že ho jeden ze členů vyhlásí rozesláním zpráv všem členům, na které má holuby, a ti pak pošlou zprávu dál svými holuby.
Když znáte strukturu spolku, v čase lineárním s počtem zůčastněných holubů a členů zjistěte, zda vůbec existuje někdo, kdo má možnost setkání všech členů svolat.

Devátá sada

(9 bodů) V poušti na Sahaře byly nalezeny zbytky knihovny nějaké dávné civilizace. Civilizace znala písmo a předpokládá se, že měla i abecedu (lineární uspořádání písmenek). Vědci se domnívají, že nalezené spisy byly v knihovně seřazeny lexikograficky.
Dostanete názvy spisù, které se zachovaly a to v pořadí jak byly poskládány na poličce. Názvy spisù jsou přepsané tak, že si každý znak označíme jedním písmenkem naší abecedy.
Například pro českou knihovnu byste dostali seznam: "Alenka v říši divů", "Alexandr Veliký", "Baron Prášil", "Broučci", "Malý princ", "Medvídek Pů". Ze seznamu mùžete vyvodit, že v české abecedě je `A' před `B', ale také `n' před `x'.
Podle názvu spisù, které dostanete, zkuste potvrdit nebo vyvrátit teorii o tom, že saharská civilizace měla abecedu.
(7 bodů) Pro graf $G=(V,E)$ a startovní vrchol $s$ nalezněte pro každý vrchol $v\in V$ délku nejkratší cesty $d(v)$ spolu s číslem $h(v)\in\N$, kolik hran nejméně má nejkratší cesta.

Sada desátá a závěrečná

(7 bodů) Závod bludištěm z živých plotů! Jste rozhodnuti vyhrát a to i za cenu malé ... zkratky, kterou pravidla zapoměla zmínit. Nejste ale ochotni se křovím prodrat víc než jednou, ještě by si toho někdo všiml a mohl by to ... špatně pochopit.
Bludiště je popsáno grafem se startem, cílem, délkami hran a dvěma typy hran – chodby bludištěm a zkratky křovím, kterými se ještě jde prodrat. Navrhněte algoritmus pro nejkratší cestu do cíle v co nejlepším čase.
(10 bodů) Máme dánu $U$ jako podmnožinu vrcholů souvislého grafu $G$ s váhami hran $w$. Najděte minimální kostru grafu $G$ ze všech takových koster, které mají vrcholy z $U$ jako listy. Algoritmus by měl být stejně rychlý jako jiné vám známé algoritmy na min. kostru a měl by rozpoznat situaci, že taková kostra neexistuje.