Druhá série dvacátého šestého ročníku KSP

Termín odeslání Vašich řešení této série jest určen na 9. prosince 2013 8:00. Termín odevzdání CodExové úlohy je pak 10. prosince 2013 8:00. Ř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

V předchozí sérii jste mohli sledovat nouzové přistání vesmírné lodi Freya. Jacob, který přistání přežil, nalezl kus od lodi zdobený oštěp, známku inteligentního života. Vyrazil ho hledat. Najednou ho ale vyrušilo zapraskání za jeho zády …

* * *

Mezi listy zlatě zasvítily dva velké kruhy. Byly to oči nějakého zvířete. K očím patřil i čumák a překvapivě malá hlava. A tělo a čtyři dlouhé nohy. Jacobovi vyskočilo srdce někam do krku.

Nedělal si iluze o tom, že zvíře přišlo, aby se stalo jeho průvodcem po neznámé planetě. Když jako jediný přežijete nouzové přístání vesmírné lodi, je to samo o sobě dost šílené a na další zázrak si obvykle musíte zase chvíli počkat.

Zvíře zatím Jacoba pozorovalo. Možná pozorovalo i kus jeho okolí. Rozhodně se zdálo, že pozorně naslouchá. Aspoň pokud to, co Jacob považoval za uši, skutečně byly uši. Něco tu nesedělo, ale strach nedovolil jeho mozku zabývat se nějakými nepodstatnými nesrovnalostmi. Místo toho se dal na útěk.

Běžel, co mu síly stačily, a litoval, že se nedá vylézt na okolní stromy. Netušil, jestli zvíře zůstalo stát na místě, nebo jestli běží za ním a on ho jen pro svůj vlastní dusot neslyší. Netroufal si ohlédnout se, a navíc, dokud zvíře neviděl, mohl doufat, že tam není.

Najednou vzduch prořízlo nějaké zasvištění. Ani tehdy se Jacob neohlédl, jen si uvědomoval, že ho nic neskolilo, že může běžet dál.

Zastavil se až za hodnou dobu, kdy začal opadávat jeho strach, a s tím mu začaly docházet síly. Našel odvahu ohlédnout se. Po zvířeti nebylo ani vidu. Jacob si nebyl úplně jistý, že trefí zpět, ale pro tuhle chvíli se rozhodl doufat, že cestu najde.

Začal se zase soustředit na svůj původní plán, totiž hledat místní inteligentní život. Pozorně se rozhlédl po okolí. A zděsil se.

Teprve teď si všiml, že kus od něj jsou volně natažené dva provazy, které se do sebe navíc poněkud zamotaly. Byl div, že se o ně při svém úprku nepřerazil. Jacob se k nim sehnul, aby je mohl prozkoumat blíž.


26-2-1 Zamotané provazy (7 bodů)


Jednoduchá úlohaV pralese jsou volně natažené dva provazy, které se do sebe zamotaly. Provazy jsou pevně uvázané na dva stromy, první provaz níž a druhý výš. Žádný z nich se nikde nevrací. Může to tedy vypadat třeba takto:

Příklad k 26-2-1

O každém překřížení víme, který z provazů je vpředu. Chceme zjistit, jestli je možné provazy rozmotat bez toho, aby bylo nutné některý z nich odvazovat.

Program dostane na vstupu číslo N udávající počet křížení a N čísel 1 nebo 2 udávajících, který provaz je vpředu (na stromech je provaz 2 vždy uvázaný nad provazem 1). Odpovědět má ano, nebo ne, podle toho, zda je provazy možné rozmotat.

Příklad (odpovídá obrázku):

4
1 2 2 1
Odpovědí je ano, jelikož provazy rozmotat jdou.

Řešení

Při zkoumání provazů Jacob najednou zahlédl mezi stromy jakýsi barevný záblesk. Pouhým pohledem se mu nedařilo zjistit víc, a tak se s patřičnou obezřetností vydal tím směrem. Jak se přibližoval, měnily se občasné záblesky v barevnou plochu prosvítající mezi stromy.

