Pátá série třicátého osmého ročníku KSP

Celý leták v PDF.

Dostává se k vám páté číslo hlavní kategorie 38. ročníku KSP.

Až si budete venku užívat teplých dnů, nezapomeňte si s sebou přibalit i toto zadání, ve kterém naleznete poslední sadu úloh tohoto ročníku. Získáte dostatečný počet bodů a diplom úspěšného řešitele? Pojedete na Podzimní soustředění? Ať už to vyjde nebo ne, doufáme, že jste si z řešení tohoto ročníku odnesli nové znalosti a zkušenosti a že nepovažujete čas strávený nad úlohami za promarněný.

Odměny & na Matfyz bez přijímaček

• Termín série: 14. června 2026 ve 32:00 (tedy další ráno v 8:00)
• Odevzdávání: elektronicky přes Odevzdávátko
• Jak řešit: viz Návod na teoretické úlohy a Návod na praktické úlohy
• Dotazy ohledně zadání: posílejte na ksp@mff.cuni.cz, nebo se ptejte na Discordu KSP.

Zadání úloh

• 38-5-1: Rozmanitý mrak
• 38-5-2: Garážový výprodej
• 38-5-3: Nespolehlivé autobusy
• 38-5-4: Linuxáci a Windowsáci
• 38-5-S: Hešování řetězců

38-5-1 Rozmanitý mrak (8 bodů)

Jednodimenzionální Kevin jednoho jednodimenzionálního dne zkoumal jednodimenzionální oblohu. Zrovna na ní (směrem doleva) připlul krásný rozmanitý jednodimenzionální mrak. Kevin v něm s nadšením rozpoznával zvířátka. Třeba nalevo rozpoznal kočičku, když si ale odmyslel její hlavičku, viděl tam hada, když zase k tělíčku zvážil přidat i kousek napravo, co vypadal jako hroch, vypadalo to jako kočkopes.

Takových zvířátek viděl Kevin na mraku spoustu. Po chvíli ho ale napadlo, jestli jsou na mraku zvířátka úplně všude? Pomozte Kevinovi zjistit, zda každičký kousek mraku je součástí alespoň jednoho úseku, který vypadá jako zvířátko.

Toto je teoretická úloha. Není nutné ji programovat, odevzdává se pouze slovní popis algoritmu. Více informací zde.

Dostanete kódovaní mraku M jako řetězec D znaků, a seznam kódování N zvířátek Z₁,…,Z_N, každé z nich také jako řetězec znaků. Protože jednodimenzionální vědci zjistili, že existuje právě 26 typů kousku mraku, znaky jsou pro jednoduchost malá písmena anglické abecedy. Vaším úkolem je zjistit, zda je celý mrak pokrytý zvířátky, nebo se to Kevinovi jen zdá.

U řešení se vám jistě bude hodit přečíst si naši kuchařku o hledání v textu. Doporučujeme si ověřit, že neděláte v řešení žádné zbytečné kroky kazící časovou složitost.

38-5-2 Garážový výprodej (10 bodů)

Kevinova kamaráda Prokopa zaujala výhodná nabídka v garážovém výprodeji: „Dva algoritmy za cenu jednoho!“

První nabízený algoritmus má za úkol najít komponenty silné souvislosti v orientovaném grafu. Dostane na vstupu orientovaný graf G a funguje následovně:

1. Sestroj graf G^T s obrácenými hranami.
2. Z ← prázdný zásobník
3. Pro všechny vrcholy v∈G nastav komponenta(v) ←nedefinováno.
4. Pro všechny vrcholy v:
5. Pokud DFS ještě nenavštívilo v:
6. Spusť DFS v G^T z vrcholu v. Při uzavření každého vrcholu jej vlož do Z.
7. Postupně odebíráme vrcholy ze zásobníku Z a pro každý takový vrchol v:
8. Pokud komponenta(v) = nedefinováno:
9. Spusť DFS v G z vrcholu v, přičemž DFS vstupuje jen do vrcholů u s nedefinovanou hodnotou komponenta(u) a tuto hodnotu přepisuje na v.
10. Výstup: komponenta(v) teď každému vrcholu v dává identifikátor jeho komponenty silné souvislosti.

