Arktida2024banner2Arktida2024banner2Arktida2024banner2Arktida2024banner2Arktida2024banner2Arktida2024banner2

Aktuální číslo:

2024/12

Téma měsíce:

Expedice

Obálka čísla

Stavy a stavy

 |  9. 9. 2010
 |  Vesmír 89, 503, 2010/9

Kdo nejde vpřed, jde vzad: neexistuje nehybný stav.

V. G. Bělinskij

Bludiště není k chození, nýbrž k bloudění. Chůze bloudícího (říkejme mu bludič) je totiž komplikována tím, že se od něj vyžaduje časté rozhodování, které navíc může být podřízeno nějakému jeho záměru. Třeba se chce dostat k místu, kde čeká odměna (laboratorní potkani to znají), jindy mu jde zase o to, jak z bludiště uniknout. Anebo chce jen tak bloudit. Obecně jsou bludiště docela zajímavé objekty jak pro hádankáře, tak pro matematiky, ba i pro filosofující teoretiky.

Představte si velmi jednoduché bludiště (viz obrázek) a sebe sama v roli bludiče. Je tu ovšem jistá dichotomie perspektiv: buď jste uvnitř a vidíte jen, co máte v přímém dohledu, anebo hledíte na bludiště jakoby shora (jako zrovna teď) a máte je celé před očima. V druhém případě je hledání jednodušší, správnou cestu můžete spatřit takříkajíc na jeden pohled. Tento rozdíl perspektiv (nikoliv prožitků při bloudění) nicméně zaniká, jsou-li bludiště velmi rozsáhlá a složitá.1) U těch už není pohled shora tolik výhodný, cestu lze stěží najít jedním pohledem a nakonec nezbude, než si prstem ukazovat na předpokládanou pozici bludiče (proto zde nebudu obě perspektivy nijak zvlášť rozlišovat).

Právě zmínka o „pozici bludiče“ v předešlé větě může být motivací k dalším úvahám, ale s tím rozdílem, že místo o pozicích budeme mluvit o stavech (uvidíte proč). Řekněme, že každému důležitému místu v bludišti odpovídá jeden stav – za „důležitá“ považujme taková místa, v nichž se bludič rozhoduje, kudy dál (popřípadě, zda se raději nevrátit). Chodby se třeba rozvětvují nebo se otevírá pohled na dosud neznámou část bludiště. Vágnost definice nevadí, stavy lze nasázet i jinam – důležité je, že v každém prostorově omezeném bludišti (našeho typu) vystačíme s konečnou množinou stavů (pro naše bludiště stačí 14). Tato množina tvoří stavový prostor bludiště.

Musím být přesnější: ke stavovému prostoru patří nejen stavy, ale též všechny elementární přechody mezi nimi, odpovídající přípustným pohybům bludiče mezi sousedními místy. Proto mluvíme o prostoru, nikoliv jen o množině stavů.2)

Stavový prostor typu bludiště je velmi speciálním případem daleko obecnějšího pojetí stavového prostoru, jaké je užíváno vždy, když statický (situační, konfigurační) aspekt nějakého systému je svázán s aspektem dynamickým (pohybovým, akčním, evolučním) – prvého aspektu se týkají stavy, druhého přechody. Zde ovšem mluvím výhradně o diskrétních3) stavových prostorech; ty si můžeme vizuálně představovat (a kreslit) jako grafy s vrcholy pro stavy a hranami pro přechody.4)

Typickým problémem u diskrétních stavových prostorů je nalézt (co nejlepší) cestu k nějakému cílovému stavu, popřípadě určit strategii, jak se (co nejlépe) chovat v kterémkoli stavu (šach je dobrým příkladem). S diskrétními a často jen konečnými stavovými prostory se setkáme hlavně v kombinatorické matematice, v teorii automatů5) a algoritmů a v teorii řešení úloh.

V tomto čísle si všimněte článku Radka Pelánka o Hanojských věžích (Vesmír 89, 544, 2010/9). Jde o manipulační hlavolam, jehož stavy odpovídají všem dovoleným rozmístěním různě velkých disků na kolících. Doporučuji si všimnout zajímavého rozdílu mezi stavovým prostorem pro Hanojské věže a pro bludiště. V případě bludiště je stavový prostor přirozeným korelátem reálného geometrického prostoru (v našem případě dvourozměrného) – stavy jsou místa v bludišti a přechody jsou cesty mezi (sousedními) místy. Naproti tomu stavový prostor pro Hanojské věže (viz obr. 2, Vesmír 89, 544, 2010/9) je abstraktní a s reálným prostorem přímo nesouvisí: stavy představují různá rozmístění disků a přechody odpovídají jejich možným změnám.

Abstraktní stavové prostory můžeme konstruovat pro rozličné jiné hlavolamy, skládačky, hry (jako šach) a pro různé mechanické agregáty. Ba i programy pro „inteligentní“ roboty byly již od samého počátku6) založeny na obdobném principu: prostředí, v němž se robot pohybuje a manipuluje s předměty, je charakterizováno množinou „situací“, tj. možných konfigurací předmětů včetně robota samotného. Ten je vybaven repertoárem elementárních „akcí“, pomocí nichž může přesně definovaným způsobem transformovat jednu situaci v jinou tím, že manipuluje s předměty anebo mění svou pozici. Ze známé počáteční situace je pak schopen si „sám“ naplánovat posloupnost akcí k dosažení zadaného cíle.

