Druhá série jedenáctého ročníku KSP

Řešení úloh

11-2-1 Kva-kva-kvadrant (Zadání)

Řešení této úlohy má dvě hlavní části: první je zjednodušování posloupnosti transformací a druhá je jejich provádění. Na každé z nich se dalo mnoho optimalizovat – při zjednodušování se ušetřil čas a při transformování paměť. Nechť počet transformací je M a délka kódu obrázku je N.

1. Zjednodušování permutací

Jak již bylo v zadání zdůrazněno, posloupnost transformací může být velice dlouhá, a není proto radno aplikovat je postupně všechny (M krát) na každý obrázek. Stačí si všimnout těchto základních vlastností transformací:
  1. Inverze a ostatní transformace se neovlivňují. Černá a bílá se prohazují právě tehdy, pokud je počet inverzí lichý.
  2. Všechny popsané transformace (X, Y, +, -) aplikované na 4 podoblasti jsou obyčejné permutace čtyřprvkové množiny. Jako takové se dají skládat. Místo postupného provádění dílčích permutací tedy můžeme provést všechny najednou. Při dalším zpracování samozřejmě nesmíme zapomenout, že stejnou permutaci musíme provést rekurzivně i na dalších podoblastech podoblastí…
Na počátku programu nadefinujeme tabulkou 4 základní transformace a uložíme si identitu jako počáteční stav. V proceduře nacti_transformace po každém načteném znaku složíme aktuální permutaci s permutací odpovídající načtenému znaku, resp. změníme paritu počtu výskytů inverze. Výsledkem je permutace ekvivalentní dané posloupnosti permutací. Permutace čtyřprvkové množiny skládáme v konstantním čase, zjednodušení nám zabere celkem O(M) kroků. Paměti potřebujeme konstantně mnoho O(1).

Pár řešitelů se složitě pokoušelo nalézt algebraické metody, jak posloupnost transformací zjednodušit. To bylo značně složité a použitelné pouze na tomto konkrétním zadání. Výše uvedená metoda může pracovat na libovolné sestavě základních permutací jakékoliv množiny. Kromě toho je jednodušší a pochopitelnější.

2. Transformace kódu obrázku

V druhé části úlohy většina z vás správně odhadla, že by se měl použít strom. Jeho struktura odpovídá zadání, tzn. pokud je oblast jednobarevná, uložíme si její barvu, v opačném případě zapíšeme 4 ukazatele na stromy 4 kvadrantů – podoblastí dané oblasti, atd.

Při řešení této úlohy bylo nutné zvládnout 3 fáze: konverze vstupního kódu do stromu, transformace stromu podle zadání a výpis modifikovaného stromu. Zajímavé je, že 2. fázi nemusíme vůbec provádět, protože se jedná o pouhé přeházení pořadí kvadrantů. To můžeme přece udělat až při výstupu. Oba směry konverze mezi textovou a stromovou reprezentací lze nejjednodušeji naprogramovat rekurzivními procedurami.

Většina řešitelů celkem neefektivně alokovala dynamické datové struktury a propojovala je ukazateli. To je celkem pomalé a pamětí plýtvající řešení. Když už máme znaky jednou načtené v poli (vstupní řetězec), nejjednodušší je použít přímo toto pole. Jako ukazatel použijeme index do pole, hodnotou bude znak 0, 1, 2 přímo na daném místě. K uložení stromové struktury potřebujeme ještě u znaků 2 uložit pozice 4 synů.

Kdybychom použili takto naivní postup, potřebujeme na každý znak v poli uložit 4 čísla, což zabere až 4*4=16 bajtů. Většinu takto naalokovaného místa přitom nepoužijeme, protože plno oblastí bude jednobarevných. Zkusme na to jít jinak. Existuje metoda, pomocí které můžeme pouhým binárním stromem zaznamenat libovolně rozvětvený strom s různými stupni vrcholů. Místo toho, abychom zaznamenávali všechny informace o synech v daném vrcholu, propojíme je do spojového seznamu. Levý syn vrcholu bude nyní ukazatel na prvního původního syna, pravý syn vrcholu zase ukazatel na původního bratra nebo NULL pokud to byl poslední bratr. Vzhledem k tomu, že pozice prvního syna je v našem příkladě jasná (je-li na pozici k rozvětvovací znak 2, pak levý horní kvadrant, což je první syn, začíná na pozici k+1), stačí ukládat pouze pozici pravého bratra.

