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

Termín odeslání Vašich řešení této série jest určen na 12. prosince 1997. Řešení můžete odevzdávat jak elektronicky, tak klasickou poštou na známou adresu.

Dotazy ohledně zadání můžete posílat na adresu ksp@mff.cuni.cz, nebo se ptát přímo na diskusním fóru KSP.

Zadání úloh


10-2-1 Byrok(r)ati (10 bodů)


V královském paláci se ke značnému zoufalství všech poddaných rozbujela byrokracie – královští ouřadníci si navzájem vytvořili n papalášských funkcí a do nich se jmenovali (označíme si je třeba čísly 1 až n). A když někdo přišel do paláce žádaje audienci u krále, musel jít za ouřadníkem, který byl pro daný den zvolen jako lord tiskový mluvčí (nechť má číslo L) a vyžádat si od něj povolení k audienci.

Jenže jak už to v byrokratických systémech bývá, týmová práce jest nezbytná (asi proto, že umožňuje svalit vinu na ostatní), a tak lord tiskový mluvčí vydá povolení pouze tehdy, dostane-li potvrzení o odbornosti tazatele, potvrzení o loayalitě králi, dále pak glejt o bezúhonnosti, jakož i výpis z rejstříku tortury – tedy vlastně mnoho dalších lejster, která vydávají jiní ouřadníci. Ale vydají je obvykle jen tehdy, přinese-li jim ubohý poddaný glejty od jiných ouřadníků atd. Každý z nich ovšem vydává pouze jedno lejstro (takže každého z nich má smysl navštěvovat nejvýše jednou).

Ale poddaní se nedali – na cestě ke královskému paláci stojí stánek byrokata (to je člověk, jenž se specializuje na potírání byrokracie) a z jedné strany k němu chodí donašeči z paláce dodávající informace o tom, který z pánů ouřadů zrovna chce potvrzení od kterých ostatních (například jakožto čísla oij jsoucí nenulová, pokud i-tý ouřada požaduje k vydání svého lejstra jiné od j-tého ouřady), zatímco ze strany druhé přicházejí poddaní a ptají se, v jakém pořadí mají papaláše navštívit, aby povolení k audienci od lorda L získali. (Všechny osoby v tomto příběhu jsou smyšlené a jakákoliv podobnost s pohádkou o kohoutkovi a slepičce, s realitou, jakož i s úlohou o topologickém třídění grafu je čistě dílem náhody.)

Úkol pro vás: vymyslet program, který bude řešit byrokatův problém.

Příklad: Pro o=

0 1 1 0 0 0
0 0 1 1 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 1 0 0 0 1
0 1 0 0 1 0

a L=1 je jedním z možných pořadí 4, 3, 2, 1, zatímco pro tatáž oij a L=5 není úkol splnitelný, protože papaláši 5 a 6 se navzájem posílají jeden k druhému.

Řešení


10-2-2 Minitónní posloupnost (12 bodů)


Napište program, který pro dané číslo n vytvoří posloupnost délky n obsahující každé z čísel 1n, a to takovou, aby délka nejdelší monotónní (to jest rostoucí či klesající) podposloupnosti byla co nejmenší. Podposloupností posloupnosti a1, … , an se rozumí jakákoliv posloupnost ai1, … aik, kde i1 < i2 < … < ik.

Kupříkladu pro n=5 program vygeneruje 1, 4, 5, 2, 3 nebo 3, 2, 1, 4, 5 atd. Nejdelší monotónní podposloupnost má v obou případech délku 3.

Řešení


10-2-3 Turingův stroj (10 bodů)


Turingův stroj sestává z pásky a řídící jednotky. Páska Turingova stroje má jen jeden konec, a to levý (doprava je nekonečná) a je rozdělena na políčka. Na každém políčku se nachází právě jeden znak z abecedy Σ (to je nějaká konečná množina, o které navíc víme, že obsahuje znak Λ). Nad páskou se pohybuje hlava stroje, v každém okamžiku je nad právě jedním políčkem.

Řídící jednotka stroje je v každém okamžiku v jednom stavu ze stavové množiny Q (opět nějaká konečná množina) a rozhoduje se podle přechodové funkce f(q,z), která pro každou kombinaci stavu q a znaku z, který je zrovna pod hlavou, dává uspořádanou trojici (q,z,m), přičemž q je stav, do kterého řídící jednotka přejde v dalším kroku, z znak, kterým bude nahrazen znak z umístěný pod hlavou a konečně m je buďto L nebo R podle toho, zda se má hlava posunout doleva nebo doprava.

Výpočet Turingova stroje probíhá takto: na počátku je hlava nad nejlevějším políčkem, na počátku pásky jsou uložena vstupní data (zbytek pásky je vyplněn symboly Λ) a řídící jednotka je ve stavu q0. V každém kroku výpočtu se Turingův stroj podívá, co říká funkce f o kombinaci aktuální stav + znak pod hlavou, načež znak nahradí, přejde do nového stavu a posune hlavu v udaném směru. Takto pracuje do té doby, než narazí hlavou do levého okraje pásky, čímž výpočet končí a páska obsahuje výstup stroje.

Příklad: Následující tabulka definuje Turingův stroj nad abecedou Σ= {0, 1, Λ}, který ze vstupního slova složeného ze znaků 0 a 1 odstraní všechny jedničky. Počátečním stavem je stav 0, políčka tabulky označená `- - -' nemohou být strojem nikdy dosažena.

     0 1 Λ
0 0,0,R 0,1,R 1,Λ,L
1 1,0,L 2,0,R - - -
2 2,0,R - - - 3,Λ,L
3 1,Λ,L - - - - - -

Úkol: Popište Turingův stroj realizující výpočet součinu dvou čísel. Representaci čísel na pásce stroje si zvolte, jakou uznáte za vhodné.

Řešení


10-2-4 Bynáriho logaritmus (10 bodů)


Představte si Pascal, v němž typ integer může obsahovat až 1024-bitové číslo (alternativně Céčko, kde platí totéž pro typ int). Napište v takovémto jazyce co nejrychlejší program, který pro dané číslo n spočte jeho Bynáriho logaritmus, což je nejmenší číslo k takové, že 2k ≥ n.

K dispozici máte všechny běžné pascalské (resp. céčkovské) operace: sčítání, odčítání, násobení, dělení, bitový and, or, xor i negaci atd.

Řešení


10-2-5 Kostky jsou vrženy (12 bodů)


Známý metrolog baron Bynári přišel s následujícím problémem: máte na stole rovnoramenné váhy a hromadu n kostek. Vaším cílem je z těchto kostek za pomoci zmíněných vah nalézt k nejtěžších.

Navrhněte algoritmus, který bude osobě obsluhující váhy (nečiňmež, prosím, žádné neodůvodněné předpoklady o její inteligenci) diktovat, co má dělat: v každém kroku vypíše čísla kostek, které má osoba dát na levou misku a čísla těch, která má dát na misku pravou. Načež osoba kostky naskládá a odpoví, jestli byla těžší levá miska, pravá miska či obě vyrovnané. Takto algoritmus pokračuje až do okamžiku, kdy si je jist výsledkem.

Příklad: n=3, k=2. První vážení: na levé misce 1, na pravé 2, výsledek L (levá těžší). Druhé vážení: nalevo 1, napravo 3, výsledek: P. Hotovo, nejtěžší je 3 a druhá nejtěžší 1.

Řešení