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

Zadání úloh

11-4-1 Výlet po řece (12 bodů)

Bill Gates po své prezentaci Windows 98 zchudnul. Poté, co exekutoři opustili jeho vilu, zjistil, že mu v pěněžence zbylo N dolarů. Uvědomil si, že za ty peníze může žít maximálně pár dní a pak bude muset žebrat. Protože je Bill neobyčejně hrdý, rozhodl se, že peníze utratí co nejpříjemněji, načež spáchá sebevraždu. A protože Bill už od dětství miluje řeky a vodu a má lítačku na parníky, rozhodl se, že pojede parníkem po řece Mississippi. Řeku Mississippi si můžeme představit jako strom (graf) – místa, kde se stékají dvě řeky jsou uzly (vrcholy grafu) a kořen tohoto grafu je v místě, kde se Mississippi vlévá do moře. Po každé hraně (část řeky mezi dvěmi sousedními soutoky) jedou vždy jednou za den v 10h ráno dva parníky, jeden dolů po řece a druhý nahoru.

Billova cesta po řece bude vypadat, tak, že nasedne u jednoho soutoku na parník, popojede k sousednímu, a protože ten den už mu nikam žádný parník nejede, přespí v tom městě v hotelu a druhý den popojede jiným parníkem (tj. nebude se přece vracet zpátky) na sousední soutok řek. Protože Billa parníková doprava nic nestojí, jediné jeho náklady budou na přespání v hotelech, jejichž ceny se mohou v různých městech lišit. Bill zná ceny hotelů v jednotlivých městech, a protože chce utratit všechny své peníze, zajímá ho, jestli existuje taková cesta po řece, u které součet cen za hotely v uzlech, kterými prochází, je roven přesně N. Jinými slovy, Bill po vás chce, aby jste mu napsali program, který pro vrcholově ohodnocený strom zjistí, zda v tomto grafu existuje cesta mezi dvěma vrcholy, u které suma hodnot vrcholů, jimiž prochází, je rovna danému číslu N.

Řešení

11-4-2 Komplot (10 bodů)

Bylo–nebylo. V jednom z mnoha paralelních vesmírů, v jedné vzdálené galaxii za 109-atero supernovami, 109-atero černými děrami a 109-atero hnědými trpaslíky byla–nebyla jedna malá žlutá hvězda, kolem níž ve vzdálenosti asi tak 150 milionů kilometrů obíhala malá bezvýznamná modrobílá planeta. Na jednom z jejích kontinentů stála malá vesnice, v ní malý domeček, v něm malý stoleček, na stolečku mapa, na mapě jeden z mnoha paralelních vesmírů, v jedné … ehm, takhle bychom se asi moc daleko nedostali…

Tak jinak: Kolem domečku stál plot, který ohraničoval okolní pozemky. A jelikož katastrální úředníci neměli toho času do čeho píchnout, byly hranice pozemku opravdu křivolaké – parcelu nezbývalo než považovat za obecný (tedy ne nutně konvexní) mnohoúhelník a plot za obecnou uzavřenou lomenou čáru, která sama sebe nikde neprotíná.

Napište program, který na vstupu dostane souřadnice jednotlivých zlomů plotu = vrcholů mnohoúhelníka (pozemek je malý, takže pro jednoduchost můžeme předpokládat, že země je plochá) a spočte jeho plošný obsah. Souřadnice budou zadány v pořadí obcházení plotu proti směru hodinových ručiček při pohledu shora.

Řešení

11-4-3 V jámě (10 bodů)

O Praze se říká, že je to nejrozkopanější město na této planetě a názvy některých ulic (Jamská, Na Příkopě, V Jámě, …) se snaží vypovědět, že tomu tak jest už od nepaměti.

Pan N. O'Body, zavilý pragocentrista se rozhodl, že svým přátelům předvede, že tomu tak není. Vytipoval si jednu pražskou ulici a během jedné ze svých dlouhých nedělních procházek si sestavil katalog všech rozkopanin v ní a pokoušel se najít co nejdelší úsek bez děr, kterým by své známé mohl provést, aniž by narazili na příkop, výkop, zákop či jinou silniční singularitu.

Zkuste nalézt algoritmus na řešení tohoto problému: Máte zadanou posloupnost a1,… ,an čísel [nesetříděných!] reprezentujících vzdálenosti jednotlivých děr od pevně zvoleného počátku ulice a nalezněte v této posloupnosti dvě čísla ai, aj taková, že pro žádné k není ai < ak < aj a přitom aj-ai je největší možné. [Nenápadná poznámka: existuje řešení v čase O(n).]

Řešení

11-4-4 Turingovy stroje (10 bodů)

Minule jsme si ukázali, že libovolný "rozumný" programovací jazyk lze přepsat do jednoduchého assembleru, na který nečiní žádné problémy napsat interpreter. Tentokráte zkusíme nalézt ještě jednu možnost zápisu algoritmů, a to jsou Turingovy stroje – "běžnému programátorskému uvažování" jsou sice poněkud vzdálenější, ale o to více se hodí pro různé úvahy o výpočetních možnostech jednotlivých programovacích jazyků.

Definice Turingova stroje (vyskytla se v KSP již jednou v příkladu 10-2-3, takže ti, kdo řešili loňský ročník, ji klidně mohou přeskočit – slibujeme, že jsme nic nezměnili): 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 - - - - - -

Úloha: Dokažte, že pro libovolný program v Pascalu je možno nalézt Turingův stroj, který počítá totéž (to jest zvolíme-li si nějaké kódování čísel na pásce stroje, vydá pro každý vstup stejný výstup jako původní program). Není nutné, abyste psali překládací program nebo přesně rozepisovali překlady jednotlivých operací – stačí dostatečně podrobně popsat myšlenku převodu. (Rada: Zkuste se zamyslet nad minulou úlohou, mohla by vám k tomu dopomoci.)

Řešení