Konečně se Jacob dostal až k ní. Ocitl se na něčem, co snad mohlo připomínat mýtinku, ovšem po stromech ani trávě tu nebyly vůbec žádné stopy. Teď už Jacob viděl, že trojúhelníkovou barevnou plochu tvoří zvláštní hexagonální kameny, některé červené, některé do žluta.

Zdálo se, že je kdosi naskládal do mnoha vrstev, kterými pečlivě vyplnil hlubokou jámu; několik dalších kamenů se válelo v nejbližším okolí. V jednom z nich byl vyrytý podivný nápis:

Jacob si všiml, že jedna z barev spojuje všechny tři strany trojúhelníku, a napadlo ho, jestlipak je to tak i ve vrstvách, které nevidí.


26-2-2 Barevný trojúhelník (8 bodů)


Máme rovnostranný trojúhelník o hraně N tvořený hexagonálními kameny dvou barev.

Dokažte, že v trojúhelníku existuje jednobarevná souvislá plocha, ve které se nachází alespoň jeden kámen z každé strany trojúhelníku. Kameny ve vrcholech patří do dvou stran zároveň.

Příklad takového trojúhelníku si můžete prohlédnout na obrázku. Barvou, která spojuje všechny tři strany, je zde šedá.

Příklad k 26-2-2

Řešení

Protože se začalo připozdívat, rozhodl se Jacob brzy pokračovat dál. Kamenný trojúhelník mu nyní sloužil jako dobrý orientační bod, a on se vypravil směrem dál od jednoho z jeho vrcholů.

Po nějaké době došel k místu, kde se prales najednou začal rozestupovat. Vzniklý výhled odhalil krom jiného to, že tato část pralesa je mírně vyvýšená nad okolím – zdola musel být nahoru opravdu impozantní pohled.

O kus dál uviděl Jacob řeku. To ho potěšilo, neboť pokud se tu dá spoléhat na podobné věci jako na Zemi, mohl by ji sledovat a dojít po jejím proudu k nějaké civilizaci.

Zdálo se ovšem, že terén je všelijaký a některá místa by mohla cestu hodně zpomalit. Musel si ji proto dobře rozmyslet.


26-2-3 Plánování cesty (10 bodů)


Praktická CodExová úlohaJacob se chce co nejrychleji dostat k řece. Terén, přes který musí projít, si lze představit jako čtvercovou síť o rozměrech R ×S. V některých oblastech je tento terén dost nepříjemný, a tak přes některá políčka trvá průchod delší dobu, některá jsou dokonce zcela neprůchozí.

Průchod přes oblast ležící na souřadnicích i, j trvá ti, j. Přecházet mezi políčky je možné pouze vodorovně nebo svisle (šikmo ne).

Vaším úkolem je najít nejrychlejší cestu.

Tato úloha je praktická a řeší se ve vyhodnocovacím systému CodEx. Přesný formát vstupu a výstupu, povolené jazyky a další technické informace jsou uvedeny v CodExu přímo u úlohy.

Řešení

Jacob cestu naplánoval, jak nejlépe uměl. Dál byl ovšem rozhodnutý vyrazit až ráno. Přeci jen není nejrozumnější pohybovat se unavený někde, odkud můžete spadnout. Teď si raději opatřil provizorní přístřešek. Chvíli se ještě podivoval nad tím, jak jasná je noc, a pak se uložil ke spánku.

* * *

Ráno se Jacob vzbudil brzy. Pobalil si svých několik věcí a odhodlaně vyrazil na cestu. Terén tu byl skutečně všelijaký, místy příjemně ušlapaná hlína, místy skoro bažiny, mezitím ledacos jiného, ovšem připravená trasa se vcelku osvědčila. Mohlo být krátce po poledni, když Jacob dorazil k řece.

