Druhá série desátého ročníku KSP

Řešení úloh

• 10-2-1: Byrok(r)ati
• 10-2-2: Minitónní posloupnost
• 10-2-3: Turingův stroj
• 10-2-4: Bynáriho logaritmus
• 10-2-5: Kostky jsou vrženy

---

10-2-1 Byrok(r)ati (Zadání)

---

Z řešení bylo vidět, že s byrokratickým aparátem máte každý nějaké ty zkušenosti. Ne všichni je však máte stejné. Někteří z vás byli z těch byrokratů tak zmatení (nebo byli tak pilní?), že se zapomínali podívat do tašky na lejstra, zda tam již požadované lejstro nemají, a jedno a totéž lejstro sháněli při každém byrokratickém požadavku stále znovu a znovu. To u těchto lidí vedlo k tomu, že objem jejich tašky narůstal a narůstal, až přerostl únosné meze a přiblížil se exponenciální hranici. Tací se tedy zjevně nikdy audience nedočkali, neboť v průběhu shánění lejster padli vyčerpáním. Za tuto metodu shánění lejster jsme strhávali čtyři body. Skupina studovaných lidí, kteří ohřívají vodu na čaj tak, že nejprve případnou vodu z konvice vylijí, poté znovu do konvice napustí požadované množství vody a pak teprve postaví konvici na sporák, převedla tento problém na známý problém topologického třídění. Podle toho, jak se jim zadařilo, pak úlohu řešili buď v čase kubickém či čase kvadratickém. Za takové řešení obvykle autor utržil o nějaký ten bod méně.

Ti nejzkušenější z vás, mezi které patří i Tonda Hildebrand z Jeseníku, řešili tento problém postupem, který byl výstižně popsán právě v pracech zmíněného, s byrokracií zkušeného autora, a proto si zde jeho popis dovolíme otisknout doslova. (Věříme, že díky jeho postupu budeme v byrokratickém aparátu tak zběhlí, že případné spory o autorská práva dokážeme odrazit.)

Tedy: Byrokratický systém je věc záludná a nejeden poddaný padl vyčerpáním při shánění povolení k audienci. Není se co divit, když prochodil kilometry palácových chodeb, mnohokrát se ztratil, povolení k audienci stále neměl, ale zato různých zbytečných lejster měl bezpočet. Takový hloupý sedlák udělal chybu, že se zběsile vrhnul do ještě zběsilejší rekurze, stále se vnořoval do nových ouřadů až nakonec zapomněl cestu domů.

Byrokat je naštěstí člověk líný, nejraději by seděl u svého číslicového stroje a z donesených informací zjišťoval, jak to v tom paláci vlastně chodí. Je mu jasné, že procházet úřady na papíře je daleko rychlejší než je hledat v paláci. V zájmu pohodlí také zjistil, že na obelstění byrokratického aparátu mu stačí jedno pole PAPALÁŠI s tolika prvky, kolik je v zámku ouřadníků. Tady bude mít u každého ouřadníka:

• Jestli nemá jeho lejstro L, pak pokud bude o toto lejstro požádán, tak ho musí sehnat.
• Jestli už má jeho lejstro L, pak ouřadníka už nikdy nemusí vidět.
• Jestli shání jeho lejstro L, aby si ho ouřadové neposílali mezi sebou.

Dále si na papírek zapisuje, v jakém pořadí lejstra získává. Protože chodil po ouřadech v určeném pořadí (a jen když musel) a na papírek si zapisoval čísla ouřadníků teprve tehdy, až lejstro opravdu držel v ruce (pomyslně), je tedy pořadí ouřadníků na papírku výsledkem a může ho (samozřejmě za honorář) předat poddanému. Pokud by se mu stalo, že při shánění určitého lejstra by po něm jiný ouřada toto lejstro chtěl (jednoduše se podívá do pole PAPALÁŠI), je úkol nesplnitelný a poddaný to musí zkusit zítra.

Výše uvedený popis odpovídá postupu chytrého sedláka, který dělá jen to co musí, ale poctivě. Takovýto postup spotřebuje kvadratické množství času v závislosti na počtu ouřadníků (O(n²), kde n je počet ouřadníků) a stejné množství paměťového prostoru (na zapamatování provázanosti ouřadů).

Program snad netřeba zvlášť komentovat.

Program

Michal Koucký

---

10-2-2 Minitónní posloupnost (Zadání)