Tento algoritmus skutečně funguje (a můžete si o něm přečíst více v Průvodci labyrintem algoritmů v oddílu 5.9). Má to ale jeden háček: algoritmus jako podproceduru využívá DFS, které prodejce nemá v nabídce. Druhý algoritmus v ceně je proto BFS se zásobníkem. Prodejce tvrdí, „Mám jenom BFS, ale to přece nevadí. Vyměním v něm frontu za zásobník a vznikne DFS, ne?“ Takhle vypadá „DFS“, které se použije v nabízeném algoritmu:

1. Vstup: Graf G a jeho vrchol u.
2. S ← zásobník s jediným prvkem u
3. Označ vrchol u jako navštívený.
4. Dokud je zásobník S neprázdný:
5. Odeber ze S vrchol a označ ho v.
6. Pro všechny vrcholy w, do kterých z v vede hrana:
7. Pokud w ještě není označen jako navštívený:
8. Označ w jako navštívený.
9. Přidej w do S.
10. Uzavření vrcholu v.

Prokop je nadšený, že získá tyhle dva algoritmy v ceně jednoho, ale Kevinovi se to nezdá. Je přesvědčený, že s tímhle falešným „DFS“ algoritmus nemusí najít komponenty silné souvislosti. Chce Prokopovi ukázat, jak zrádný ten algoritmus je, a my mu s tím pomůžeme.

Od toho, v jakém pořadí algoritmus prochází vrcholy (ve čtvrtém řádku prvního algoritmu a v šestém řádku falešného DFS), se odvíjí, zda správně rozdělí graf na komponenty silné souvislosti. Na vstupu dostanete graf a vaším úkolem je najít dvě specifická pořadí vrcholů. První pořadí má tento zrádný algoritmus dovést ke správnému rozdělení grafu na komponenty, druhé pořadí ho má donutit selhat. Slibujeme, že obě pořadí půjde pro naše vstupy najít. Tím určitě Prokopa přesvědčíme, aby si algoritmy nekoupil. Není přece nic zrádnějšího, než chybný algoritmus, který ale za určitých okolností uspěje.

Toto je praktická open-data úloha. V odevzdávátku si necháte vygenerovat vstupy a odevzdáte příslušné výstupy. Záleží jen na vás, jak výstupy vyrobíte.

Formát vstupu:

Na prvním řádku dostanete dvě kladná čísla N a M. Zadaný graf má N vrcholů pojmenovaných 1 až N. Na dalších M řádcích je vyjmenovaných jeho M orientovaných hran.

Formát výstupu:

Na výstup vypište dva řádky. První by měl obsahovat pořadí vrcholů, tedy čísla od 1 do N, oddělená mezerou, na kterém popsaný algoritmus uspěje. Na druhém řádku bychom chtěli mít pořadí, na kterém neuspěje, tedy vrcholy rozdělí do skupin, které nejsou silně souvislé komponenty. Algoritmus přitom s pořadím pracuje ve čtvrtém řádku prvního algoritmu a v šestém řádku falešného „DFS“, kde slouží na seřazení následníků vrcholu v.

3 3
1 2
2 3
3 2

1 2 3
2 1 3

Zadaný graf má dvě komponenty silné souvislosti – {1} a {2, 3}. Když se algoritmus bude řídit prvním pořadím, nejprve „DFS“ v G^T spustí pro vrchol 1. Z toho v G^T nevede žádná hrana, takže bude rovnou uzavřený a vložený do Z. Potom se „DFS“ v G^T spustí pro vrchol 2, čímž se do Z vloží vrcholy 2 a 3.

