58 FRAKTALI - ZNANOST ALI UMETNOST INFORMATICA 4/89 Keywords: fractal, iterated function method, Julia set, Mandelbrot set Jasna Donlagič, Nikola Guid Tehnična fakukteta Maribor V naravi Je veliko objektov in pojavov, kot n.pr. drevesa, gore, oblaki, pretok tekočin, rast populacije, oblika možganskih gub ter podobni pojavi, ki iz določenega reda preidejo v nered in ki jih ne moremo matematično predstaviti z običajnimi orodji, lahko pa Jih s fraktalno geometrijo oz. fraktali. V članku obravnavamo naravne in geometrične fraktale, metodo iterativnih funkcijskih sistemov (IFS) in nakažemo uporabo formalnih jezikov. Na koncu izdelamo algoritme za naslednje vrste fraktalov: Juliovo množico, Mandelbrotovo množico in fraktale določene po metodi IFS. For some natural objects like trees, mountains, clouds, flow of liquids, population growth, surface of brain etc. , which turn from order into chaos, it is impossible to describe all mathematical data, but it is possible to present them with fractal geometry or fractals. The purpose of this article is to present natural and geometrical fractals, iterated function method (IFS), and use of the formal languages in the fractal theory. At the end we show some algorithms for creating the following fractals: Julia set, Mandelbrot set, and fractals produced by IFS method. ABSTRACT 1. UVOD Beseda fraktal Je latinskega izvora (lractus = zlomljen), torej naj bi spominjala na lomljenje, drobljenje. S fraktalno teorijo se je pričel ukvarjati Benoit B. Mandelbrot 1980. leta 16], čeprav so matematične osnove za nastanek te teorije ustvarili te mnogo prej P. F. Verhulst, Gaston Julia, Pierre Fatou, Adrien Douady in drugi [71. Fraktale delimo na dve osnovni skupini, in sicer na: naravne in geometrične. Članek obsega opis naravnih in geometričnih fraktalov ter uporabo formalnih Jezikov na področju fraktalne teorije. V povezavi z naravnimi fraktali smo opazovali Verhulstov dinamični proces ter Juliove in Mandelbrotove množice. Pri geometričnih fraktalih smo podali metodo IFS in opisali nekatera pravila za generiranje geometričnih fraktalov. Prav tako smo razvili tri algoritme za generiranje fraktalnih slik. 59 2. NARAVNI FRAKTAU Naravne fraktale lahko zasledimo na področju geografije, biologije, biokemije in fizike, ko želimo z njimi upodobiti naravne pojave, kot so na primer poplave rek, pretok tekočin, obliko možganskih gub, vaskularnl sistem, vreme itn. Ideja za nastanek naravnih fraktalov izvira iz biologije, ko Je P. F. Verhulst 1845. leta definiral zakon rasti populacije [7], Zagovarjal je trditev, da lahko določena populacija narašča tako dolgo, dokler ne doseže svojega razsežnostnega maksimuma X. Če le tega prekorači, velikost populacije pade. Potrebno je bilo več kakor 'sto let, da so dokazali vse nejasnosti te trditve. Prišli so do zanimivih rezultatov : Ce je faktor rasti majhen, se velikost populacije uravnava sama po sebi in zmeraj ostaja znotraj optimalne vrednosti X. To pomeni, da populacija narašča, kadar je pod optimalno vrednostjo X, in pada, kadar je nad optimalno vrednostjo X. V primeru, da je faktor rasti velik, taksen, da se populacija poveča za več kakor 200 '/., pa optimalne vrednosti X ni mogoče več doseči. Porodi se vprašanje, ali je rast populacije sploh kdaj tako velika? Seveda! Človeške populacije ne naraščajo tako hitro, toda pri nekaterih insektih tak pojav ni nenavaden. Ugotovili so, da pri 245 '/. povečanju populacije nastanejo oscilacije okoli optimalne vrednosti X z velikostjo periode 2,4,8,16..... dokler pri 257 '/. ne preidemo v zmedo. Kako si razlagamo besedo zmeda? To preprosto pomeni, da delovanja sistema ne moremo več nadzorovati, da je ušla Izpod naše kontrole. Najzanimivejša točka Verhulstovega dinamičnega procesa pa ni zmeda sama po sebi, temveč dogodek, ki spremeni red v nered. Verhulst je to trditev matematično dokazal. Z x označi začetno velikost populacije, z x o n pa velikost populacije po n letih. Jakost rasti populacije R definira relativni prirastek populacije na leto: nestabilnost teh dveh stanj. Pri xq= 0 ne pride do rasti populacije, saj nimamo s čim začeti. To stanje smatramo za nestabilno, saj že pri 0xi,x2..... narašča, dokler ne doseže velikosti 1. Ali Je stanje xq= 1 stabilno? Da bi prišli do odgovora, opazujmo razliko S = x - 1! Dinamični zakon nam omogoča izračun x , torej lahko določimo n + l tudi naslednji 6 S s S (1-r) n+l n Težimo za tem, da se x stabilizira pri 1, zato mora n+l 5 limitirati proti 0. n + l ■ r lim 5 =0 n + l n«Ko Um 5 (1-r) = 0 o n-Wo To bo veljalo, kadar bo |5 < S I (z x se bomo 1 n + l n' n+l približevali k 1), če Je 02. Oglejmo si primer, pri katerem postavimo xQ= 0.1 in r=l. 8 (slika 2.1). R = Slika 2.1 Rast populacije pri r=1.8 in xq= 0.1 Nato uvede določene predpostavke: - Populacija lahko naraste do določenega maksimuma X (maksimum normirajmo, tako da Je X=l) - R se naj spreminja glede na velikost populacije in naj bo linearna funkcija od r (r imenujemo parameter rasti in r>0): R=r(l-x ) n Ob teh predpostavkah dinamični zakon rasti preide v naslednjo obliko: x = f (x ) = (l+r)x -r rx n+l n n n Vidimo, da velikost populacije x sprva narašča, saj Je pod maksimalno vrednostjo X=l. V četrtem koraku pride do prekoračitve. Zaradi tega se velikost populacije zmanjša in pade pod 1. To povzroči ponovno rast in takoj za tem ponoven padec itn., dokler se dokončno ne umiri pri stabilni vrednosti X=l. Zanimivejši položaj nastane, kadar Je r>2. Zato razlščlmo primer, ko postavimo xQ= 0.1 in r=2.3 (slika 2.2) ter xq= 0.1 in r=2.5 (slika-2.3). Ločimo dve stanji, pri katerih populacija ne spreminja velikosti: x = 0 in x = 1. Zanima nas stabilnost oz. o o 60 Slika 2.2 Rast populacije pri r=2.3 in * = 0. 1 Slika 2.3 Rast populacije pri r=2.5 in 0.1 Ugotovimo, da pride do periodične oscilacije med nivoji. V prvem primeru dobimo periodo 2, v drugem pa 4. Če bi nadaljevali s postopkom, bi dobili periodo 8,16,32,..., dokler pri r=2.57 ne bi prešli v zmedo in periode ne bi bilo več mogoče določiti (slika 2.4). Slika 2.4 Rast populacije pri r=2.57 in XQ= 0.1 V nadaljevanju si lahko zastavimo zanimivo vprašanje: Katero maksimalno vrednost lahko zavzame r, da bi dobili še" enako stabilno oscilacijo (n.pr. s periodo 2)? Če Izberemo 2 1. Zaporedje limitira proti neskončnosti In pravimo, da je neskončnost stekallšče procesa x ■» x2. - = 1. V tem primeru so števila zaporedja na meji med dvema stekallščema. Mejo sestavlja krožnica enotsf .ga kroga, ki razdeli ravnino na dve regiji. Nič predstavlja notranje stekallšče, neskončnost pa zunanje stekallšče. 61 b) Če predvidimo c * 0 dobimo zaporedje iteracij Xo'Xi'X2..... prl katerem lahko prav tako nastanejo prej naštete možnosti. Razlika je le v tem, da notranje stekališče nima več vrednosti 0, temveč drugačno vrednost, in da meja ni več lepo ukrivljena, temveč je "nazobčana". Prav s tem pa smo porušili pravilnost geometrijskih likov in dobili lik, ki je podoben naravnemu. Imenujemo ga fraktal (slika 2.6). Slika 2.6 Fraktal Pri podrobnejši analizi meje ugotovimo dve zanimivi lastnosti : - Če vzamemo povečevalno steklo in pogledamo delček meje od blizu, ugotovimo, da je popolnoma enak, kakor če ga pogledamo brez povečevalnega stekla. To lastnost imenujemo samopodobnost. - druga lastnost Je zrcalnost .Če pogledamo obliko meje v enem kotu, ugotovimo njeno zrcalno sliko v nasprotnem kotu. Fraktale, ki posedujejo takšne lastnosti, imenujemo Juliove množice (po francoskem matematiku Gaston Julii) [7]. Druga možnost je, da fiksiramo xq= 0 in dovolimo spremembo c po vsej kompleksni ravnini. Na tak način dobimo novo množico, ki Jo imenujemo Mandelbrotova množica M (B. Mandelbrot je prvi objavil njen opis in jo prikazal na računalniku, slika 2.7). -2,25 0,75 Re(c) Zanimive so naslednje ugotovitve: - Če izberemo c iz notranjosti glavnega dela telesa Mandelbrotove množice in ga po prvem postopku razvijemo v Juliovo množico, dobi Juliova množica obliko deformirane, nazobčane krožnice, ki obkroža stekališče (slika 2.6, podoben primeru 1 na sliki 2.13). - Če izberemo c v notranjosti enega izmed "popkov" Mandelbrotove množice in ga razvijemo v Juliovo množico, bo Juliovo množico sestavljalo več deformiranih, nazobčanih krožnic, kjer vsaka izmed njih obkroža svoje stekališče (slika 2.8, primer 3 na sliki 2.13). Slika 2.8 Primer fraktala, ki se nahaja v notranjosti enega izmed "popkov" Mandelbrotove množice - Če izberemo c na meji, kjer se "popek" dotika glavnega dela telesa Mandelbrotove množice in ga razvijemo v Juliovo množico, dobimo t.1. parabollčni primer. Zanj je značilno, da se več nazobčanih krožnic steka v eno točko (slika 2.9, primer 8 s slike 2.13). Slika 2.9 Parabolični primer fraktala - Če izberemo c na "anteni" Mandelbrotove množice in ga razvijemo v Juliovo množico, dobimo fraktal imenovan dendrit. Zanj je značilno, da ima eno samo stekališče, ki je v neskončnosti. Zaradi tega tak fraktal nima notranjosti (slika 2.10, primer 4 na sliki 2.13). Slika 2.7 Mandelbrotova množica pri x = 0 o 62 Imlil t.S -15 t.5 Bel.l 1983. leta je Dennis Sullivan dokazal, da so to edl ne oblike, ki jih Juliova množica lahko zavzame Obstaja še ena možnost, tako imenovani Hermanov obroč (Herman ring), ki pa ne nastane v primeru x«>x2. Teoretično je dokazano, da lahko do njegovega pojava pride v drugih primerih, čeprav praktično Se nI bil nikdar opazovan [7]. Slika 2. 13 prikazuje nekaj Juliovlh množic, ki Jih dobimo z ustrezno izbiro parametra c iz Mandelbrotove množice. Slika 2.10 Primer dendrita - Če izberemo c kjerkoli drugje na meji Mandelbrotove množice in ga razvijemo v Juliovo množico, pride do pojavov Siegelovih diskov. Če točka v iteracijskem postopku doseže Siegelov disk, bo v nJem tudi ostala. To pomeni, da bo v krogu rotirala okoli stekališča, samega stekališča pa ne bo nikdar dosegla (slika 2.11, primer 9 s slike 2.13). 1.5 Rel«i Slika 2.11 Primer fraktala s Siegelovimi diski - Če izberemo c izven Mandelbrotove množice in ga razvijemo v Juliovo množico, bo Juliova množica nepovezana. To pomeni, da razpade v množico točk In tak fraktal imenujemo Fatouov prah (slika 2.12, primer 11 na sliki 2. 13). In I» I 15 1.5 Rt(.| 2.1 Podobnosti Mandelbrotove množice z Verhulstovim dinamičnim procesom Raziskave so pokazale, da ima Mandelbrotova množica veliko skupnih točk z Verhulstovim dinamičnim procesom (slika 2.14). Pri Mandelbrotovl množici ugotovimo stabilno področje ter oscilacije s periodo 2,4,8,16..... ravno tako kakor pri Verhulstovem dinamičnem procesu. Stabilno področje zajema območje med c=0.25 ln c=-0.75, oscilacije s periodo 2 se pojavljajo v krogu s polmerom 1/4 ln središčem v točki c=-l, oscilacije s periodo 4 pa okoli središča c=-1.3107 itn. Točke, kjer nastajajo "popki" na realni osi na sliki Mandelbrotove množice, ustrezajo točkam, kjer prihaja do podvajanj periode v Verhulstovem procesu. Slika 2.14 Podobnosti Mandelbrotove množice 2 Verhulstovim dinamičnim procesom Slika 2.12 Fatouov prah 63 lm(c)[ 1,5 • -1,51-,---- -2,25 O 0,75 Refc> Slika 2.13 Jullove množice kot sestavni del Mandelbrotove množice 3. GEOMETRIČNI FRAKTALI Geometrični fraktali se od naravnih razlikujejo po tem, da ustvarjajo slike, ki Jih Je mogoče vnaprej predvideti. Primer geometričnega fraktala Je Kochova snežinka (slika 3.1), ki Jo lahko generlramo s pomočjo naslednjega algoritma: Kochova_krlvulJa := lnlciator; loop vsak osnovi element v Kochovi_krivulJ1 zamenjaj z generatorjem endloop. lnlciator 1. IttfKlJ«: 1. it«r»clj»: O Slika 3.1 Primer geometričnega fraktala-Kochova snežinka Opazimo lahko, da s ponavljanjem iteracij v globino ustvarjamo čedalje bolj natančno sliko. S tem dobimo občutek, da je objekt (snežinka), ki ga opazujemo, zelo blizu. Pri majhnem Številu iteracij dobimo občutek oddaljenosti objekta. Kochova snežinka predstavlja najprlmitlvnejšl fraktal v verigi geometričnih fraktalov. To pomeni, da lahko v osnovni algoritem uvedemo dodatna pravila in na tak način dobimo zanimivejše in bolj komplicirane fraktale. 64 Pravilo 1: Nekatere daljice iniciatorja zaznamujemo kot Pravilo 4: Predpostavimo, da je osnovni element enak koristne ln Jih v lteraciJskem postopku iniciatorju (slika 3 5) spreminjamo (slika 3.2). Initiator Generator Osnovni element □ 17 i Slika 3.2 Drevo, narisano s pomočjo pravila 1 in zapolnitvijo notranjosti Pravilo 2: Dodamo funkcijo, ki bo dovoljevala generatorju naključni premik na levo ali desno (slika 3.3). Iraciator ■ Generator Osnovni element A A A Slika 3.5 Trikotnik Sierpinskega, narisan s pomočjo pravila 4 Seveda lahko ta pravila združimo in Jih uporabimo skupaj. Na tak način porušimo geometrijsko natančnost ln dobimo nepravilne krivulje, ki imajo obliko oblakov, gorovja Itn. 4. UPORABA METODE IFS ZA GENERIRANJE GEOMETRIČNIH FRAKTALOV Inicialor Generator Osnovni element □ Ti — Slika 3.3 Drevo, narisano s pomočjo pravila 2 ln zapolnitvijo notranjosti Pravilo 3: Generator sestavimo iz dveh ali večih delov (slika 3.4). Initiator Generator Osnovni element □ □ — •4-B-f "■H- |||j +■+ Slika 3.4 Vzorec, narisan s pravilom 3 in zapolnitvijo kvadratkov Trikotnik Sierpinskega iz pravila 4 Je mogoče narisati tudi na na drugačen način in sicer tako, da izberemo začetno točko pQ = 10,0,11 (dano s homogenimi koordinatami) ter eno Izmed treh transformacij: T = 1 T = 2 0.5 0 0 0. S 0 0 0.5 0 0 0.5 1 0 0.5 0 0 0.5 0.5 0.5 T je skalirna matrika. Ta Je produkt skalirne in translacijske matrike. T3 Je produkt skalirne in translacijske matrike. Transformacijo izberemo naključno, jo izvršimo nad začetno točko in dobimo točko p . Nato naključno S, h izberemo naslednjo transformacijo ln Jo izvršimo nad točko, dobljeno v prejšnjem koraku. Verjetnosti za Izbiro posamične transformacije so enake. Postopek nadaljujemo ln po določenem Številu lteraclj pridemo do trikotnika Sierpinskega. Na prvi pogled se zdi čudno kako lahko naključna izbira ene od treh transformacij privede v iterativnem postopku do tako složne harmonije, kakor Je trikotnik Sierpinskega. Področje v matematiki, ki se ukvarja s takšnimi transformacijami, Je teorija iterativnih funkcijskih sistemov (1FS) ln od tod tudi ime za naSo metodo. 65 5. UPORABA FORMALNIH JEZIKOV NA PODROČJU FRAKTALNE TEORIJE Nekatere objekte, na primer drevje In rastlinje, je mogoče predstaviti s pomočjo gramatik PRC (parallel rewriting grammars). Benoit Mandelbrot v svojih definicijah [6] ne dovoljuje , da bi objekte, dobljene na tak način. Imenovali fraktali. Trdi namreč, da je pojem fraktala strogo geometrijski, medtem ko s pomočjo formalnih jezikov dobimo strukturirano zgradbo. Objekte, nastale s pomočjo gramatik, imenujemo graf tali (81. Graftali se od fraktalov razlikujejo po tem, da ne ustvarjajo strogo zrcalnih in samopodobnih slik ter ne dovoljujejo nikakršne naključnosti pri uporabi produkcijskih pravil. Značilnost gramatik PRG je zaporedna uporaba produkcijskih pravil (nad vsakim simbolom izvršimo produkcijsko pravilo), prav tako ne ločijo terminalnih simbolov od neterminalnih. Oglejmo si primer! Dana naj bo abeceda £ = <0,1, (,),[,!} začetni simbol S=0 ter produkcijska pravila: 0-» 1(0)1(0)0 ■ 11 [->1 ) 1 )-*• ) (-► ( i 1] število generacij Slika 5.1 Prikaz postopka, kako s pomočjo predhodno definirane gramatike tvorimo graftalno sliko. Vejitveni kot znaša 45 stopinj. Seveda obstajajo Se bolj komplicirane interpretacije našega niza. Tako lahko npr. spreminjamo vejitveni kot glede na smer vetra, čvrstost, velikost drevesa itn. Prav tako lahko predpostavimo veje v obliki valja, katerega premer in višina sta odvisna od položaja enlce v nizu. Ta dodatni pogoj omogoča, da v določenem trenutku dobimo manjše in tanjše veje. 6. OPIS ALGORITMOV ZA GENERACIJO FRAKTALOV Pri oblikovanju 2D fraktalnih slik smo upoštevali dinamični proces nad polinomom druge stopnje z ■» z2 + c (namesto x pišimo z). Kompleksni števili z in c smo razdelili na realni in imaginarni del (z=x+iy, c=p+lq) tako, da je dinamični zakon prešel v obliko: Uporabimo naslednji algoritem: for i:= 1 to števllo_generacij do nad vsakim simbolom v nizu uporabi produkcijsko pravilo Pri številu_generacij = 3 dobimo: štev ilo generaci j niz 11011(0)0 11[1(0]1(0)0)11(1(0)1(0)0)1[0]1(0)0 Dobljeni niz želimo grafično predstaviti v obliki drevesa, zato uporabimo preprosto interpretacijo: ..nariši list ..nariši črto ..začetek vejitve v levo ..konec vejitve v levo ..začetek vejitve v desno ..konec vejitve v desno 2 2 = f(x . y ,p) = x - y y , = g(x ,y .q) = 2x y n+1 nn n n Kot že omenjeno, smo do oblikovanja slik prišli po dveh poteh: 1. Upoštevali smo ravnino xy in fiksni vrednosti p ter q. Za vsako točko ravnine smo ugotovili njeno dinamično povezanost do ustreznega stekališča. Na tak način smo raziskali strukturo Juliovih množic. 2. Upoštevali smo ravnino pq ter fiksno točko (x,y). Tak postopek Je produciral slike Mandelbrotove množice. Program za izračun dinamičnega procesa ter določitev barv Je tekel na VAX 8800. Rezultate je shranjeval na datoteke, ki smo Jih kasneje prenesli na PC-AT. Tam Je tekel program za izris fraktalnih slik. Napisan je bil v turbo pascalu. Pri izrisu slik smo uporabili 16 barv. Povedale so, kako dolgo je potrebovala točka (x,y) da se je približala stekallšču. Ce se točka po določenem Številu iteracij (5000) ni približala stekališču, smo Jo pobarvali s črno barvo. Velikost okna (a x b) smo izbrali (511 x 350) pikslov. Algoritma 1 in 2 smo uporabili za generlranje naključnih fraktalov. S pomočjo algoritma 3, pa smo 66 narisali geometrična fraktala trikotnik Sierplnskega in list praproti. Algoritem 1: Juliova množica korak 0: Izberi parameter c=p+lq Določi velikost okna: x m x ¿x=(x - x )/(a-l) max m 1 n Ay=(y - y , )/(b-i) max min 2a vse točke zaslona (n ,n ), n = 0,1.....a-1, x y x n = 0,1.....b-1. Izvrši naslednje korake. y korak 1: x = x + n Ax 0 min x y = y + n Ay 0 min y števec_iteracij = 0 korak 2: x n»l 2 2 = x - y + p y = 2x y + q n+1 n-'n M Povečaj števec_lteracij za 1. korak 3: Izračunaj r2= x2 + y2 n n (1) If r>2 then Izberi barvo in goto korak 4 (ii) if števec_iteracij = 5000 then izberi barvo 0 (črno) in goto korak 4 (ill) if r s 2 and števec_lteracij<5000 then goto korak 2 korak 4: Pobarvaj točko (n ,n ) z ustrezno barvo, izberi x y naslednjo točko in pojdi na korak 1. Da bi izboljšali čas računanja, smo upoštevali, da točki (x, y) in C-x,-y) producirata enak rezultat, saj je slika simetrična glede na izhodišče. Pozorni moramo biti tudi na izbiro koordinat okna, saj ob njihovi nepravilni izbiri lahko dobimo nezanimivo sliko. Algoritem 2: Mandelbrotova množica korak 0: Izberi p , p , q , q min max min max Ap = (p - p )/(a-l) max a 1n Aq = (q - q )/(b-l) max min Za vse točke zaslona (n ,n ), n = 0, 1,-..., a-1, p q P n = 0,1.....b-1, Izvrši naslednje korake. korak 1: p = p + n ¿p 0 min p q = q + n Aq m 1 n q števec_lteracij = 0 x = y = 0 o Jo 2 2 korak 2:x =x-y+p n* 1 n n y = 2x y + q n+1 n n Pri tretjem algoritmu smo začetno točko Izbrali (0,0). Število lteraclj Je bilo 32000. Program Je v celoti tekel na PC. Algoritem 3 : metoda IFS korak 0: Okno opazovanja V naj bo velikosti X x Y, pri čemer Je X x Y resolucija zaslona. Okno V razdelimo na L x M kvadratov (označimo Jih z V ) velikosti doli (L=L/dol2, M=M/dol2). Izberi število_lteraciJ e L x M. Polje V iniclallziraj na 0. Izberi začetno točko (x ,y ) e R2. o o število_barv=16. korak 1: for n = 0 to Stevilo_iteraclj do begin (• izberi nakjučno transformacijo M^ •) rand = random Število med [0,1]; verjetnost = p ; k = 1; while (verjetnost < rand) do begin k = k+1; verjetnost = verjetnost +.Pk; end; (• Izvrši transformacijo nad točko •) r x y i ] = r * y 11 m L ntl n»l J L n '„ J k n = lnt(x ); 1 n*l n = lnt(y , ); 2 n+1 (• zaznaj "obisk" v kvadratu V •) Vtni1 lna] = Vf"!1'^1 + 1: end; korak 2: Poišči maksimalno vrednost max v polju V. Določi barvo pravokotnlka V : barva_pravokotnika=barva(V[i)(J)•15/max) ln ga pobarvaj. Slike 6.1, 6.2 in 6.3 so bile izrisane na barvnem brizgalnem risalniku Tektronix 4696. Povečaj števec_iteracij. 2 2 2 korak 3: Izračunaj r = x + y n n (i) if r>2 then izberi barvo goto korak 4 (11) if števec_iteracij=5000 then izberi barvo 0 (črno) ln goto korak 4 (lil) lf r s 2 and števec_iteracij<5000 then goto korak 2 korak 4: Pobarvaj točko (n ,n ) z ustrezno barvo, p q Izberi naslednjo točko ln pojdi na korak 1. 67 xwin= -i, 50 yriin= -1.50 xnax= 1.50 anax= 1.50 Slika 6.1 Jullova množica pri c = 0.11031 - 0.670371 pnin= -0.74591 qnin= D.11196 pnax= -0.74448 qnax= 0.11339 Slika 6.2 Mindelbrotova množica 68 Slika 6.3 Trikotnik Slerpinskega dobljen s pomočjo metode IFS 7. ZAKLJUČEK Znanost in umetnost sta dva nasprotujoča si načina za izražanje naravnega sveta - prvi analitičen, drug intuitativen. S pomočjo fraktalov smo ti dve poti združili in dokazali, da sta odvisni druga od druge. Fraktall so zanimivi zaradi visoke stopnje vizualne kompleksnosti, čeprav so v svojem bistvu izredno preprosti. Matematična osnova fraktalne teorije je enostavna, saj temelji na ponavljanju. Prav zaradi tega jo je bilo izredno lahko uporabiti na področju računalništva. Algoritmi za kreiranje fraktalnlh slik potrebujejo malo podatkov, s pomočjo rekurzije pa so zelo uspešni. Teorija fraktalov Je pomagala zlomiti strogo geometrijo likov. Trendi v svetu pa segajo še dalje. Področje uporabe fraktalov se naglo Siri - od biologije do tekstilne industrije pa vse do drugih, predvsem barvnih grafičnih izdelkov. Možnosti je torej ogromno -ta članek opisuje le delček njih. 8. LITERATURA [1) M. Barnsley: "Harnesslnj; Chaos for Image Synthesis", Computer Graphics, Volume 22. Number 4, avgust 1988 12] P.Blanchard: "Complex Analytic Dynamics on the Rlemann Sphere", Amer.Math Soc. 11, 1984, str.85-141 13] S.Demko: "Construction of Fractal Objects with Iterated Function Systems", Computer Graphics, Volume 19, Number 3, 1985, str.271-278 [4] M.Gervautz: "Fractals in Computer Graphics", Proceeding of The Second Austro-Yugoslav Conference on Computer Graphics, str.96-103 [5] J.A.Kaandorp : "Interactive Generation of Fractal Objects", Eurographics',87, str. 181196 [6] B.B.Mandelbrot: "The Fractal Geometry of Nature", W.H.Freeman, San Francisco, 1982 [7] H.0.Peltgen, P.H.Richter: "The Beauty of Fractals", Springer Verlag, Berlin, Heidelberg, New York, 1986 [8] A.R.Smith: "Plants, Fractals and Formal Languages", Computer Graphics, Volume 18, Number 3, JullJ 1984, str.1-10 [9] A.TerčelJ: "Fraktali - grafične skrivnosti računalniških umetnikov", Informática 3/87, str.46-50 69 PRIMENA METODA INŽENJERSTVA ZNANJA INFORMATICA 4/89 U OBRAZOVANJU Keywords: method, knowledge engineering, artificial intelligence, education Ljubomir Jerinič, Zoran Budimac, Dura Paunič i Mirjana Ivanovič U radu su opisane metode inienjerstva znanja kao podoblasti veStačke intejigencije, i mogučnosti prlmene tih metoda u obrazovanju. Kao najpogodnija metoda reprezentaciJe znanja za potrebe obratovanja izabran je sistem okvira Marvina Minskog. Na osnovu takvog pristupa razvijen Je programski sistem OSOF za prikupijanje, internu reprezentaciju i koriščenje znanja u svim vidovima i nivoima obrazovanja. 1. uvod Prema ti), veStačka i ntel i genci ja je deo ratunarskih nauka u koj ima se projektuJu inteligentni raiunarski sistemi, koj i se ponaSaju na način sličan inteligene ij i u ljudskom ponaSanJu, za razumevanje prlrodnih jezika, učenje, rezonovanje, reSavanje problema i si. VI Je interdisciplinarna nauka i potekla je iz istraživanja iz domena simboličke obrade podataka i dela psihologije o rasudivanju. VI istražuje simboliCku obradu i heurističke procese zaključivanja i rezonovanja, kao i predstavljanje znanja u obliku pogodnom za zaključivanje uz pomoi računara (2) . Osnovni pravci lstraživanja u okviru VI su: razumevanje prirodnog govora, maSinsko učenje,, automatsko program iranje, rafiunarska vizija, inteligentna robotika, inženjerstvo znanja itd. Razvojem računarske tehnologije i metoda VI u zadnjih deset godina, približavanjeis računara svim uzrastina, kao i uvodenjem raCunara u Skole, istraživačima VI obrazovanje postaje ¡i nteresantno polje rada. Deo VI, inženjerstvo ananja, po svojoj definiciji, metodama i rezultatima postaje direktno primenljivo i u obrazovanju, sa ciljem krajnje individualizacije obrazovnog procesa. Davnažnja težnja da Jedan nastavnik ili profesor obrazuje jednog učenika ovakvim- pristupom postaje realnost, kao i napredovanje svakog učenika prema njegovim sposobnost ima. U radu se dalje opisuju metode inženjerstva znanja i njihova primena u obrazovanju. Data je definicija i klasifikacija načina pretstavlJanja znanja, prlhvačena u inienjerstvu znanja. IskoriSčena je metoda M. Minskog 16) za reaiizaciju univerzalnog programskog paketa OSOF 13J za primenu računara u obrazovanj u. 2. inženjerstvo znanja U ranom razdoblju istraži vanja u ovoj podoblasti VI, do sredine 70-tih godina, težilo se Cpod uticajem psihologije}, iznalaženJu opatih metoda reSavanja problema "ekspertize" znanja, zasnovanih na opStim principima zaključivanja sa psiholoSkog aspekta. Ovakav pristup se pokazao neefikasnim za Von Neuman-sku oj -snizacijt' računara i sa milom primeni J ivoSču u praksi. Nedostatak je prevashodno Sto se unutar opSteg generalizovalo specifično znanje relativno disjunktnih oblasti. Krajem sedamdesetih godina se sa paradigme zasnovane na zaklJučivanju preSlo na novu paradigmu zasnovanu na znanju. Oblast delovanja istraživača inienjerstva znanja postaje istovetna sa oblastima delovanja stručnjaka iz pojedinih uskih oblasti: prikupljanje specifičnih znanja i iskustava, te potom i njihova primena u reSavanJu odredene grupe problema. Preduslov za ovakvo, heuristlčko, reSavanje problema Je izbor pogodne reprezentaciJe relevantnog znanja kome inteligentni program može lako da pristupi, dok mehanizam zaključivanja, tj. mehanizam koriščenja tako memorisanog znanja treba da je jednostavan i zasnovan na tom znanju umesto na opStim principima ili nekakvim funkcijama koreplikovanim za izračunavanje. Ljudsko znanje se kodira odredenim metodama u module koji se u mehanizmu zaklJučivanja aktiviraju uzorcima: "sirovi" podaci, "obradeni" podaci, parcijalna reSenJa, neočekivane situacije, greSke i si. Ovakvi uzoračko vodeni moduli imaju niz prednosti u odnosu na nekakav opSti aIgori tam zaklJ uč i vanj a: -predstavljanje znanja u delovima je primereniJ i načinu memorisanja znanja eksperata, -programiranje sa ovakvim modul ima omogučava razvoje inteligentnih sistema u koracima, programi se lako modifikuju i proSiruju, a greSke unutar znanja se poprav1jajubez izmene koda programa, i si. Proces konstruisanja Jednog lnteligentnog sistema obuhvata sledečih pet oblasti: -prikupiJanje i sistematizacija relevantnog znanja: od eksperta ili maSinsklm učenjem na primerima, -reprezentaciJa znanja: izbor pogodnog načina kojim se velika količina znanja može predstaviti pomoču simboličkih struktura podataka unutar računara, pogodnih za zaklJučivanje. Odabrana struktura treba da omoguči fleksibilne Izmene i dopune memorisanog znanj a, -primena znanja: planiranje i kontrola reSavanja problema, heuristlčko zaklJučivanje, tačnost i efikasnost rada lnteligentnih procesa, koje memorisano znanje predstavlja, -generisanje objaSnJenja: interakcija računal—čovek, objaSnjenje zaSto Je problem reSen na jedan a ne na neki drugi način, mogučnost učenja na greSkama i utlcanja čoveka na proces zaklJučivanja, -obrazovanje: saeSteno znanje se uz izvesne ograde može koristiti i za stvaranje 70 inteligentnih sistema učenja. 3. IN2ENJERSTVO znanja i obrazovanje Računaj- u obrazovanj u sa stanoviSta nastave se može posmatrati kao novo nastavno sredstvo i kao upravijač nastavnog procesa. Za razliku od konvencionalnih nastavnih sredstava Cgrafoskop, diaskop, interna televizija, responderi i dr.) računar u nastavni proces unosi značajnu novinu - mogučnost obostrane komunikacije računar -učenik. Nijedno od konvencionalnih nastavnih sredstava ne može da odgovara na pitanja učenika i da na taj način usmerava nastavni proces. JCao upravijač nastavnog procesa, raCunar u obrazovanju se posmatra kao neposredni izvrSioc nastavnog procesa kreiranog putem programske podrSke i upravljat raznih pomočnih uredaja nastavnog procesa Claboratorijski uredaji, responderi i dr.). Ovako posmatrana primena računara u obrazovnom procesu otvara mogučnost pri mena metoda i tehnika inženjerstva znanja u obrazovanju i otvara novo polje lstraiivanja - projektovanje inteligentnih sistema učenja. Projektovanjo ovakvih sistema učenja zahteva interakciju metoda inženjerstva znanja sa jedne strane i metoda pedagogije, metodike, didaktike i psihologije sa druge. Pretpostavka da se znanje koje sadrže ekspertni sistemi standardnog tipa nože iskoristiti i u svrhe obučavanja, demantuje se u praksi Jer su takvi inteligentni programi losi učitelji 141. Uzrok je upravo izostav1 janje osnovnih principa pedagogije i metodike pri kreiranju programskih sistema čija je svrha prvenstveno konsultanska pomoč pri reSavanju problema. Kreiranje posebnih inteligentnih sistema namenjenih obrazovanju, mora reSiti sledeče probleme: -kako predstaviti znanje koje učenik treba da usvoji, -kako opisati pojmove koj i se usvajaju, -kako usaglaslti mehanizam koriščenja takvog znanja sa metodički m i pedagoškim principima usvajanja znanja, -kako iskoristiti dobre osobine svih vrsta konvencionalnih načina prenosenja .i usvajanja znanja: predavanje, testiranje, eksperiment, opažanje, programirana nastava i dr. 4. sistemi reprezentovanja znanja Znanje se može definisati kao simbolička reprezentacija činjenica i relacija medu njima. Reprezentacija znanja je način predstavljanja znanja, kao i način kako se ono može povezivati sa drugim znanjem, koristiti za reSavanje novih situacija i izvoditi novo znanje. U ISJ reprezentacija znanja se definiSe kao skup sintaksnih i semantičkih konvencija koje omogučavaju opisivanje stvari. Sintaksa reprezentacije je skup pravila za formiranje, kombinovanje i uredenje izraza u Jeziku reprezentacije. Semantika reprezentaciJe odreduje kako se sintaksno valjani izraz koj i reprezentuje znanje interpretira, tj. kako se iz date forme može Izvesti i koristiti znante. Reprezentacija znanja je bitan element inJtenjerstva znanja koj i omogučava sistematičan način kodiranja znanja stručnjaka o nekom problemu unutar neke Sire kategorije. Ona implicitno obuhvata i organizaclju podataka u raCunaru za memorisanje znanja. Postoji niz notacijskih sistema za predstavljanje znanja u računaru. Zajednička karakteristika svih je da treba da obezbede brz pristup znanju i da se znanje može lako koristiti pomoču manje-viSe prirodnih mehanizama zaključivanja ili izvodenja. Programeru nakon odabiranja notacijskog sistema ostaje da izabere najpogodnlju strukturu podataka koja se implementira zadržavajuči sve dobre osobine izabranog notacijskog sistema. Važni kriterijumi za izbor notacijskog sistema 1 organizadJu podataka za reprezentaciJu znanja su: -logička dovoljnost tj. da formalizan može na pogodan način da opiše znanje, -efikasnost pristupa pri obradi znanja, -iskorlstivost, tj. reprezentovano znanje se može upotrebiti u reSavanju problema za koje su ta znanja dovoljna. Za reprezentaciJu znanja u primeni inženjerstva znanja se korlste sledeči formalizmi: produkcijska pravila, strukturni objekti i predikatska logika. Svi navedeni formalizmi se implementiraju sami ili u nekoj kombinaciji, u uzoračko vodenim sistemima. Struktura podataka koja pretstavlja unutrafinju reprezentaciju izabranih formalizaría pretstav1 janja znanja Je zavisna od problema koji se reSava, sistema zaključivanja, interpretatora mehanizma procesiranja znanja, računara na kome se implementira i programskog Jezika Izabranog za realizadJu odredenog inteligentnog sistema. Sistemi koji koriste neki od navedenih formalizama, se sastoje od niza relativno nezavisnih modula koji omogučavaju prikupiJanJe i memorisanje znanja, formiranje odgovarajuče unutraSnje reprezentaciJe znanja, koriščenje prikupljenog znanja i si. Produkcijska pravila su formalizan za predstavljanje znanja koji se koristi i u teoriji autómata, formalnim jezicima i dlzajniranju programskih jezika. Sastoje se od skupa pravila oblika: if (P, A . . . A p > then CA. A . . . A A ), 1 n 1 m gde su Pj , 1=1, . . . ,n uslovi, a A j , J»l, . . . ,m zaklJučci.Uslovi su trojke objekt - atribut -vrednost oblika: CBor Je_rudnlk bakar) dok su zaključci akcije koje se preduzimaju ako su uslovi zadovoljeni. Koriščenjem ovog formalizma kodiraju se iskustvene veze with VCO. 7) 1 m gde je VC0.7) verovatnoča da CP1 A . . . A p^j izvodi CA. A . . . A A >. i m Predikatska logika, u čijoj osnovi Je propozicioni i predlkatski račun, razvojem logičkog programiranja i logičkih programskih jezika, se koristi i kao sistem predstavljanja znanja. Znanje se predstavlja pomoču formula, kao napr.: Svako voli nekog <==> CvoliCx y» Ovakav načina opisivanja znanja se koristi u 71 reprezentacij i opStih člnjenica za raziiku od produkcijskih pravila u koj ima znanje predstavlja iskustvene Cinjenice. Strukturni objekti su op£ti izraz za bilo koju Senu reprezentacije znanja. Osnovni delovi strukturnih objekata su analogni Cvorovima i vezama u teoriji grafova, otvorima <"slot") i markerima teorije okvira ("fraae"), ili otvorima i puniočima <"filler"5 konvencionalnih struktura podataka tipa slog. Oni obuhvataju sledeče formalizme: semanticke Casoc1jativne nre2e>, okvire, objektno orjentisane sisteme, strukture konceptualne zavisnosti ili skripte. Predikatska logika i produkcijski sistemi kao formalizmi predstavljanja znanja se koriste za reprezentovanje razliti tih aspekata oko11ne. Medutlm, u opStem sluCaJu, oni ne dozvoljavaju da struktuirarao znanje o toj okolini. Strukturni objekti ukijuCuJu moguCnost reprezentovanja strukture znanja, grupisanjem delova znanja u celine i relacija medu znanjem, kao i pokaži vata na akciju koja se preduzima koriščenjem tog znanja. Takode se unutar strukturnih objekata pred v i da rad sa podrazumevanim Begin Članak < Pojam: Niska; Opis: Niska, Simulacija, Slika; F Pitanje: Zadatak > End ; Begin Zadatak < Opis: Niska, Simulacija, Slika; F Sledeči: Zadatak; F Odgovor: Alternativa > End; Begin Alternativa < Opis: < Izbor, Otvoreni odgovor, Uparlvanje ); F Akcija: < Članak, Zadatak, Dopuna_op i sa, Kraj >; F SledeCi: Alternativa > End; Begin Kraj < Ime: Niska; F Akcija: < Sekvenca, Članak, "Exit" 5 > End; U okvirima Sekvenca, Članak, Zadatak i Kraj "Niska" oznaCava tekst proizvoljne dužine, "Simulacija" proceduru za 'simuliranje nekog procesa, a "Slika" proceduru za grafickl prikaz proizvoljne slike. Unutar okvira Alternativa moguči zadaci koje uCenik treba da izvrSi su: "Izbor" - na postavljeni zadatak se odgovara izbor jedne od navedenih alternativa, "Otvoreni odgovor" - zahtev za eksplletni upls reienja i "Uparivanje odgovora" - postavljeni zadatak se reSava uparivanjem odgovarajuClh alternnativa iz dva skupa. Na osnovu uCenikovog reSenja zadatka, akcija raCunara se odvija prelaskom na: jedan od okvira članak, Zadatak i Kraj, ill grupu okvira Članak koji pružaju dodatno objaSnjenje nejasnog opisa ("Dopuna opisa"). Oznaka F ispred imena slota oznaCava da je njegova vrednost pokaživat na okvir. 6. SISTEM OSOF Sistem OSOF 131 Je razvljen u .Institutu za matematiku u Novom Sadu 1 sastoji se iz modula za prikupljanje znanja TEA, njegovu internu reprezentac1Ju po opisanoj Semi i dva modula elementarnog koriščenja za usvajanje znanja: izborom alternativa - LEA i testiranjem - EXA. Real izovan je programom vodenim meniJ ima 1 izuzetno Je Jednostavan za koristenje, te od nastavnika 1 utenika ne zahteva nikakvo znanje o ustrojstvu raCunara - niti znanje programiranja. Prlmenom sistema zaključeno Je da Je odabrana. metoda okvira pogodna za prlmenu u obrazovanju. LITERATURA: 1. Barr A., Felgenbaum E. A., Handbook of Artificial Intelligence, Stanford University Computer Science Dept, Stanford, <19805, USA 2. Buchanan B. Q., Felgenbaum E. A., Dendral and Meta-Dendral: their applications dimension. Artificial Intelligence, 1K1.25, 5-24, <19785, USA. 3. PauniC D., JerlnlC LJ. , Budimac Z., IvanoviC M. , Univerzalni programski paket za primenu raCunara u nastavi, u Stampi. 4. Clancey V. J., Methodology for building an intelligent tutoring system, from "Methods and tactics in Cognitive Science", Lawrence Erlbaun Publishers, <19835, USA. 5. Frost R. , Introduction to Knowledge Based Systems, Collins, London, <19865, Great Britain. 6. IvanoviC M., JerlniC L J . , PauniC D. , Budimac . Z., On knowledge representation in education, Review of research. Institute of Mathematics, Novi Sad, <19885,