Strom tedy můžeme snadno vytvořit pomocí rekurzivní funkce dekoduj_obraz, která pro jednobarevnou oblast 0 nebo 1 (triviální případ) neudělá nic, pro dělenou oblast 2 propojí syny spojovým seznamem a vrátí celkovou délku celé oblasti. Pomocí této vrácené délky může její volající zase vyplnit spojový seznam jejích bratrů. Každá oblast je takto zapojena do seznamu maximálně jednou a každá dělená oblast se maximálně jednou takto zpracuje, takže celkový čas bude O(N) s pamětí O(N) pro kód obrazu.

Pro transformaci a zápis stromu nadefinujeme proceduru zapis_ztransformovano, která triviální jednobarevnou oblast rovnou vypíše (po případné inverzi) a složenou oblast zpracuje takto: pročtením spojového seznamu zjistí pozice 4 synů, načež rekurzivně vyvolá sama sebe ve zpermutovaném pořadí pro každou podoblast. Tím pádem nejenom převedeme strom na text, ale dokonce ho i ztransformujeme podle dané permutace. Opět pracujeme každý znak právě jednou, což nám zabere čas O(N).

Celkově program vystačí s pamětí O(Nmax), kde Nmax je délka nejdelšího kódu obrázku, a poběží O(M+∑Ni) kroků, kde Ni jsou délky jednotlivých kódů.

Program

Robert Špalek

11-2-2 Zákeřná posloupnost (Zadání)

Zákeřnost naší posloupnosti je v její délce. Je totiž dlooouhatánská, což znamená, že se nevejde do žádného pole ani souboru a dokonce ani na celý disk. Proto bylo nutné najít takový algoritmus, který není paměťově a ani časově náročný. Takový algoritmus existuje a využívá funkce XOR, která má následující vlastnosti:

  1. Komutativnost: a xor b = b xor a
  2. Asociativnost: (a xor b) xor c = a xor (b xor c)
  3. ∀a platí, že a xor a = 0
  4. ∀a platí, že a xor 0 = a

Pokud postupně xorujeme čísla v dané posloupnosti, bude výsledkem číslo, které je v posloupnosti pouze jednou. Proč?

Každé číslo až na nějaké b je v posloupnosti dvakrát. Díky vlastnosti 1) můžeme posloupnost xorů určitě přerovnat na: b xor a1 xor a1 xor a2 xor …xor an xor an. Díky vlastnostem 2) a 3) pak víme, že výsledek bude b xor 0, což je podle 4) rovno b.

Časová složitost bude lineární s délkou posloupnosti (lépe už to ani nemůže jít – musíme načíst celou posloupnost), paměťová bude konstantní.

Program

Ája

11-2-3 Případ scottského skota (Zadání)

Valnou většinu řešitelů napadl známý Dijkstrův algoritmus. U tohoto algoritmu je ale problém se správou prioritní fronty, která je v optimální implementaci pomocí Fibonacciho hald sice docela rychlá, ale zato značně komplikovaná. Nicméně použití Dijkstrova algoritmu pro tento problém je vrhání atomových náloží na vrabce.

Úlohu lze řesit jednoduchou modifikací algoritmu vlny. To je algoritmus, který lze použít ke hledání nejkratší cesty v jednoduchém bludišti (bez dveří). Algoritmus postupně počítá velikosti nejkratších cest do jednotlivých políček bludiště. Nejprve nastaví délku cesty vstupního políčka na 0. Dále následují jednotlivé etapy (vlny), které vždy označí všechna ještě neoznačená políčka sousedící s označeným políčkem z minulé etapy. Jejich vzdálenost se snadno určí tak, že se přičte 1 ke vzdálenosti jeho označeného souseda.

