Třetí série čtrnáctého ročníku KSP

Zadání úloh

14-3-1 Ježíškův problém (11 bodů)

Vždy před Vánoci má Ježíšek problém, jak rozdělit mezi děti dárky. V průběhu roku z nebe Ježíšek pečlivě sleduje, jak je které dítě hodné a podle toho pro něj udržuje index zlobivosti. Před Vánoci by pak chtěl mezi děti rozdělit dárky tak, aby když dítě A má vyšší index zlobivosti než dítě B, tak A dostane nejvýše tolik dárků, kolik dostane B (předpokládejte, že žádné dvě děti nemají stejný index zlobivosti). Může se přitom stát, že hodně zlobivé děti nedostanou žádný dárek a hodné děti dostanou dárků více. Dárky musí být rozděleny všechny. Aby se Ježíšek mohl dopředu připravit na rozhodování, chce po vás napsat program, který dostane počet dětí N a počet dárků M a na výstup vypíše počet způsobů, kterými lze mezi děti dárky rozdělit. Sami si rozmyslete, že jednotlivé indexy zlobivosti vlastně nepotřebujete znát.

Příklad: Pro čtyři děti a čtyři dárky je pět možností, jak dárky mezi děti rozdělit ((0,0,0,4), (0,0,1,3), (0,0,2,2), (0,1,1,2), (1,1,1,1)).

Řešení

14-3-2 Cestářův problém (10 bodů)

S novým rokem vešel v platnost i nový rozpočet v Agranetánii. V něm se našlo pouze velmi málo prostředků na údržbu cest a silnic. Ministr Poslů a cest rozhodl, že je třeba co nejvíce snížit délku udržovaných cest a tím pochopitelně i náklady na jejich údržbu. Na druhou stranu je ovšem třeba zajistit, aby se po udržovaných cestách stále dalo dojet z libovolného města do libovolného jiného (jinak by se totiž král mohl zlobit, že jeho luxusní kočár příliš kodrcá a ministra by sesadil). Protože úkol to není jednoduchý, rozhodl se ministr najmout vás, abyste mu napsali program, který problém vyřeší.

Váš program dostane na vstupu počet měst N a dále současný počet cest M. Pak následuje popis M cest. Pro každou cestu dostane program čísla dvou měst (města si očíslujeme od jedné do N), mezi kterými cesta vede, a dále délku příslušné cesty. Na výstup má váš program vypsat cesty, které je třeba zachovat, aby se stále ještě šlo dostat mezi každými dvěma městy a přitom byl součet délek cest nejmenší možný.

Příklad: Pro osm měst a deset cest (cesty jsou zapsány ve tvaru (a,b,d), kde a a b jsou města a d je délka cesty) (1,2,1), (2,3,4), (1,4,3), (2,4,2), (2,5,2), (3,6,3), (5,6,1), (6,8,4), (4,7,1), (5,7,2) jsou hledané cesty (1,2), (2,4), (4,7), (7,5), (5,6), (6,3), (6,8).

Poznámka: Pokud se vám předchozí zadání zdá příliš triviální, zkuste se zamyslet, jak vaše řešení zrychlit za předpokladu, že zadaný graf lze nakreslit do roviny bez křížení hran. Za kvalitní řešení tohoto složitějšího problému je možno získat až pět bonusových bodů.

Řešení

14-3-3 Králův problém (10 bodů)

Král Trdlo z Tramtárie vás poté, co se doslechl o vašich řešeních hry Kyvadlo, požádal o pomoc s další oblíbenou hazardní hrou. Jedná se o hru „Kamínky“. Tato hra se hraje na hracím plánu ve tvaru stromu (tedy grafu, kde mezi každými dvěma vrcholy vede právě jedna cesta). Bankéř vždy podle určitých pravidel vytvoří strom, na kterém se bude hrát. Pak v něm zvolí jeden významný vrchol (nazvěme ho kořen) a všechny hrany ve stromu zorientuje směrem ke kořeni. Nyní může hra začít. V každém tahu může hráč položit jeden hrací kámen na takový vrchol, jehož všichni předchůdci (tedy vrcholy, z nichž vede do onoho vrcholu hrana) již na sobě kameny mají, nebo může z libovolného vrcholu kámen odebrat. Speciálně na vrcholy, do kterých nevede ze žádného vrcholu hrana, lze položit kámen kdykoliv. Hráč vyhrává, pokud se mu podaří umístit dle pravidel hry kámen do kořene stromu. Problémem v této hře je, že hráč má pouze tolik kamenů, kolik si od bankéře na počátku hry koupil. Je proto třeba co nejlépe odhadnout potřebný počet kamenů. A to je přesně problém, o jehož řešení vás král Trdlo požádal.