Algoritmus pak postupně odebírá vrcholy ze Z a pouští na nich „DFS“ v G. První na řadu přijde vrchol 3, ze kterého je dostupný jen vrchol 2, tedy komponenta(3) = komponenta(2) = 3. Potom se ještě spustí „DFS“ pro vrchol 1, čímž se označí komponenta(1) = 1. „DFS“ už se nezavolá pro vrchol 2, protože ten už má označenou komponentu. Vrcholy jsou tak korektně rozdělené na komponentu „1“, která obsahuje vrchol 1, a komponentu „3“, která sestává z vrcholů 2 a 3.

Pro druhé pořadí algoritmus selže, protože vrcholy se do Z vloží v pořadí 2, 3, 1, takže vrchol 1 bude ze Z odebraný jako první, a z něj už „DFS“ přejde i do vrcholů 2 a 3, čímž budou všechny vrcholy nesprávně přiřazeny stejné komponentě „1“.

38-5-3 Nespolehlivé autobusy (13 bodů)

Kevin se vrací domů z noční procházky po svém oblíbeném evropském hlavním městě. Protože už ho bolí nohy, tak k cestě domů plánuje využít místní husté sítě autobusů. Pro zjednodušení orientace v dopravě nedávno dopravní podnik zavedl opatření, že každý spoj bude mít jen dvě zastávky, jednu nástupní a jednu výstupní. Kevin ale ze svých zkušeností ví, že takto pozdě večer existuje pravděpodobnost, že řidič autobusu během přestávky usne a autobus pak nepřijede. Poradíte mu, jak maximalizovat pravděpodobnost, že se Kevin do půlnoci dostane domů?

Kevin má k dispozici tabulku jízdních řádů, kde je pro každý spoj uvedeno místo a čas odjezdu a místo a čas příjezdu. Přirozeně je čas příjezdu vždy ostře větší než čas odjezdu a ze zastávky je v jeden čas naplánován vždy nejvýše jeden odjezd. Ke každému autobusu navíc na základě svých zkušeností Kevin dopsal, s jakou pravděpodobností pojede. To, jestli nějaký autobus pojede, nemá žádný vliv na další autobusy – formálně jsou tedy příjezdy autobusu nezávislé jevy. Autobusy s bdělými řidiči jezdí na vteřinu přesně, takže Kevin zjistí, zda autobus jede nebo ne, přesně v okamžiku plánovaného odjezdu.

Vaším úkolem je navrhnout interaktivní algoritmus, který Kevinovi bude radit, jak se má chovat. Nejprve do něj Kevin zadá jízdní řády s pravděpodobnostmi, název zastávky, na které začíná, a název zastávky na které kde chce skončit. Váš program by pak měl Kevinovi říci, kterým spojem má jet jako první. Kevin pak počká do jeho plánovaného příjedu a do programu zadá, že se autobusem svezl, nebo že autobus nepřijel. Program pak vypíše další spoj, kterým má Kevin jet, a tak dále. Jakmile Kevin dorazí domů, nebo začne být nemožné, aby dorazil do půlnoci, tak to má program zahlásit a skončit.

Popis jízdního řádu by mohl vypadat například takto:

Spoj 001: z A v 19:00 do B v 19:10 (60 %)
Spoj 002: z B v 19:15 do Z v 20:00 (10 %)
Spoj 003: z B v 19:20 do A v 19:30 (100 %)
Spoj 004: z A v 19:45 do Z v 20:10 (80 %)
Chci z A do Z, je 18:55.

V ukázkovém jízdním řádu existuje spoj 004 z A do Z, co jede s vysokou pravděpodobností 80 %. Vyplatí se ale nejprve zkusit jet spojem 001 a 002, což má sice pravděpodobnost úspěchu jen 6 %, ale pokud spoj 002 nepřijede, tak se můžeme jistě autobusem 003 vrátit zpátky do A a spoj 004 použít stejně. Tato strategie bude mít pravděpodobnost úspěchu 81,2 %.

Interakce Kevina s programem by pak tedy mohla vypadat například takto:

Jeď spojem 001.
> Jedu.
Jeď spojem 002.
> Nepřijel.
Jeď spojem 003.
> Jedu.
Jeď spojem 004.
> Nepřijel.
Máš smůlu, musíš pěšky.

