Úvod do teorie kombinatorických her

Řešitel: Doc. Dr. Jaroslav Blažek, CSc.
Spoluřešitel: Dr. Václav Vopravil

Úvod

       
         
           

>
a)  dlouholetá spolupráce řešitele s malířem Z. Sýkorou v oboru počítačového umění, společná publikace v umělecky zaměřeném časopise Leonardo a následný přepis In: Visual Art Mathematics \& Computer, F. J. Malina, Pergamon Press Oxford, 1979
b)  zkušenosti s publikací článku s podobnou tématikou v Itálii, který měl dobrý ohlas, takže byl přetištěn v dalším italském časopise
c)  s počátečními výsledky byl seznámen prof. Erwin Steller, přední odborník oboru "Computer Kunst", přednášející na univerzitě v Karlruhe, autor publikace Computer und Kunst, BI Wissenschaftsverlag, Mainheim, 1992; k naší práci zaujal kladné stanovisko.

Práce na řešení grantu "Computer Painting" byla zahájena v březnu 1993. První stádium bylo věnováno studiu algoritmů, implementace standardních matematických funkcí a chyb (které jsou způsobovány především softwarem a hardwarem počítačů), s jejich pozdějším záměrným využitím pro získání výsledného obrazu s estetickým účinkem. Bylo třeba vyřešit řadu dílčích technických problémů --- snímání obrazu na filmový pás, snímání obrazu na barevnou tiskárnu a na laserovou tiskárnu, obarvování, změna barev, a pod. Studiu této problematiky byla věnována první etapa řešení grantu, která trvala asi 3 měsíce.

··
Druhou --- experimentální --- část řešení grantu jsme zaměřili především na některé metody vizualizace matematických funkcí. Ke zprávě přikládáme výběr výsledků, tj. přikládáme ke zprávě pouze typické ukázky užití dále popsaných metod. Výsledky práce jsme zaznamenali na fotografie, vytiskly na barevné, resp. laserové tiskárně, nebo jsme ostatní výsledky (především z technických, finančních a časových důvodů) zaznamenávali v elektronické formě.

···
Existuje mnoho nejrůznějších způsobů, jak pomocí počítače vytvářet barevně, tvarově, kompozičně atd. zajímavé estetické obrazy. Je však zřejmé, že bez předem vytčeného uměleckého záměru, ideje obrazu, nemůže počítač sám vytvořit umělecké dílo. V tomto smyslu je tedy počítač pouze nástrojem, který usnadňuje realizaci umělcových ideí. Na druhé straně však i umělec je zpětně ovlivňován výsledky získanými pomocí počítače. Tato zpětná vazba může velmi podnětným způsobem ovlivňovat další tvorbu, jak jsme toho svědky v tzv. počítačovém umění. V naší práci se zabýváme třemi metodami vytváření počítačových obrazů, které poměrně jednoduchými matematickými prostředky (tedy jejichž aplikace je snadno zvládnutelná i nematematiky) dávají --- jak se domníváme --- zajímavé výsledky. Každému bodu obrazovky (c,r), (0 < c<640, 0 < r<480) přiřadíme atribut (barvu) p(c,r), (0 < p(c,r) < 16 ), takže pracujeme s uspořádanou trojicí --- barevný pixel --- (c,r,p(c,r)). Budeme-li chtít např. zviditelnit některé matematické funkce, můžeme postupovat tak, že vybereme zcela libovolnou reálnou funkci f(x,y) dvou reálných proměnných x,y, nebo komplexní funkci j (z)=j (x +iy) komplexní proměnné x + iy. Každý bod obrazovky (c,r) potom pomocí zadané funkce "obarvíme". Vybereme-li nyní "nejlevější" dolní bod obrazovky, který označujeme (0, 0), resp. počáteční bod iterace z0 =(x0, y0), sousední bod a každý další bod bude mít souřadnice

(x0 + cd,y0 + rd),    0 < c <640,    0 < r < 480,
kde d je tzv. diference, která má význam přibližování, resp. vzdalování, popřípadě zvětšení a zmenšení.

I

První používaná metoda spočívá ve výběru přirozeného čísla m a přiřazení barvy p(c,r)

