Přímé procvičení vyložených algoritmů

  1. Graf na následujícím obrázku projděte pomocí průchodu do hloubky ($DFS$). Pokud si v některém kroku můžete vybrat z několika vrcholů, tak si vždy vyberte ten abecedně nejmenší z nich.
    1. Rozdělte hrany na stromové a zpětné.
    2. U každého vrcholu $v$ spočítejte časy příchodu a odchodu — hodnoty $\ARRAY{in}{v}$ a $\ARRAY{out}{v}$.
    3. Najděte $2$-souvislé komponenty grafu.
    4. Pro každý vrchol $v$ spočítejte hodnotu $\ARRAY{LOW}{v}$.

  2. Oba orientované grafy na následujících obrázcích projděte pomocí průchodu do hloubky ($DFS$). Pokud si v některém kroku můžete vybrat z několika vrcholů, tak si vždy vyberte ten abecedně nejmenší z nich.
    1. Rozdělte hrany na stromové a zpětné, příčné a dopředné.
    2. U každého vrcholu $v$ spočítejte časy příchodu a odchodu — hodnoty $\ARRAY{in}{v}$ a $\ARRAY{out}{v}$.
    3. Najděte topologické uspořádání každého z grafů.
    4. Vyznačte, které vrcholy jsou zdroje a které stoky.
    5. Najděte silně souvislé komponenty každého z grafů.
    6. Vyznačte, které silně souvislé komponenty jsou zdrojové a které stokové.