V jednom kameni u břehu byl opět vyrytý podivný nápis:

Ještě víc ovšem Jacoba zaujaly podivné kostky na protějším břehu. Vypadaly trochu jako dětské dřevěné kostičky, jen o mnoho větší. A zdálo se, že z nich někdo chce podobně jako z kostiček pro děti postavit velkou věž.


26-2-4 Stavba věže (10 bodů)


Někdo se z K kostek snaží postavit věž. Všechny kostky jsou stejně velké, ale každá kostka má svoji váhu wi a nosnost i. Nosnost i znamená, že i-tá kostka unese na ní stojící kostky o maximální celkové váze i, jinak se zbortí a věž spadne.

Zajímá nás, jestli lze postavit věž ze všech K kostek. Věž stavíme tak, že přímo na sebe pokládáme jednotlivé kostky (můžete si představit i to, že stavíme komín).

Lehčí variantaLehčí varianta (za 3 body): Vyřešte úlohu za předpokladu, že všechny kostky mají váhu w = 1.

Řešení

Stavba, ať už měla být v budoucnosti čímkoli, byla zrovna opuštěná. Jacob se tedy vydal dál po proudu řeky. Cestou občas potkal nějaký ten nápis na kameni, stále se mu v nich ale nedařilo odhalit žádný smysl.

Po několika nápisech a mnoha krocích se před Jacobem najednou objevila malá věžička. Nebo alespoň malá na místní poměry. Jak už Jacob očekával, stál před ní kámen s nápisem:

Věžička neměla okna, měla ovšem dveře. Po troše váhání si Jacob dodal odvahy a zkusil dveře otevřít. Šlo to překvapivě lehce. Jako první zaznamenal směs různého hučení a bzučení. Pak teprve s jistou úlevou zjistil, že vevnitř nikdo není.

Původcem podivných zvuků se ukázaly být jakési krabičky. Byly na sobě různě zavěšené, celá konstrukce byla navíc uchycená ve věžičce. Jacob se ale nemohl ubránit dojmu, že konstrukce už nemůže dlouho vydržet. Ačkoli si nebyl jistý, jestli je to dobrý nápad, rozhodl se jí pomoci tím, že ji vyváží.


26-2-5 Vyvažování (12 bodů)


Kuchařková úlohaOčíslované krabičky jsou zavěšené ve věžičce, hrozí ale, že celá konstrukce spadne. Chceme ji proto vyvážit. Podle piktogramů na zdech víme, že je potřeba zachovat určité pořadí krabiček na konstrukci. Celou úlohu si tak můžeme představit jako vyvažování binárního vyhledávacího stromu.

Na vstupu máme obecný binární vyhledávací strom (jeho definici naleznete v kuchařce) a chceme z něj udělat dokonale vyvážený binární vyhledávací strom. Pro každý vrchol výsledného stromu tedy musí platit, že rozdíl velikostí jeho levého a pravého podstromu je nejvýše 1.

Konstrukce už drží jen silou vůle, takže požadujeme, aby váš algoritmus pracoval s lineární časovou složitostí. Počet bodů, které dostanete, bude záviset na prostorové (paměťové) složitosti vašeho řešení. Nějaké body dostanete i za lineární, na plný počet ale potřebujete konstantní složitost.

Řešení

Po práci si Jacob udělal pauzu na svačinu. Bylo pomalu vhodné začít myslet na návrat, ale on chtěl ještě pokračovat ve svém pátrání. Usoudil, že alespoň do večera může jít dál, a pak se uvidí.

S plnějším žaludkem se pak Jacob vypravil opět po proudu řeky. Tentokrát ovšem potkal něco zajímavého mnohem dřív. Došel totiž k něčemu, co se snad dalo považovat za brod.

Tradičně tu potkal vyrytý nápis, tentokrát dost složitý. Po chvilce jeho zkoumání Jacob pojal podezření, že znaky, které už nějakou dobu potkával na kamenech u břehu, jsou zkratkou nějakého názvu. Studoval další slova na kameni a přemýšlel, která z nich by také mohla být názvy a mít nějakou svoji zkratku.