---

Před započetím řešení úlohy je třeba si důkladně přečíst definici podposloupnosti. První řešení, které nás napadne je střídat "velká" a "malá" čísla a vytvořit např. pro n=8 posloupnost 1,8,7,2,6,3,5,4 – tato posloupnost má však monotónní podposloupnost délky 5 a to 8,7,6,5,4. Po chvilce zkoušení však pro n=8 nalezneme posloupnost 1,8,7,2,4,6,3,5, kde délka nejdelší monotónní podposloupnosti je 4, a poté i posloupnost 7,2,4,1,8,6,3,5, kde délka nejdelší monotónní podposloupnosti je dokonce pouze 3.

Pokusme se tedy nejprve udělat pro dané n odhad délky nejdelší monotónní podposloupnosti. Uvažme libovolnou posloupnost dle zadání úlohy a každému jejímu členu přiřaďme dvojici čísel reprezentující délku nejdelší rostoucí posloupnosti a délku nejdelší klesající posloupnosti jím končící. Tedy např. pro posloupnost 7,2,4,1,8,6,3,5 z prvního odstavce tímto postupem vytvoříme 7→(1,1),2→(1,2),4→(2,2),1→(1,3), 8→(3,1),6→(3,2),3→(2,3),5→(3,3). Délka nejdelší monotónní podposloupnosti je rovna maximu z přiřazených čísel. Použité dvojice čísel se neopakují, nebot všechny členy posloupnosti jsou různé. Byla-li některému členu přiřazena nepř. dvojice (5,?), byla určitě jinému členu přiřazena dvojice (4,?) – "každá alespoň dvouprvková posloupnost má předposlední prvek". Má-li tedy nejdelší monotónní podposloupnost délku k, lze vytvořit k² dvojic čísel 1 až k a tedy k²≥ n.

Jestliže pro dané n vypíše program posloupnost, jejíž nejdelší monotónní podposloupnost má délku ⌈√n⌉ (pro neznalé horní celá část odmocniny z n), je tato posloupnost optimální. Nejobtížnější je to samozřejmě učinit pro n=k², neboť pro menší n můžeme hledanou posloupnost získat z posloupnosti pro k² vynecháním příliš velikých členů. Jedním z mnoha možných řešení je vytváření pro k² posloupností sestavených z k klesajících bloků: 3,2,1,6,5,4,9,8,7 (k=3). Analogicky pro větší k.

Napsat program realizující daný algoritmus je nyní již snadné. Časová složitost je (při dobré realizaci) lineární, paměťová je dokonce konstantní.

Program

Daniel Kráľ

---

10-2-3 Turingův stroj (Zadání)

---

U této úlohy se nám sešlo relativně málo řešení, zato většina z nich opravdu fungovala. Základní problém byl ovšem v určování časové a paměťové složitosti – i u Turingova stroje samozřejmě mají tyto pojmy rozumný smysl: paměťová složitost algoritmu je počet použitých políček pásky (řídící tabulka stroje se do ní nepočítá, jelikož je konstantní pro všechna vstupní data a u běžných programů se také do paměťové složitosti program nepočítá), časová složitost pak celkový počet kroků výpočtu. Uvědomte si, že paměťová složitost nikdy nemůže přesáhnout časovou (v každém kroku výpočtu můžeme použít maximálně jedno dosud nepoužité políčko) a že na rozdíl od obvyklých programovacích jazyků zde má smysl nejen asymptotické vyjádření složitosti, ale i přesná čísla (my si ovšem vystačíme s tvarem asymptotickým).