Průchod grafu do šířky

  1. (Cesta tunelem)
    Rodina tvořená tatínkem, maminkou, dcerou a synem chce projít tunelem. Tatínek projde tunelem za jednu minutu, maminka za dvě, syn za čtyři a dcera za pět. Problém je v tom, že v tunelu je hrozná tma a jejich svíčka vydrží hořet pouze dvanáct minut. Úzkým tunelem mohou procházet naráz nejvýše dva lidé a v žádném případě nesmí jít tunelem nikdo bez svíčky. Poradíte rodině, jak mají tunelem projít?
  2. (Přelévání tekutin)
    Máme $3$ nádoby o různých objemech. Žádná nádoba na sobě nemá stupnici a nádoby mají dokonce tak roztodivné tvary, že nám znemožňují odhadování množství vody v nich. Stále ale může naměřit i jiné množství tekutiny. Můžeme přelévat obsah jedné nádoby do druhé tak dlouho, dokud nepřelijeme všechno nebo dokud se druhá nádoba nezaplní. Jaký je nejmenší počet přelití, abychom vyřešili následující úlohy? Ve všech variantách je na počátku největší nádoba plná. 

    1. Máme $3$ nádoby o objemech $7$l, $5$l a $3$l. Chceme naměřit $1$ litr.
    2. Máme $3$ nádoby o objemech $7$l, $4$l a $3$l. Přeléváním se chceme dostat do stavu, kdy je v jedné nádobě $3$l a ve zbylých dvou po $2$ litrech.
    3. Máme $3$ nádoby o objemech $8$l, $5$l a $3$l. Přeléváním se chceme dostat do stavu, kdy je počáteční množství rozděleno na dva stejné díly.
  3. (Nejkratší cesta)
    1. V neohodnoceném grafu $G$ najděte nejkratší cestu z vrcholu $s$ (start) do vrcholu $c$ (cíl).
    2. Všechny hrany v grafu $G$ mají délku $1$ nebo $2$. Najděte nejkratší cestu z vrcholu $s$ (start) do vrcholu $c$ (cíl).
    3. Dokázali byste řešení zobecnit i pro grafy s ohodnocením hran $1$ až $k$? Zajímá nás lepší řešení, než pomocí Dijkstrova algoritmu. Chtěli bychom najít řešení v čase $\OO(km+n)$.
  4. (Cesta kulhavého koně)
    Náš šachový kůň kulhá. To znamená, že v sudých tazích provede krok jako šachový kůň a v lichých tazích provede krok jako šachový král. Zjistěte, na kolik nejméně kroků se dostane kulhavý kůň z políčka A1 na políčko H8. Až to zjistíte, tak úlohu vyřešte obecně pro libovolné počáteční a cílové políčko.
  5. (Bludiště)
    Pomocí matice velikosti $n\times m$ máte zadáno bludiště. X značí zeď a nula volný prostor. Na okraji matice jsou všude zdi, takže jde o uzavřený systém místností a chodeb. V matici se vyskytují i znaky \$=poklad a S=místo, kde se zrovna nacházíte. Zjistěte, zda se můžete dostat k pokladu. Předpokládejte, že nejste bílá paní, která by mohla procházet přes zdi. 

    $$
    \begin{array}{rrrrrrrrr}
    X & X & X & X & X & X & X & X & X \\
    X & S & 0 & 0 & X & 0 & 0 & 0 & X \\
    X & 0 & X & 0 & X & 0 & X & 0 & X \\
    X & 0 & 0 & 0 & 0 & 0 & X & 0 & X \\
    X & 0 & 0 & 0 & X & 0 & X & \$ & X \\
    X & X & X & X & X & X & X & X & X \\
    \end{array}
    $$

  6. (Bludiště se dveřmi)
    Máte zadané bludiště jako v předchozí úloze. Navíc se ale v bludišti vyskytují znaky D jako dveře. Dveře jsou ocelové a dají se otevřít pouze dynamitem. Nejste bílá paní, ale jste lupiči, co se chtějí vloupat do sejfu a vykrást banku. Podařilo se vám ukořistit plán sejfu. Pro hladký a bezpečný průběh akce se chcete dostat k penězům na co nejmenší počet kroků, ale hlavně tak, abyste museli odbouchnout co nejméně dveří. Jednou odbouchnutí dveří trvá nesrovnatelně déle než libovolný počet kroků v sejfu. Navíc nadělá ohromný hluk. Vaším úkolem je najít pro lupiče posloupnost pohybů vlevo, vpravo, nahoru, dolů tak, aby se dostali co nejrychleji k penězům. Lupiči už sami pochopí, že když mají projít dveřmi, tak je mají odprásknout.
  7. (Průjezd městem)
    Máte zadaný plán města podobně jako v předchozích úlohách, tj. pomocí matice. Tentokrát jsou v něm pouze silnice široké jeden čtvereček a křižovatky. Vaším úkolem je najít cestu ze startu do cíle (čtverečky označené S a C). Zdá se vám to jednoduché? Tak zkuste najít cestu ze startu do cíle s dodržováním místních dopravních předpisů. V tomto městě je zakázáno na libovolné křižovatce odbočovat vpravo. Vpravo se ale můžete dostat například tak, že projedete rovně přes křižovatku a objedete jeden blok (třikrát zatočíte vlevo).
  8. (Theseus a Minotaurus)
    Zahrajeme si hru ve dvourozměrném bludišti $n\times m$ polí. V bludišti se (samozřejmě kromě zdí, ty se vyskytují v každém pořádném bludišti) nachází Theseus a Minotaurus. Vy budete ovládat Thesea a budete se snažit dostat z bludiště ven, čili dostat se na hranici bludiště a následujícím krokem z bludiště utéct. Ovšem nikdy nesmíte narazit na Minotaura, sic bídně zhynete. Na Minotaura narazíte, pokud s ním sdílíte políčko. 

    Jeden tah probíhá následovně: nejprve se hýbe Minotaurus a táhne $k$-krát následujícím způsobem. Pokud nejsou postavy Minotaura a Thesea ve stejném sloupci, chce se Minotaurus pohnout o jedno políčko vlevo nebo vpravo, aby se Theseovi přiblížil. Pokud mu v tom nebrání zeď, skutečně se tam posune. Pokud nejsou obě postavy na stejném řádku bludiště, chce se Minotaurus pohnout nahoru či dolů opět směrem k Theseovi. Opět se na zvolené políčko Minotaurus přesune jen tehdy, není-li tam zeď. V jednom kroku provádí Minotaurus tyto pohyby v zadaném pořadí a může provést oba dva, čili se může dostat na jedno z okolních osmi políček. Po $k$ takovýchto krocích Minotaura se hýbe Theseus, a to na jedno ze čtyř okolních volných polí. Takto se oba střídají na tahu, dokud buď Theseus neuteče z bludiště, nebo dokud Minotaurus nedohoní Thesea. Vaším úkolem bude najít pro Thesea nejkratší posloupnost pohybů vlevo, vpravo, nahoru, dolů, aby se dostal bezpečně z bludiště, případně říci, že to není možné.

  9. (Loydova devítka)
    Napište program, který zjistí, jestli jde Loydova devítka poskládat a řekne vám, jak šoupat čtverečky tak, abyste ji poskládali na nejmenší počet tahů.