Toto je teoretická úloha. Není nutné ji programovat, odevzdává se pouze slovní popis algoritmu. Více informací zde.

Ve svém popisu algoritmu můžete předpokládat, že s reálnými čísly, například s pravděpodobnostmi, můžete provádět aritmetické operace s neomezenou přesností v konstantním čase. Můžete také předpokládat, že zastávky a časy dostanete zadané jako přirozená čísla. Časovou složitost určujte vzhledem k počtu spojů a počítejte ji za celý běh programu dohromady.

38-5-4 Linuxáci a Windowsáci (14 bodů)

V hroší říši v nějakém paralelním vesmíru se právě koná soustředění hrochů v hrošení. Tato událost je veliká – každý rok se tam schází tisíce hrochů a poměřují se v této královské disciplíně. Nejlepších výsledků lze dosáhnout tak, že si hroši napíšou program, který jim s hrošením co nejvíce pomůže – proto každý hroch potřebuje svůj notebook. Přestože tento požadavek byl v pozvánce silně zdůrazněn, našli se tací, kteří si žádný notebook nevzali. Orgové však s tímto již dopředu počítali a mají velké množství notebooků v záloze.

Máme tu však jistý zádrhel. Víme, že je spousta účastníků, kteří mají velmi rádi svá okna nebo velmi rádi své tučňáky, a to tak moc, že pokud jejich kamarád nemá stejný operační systém jako oni, začnou na něj nadávat, že používá systém, který špehuje a využívá uživatele, nebo že má systém, na kterém nespustí software od Adobe. Orgové tedy chtějí rozdat notebooky tak, aby celkem bylo mezi kamarády co nejméně konfliktů. Každému hrochu, který si nevzal notebook, je jedno, co dostane za systém, hlavně že má notebook.

Zadání tedy zní: máme neorientovaný graf tvořený N hrochy a M kamarádskými vazbami mezi nimi. Každý hroch buď má notebook s Linuxem, s Windows, nebo si notebook zapomněl. Vaším úkolem je přiřadit všem hrochům bez notebooku Linux nebo Windows tak, abychom minimalizovali celkový počet hran mezi hrochy s Windows a Linuxem.

Toto je praktická open-data úloha. V odevzdávátku si necháte vygenerovat vstupy a odevzdáte příslušné výstupy. Záleží jen na vás, jak výstupy vyrobíte.

Formát vstupu:

Na první řádce dostanete číslo N. Na dalším řádku pak bude N znaků, kde i-tý znak buď značí, že i-tý hroch má buď Linux (znak L), Windows (znak W), nebo je bez notebooku (znak B). Na dalším řádku pak dostanete číslo M a pod ním M řádků. Na každém z těchto řádků pak máme čísla u_i a v_i, která značí, že hroši u_i a v_i jsou přátelé (hrochy počítáme od nuly).

Formát výstupu:

Na výstup vraťte N znaků, kde i-tý znak značí, zda i-tý hroch má notebook s Linuxem či Windows.

10
WWLBLWBLLL
15
3 8
3 4
5 8
0 9
2 3
2 9
0 2
1 7
3 9
6 7
4 8
3 6
2 5
4 7
3 5

WWLLLWLLLL

V ukázkovém vstupu jsou hroši 3 a 6 bez notebooku. Pokud oběma dáme notebook s Linuxem, budeme celkem mít 6 konfliktů, což je optimální.

38-5-S Hešování řetězců (15 bodů)

V minulém dílu seriálu jsme studovali univerzální systémy hešovacích funkcí pro čísla. Teď si ukážeme, jak hešovat posloupnosti čísel a řetězce znaků a co se s tím dá vyvádět zajímavého.

Polynomiální hešování

Nejdřív budeme hešovat uspořádané k-tice (x₁, …, x_k). Jejich složky budou buďto čísla, nebo znaky, které si také převedeme na čísla. Každopádně je můžeme považovat za prvky nějakého konečného tělesa Z_p pro dost velké prvočíslo p.