p(c, r) = [f(x0 + cd, y0 + rd)]     (mod m),
kde hranaté závorky znamenají tzv. celou část čísla f(x0 + cd, y0 + rd). Číslo p(c,r) je tedy nejmenší nezáporný zbytek celé části [f(x0 + cd, y0+ rd)] po vydělení číslem m, což znamená, že p(c,r) může nabývat pouze hodnoty 0,1,...,m-1. V případě použití komplexní funkce j (z) je postup analogický, pro každé 0 < c < 640, 0 < r < 480 je
p(c,r) = [|j (x0+cd + (y0+rd)i)|]    (mod m),
nebo
p(c,r) = [|j (x0+cd + (y0+rd)i)|2 ]     (mod m).
Pro získání odpovídajícího výsledku je důležité:

Na výsledný efekt ale má zajisté i vliv zkušenost, způsob zápisu čísel v počítači, použitá výstupní periferie, použití standardních funkcí a dokonce jejich pořadí a pod. Např. při zviditelňování funkce z3 a při výpočtu

p = p(c,r) = [|j (x0+cd + (y0+rd)i)|2 ]     (mod 16),
funkce `celá částc pro malé hodnoty |z| přiřazuje všech 16 možností, pro větší hodnoty v některých případech poskytuje pouze sudá čísla (tj. 8 různých výsledků), dále jen 4, resp. 2 výsledky, tj. barvy, a nakonec pro |z| > 22.627 ... je již p=0. Budeme-li tedy chtít vizualizovat tuto funkci, musíme tedy mimo definičního oboru, vybrat i počáteční bod uvnitř kruhu |z| < 22.627 ... Samozřejmě pro jiné funkce může mít oblast, z níž je třeba vybírat, jiný, někdy i velmi komplikovaný, tvar.

II

Modifikací předcházející metody je i následující postup: Opět vizualizujeme funkce f(x,y) nebo j (z). Vybereme nyní počáteční bod (x_0,y_0), diferenci d, ale místo modulu m zvolíme množinu{m_1,m_2,...,m_k} kladných celých čísel, kde 1-li P(c,r) jednu z následujících funkcí [f(x_0+cd,y_0+rd)],    [|j (x_0+cd+(y_0+rd)i)|],    [| j (x_0+cd+(y_0+rd)i)|2], potom barvu, tj. hodnotu p(c, r), přiřadíme podle následující předpisu: p(c, r) = i, je-li index i Î {1,2,...,k}, nejmenší takové číslo, pro které P(c, r) = 0 (mod m_i), což znamená, že pro všechna j, 1 < j< i platí P(c, r) ¬ = 0 ( mod m_j). V případě, že takový index i neexistuje, pokládáme p(c, r) = 0. Velmi zajímavé výsledky jsme dosáhli především volbou čísel m_1,m_2,... (např. prvočísla, různá pořadí a pod.).

III

Poslední metodu, kterou stručně v černo--bílé verzi popíšeme, používáme především ve spojení s předcházejícími metodami. Metoda spočívá ve volbě "bázových bodů"; B1,B2,B3,..., počátečního bodu P =(x0, y0) a volbě diference d. Iterativní algoritmus náhodně zvolí jeden z bázových bodů, např. Bi, a sestrojí nový počáteční bod P+d ® PBi atd. Tuto metodu kombinujeme s předcházejícími tak, že bázové body počítáme podle první popsané metody a barvy klademe podle druhé popsané metody. Tak získáváme efekty typu "froté".

Závěr

Několik ukázek výsledků naší práce (s plnou citací autorů a pracoviště) bylo použito ve filmu o užití počítačů --- vyrobilo ČVUT v Praze v r. 1993. Paralelně připravujeme článek pro italský časopis L\cinsegnamento della matematica e delle scienze integrate. Článek je nyní ve stádiu diskuse dosažených výsledků se zahraničním partnerem --- prof. C. Sitiou (Itálie). Připravujeme výstavku některých prací (materiál pro výstavku je dokončen).O výsledky práce byl již projeven zájem vedením univerzity --- pro výzdobu školy.

····