Průchod grafu do hloubky

  1. (Obrácení hran)
    Orientovaný graf $G^R=(V,E^R)$ vznikne z orientovaného grafu $G=(V,E)$ obrácením hran. Tedy $E^R=\{ xy \,|\, yx \in E \}$. Navrhněte algoritmus, který spočítá reprezentaci grafu $G^R$ v lineárním čase $\OO(n+m)$. Úlohu řešte pro reprezentaci seznamem sousedů. Jak by to bylo pro reprezentaci maticí incidence?
  2. (Vstupní a výstupní stupně)
    Dostaneme orientovaný graf $G=(V,E)$ reprezentovaný seznamem sousedů. Stupeň vrcholu $v$ (značíme $\deg v$) je počet hran grafu $G$, které do vrcholu $v$ vedou a nebo které z vrcholu $v$ vychází. Vstupní stupeň vrcholu $v$ (značíme $\deg^+ v$) je počet hran grafu $G$, které do vrcholu $v$ vstupují. Výstupní stupeň vrcholu $v$ (značíme $\deg^- v$) je počet hran grafu $G$, které z vrcholu $v$ vychází. Platí $\deg^+ v + \deg^- v = \deg v$. 

    1. Dokažte, že $\sum_{v\in V} \deg v = 2|E|$.
    2. S využitím části (a) dokažte, že počet vrcholů s lichým stupněm musí být sudé číslo.
    3. Navrhněte algoritmus, který v lineárním čase spočítá vstupní a výstupní stupně všech vrcholů.
  3. (Čtverce stupňů sousedů)
    Dostaneme neorientovaný graf $G=(V,E)$ reprezentovaný seznamem sousedů. Definujeme $\ARRAY{dvadeg}{v} := \sum_{u\in \ARRAY{Sousedi}{v}} (\deg v)^2 $. Navrhněte lineární algoritmus, který pro všechny vrcholy spočítá $\ARRAY{dvadeg}{\cdot}$ v čase $\OO(n+m)$.
  4. (Bipartitní graf)
    Graf $G=(V,E)$ je bipartitní,pokud jeho vrcholy můžeme rozdělit na dvě disjunktní množiny $V_1$, $V_2$ (tedy $V_1\cup V_2 = V$ a $V_1 \cap V_2 =\emptyset$) tak, aby všechny hrany vedly z jedné množiny do druhé. (Graf nemůže obsahovat hranu s oběma konci ve stejné množině.) 

    1. Navrhněte lineární algoritmus, který dostane graf $G$ a zjistí, jestli je bipartitní.
    2. Navrhněte algoritmus, který v lineárním čase zjistí, jestli graf obsahuje lichý cyklus (cyklus liché délky).
    3. Pokud graf neobsahuje lichý cyklus, dokážete ho obarvit $2$ barvami? Obarvení grafu $2$ barvami je obarvení jeho vrcholů $2$ barvami takové, že každé dva vrcholy spojené hranou mají různou barvu. Je každý takový graf bipartitní?
  5. (Vyhodnocení stromu)
    Dostanete binární zakořeněný strom, jehož každý vrchol $v$ obsahuje číslo $\ARRAY{z}{v}$. Hodnota $\ARRAY{zmax}{v}$ je definovaná jako maximum z hodnot $\ARRAY{z}{w}$, pro všechny potomky $w$ vrcholu $v$. Spočítejte celé pole $\ARRAY{zmax}{\cdot}$ v lineárním čase.
  6. (Následník ve stromě)
    Dostaneme zakořeněný strom. Vrchol $u$ je následníkem vrcholu $v$, pokud $v$ leží na cestě z kořene do $u$. Postupně budete dostávat dvojice vrcholů $x$, $y$ a chtěli bychom co nejrychleji odpovídat na otázku, jestli je $x$ následníkem $y$? 

    Pokud si můžete dovolit předzpracování v čase $\OO(n)$, zvládnete odpovídat v konstantním čase?

  7. (Eulerovský tah)
    Tah v grafu $G$ je posloupnost $v_0$, $e_0$, $v_1$, $e_1$,\dots $v_n$ taková, že $e_i=\{v_i, v_{i+1}\}$ a $v_i \not= v_j$ pro všechna $i$, $j$ (neboli každé $2$ po sobě jdoucí hrany mají společný vrchol a vrcholy se v posloupnosti neopakují). Uzavřený Eulerovký tah je tah, který projde všechny hrany grafu a skončí ve stejném vrcholu, ve kterém začal. Otevřený Eulerovský tahprojde všechny hrany grafu, ale může končit na jiném místě, než začal. 

    1. Navrhněte algoritmus, který v grafu $G$ najde uzavřený Eulerovský tah a vypíše ho. Případně odpovězte, že takový tah neexistuje.
    2. Navrhněte algoritmus, který v grafu $G$ najde otevřený Eulerovský tah a vypíše ho. Případně odpovězte, že takový tah neexistuje.
    3. Následující rostlinky nakreslete jedním tahem. Křížení čar považujte za vrcholy.
  8. Navrhněte algoritmus, který v grafu $G$ najde libovolnou kostru, případně odpovězte, že neexistuje. Zkuste vymyslet velice jednoduché řešení pracující v čase $\OO(n+m)$.
  9. Navrhněte algoritmus, který pro graf $G$ vypíše jeho komponenty souvislosti.
  10. Navrhněte algoritmus, který pro graf $G$ vypíše jeho $2$-souvislé komponenty.
  11. Navrhněte algoritmus, který pro orientovaný graf $G$ vypíše jeho silně souvislé komponenty.
  12. (Topologické uspořádání)
    V poušti na Sahaře byly nalezeny zbytky knihovny nějaké dávné civilizace. Civilizace znala písmo a předpokládá se, že měla i abecedu (uspořádání písmenek). Vědci se domnívají, že nalezené spisy byly v knihovně seřazeny lexikograficky.1 Dostanete názvy spisů, které se zachovaly a to v pořadí jak byly poskládány na poličce. Názvy spisů jsou přepsané tak, že si každý znak označíme jedním písmenkem naší abecedy. 

    Například pro českou knihovnu byste dostali seznam: “Alenka v říši divů”, “Alexandr Veliký”, “Baron Prášil”, “Broučci” “Malý princ”, “Medvídek Pů”. Ze seznamu můžete vyvodit, že v české abecedě je ‚A‘ před ‚B‘, ale také ‚n‘ před ‚x‘.

    Podle názvu spisů, které dostanete, zkuste potvrdit nebo vyvrátit teorii o tom, že saharská civilizace měla abecedu. Pokud teorii potvrdíte, tak vypište jednu možnost, jak mohla jejich abeceda vypadat.

  13. (Poznámka k topologickému uspořádání)
    Navrhněte algoritmus, který dostane neorientovaný graf, a zjistí, jestli graf obsahuje kružnici. Zkuste vymyslet řešení, které běží v čase $\OO(n)$ (tedy je nezávislé na počtu hran).
  14. (Topologické uspořádání)
    Dokažte nebo vyvraťte: Pokud orientovaný graf obsahuje orientované cykly, tak procedura pro topologické uspořádání nalezne uspořádání vrcholů, které minimalizuje počet “špatných” hran, vedoucích zprava do leva.
  15. (Polosouvislé grafy)
    Orientovaný graf $G=(V,E)$ je polosouvislý, pokud pro každé dva vrcholy $u,v\in V$ existuje orientovaná cesta z $u$ do $v$ nebo orientovaná cesta z $v$ do $u$. Navrhněte algoritmus, který zjistí, jestli je graf $G$ polosouvislý. Dokažte jeho správnost a určete jeho časovou složitost.
  16. (Jednoznačně souvislé grafy)
    Orientovaný graf $G=(V,E)$ je jednoznačně souvislý, pokud pro každé dva vrcholy $u,v\in V$ existuje právě jedna orientovaná cesta z $u$ do $v$ a právě jedna orientovaná cesta z $v$ do $u$. Navrhněte algoritmus, který zjistí, jestli je graf $G$ jednoznačně souvislý. Dokažte jeho správnost a určete jeho časovou složitost.
  17. (Cyklus obsahující hranu $e$)
    Dostanete neorientovaný graf $G$ s vyznačenou hranou $e$. Navrhněte algoritmus pracující v lineárním čase, který zjistí, jestli v grafu $G$ existuje cyklus obsahující hranu $e$.
  18. Navrhněte efektivní algoritmus, který dostane orientovaný graf $G=(V,E)$ a zjistí, jestli v $G$ existuje vrchol $v\in V$, ze kterého jsou všechny ostatní vrcholy dosažitelné.
  19. Navrhněte efektivní algoritmus, který dostane orientovaný acyklický graf $G=(V,E)$ a dvojici vrcholů $s$, $c$ a vrátí počet různých cest vedoucích z $s$ do $c$.
  20. Dostanete orientovaný acyklický graf. Navrhněte efektivní algoritmus, který zjistí, jestli v grafu existuje cesta, která navštíví každý vrchol právě jednou.
  21. Dostanete orientovaný acyklický graf. Navrhněte efektivní algoritmus, který spočítá délku nejdelší orientované cesty.
  22. Dostanete orientovaný graf $G=(V,E)$, a ke každému vrcholu $v\in V$ dostanete navíc jeho cenu $\ARRAY{c}{v}$. Definujeme $\ARRAY{mcena}{v} := $ cena nejlevnějšího vrcholu dosažitelného z $v$ (včetně $v$). Naším cílem na vymyslet algoritmus pracující v čase $\OO(n+m)$, který vyplní pole $\ARRAY{mcena}{\cdot}$.
    1. Nejprve vymyslete algoritmus, který funguje pro orientované acyklické grafy. Nápověda: Zpracovávejte vrcholy v určitém pořadí.
    2. Rozšiřte předchozí algoritmus tak, aby pracovat na všech orientovaných grafech. Nápověda: Připomeňte si strukturu orientovaných grafů (meta-graf, silně souvislé komponenty).
  23. Dostanete neorientovaný graf $G=(V,E)$. Zorientujte jeho hrany tak, aby pro každý vrchol $v$ byl $|\deg^+ v – \deg^- v| \leq 1$.
  24. Dostanete neorientovaný graf $G=(V,E)$. Zorientujte jeho hrany tak, aby se po orientovaných cestách dalo dostat odkudkoliv kamkoliv. Případně řekněte, že taková orientace neexistuje.
  25. Dostanete neorientovaný graf $G=(V,E)$. Přidejte k němu nejmenší možný počet hran, aby $G$ byl $2$-souvislý.
  26. Dostanete orientovaný graf $\vec{G}=(V,E)$. Přidejte k němu nejmenší možný počet orientovaných hran tak, aby $G$ byl silně souvislý souvislý.
  27. Dostanete rovinný graf $G=(V,E)$. Obarvení grafu je přiřazení barev vrcholům takové, že vrcholy spojené hranou mají různou barvu. Zajímá nás, kolik nejméně barev je potřeba.
    1. Navrhněte efektivní algoritmus, který obarví $G$ co nejmenším počtem barev.
    2. Navrhněte lineární algoritmus, který obarví $G$ pomocí $6$ barev.
    3. Jak rychle byste dokázali obarvit $G$ pomocí $5$ barev?
    4. Graf $G$ je $k$-degenerovaný, pokud každý jeho podgraf (včetně $G$ samotného) obsahuje vrchol stupně menšího nebo rovno $k$. Ukažte, jak obarvit $k$-degenerované grafy pomocí $k+1$ barev. Jak rychle poběží Váš algoritmus?