Základní otázkou ovšem je, jakou representaci čísel si zvolit: nejjednodušší by bylo užít "jedničkovou soustavu" (též řečenou jedničkový aditivní kód – prostě číslo n je zapsáno n jedničkami), ale u ní je základní nevýhodou velká paměťová (a tím pádem i časová) náročnost algoritmu (násobíte-li čísla m a n, potřebujete paměť O(m×n) na uložení výsledku. Na druhou stranu, násobit čísla v desítkové soustavě by bylo zbytečně složité, zvolíme proto soustavu dvojkovou. Čísla budeme zapisovat tak, že nalevo (tak budeme říkat poloze nejblíže k začátku pásky) bude číslice nejnižšiho řádu, napravo pak nejvyššího.

Pokud máme více čísel, můžeme je jednoduše zapsat za sebe a oddělit nějakým speciálním znakem (nabízí se kupříkladu Λ). Jelikož však jsme ve stavech stroje schopni uchovat pouze konečně mnoho informace a zpracovávaná čisla nejsou nijak omezena, musíme pak libovolnou operaci s nimi (tedy i prosté zkopírování jinam) provádět po malých kouscích a neustále skákat od jednoho čísla k druhému, čímž algoritmus oproti programovacím jazykům dovolujícím přímou adresaci paměti zpomalíme řádově tolikrát, kolik je vzdálenost začátků čísel od sebe (a to je minimálně délka kratšího z nich).

Existuje ovšem jednoduchý trik, s jehož pomocí se lze tomuto poskakování mezi čísly vyhnout: prostě obě čísla zapsat na totéž místo – buďto proloženě (tedy číslice střídavě z jednoho a z druhého čísla), nebo místo dvou číslic použít čtyři a každou novou číslicí kódovat jednu číslici prvního čísla a jednu (téhož řádu) druhého. Tak všechny algoritmy procházející obě čísla "zleva doprava" dokážeme provést v lineárním čase. My si pro náš stroj zvolíme metodu první (prokládání), jež vede na menší abecedu za cenu zvětšení počtu stavů.

Páska stroje bude při násobení x=a·b vypadat takto: a₀ a₁… a_n ♥b₀x₀b₁x₁… přičemž nevyužité číslice b a x budou mít hodnotu Λ, chápanou jako nulu. Navíc si v průběhu výpočtu budeme již zpracovaná a_i odškrtávat znakem †. Abeceda stroje tedy jest Σ= {0, 1, †, ♥, Λ}.

A nyní již k algoritmu: násobíme-li číslo b číslem a zapsaným ve dvojkové soustavě jako a = ∑_i a_i2ⁱ, je jistě x = a ·b = (∑_i a_i2ⁱ ) ·b = ∑_i a_i2ⁱ ·b. Toto nám přesně dává školský algoritmus na násobení zapsatelný takto:

1. x ←0
2. Jestliže a mod 2 = 1, pak x ←x + b
3. a ←⌊a/2 ⌋
4. b ←2 ·b
5. Pokud a ≠ 0, pokračuj krokem 2.

Přeformulováno pro Turingův stroj: Najdi nejlevější číslici a_i, která dosud není škrtnuta a škrtni ji. Pokud to byla jednička, přičti k x hodnotu b. V každém případě pak vynásob b dvěma (to jest posuň o řád doprava). Toto opakuj, dokud zbývají v a neškrtnuté číslice.

Následující tabulka definující náš stroj (S je počáteční stav; proškrtnutá okénka stroj pří korektním zadání nemůže použít) snad ani nepotřebuje dalších komentářů:

A jak je to s časovou složitostí? Při zpracování každé cifry čísla a "přejedeme" celou využitou část pásky doprava, pak se o kus vrátíme, pak opět doprava a pak se opět vrátíme ⇒ celkem tedy O(log a + log b), toto vykonáme (log a)-krát, což dává celkem

Zkuste si promyslet, jak by se toto řešení změnilo, když bychom místo prokládání čísel na pásce zkusili použít větší abecedu…

Martin Mareš

---

10-2-4 Bynáriho logaritmus (Zadání)

---

Většinou jste přišli na to, že pro Bynáriho logaritmus je rozhodující první jednička daného čísla ve dvojkovém zápisu. Většinou jste také přišli na to, že mocniny dvojky je třeba zpracovat zvlášť nebo si na ně dát aspoň pozor, protože u nich je logaritmus roven exponentu v mocnině, zatímco u ostatních čísel je o jedna vyšší, než pořadí nejvyššího nenulového bitu.

Zbývá tedy vyřešit, jak najít nejvyšší bit. A tady nám pomůže půlení intervalu. Nejvyšší jednička totiž může být buď v prvních 512 bitech, nebo ve druhých. To zjistíme prostým porovnáním našeho čísla s 2⁵¹², tedy vlastně s 1 << 512 (pro pascalisty: 1 shl 512). Řekněme, že je ve vyšších 512 bitech. Pak může být buď ve 256 nejvyšších, nebo zas v té druhé půlce, zjistíme porovnáním s 1 << (256+512)…

Potřebujeme tak log₂ 1024=10 kroků (mimochodem, všimli jste si, že 1024 je také číslo úlohy? – pozn. M.M.)

Program

Vít Novák

---

10-2-5 Kostky jsou vrženy (Zadání)

---

Triviálně lze úlohu řešit setříděním kostek a pak vybráním prvních K největších. To je ovšem zbytečně pomalé (v čase alespoň O(N· log N)), neboť je zbytečné třídit příliš lehké kostky (ty nás nezajímají) ani příliš těžké (to po nás nikdo nechce).

Úlohu jste řešili dvěma způsoby: za předpokladu, že Baron Bynári je negramotný, jste se pouze soustředili na algoritmus nalezení K největších prvků z pole a prvky jste v poli pouze řadili a nepamatovali jste si jednotlivé výsledky vážení.

Někteří z vás se snažili minimalizovat počet vážení tím, že si pamatovali v jiné datové struktuře výsledky jednotlivých vážení, aby se nevážily koule, které již byly jednou vzájemně zváženy, nebo navíc někteří na základě předchozích vážení byli schopni říct, jak některé konkrétní vážení dopadne (např. vím-li, že 1>2 a 2>3, dá se odvodit, že 1>3). Tímto řešením jste ale předpokládali gramotnost Bynáriho (musel by si výsledky zapisovat). Toto je však už řešení obecnějšího problému, než bylo myšleno zadáním. K tomuto řešení byste potřebovali další datovou strukturu – tabulku, do níž byste si zapisovali výsledky a podle konkrétních vážení doplňovali další relace mezi kostkami vyplývající z vážení. Doplňování relací by navíc zvětšilo celkovou složitost původního algoritmu, který by bez tohoto pracoval v průměru v lineárním čase vůči počtu kostek. Dále se tedy zabývejme pouze algoritmem nalezení K největších kostek řazením.

Náš algoritmus je modifikací známého třídícího algoritmu Quicksort. Kostky dáme do řady a budeme se na ně odkazovat pomocí indexu v řadě.

Vybereme si nějakou kostku v řadě, označme ji X. Rozdělíme řadu na tři části, do levé dáme kostky těžší než X, do pravé lehčí než než X a uprostřed rovné X. Nechť je počet kostek v levé části L, pravé P, uprostřed U. Máme-li najít K největších kostek a K<L, pak opakujeme algoritmus od začátku, ale vstupem bude pouze těchto L kostek. Pokud K>L+U, pak jsme našli L+U hledaných kostek a opakujeme algoritmus od začátku s tím, že už hledáme pouze v pravé části s P kostkami a hledáme K-L-U kostek. V ostatních případech jsme našli K největších kostek: je to L kostek vlevo a z prostředku vezmeme prvních K-L kostek (neboť uprostřed jsou všechny stejně těžké).

Jinak řečeno: náš algoritmus najde K-tý největší prvek a všechny prvky nalevo od něj jsou díky vhodnému řazení větší nebo stejné.

Důkaz správnosti: Algoritmus skončí, když bude K v prostřední části, což bude nejpozději, když bude na vstupu jedna kostka, a protože v každém kroku algoritmu rozdělíme řadu kostek na alespoň dvě menší části (jinak bychom ihned skončili – vše by bylo uprostřed). Nalézáme postupně nejtěžší kostky v levé části a příliš lehké zahazujeme a v každém kroku algoritmu platí K>poč. už nalezených+L+U, takže o žádnou kostku ve správném výsledku nepříjdeme.

Složitost: Záleží na výběru kostky X. Kdybychom dokázali pokaždé vybrat prostřední kostku co do váhy, rozdělili bychom řadu kostek (když by se v řadě nevyskytovaly stejně těžké kostky) nejprve na polovinu, pak na čtvrtinu, osminu,..., tedy počet vážení by se dal odhadnout na N+N/2+N/4+ ...+1=2·N, tj. počet vážení je lineárně závislý na počtu kostek O(N).

Když bychom vybírali pokaždě nejhorší možnost, tj. za X bychom vybrali např. nejlehčí kostku, počet vážení by byl přibližně N+(N-1)+ (N-2) + … +K, což je v součtu kvadratický počet vážení vůči počtu kostek – O(N²). O průměru se však dá říci (leč přesné spočítání průměrného chování je bohužel nad rámec našeho semináře), že se bude provádět O(N) vážení. Důkaz je velice podobný důkazu složitosti algoritmu Quicksort.

Program

Martin `Mafi' Bělocký

Menu