Čtvrtá série čtrnáctého ročníku KSP

Zadání úloh

14-4-1 Povodeň (11 bodů)

Karchamon byl prostým rolníkem hospodařícím na břehu Nilu. Každé jaro jeho políčka zaplavovala řeka a když voda ustoupila, zbyla na jeho políčkách různě velká jezírka vody. Karchamona jednoho dne napadlo, že zachycenou vodu by mohl využít k zavlažování alespoň pro několik následujících týdnů a nemusel by tak nosit vodu přímo z řeky. Aby ale zjistil, jestli se mu vůbec takovéhle zavlažování vyplatí, potřeboval by vědět, kolik vody se zachytí na jeho políčkách. A to je problém, se kterým si Karchamon nevěděl rady. Budete si vědět rady vy?

Vaším úkolem je navrhnout algoritmus a napsat program, který dostane na vstupu N a matici přirozených čísel N×N (hodnoty v matici zachycují výšku terénu na jednotlivých čtverečcích) a spočítá kolik jednotek vody (čtverečky odpovídající prvkům matice mají jednotkové hrany) se v popsaném terénu zachytí (předpokládejte, že terén byl na počátku celý zatopen a že krajina „okolo“ matice má výšku nula).

Příklad: Pro N=4 a terén

4444
3113
3213
4444
je objem zadržené vody 7 jednotek.

Řešení

14-4-2 Posloupnost (10 bodů)

Na vstupu je dána uspořádaná posloupnost celých čísel a1,… ,an. Navrhněte algoritmus a napište program, který zjistí, zda se ve vstupní posloupnosti nachází tři čísla x, x2, x3 a pokud ano, tak je vypíše.

Příklad: Pro vstupní posloupnost -5,-1,2,4,5,7,8,10 jsou hledaná čísla 2,4,8.

Řešení

14-4-3 Koordinátor (12 bodů)

Inženýři společnosti IBM (Interconnected Bloody Machines) vytvořili nový neomylný počítač. Ten se skládá z N výpočetních jednotek (procesorů). Všechny jednotky provádějí ten samý program a vždy na konci výpočtu své výsledky porovnají. Pokud se nějaká z jednotek odchýlí, tak je označena jako vadná a nadále se nebude účastnit výpočtů. Problémem ale je, že v síti musí být jedna „vedoucí“ jednotka – takzvaný koordinátor. Je ovšem poněkud nepraktické, aby když se koordinátor porouchá, tak selhal celý počítač. Proto je třeba navrhnout nějaký postup, jakým se jednotky v síti dohodnou na koordinátorovi. A to je již úkol pro vás.

Máte dáno N – počet výpočetních jednotek (jednotky jako takové ale počet jednotek nevědí!). Každá z jednotek má své unikátní identifikační číslo, které má uložené ve speciální proměnné ID. Jednotky jsou spojeny do kruhové sítě a každá jednotka může komunikovat pouze se svým levým a pravým sousedem. Všechny jednotky začnou ve stejný okamžik vykonávat vámi zadaný program (ten musí být pro všechny jednotky identický). Ten mimo standarních příkazů programovacího jazyka může ještě obsahovat příkazy SendLeft(message), SendRight(message), které pošlou levému resp. pravému sousedovi zprávu message. Dále může obsahovat příkaz Receive(buffer), který první došlou a nezpracovanou zprávu zkopíruje do bufferu. Předpokládejte, že zprávy se neztrácí, dochází v tom pořadí v jakém byly odeslány a že u každé jednotky jsou neomezené fronty na příchozí zprávy. O vzájemné rychlosti výpočetních jednotek však již nemůžete dělat žádné předpoklady. Navrhněte postup (přímo program psát nemusíte), jakým mezi sebou jednotky mají zvolit koordinátora tak, aby bylo celkově vysláno co nejméně zpráv.

Řešení

14-4-4 Triramidy (10 bodů)

Slavný archeolog Bedřich Šílený přišel na stopu jedné dosud nepoznané civilizace. Příslušníci této civilizace byli velmi vyspělí stavebníci. Zajímavé je, že všechny stavby, které byly civilizací postaveny, měly půdorys pravoúhlého rovnoramenného trojúhelníku, jehož odvěsny byly rovnoběžné triběžkami a triledníky (takto pan Šílený pojmenoval souřadnice odpovídající našim rovnoběžkám a poledníkům). Proč měly stavby takový neobvyklý tvar se zatím nikomu nepodařilo zjistit. Bedřich má jednu teorii hodnou svého proslulého jména, ale neodvažuje se ji zveřejnit…Aby si pan Šílený mohl svou teorii ověřit, potřeboval by nalézt největší stavbu. A to je již úkol pro vás.

Navrhněte algoritmus a napište program, který dostane na vstupu letecký snímek oblasti a na výstup vypíše souřadnice rohů největší stavby. Snímek je popsán dvěma čísly M a N (rozměry snímku) a maticí M×N jejíž hodnoty jsou x (místo s troskami budovy) nebo _ (volný prostor). Předpokládejte, že snímek je vyfocen tak, že jeho strany jsou rovnoběžné s triběžkami respektive triledníky. Pozor! Jednotlivé budovy se mohou překrývat.

Příklad: Na snímku 8×5

__x_x___
__xxx_x_
_xxxxxx_
__xxxxx_
__xxxx__
má největší stavba vrcholy v bodech (1,3), (4,3) a (4, 6).

Řešení

14-4-5 Turingovy stroje (10 bodů)

V minulé sérii jste dokazovali, že Turingův stroj s jednou páskou dokáže spočítat přesně ty úlohy, které dokáže spočítat Turingův stroj s více páskami. Co když ale zkusíme možnosti našeho Turingova stroje omezit ještě více? Ukazuje se, že například omezení počtu stavů na dva stále sílu (tedy množinu řešitelných úloh) Turingova stroje nezmění. Také když Turingovu stroji dovolíme v každém kroku udělat pouze jednu z obvyklých činností (tzn. přepsat písmeno, změnit stav, posunout hlavu), zůstává jeho síla nezměněna (pokud bychom ale stroji povolili pouze dva stavy a současně v každém kroku pouze jednu z činností, byla by síla už zmenšena).

Nyní si představme, že Turingův stroj pracuje nad skutečnou děrnou páskou. Ta se vyznačuje tím, že pokud na nějaké políčko zapíšeme znak A, tak na toto políčko už můžeme zapsat pouze znak * (tomuto znaku se říká „kaňka“). Tedy jediné povolené přepisy jsou Λ→A a A→*, kde A∈Σ. Otázkou pro vás je: Může takto omezený jednopáskový stroj vyřešit stejné úlohy jako standardní jednopáskový Turingův stroj? Protože takovýto stroj pochopitelně nemůže zapisovat výstup na místo původního vstupu, bude nám stačit, pokud se výstup vyskytne někde na pásce a ostatní políčka budou zakaňkovaná.

Řešení