V okamžiku, kdy algoritmus označí políčko s pokladem, je vyhráno. U každého políčka je dobré si poznamenat, od jakého souseda se na něj přišlo. Cestou zpět se pak stačí řídit těmito ukazateli a musíme dojít nejkratší cestou ke vchodu. Aby se cesta nevypisovala odzadu, lze použít jednoduchý trik a prohodit vchod a poklad v bludišti. Pokud algoritmus v nějaké etapě neoznačí žádná nová políčka, cesta k pokladu neexistuje.

Nejdelší čas algoritmus tráví při hledání sousedů označených políček z minulé etapy. Tato práce je ale naprosto zbytečná. Je možné si vytvořit frontu a už při zpracovávání políčka zařazovat jeho sousedy na konec fronty. Další políčko na zpracování se pak získá vybráním prvního prvku fronty. Tím zmizí i hranice etap. Políčka z jedné etapy se dostanou do fronty dříve, než políčka z následujících etap. Tím pádem se algoritmus o žádné etapy starat nemusí. Pokud cesta k pokladu nevede, algoritmus vyplní celé dostupné bludiště a pak vyprázdní frontu. Tak se snadno pozná, že cesta není.

Komplikaci přinášejí dveře. Pokud algoritmus bude brát dveře jako místnosti, najde sice cestu, ale chudák Scott o dveře omlátí nejeden krumpáč. Zkusíme tedy náš algoritmus poněkud vylepšit. Pro začátek budeme o dveřích uvažovat jako zdech a nalezené dveře si pouze budeme řadit do nějaké pomocné fronty. Když už projdeme všechna políčka v dané oblasti (část bludiště dosažitelná bez prokopnutí dveří), začneme prokopávat dveře. Prokopneme tedy první dveře (zařadíme je do fronty ke zpracování), na které jsme narazili, a za nimy pokračujeme v šíření stejně jako na počátku, až na jednu malou úpravu. V případě, že je vzdálenost zařazovaných políček stejná jako vzdálenost prvních dveří v pomocné frontě (ty zároveň budou jistě také nejbližší), zařadíme tyto dveře do fronty jako normální políčko ke zpracování (samozřejmě z pomocné fronty dveře odebereme). Takto si zajistíme, že pokud jde mezi dvěma oblastmi projít různými dveřmi, vybere si Scott ty nejvhodnější (tzn. ne nutně ty nejbližší). Ještě si musíme zajistit, aby jsme takto nezařadili dveře, ke kterým jsme se dostali na větší počet prokopnutí. To můžeme udělat snadno – třeba tak, že si budeme udržovat 2 pomocné fronty na dveře. Jednu, ze které odebíráme dveře, a druhou, do které dveře přidáváme (ke dveřím z této fronty jsem se dostal až po prokopnutí dveří z předchozí fronty). Když se fronta, ze které odebírám, vyprázdní a nebude už kam jít – prošel jsem všechny oblasti dosažitelné jedním prokopnutím – začnu odebírat z druhé fronty a zařazovat zase do nějaké další...

Pro důkaz si poněkud předefinujeme význam slova vzdálenost. Pro nás bude vzdálenost políčka nějaké dvojsložkové číslo X = (x1, x2), kde x1 je počet prokopnutí nutný k dosažení políčka a x2 pak počet políček, kterými k tomuto políčku musíme na daný počet prokopnutí projít. Řekneme, že A < B – políčko A je blíže než políčko B – právě když a1 < b1 ∨ (a1 = b1 ∧ a2 < b2).

Nyní si ukážeme, že náš algoritmus v průběhu celého výpočtu dodrží následující podmínky:

  1. V každé etapě vyřídí všechna políčka s nějakým ohodnocením w.
  2. Na konci každé etapy budou mít všechna nevyřízená políčka větší vzdálenost, než w.