26-2-6 Zkratky míst (12 bodů)


Máme podezření, že pro názvy míst se používají třípísmenné zkratky, a máme také seznam slov, o kterých si myslíme, že by mohly být názvem nějakého místa.

Zkratka má první písmeno vždy stejné, jako je první písmeno názvu daného místa, a zbylá dvě písmena jsou libovolná dvě písmena z názvu místa ve správném pořadí. Název Praha tak lze zkrátit např. na PRH nebo PHA, ale už ne na PHR nebo RHA.

Vaším úkolem je zjistit, pro která všechna slova bychom skutečně uměli takovou zkratku najít. Zkratky míst musí být navzájem jedinečné, chceme jich ale najít co nejvíce. Je-li možných řešení se stejným počtem nalezených zkratek víc, vypište libovolné z nich.

Příklad:

Vstup:			Výstup:
Pra			Pra	PRA
Praga			Praga	PAA
Prak			Prak	PAK
Prk			Prk	PRK
Prkg			Prkg	PRG
Pak			Prague	PGU
Prague

Řešení

Jacobovi se povedlo překonat řeku a dostat se na druhý břeh. Před ním začínalo něco, co silně připomínalo cestičku. Zhluboka se nadechl a pak po ní vyrazil.

Cestička chvíli vedla skoro podél řeky, pak se od ní ovšem prudce odklonila a zavedla Jacoba za hradbu stromů. Nebyly to stejné stromy jako v pralese, ale podobně jako ony byly vysokánské a měly o trochu jinou barvu, než by člověk čekal na Zemi.

Jacob se rozhlédl kolem sebe a bezděky zatajil dech. Našel, co hledal! Byl tu inteligentní život, byl tady, přímo před ním.

Tvorové byli vlastně podobní lidem. Byli vyšší, Jacob by vedle nich vypadal jako malé dítě. Podobně jako zvíře minulý den měli překvapivě malou hlavu a naopak nezvykle velké oči. Barvou kůže připomínali spíše pozemšťany, kterým zrovna není dobře od žaludku. Ale bez nejmenších pochyb to byli představitelé místního inteligentního života.

Skupinka tvorů se zrovna motala kolem obrovského kmene stromu, který zřejmě pocházel z pralesa.


26-2-7 Čištění kmene (13 bodů)


Humanoidní tvorové čistí kmen stromu. Celkem se práce účastní T tvorů. Na kmeni je M míst, která je potřeba očistit. Každé takové místo je na nějaké pozici mi (to může být třeba vzdálenost od konkrétního konce kmene; pozice bude vždy celočíselná).

Na začátku stojí j-tý tvor na pozici tj. Práce tvorů probíhá v jednotlivých krocích: v každém kroku se každý tvor (nezávisle na ostatních) může přesunout o jednu pozici vlevo, vpravo, nebo může zůstat stát na místě.

Očištění části kmene, nad kterou tvor stojí, je bleskové (proběhne ve stejném kroku, kdy tvor k této části kmene dojde). Speciální výjimkou je počáteční pozice každého tvora. Ta je očištěná ještě před tím, než tvor udělá první krok.

Zajímá nám nejmenší počet kroků potřebný k očištění celého kmene.

Při řešení můžete předpokládat 1 ≤ M, T ≤ 100 000 a 1 ≤ mi, tj ≤ 1 000 000 000.

Příklad: Mají-li se zkontrolovat místa 2, 5, 6 a tvorové stojí na pozicích 3, 5, zvládnou kmen očistit na 1 krok. Kdyby stáli na 3, 4, budou kroky potřebovat 2.

Řešení

Když se před ním tvorové vynořili, nebyl si Jacob najednou vůbec jistý, co by vlastně měl udělat. Pozoroval skupinku, všiml si také kdesi za nimi ďolíků v zemi, všiml si, že v jednom z nich zmizel stejný tvor.

