Dokončení kostry grafu jsem neměl připraveno, udělám až po vyhledávání v textu.
Náměty na cvičení viz například Martinovy texty http://mj.ucw.cz/vyuka/ads/40-kmp.pdf
A ještě s nimi prosím proberte lemma, které je sice ve skutečnosti triviální, ale když ho mnozí studenti mají naformulovat a využít při dokazování správnosti KMP algoritmu a konstrukce failure function, tak ho nedají dohromady (jak o tom včera mluvil Jano Hric), nebo si neuvědomují, že to je základ, na kterém vše stojí:
prefix v_0,...,v_k vzoru V je suffixem t_0,...,t_j přečteného textu právě když zkrácený prefix v_0,...,v_{k-1} je suffixem zkráceného textu t_0,...,t_{n-1} a současně v_k=t_j.
Ve cvičení pokračujte s vyhledáváním v textu, např. podle Martinových příkladů na cvičení.
Následující přednášku ukáži Rabin-Karpův algoritmus pro vyhledávání v textu, zopakuji (dokončím) hledání minimální kostry (z minulého semestru) a pustím se do toků v sítích.
Poznámky k přednášce a prosby k cvičícím.
1. Řada studentů na zkoušce za minulý semestr dokazovala správnost algoritmu pro min kostru pomoci t.zv. řezového lematu. Proti tomu není možno nic mít, pokud není podáno v následujícím tvaru nebo jeho mírnějších obměnách: máme-li množinu vrcholů grafu rozdělenu do dvou disjunktních množin A,B, pak minimální kostra vypadá tak, že vezmeme kostru podgrafu na A, kostru podgrafu na B a spojíme je nejlacinější hranou spojující B. Z toho správnost algoritmu pro min kostru snadno vyplyne, až na to, že to lemma v této formě je pochopitelně špatně, i když třeba podgrafy na A i B jsou souvislé. Proberte prosím na cvičení, jak vypadají (triviální) protipříklady - ta chyba se vyskytla příliš často, takže to stojí za to. Pokud text, který řezového lemmatu využívá, napsal někdo z fakulty, stálo by asi za to, ho upravit tak, aby z něj bylo jasné, že něco jako výše uvedení formulace NENÍ řezové lemma.
2. Prosím na cvičení probrat, že Ford Fulkerson s celočíselnými kapacitami zvýší tok po každé probrané cestě o 1, takže velikost toku je horní odhad počtu probraných cest, když jsou kapacity racionální, tak se dají vynásobit jejich nejmenším společným násobkem a pak viz výše, a ukázat příklad, že s iracionálními kapacitami se může nezastavit a k maximu pouze konvergovat.
3. Pro toky v sítích používám nasledující formalismus: jsou-li u,v dva vrcholy sítě, pak pokud (u,v) je hrana, jsou c(u,v) a t(u,v) rovny kapacitě hrany (u,v) a toku touto hranou, v opačném případě je c(u,v)=t(u,v) = 0. Je-li h=(u,v), pak taky píšu c(h) a t(h). Dále rezerva r(u,v) = (c(u,v)-t(u,v)) + t(v,u). A nakonec síť rezerv pro danou síť a daný tok t je orientovaný graf, mající stejné vrcholy jako ta síť a (u,v) je v něm hranou, právě když r(u,v) > 0. (Síť rezerv je závislá i na tom toku, mění se během výpočtu. Taky může být r(u,v)>0 i když (u,v) není hrana - ale pak musí být hranou (v,u)).
Převedení přebytku velikosti d z vrcholu u do vrcholu v je buď zvýšení toku t(u,v) hranou (u,v) o d, pokud ta hrana tam je a je c(u,v)-t(u,v) >= d, nebo snížení toku hranou (v,u) o d, pokud ta hrana tam je a je t(v,u)>=d, nebo kombinace obojího. V obou případech operace sníží přebytek ve vrcholu u (co do u vtéká minus co z něj vytéká) o d, přebytek v zvýší o d, rezerva r(u,v) klesne a r(v,u) stoupne o d. Proto tu operaci (kteroukoli z možností) nazývám přesunutím přebytku.
Je to na první pohled trochu zapletené, ale vyplati se to pro popis algoritmů, obzvlaště Goldbergova. FF algoritmus je pak prosté hledání orientované cesty ze zdroje do spotřebiče v síti rezerv a přenesení přebytku rovného minimu rezerv hran cesty podél této cesty. A u Goldberga se bez pojmu přebytku těžko obejdeme.
Prosím převádění přebytku trochu procvičit, hlavně aby nezapomněli, že přenesení přebytku z u do v nemusí být JEN zvýšení toku hranou (u,v).
A taky aby věděli, že pokud znám rezervy hran a předpokládám, že pro žádné u,v nejsou t(u,v) i t(v,u) současně nenulové (nedává smysl komoditu vozit tam a hned zase zpátky), pak snadno spočítám i odpovidající tok.
Započat výklad o DFT - na rozdíl od řady kolegů nepopisuji DFT jako nástroj pro rychlé formální násobení polynomů, ale jako metodu pro spektrální rozklad digitalizovaného periodického signálu.
Pro DFT je třeba, aby studenti rozuměli vzorečku exp(ix)=cos x + i sin x, trochu se tomu na cvičeních věnujte, třeba ukázat, jak se jednoduše dostanou vzorce pro cos 2x a sin 2x, o tom jak plyne z mocninných řad pro exponenciálu a cos a sin se zmíním na přednášce, ale dotknout se toho na cvičení by bylo užitečné.
A stálo by za to také na cvičení probrat obrazy některých funkcí pomocí přímé a inverzní DFT nebo spojité FT.
Byl probrán algoritmus FFT, příště bude ještě ukázáno, že přímá a inverzní transformace jsou vlastně totéž a ukázány aplikace (kosinová transformace a komprese dat, násobení polynomů a čísel)
Naměty na cvičení:
Ukázat FFT v konečném tělese, podaří-li se najít vhodná n-tá odmocnina 1 a zmínit, že v tomto případě nedochází k zaokrouhlovacím chybám
Zkusit si vynásobit dva polynomy pomocí DFT
Dále byl započat výklad o bitonickém třídění - ukázána konstrukce obvodu z komparátorů, zbývá dokázat, že separační vrstva komparátoru, dostane-li na vstup bitonickou posloupnost, opravdu dělá, to co má.
Skoro celý byl vyložen popis sčítání dvou binárních čísel způsobem carry look-ahead. Zbývá jen ukázat, jak upravit obvod pro zřetězené (pipelined) počítání a ukázat, jak jednotlivé elementární uzly v obvodu vyrobit ze základních booleavských funkcí (AND, OR, NOT,...).
Příště také přidám násobení algoritmem Karacuba-Ofman a pak budu pokračovat na geometrické algoritmy (konvexní obal a Voroného diagram).
Na Karacubu-Ofmana (zmiňovaného před týdnem) jsem zapomněl, zmíním ho spolu s O(n^log_2 7) algoritmem pro násobení matic později (asi příště).
Ukázal jsem algoritmus pro konvexní obal konečné množiny v rovině, kde hlavním cílem byla zajímavá a často užívaná myšlenka důkazu lineární výpočetní složitosti (jsou-li místa předem srovnána podle x-ové souřadnice). Započal jsem výklad Voroného diagramu a vyložil jsem 3D intuici, která je za Fortune-ovým algoritmem.
Náměty na cvičení:
binární operace * na množině {+,-,<}, definovaná pro carry look-ahead sčítání jako +*x=+, -*x=-, <*x=< je asociativní - dokažte s nimi a ukažte, že je-li # libovolná asociativní operace, pak a1#a2#...#an se dá paralelně počítat v čase log_2 n tak, že se napřed v jednom paralelním kroku spočítají a1#a2,a3#a4,..., v druhém paralelním kroku se součty dvojic posčítají na součty čtveřic, ... atd.
Pro Voronoi diagram proberte, že místa s neomezenými oblastmi jsou místa na obvodu konvexního obalu množiny míst. Dále prosím proberte konkrétní tvary diagramu pro jednoduché množiny míst (trojúhelník, 4 místa do obdélníka atd.)
O Voronoi diagramu je možno na cvičení ještě říci dost detailnějších informací. Například, že při místní události (site event) obecně se počet oblouků pobřežní čáry (beachline) zvýší o 2 (v degenerovaném případě o 1), u kružnicové události (circle event) o 1 klesne. Z toho se dá odhadnout, kolik kružnicových událostí se během výpočtu provede, kolik oblouků kdy může mít pobřežní čára během výpočtu i po jeho ukončení atd.
Výklad o NP-úplnosti začnu konkrétními převody mezi 3SAT, 3-barevností a hledáním nezávislé množiny dané velikosti, viz .ppt prezentace na mé webové stránce v literatuře k odkazu ADS 2. Hodilo by se mi, kdybyste ukázali, jak konkrétně sestrojit booleovskou prahovou funkci n proměnních (=1 právě když alespoň k proměnných je rovno 1). Případně možno už dopředu ukázat nějaké další převody úloh, třeba z hledání množinových pokrytí na batoh nebo 2 loupežníky, to na přednášce dělat nebudu.
Algoritmus Aho-Corasick
Algoritmus Rabin-Karp
Výhodný algoritmus zlepšující cesty - Dinic
Algoritmus využívající "preflow" - Goldberg
(Neprobráno: Maximální párování v bipartitním grafu)
Rychlá Fourierova Transformace (FFT)
Kosinová transformace
Násobení čísel - algoritmus Karatsuba-Ofman
Voroného diagram
Nedeterministické algoritmy, třídy P a NP
NP-úplnost
Aproximační algoritmus pro problém batohu
Aproximační algoritmy pro bin packing
Šifrování s otevřeným klíčem - RSA šifra
Aho, Hopcroft, Ullman : The design and analysis of computer algorithms, Addison-Wesley 1976
T. Cormen, Ch. Leiserson, R. Rivest, C. Stein : Introduction to Algorithms (2nd Edition), McGraw-Hill 2001
L. Kučera : Kombinatorické algorithmy, SNTL Praha 1983
L. Kučera, J. Nešetřil : Algebraické metody diskretní matematiky, SNTL Praha 1989