Z těchto podmínek už správnost algoritmu snadno vyplyne – když skončí etapa vyřizující políčka s ohodnocením w a nenalezneme poklad, víme, že jeho vzdálenost je jistě větší, než w (plyne z podmínky 2)). Pokud v nějaké etapě na poklad narazíme, víme, že všechna nevyřízená políčka mají stejnou nebo větší vzdálenost, než w, a tedy se k pokladu rozhodně nemůžeme dostat lépe.

To, že náš algoritmus bude dané podmínky splňovat je poměrně jasné. Pro počáteční etapu podmínky jistě platí (políčko je jen jedno a všechna nově dosažená políčka mají nenulovou vzdálenost). V další etapě vezmeme všechna „nedveřní“ políčka z předchozí etapy. Ta budou jistě mít stejnou vzdálenost. Stejnou vzdálenost navíc mohou mít také dveře zbylé z procházení předchozích oblastí. Ty si ale hlídáme a v případě, že skutečně nějaké dveře stejnou vzdálenost mají, tak je též zpracujeme. První podmínka tedy bude splněna. Druhá ale také, protože pro každou etapu vybíráme w co nejmenší (čtenář jistě sám snadno uváží, že naše fronta bude vlastně setříděna podle vzdálenosti a vybráním jejího prvního prvku tedy vezmeme minimum), a protože všechna nově dosažená políčka budou mít jistě větší vzdálenost než w. Pokud tedy algoritmus skončí, dá správný výsledek. Algoritmus ale jistě skončí po nějakém konečném počtu kroků, protože v každém kroku vyřídí právě jedno políčko a tím se již nikdy nebude zabývat. Tím jest ukázáno.

Časová náročnost tohoto algoritmu je O(N), kde N je počet políček v bludišti, protože se každé políčko zpracovává v konstantním čase maximálně jednou. Paměťová náročnost je též lineární s velikostí bludiště.

Program je ve své podstatě přímou implementací algoritmu. Za zmínku snad stojí pouze to, že frontu na dveře si udržuji jen jednu a pouze si pamatuji, kde v ní končí dveře dosažitelné na N prokopnutí a začínají dveře dosažitelné na N+1 prokopnutí...

Program

Jan Hubička

11-2-4 Alea iacta est (Zadání)

Nejprve se zkusme zamyslet nad tím, jak vypadá pohyb robota. Uvažme nějaký korektní program pro robota – předpokládejme, že příkaz pro pohyb robota (G(a)) se pravidelně střídá s příkazy pro otočení (L, R); to můžeme předpokládat, neboť dva příkazy pro pohyb, které jsou v programu za sebou, lze sloučit beze změny funkčnosti programu v jeden a dva příkazy pro otočení za sebou být nemohou, protože by robot do bodu, kde právě je, položil dvě kostičky. Na tomto místě se sluší poznamenat, že nyní uvažujeme pouze ty případy, kdy zadaných n bodů je navzájem různých. Každý si jistě sám snadno rozmyslí, jak by se řešení a naše úvahy změnily, kdyby tomu tak nebylo.

Směr, do kterého vyrazí robot na začátku svého pohybu, si nazvěme vodorovný. Pohyb robota se skládá z pravidelně se střídajících vodorovných a svislých úseků. Robot dorazí, např. ze svislého směru, do bodu X, zde se otočí doprava nebo doleva o 90 stupňů, pokračuje vodorovně do bodu Y, v něm se znovu otočí a poté opustí vodorovnou přímku (řádek), na které leží body X a Y. Leží-li na tomto řádku ještě nějaké další body, např. A, pak robot někdy dorazí (opět ze svislého směru) do bodu A a tento řádek opět opustí v nějakém dalším bodě. Pohyb robota, tedy body na stejném řádku „spároval“ – jedním na řádek „vstoupil“ a druhým z řádku „odešel“. Na každém řádku (analogicky i sloupci), pokud existuje korektní program pro robota, leží tedy sudý počet bodů. Výjimku může tvořit pouze řádek a sloupec s počátečním bodem. Pokud bude v tomto řádku i sloupci lichý počet bodů, program bute též existovat. V tomto případě totiž skončí robot natočen do svislého směru, čímž bod „ušetříme“. Detailní rozbor tohoto případu necháváme na laskavém řešiteli.