Pořídíme si systém hešovacích funkcí {h_a | a ∈Z_p}, které vypadají následovně. Vše počítáme v Z_p, tedy modulo p. Parametr a budeme jako obvykle volit náhodně ze Z_p.

Sumu můžeme rozepsat takto:

To je polynom v proměnné a, jehož koeficienty jsou složky k-tice. Proto se celému systému říká polynomiální hešování.

Uvažujme, jestli je polynomiální hešování c-univerzální pro nějaké c. Bude se nám hodit standardní věta z algebry (kterou nebudeme dokazovat):

Věta: Nenulový polynom stupně d nad libovolným tělesem má nejvýše d kořenů.

Co tato věta znamená? Stupeň polynomu je nejvyšší mocnina proměnné, která se v něm vyskytuje. Nenulový znamená, že aspoň jeden koeficient není nula. A kořen polynomu p(t) je takové t, pro něž p(t)=0.

Definice c-univerzality po nás chce, abychom pro každé dvě různé k-tice (x₁, …, x_k) a (y₁, …, y_k) omezili pravděpodobnost toho, že pro náhodné a nastane kolize

Do toho dosadíme definici h_a a získáme:

což po převedení pravé strany nalevo dává:

Levá strana je polynom v proměnné a, který má stupeň maximálně k-1 (může být nižší, pokud x_k = y_k). Jelikož aspoň pro jedno i je x_i různé od y_i, polynom není nulový. Kořeny polynomu jsou ta a, pro která rovnost platí, a podle věty jich je nejvýše k-1. Parametr a ovšem volíme náhodně z p-prvkového tělesa. Proto pravděpodobnost, že nastane kolize, je nejvýše (k-1)/p.

Zjistili jsme tedy, že polynomiální hešování je c-univerzální pro c=k-1. Většinou ho budeme prohlašovat za k-univerzální, což je slabší vlastnost, ale lépe se s ní pracuje.

To nám dává použitelné hešovací funkce (alespoň pokud k není moc velké), ale pozor, že časová složitost výpočtu funkce už není konstanta, nýbrž O(k).

Ještě dodejme, že praktické implementace často místo modulo prvočíslo počítají modulo nějaká mocnina dvojky (třeba 2^b, pokud pracujeme s b-bitovými čísly). Tehdy se nejedná o těleso, takže nemůžeme využívat věty o polynomech v tělese, a díky tomu zaručit univerzalitu. Nicméně experimenty ukazují, že se takové funkce stále chovají dobře a jsou rychlejší.

Hešování řetězců

Co kdybychom hešovali posloupnosti nebo řetězce, které nemají pevnou délku k? Pokud víme, že všechny délky budou shora omezené nějakým maximem M, můžeme všechny řetězce doplnit „mezerami“ na délku M a hešovat polynomiálně. Mezerou myslíme hodnotu, která se v řetězcích nevyskytuje.

Tak získáme M-univerzální hešování, ale bohužel je dost pomalé: i kratičké řetězce hešujeme v čase O(M). Pomoc je snadná: pro mezeru si vybereme číslo 0, takže členy polynomů s mezerami můžeme vynechat. Pak už hešování k-prvkového řetězce potrvá O(k).

Úkol 1 [3b]