Úlohy na DFS průchod stavovým prostorem

Tady je pár úloh, jejichž řešení můžete nalézt vyzkoušením všech možností (tak zvaný backtracking). Připomínáme, že zkoušení všech možností, není vždy nejrychlejším řešení, ale někdy nic lepšího neumíme.

Pozor, často se stává, že studenti napíší backtracking nevhodně a vyhodnocují některé stavy vícekrát (viz jak se neefektivně počítali Fibonacciho čísla v sekci [ref]odstraneni_opakujicich_se_vypoctu[/ref]).

  1. (Proskákání šachovnice koněm)
    Dostanete šachovnici o rozměrech $n\times m$. Vaším úkolem je zjistit, jestli šachovnici můžeme proskákat šachovým koněm tak, abychom každé políčko navštívili právě jednou. 

    Nápověda : Pro urychlení výpočtu zkuste použít následující heuristiku. Vždy když si můžete vybrat, kam skočíte, tak nejdřív zkuste skočit na to políčko, odkud je nejméně možností jak pokračovat.

  2. (Rozmístění šachových figurek na šachovnici tak, aby se neohrožovali)
    Je dána šachovnice o rozměrech $n\times m$. Jedna figurka ohrožuje druhou, pokud ji může skočit jedním šachovým tahem. Vaším úkolem je rozmístit na šachovnici co nejvíce předepsaných figurek tak, aby se navzájem neohrožovali. 

    1. Šachové věže.
    2. Šachové střelce.
    3. Šachové koně.
    4. Šachové dámy.
    5. Maharadže. Maharádža si v každém tahu může vybrat, jestli bude skákat jako kůň a nebo jako dáma.
    6. Sultány. Sultán si v každém tahu může vybrat, jestli bude skákat jako kůň a nebo jako střelec.

    Nápověda: Program lze zjednodušit malým trikem. Místo toho, abychom si pamatovali, jestli je určité políčko ohroženo nějakou už umístěnou figurkou, si budeme pamatovat kolika figurkami je dané políčko ohroženo. Zjednoduší nám to návrat do předchozího stavu (odebrání figurky). Trik lze dobře využít například pro šachového koně.

  3. (Rozmístění šachových figurek na pneumatiku tak, aby se neohrožovali)
    Navážeme na předchozí úlohu. Jestli už umíte rozmístit co nejvíce předepsaných šachových figurek na normální šachovnici, tak je můžete zkusit rozmístit na šachovnici, které je nakreslená na pneumatice. Šachovnici na pneumatice dostaneme tak, že běžnou šachovnici nejprve stočíme do válce a válec pak ohneme tak, aby se děravé konce spojili. Předpokládejme, že se kraje původní šachovnice spojí tak, že už ani nepoznáme, kde byly. 

    Pozor, diagonály na šachovnici na pneumatice se chovají úplně jinak než na normální šachovnici!

    1. Pro které rozměry $n\times m$ má šachovnice jen jednu levou a jednu pravou diagonálu?
    2. Jak poznáme, kolik levých a kolik pravých diagonál má šachovnice o rozměrech $n\times m$?
    3. Pokud už víte, kolik diagonál má která šachovnice na pneumatice a jak jsou diagonály na šachovnici “namotané”, tak na takovou šachovnici můžete zkusit rozmístit co nejvíce dam tak, aby se vzájemně neohrožovali.