Podobně jako u Hanojských věží (a jak výše zmíněno, na rozdíl od bludiště) mají abstraktní stavové prostory zpravidla jen velmi málo společného s reálným geometrickým prostorem (což ještě neznamená, že nemají vztah k realitě jako takové – to by však byla už jiná otázka).

Na závěr ještě malý příklad, na němž lze právě ztrátu přímé korelace s reálným prostorem předvést takříkajíc (a vlastně doslova) „v pohybu“. Vzpomeňme na naše bludiště a představme si, že se v něm vedle prvého vyskytne i druhý bludič. Pokud se nebude hýbat, nic se nezmění, bludiště bude mít stejný stavový prostor jako prve. Jakmile se však i druhý bludič začne pohybovat (nezávisle na prvním), nelze než si představit nový stavový prostor, v němž pro každou dvojici pozic bludičů bude existovat jeden (nový) stav. Pokud původní stavový prostor měl (řekněme) n stavů, nový stavový prostor bude mít n × n stavů.7) A co teprve, když bloudících bude velmi mnoho? Formálně trivialita, ale kam se poděla naše jednoduchá reálně geometrická intuice?

Poznámky

1) Připomíná to rozdíl mezi přímým viděním malých počtů a postupným počítáním prvků velkých souborů; psal jsem zde o tom právě před rokem („Vidět počty a čísla“, Vesmír 88, 527, 2009/9).

2) V matematice (hlavně od 20. stol.) ztratilo slovo „prostor“ svůj původní, čistě geometrický nebo fyzikální význam a začalo být užíváno pro daleko obecnější struktury.

3) S konečným nebo spočetně nekonečným počtem stavů.

4) Naproti tomu v teorii dynamických systémů a v matematické fyzice hrají velkou roli kontinuální stavové (či fázové) prostory.

5) Konečné automaty jsou v jistém pohledu totéž co stavové prostory s konečným počtem stavů.

6) Např. program STRIPS ze začátku 70. let. Srov. I. M. Havel, Robotika – úvod do teorie kognitivních robotů, SNTL, Praha 1980.

7) K úvaze na cestu domů: Co když se druhý bludič bude pohybovat extrémně pomalu?

Ke stažení

OBORY A KLÍČOVÁ SLOVA: Matematika
RUBRIKA: Úvodník

O autorovi

Ivan M. Havel

Doc. Ing. Ivan M. Havel, CSc., Ph.D., (11. 10. 1938 – 25. 4. 2021) po vyloučení z internátní Koleje krále Jiřího pro „buržoazní původ“ dokončil základní školu v Praze a poté se vyučil jemným mechanikem. Později však večerně vystudoval střední školu a večerně také automatizaci a počítače na Elektrotechnické fakultě ČVUT (1961–1966). V letech 1969 až 1971 postgraduálně studoval na Kalifornské univerzitě v Berkeley, kde získal doktorát v matematické informatice. Po návratu se v Ústavu teorie informace a automatizace ČSAV zabýval teorií automatů. Z politických důvodů musel ústav v roce 1979 opustit a až do roku 1989 se živil jako programátor v družstvu invalidů META. Nespokojil se však s prací pro obživu. Organizoval bytové semináře, věnoval se samizdatové literatuře. Po sametové revoluci od listopadu 1989 do června 1990 působil v Koordinačním centru Občanského fóra. V polovině roku 1990 se stal spoluzakladatelem a prvním ředitelem transdisciplinárního pracoviště Centra pro teoretická studia UK a AV ČR. Nadále se zabýval kybernetikou, umělou inteligencí a kognitivní vědou, v souvislosti s transdisciplinaritou jej zajímala komplexita, emergentní jevy, vznik vědomí. V roce 1992 se habilitoval v oboru umělá inteligence. Do roku 2018 přednášel na MFF UK. Od srpna 1990 do konce roku 2019 byl šéfredaktorem časopisu Vesmír. Stejně jako v CTS i zde svou zvídavostí i šíří zájmů propojoval vědce, filosofy, umělce. Editoriály, které psal do Vesmíru, daly vznik knihám Otevřené oči a zvednuté obočí, Zvednuté oči a zjitřená myslZjitřená mysl a kouzelný svět. (Soupis významnějších publikací)
Havel Ivan M.

Doporučujeme

Pěkná fotka, nebo jen fotka pěkného zvířete?

Pěkná fotka, nebo jen fotka pěkného zvířete?

Jiří Hrubý  |  8. 12. 2024
Takto Tomáš Grim nazval úvahu nad svou fotografií ledňáčka a z textové i fotografické části jeho knihy Ptačí svět očima fotografa a také ze...
Do srdce temnoty

Do srdce temnoty uzamčeno

Ladislav Varadzin, Petr Pokorný  |  2. 12. 2024
Archeologické expedice do severní Afriky tradičně směřovaly k bývalým či stávajícím řekám a jezerům, což téměř dokonale odvádělo pozornost od...
Vzhůru na tropický ostrov

Vzhůru na tropický ostrov

Vojtěch Novotný  |  2. 12. 2024
Výpravy na Novou Guineu mohou mít velmi rozličnou podobu. Někdo zakládá osadu nahých milovníků slunce, jiný slibuje nový ráj na Zemi, objevuje...