Představte si, že znáte h_a(α) pro nějaký řetězec α. Ukažte, jak v konstantním čase spočítat h_a(α') pro řetězce α', které vzniknou z α přidáním nebo ubráním jednoho znaku na začátku nebo na konci. Nezapomeňte, že h_a se počítá modulo p.

Rabinův-Karpův algoritmus

Na polynomiálních hešovacích funkcích je založený pěkný algoritmus na vyhledávání v textu. Mějme řetězec σ (seno), ve kterém chceme najít všechny výskyty řetězce ι (jehla) jako souvislý podřetězec. Označme J délku jehly a S délku sena.

Vezmeme hešovací funkci h_a v tělese Z_p pro dost velké p a náhodné a∈Z_p. Spočítáme si heš jehly, pojedeme po seně „okénkem“ délky J a budeme přepočítávat heš okénka. Z předchozího úkolu plyne, že se při posunutí okénka o znak doprava dá jeho heš přepočítat v konstantním čase. A kdykoliv se heš okénka rovná heši jehly, znamená to buďto nalezený výskyt, nebo kolizi hešovací funkce (těch snad nebude mnoho). Abychom tyto dva případy rozlišili, porovnáme obsah okénka s jehlou znak po znaku.

Úkol 2 [2b]

Spočítejte průměrnou časovou složitost algoritmu v závislosti na délce jehly J, délce sena S, počtu výskytů V a prvočíslu p. Jak byste nastavili p, aby čas vyplýtvaný na kolizích byl zanedbatelný?

Izomorfismus binárních stromů

Uvažujme čistě binární stromy. To jsou zakořeněné stromy, v nichž každý vnitřní vrchol (takový, co není list) má právě dvě děti. Otočení vnitřního vrcholu nazveme operaci, která prohodí jeho děti včetně jejich podstromů (podstromem myslíme dítě se všemi jeho potomky). Dva stromy jsou izomorfní, pokud jeden můžeme z druhého vyrobit nějakou posloupností otočení vrcholů.

Například na následujícím obrázku je první strom izomorfní s druhým, ale ne s třetím:

Hledejme algoritmus, který pro dva stromy rozhodne, zda jsou izomorfní. Postupně všem vrcholům v obou stromů přiřadíme kódy. To budou nějaká čísla k(v). Bude platit, že dva vrcholy mají stejný kód právě tehdy, když jejich podstromy jsou izomorfní. Izomorfismus celých stromů tedy půjde rozhodnout porovnáním kódů kořenů.

Nejprve pro všechny vrcholy spočítáme výšky jejich podstromů. To zvládneme prohledáním obou stromů do hloubky. Kdykoliv budeme opouštět vrchol, přidělíme mu výšku. Je-li to list, výška bude nulová. Vnitřnímu vrcholu přidělíme o 1 víc, než je maximum z výšek dětí. Celé prohledání zvládneme v čase O(n), kde n je celkový počet vrcholů v obou stromech.

Vrcholy podle výšek rozdělíme na hladiny a v tomto pořadí jim budeme přidělovat kódy. Listům (vrcholům výšky 0) přidělíme všem stejný kód. Když už máme zakódované vrcholy výšek 0 až h-1, můžeme snadno zakódovat vrcholy výšky h.

Těm přidělíme nové kódy (vrcholy různých výšek nemohou nikdy mít izomorfní podstromy). Označme levé a pravé dítě vrcholu x jako ℓ(x) a p(x) a příslušné podstromy L(x) a P(x) Pak dva vrcholy u a v mají dostat stejný kód, pokud buď L(x) je izomorfní s L(y) a P(x) s P(y), nebo „křížem“ L(x) s P(y) a P(x) s L(y). Jelikož děti vrcholu x mají menší výšku než x, už známe jejich kódy, tedy stačí porovnat neuspořádané dvojice { k(ℓ(x)), k(p(x)) } a { k(ℓ(y)), k(p(y)) }.

Chceme tedy vzít všechny vrcholy výšky h, každému z nich přiřadit neuspořádanou dvojici kódů dětí, a každé skupině vrcholů se stejnou dvojicí přidělit jeden nový kód. To převedeme na porovnání uspořádaných dvojic tak, že vždy zapíšeme nejdřív menší z kódů dětí a pak ten větší. Jelikož nechceme porovnávat každou dvojici s každou, nabízí se následující možnosti:

První možnost: Kódy setřídíme lexikograficky. Tím se nám dostanou stejné dvojice k sobě, takže skupiny stejných dvojic nalezneme snadno. To potrvá O(n_h log n_h), kde n_h≤ n je počet vrcholů výšky h. V součtu přes všechny hladiny pak O(n log n).

Druhá možnost: Pořídíme si datovou strukturu, jež si bude pamatovat dvojice, kterým už jsme přiřadili kód. A pokaždé, když potkáme nový vrchol, vyhledáme jeho dvojici v datové struktuře a buď použijeme známý kód, nebo přidělíme nový a zaznamenáme ho do datové struktury. Pokud datová struktura bude vyhledávací strom, budou operace s ní trvat O(log n), a proto kódování všech vrcholů dohromady potrvá O(n log n).

Třetí možnost: Jako datovou strukturu použijeme hešovací tabulku. Tehdy bude mít jedna operace průměrnou složitost O(1) a celý algoritmus průměrně O(n).

Čtvrtá možnost by byla použít šikovně přihrádkové třídění. Tím by se dala dosáhnout časová složitost celého algoritmu O(n) v nejhorším případě.

Raději prozkoumáme pátou možnost: obzvláště jednoduchý pravděpodobnostní algoritmus. Místo datové struktury budeme kódy přiřazovat hešovací funkcí h(k₁,k₂), které dáme kódy dětí k₁ a k₂ a její výsledek prohlásíme za kód rodiče. Tehdy bude pořád platit, že izomorfní stromy dostanou stejný kód, ale kolize mohou způsobit, že stejný kód občas dostanou i neizomorfní stromy.

Úkol 3 [3b]

Vyberte pro pravděpodobnostní algoritmus vhodnou hešovací funkci, ideálně z nějakého univerzálního systému nad tělesem Z_p pro vhodné p. Jakou časovou složitost bude mít algoritmus? Jaká bude pravděpodobnost, že selže, tedy že neizomorfním stromům přiřadí stejný kód? Jak byste zvolili p tak, aby pravděpodobnost selhání klesla pod zadané ε?

Úkol 4 [2b]

Předpokládejme, že náš pravděpodobnostní algoritmus doběhl a oběma zadaným stromům vyšly stejné kódy kořenů. Vymyslete, jak v čase O(n) pomocí spočítaných hešů buď zjistit, že skutečně jsou izomorfní, nebo že došlo ke kolizi (aniž bychom používali celý komplikovaný deterministický algoritmus na izomorfismus). Co kdybychom v případě, že izomorfní nebudou, algoritmus znovu spustili? To už by nám dalo spolehlivý algoritmus. Jaká by byla jeho průměrná časová složitost?

Úkol 5 [2b]

Navrhněte, jak přidělování kódů hešováním rozšířit na stromy s libovolným počtem dětí. Tehdy operace otočení vrcholu bude moci libovolně přeházet pořadí dětí. Snažte se dosáhnout stejné průměrné složitosti a podobně malé pravděpodobnosti chyby. Tentokrát můžete předpokládat, že máte k dispozici dokonale náhodné hešovací funkce do množiny {0, …, m-1} pro jakékoliv m (nejvýše polynomiálně velké).

Mezigalaktická kandidátka

Na závěr seriálu si vyzkoušíme sílu pravděpodobnostních algoritmů na úloze 36-1-X1 (Mezigalaktická kandidátka). Přečtěte si zadání a prvních část vzorového řešení, zastavte se před nadpisem „Rozděl a panuj“.

Úkol 6 [3b]

Ukažte, jak k-složkové vektory kódovat tak, aby stejné kódy skoro vždy odpovídaly stejným vektorům a jedním kódem jste trávili čas jen O(1). Na tom založte pravděpodobnostní algoritmus, který poběží v průměrném čase O(n) a vydá vždy správný výsledek.

Závěrem

Tím končí náš pětidílný výlet do říše pravděpodobnostních algoritmů. Viděli jsme, že tyto algoritmy dokáží být v mnoha případech mnohem jednodušší než jejich determinističtí příbuzní. Ale jednoduchost bývá vykoupena tím, že algoritmy jsou rychlé pouze v průměru, nebo dokonce nemusí být úplně spolehlivé.

Dalo by se pokračovat mnoha dalšími tématy, třeba treapy, což jsou pravděpodobnostní vyhledávací stromy (viz kuchařka nebo kapitola 11.6 v Průvodci). Ale to už je jiný příběh a ten si budeme vyprávět zase někdy jindy.

Martin „Medvěd“ Mareš