Třetí série čtrnáctého ročníku KSP
Řešení úloh
- 14-3-1: Ježíškův problém
- 14-3-2: Cestářův problém
- 14-3-3: Králův problém
- 14-3-4: Hammingův problém
- 14-3-5: Turingův problém
14-3-1 Ježíškův problém (Zadání)
Můj nejmilejší Ježíšku,
minulé Vánoce byly na prosto skvělé, ale musím Ti napsat, že roztomilý kanárek skončil ve věčně nenažrané tlamě našeho Moura a rovněž potápěčské brýle doznaly patrných změn na levém předním skle v důsledku ztřeštěného chování mé sestry. Jelikož vím o Tvém zapeklitém problému, rozhodl jsem se pomoci. Drahnou dobu jsem si říkal, že postačujícím řešením by bylo postupně nagenerovat všechny uspořádané monotónní posloupnosti, zvláště poté, co se ukázalo, že rekurzivní funkci velmi často volám se shodnými parametry – pouhým zapamatováním jednou spočtených hodnot se vyhnu exponenciální časové složitosti. Když jsem si však uvědomil, že se mi rozdírá starotou zašlá kopací meruna, bylo mi jasné že by to pro Tebe chtělo něco lepšího.
První trik spočívá v tom, že budu při generování rozdělovat dárky postupně od nezlobivějšího děcka. Jestliže mu dám i≥ 0 dárků, musím dát alespoň i všem ostatním.
| m |
| i=0 |
| m |
| n |
Pro druhý trik využijeme dynamického programování: R(i,*) je závislé pouze na R(i-1,*), takže nám stačí generovat postupně řádky od R(1,0),… ,R(1,m) do R(n,0),… ,R(n,m). Tím se jednak zachránila paměťová složitost O(m) (pro generování stačí dva řádky) a druhak je zaručeno, že se nic nepočítá na dvakráte.
| m |
| i |
| m2 |
| i |
| n |
| i=1 |
| m2 |
| i |
| n |
| i=1 |
| 1 |
| i |
14-3-2 Cestářův problém (Zadání)
A jak by to vlastne v Agranetámii dopadlo, kdyby vás požádali o program, který určuje udržované silnice? Docela dobře. Většina z vás si všimla, že jde o klasický problém již tisíckrát řešený, tedy o hledání minimální kostry v grafu. Je pravda, že někteří neměli řešení zrovna optimální, ale povětšinou by alespoň vedlo ke správnému výsledku.
Jak se tedy s tímto problémem vypořádat? Já použiji Kruskalův algoritmus na hledání minimální kostry. Algoritmů je více – např. Borůvkův, Jarníkův – ale tento je nejjednodušší; na implementaci navíc využiji union findu.
Úlohu si nejdříve převedeme do řeči grafů. Města budou vrcholy našeho grafu a silnice jeho hrany. Na začátku algoritmu máme graf bez hran – každý vrchol má tedy vlastní komponentu souvislosti. Postupně bereme hrany podle jejich délky (od nejkratší k nejdelší) a pokud hrana nespojuje vrcholy ve stejné komponentě, tak hranu přidáme do našeho grafu a komponenty, které hrana spojila slijeme (takto přidáme N-1 hran (N je počet vrcholů), protože přidáním každé hrany se sloučí dvě komponenty). A tím je vlastně popsán celý algoritmus.
Implementace je v podstatě přesnou kopií algoritmu až na to, že zde používám algoritmus union find, který nám zaručuje, že celkem na slévání komponent a testování, do které komponenty jaký vrchol patří spotřebujeme čas nejvýše O(M·α(N)), kde N je počet vrcholů a M počet hran (α(N) je funkce inverzní k Ackermanově funkci. Pro naše účely nám bude stačit, že α(N) roste skutečně velmi pomalu a pro praktické účely ji lze bez problémů považovat za konstantní). Union find funguje tak, že každý vrchol si udržuje odkaz na „nadřízený“ vrchol v jeho komponentě souvislosti. Na počátku se každý vrchol odkazuje sám na sebe. Když chceme zjistit, zda dva vrcholy leží ve stejné komponentě, zjistíme si nejdříve „šéfy“ komponent, ve kterých leží – půjdeme po nadřízených vrcholech tak dlouho, až narazíme na vrchol, který se odkazuje sám na sebe – to je šéf komponenty. Jestli jsou vrcholy stejné komponentě zjistíme pak snadno tak, že zjistíme, zda mají shodného šéfa. Propojení komponent pak realizujeme tak, že šéfovi menší komponenty dáme za nadřízeného šéfa větší komponenty (u každého šéfa komponenty si budeme proto udržovat velikost komponenty, které šéfuje). Jak si někteří pečlivější čtenáři všimli, takto by struktura ještě zdaleka neměla požadovanou složitost (cesty k šéfům komponent mohou vznikat dosti dlouhé). Složitost se nám ale zlepší na požadovanou, pokud uděláme do hledání šéfů drobné vylepšení: Vždy když k nějakému vrcholu nalezneme šéfa jeho komponenty, tak projdeme cestu k šéfovi ještě jednou a u každého vrcholu nastavíme odkaz na nadřízeného na šéfa komponenty. Výpočet časové složitosti takto vylepšeného algoritmu rozhodně není jednoduchý, a proto ho zde nebudeme uvádět.
A jakou má náš algoritmus celkovou složitost? To spočítáme jednoduše: třídění O(M· log M), zkoušení a přidávání hran uděláme v O(M·α(N)). Dohromady to tedy dává O(M · log M).
14-3-3 Králův problém (Zadání)
Máme dán kořenový strom a naším úkolem je umístit kámen podle daných pravidel do kořene. Ukažme si jednoduché řešení pracující v čase O(N log N). Strom budeme prohledávat od kořene do hloubky. Řekněme, že chceme zjistit, kolik minimálně potřebujeme kamenů k obsazení vrcholu v. Pokud je v list, je hledaná hodnota rovna jedné. Jinak si vezměme všechny jeho syny w1, …, wk. Rekurzivně pro každého syna wi určíme minimální počet kamenů potřebný k jeho obsazení. Takto získané hodnoty setřiďme sestupně, vzniklou posloupnost označme pi. Tvrdím, že minimální počet kamenů nutný k umístění kamene do vrcholu v je maximum z čísel pi + i, i = 1, 2, …, k. Je jasné, že nejlepší pro nás bude obsazovat kameny od těch vrcholů, které potřebují nejvíce kamenů na své obsazení. Po obsazení některého syna kamenem je však již tento kámen blokován a nemůžeme jej dále použít. Proto proměnná i. Tvrzení je velice jednoduché, samostatně si jej promyslete.
Poměrně častou chybou ve Vašich řešeních bylo, že jste si neuvědomili, že záleží na pořadí, v jakém budete jednotlivé vrcholy obsazovat kameny. Převládala však řešení používající stejnou myšlenku jako výše uvedené. K programu snad jen to, že se předpokládá, že na vstupu jsou hrany, podobně jako v zadání, vzestupně setříděny podle koncového vrcholu.
14-3-4 Hammingův problém (Zadání)
Tato úloha byla spíše praktického ražení. Proto byl pro zajímavost k jednotlivým způsobům řešení připojen i čas běhu na reálném počítači. Řešení této úlohy spolu s komentářem naleznete mezi vzorovými programy.
14-3-5 Turingův problém (Zadání)
Na tuto úlohu se nesešlo mnoho řešení, zato povětšinou obsahovala pouze drobnější chyby. A nyní k vzorovému řešení: Původní k-páskový Turingův stroj si označíme T, jeho abecedu Σ. Nově vytvářený jednopáskový stroj si označíme T' a jeho abecedu Σ'. K řešení lze přistupovat v zásadě třemi způsoby: buď pásky proložit (tj. i-té políčko z j-té pásky bude na pozici i·k + j) nebo je naskládat za sebe (pak se ale musí při zápisu nového znaku pásky posouvat) nebo i-tá políčka na všech k páskách „zakomprimujeme“ do jedné k-tice na i-tém políčku jediné pásky nového stroje. Posledně jmenovaný způsob použijeme i v našem vzorovém řešení. Protože si také potřebujeme pamatovat pozice hlav nad jednotlivými páskami, bude abeceda stroje T' Σ'=(Σ×{H,V})k×{Z,S}∪{ω}. Značka H u znaku znamená, že nad znakem je hlava; značka Z u k-tice znaků znamená, že k-tice je první na pásce. ω je speciální znak konce pásky. Znaky vyjadřující k-tice, kde na první pásce je nějaký znak z abecedy a na ostatních páskách jsou znaky Λ (nad žádným znakem není hlava) ztotožníme se znaky původní abecedy Σ. Tím se nám překódovnání vstupu zjednoduší na přepsání prvního znaku α∈Σ na pásce znakem ({α,H},{Λ,H},… ,{Λ,H},Z) (všechny hlavy totiž na počátku stojí na začátku pásek). Uvědomte si, že překódování celého vstupu by nebylo vůbec jednoduché, protože stroj nemusí být schopen poznat, kde vlastně vstup končí – znak Λ může být korektní součástí vstupu.
Nyní jak bude stroj T' pracovat: Stroj vždy dojede hlavou na počátek pásky (ten pozná podle značky Z). Pak jede hlavou doprava, dokud nenarazí na značku odpovídající hlavě nad první páskou, zde si přečte znak pod hlavou na první pásce a znak si uloží do stavu. Pak se stroj opět přesune na počátek pásky a obdobným způsobem načítá znaky pro druhou až k-tou pásku. Nyní, když má stroj ve stavu uloženu celou k-tici znaků pod hlavami, není problém přejít do stavu, do kterého přejde původní stroj T a zároveň si ve stavu uložit znaky, které mají být zapsány a směry, kterými mají být posunuty hlavy. Pak stroj začne podobně jako při načítání jezdit po pásce, zapisovat nové znaky a posouvat značky pro hlavy. Když byly zapsány všechny znaky a posunuty všechny hlavy, začne stroj simulovat další krok původního stroje. Pokud stroj T' zjistí, že se nějaká hlava posunula nad znak ω, tak posune znak ω o jedno pole doprava a na jeho původní místo zapíše znak příslušné k-tice (tedy k znaků Λ s příslušnou značkou pro hlavu). Pokud stroj T' při posouvání hlav zjistí, že nějaká hlava narazila do levého okraje své pásky (to snadno pozná podle značky Z), tak projde celou pásku až po znak konce pásky ω a znaky na pásce přepíše znaky odpovídajícími obsahu první pásky a pak se ukončí nárazem hlavy do levého konce pásky. Všimněte si, že znak ω je nutný, protože jinak bychom při přepisování nepoznali, kde končí výstup. Takto ale máme jistotu, že za znakem ω už jsou pouze znaky Λ, které není třeba přepisovat. Počet stavů stroje T' bude zřejmě konstantní (řádově c·k·3k·|Σ|k ·Q (Q je počet stavů původního stroje T) – tolik stavů potřebujeme, abychom si zapamatovali do jakého stavu chceme přejít, kam posunout hlavy, jaké znaky zapsat a kolik pásek jsme již vyřídili).