Váš program dostane na vstupu počet vrcholů stromu N. Dále dostane číslo vrcholu, který byl bankéřem vybrán za kořen (vrcholy si očíslujeme od jedné do N). Nakonec dostane popis N-1 hran ve stromu. Pro každou hranu dostane dvojici čísel vrcholů, mezi nimiž hrana vede. Na výstup má váš program vypsat minimální počet kamínků potřebný k vyhrání hry.

Příklad: Máme strom na sedmi vrcholech. Kořen je ve vrcholu jedna. Hrany ve stromu jsou: (2,1), (3,1), (4,1), (5,2), (6,2), (7,3). Na vyhrání hry jsou třeba čtyři kamínky. Můžeme táhnout například: +5, +6, +2, -5, -6, +7, +3, -7, +4, +1 ('+' před číslem znamená, že do daného vrcholu přidáváme kámen; '-' před číslem znamená, že z daného vrcholu odebíráme kámen).

Řešení

14-3-4 Hammingův problém (10 bodů)

Pro dvě čísla si nadefinujeme Hammingovu vzdálenost jako počet bitů, ve kterých se čísla liší. Například pro čísla 7 a 9 je jejich Hammingova vzdálenost tři, protože 7 je ve dvojkové soustavě 0111 a 9 je 1001 a čísla se tedy liší ve spodních třech bitech. Vaším úkolem je napsat program, který pro dvě čísla (předpokládejte, že se vejdou do standardního celočíselného typu) co nejrychleji zjistí jejich Hammingovu vzdálenost.

Řešení

14-3-5 Turingův problém (10 bodů)

V minulých dvou sériích jste pracovali s jednopáskovým a vícepáskovým Turingovým strojem. Asi je každému jasné, že co jde spočítat na jednopáskovém stroji, půjde spočítat i na stroji vícepáskovém. Navíc vícepáskový stroj nám umožňuje mnohé úlohy spočítat rychleji než stroj jednopáskový – například otočení slova zvládneme na dvoupáskovém stroji snadno v lineárním čase. Je poměrně zajímavým faktem (i když důkaz není úplně jednoduchý), že dvoupáskový stroj sice umožňuje spočítat některé úlohy rychleji než stroj jednopáskový, ale třípáskový stroj nám už oproti dvoupáskovému další zrychlení neposkytne. Další zajímavou skutečností je, že pokud má alespoň dvoupáskový Turingův stroj vyšší než lineární časovou složitost (tedy například n log n), tak pak pro každé přirozené číslo c>1 lze vytvořit Turingův stroj, který bude c-krát rychlejší. Tato skutečnost je také jedním z důvodů, proč v teoretické informatice nehledíme na konstanty. Na důkazu tohoto tvrzení si teď ukážeme některé techniky, které se při podobných důkazech používají.

Náš nově vytvářený stroj bude pracovat ve třech fázích. V první fázi zakomprimuje vstup, v druhé fázi bude konstantním počtem svých kroků simulovat alespoň c-krát více kroků původního Turingova stroje a ve třetí fázi bude dekomprimovat výstup.