Pokud existuje program pro robota, tak platí, že pro každý zadaný bod X existuje program, že se robot postupující podle něj přesune z počátečního bodu M do bodu X, přičemž se bude otáčet pouze v ostatních zadaných bodech. Stačí totiž uvážit tu počáteční část programu řešícího naši úlohu, která končí otočkou robota v bodě X.

Než přistoupíme k vyřešení zadané úlohy, zaměřme pozornost na dvě chyby, které se často vyskytovaly ve vašich řešeních. V zadání úlohy není řečeno, že se robot může pohybovat pouze rovnoběžně s osou x nebo y; naopak je tam zdůrazněno, že počáteční směr robota, lze určit libovolně a tedy je třeba za „vodorovný“ směr z minulého odstavce postupně volit směry z bodu M do všech zadaných bodů. Řada z Vás poté konstatovala, že tato úloha (pro pevně zvolený „vodorovný“ směr) je hledání hamiltonovské kružnice v grafu s jistými omezujícími podmínkami – vrcholy jsou zadané body, hrany jsou mezi body na stejném řádku nebo sloupci. To, že pro hledání hamiltonovské kružnice v grafu není znám polynomiální algoritmus, však neznamená, že námi zadanou úlohu nelze vyřešit polynomiálně – výše naznačená úvaha pouze znamená, že polynomiální algoritmus pro hledání hamiltonovské kružnice v grafu, by nám (možná) pomohl vyřešit naši úlohu v polynomiálním čase; nikoliv však, že z polynomiálního algoritmu pro naši úlohu se nám podaří sestrojit algoritmus pro hledání hamiltonovské kružnice v obecném grafu, protože ty grafy, které odpovídají rozmístění bodů do roviny, určitě nejsou všechny grafy, které existují, a pouze pro tyto grafy jsme schopni nalézt hamiltonovskou kružnici v polynomiálním čase a to ještě s nějakými omezujícími podmínkami. Naši úlohu lze však převést na hledání eulerovského tahu v grafu, kde vrcholy jsou řádky a sloupce, a vrchol odpovídající řádku je spojen hranou s vrcholem odpovídajícím sloupci, pokud existuje bod na průsečíku příslušného řádku a sloupce; vrcholy odpovídající řádkům, resp. sloupcům, nejsou nikdy spojeny navzájem hranou.

Nyní předpokládejme, že počáteční směr robota máme již zvolen, a chceme rozhodnout o existenci a případně i nalézt program pro robota, který vyhovuje zadání úlohy. Začněme sestrojovat program pro pohyb robota z bodu M „hladově“. Pokud ve směru, do kterého je robot natočen, leží nějaký nenavštívený bod, přidejme do programu příkaz, který přesune robota do tohoto bodu. Pak robota otočme (pokud je to možné) tak, aby se díval směrem k některému z bodů, který dosud nenavštívil. Takto postupujme, dokud je to možné. Skončí-li robot svou pouť v jiném bodě, než v bodě M, potom v řádku, resp. sloupci, ve kterém se měl robot nyní pohybovat, je lichý počet bodů a tedy korektní program pro robota neexistuje. Pokud robot doputoval až do bodu M, rozlišíme 2 případy. Prošel-li robot všemi body, které jsou zadány, nalezli jsme program řešící naši úlohu. V opačném případě, zkusme najít bod Y, který robot nenavštívil a je přitom ve stejném řádku nebo sloupci jako některý z navštívených bodů (ten si označme X). Pokud takový bod Y neexistuje, tak pro žádný z dosud nenavštívených bodů neexistuje program, který by dovedl robota z bodu M do tohoto bodu tak, jak je poznamenáno na konci předminulého odstavce. Tedy opět určitě neexistuje program pro robota, který vyhovuje podmínkám úlohy. V opačném případě existuje výše zmíněná dvojice bodů X a Y. Dosud vytvořený program P pro pohyb robota, pozměňme tak, že robot nejprve vykoná část programu P od návštěvy bodu X, přijde tedy do bodu M, jím projde, a vykoná část programu po návštěvu bodu X, nyní se natočí tak, aby mohl dále pokračovat přes bod Y a program prodlužujeme dále „hladově“. Pokud, již dále nelze postupovat a nevrátili jsme se do bodu Y jsme v řádku nebo sloupci s lichým počtem zadaných bodů a program tedy neexistuje. V opačném případě, nově vytvořenou část programu vložíme do programu P do místa, kde procházíme bodem X. Samozřejmě je potřeba si ještě rozmyslet, že programy půjdou napojit a jak tak učinit, ale to jistě každý zvládne sám.