Najednou se ozval výkřik. Jacob se polekaně rozhlédl. Někdo si ho zřejmě všiml a upozornil na něj ostatní. V té chvíli se na něj upřely pohledy všech tvorů.

Pokračování příště…

První Jacobovy kroky po neznámé planetě s vámi sledovala

Karolína „Karryanna“ Burešová


26-2-8 Továrna na přepisování (14 bodů)


SeriálV prvním díle letošního seriálu jste se mohli seznámit s Turingovými stroji coby zajímavým teoretickým modelem počítače. Dnes v naší zoo výpočetních modelů popojdeme k sousednímu výběhu, kde se pasou přepisovací pravidla. Ne nadarmo jsou hned vedle – časem uvidíme, že si spolu tahle dvě zvířátka náramně rozumějí.

Abeceda a vstup s výstupem

Jak už název napovídá, přepisovací pravidla pracují nad nějakým zadaným řetězcem znaků (říkejme mu vstup) a postupně ho nějak přepisují, až dostanou nějaký další řetězec znaků (výstup). Než začneme mluvit o samotných pravidlech, pojďme tyto řetězce pořádně definovat.

Za abecedu budeme označovat konečnou množinu všech znaků, které se mohou vyskytnout v řetězci. Vstupvýstup jsou pak vždy nějaké konečné řetězce znaků z této abecedy.

Mimo to zavedeme dva metaznaky, kterými budeme označovat okraje řetězce: ^ na začátku a $ na konci řetězce. Tyto znaky nebudou součástí abecedy, a tedy se nebudou vyskytovat nikde jinde než právě na okrajích řetězce. (Podobnost s regulárními výrazy používanými v praxi vůbec není náhodná. Chcete vědět víc? Nahlédněte do seriálu 23. ročníku.)

Abecedou mohou být například čísla 0-9, písmena a-z, nebo třeba { , ♠, ♣, }. Jednotlivé úlohy pak mohou navíc určit, že ve vstupu nebo výstupu se smí vyskytovat jen některé znaky abecedy.

Přepisovací pravidla

Každé přepisovací pravidlo má svou levou a pravou část: levé části budeme říkat vzor a pravé přepis. Zapisovat ho budeme takto:

vzorpřepis

Ve vzoru se mohou kromě znaků abecedy vyskytovat i metaznaky začátku a konce řetězce (pak se vzor váže k nějakému z okrajů řetězce), v přepisu se už mohou vyskytovat jen znaky abecedy.

Aplikace konkrétního pravidla na nějaký řetězec pak vypadá následovně:

  • Najde se první (nejlevější) výskyt vzoru v řetězci.
  • Tento výskyt se vymaže a na jeho místo se vloží přepis.

Pravá strana (přepis) může být i prázdná. Takové pravidlo lze například využít k vymazání části vstupu. Vzor naopak prázdný být nemůže, vždy musí obsahovat alespoň jeden znak nebo metaznak.

Uvažme například následující pravidla:

a b
a$ b
^aa ccc

Každé samostatně aplikujeme na vstup baa. První pravidlo ho přepíše na bba, druhé na bab a třetí pravidlo nic nepřepíše (takovýto vzor ve vstupu neexistuje, a tedy se nic neprovede).

Samostatnou aplikací pravidel ovšem dost silný výpočetní model nedostaneme. Na to bude potřeba poskládat více pravidel dohromady.

Přepisovací programy

Přepisovacím programem nazveme nějaký uspořádaný soubor přepisovacích pravidel, čili několik pravidel seřazených za sebe.