Vstup budeme komprimovat tak, že si vstupní pásku rozdělíme na d-tice (d zvolíme dostatečně velké – řekněme jako 20·c). Do abecedy si přidáme nové znaky – pro každou možnou d-tici jeden. Například pro abecedu {0, 1, Λ} a d=2 do abecedy přidáme písmena (Λ,Λ), (Λ,0),(Λ,1),(0,Λ),… ,(1,1). Protože jak d tak velikost abecedy jsou pevné, přidáme tím do abecedy pouze konstantní počet znaků, a tedy jsme se nedostali do rozporu s definicí Turingova stroje (velikost abecedy nesmí záviset na velikosti vstupu). Komprese pak probíhá tak, že si stroj vždy „do stavu“ načte jednu d-tici a znak odpovídající d-tici zapíše na druhou pásku. Když takto stroj zakomprimuje celý vstup, přepíše původní vstupní slovo lambdami a přejde do druhé fáze.

Druhou fázi si ukážeme pouze pro jednu pásku. Pro více pásek by konstrukce fungovala úplně stejně, pouze by byla technicky komplikovanější. V této fázi budeme pěti kroky našeho stroje simulovat alespoň d kroků původního stroje. Ve stavu našeho stroje si mimo stavu původního stroje budeme udržovat obsah políčka pod hlavou a políček sousedních (nezapomeňte, že již pracujeme nad zakomprimovanou páskou, takže si vlastně ve stavu pamatujeme 3d políček). Krajní políčko na pásce má pouze jedno sousední políčko, takže pro toto políčko si musíme vytvořit ještě speciální stavy. Snadno si můžete ověřit, že stavů jsme opět přidali pouze konstantní (i když značné) množství. Přechody nového stroje ze stavu q, kde q kóduje 3d-tici písmen (α1,… ,α3d) a nějaký stav q′ původního stroje, vytvoříme následujícím způsobem: Vezmeme ona políčka, která máme uložena ve stavu, a necháme původní stroj nad nimi běžet (bude začínat ve stavu q′), dokud z nich jeho hlava nevyběhne. Přechod nyní nadefinujeme do stavu, který odpovídá obsahu oněch 3d políček po běhu stroje, a stavu, ve kterém stroj z 3d políček vyběhl. Přechod nebude ve skutečnosti tak jednoduchý – ještě než přejdeme do stavu, který jsme si vyhlédli, musíme také změněná políčka přepsat na pásku. To je ale pouze technická komplikace, kterou snadno vyřešíme tak, že každý přechod se bude odehrávat přes čtyři stavy pro tento přechod speciálně vytvořené (takovýchto stavů budeme opět potřebovat pouze konstantní množství, takže dodržíme požadavky v definici Turingova stroje). V prvním ze stavů zapíšeme na políčko pod hlavou nový obsah prostředních d políček a přejdeme hlavou doleva. Tam zapíšeme obsah prvních d políček a přesuneme se dvakrát doprava, kde zapíšeme obsah posledních d políček. Nakonec se přesuneme nad políčko obsahující d-tici, nad kterou momentálně má stát hlava. Pokud původní stroj vyběhnutím z 3d políček vyběhl z pásky a tím skončil, přejdeme po předchozích operacích do třetí fáze. Protože původní stroj začíná buď nad d-tým nebo 2d-tým políčkem z oněch 3d zapamatovaných, bude mu vyběhnutí trvat alespoň d kroků, a tedy našimi pěti kroky nasimulujeme alespoň slibovaných d kroků původního stroje.

Ve třetí fázi už jen dekomprimujeme výstup podobným způsobem, jakým jsme ho v první fázi komprimovali. Všiměte si, že naše konstrukce skutečně nutně potřebuje alespoň dvě pásky, protože jinak bychom kompresní a dekompresní fázi nemohli dělat v lineárním čase.

Nyní, když jsme si ukázali jeden z obtížnějších důkazů v této oblasti teorie složitosti, přichází čas na úlohu pro vás. Ukázali jsme si, že jednopáskové a vícepáskové mají některé dosti odlišné vlastnosti – například dvoupáskové stroje není problém konstantně zrychlovat. Vyvstává proto přirozená otázka: Pokud máme vícepáskový Turingův stroj, dokážeme sestrojit jednopáskový Turingův stroj, který bude dávat stejné výsledky (tzn. na jeho pásce bude na konci stejný výstup, jako na první pásce vícepáskového stroje)? Vaším úkolem je takovouto konstrukci vymyslet (samozřejmě se zdůvodněním, proč by měla fungovat).

Řešení