Nyní přejděme k realizaci výše naznačeného algoritmu. Nejprve načteme souřadnice bodu M a bodů, kterými má robot projít. Body si v rovině posuneme tak, aby bod M byl v počátku souřadnic. Nyní postupně pro každý bod X ze zadaných bodů, otočíme body kolem počátku tak, aby bod X ležel v kladné části x-ové osy. Směr z bodu M do bodu X bude pro nás „vodorovný“. Přepočítané souřadnice bodů setřídíme zvlášť podle x-ové a podle y-ové složky – to nám umožní rychleji rozpoznat, zda dva body leží ve stejném řádku nebo sloupci. V programu ještě k zadaným bodům přidáme bod M, čímž se vyhneme ošetřování okrajových případů v proceduře vytvorplan. Nyní vytvoříme plán cesty robota – pro každý bod určíme, který bod robot navštíví po tomto bodě. Požadujeme navíc, aby první a poslední bod v našem plánu byl bod M. Nejprve sestrojíme nějaký plán z bodu M do bodu M. Pak půjdeme po jednotlivých bodech v tomto plánu a budeme zkoumat, zda některý z nich leží ve stejném řádku nebo sloupci jako některý z dosud nenavštívených bodů. Pokud takový bod neexistuje a robot neprošel všemi zadanými body, program, jak již bylo výše zdůvodněno, nelze sestrojit. Pokud robot prošel všemi zadanými body, máme pro robota plán, jak projít všemi body, a sestavit z něj program je již jednoduché.

Nyní provedeme odhad časové a paměťové složitosti programu. Nechť je na vstupu zadáno n bodů. Program celkem n-krát zvolí vodorovný směr. Pro každou z těchto voleb, přepočítá souřadnice bodů, setřídí je dle jejich souřadnic a pokusí se sestavit program pro robota. K setřídení bodů je třeba čas O(n log n), ostatní části se provedou v lineárním čase vzhledem k n. Celková časová složitost je tedy O(n2 log n), paměťová O(n).

Program

Daniel Kráľ

11-2-5 Mnoho CPŮ, složitosti smrt (Zadání)

1. Hledání minima

Tuto úlohu je možno vyřešit použitím metody Rozděl a panuj, to jest napsáním rekursivního paralelního programu. Myšlenka je velice jednoduchá: minimum v poli najdeme tak, že si pole rozdělíme na poloviny, v každé z nich rekursivním aplikováním téhož algoritmu (ovšem pro obě poloviny najednou!) nalezneme minimum a poté za globání minimum prohlásíme menší z minim částí.

Program zapsaný v paralelním Céčku jako funkce, která dostane pole, levou a pravou hranici úseku v tomto poli a spočte minimum tohoto úseku, vypadá takto:

int min(int x[], int l, int r)
{
  int a, b, m;
  if (l == r)	  /* jednoprvkový úsek */
    return x[l];
  m = (l+r)/2;	  /* střed úseku */
  parallel {  /* obě poloviny najednou */
    a = min(x, l, m);
    b = min(x, m+1, r);
  }
  return (a < b) ? a : b;
}

