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/05/03 13:52] – Martin Koutecky | teaching:ads11314 [2019/09/24 13:25] (aktuální) – Martin Koutecky | ||
---|---|---|---|
Řádek 112: | Řádek 112: | ||
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. | 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 129: | Řá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, | ||
- | - [[https:// | ||
- | - < | ||
- | - Nejlepší posloupnost mezer v průměrném případě je prý 1, 4, 10, 23, ... (vizte [[https:// | ||
- | - Co kdyby se měl Shellsort přednášet? | ||
- | - **ZAMLUVENO** [[https:// | ||
- | - Implementujte [[https:// | ||
- | - Implementujte [[https:// | ||
- | - Implementujte kterýkoliv exponenciální algoritmus z [[http:// | ||
- | - Implementujte algoritmus, který rozhodne, jakou má graf // | ||
- | |||
- | ==== Články k rozebrání ==== | ||
+ | {{page> | ||
- | [Časem budu doplňovat.] | ||
===== Body za úkoly ===== | ===== Body za úkoly ===== |
teaching/ads11314.1399117976.txt.gz · Poslední úprava: 2014/05/03 13:52 autor: Martin Koutecky