Aktuální číslo:

2025/7

Téma měsíce:

Umění

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

Najít své těžiště kontroly

Najít své těžiště kontroly uzamčeno

„Svobodu, nebo smrt je návod, jak vyhrát bitvu, ale zároveň recept na rozchod,“ říká bývalý hlavní armádní psychiatr Jan Vevera. Faktory, které...
Věstonická superstar

Věstonická superstar video

Soška tělnaté ženy z ústředního tábořiště lovců mamutů u dnešních Dolních Věstonic pod Pálavou je jistě nejznámějším archeologickým nálezem...
K čemu je umění?

K čemu je umění? uzamčeno

Petr Tureček  |  7. 7. 2025
Výstižná teorie lidské evoluce by měla nabídnout vysvětlení, proč trávíme tolik času zdánlivě zbytečnými činnostmi. Proč, jako například lvi,...