Časovou složitost algoritmu rozebereme pro jednoduchost pouze pro příklad, že n je mocninou dvojky (jinak bychom museli zohlednit to, že obě „poloviny“ nejsou stejně velké; uvědomte si, že to není na újmu obecnosti, protože pro libovolné jiné n jistě algoritmus vykoná méně práce než pro nejbližší vyšší mocninu dvou). Pro úsek délky jedna provede algoritmus konstantní počet operací, tedy t(1)=c, pro libovolný větší pak provede paralelně dva (stejně dlouhé) výpočty pro poloviny pole plus nějakou konstantní režii navíc: t(n)=t(n/2)+C, tedy také

t(n)=t(n/4)+2C=t(n/8)+3C=… =t(n/2k)+kC.

Pro k= log2 n je tedy t(n/2k)=t(1)=c, proto

t(n)=c+ log2n·C=O(log n).

Paměťovou složitost spočítáme obdobně: pro jednotkovou délku úseku je konstantní, s(1)=s, pro delší úsek potřebujeme pouze místo na zásobníku pro vyvolání funkcí plus místo zabrané každou z nich (tentokráte ovšem dohromady – použitá paměť není paralelním zpracováním nijak ovlivněna):

s(n)=2s(n/2)+S=2(2s(n/4)+S)+S=
=4s(n/4)+3S=… =2ks(n/2k)+(2k-1)S,

pro k= log2n dostaneme

s(n)=2ks+(2k-1)S=ns+(n-1)S=O(n).

2. Převod paralelní → sekvenční výpočet

Jelikož definice paralelního výpočtu nepovoluje vzájemné ovlivňování jednotlivých větví výpočtu, musí být výsledek nutně týž, jako když se provádí jedna po druhé. Proto nahradíme-li všechny bloky parallel bloky normálními, získáme ekvivalentní (i když mnohem pomalejší [až tolikrát, kolik bylo původních větví výpočtu, což může být až exponenciálně mnoho]) sekvenční program. [Analogicky bychom takto mohli z nedeterministického paralelního programu zkonstruovat nedeterministický sekvenční program, ale to po nás nikdo nechtěl.]

3. Převod nedeterministický → paralelní výpočet

Nejprve je třeba uvědomit si, jaké problémy vlastně při tomto převodu mohou nastat:

  1. Časová složitost nedeterministického algoritmu je dána nejkratší úspěšnou větví, případně větví nejdelší, pokud žádná větev není úspěšná. To tedy také znamená, že v úspěšně dokončeném výpočtu mohly existovat nekonečné větve. Tohoto problému se zbavíme tak, že stejně jako v řešení úlohy 11-1-4 přídáme počítadlo omezující délku výpočtu a budeme úlohu opakovaně řešit pro stále rostoucí omezení – tím sice vše kvadraticky zpomalíme, ale polynom na druhou je opět polynom, pročež to nevadí.
  2. Funkce oracle mohla za parametr dostat libovolně velké číslo. Ano, to je chyba v zadání, argumenty této funkce měly být také omezené nějakým polynomem, takže předpokládejme, že opravdu jsou. Navíc vzhledem k tomu, že libovolné polynomiálně velké číslo má polynomem omezený počet bitů, můžeme po vzoru minulé úlohy generovat odpovědi orákula po jednotlivých bitech.

Po vypořádání se s těmito problémy můžeme postupovat velice jednoduše: při každém volání orákula prostě spustíme paralelně dvě větve výpočtu pro obě možné odpovědi a vrátíme true, pokud alespoň jedna z nich vrátila true.

[Analogie s prohledáváním grafu z minulé úlohy opět platí, pouze místo prohledávání do šířky použijeme rekursivní prohledávání do hloubky omezené maximální hloubkou, v němž budeme rekursivní volání paralelizovat stejně jako pří hledání maxima v poli.]

Martin Mareš