teaching:ads11314
Rozdíly
Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
Obě strany předchozí revizePředchozí verzeNásledující verze | Předchozí verze | ||
teaching:ads11314 [2014/04/04 14:57] – dalsi priklady Martin Koutecky | teaching:ads11314 [2019/09/24 13:25] (aktuální) – Martin Koutecky | ||
---|---|---|---|
Řádek 17: | Řádek 17: | ||
- {{: | - {{: | ||
- {{: | - {{: | ||
+ | - DFS a BFS -- opakování, | ||
===== Domácí úkoly ===== | ===== Domácí úkoly ===== | ||
Řádek 93: | Řádek 94: | ||
| | ||
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ě: | 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ě: | ||
+ | |||
+ | **Úloha housenka (9b, plný počet do 24. 4. 14:00)** | ||
+ | Najděte v zadaném stromě housenku na co nejvíce vrcholech. < | ||
+ | na jejímž každém vrcholu jsou až čtyři listy (nožičky), | ||
+ | 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)$. | ||
+ | |||
+ | **Úloha kůň (8b, plný počet do 24. 4.)** | ||
+ | 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? | ||
+ | |||
+ | **Úloha polosouvislost (9b, plný počet do 15. 5.)** | ||
+ | |||
+ | Řekněme, že orientovaný graf $G$ je // | ||
+ | |||
+ | **Úloha holubi (9b, plný počet do 15. 5.)** | ||
+ | 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. | ||
+ | |||
+ | **Úloha abeceda (9b, plný počet do 22. 5.)** | ||
+ | Nalezli jste knihovnu ztracené civilizace a zkoumáte její abecedu o $n$ prapodivných znacích. | ||
+ | Každá kniha má na svém hřbetu nápis touto abecedou a doufáte, že jsou knihy seřazené abecedně (lexikograficky). | ||
+ | Rádi byste věděli, jestli z pořadí knížek lze zjistit jednoznačné pořadí znaků abecedy, jestli je pro to | ||
+ | informací málo, či zda dokonce takové pořadí nemůže existovat (a knihovnu tedy někdo přeházel). | ||
+ | |||
+ | Zadání si představte třeba jako seznam slov bez mezer z abecedy " | ||
+ | v hledané abecedě. Zkuste najít algoritmus, který to zvládne v lineárním čase s velikostí vstupu. Můžete | ||
+ | předpokládat, | ||
+ | |||
+ | **Úloha negative-floyd (8b, plný počet do 22. 5.)** | ||
+ | |||
+ | Co udělá F-W algoritmus na grafu se zápornými vahami, ale bez záporných cyklů? | ||
+ | A co udělá F-W na grafu se záporným cyklem? Svá tvrzení dokažte. | ||
+ | |||
+ | Pro bonus vysvětlete (potenciálně chybný) výsledek algoritmu a význam získaných hodnot | ||
+ | (tedy zda výsledná čísla přeci jen něco popisují). | ||
+ | |||
+ | **Úloha cheating (7b, plný počet do 22. 5.)** | ||
+ | |||
+ | Závod bludištěm z živých plotů! Jste rozhodnuti vyhrát a to i za cenu malé ... zkratky, kterou | ||
+ | pravidla zapomně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. | ||
+ | |||
+ | **Úloha listy-kostry (10b, plný počet do 22. 5.)** | ||
+ | |||
+ | Máme dánu $U$ jako podmnožinu vrcholů souvislého grafu $G$ s váhami hran $w$. | ||
+ | Najděte minimální kostru $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. | ||
===== Požadavky na zápočet ===== | ===== Požadavky na zápočet ===== | ||
Řádek 110: | Řádek 164: | ||
Termín na domluvení programu je do 15. č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. | Termín na domluvení programu je do 15. č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. | ||
- | ==== Nápady na zápočťáky ==== | ||
- | |||
- | - Implementovat R-B-stromy a (2, | ||
- | ==== Články k rozebrání ==== | + | {{page> |
- | [Časem budu doplňovat.] | ||
===== Body za úkoly ===== | ===== Body za úkoly ===== |
teaching/ads11314.1396616239.txt.gz · Poslední úprava: 2014/04/04 14:57 autor: Martin Koutecky