Související úložky z teorie grafů

  1. (Struktura $2$-souvislých komponent)
    Pro každou $2$-souvislou komponentu vytvoříme zvláštní vrchol. Dva zvláštní vrcholy spojíme hranou právě tehdy, když jim odpovídající $2$-souvislé komponenty mají společnou artikulaci. Ukažte, že takto vzniklý graf je strom. 

    Nápověda: Ukažte, že vzniklý graf nemůže obsahovat kružnice.

  2. Dvě cesty v grafu jsou hranově disjunktní, pokud nemají společnou hranu (ale mohou sdílet vrchol). Ukažte, že v libovolném neorientovaném grafu můžeme spárovat vrcholy lichého stupně a spojit každý pár cestou tak, aby všechny cesty byly hranově disjunktní.
  3. (Relace ekvivalence)
    Nechť $S$ je konečná množina. Binární relace$R$ je podmnožina $S\times S$. Jinými slovy $R$ je množina dvojic $(x,y)\in S\times S$. Například pokud by $S$ byla množina lidí, tak $(x,y)\in R$ právě tehdy když “$x$ zná $y$”. 

    Relace je relací ekvivalence, pokud splňuje následující vlastnosti

    • (reflexivita): $(x,x)\in R$
    • (symetrie): pokud $(x,y)\in R$, potom i $(y,x)\in R$
    • (tranzitivita): pokud $(x,y)\in R$ a $(y,z)\in R$, potom $(x,z)\in R$

    Například relace “má ve stejný den narozeniny” je relace ekvivalence a relace “je otcem” není relace ekvivalence.

    Dokažte, že relace ekvivalence rozkládá množinu $S$ na disjunktní skupiny $S_1$, $S_2$, \dots, $S_k$ takové, že

    • Každé dva prvky jedné skupiny jsou v relaci. To je $(x,y)\in R$ pro každé $x,y\in S_i$, pro každé $i$.
    • Žádné dva prvky z různých skupin nejsou v relaci. Jinými slovy pro každé $i\not=j$ a pro každé $x\in S_i$, $y\in S_j$ platí $(x,y)\not\in R$.

    Rozkladem $S$ na skupiny $S_1$, $S_2$, \dots, $S_k$ myslíme, že $S=S_1 \cup S_2 \cup \dots \cup S_k$ a $S_i \cap S_j = \emptyset$ pro každé $i\not = j$.

    Nápověda: Reprezentujte si relace pomocí orientovaných grafů.

  4. (Kotouč)
    Máme veliký kotouč, který má na obvodu napsány nuly a jedničky. Celý kotouč je skryt v pouzdře, akorát na jedné straně má “okénko”, kterým je vidět $k$ po sobě jdoucích čísel. Pootočením kotouče se nejlevější číslice v okénku schová, ale zprava se objeví nová číslice. Takovýmto pootočením dostaneme následující $k$-tici. Kolik nejvíc číslic (nul a jedniček) můžeme napsat na obvod kotouče tak, aby se žádná $k$-tice po sobě jdoucích čísel neopakovala? Umíte takové pořadí nul a jedniček najít?
  5. (Nekonečné grafy)
    1. (Kráva před nekonečným plotem) Kráva stojí před nekonečně dlouhým a rovným plotem. Někde v plotu je díra. Kráva se může vydat hledat díru buď doleva nebo doprava. Zjistěte, jak má kráva postupovat, aby se nenachodila moc a zjistila, kde je díra.Zkuste najít algoritmus, podle kterého kráva nachodí nejvýše 2 krát tolik než je počáteční vzdálenost mezi krávou a dírou (plus malé epsilon). Takovýmto algoritmům se říká $2$-kompetitivní, protože vydají nejvýše $2$ krát větší odpověď, než kolik je optimum.
    2. (Nekonečné bludiště)
      Stojíte uprostřed nekonečně velkého bludiště. Někde v bludišti je ukryt teleport, kterým se můžete dostat ven. Vymyslete, jak ho s jistotou najít.

Hravá bludiště

  1. (Farmář jede na trh)
    Následující bludiště pochází od Robert Abbotta a jmenuje se “Farmer goes to market”.2 Vaším úkolem je poradit farmáři, jak má projet městem tak, aby se ze startu dostal do cíle (finish) a neporušil místní dopravní předpisy. Šipky na každé křižovatce znázorňují, odkud kam se dá křižovatka projet bez porušení dopravních předpisů. 

     

Šifry

Vyřešte následující šifry. První se objevila v šifrovací hře Bedna 2005 a druhá ve hře MATRIX 2005.