Modelování hodnotového toku MHTOK, 2. Matematické a fyzikální modely
David Kruml
8.10.2024
Mapovaní hodnotového toku
► Schéma receptury nebo výroby, jak jsme v předešlém chápali (procesy, zásobníky, kanály).
► Cílem bývá i zpětné porozumění probíhající výrobě (nalezení vazeb).
► Drobné odlišnosti v označení (trojúhelníky pro zásobníky), další symboly (brýle, autíčko, blesk, ...).
► Naopak se moc neřeší obsazení procesů stroji a lidmi (podobně jako u původního MRP).
► Je snaha doplnit k prvkům sítě číselné parametry.
Petriho sítě
► Pořád víceméně totéž (procesy, zásobníky, kanály).
► Abstraktní struktura, řeší se otázky průtoku sítí.
► Položky (výrobky, stroje) reprezentují žetony (tokens).
► Proces (znázorněný jen jako čára) je odpálen (fired), pokud je ve vstupních zásobnících potřebné množství žetonů (to se pro hodnoty 7^ 1 obvykle píše ke kanálům = kapacita kanálu).
► Po odpálení procesu se odmažou použité žetony ze vstupních zásobníků a připíšou nové do výstupních zásobníků.
► U časovaných Petriho sítíse definuje časová náročnost procesu (tak jak to uvažujeme my). Na rozdíl od „obyčejných" Petriho sítí se neřeší tahy, ale celkový čas.
► Logiku sítě lze upravovat zařazením booleovských zásobníků.
Cvičení: Rozmyslete si modelování obvyklých situací Petriho sítí, zejména cyklus a řízení tahem.
Příklad odpálení procesu
kola
podvozky
kola
podvozky
Relační implementace časované Petriho sítě
► Tabulka procesů — parametrem časová náročnost.
► Tabulka zásobníků — hodnota zásoby, případně omezení.
► Tabulka kanálů — index procesu, index zásobníku, orientace, kapacita (dávka).
rafový model
► Hovořili jsme už možnosti interpretovat výrobní síť v jazyce teorie grafů, kde např. zásobník = vrchol, proces = orientovaná hrana.
► Toto pojetí přestává fungovat u větvených procesů (více vstupů nebo výstupů), ale zatím se ho ještě držme.
► Teorie grafů řeší řadu kapacitních problémů — minimální cesta, kritická cesta, maximální tok.
► Od grafů lze snadno přejít ke kategoriím, které přináší možnost kompozice (agregace procesů) a s další strukturou vyřeší i potíže s větvenými procesy.
Definice kategorie
► Kategorie sestává z objektů (teček) a morfismů (šipek).
► Každá šipka spojuje dva objekty — svůj domain a codomain.
► Je-li A objekt, existuje identický morfismus id/\ — l/\ . A A.
► Jsou-li >A, ß, C objekty a ŕ: A ^ B,g : B —± C morfismy, existuje složený morfismus g o f = gf = f; g \ A —> C (jen různé typy značení).
► Skládání je asociativní: f(gh) = (fg)h.
► Složení s identitou je očekávané: ŕid/\ — f — idßr.
Příklady kategorií
► Set — objekty = množiny, morfismy = zobrazení, skládání.
► Rel — objekty = množiny, morfismy = binární relace.
► Vect — objekty = vektorové prostory, morfismy = lineární zobrazení.
► Kategorie, jejíž objekty jsou množiny, se nazývají konkrétní. (Lidé často zapomínají, že jsou i nekonkrétní kategorie.)
► Každá tranzitivní a reflexivní relace p na množině A je kategorií. Objekty jsou prvky A, morfismy jsou prvky p. Reflexivita zaručí identity, tranzitivita skládání.
► Speciálně každá uspořádaná množina je kategorií.
► Tyto kategorie jsou tzv. tenké— mezi dvěma objekty existuje nejvýše jeden morfismus v každém směru. (Kategorie obecně mívají mezi objekty více morfismů.)
► Vyhýbáme se „filozofické diskuzi", co má být ještě množina a co už třída.
Využití kategorií
► Teorie kategorií má ambice být základní matematickou teorií jako alternativa k teorii množin.
► Nestuduje „vnitřek" objektů, ale jejich vnější interakce vyjádřené morfismy. Např. podmnožinu lze definovat vlastnostmi zobrazení vložení, aniž bychom mluvili o prvcích.
► Konstrukce a způsob myšlení je od „klasického" docela odlišný. Posměšný název „abstraktní nesmysl".
► Základy položeny v polovině 20. století při studiu algebraické topologie (S. Eilenberg, S. Mac Lane), praktické aplikace přišly mnohem později (funkcionální programování, kvantové procesy, ...).
► Z teorie kategorií využijeme víc jazyk a základní konstrukce než hluboké výsledky.
► Hodí se k pohledu na procesy jako na černé skříňky.
► Doporučení pro začátečníky: veškeré pojmy a konstrukce si nejprve představujte na uspořádané množině, pak v Set nebo jiné pěkné kategorii, pak obecně.
► Diagramem v kategorii (prozatím neformálně) rozumíme schéma (i opakujících se) objektů spojených morfismy z této kategorie.
► Např. nechť A = {1,2, 3}, B = {a, b}, f (1) = a, f(2) = a, f(3) = = a,ř(2) = b,g(3) = b. Pak
f     g L B^A, A^B
g
jsou diagramy v Set.
► U diagramů často požadujeme komutativitu — pokud je mezi dvěma objekty více cest, chceme, aby složením byl stejný morfismus. (To je u tenkých kategorií banální, jinde ne.)
► V příkladu je první diagram komutativní (není co kontrolovat), druhý není (f ^ g).
Limita diagramu
► Snažíme se doplnit diagram dalším objektem spolu s morfismy do všech objektů diagramu, aby s diagramem komutovaly.
► Pokračování příkladů:
A —»• B
T
l /
l /
C --> A
D
► Limitou rozumíme univerzální řešení úlohy ve smyslu, že všechna ostatní řešení se přes limitu faktorizují (viz dolní závory a infimum v uspořádaných množinách).
c--> C
► V diagramech z příkladu dostáváme limity
C = {(1,1), (2,1), (3, 2), (3, 3)} spolu s projekcemi na A, resp. D = {1,3} spolu s vložením do A, morfismy do B se v obou případech snadno dopočítají složením.
Oblíbené diagramy a jejich limity
A
^ C
A      B B B
ekvalizátor součin pullback
► Věta: Má-li kategorie všechny součiny a ekvalizátory, pak má všechny limity.
► Princip duality: Otočením všech morfismů dostáváme opět kategorii, tzv. duální kategorii. Pomocí duální kategorie snadno zavedeme duální pojem k limitě — kolimitu.
► Kolimity duální k ekvalizátoru, součinu a pullbacku se nazývají koekvalizátor, součet (koprodukt) a pushout.
Cvičení: Rozmyslete si základní typy limit a kolimit ve Vect1
Existence limit a kolimit
Věta: Má-li kategorie všechny součiny (i nekonečné) a ekvalizátory, pak má všechny limity.
Důsledek: (z duality) Má-li kategorie všechny součty a koekvalizátory, pak má všechny kolimity.
Limita se obvykle realizuje jako podstruktura součinu objekt diagramu, kolimita jako faktorstruktura sjednocení/součtu.
Funktor
► Funktor je analogie homomorfismu (v algebře a jinde), tj. strukturu zachovávající zobrazení. Nyní jde o zobrazení mezi kategoriemi.
► Přesněji, funktor F : /C —> C tvoří dvojice zobrazení, z nichž jedno přenáší objekty a druhé morfismy. Píšeme např. A^ FA,f ^ Ff.
► Požadujeme:
► zachování domainů a codomainů: Je-li f : >4 —>* B morfismus v K,, zobrazí se na morfismus Ff : FA —>► FB v £.
► zachování identit: Fidy\ = id^.
► zachování skládání: F(gf) = (Fg)(Ff).
► Příklady: Funktor mezi dvěma uspořádanými množinami je právě izotonní zobrazení. Vložení Set do Rel je funktor. Zapomenutí struktury F : Vect —> Set je funktor.
Poradná definice diagramu
► Diagram v kategorii K je funktor D : V K.
► Zde V je „čisté strukturní schéma", jemuž D přiděluje „konkrétní obsah" z /C.
► Ve výrobě může V odpovídat „čisté receptuře", které přidělíme funktorem D určitou procesní realizaci.
► Tyto realizace jsou popsány kategorií/C, která by měla zahrnovat veškeré možné stavy/zdroje (jako objekty) a procesní změny mezi nimi (jako morfismy).
► Konstrukce může připomínat ohodnocení nebo obarvení grafu. (/C jsou „barvy".)
► Rádi bychom všechny datové manipulace s tokem viděli jako funktory.
Příklad: faktorizace iterovaného procesu
„Namotání" iterovaného procesu do smyčky je funktoriální:
S'
S<
S
SO P
s<
s<
Obě situace jsou diagramy odkazující na S,p a lze je komutativně propojit morfismy (zde dokonce identitami). Konstrukce odpovídá tzv. přirozené transformaci (možná později).
Feynmanovy diagramy v časticové fyzice
manový diagramy, komentáre
► F. d. vyjadřují interakce elementárních částic.
► Pohyb částice je reprezentován orientovanou čarou v časoprostoru.
► Antičástice se pohybují proti směru času
(Feyn ma nova-Stúckel bergova i nterpretace).
► Vznik nových částic spojením nebo jejich rozpad odpovídá interakci zdrojů v procesu.
► Na pohyb každé částice můžeme nahlížet jako na proces. F. je další možností, jak znázornit tok.
► V kvantové fyzice dochází k provázání stavů (entanglement) kdy částice sdílí stav i po odloučení (nelokalita). To je silně neinuitivní vlastnost, vede k různým „paradoxům" a revolučním technikám (kvantová teleportace, algoritmy, šifrování).
nzorový součin
► Stavy v kvantové mechnice jsou popsány jako jisté vektory komplexních vektorových prostorů.
► Provázání si vynucuje konstrukci prostorů složených stavů pomocí tenzorového součinu.
► Tenzorový součin je něco jiného než kartézský součin. Dimenze činitelů se násobí.
► Vlastnosti tenzorového součinu lze formalizovat i kategoriálně. Výsledkem (pro rozumné požadavky) jsou tzv. monoidální kategorie.
► Přesným popisem se nebudeme zdržovat, tenzorový součin využijeme jen jako „jazykový prostředek" pro sdružování zdrojů a paralelních procesů.
► Tenzorový součin se zavádí pro objekty i morfismy.
Co tenzorový součin umí
► Sdružení zdrojů u větveného procesu:
► Skládání paralelních procesů:
Poznámky k tenzorovému součinu
► Tenzorový součin budeme využívat naivně, tj. jako symbol pro paralelní skládání.
► Pro náš model požadujeme vlastnosti, aby „fungoval jako
In ego :
► kostky na sobě = normální skládání,
► kostky vedle sebe = tenzor.
► Platí např. pravidlo výměny (interchange rule):
(gf)<g>(Wi) = {g®k){f®h)
► V monoidální kategorii existuje tenzorová jednotka 1 (a kvůli ní se tak jmenuje) s řadou vlastností, zejména 1 ® A = A.
► V toku by se jednalo o formální „zdroj bez účinku".
■v
► Rada očekávaných vlastností neplatí jako rovnost, ale jen ve formě izomorfismu.
Příklad
Cvičení: Zapište složený proces jako výraz:
rovaný a dávkový proces
► Iterovaný proces je (z pohledu stroje) sériovým složením n kopií procesu:
P • • • P — Pn
► Dávkový proces je paralelním složením procesů (často stejných, nikoli však nutně — viz lakovna):
p ® ... ® p = p®n
► Dávkový proces naplňuje podstatu provázaných stavů — všechny činitele provádíme souběžně, nejde o pouhé sjednocení paralelních procesů.
► Rozlišujeme nezávislou paralelnost, kde procesy mohou běžet úplně odděleně a s různými parametry.
► V monoidálních kategoriích je občas k dispozici unární operace/Vivo/i/ce f, která definuje pro každý morfismus f : A —>> B k němu sdružený f^\B—tAa splňuje:
► id^ = \dA
► (gfY = /V-
► Příklady: (1) hermitovský operátor M* = MT ve Vect, (2) inverzní relace p~ľ v Rel.
► V časticové fyzice involuce odpovídá přiřazení antičástice k dané částici (a naopak).
► V zajímavých aplikacích involuce nesplývá s inverzí (ta má silnější vlastnosti).
Obrácení Feynmanova-Stúckelbergovy interpretace
► V časticové fyzice se antičástice tradičně chápou jako „duální" k částicím.
► Feynmanova-Stúckelbergovy interpretace říká, že antičástice jsou vlastně částice pohybující se proti směru času.
► Při zrodu páru částice-antičástice nebo při jeho anihilaci tak dochází k „odrazu v čase".
► My pro potřeby modelování toku připouštíme obrácenou myšlenku: Místo představy výstupů zásobníku budeme předpokládat, že má pouze vstupy, z nichž některé ho plní zápornými výrobky:
Důsledky zavedení involuce
► Výrobní síť si lze úplně přeskládat a vytvořit samostatnou vrstvu procesů a samostatnou vrstvu zásobníků.
► Pro každou vrstvu si následně můžeme zvolit nejvhodnější organizaci (rozpadové struktury).
► Záporný příspěvek (odběr) je spolu s dávkou parametrem kanálu. Involuce by se tedy měla týkat spíš kanálů a ne procesů. Neměli bychom tedy za morfismy brát raději kanály?
Další poznámky ke kvantovým principům
► Kvantové protokoly se mohou zapisovat v jazyce monoidálních kategorií s involucí (konkrétně tzv. dagger compact categories).
► Teorie pak popisuje, které situace jsou ekvivalentní (tj. liší se jen způsobem zápisu, ne svojí funkcí).
► O kvantové informaci je známo, zeji nelze:
► duplikovat/kopírovat,
► mazat.
► Vlastnosti kvantové informace se tak velmi podobají vlastnostem hmoty (zákony zachování).
► U kvantových protokolů se hodně řeší transformace mezi klasickou a kvantovou informací.
► To je dobrá analogie s výrobním tokem, kde také současně působí hmotný tok i informační tok.
Přirozená transformace
► Nechť F, G : /C —> C jsou funktory. Přirozenou tranformací (f) : F =4> G nazýváme systém morfismů 0^ : F4 —> G A pro každý objekt A kategorie /C, které komutují ve smyslu
Gf o (f)A = (f)B o Ff pro každý morfismus ŕ : /4 —> B v /C.
► Otcové zakladatelé pokládali až př. tr. za první zajímavý pojem v teorie kategorií.
► Př. tr. si můžeme představovat jako „žebřík morfismů"
v kategorii C mezi obrazy kategorie /C ve funktorech F, G.
► Příklad: Vložení vektorového prostoru do svého druhého duálu.
► Lepší definice limity: Tzv. terminálni objekt mezi přirozenými transformacemi 0 : Kq —>> D, kde Kc je konstantní funktor (na jeden objekt C a jeho identitu).
► Složitější (ale užitečný) příklad: Nechť C je pevná množina a F přiřazuje každé A množinu Ac x C. Pak evaluace
evA : >AC x C —>> A daná (ŕ, c)     f (c) tvoří přirozenou transformaci ev : F =4> Id v Set.
Skládání funktorů a přirozených transformací
► Jsou-li F : /C —>• £, G : C     Aí funktory, definujeme složený funktor G o F očekávaným způsobem.
► Jsou-li (j) \ F G,i/j \ G H přirozené transformace, složené morfismy ty a ° <\>a vytváří složenou přirozenou transformaci
ty o cf) : F =4> H.
► Popsanému skládání přirozených transformací se někdy říká vertikální. Vedle něj lze definovat i horizontální skládání pro transformace (j) : F =4> G,ty : H =4> N, kde F, G : /C —>» £, H,N : £^ M, jako ty*(f): HoF^NoG,
(ty *        = 0 = A/(^ o ^M-
► Vertikální a horizontální skládání se k sobě mají velmi podobně jako sériové a paralelní skládání procesů či normální skládání a tenzor v monoidálních kategoriích (např. pravidlo výměny).
Kategorie f u n ktorú
► Pro dvě kategorie /C,£ definujeme kategorii funktorů £\ kde objekty jsou funktory /C^£a morfismy přirozené transformace mezi nimi.
► Mohou nás zajímat kategorie diagramů KP pro speciální případy:
► £> = {•   •}: Na př. tr. nejsou zvláštní požadavky, lze ztotožnit s K?.
► V = {• —)► •}: Zajímavější, objekty KP jsou morfismy v /C, morfismy KP jsou kompatibilní dvojice morfismů z K.
► atd.
► Kategorie funktorů vypadají velmi slibně pro abstraktní popis toku.
Cvičení: Rozmyslete si druhý případ, pokud /C je uspořádaná množina.
2-kategorie
► Příjemné vlastnosti přirozených transformací lze abstrahovat pojmem 2-kategorie.
► 2-kategorie je (kromě základní struktury kategorie) vybavena 2-morfismy, což jsou „morfismy mezi morfismy", značíme
► Vlastnosti 2-morfismů a vztah k morfismům je popsán řadou axiomů (vynecháváme).
► Příklad: Morfismy v /C^#^#^ jsou právě 2-morfismy (mj. vysvětluje se tak označení f =4> g).
► Příklad: Nechť f,g jsou dvě cesty prostoročasem od jedné události k jiné, přičemž f označuje složení „nejdřív čekám, pak vyrábím" a g „nejdřív vyrábím, pak čekám". Pak f lze prohlásit za pomalejší plán než g a vzniklé uspořádání f < g chápat jako 2-morpfismus f =4> g.
► V úvaze lze pokračovat až do r?-kategorií.
Obohacené kategorie
► Množina morfismů mezi dvěma objekty A, B se značí Hom(A B).
► Je-li f : B —> C morfismus, pak pro každé g : A —> B máme f o g : A —> C. To indukuje zobrazení mezi „Horny", které logicky označíme Hom(/4, f) : Hom(/4, B) —>> Hom(yA, C).
► Hom(/4, —) : /C     Set je tedy funktor.
► Množiny Hom(yA, B) mohou mít další strukturu a zobrazení Hom(/4, f) ji respektovat. Stávají se tak objekty a morfismy „lepší kategorie" než jen Set. Pokud pro každý A máme Hom(/4, —) : /C     C, pak o kategii /C říkáme, že je obohacená nad C.
► Mnohé kategorie jsou obohacené samy nad sebou — Vect, Ab (abelovské grupy), Sup (úplné polosvazy), atd.
► Pro nás je zajímavá otázka, zda množinu procesů mezi dvěma zdroji lze považovat za zdroj. „Metaprocesy" pak jsou manipulace s plány.
Uzavřené kategorie
► Kategorie uzavřené nad sebou a splňující další přirozené axiomy se nazývají uzavřené.
► Zvláštní postavení mají
► kartézský uzavřené kategorie, kde Horn „se doplňuje" se součinem a
► monoidálně uzavřené kategorie, kde platí podobné pro tenzor.
► Náznak podstaty: Je jedno, zda si dva vstupy si součinem/tenzorem nejprve sloučíme do jednoho, nebo zda je dosazujeme postupně:
Horrig (g) ß, C) = Horrig, Hom(ß, C))
► Uplatňuje se evaluační morfismus —jedním ze vstupů je struktura vyššího řádu, další vstup ji specifikuje.
► Příklad: Vstupem programovatelného stroje je program a data. Můžeme nejprve vložit jen program, čímž se ze stroje stane jednoúčelové zařízení. To pak zpracuje data.
Příklad na „sčítací krabičky"
1 \	X	sl
1 >		
1 >		
Závěry ke kategoriím
► Jazyk teorie kategorií nabízí mnoho možných popisů toku, výběr není snadný.
► Naše hlavní požadavky: horizontální a vertikální skládání procesů, agregace zdrojů.
► Bonusy: involuce, metaprocesy.
► Model je stále ve vývoji.