teaching:ads11516
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í verzeNásledující verzeObě strany příští revize | ||
teaching:ads11516 [2016/04/04 13:04] – Martin Koutecky | teaching:ads11516 [2016/05/14 06:38] – [Domácí úkoly] Martin Koutecky | ||
---|---|---|---|
Řádek 12: | Řádek 12: | ||
* {{: | * {{: | ||
* [[http:// | * [[http:// | ||
+ | * {{: | ||
+ | * {{: | ||
+ | * {{: | ||
+ | * {{: | ||
+ | * {{: | ||
+ | |||
+ | ===== Co se (údajně) dělalo na přednášce ===== | ||
+ | |||
+ | * 6. přednáška | ||
+ | * quicksort je velmi podobný jako vkládání prvků do BVS | ||
+ | * B-stromy (jak vypadají, insert, delete) | ||
+ | * úvod do třídících algoritmů (časová složitost bubble sortu, merge sortu a quicksortu) | ||
+ | * 7. přednáška | ||
+ | * znovu B-stromy | ||
+ | * halda (k čemu je + operace hledání min, sjednocení dvou hald, insert, delete) | ||
+ | * opět třídění (jak průměrně funguje bubble sort, quick sort, merge sort; důkaz toho, že když máme jakýkoli algoritmus, který třídí na základě porovnávání prvků, tak musí provést alespoň $O(n \log n)$ porovnání --> důsledek: nemůžeme vymyslet třídící algoritmus, kterému stačí méně než $\log_2 n$ operací pro jeden prvek) | ||
+ | * 8. přednáška | ||
+ | * detailně důkaz dolního odhadu třídích algoritmů ([[http:// | ||
+ | * radix sort (popis a ukázka toho, že pokud máme nějakou přiměřenou množinu malých čísel, tak algoritmus tohoto sortu beží v $O(n)$) | ||
+ | * 9. přednáška | ||
+ | * pokračování radix sort (změna oproti minulé přednášce - závěrečný for cyklus pozpátku, abychom měli stabilní uspořádání, | ||
+ | * hashování (základní popis, co říká (bez důkazu) ([[http:// | ||
+ | * implementace hashování (otevřené hashování = hashovací pole minimálně 2x větší než počet prvků, pokud by více prvků hashovací funkce namířila do jednoho políčka v hashovacícm poli, tak ho uložíme do nejblížšího volného políčka napravo, v hashovací tabulce vyhledáváme standardně, | ||
+ | * 10. přednáška | ||
+ | * univerzální hashování (kde počet prvku universa je prvočíslo) | ||
+ | * perfektní hashování (snaha vyhnout se kolizím -- máme k dispozici více hashovacích funkcí a vybíráme si tu, která danou podmnožinu množiny universa zobrazí bez kolizí) | ||
+ | |||
+ | |||
===== Domácí úkoly ===== | ===== Domácí úkoly ===== | ||
Řádek 65: | Řádek 93: | ||
Pro 5 bodů navíc dokažte, že rychleji toto není možné zjistit. Pro plný počet by tento důkaz měl být jasný a úplný. | Pro 5 bodů navíc dokažte, že rychleji toto není možné zjistit. Pro plný počet by tento důkaz měl být jasný a úplný. | ||
+ | |||
+ | **Úloha housenka (9b, plný počet do 2. 5.)** | ||
+ | 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 2. 5.)** | ||
+ | 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 zakázka (10b, plný počet do 11. 5.)** | ||
+ | |||
+ | Olga Opatrná najala Láďu Lenocha, aby ji pro daný neorientovaný graf $G=(V,E)$, vrchol $s\in V$ a // | ||
+ | |||
+ | Olga ale moc nevěří Láďově pečlivosti, | ||
+ | |||
+ | - $d(s)=0$ | ||
+ | - $\pi(s)=\mathrm{NIL}$ | ||
+ | - $\forall (u,v)\in E: d(v) \leq d(u) + w(u, v)$ | ||
+ | - $\forall v\in V: \pi(v)\neq\mathrm{NIL}\Rightarrow d(v) = d(\pi(v)) + w(\pi(v), | ||
+ | - $\forall v\in V, v\neq s: d(v) < \infty \Rightarrow \pi(v) \neq\mathrm{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ě: | ||
+ | |||
+ | |||
+ | **Úloha abeceda (9b, plný počet do 11. 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 polosouvislost (9b, plný počet do 30. 5.)** | ||
+ | |||
+ | Řekněme, že orientovaný graf $G$ je // | ||
+ | |||
+ | **Úloha holubi (9b, plný počet do 30. 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 cheating (7b, plný počet do 30. 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 (8b, plný počet do 30. 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. | ||
+ | |||
+ | |||
+ | |||
teaching/ads11516.txt · Poslední úprava: 2020/04/01 15:50 autor: Martin Koutecky