Příklady ADS2
(ZS 2023/24)
Podmínky zápočtu: každá DÚ je různě, celkem 150 bodů, na zápočet máte mít 2/3 bodů z možného počtu.
Standardně máte 1 týden, tj. odevzdat před dalším cvičením pomocí Moodlu.
Co má obsahovat DÚ: Popis souvislým textem, ze kterého je jasné, že jste úlohu vyřešili správně.
V případě algoritmů typicky a) popis algoritmu a/nebo konstrukce, b) pseudokód algoritmu (u pseudokódu je
menší pravděpodobnost, že ho popíšete neúplně a/nebo s chybou), c) zdůvodnění
správnosti alg. a/nebo konstrukce, d) rozbor složitosti alg.
readme:
Cvičíme příklady ze začátku, přizpůsobujeme se přednáškám (tj rozdělení je předběžné),
příklady nad 30 (za "další") jsou pro vás na rozmyšlení, případně kdyby zbyl na cvičení čas.
"naučit": co se naučit, co si zapamatovat a co si odnést (z příkladu).
Slovníček je na konci.
verze 2.4.8 ;
(verze 1.13.3, +ZP)
Cvičení 1. Alg. Aho-Corasicková
- Úvod (kde jsou materiály, podmínky zápočtu). Tento rok (2020) bylo první cvičení před přednáškou,
tak jsme dělali vybrané techniky z ADS1.
- (z1) Linearizace/serializace haldy jako aplikace DFS. Potřebné datové struktury.
Varianty: jeden průchod při čtení, jeden při zápisu, jeden při obou.
- (z2) Hašování, dynamizace. Zmenšování tabulky, amortizace. Kdy se rehašuje do stejně velké tabulky?
Průběžné rehašování bez "stop the world".
- z3. Odvození rovnosti z daných rovností (z ADS1), Union-find struktura ADS1/4/58
- z4. Nalezení propojení drátů v kabelu. ADS1/9/37 Neadaptivní řešení.
- Značení. Délka textu $n$, celková délka vzorů $l$, počet vzorků $k$, délka nejdelšího vzorku $m$.
- 1. Zkonstruujte AC stroj pro vzorky:
- a) VATRA, TATRA, TRAVA, RA, VAT
- b) OKOLO, KOLO, OKO, LOLOK, OLOVO
- c) SENO, NOS, OBNOS, SOB
- d) atata, gatt, tagg, att
- e) KRAKA, RAK, RARAKR, AKRA
- f) NEJEN, JENE, NEE, EN, JEJE
- g) LUP, LUPU, LUPUS, PULL, UP, USUS
- 2. a) Jak cyklicky pootočit daný text "na místě", tj. s konstantní ($O(1)$) pomocnou pamětí?
b) Jakou mají (tři) řešení konkrétní složitost?
- 3. Když chceme ušetřit průchody zpětnou funkcí, tj. dopředná funkce má
pro každý znak vést na správný stav. Kolik ušetříme času a kolik nás to bude stát
paměti? (Toto je přístup konečných automatů, budou v dalším semestru.)
- 4. a) Ukažte, že naivní algoritmus může v nejhorším případě vykonat až $\Theta(nl)$ porovnání znaků,
b) a to i v případě, že nic nenajde.
- 5. Chceme zjistit, jestli je jeden vzorek cyklickým pootočením druhého.
- (5b.) Přijdete na implementační trik, který umožní (v tomto alg.)
nepočítat indexy modulo délka?
- 6. Dokážete odhadnout největší a nejmenší počet stavů AC-stroje (vzhledem k $l$, $k$ nebo $m$)?
- 7. Postavíme a pro vyhledávání použijeme jen dopřednou funkci, tj. písmenkový strom (TRIE).
Odhadněte složitost vyhledávání (co nejtěsněji).
- 90. DÚ kandidát. Typicky: postavte AC stroj pro vzorky z úlohy 1.něco
- 91.
Další:
- 31. a) Navrhněte algoritmus, který místo konkrétního vzorku hledá
danou podposloupnost (tj. znaky nemusí jít za sebou).
- b) Hledáme nejkratší úsek, který obsahuje danou podposloupnost.
- c) Jednotlivé sousedící znaky mají danou požadovanou minimální a maximální
vzdálenost ve zpracovávaném textu.
- 32. Chcete spočítat počet výskytů dané podposloupnosti v textu. ($o(n.l)$)
- 33. Hledáme slova s jednou chybou. Jak implementovat a) výměnu znaku, b) vložení znaku (tj. v textu je vložen
znak, který ve vzorku není), c) vypuštění znaku, (d) prohození dvou sousedních znaků.
- 34. (i DU) (PLA) Máte daný text zašifrovaný neznámou permutační šifrou a nezašifrované vzorky. Upravte alg. AC tak, aby našel
všechny možné výskyty vzorků v textu, tj. vydal vzorek, pokud pro danou pozici existuje nějaká možnost zašifrování.
Permutační šifra je daná permutací, která každému písmenu vstupního plaintextu přiřazuje písmeno šifrovaného
ciphertextu. Vstupní písmeno se šifruje všude stejně a různým vstupním písmenům odpovídají různá zašifrovaná
písmena. Permutační šifra může zobrazit písmeno na sebe.
Př. Slova MAKAK a KOKOS se můžou překrývat max. 4 písmeny v jednom směru a max. 3 v druhém.
- (35.) Dovolíte hledat vzorky s 1 chybou. Jak navrhnete automat? Jaké hrany budou odpovídat jednotlivým druhům
chyb, tj. DEL, INS, EXCH, resp. SWAP, značící vypuštění písmena ze vzorku, přidání písmena, nahrazení písmena,
resp. prohození dvou sousedících písmen? (+ Nedeterminismus)
Cvičení 2. Alg. Knuth-Morris-Pratt, Rabin-Karp
- 0. Opakování: a) Hornerovo schéma pro výpočet hodnoty polynomu v bodě, pro R-K.
- 1. KMP: a) pro vzorek ANANASY,
b) ABRABABABRA, c) ababaabbabaaa.
- 2. R-K: a) Jak navrhnete optimalizovanou variantu algoritmu R-K pro víc
hledaných vzorků stejné délky.
- b) To samé, víc vzorků různé délky.
- c) Je vhodné počítat jedno okno odpovídající délce nejkratšího vzorku?
- d) Když budete počítat haše oken různé délky, daly by se využít na zmenšení pravděpodobnosti falešného hitu?
Za jakou asymptotickou cenu? (Příprava na další příklad.)
- 3. R-K: a) Chcete zmenšit pravděpodobnost falešného hitu a přitom pracovat
s klasickou (ne dlouhou) aritmetikou. Co můžete udělat?
b) Jedna z myšlenek je rozdělit vzorek na dvě části, např. poloviny nebo sudé a liché znaky. Rozeberte výhody a (hlavně) nevýhody.
z) Např. Case study: víte, že vzorek je periodický a obáváte se, že falešných
výskytů může být mnoho.
- 90. DÚ kandidát/nevhodný: Máte daný vzorek. Najděte jeho lexikograficky minimální cyklické pootočení.
Nápověda: lineárně.
- 91. Kandidát: 1/34 permutační šifra
Další:
- 31. Chcete zjistit, jestli je ve slovníku cyklické pootočení daného vzorku (tj. slova).
- 32. Chcete zjistit, jestli je ve slovníku permutace daného vzorku (tj. slova).
- 33. Porovnáváte dokumenty pomocí histogramu trojic sousedních slov po zahašování. Chcete
(aspoň zčásti) odmaskovat prohození slov. Co doporučíte?
- 34. (PLA 10...) Najděte ve slově nejdelší příponu, která je zároveň předponou.
- b) Najděte ve slově všechny přípony, které jsou zároveň předpony.
- 35.a) Najděte ve slově nejdelší počáteční usek, který je palindrom.
Palindrom je slovo, které je stejné při čtení zleva i zprava.
- b) Najděte nejdelší (souvislé) podslovo, které je palindrom.
- 36. (PLA) Najděte nejdelší Fibonacciho slovo.
- 37. a) Vzorek $v$ považujeme za variantu slova $s$, pokud se shodují první a poslední písmeno a
vnitřní písmena jsou navzájem permutací. Chcete zjistit, zda je v slovníku varianta slova $v$.
-- b) Jak navrhnout rozumnou hašovací funkci tak, aby se podobné řetězce $v$ a $s$ hašovali stejně? (A nepodobné
řetězce náhodně.)
-- c1) Analogicky k b), chcete odmaskovat pomocí hašovací funkce pootočení vzorku podle př. 2/31 anebo
c2) permutaci vzorku podle 2/32 ; TODO: přidat/přemístit k hašování
- 38. (BioINF, spíš chemoinf.) TODO: přidat k hašování
-- a) Pracujete se "zobecněnými" sumárními chemickými vzorci, např. C10H16. Nekompatibilní program ale vydává
vzorce s jiným zápisem
s neznámým (až náhodným) pořadím složek, např. H16C10. (Chem. značky a počty jsou správně.)
Zjistěte, zda ve slovníku je stejný sumární vzorec, který se může lišit zápisem.
-- b) Analogicky k 2/37.b) navrhnout hašovací funkci, která různé zápisy hašuje stejně.
-- c) Varianta: sumární vzorce jsou v "unární" reprezentaci (CCHHHH místo C2H4). Hašovací funkce pracuje
inkrementálně a umožní přidávat a ubírat značky prvků.
- 39. Navrhněte variantu alg. Rabin-Karp, která bude založena na xor, místo plus a modulo.
(Motivace Zobristovým a tabelačním hašováním.)
- Písmena na různých místech vzorku chceme hašovat různě, aby výsledek haše byl citlivý na permutace.
Jak implementujeme přepočet okna při posunu? Jaká operace bude odpovídat odstranění písmena z okna? A jak využijete modulo?
Cvičení 3. Toky v sítích, zlepšující cesta
- 1. Ukažte, jak zobecnit algoritmus na případ, kdy máte víc zdrojů a víc stoků.
- 2. Jak naleznete max. tok v síti, pokud i vrcholy mají kapacitní omezení?
- Pozn. Pro pozměněný alg. můžete použít 2 přístupy. 1) Upravíte alg. tak, aby
počítal novou úlohu. 2) Upravíte nová vstupní data tak, aby jste měli platné zadání
pro původní algoritmus a z jeho výstupu jste byli schopni rekonstruovat výsledek nové úlohy.
Přístup 2) je obvykle méně pracný (pokud ho použít lze), protože nemusíte programovat,
ladit a dokonce ani mít zdrojové kódy pro úpravy. ("Převoditelnost": bude dále v přednášce)
- 3. Navrhněte algoritmus, který najde maximální počet hranově disjunktních cest
mezi dvěma vrcholy $u$ a $v$?
- 4. Upravte algorimus z minulého cvičení, aby hledal vrcholově disjunktní
cesty (až na krajní vrcholy).
- 5. a) Jaká je složitost F-F. alg. na grafu s jednotkovými kapacitami?
-- (... i pro jiné alg.)
-- b) Jaké hodnoty můžou mít kapacity v reziduálním grafu?
-- c) O jaké hodnoty lze zlepšovat tok po zlepšující cestě?
- 6. a) Zdůvodněte, že na grafu s celočíselnými kapacitami existuje celočíselný maximální tok.
-- b) Ukažte, že na grafu s celočíselnými kapacitami může existovat i neceločíselný maximální tok.
(Tj. na hranách max. toku nejsou celá čísla)
- 7. Pomocí toku v sítích řešte úlohu maximálního párování v bipartitním grafu. (Předn.)
Čemu odpovídá zlepšující cesta, převedena do pojmů párování?
- Pozn. Z neceločíselného toku z příkladu 6b) bychom špatně rekonstruovali párování.
Ale 6a) umožní rekonstrukci vždy.
- 8. Hrany grafu jsou kromě kapacity ohodnoceny cenou za jednotku toku.
Najděte maximální tok minimální ceny.
- 9. Pokud budeme vybírat vždy nejkratší zlepšující cestu, obejdeme se bez snižování toku
na hranách, tj. použití protisměrných hran ?
- 10. a) Lze každý tok rozložit na nějaké zlepšující cesty?
-- b) Lze každý tok rozložit na zlepšující cesty, které jdou po směru hran?
-- c) Odhadněte počet $k$ zlepšujících cest, na které se podaří rozložit každý maximální tok.
-- d) Dokážete popsat algoritmus pro rozklad toku na sousměrné zlepšující cesty?
-- (e) Existuje nějaká posloupnost zlepšujících cest po směru hran, která vytvoří
maximální tok? e2) Platí to i pro nějakou posloupnost nejkratších zlepšujících cest?
- 11. Najděte graf o $n$ vrcholech, který má minimální řez o $O(n^2)$ hranách.
- 12. Najděte graf o $n$ vrcholech, který má nepolynomiální počet zlepšujících cest.
- 90. "Inkrementální update." Máte síť s celočíselnými kapacitami a známým tokem.
Jedna hrana změní svojí kapacitu o $\pm 1$. Dokážete (rychle) upravit tok, aby
byl opět maximální?
- 91. Navrhněte algoritmus, který určí hranovou $k$-souvislost grafu $G$.
(Zajímá nás maximální $k$.) Odhadněte složitost alg.
-Def: Graf $G$ je hranově, resp. vrcholově, $k$-souvislý, pokud po odebrání
libovolných $k-1$ hran, resp. vrcholů, zůstane souvislý.
- 92. DÚ kandidát. Navrhněte algoritmus, který určí vrcholovou $k$-souvislost grafu $G$.
(Zajímá nás maximální $k$.) Odhadněte složitost alg.
- 93. Minulé dvě úlohy, ale efektivněji. ${\tt {:-)}}$
- (94.) Přeformulujte 3:91-Def do pojmů řezů.
- 95. DÚ kandidát. 3/39
Další:
- 31. a) Je minimální řez v grafu určen jednoznačně?
-- b) Umíte charakterizovat minimální řez, který vydá konstrukce z Věty o max. toku a min. řezu?
(Konstrukce: V levé množině řezu jsou vrcholy, do kterých vede zlepšující cesta.)
-- c) Jak najít jiný minimální řez, pokud existuje?
-- d) Zkonstruujte graf, který bude mít aspoň 10 minimálních řezů.
- 32. Ukažte, že pokud algoritmus pro max. tok nekončí, tak ani nemusí konvergovat
ke správnému max. toku.
- 33. Zkonstruujte síť na nejvýš 10 vrcholech a 10 hranách, pro kterou Fordův-Fulkersonův alg.
provede aspoň milion iterací.
- 33.1* Najděte* síť, pro kterou Fordův-Fulkersonův alg. neskončí.
- 34. Popište možné strategie pro výběr zlepšující cesty pro alg. Ford-Fulkerson.
Jaká je složitost nalezení cesty?
- 35. Kolik lze postavit na šachovnici s vynechanými políčky věží tak, aby se
neohrožovaly? Věže se ohrožují, pokud jsou ve stejném řádku nebo sloupci.
- 35.1 Chci upřednostnit některé políčko (nebo víc). Jak zjistit, zda existuje postavení
max. věží, které obsahuje dané políčko (nebo políčka)?
- 36. Totéž, ale přes díru se věže neohrožují
- 37. Rozhodněte, zda lze pokrýt šachovnici s dírami kostičkami 2x1. Najděte
konkrétní pokrytí. Čemu odpovídá zlepšující cesta?
- 38. a) Máte dodavatele a odběratele se známou kapacitou a vztahy určujícími, který
dodavatel schopen dodávat kterému odběrateli a kolik. Je možné pokrýt požadavky všech odběratelů?
b) Kromě kapacit jsou dánu i ceny za přepravenou jednotku. Jak najít nejlacinější pokrytí požadavků?
- 39. (i DÚ) Máte nástroje, které něco stojí, a projekty, které po realizaci něco vynesou.
Každý projekt potřebuje určité nástroje, bez nich nemůže být realizovaný. Jeden nástroj
může sloužit víc projektům a kupuje se pouze jednou. Rozhodněte, které nástroje koupíte a které
projekty realizujete, aby zisk (a druhotně obrat) byl co největší. (I jiná formulace.)
- 40. a) Je pravda, že pokud přes minimální řez vede $k$ hran, tak maximální tok
najdete pomocí $k$ zlepšujících cest?
- b) Tatáž otázka pro graf s jednotkovými kapacitami.
- 41. a) Je pravda, že pokud ze zdroje vede $k$ hran, tak maximální tok
najdete pomocí nejvýše $k$ zlepšujících cest?
- b) Tatáž otázka pro graf s jednotkovými kapacitami.
- 42. Přímočará implementace F-F hledá zlepšující cestu prohledáváním do šířky.
Ukažte, že pak stačí najít $O(nm)$ zlepšujících cest pro nalezení max. toku.
- 43. (z Diskrétní matematiky) Najděte šířku částečného uspořádání $U$, tj. max. počet
vzájemně neporovnatelných prvků, tj. velikost maximálního antiřetězce.
Návod: Je rovna min. počtu (lineárně uspořádaných) řetězců, na které jde $U$
rozložit (Dilworthova věta). Následně převést na max. párování v bipartitním grafu (a min.
vrcholové pokrytí, Königova věta o párování bipartitních grafů).
- (44.) Párování nejen v bipartitním grafu. Hledáme zlepšující/střídavou cestu, která
začíná a končí v neobsazeném vrcholu.
Cykly liché délky zkondenzujeme do 1 vrcholu.
Cvičení 4. Dinicův alg.
- 1. Implementace Dinicova alg. Výroba vrstevnaté sítě.
(Pročistěná síť, kaskádové odebírání hran a vrcholů)
- 2. a) Jak se chová Dinic na síti s jednotkovými kapacitami? Dokážete složitost
odhadnout lépe než v obecném případě?
-- (b) Zdůvodněte stejný odhad i pro celočíselné kapacity omezené konstantou.
- 3. Najděte příklad grafu, na kterém Dinicův alg.
- a) vykoná $O(n)$ fází,
- b) v jedné fázi stráví $O(nm)$ času,
- c) celkově potrvá $O(n^2 m)$.
- 4. a) Jaká výhoda plyne z toho, že vrstvenou síť udržujeme pročištěnou?
-- b) Ve kterém okamihu vykonávání algoritmu je potřeba mít síť pročištěnou?
-- c) Jaký je invariant pročištěné sítě?
- 5. (Implementační) a) Popište prohledávání vrstevnaté sítě do hloubky. Přitom chceme nalézt
blokující tok a zbytečně se nevracet při propagaci jedné zlepšující cesty.
- 90. DÚ: Napsat jako výukový text. (Alg. tří Indů) a) Rychlejší způsob hledání blokujícího toku
ve vrstevnaté síti
spočívá v tom, že najdeme vrchol $v$ s minimální rezervou a pak hledáme tok, který naplní
rezervu vrcholu $v$. A opakujeme. Rezerva vrcholu $u$ je minimum ze součtu rezerv vstupních
hran do $u$ a ze součtu rezerv výstupních hran z $u$.
- b) Odhadněte složitost jedné fáze a následně celého algoritmu. Jeden vrchol máte zpracovat
v čase $O(n)$ a celou fázi v $O(n^2)$.
Další:
- 31. OPAK? a) Jak se chovají jednotlivé algoritmy na síti s jednotkovými hranami?
- b) Jaká zlepšení po zlepšující cestě, resp. přenosy v Goldbergově alg. můžeme realizovat?
- c) Jak se chovají alg. na síti s celočíselnými kapacitami omezemýni shora konstantou $k$?
Cvičení 5. Goldbergův alg.
- 1.a) Jak se bude chovat G. algoritmus, pokud při inicializaci umístíme zdroj
do výšky $n-1$, $n-2$ nebo $n-3$?
-- (b) (Pokud nejde G.a. použít přímo, jde ho "opravit"/"opatchovat"?)
- 2. Jak se bude chovat G. algoritmus na síti s jednotkovými kapacitami?
- 3. Implementace GA.
- 4. Strategie výběru nejvyššího vrcholu.
a) Jako heuristika.
(b) Odhad počtu nenasycených převedení. ($O(n^3)$, pomocí $O(n^2)$ fází s pevnou nejvyšší hladinou)
- Pozn. Jakou má výhodu znát a používat tuto strategii jako heuristiku?
- 5. Heuristika mezery: Zdůvodněte, že pokud existuje hladina, na které není
žádný vrchol, tak vrcholy nad ní můžeme zvednout o 1 nad zdroj.
- 90. DÚ kandidát.
- 91. Pro nekonečně mnoho $n$ najděte síť $G$ velikosti $n$ a pro ni strategii výběru vrcholů, která při zafixování
zdroje ve výšce $n-3$ nenajde maximální tok v grafu.
Další:
- 31. Správci a projekty. (Reformulace) Programátoři pracují na několika projektech,
jeden na více. Každý projekt má mít jednoho správce ze zúčastněných programátorů, přičemž
správce spravuje výhradně jeden projekt.
Najděte přiřazení správců projektům. Případně zjistěte, že přiřazení neexistuje
a v tom případě maximalizujte počet projektů se správci.
-- b) Zobecnění. Jednotlivý projekt $p$ má určený počet správců $s_p$, jednotlivý
programátor $r$ smí být správcem $t_r$ projektů.
-- b2) Umíte zobecnit na situaci, když jednotlivé projekty jsou různě náročné
na správu? Např. v hod./týden?
-- (c) Víte (z jiných předmětů, např. diskrétní matematiky nebo kombinatoriky), za jakých podmínek
je existence řešení zaručena, pro a), resp. b)?
-- (d) Ve VPL je v cvičeních Petra Gregora i nekonečná (spočetná) verze.
- 32. Svišti a díry. a) Na louce jsou svišti a jejich díry. Když se objeví orel,
tak svišť uběhne nejvíce $u$ metrů, než ho uloví orel. Při dobrém plánování, kolik
nejvíc svišťů se stihne schovat, když jedna díra pojme jednoho sviště?
-- b) Kolik svišťů se stihne schovat, pokud jedna díra pojme $d$ svišťů?
- 33. Robůtci. (Reformulace/Varianta) a) Máte dané bludiště jako graf $G$
(například čtverečkové bludiště). Je dána množina počátečních pozic a mno6ina koncových pozic všech
robotů (případně nadmnožina pozic). Roboti jsou záměnní, tj. robot může skončit na libovolném koncovém poli.
V jednom taktu se robot může přesunout na sousední vrchol $x$,
pokud je $x$ volný nebo se v tomto taktu uvolnil. V jednom vrcholu může být současně
nejvýš jeden robot a po hraně se smí posouvat nejvýš jeden robot (tj. roboti si
nemohou vyměnit místa). Zjistěte, zda se roboti dokáží přemístit na určená místa
a jaký
nejmenší počet taktů potřebují.
-- b) Tytéž otázky pro variantu, kdy robot se smí přesunout pouze na volný vrchol.
-- ca), cb) Zjednodušení: Stejné otázky, ale graf je orientovaný a acyklický.
-- (d) Zkuste si rozmyslet okrajové případy: 1 robot, 2 roboti, 1 takt.
"Graphlet": Malý graf, který zakáže robotům vyměnit si místa.
- Pozn. Potřebujeme záměnné roboty, abychom úlohu mohli převést na tok s jednou komoditou.
Pokud by roboti nebyly záměnní, pak bychom museli řešit multikomoditní tok, čož je NP-úplná úloha.
(O NP-úplných úlohách se dozvíte na ADS2 tento semestr.)
- Pozn2. Tato úloha se dá převést i do jiných formalizmů, pro které máme řešice. Kromě toků v sítích
taky do SAT, Lineárního programování, MIP (Mixed integer programming), ...
A hodily by se inkrementální řešiče, které dokážou rozšířit zadání a využít již známé částečné řešení.
- (34.} Sokoban. Robůtci tlačí krabice ve čtvercovém bludišti. Obvykle jen jeden robot a mnoho krabic. (Jde to?)
Cvičení 6. Fast Fourier Transform
- 0. Opakování (i z lineární algebry): Je Fourierova transformace lineární?
Jak se spočítá velikost reálného vektoru? Jak se spočítá velikost komplexního vektoru?
(Jak se spočítá jeden koeficient výsledku vůči jednomu bázovému vektoru?)
- 0.1. a) Napište Vandermondovu matici velikosti $4$ pro FT pro $\omega_4 = i$.
Jak vypadá odpovídající matice pro IFT?
-- b) První 4 řádky z V. matice velikosti $8$, přičemž $\omega_8^2$ všude zjednodušte.
- 0.2. Fourierova transformace, když velikost $n$ není mocnina dvojky. Jde spočítat FT?
Jde spočítat FFT? (Cooley–Tukey FFT algorithm)
- 1. Spočítejte DFT pro vektory
-- a.0) $(0,0,0,0,0,0,0,0)$
-- a.1) $(1,1,1,1,1,1,1,1)$
-- a) $(c,c,c,c,c,c,c,c)$
-- b) $(1,-1,1,-1,1,-1,1,-1)$ (dva způsoby)
-- c) $(0,1,0,1,0,1,0,1)$
-- d) $(\omega^0,\omega^1,...\omega^{n-1})$
-- e) $(\omega^0,\omega^{-1},...\omega^{-(n-1)})$
-- f) $(\omega^0,\omega^2,...\omega^{2n-2})$
-- i) úlohy a)-c) pro vektory stejné struktury s libovolnou délkou $n$
- 2. a) (Na základě minulého cvičení:) Na co se transformuje jednotkový vektor $e_i$ s jedničkou pouze na $i$-tém místě?
-- b) Jaký vektor se transformuje na $e_i$? (dva způsoby)
-- (c) Poskládejte s pomocí minulé odrážky inverzní FT.
- 3. O jakých vlastnostech vektoru vypovídá nultý a $(n/2)$-tý koeficient jeho Fourierova obrazu?
- 4. Násobení dlouhých čísel. Vynásobte pomocí FFT a) 35 a 28, b) 14 a 123.
- 90. DÚ kandidát.
- 91. Programátorský. Najděte vhodné $p$, $n$ a $w$ pro vhodná tělesa $Z_p$.
Pro prvočíslo $p =c*2^l+1$, najdete generátor $g$ cyklické multiplikativní grupy $Z_p$.
Pro generátor $g$ je $p-1$ nejmenší mocnina, pro kterou platí $g^{p-1}\equiv 1 \mod p$,
tj. $g$ je primitivní $(p-1)$-ní odmocnina jedničky. Následně pro $n=2^l$ je $w=(g^c \mod p)$
je $2^l$-tou odmocninou jedničky. Najděte nějaké vhodné trojice pro $n$ v rozsahu 25 až 70 bitů.
- Pozn. Místo tělesa stačí komutativní okruh, kde existuje vhodná odmocnina
jedničky $w$ (a její inverzní prvek $w^{-1}=w^{n-1}$) a inverzní prvek k $n$.
-
Další:
- 31. Dělení polynomů. Definovat. TODO
- 32. (I varianty.) Pro otevření sejfu je potřeba shodu aspoň $k$ z $n$ manažerů.
Navrhněte způsob odvození klíčů pro manažery tak, aby se z libovolných $k$ klíčů dal
odvodit kód sejfu, ale z méně klíčů jste ho odvodit nedokázali
(vyjma délky, resp. možného rozsahu klíče).
-- (b) Totéž, víceúrovňově.
-- c) Totéž, pro nekonečný (spočetný) počet manažerů. Vhodnější v jiné formulaci: Chráněnou správu můžeme rozšifrovat, pokud
získáme aspoň $k$ částečných informací z nekonečného seznamu částí.
- 33. Fourierova báze. Složky vektoru vůči ortonormální bázi.
- 34. DÚ kandidát:
Volba $\omega$. Ukažte, že volba jiné primitivní odmocniny jedničky
jako základ FT se projeví pouze přeházením složek Fourierova obrazu.
- 35. a) DFT reálného vektoru $\bf x$. Zdůvodněte, že Fourierův obraz $\bf x$
je antisymetrický vektor $\bf y$, tj. $y_j = \overline{y_{n-j}}$.
Následně nultý a $(n/2)$-tý koeficient jsou reálné. A $\bf y$ je určen $n$ reálnými čísly.
- b) DU kandidát: Jakou vlastnost má Fourierův obraz antisymetrického vektoru?
- c) Diskrétní kosinová transformace DCT: z DFT v $C^n$ k DCT v $R^{(n/2)+1}$.
- Pozn. Je víc způsobů doplnění vektoru a následně počítání DCT.
- Pozn. $\cos 2x = \cos^2 x-\sin^2 x = 2 \cos^2 x-1$
- 36. Jiné transformace. 2D na 2x2 s ortogonální, příp. ortonormální maticí.
- b) V 1D. Fourierova transformace je "globální" v tom smyslu, že ve Vandermontově matici nejsou nuly
a složky obrazu závisí na celém vzoru. Jiná transformace může být lineární a invertibilní, ale někde výsledek
závisí pouze na části vzoru.
- 37. a) Dokažte, že každá primitivní odmocnina $\alpha$ z jedničky je ve tvaru $\alpha=x^t$,
kde $x=e^{2\pi i/n}$ a $t$ je přirozené číslo nesoudělné s $n$.
-- b) Kolik je primitivních $n$-tých odmocnin z $1$?
- 38. Převod grafu polynomu na polynom. Hledáme polynom stupně nejvýš $n$, který
prochází body $(x_0,y_0)$, $(x_1,y_1)$, ..., $(x_n,y_n)$ pro $x_i$ navzájem různá.
- Značení: $P(x)=\sum_{k=0}^n a_k x^k $, $P(x_i)=y_i$ pro $i=0,...,n$.
- Použít
Lagrangeovu interpolaci. Zavedeme polynomy
$$A_j(x)=\prod_{k\neq j}(x-x_k),\qquad
B_j(x)={A_j(x) \over \prod_{k\neq j}(x_j-x_k)},\qquad
P(x)=\sum_j y_j B_j(x) $$
Dokažte, že deg $P \le n$ a $P(x_j)=y_j$ pro všechna $j$.
Odvoďte pomocí hodnot $A_j(x_k)$ a $B_j(x_k)$.
- (b) Jak co nejrychleji spočítat koef. polynomu?
- 39. Tatáž úloha, řešená pomocí soustavy lineárních rovnic
$\sum_{k=0}^{n}a_i x_i^k=y_i$ pro $i=0,...,n$,
v proměnných $a_i$. Můžeme zapsat jako $\bf Va=y$ pro vektor proměnných $\bf a$,
vektor pravých stran $\bf y$ a
Vandermondovu matici $\bf V$ obsahující ${\bf V}_{ik}=x_i^k$.
- Ukažte, že pro navzájem různá $x_i$ je matice $\bf V$ regulární a soustava má právě jedno řešení.
- Jak se projeví, že polynom má menší stupeň než $n$?
- 40. FFT v celočíselných okruzích $Z_p$. Protože $2^4=16\equiv -1 \mod 17$, je 2 osmá primitivní odmocnina z $1$ v $Z_{17}$.
(A $g=3$ a $g=6$ jsou $\omega_{16}$.)
-- a) Jaký je (multiplikativní) inverzní prvek k $2$ v $Z_{17}$?
-- b) Jak vypadá Vandermondova matice, případně aspoň první dva řádky?
-- c) Vynásobte $11_2 \cdot 14_2$ pomocí FFT v $Z_{17}$. Návod: Vstupní čísla jsou 4-bitová, následně výsledek je až
8-bitový. Použijeme FFT délky 8.
- 42. Chceme omezit zaokrouhlovací chyby při počítání s $\omega_8={(1+i)\over\sqrt 2}$. Co navrhnete?
(Technika je použitelná i jinde. Např. pro přesné (rychlé) počítání Fibonacciho čísel, s $\sqrt{5}$)
- 43.a) Formulujte FFT jako úlohu dynamického programování.
- 43.b) Formulujte FFT pomocí metody rozděl a panuj.
- 44. Nakreslete butterfly obvod pro počítání FT velikosti 8 a 16.
- 45.
Dvourozměrná DFT. Při zpracování obrazu se hodí dvojrozměrná DFT, která matici ${\bf X} \in {\mathbb{ C}}^{n\times n}$
přiřadí matici ${\bf Y} \in {\mathbb{ C}}^{n\times n}$ takto (kde $\omega$ je primitivní $n$-tá odmocnina z 1):
$${\bf Y}_{jk} = \sum_{u,v} {\bf X}_{uv}\omega^{ju+kv}.$$
Dokažte, že tato tranformace je bilineární bijekce, a odvoďte algoritmus na její efektivní výpočet pomocí jednorozměrné FFT.
Fyzikální interpretace je podobná: Fourierův obraz popisuje rozklad matice na "prostorové frekvence".
- Pozn. Jednorozměrná DFT se používá pro zpracování např. zvuku. Pro zpracování obrázků potřebujete dvourozměrnou DFT.
U formátu .JPEG se obrázek rozdělí na čtverce $8\times 8$, ty se jednotlivě zakódují dvourozměrnou kosinovou transformací
a vysoké frekvence (s nízkými hodnotami) se při kompresi zahodí.
- Pozn. Některá poškození obrázků (pohyb kamery, rozostření) se dají popsat jako konvoluce. Při zpracování
a restauraci obrázku (opačný proces dekonvoluce) se používá i Fourierova transformace.
- 46.
Cyklické posunutí. Vektor $\bf y$ je cyklické posunutí vstupního vektoru $\bf x$ o $k$ pozic,
tj. $y_i = x_{(i+k)\bmod n}$.
Jak se změní Fourierův obraz, tj. v jakém vztahu jsou ${\cal F}({\bf x})$ a ${\cal F}({\bf y}) $? TODO: možná se opakuje.
Cvičení 7. Hradlové sítě, třídicí síť
- 0. a) Neuniformní algoritmy - alg. závisí na počtu vstupů. (generování popisu, DSL)
- b) Popis komparátorové sítě.
- c) Čemu odpovídají velikost a hloubka sítě z hlediska složitosti algoritmů?
(Představte si, že "rozvinete" algoritmus na jednotlivé operace a jejich závislosti.
Používá se to např. u dynamického programování.)
- (d) Pozn., navazující. Je vztah mezi časovou a paměťovou složitostí algoritmu? Jedním *a* druhým směrem?
... Časová složitost je počet mezivýsledků (při jednotkových operacích, tj. určité abstrakci).
- 1. Máte třídicí síť.
- a) Můžete hradlo odebrat bez změny funkce?
- b) Můžete hradlo přidat bez změny funkce?
- 2. a) Chcete zkonstruovat třídicí síť pro $n$ vstupů, kde $n$ není mocnina dvojky.
Co navrhnete?
-- b) Dokážete některé "dráty" vypustit ze sítě, tj. síť zmenšit?
-- (c) Lze vypustit drát začínající na libovolném místě?
- 3. a) Zkonstruujte třídicí sítě odpovídající dalším třídicím algoritmům, pokud je dokážete navrhnout.
Např. insertsort - zatřiďování, selectsort - výběrem (maxima), bublinkové třídění jednostranné a oboustranné
(bez optimalizace).
-- b) Různé konkrétní implementace vedou na různé hloubky sítě. Jednotlivé "abstraktní" algoritmy lze
implementovat různým konkrétním způsobem (nakonec v .
(Které alg. dokážete přepsat? Co mají společného?)
- 4. Navrhněte třídicí síť pro vkládání prvku do uspořádané posloupnosti.
- 5. Navrhněte komparátorovou síť pro určení maxima. Na konci výpočtu bude vpravo
největší hodnota.
- 6. Dokažte
nula-jedničkový princip: pokud třídicí síť třídí správně všechny posloupnosti
nul a jedniček, pak třídí správně libovolné vstupy.
- 7.
- 90. DÚ kandidát. Ukažte, že na určení maxima z $n$ čísel potřebujete
aspoň $\log(n)$ hladin komparátorů a $O(n)$ hradel.
- 91. DÚ kandidát. (Varianta minulého příkladu.) Máte hradlo pro určení
maxima z $k$ vstupů. Ukažte, že na určení maxima z $n$ čísel potřebujete
$O(\log(n))$ hladin komparátorů a $O(n)$ hradel.
- Pozn. Oba předcházející příklady jsou dolní odhady.
- 92. DÚ kandidát. Pomocí př. 4 navrhněte třídicí síť. Jakou má velikost a hloubku?
(Jakému alg. odpovídá postup?)
- 93. DÚ kandidát.
Další:
- 31. Bitonické třídění. (Není na všech, resp. obou, přednáškách.)
Bitonické třídění je založeno na následujícím alg. utřídění bitonické posloupnosti. Bitonická posloupnost je cyklické pootočení posloupnosti, která má jeden stoupající úsek následovaný jedním klesajícím.
Procedura BitonSep
Vstup: Bitonická posloupnost $(z_0,z_1,...,z_{2n-1})$.
Pro volání z třídicí procedury vytvoříme bitonickou posloupnost $(x_0,x_1,...,x_{n-1},y_{n-1},...,y_1,y_0)$ ze dvou (vzestupně) utříděných posl. $(x_0,x_1,...,x_{n-1})$ a $(y_0,y_1,...,y_{n-1})$.
1. Pro $n\le 1$ uspořádáme triviálně.
2. $(u_0,u_1,...,u_{n-1}) \leftarrow$ BitonSep$(min(z_0,z_{n}), min(z_1,z_{n+1}),...,min(z_{n-1},z_{2n-1}))$
3. $(v_0,v_1,...,v_{n-1}) \leftarrow$ BitonSep$(max(z_0,z_{n}), max(z_1,z_{n+1}),...,max(z_{n-1},z_{2n-1}))$
Výstup: spojení posloupností $\bf u$ a $\bf v$, tj. $(u_0,u_1,...,u_{n-1},v_0,v_1,...,v_{n-1})$.
- a) Zkonstruujte třídicí síť.
- b) Pomocí
0-1 principu dokažte, že třídí správně.
- Nápověda: Jak vypadají bitonické posloupnosti z nul a jedniček?
- c) Rekurzivní vzorce pro velikost a hloubku.
- 32. Mergesort. (
Batcherovo třídění)
- a) Návrh sítě. Rekurzivní použití třídicí sítě následované slévačkou. Rekurzivní slévačka
dělená na sudé-liché vstupy s dotříděním v poslední vrstvě $s_i$ s $l_{i+1}$, $i=0,...,n-1$,
indexováno od (sudé) 0.
- b) Rekurzivní vzorce pro velikost a hloubku.
- c) Dokažte explicitní vzorce pomocí indukce s využitím b). Slučovací síť $M_n$ je šířky $2n$,
třídicí síť $S_n$ šířky $n$.
$$d(M_n) = \log_2 n + 1$$
$$s(M_n) = n \log_2 n + 1$$
$$d(S_n) = {1/2}\log_2 n (\log_2 n + 1)$$
$$s(S_n) = {n/4}\cdot\log_2 n (\log_2 n - 1) + (n-1)$$
- d) Pomocí
0-1 principu dokažte, že třídí správně.
- 33. Navrhněte způsob, jak komparátorovou síť obsahující komparátory v obou směrech převést na tvar, kde všechny
komparátory vydávají maximum vpravo.
- 34. Medián. Navrhněte komparátorovou síť pro hledání mediánu: dostane-li $n$ prvků, vydá takovou permutaci,
v níž bude poslední hodnota medián všech prvků.
Cvičení 8. Aritmetické sítě, sčítačka
- 1. a) Navrhněte síť pro porovnání dvou bitových čísel. Vydává 1, pokud je
první číslo větší.
- b) Varianta. Stejný vstup, chceme na výstupu rozlišit 3 případy: první
vstup větší, druhý vstup větší, stejné vstupy. Rozeberte možnosti, jak reprezentovat výstup.
- 2. a) Navrhněte síť pro naivní násobení dvou $n$-bitových čísel $\bf x$ a $\bf y$.
Odhadněte hloubku a velikost.
-- b) Vylepšete síť pomocí sčítačky. Odhadněte hloubku a velikost. (Víc možností.)
-- c) Další možnost viz př. 8/91 (DÚ).
-- d) Ukažte, že sítě založené na pronásobení bitů vstupních čísel $x_i$ a $y_j$ a následném sčítání,
mají velikost $O(n^2)$.
-- e) Násobení pomocí Fourierovy transformace. Odhadněte hloubku a velikost.
(Víc detailů: pracujeme v celočíselných okruzích (kvůli zaokrouhlování) s čísly velikosti $O(\log n)$
v čase $O(\log(\log n))$ $\verb/;-)/$)
- 3. Navrhněte síť pro odečítání dvou bitových čísel. (Víc možností.) Odhadněte hloubku a velikost.
- 4. Chcete sčítat čísla, která nemají délku mocninu dvojky. Jde využít sčítačka založená
na metodě Rozděl a panuj?
- 90. DÚ kandidát.
- 91. DÚ kandidát. a) Násobení. Sčítáme 3 čísla na dvě (carry/přenos a paritu), v konstantní hloubce.
Poslední dvě čísla sečteme sčítačkou.
-- b) Odhadněte asymptoticky hloubku a velikost sítě pro násobení.
- 92. DÚ kandidát. Ukažte, jak hradlovou sítí v logaritmické hloubce otestovat, zda je
bitové číslo dělitelné a) sedmi , b) třinácti, c) jedenácti, d) pěti.
- (93.) DÚ kandidát. Ukažte, jak hradlovou sítí v logaritmické hloubce spočítat zbytek po dělení
čísla $n$ pevným číslem $k$. Řešte pro a) k=3, b) k=5, c) k=7, d) k=9, e) k=11, f) k=13, g) k=15,
h) obecné pevné $k$.
-- Pozn: vztah k 8/91. Hodí se např. pro rychlé násobení čísel, s malým počtem hradel.
Další:
- 31. Popište logickou formulí vztah vstupů a výstupů hradla a) XOR,
-- b) NAND.
- 32. Sestrojte XOR pomocí NANDů.
- 33. Kolik je různých binárních funkcí na $n$ binárních vstupech? Vyjmenujte
je pro 2 vstupy (a jeden vstup).
- 35. a) (Dokažte, že) Libovolnou booleovskou funkci s $k$ vstupy, tj. $\{0,1\}^k \to\{0,1\}$,
lze spočítat booleovským obvodem hloubky $O(k)$ s $O(2^k)$ hradly.
- Důsledek: Hradla s nejvýš $k$ vstupy a booleovské obvody s takovými hradly
lze překládat na dvouvstupová hradla a hloubka přitom vzroste pouze konstanta-krát.
- b) Nepolynomiální velikost obvodu je nutná: (dokažte, že) pro žádné $k$ neplatí,
že všechny $n$-vstupové booleovské funkce lze spočítat obvody s $O(n^k)$ hradly.
- 36. a) Zdůvodněte (i líně), že na každou boolovskou funkci stačí NOT a dvouvstupová hradla AND a OR.
-- b) Totéž, stačí dvouvstupové NAND. *Víte*
- 37. a) Ukažte, že každou boolovskou formuli lze přeložit na boolovský obvod.
Velikost obvodu a jeho hloubka budou nejvýš lineární v délce formule.
-- b)* Stačí logaritmická hloubka obvodu v délce formule.
- 38* Dokažte, že každý regulární jazyk lze rozpoznávat hradlovou síti logaritmické hloubky.
(PLA: Univerzální přístup pro ostatní úlohy.)
- Regulární jazyk. Sled v konečném grafu s označenými hranami (označení písmeny z nějaké abecedy).
Hledáte v grafu sled s daným označením a chcete rozhodnout, jestli z daného počátečního vrcholu vede
do některého z daných koncových vrcholů. Obecněji, hledaný sled je popsán regulárním výrazem a
každý vyhovující sled je popsán / charakterizován vlastností výše.
- Pro deterministický konečný automat je jeden počáteční stav a z libovolného stavu právě jedna hrana
s daným označením,
proto je automat v právě jednom stavu (to je determinizmus). Koncových stavů je obecně víc.
Stav můžeme reprezentovat jedním číslem. (Nemáme prázdné (lambda / epsilon/ $\lambda-$ / $\epsilon-$) přechody.)
- I nedeterministický KA. Pro nederministický automat máme obecně víc stavů a libovolný počet hran
se stejným označením, i nulový.
Automat je v podmnožině stavů/vrcholů, reprezentace charakteristickou funkcí na unární reprezentaci čísel stavů.
-- spíš pro ústní vysvětlení, TODO
- KA je kongruence (měli jste na VPL) s konečným počtem tříd.
- 39. i DU kandidát. Sestrojte hradlovou síť logaritmické hloubky, která dostane matici
sousednosti neorientovaného grafu a rozhodne, zda je graf souvislý.
- 40. a) Hradlová síť logaritmické hloubky pro spočítání indexu $i$ nejvyšší jedničky v $n$-bitovém čísle,
indexováno od 0. (Jinak: Dolní celá část dvojkového logaritmu.)
-- b) Varianta: Hradlová síť logaritmické hloubky pro spočítání indexu $i$ nejnižší jedničky v $n$-bitovém čísle,
indexováno od 0.
-- c) Varianta: Hradlová síť logaritmické hloubky vynuluje všechny bity kromě nejvyššího nastaveného v $n$-bitovém čísle.
- 41. a) Lze použít princip sčítačky v logaritmické hloubce na desítková čísla?
-- b) Jak použít (vhodně) tentýž princip na sečtení 4 čísel v logaritmické hloubce?
- 42.
Porovnávání unárních čísel. Dvě čísla, které jsou zadány v unární reprezentaci, chcete porovnat.
-- a) Navrhněte naivní (přímočarý) obvod na porovnání vstupů. Jakou má velikost a hloubku?
-- b) Navrhněte obvod s použitím metody Rozděl a panuj. Jakou má velikost a hloubku?
- 43.
Částečné vyhodnocování Pro řešení nějakého problému dokážeme navrhnout metodou Rozděl a panuj hradlovou síť
s logickými/bitovými operacemi
pro $n=2^l$ vstupů. Víme, že zarovnání vstupu *například* nulami zleva na šířku $n$ se neprojeví na výsledku.
-- a) Jak můžete upravit síť pro $k
-- b) Jak můžete zjednodušit síť pro $k
- Pozn. Podobnou úlohu jsme řešili i pro třídící sítě.
Cvičení 9. Hradlové sítě
- 1. Příklady z minula.
- 2.
- 90. DÚ kandidát.
- 91 a) *na rozmyšlení*
Další:
- 31.
Cvičení 10. Převoditelnost, NP-úplnost
- 0. Opakování: Vysvětlete (v závislosti na přednášejícím): rozhodovací problém, instance problému,
nedeterministický výpočet (pro rozhodovací problém)/verifikátor, svědek řešení/certifikát/nápověda,
převod a polynomiální převod (nebo redukce); třídy P, NP a problémy NP-těžké, NP-úplné.
- Pozn. Certifikát nemusí být "řešení": Pro neprvočíselnost je certifikát dělitel, pro prvočíselnost něco jiného.
- Pozn2. Svědků pro jednu instanci může být víc. (Případně se liší symetriemi.)
- Pozn3. Převod znamená polynomiální převod, pokud není řečeno jinak.
- 0.1 Triviality: a) Máme problém $R$ z NP, o kterém chceme dokázat, že je NPÚ a nějaký vhodný NP-úplný problém $X$. Potřebujeme převod $X$ na $R$ nebo $R$ na $X$?
-- b) Jak se typicky dokazuje o problému $R$, že patří do třídy $NP$?
- Pozn. Pro def. třídy NP potřebujeme nedet. alg./verifikátor. Pro def. třídy NPÚ potřebujeme polynomiální převod.
- 1. a) Najděte boolovské formule (tj. formule výrokové logiky), které se při převodu do CNF zvětší exponenciálně.
-- b) Navrhněte způsob, jak převést boolovské formule do CNF a přitom zaručit pouze polynomiální zvětšení.
- 2. Popište polynomiální algoritmy pro rozhodnutí, zda
-- a) lze graf $G$ obarvit dvěma barvami, (barvení 3 (a více) barvami je "těžké")
-- b) je formule v CNF s klauzulemi délky nejvýš 2 splnitelná, tzv. 2-SAT, (splnitelnost 3-SAT je "těžká")
-- c) je formule v DNF splnitelná,
-- d) v grafu $G$ existuje klika velikosti 5.
-- Pozn: U problému Klika je pro NP-úplnost podstatné, že velikost kliky $k$ je neomezena.
Některé jiné úlohy (3-SAT, Barvení) jsou NP-úplné i pro pevnou hodnotu parametru $k$.
- 3. a) Popište převod mezi problémy KLIKA a NezávisláMnožina (oběma směry).
-- b) Mezi NezávisláMnožina a VrcholovéPokrytí.
-- Pro VrcholovéPokrytí máme jako instanci daný graf $G$
a přirozené číslo $k$ a hledáme podmnožinu vrcholů $P$ velikosti (nejvýš) $k$, ve které leží
z každé hrany alespoň jeden vrchol.
Formálně $|P|\le k \wedge P \subseteq V(G) \land \forall e (e\in E(G) \to e\cap P \not=\emptyset)$
- 4. a) Převod 3-SAT na SAT,
-- b) (Předn. MM) převod SAT na 3-SAT,
-- (c) (Předn. MM) převod 3-SAT na 3,3-SAT - délky klauzulí jsou nejvýš 3 a každá proměnná má nejvýš tři výskyty. (c.1: Jaké kombinace literálů pro jednu proměnnou můžou nastat?)
-- d) Proč problém splnitelnosti obecné (výrokové) formule redukujeme na problém splnitelnosti formule v CNF a ten dále na problém splnitelnosti v CNF "s klauzulemi délky nejvýš 3".
- 5. (Polynomiální) Převod splnitelnosti obecné výrokové formule na splnitelnost formule v CNF (SAT). (Víte: opačně je to jednoduché.)
- (6). a) Převod SAT $\to$ NezávisláMnožina, (nebo SAT $\to$ KLIKA - Předn.JH). (Předn. OC: 3-SAT $\to$ NezávisláMnožina )
-- (b) Upravte obecný převod na převod z 3-SAT (Co se zjednoduší?)
- 7. (Předn. OC,MM) Opačný převod NezávisláMnožina $\to$ SAT, pro vstupní instanci $(G,k)$.
Idea: Očíslujeme vrcholy, proměnné pro příslušnost vrcholu ke NM na i-tém místě a zabezpečení požadovaného počtu $k$ vrcholů v NM.
-- Pozn.: Obecně, oba problémy můžou mít víc řešení. Speciálně zde, jednomu řešení NM odpovídá víc řešení SAT, protože převod obsahuje inherentně určení pořadí. (Zpermutovaná symetrická řešení jsou taky řešení.)
-- Pozn2. Zavedení proměnných pro všechny nezávislé množiny až do dané velikosti není
polynomiální redukce.
- 8. Jak řešit zjišťovací problém pomocí rozhodovacího? (Tj. jak omezující jsou rozhodovací problémy?) Tj. chceme najít
konkrétní řešení pro problém a) Kliky, b) HAM, c) Barvení.
- (8.1) Jak řešit optimalizační problémy? (Např. jak nalézt a/ největší kliku, b/ nejkratší HAM, *s_reálnými_čísly*.)
- 90. DÚ kandidát. Najděte převod HAM $\to_p$ SAT. Převeďte
polynomiálně problém existence Hamiltonovské kružnice HAM
na problém Splnitelnosti SAT,
kde formule je v CNF. Instance HAM je neorientovaný graf, instance SAT je formule v CNF.
- 91. DÚ kandidát. Máme 3 úlohy, všechny na neorientovaných grafech. 1. HAM: Existuje Hamiltonovská kružnice v grafu $G$;
2. HAMC: existuje Hamiltonovská cesta v grafu $G$ (tj. cesta, která prochází všemi vrcholy);
3. HAMuv: existuje Hamiltonovská cesta v $G$ z $u$ do $v$, instance je $(G,u,v)$.
Najděte přímé převody mezi těmito úlohami.
- Pozn. Pro převod HAMC $\to$ HAM převod identitou grafu $G$ se zdůvodněním "Pokud v $G$ existuje hamiltonovská kružnice, pak v $G$ existuje
také hamiltonovská cesta" není správné řešení ani postup. (Viz 10/34.)
- Pozn2. Viz 10/85,86,87 pro popis některých častých chyb.
- Var./rozšíření: viz 10/50
- Pozn3. Všimněte si, že: Jedno z řešení obsahuje mnoho klauzulí délky 2 a málo klauzulí větší délky. Přesto
nejde použít polynomiální alg. pro 2SAT. Na druhé straně, klauzule délky 2 v DPLL při dosazení proměnné buď jsou
splněné (a vypadnou) nebo lze hodnotu druhé proměnné určit (a dále propagovat). ; TODO-dočistit a přidat do VPL
- 91.1 Analogicky k cv. 91.: Převeďte navzájem polynomiálně problémy HAM, HAMC a HAMuv na orientovaných grafech.
- 92. *Na rozmyšlení*/DÚ spec.: Navrhněte heuristický algoritmus (nebo heuristiky)
pro obarvení grafu co nejmenším počtem barev.
- Motivace: a) hladová heuristika,
- b) máte skoro 3-regulární graf, který obsahuje pouze jeden vrchol stupně 2. Jak ho obarvit 3 barvami?
- c) (statický a) dynamický výběr vrcholů ... víc možností.
- 93. *Na rozmyšlení*: Navrhněte heuristické algoritmy nebo heuristiky pro Problém Obchodního Cestujícího.
-- a) Heuristiky, které budou účinné/vhodné pro grafy s trojúhelníkovou nerovností.
-- b) Heuristiky, které budou účinné/vhodné pro obecně ohodnocené grafy.
- 94. DÚ kandidát/náhr. Najděte převod 3-BARVENÍ $\to_p$ SAT. Převeďte
polynomiálně problém 3-BARVENÍ grafu $G$
3 barvami na problém Splnitelnosti SAT, kde formule je v CNF.
- 94.1 Najděte převod BARVENÍ $\to_p$ SAT. Převeďte
polynomiálně problém BARVENÍ grafu $G$
$k$ barvami na problém Splnitelnosti SAT, kde formule je v CNF. Instance problému BARVENÍ je $(G,k)$.
Další:
- 9. a) (Předn. JH) TODO/Spojit do dalšího příkladu. Převod problému Součet podmnožiny na Problém dvou loupežníků.
- b) Opačně: Převod Problém dvou loupežníků na Součet podmnožiny.
- c) Speciálně: Při převodu chcete dostat množinu čísel, tj. chcete zabránit opakovaným hodnotám na vstupu.
- 31. (Předn. JH) Problém SoučetPodmnožiny je zadán jako množina přirozených čísel $V$ a číslo $b$.
Odpověď je ano, pokud existuje množina $S \subseteq V$, tak že součet $S$ je přesně $b$.
-- Problém dvou loupežníků je zadán jako množina $V$. Odpověď je ano, pokud $V$ lze rozdělit na dvě podmnožiny se stejným součtem.
-- a) Převeďte problém dvou loupežníků na součet podmnožiny.
-- b) Převeďte součet podmnožiny na problém dvou loupežníků.
-- c) Specificky, v minulé odrážce, pokud v problému součet podmnožiny dostaneme podmnožinu s lichým součtem, co s tím?
-- d) Obecně, pokud dostanete "syntakticky" špatný vstup, co s tím?
-- e) Jak by vypadala optimalizační verze problému SoučetPodmnožiny?
- 32. Problém batohu. Máme dány předměty s váhami a cenami a nosnost batohu. Máme najít co nejdražší podmnožinu předmětů, kterou batoh unese. Toto je častá optimalizační formulace. Pro rozhodovací formulaci bychom na vstup zadali ještě požadovanou cenu a ptali se, jestli je dosažitelná.
-- V problému jsou předměty celočíselné a nedělitelné. Pro dělitelné předměty existuje polynomiální řešení.
-- Pozn.: zjednodušená varianta bez cen je problém SoučetPodmnožiny.
- 33. Dal by se pro úlohy podobné splnitelnosti použít podobný přístup, např. pro
nesplnitelnost, pravdivost, existence nepravdivého ohodnocení. Co by mohl být v jednotlivých případech svědek a jak by byl velký?
- 34. Při důkazu převoditelnosti konstrukci děláme specificky pro jeden převod $A \to B$ (určitým směrem) pomocí $f$, ale
vztah $x\in A \leftrightarrow f(x) \in B$ mezi $ x $ a $f(x)$ dokazujeme oběma směry. Co by se změnilo, pokud bychom požadovali pouze implikaci $x\in A \rightarrow f(x) \in B$?
- 35. Pokud bychom použili polynomiální převoditelnost ve třídě P, jaké problémy by byly P-úplné? (Pojem P-úplnosti
se používá, ale pro jinou, "jemnější" převoditelnost)
- (36.) Dokázat NP-úplnost 3D párování. Máme 3 druhy objektů A, B a C a množinu
kompatibilních trojic $T \subseteq A \times B \times C$. Chceme zjistit, zda existuje perfektní množina trojic, ve které je každý prvek jednou. Z 3,3-SAT. (Predn. MM) TODO
-- Pozn. 3D párování při převodu na jiné problémy má výhodu, že řešení je "přesně určeno": každý prvek je ve vybraných trojicích *právě* jednou.
- 37. A naopak, převést 3D-párování na SAT.
- Myšlenka typického převodu na SAT: zavedeme (výrokové, dvouhodnotové) proměnné reprezentující stavy řešení instance a vyjádříme požadavky
na řešení jako formule (často přímo v CNF).
- Myšlenka typického převodu ze SAT: potřebujeme gadgety/graphlety pro 1) reprezentování dvouhodnotové proměnné a 2) reprezentování splnitelné klauzule
- 38. Další problémy:
-- a) Barvení grafu $k$ barvami. Dokonce barvení 3 barvami je NPÚ.
-- b) Soustava nula-jedničkových lineárních rovnic ${\bf Ax} = {\bf 1}$:
Je dána matice ${\bf A}\in \{0,1\}^{m\times n}$ a ptáme se, zda existuje vektor ${\bf x}\in \{0,1\}^{n}$
takový, že $\bf Ax$ je rovno vektoru samých jedniček.
-- c) Splnitelnost obecných formulí, nejen v CNF.
-- Při převodu obecných formulí na ekvivalentní (ekvisplnitelnou) formuli v CNF potřebujeme zaručit polynomiální převod,
viz některé předchozí cvičení. (Není to triviální, přímé použití distributivity na polynomiální převod nevede.)
- 39. a) (Předn. MM/2019?) Převést 3D-párování na soustavu 0-1 rovnic.
-- b) (Předn. MM/2019?) Převod soustavy 0-1 rovnic na součet podmnožiny.
-- Idea: řádky zakódujeme do dlouhých čísel, bity musíme oddělit nulami, aby součty řádů nepřetekly.
- 40. SAT řešiče. Jaké výhody (a nevýhody) má použití SAT-solverů pro řešení úloh? Tj. místo přímého řešení
problému $X$ převedeme $X \to SAT$ a řešíme vzniklé instance SAT solverem.
- 40.1 TODO Jaké má výhody a nevýhody explicitní generování vstupních souborů v DIMACS formátu? (Z VPLogiky.)
- 41. Instantní kód. Jak zakódovat číslo $x$ neznámé velikosti tak, abychom při čtení poznali,
kde kód skončil? Ideálně chceme $\log_2 x +o(\log_2 x)$ bitů.
- 42. Výroba relace uspořádání z reflexivní a tranzitivní relace, tzv. kvaziuspořádání a jeho faktorizace.
- 43. Převod problémů na SAT: a) Barvení, b) 3D párování, c) Soustava 0-1 rovnic, ...
(Některé převody jsou samostatně.)
-- I jednodušší (i z P) i) násobení čísel, j) sčítání, k) rozklad součinu na dvě čísla.
- 44. (?Předn. MM) Převod 0-1 rovnice na součet podmnožiny.
- 45. Převod SAT na 3-barvení.
- Idea: 3 barvy jsou 0, 1 a N (neutrální). Trojúhelníky: $(0,1,N)$, $(x^+,x^-,N)$ pro každou proměnnou $x$, tj. pro její literály, pak "graflet" pro klauzuli o délce $k$ s řetízkem $k-1$ trojúhelníků a další hrany, např. pro $x\lor \neg y \lor z$ trojúhelníky $(v_x,v_y,v_{xy})$ a $(v'_{xy},v_z,v_{xyz})$ a hrany ($x^+,v_x)$,
$(y^- ,v_y)$, $(z^+, v_z)$, $(v_{xyz}, 0)$ a pro spojení trojúhelníků $(v_{xy}, v'_{xy})$.
- Pozn. I když převádíme 2-SAT, dostaneme NP-úplný problém barvení 3 barvami.
- 46. (Předn. OC) Převod Vrcholové pokrytí (G,k) na Součet Podmnožiny.
-- Idea: matici incidence $V\times E$ s předsazenou "1" zakódujeme do dlouhých čísel, přidáme samostatné řádky pro vrcholy
s předsazenou "0", (vrcholy stupně 1 ošetřené samostatně), součet jsou dvojky s předsazeným "k", přičemž bity jsou odděleny
nulami kvůli zamezení přetečení.
- (47.) Cookova věta: SAT je NP-úplný. A Kachličkování je NPÚ.
- (48.) a) Převody: Hamiltonovská kružnice (nebo cesta) v grafu s přikázanými hranami do kružnice na HAM
-- b1) Orientovaná HAMiltonovská kružnice na (neorientovaný případ) HAM, b2) a naopak.
- (49.) Multikomoditní tok v síti je NP-úplný. Každá komodita má určený zdroj a stok a kapacity hran jsou sdíleny všemi komoditami.
- 50. Rozšíření DU: HAMu: je zadaný jeden koncový vrchol cesty, pro orientované verze počáteční nebo koncový.
- (51.) a) Je zadán orientovaný graf a jedna orientovaná Ham. kružnice. Rozhodněte, zda existuje jiná.
- b) Analogicky, jeden graf a víc kružnic. Existuje další Ham. kružnice? (Pro orientované je převod snažší, prý.)
- 52. Jaká zjednodušení můžete použít jako preprocesing na formuli v CNF předtím, než ji pošlete SAT solveru?
- Pozn. Při převodu na SAT může být víc použitelných (polynomiálních) reprezentací i z hlediska promenných, i z hlediska klauzulí.
Víc klauzulí umožňuje v SAT solveru lepší propagaci, ale požaduje větší režii.
- 85. (Pozn./Reakce k DÚ 10/90 HAM->SAT) Při převodu se pracuje s nějakým konkrétním kódováním. I když je změna instance "malá", tak potřebujeme přečíst
(a deserializovat) vstup a pak (serializovat a) zapsat výstup. Kódování nemusí být na úrovni bitů, ale můžeme pracovat nad nějakou (pevnou)
abecedou $\Sigma$ (např. $\verb!;-)!$ ASCII, UTF-8).
- 86. (Pozn./Reakce k DÚ 10/90 HAM->SAT) V našem přístupu k polynomiální převoditelnosti
(rozhodovacích problémů)
převádíme problém $A$ na problém $B$,
značeno $ A \le_p B$ (nebo v knížce PLA $A \to B$). Pro převod chceme pro
instanci $I_A$ (tj. vstup, zadání)
problému $A$ vyrobit
jednu instanci $I_B$ problému $B$ tak, aby odpovědi byly stejné,
tj. $I_A \in A \leftrightarrow I_B \in B$. (Totéž vyjádřeno pomocí algoritmů $alg_A(I_A) = alg_B(I_B)$,
když $alg_A$ a $alg_B$ rozhodují problém $A$ a $B$, respektive. Funkce pro zpětný převod výsledku je vlastně identita,
nesmí to být ani negace.) Tento přístup se nazývá Karpova převoditelnost,
když ho potřebujeme odlišit od přístupu níže.
- Jiný přístup
, který my nepoužíváme (ani v DÚ), (nazývaný Cookova nebo polynomiální Turingovská
převoditelnost) je, pokud $alg_A$ může při řešení zadání $I_A$ víckrát volat $alg_B$ pro různá zadání problému $B$.
Takový přístup je více programátorský a pro někoho přirozenější. Dá se přirozeně použít např. při převodu HAM na HAMC
nebo pro převod HAMC na HAMuv (značení viz 10.91). Volaný $alg_B$ se někdy nazývá
orákulum.
- Tento druhý přístup jsme použili např. při zjišťování $k$-souvislosti pomocí toků v sítích.
- 87. (Pozn./Reakce k DÚ 10/90 HAM->SAT) Převoditelnost obecných problémů (a směr převodu). Pro zjišťovací problémy $A$, $B$,
kde $A \le_p B$, převádíme zadání $I_A$ na $I_B$ pomocí fce $g$ a výsledek $V_B$ problému $B$ na výsledek $V_A$
problému $A$ pomocí fce $h$. Pro správnost požadujeme $alg_A(I_A) = h(alg_B(g(I_A)))$, kde značení algoritmů
je převzato z minulého příkladu. Pro polynomiální převoditelnost musí být funkce $g$ a $h$ polynomiální.
- Pokud, v obecnosti, je zadání $I_A$ nad abecedou $\Sigma_A$, výsledky $V_A$ nad $\Pi_A$
a podobně $I_B$ nad $\Sigma_B$ a výsledky $V_B$ nad $\Pi_B$, potom typy použitých funkcí jsou
$alg_A:\Sigma_A^* \to \Pi_A^*$, $alg_B:\Sigma_B^* \to \Pi_B^*$, $g:\Sigma_A^* \to \Sigma_B^*$, $h:\Pi_B^* \to \Pi_A^*$,
kde hvězdička ($()^*$ v exponentu) znamená množinu konečných slov nad příslušnou abecedou.
- 88. Možnosti řešení problémů z třídy NP (a těžších): viz dále.
- 89. Různé: a) pro NPÚ problémy můžou existovat lehké instance (nebo skupiny instancí), a.1) NPÚ je dolní odhad,
-- b) fázový přechod (pro náhodný 3-SAT, ale i pro jiné problémy): Instance, které mají málo klauzulí (podmínek/omezení),
mají mnoho řešení
a jedno řešení se najde lehce (např. prohledáváním), protože pro "skoro" libovolnou volbu hodnot počátečních promenných
řešení existuje (tzv. instance je SAT - splnitelná/satisfiable) a lze ho dopočítat. Instance, které mají mnoho klauzulí,
jsou "skoro vždy" nesplnitelné (tzv. UNSAT) a neexistence řešení
se projeví už po přiřazení části proměnných. Instance, které mají vhodně klauzulí mezi popsanými extrémy, jsou těžké,
protože musíme přiřadit hodnoty skoro všem proměnným, abychom zjistili, že instance je UNSAT, a mohli pokračovat
v prohledávání bachtrackingem. U těchto instancí
dochází pridáváním klauzulí ke změně ze SAT na UNSAT, proto fázový přechod.
-- c) v NP jsou problémy s existenčním kvantifikátorem a polynomiálním ověřením.
-- Pozn. o SAT a SAT-solverech viz moje cvičení z VPL.
Cvičení 11. Převody
- 1. Příklady společně v minulém cvičení.
- 2.
- 90. DÚ kandidát.
- 91 a) *na rozmyšlení*
Další:
- 31.
Cvičení 12. Aproximační alg.
- 1. a) Reformulujte rozhodovací NP-úplné problémy jako optimalizační.
b) Dokážete převést rozhodovací verzi na optimalizační a naopak?
- 2. Uveďte obecné způsoby řešení těžkých problému a příklad(y) konkrétního alg., který ho používá.
- Tři základní, dále heuristiky, kombinace.
- 3. DÚ kandidát: a) Najděte polynomiální algoritmus pro hledání největší nezávislé množiny ve stromě.
-- b) největší kliky ve stromě $\verb/;-)/$
- 4. a) Přesné řešení problému batohu bez cen. (Proč alg. není polynomiální?) b) Rekonstruovat řešení.
- (5) a) Přesné řešení problému batohu s cenami. b) Rekonstruovat řešení.
- 6. Jaký je rozdíl mezi heuristickým a aproximačním algoritmem?
- 7. (Předn. OC) Aproximační alg. pro vrcholové pokrytí, s pevnou relativní chybou 2.
- 8. (Předn. OC) Aproximační alg. pro POC (problém obchodního cestujícího) za platnosti trojúhelníkové nerovnosti.
- 9. (Předn. OC,MM) Aproximační schéma pro batoh bez cen.
- Pozn. Teoretický příklad schematu, které není polynomiální v $1/\epsilon$: Při změně požadované chyby
od $1/n$ k $1/(n+1)$ se čas výpočtu zdvojnásobí.
- (10*) Aproximační schéma pro batoh s cenami. (Kvantovat ceny.)
- 11. a) Máte aproximační alg., heuristiky a počítačový klastr s 1024 procesory/jádry.
Jak dosáhnout co nejlepšího výsledku, ale se zárukou aprox. alg.? (Modelový problém: Barvení grafu.)
-- b) To samé, ale máte naprogramovanou jednu deterministickou heuristiku (např. hladovou heuristiku). Jak zajistit,
aby se prohledala
co největší část stavového prostoru? (Barvení, HAM, POC/TSP, SAT)
-- b1)
Rozdisjunktnění: TODO Speciálně, dokážete zajistit, že se prohledávají disjunktní části stavového prostoru? Dokážete to zadat
jako instanci původní úlohy, tj. bez pomoci samostatných okrajových podmínek? Vysvětlete pro problém
-- b1.a) barvení
-- b1.b) HAM
-- b1.c) SAT
-- (c) Anytime algoritmy: čím déle běží, tím lepší řešení vydají (často systematické nebo neúplné prohledávání
stavového prostoru, přitom čím déle běží, tím víc prohledají. Prohledávají chytře, tu "nejslibnější" část stavového prostoru.)
-- (d) Odstraňování symetrií, při (i úplném) prohledávání. TODO
-- (e) Pokročilé prohledávání: beam seach, A*, IDA, diskrepanční prohledávání, ...
- 90. DÚ kandidát. Vážená verze nezávislé množiny ve stromě. Vrcholy mají váhy a hledáme nezávislou množinu
s maximálním součtem vah.
- 91. DÚ kandidát. Největší nezávislá množina ve stromě.
Další:
- 31. Nejmenší vrcholové pokrytí stromu.
- (32.) Nejmenší vrcholové pokrytí v bipartitním grafu.
- 33. Dělení pro 3 loupežníky. Pomocí pseudopolynomiálního alg.
- 34. a) Heuristiky pro řešení POC (problému obchodního cestujícího), angl. TSP.
-- b) Heuristiky pro zlepšování POC.
- 35.
Interní heuristika. Jak dostat pro POC z aproximačního alg. s trojúh. nerovností co nejlepší řešení?
Například pro graf v rovině s euklidovskou metrikou chcete zajistit, aby se hrany kružnice neprotínaly.
- Idea: alg. je generický, dovoluje rekonstruovat řešení z lib. průchodu kostry. Jak procházet kostru vhodně?
Nebo ještě lépe, jak to formulovat jinak.
- 35.1 Christofidesův alg.: 3/2-aproximace TSP s trojúh. nerovností.
- 36. Heuristika pro hledání hamiltonovské cesty. (Co chceme dosáhnout?
Kdy je jedna heuristika lepší než druhá?)
- 36.1 Chceme nedokonalý polynomiální algoritmus pro rozhodovací problém existence Ham. cesty. Z čeho můžemem slevit?
- 37. Jak se chová hladové řešení pro vrcholové pokrytí, když přidává vždy vrchol
s největším stupněm? Najde optimální řešení? Najde $\alpha$-aproximaci optimálního řešení, pro nějaké pevné $\alpha$?
- 37.1 Je optimální řešení vrcholového pokrytí pro spojité bipartitní grafy vždy menší partita?
- 38. Řešení POC pomocí dynamického programování. Zlepšení proti hrubé síle se složitostí $O(n!)$.
- 39. 2-aproximace Vrcholového pokrytí pomocí DFS. Přidáváme všechny vrcholy kromě listů DFS stromu.
- 40. V orientovaném grafu hledáme acyklický podgraf s maximálním počtem hran.
Navrhněte 2-aproximační algoritmus.
- 41. Najděte polynomiální algoritmus pro POC, když jsou zadané body vrcholy konvexního mnohoúhelníka. (Předbíháme, asi.)
- 42.
Hladová heuristika. Ukažte, že pro optimalizační verzi Součtu podmnožiny hladová heuristika nevrací
optimální řešení.
- 43. Heuristiky/metody pro neúplné prohledávání stavového prostoru SAT.
- Jaká je nevýhoda neúplných prohledávačů?
- 44. Barvení chytrým výberem nezávislé množiny. TODO+PRESUNOUT , alg. má název (Recursive_largest_first_algorithm/RLF).
Cvičení 13. Geometrické alg, konv. obal
- 1.a
Oddělující přímka. PLA 16.1.2 Pro dvě množiny bodů v rovině hledáme přímku, která je oddělí.
-- b) Nejširší oddělující pruh. Hledáme přímku, okolo které je co nejširší pruh bez bodů.
(Používá se v UI, ale ve vícerozměrných prostorech s oddělující nadrovinou. )
-- (c) Předpokládejte, že pro obě množiny máte konvexní obal. Jak rychle najdete nejširší oddělující pruh?
- (2.) Lokalizace bodu. +Perzistence d.s.; Předn. 2021-MM
- 3. PLA 16.1.6 Převod třídění na konv. obal. Pokud body konvexního obalu vydáváme v pořadí, jak leží na konv.
obalu, tak pomocí nalezení konv. obalu dokážeme uspořádat reálna čísla. Tj. nelze nalézt konv. obal lépe než
v $O(n \log n)$ pro obecně zadané body (tj. bez předtřídění).
- 4. PLA 16.1.1 Upravte alg. na konvexní obal, aby vynechával vnitřní body na úsečkách k. o.
- 5.a) Zametání přímky bodem: Pro danou množinu uzavřených intervalů na přímce chceme zjistit, jaký je
maximální počet intervalů, které se protínají v jednom bodě.
- b) Stejné zadání. ale chceme zjistit počet protínajících se dvojic intervalů.
- 90. DÚ kandidát. PLA 16.6.1 Plocha konv. mnohoúhelníka, lineárně. Je zadán konv. obal, uspořádaně.
- 91. DÚ kandidát. PLA 16.6.2 Plocha nekonv. mnohoúhelníka, lineárně. Je zadán obal, uspořádaně.
Další:
- 30. PLA 16.1.3 Dvoudílný konv. obal. Danou množinu bodů v rovině rozdělíme na dvě části, kterým
opíšeme konv. obal. Chceme, aby součet obvodů byl co nejmenší.
- 31. PLA 16.2.1 Najděte systém $n$ úseček, které mají $\Theta(n^2)$ průsečíků.
- 32. PLA 16.2.4 Je dána množina obdélníků, jejichž strany jsou rovnoběžné s osami.
Spočítejte obsah jejich sjednocení.
- 33. PLA 16.3.3 Dostupnost kruhovým robotem. Kruhový robot se pohybuje mezi bodovými překážkami v rovině.
Jak zjistit, zda se dokáže dostat z jednoho místa na druhé? Nápověda: stačí, aby robot chodil po hranách
Voroného diagramu.
A dostal se z počátečního bodu na diagram a zpět.
- 34. PLA 16.3.5 Euklidovská minimální kostra. Hledáme minimální kostru úplného grafu. Klasický alg. musí
zpracovat kvadraticky mnoho hran. Ukažte, že hledaná kostra je podgrafem Delaunayovy triangulace a teda stačí
zkoumat lineárně mnoho hran.
- 35. PLA 16.6.3 Jak o množině bodů v rovině zjistit, zda je středově symetrická.
- 36. PLA 16.6.5 Jak k dané množině bodů v rovině najít obdélník, který bude mít nejmenší obvod
a bude obsahovat všechny body? Obdélník nemusí mít strany rovnoběžné s osami.
- 37. PLA 16.6.6 Vymyslete datovou strukturu, která bude udržovat konvexní obal množiny bodů
a bude ho umět rychle přepočítat po přidání bodu do množiny.
- 38. PLA 16.6.7 Je dána množina obdélníků, jejichž strany jsou rovnoběžné s osami souřadnic.
Navrhněte datovou strukturu, která bude umět rychle odpovídat na dotazy typu "v kolika obdélnících leží daný bod"?
- 39. Opsaná kružnice. (Smallest enclosing circle) Navrhněte algoritmus, který najde pro danou množinu bodů nejmenší opsanou kružnici.
(Např. udržujeme "bázi" pro část bodů. Lze i rekurzí. Deterministicky pomalu i randomizovaně.)
-- Pozn. Náhodnou permutaci (objektů v poli) délky $n$ lze vytvořit lineárně.
- (40.) a) Horní konv. obal, mosty.
- 41. Nejbližší body. Jak najít v dané množině bodů dva nejbližší body? (Rozděl a panuj,
s dobrou implementací. Projekce z uspořádaného seznamu, lineární spojení s konečným počtem blízkých bodů na 1 bod.)
- 42. Nejvzdálenější body. Jak najít v dané množině bodů dva nejvzdálenější body?
- 43. Šířka pásu. Pro danou množinu $n$ bodů v rovině, najít nejmenší vzdálenost mezi dvěma rovnoběžnými
přímkami tak, aby všechny body ležely mezi přímkami, včetně přímek. (Nejužší pás.)
- 44. Nej. Shrnutí. Pro $n$ bodů v rovině můžeme hledat nejmenší objekt, který je obsahuje:
a) nejmenší konvexní obal, b) nejmenší čtverec, c) nejmenší obdélník, plochou, d) nejužší obdélník (pás),
e) nejmenší kruh, f) nejmenší obdélník rovnoběžný s osami.
- (45.) Je dáno $n$ kruhů v rovině. Jak spočíst nejnižší bod jejich společného průniku? (Randomizovaně inkrementálně.)
- (46.) Je dáno $n$ kruhů v rovině. Jak spočíst nejnižší bod jejich sjednocení? (Randomizovaně inkrementálně.)
- (47.) Je dána množina $n$ polorovin. Jak efektivně rozhodnout, zda jejich průnik je prázdný?
-- b) Jak nalézt bod z průniku?
-------------------------------------------------
DÚ1 2.90 (8.10.): Máte daný vzorek. Najděte jeho lexikograficky minimální cyklické pootočení.
Nápověda: lineárně.
DÚ2 3.90 (22.10.): Inkrementální update cesty
DÚ3 3.91 (29.10.): hranová $k$-souvislost
DÚ4 4.90a (5.11. na 19.11.): Alg. 3 Indů, napsat výukově, jako součást textu do BcP
DÚ5 7.90 (26.11. na 3.12.): komparátorová síť pro max, dolní odhad.
DÚ6 8.91 (3.12. na 10.12.): Lepší síť pro násobení
DÚ7 10.91 (10.12. na 17.12.): Převody mezi HAM, HAMC a HAMuv
..a 10.92 (10.12. na 17.12.) na rozmyšlení
DÚ8 10.90 (17.12. na 8.1.2019, poslední): převod HAM na SAT.
.. na rozmyšlení zůstává z minula.
Náhradní příklady ZS2018/19:
Za každé (načaté) 2 body, které vám chybí, vypracujte 1 příklad z následujícího seznamu.
3.39 Nástroje a projekty.
6.91 Konečná tělesa pro FFT.
8.4 Hradlová síť pro odečítání
8.92a Síť pro dělitelnost 7.
-------------------------------------------
Slovníček
d.s.: datová struktura
BÚNO: Bez újmy na obecnosti
FT: Fourierova transformace
FFT: Rychlá Fourierova transformace; Fast FT
DFT: Diskrétní Fourierova transformace
IFT: Inverzní Fourierova transformace
DCT: Diskrétní kosínová transformace
DSL: Domain Specific Language, doménově specifický jazyk
NP: Nedetermnisticky Polynomiální, taky třída NP alg.
NPÚ, NPC: NP-úplný, NP-complete
CNF/DNF: Konjunktivní (Conjunctive) Normální Forma, resp. Disjunktivní NF
HAM: problém HAMiltonovské kružnice
SAT: SATisfiability, splnitelnost
POC: Problému obchodního cestujícího, angl. TSP: Travelling Salesman Problem
Řecká písmena: ...
Nástroje
- 47. zvlastni fonty: $ mathbb \mathbb{C}$ a $ mathcal \mathcal{C} $
-
--------------------
Příliš žluťoučký kůň úpěl ďábelské ódy. áäčďéěíĺľňóö $\rm\hat{o}$ řŕšťúůýž