Výpočet přepisovacího programu probíhá v krocích: první krok přepisuje vstup programu, výstup prvního kroku se stane vstupem druhého, a tak stále dokola. Výpočet končí ve chvíli, kdy již mezi pravidly neexistuje žádné, jehož vzor by se vyskytoval ve vstupu. To se samozřejmě nemusí stát – jistě snadno vymyslíte přepisovací program, který se nikdy nezastaví. (Jednou z možností je třeba program skládající se z jediného pravidla $a. Ten nikdy neskončí, protože vzor pravidla je obsažen v každém řetězci.)

Výpočet každého kroku by se dal formálně popsat takto:

  • Najde se první pravidlo, jehož vzor se vyskytuje někde ve vstupu.
  • Toto pravidlo se provede (najde se první výskyt vzoru ve vstupu a na jeho místo se vloží přepis).
  • Výstup tohoto pravidla se použije jako vstup dalšího kroku. Výpočet dalšího kroku začíná opět od prvního pravidla a od začátku řetězce.

Zbývá zavést nějakou míru efektivity – analogii časové složitosti normálních programů. Nám pro tyto účely bude sloužit počet provedených kroků přepisovacího programu. (Na zamyšlení: co by odpovídalo prostorové složitosti?)

Příklady

Pojďme vyzkoušet, co přepisovací programy dovedou.

První příklad bude jednoduchý. Představte si, že máme zadanou posloupnost nul a jedniček (třeba 01101) a chceme ji setřídit. Jinými slovy chceme přesunout všechny nuly nalevo od jedniček.

To půjde překvapivě snadno. Sestrojíme program obsahující jediné pravidlo:

1001

Na našem ukázkovém vstupu bude výpočet probíhat takto: 01101, 01011, 00111.

Povšimněme si, že dokud posloupnost není setříděná, existuje v ní aspoň jedna po sobě jdoucí dvojice 10, takže program běží dál.

Doběhne někdy? Sledujme inverze v posloupnosti: tak budeme říkat dvojicím (ne nutně sousedních) čísel, která jsou ve špatném pořadí. Naše ukázková posloupnost obsahuje 2 takové dvojice. Každé použití pravidla sníží počet inverzí právě o jedna, takže se program po konečně mnoha krocích musí zastavit.

Jak dlouho náš program poběží? Ve vstupu délky n může být nejvýše (n/2)2 inverzí (to odpovídá situaci, kdy na vstupu máme n/2 jedniček a za nimi n/2 nul) a program je odstraňuje po jedné, takže provede řádově n2 kroků. (Mimochodem, pokud budeme provádět chytřejší operace než pouhé prohazování, je možné dosáhnout i lepší efektivity. Zkuste vymyslet, jak.)

Druhý příklad už bude záludnější. Možná si vzpomínáte na kontrolu správnosti uzávorkování z minulé série. Pojďme si ukázat, jak snadno se dá vyřešit pomocí přepisovacích pravidel.

Na vstupu budeme mít posloupnost levých a pravých závorek a naším úkolem bude rozhodnout, jestli tvoří správné uzávorkování, nebo netvoří. Podle toho vrátíme na výstupu buď ANO, nebo NE. Pro připomenutí, správné uzávorkování je takové, ve kterém jsou závorky správně spárované a páry se nekříží.

Idea našeho přepisovacího programu bude takováto: Všimneme si, že se v každé neprázdné správně uzávorkované posloupnosti vyskytuje po sobě jdoucí dvojice (). Tu můžeme odstranit, čímž získáme další správně uzávorkovanou posloupnost, a tak dále, až nakonec dospějeme k prázdné posloupnosti. Funguje to i naopak: přidáním () do jakéhokoliv správného uzávorkování nelze získat nesprávné, takže se nemůže stát, že bychom na prázdný řetězec zredukovali nějaké nesprávné uzávorkování.

Program vypadá následovně:

X$ NE
X( X
X) X
()
^$ ANO
^( X
^) X

Dokud vše probíhá tak, jak má, čtvrté pravidlo umazává závorky. Pokud umaže všechny závorky, páté pravidlo vypíše ANO. Pokud ale již nebude možné umazat žádnou dvojici závorek, nastoupí jedno z posledních dvou pravidel a na scénu přijde X. To pak za pomoci prvních tří pravidel vymaže zbytek vstupu, vypíše NE a program se zastaví.

Rozmyslete si, proč namísto posledních dvou pravidel nemůžeme použít ^ X. (Správná odpověď je, že pak by se nám program nikdy nezastavil, protože vzor takového pravidla by byl nalezen vždy.)

Úlohy

Vymyslete přepisovací programy na následující problémy. U všech programů odhadněte efektivitu (v počtu provedených kroků) a pokuste se o co nejlepší. Součástí řešení by měl být slovní popis a alespoň náznak zápisu použitých přepisovacích pravidel.

Úkol 1 [2b]

Vstup je tvořený posloupností čísel 0 až 9. Vaším úkolem je zanechat na výstupu ANO, pokud je posloupnost čísel neklesající, a NE v opačném případě.

Úkol 2 [3b]

Na vstupu je posloupnost znaků *. Spočítejte, kolik jich je, a výsledek zanechte na výstupu jako číslo ve dvojkové soustavě.

Úkol 3 [5b]

Na vstupu jsou dvě čísla ve dvojkové soustavě oddělená křížkem #. Na výstupu nechť se objeví to větší z nich. Pozor, zápisy čísel nemusí být stejně dlouhé. Případ, kdy jsou si čísla rovna, nemusíte uvažovat.

Převod na Turingův stroj a naopak

Jak už jsme zmínili v úvodu, přepisovací pravidla a Turingovy stroje spolu úzce souvisí. Ukážeme, jak převést jakýkoli přepisovací program na Turingův stroj.

Nejdříve se zamyslíme, jak převést jedno přepisovací pravidlo do řeči Turingova stroje. Začneme s hlavou na levém konci pásky a budeme se postupně pokoušet najít výskyt vzoru (vyzkoušíme všechny začátky a vždy porovnáme se vzorem; stav stroje bude říkat, kolikátý znak vzoru porovnaváme).

Ve chvíli, kdy nalezneme první výskyt, přepneme se do dalšího stavu a pásku přepíšeme odpovídajícím přepisem (a případně odsuneme či přisuneme zbytek znaků na pásce, pokud přepis bude mít jinou délku než vzor). A nakonec, po dokončení přepisování, vrátíme hlavu opět na začátek pásky (a stejně tak v případě, že se nám nepovede najít žádný výskyt vzoru).

Tím jsme úspěšně naučili Turingův stroj zpracovat jedno pravidlo. K překladu celého přepisovacího programu už zbývá jen krůček. Každé pravidlo v programu bude mít svou vlastní sadu stavů (sady nechť jsou třeba očíslované). Po úspěšném provedení pravidla a návratu hlavy zpět na začátek pásky se přesuneme do první sady; po neúspěšném hledání vzoru se přesuneme do následující sady (zkusíme aplikovat další pravidlo v pořadí). Pokud budeme neúspěšní i u posledního pravidla, ukončíme výpočet.

Právě jsme dokázali, že každý přepisovací program lze simulovat Turingovým strojem. Pokud navíc ukážeme, že každý Turingův stroj lze převést na přepisovací program, bude jasné, že oba výpočetní modely jsou stejně silné (co jde spočítat v jednom, jde i ve druhém a opačně). To už ale bude na vás:

Úkol 4 [4b]

Dokažte, že pro každý jednopáskový Turingův stroj existuje přepisovací program, který počítá totéž. Přesněji řečeno, pokud se pro daný vstup Turingův stroj zastaví, přepisování se také zastaví a vydá stejný výsledek. Pokud se stroj nezastaví, přepisování se také nezastaví. Rozmyslete si, v jakém vztahu je časová složitost stroje a pravidel. Svůj přístup demonstrujte na stroji z příkladu v 1. sérii (vyvážená posloupnost).

Jirka Setnička & Martin „Medvěd“ Mareš

Řešení