Lindenmayer-rendszerek a középiskolában

Lindenmayer-rendszerek a középiskolában - Szakdolgozat Készítette: Molnár Katalin (Matematika BSc, Tanári szakirány) Témavezető: Buczolich Zoltán (Analízis Tanszék, Matematikai Intézet)

Eötvös Loránd Tudományegyetem Természettudományi Kar Budapest, 2010

TARTALOMJEGYZÉK

1

Tartalomjegyzék 1. Előszó

2

2. Elméleti bevezetés 2.1. A fraktálokról . . . . . . . . 2.2. Önhasonlóság . . . . . . . . 2.3. Dimenzió-fogalmak . . . . . 2.3.1. Topológiai dimenzió 2.3.2. Hausdorff-Besicovitch 2.3.3. Hasonlósági dimenzió 2.3.4. Doboz-dimenzió . . . 2.4. A Lindenmayer-rendszer . . 2.5. Imagine Logo . . . . . . . . 2.5.1. Behelyettesítés . . . 2.5.2. Előállítás . . . . . . 2.5.3. Kirajzolás . . . . . . 2.5.4. A verem adattípus . 3. Konkrét példák 3.1. Cantor-halmaz . . . . . . 3.2. Sierpinski-háromszög . . . 3.2.1. Sierpinski-szőnyeg . 3.2.2. Menger-szivacs . . 3.2.3. Sierpinski-tetraéder 3.3. Koch-görbe . . . . . . . . 3.3.1. Cesaro . . . . . . . 3.3.2. „Kochpihe” . . . . 3.3.3. Derékszögű Koch . 3.3.4. Koch-sziget . . . . 3.4. Lévy fraktál . . . . . . . . 3.5. Terdragon . . . . . . . . . 3.6. Cikk-cakk . . . . . . . . . 3.7. Sárkány görbe . . . . . . . 3.7.1. Sierpinski dragon .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . dimenzió . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . .

4 5 8 11 11 11 12 13 18 21 23 24 25 26

. . . . . . . . . . . . . . .

28 29 32 37 39 39 40 43 44 47 48 50 53 55 57 59

4. Mellékletek 60 4.1. Összefoglaló táblázat a dimenziókról . . . . . . . . . . . . . . . 60 4.2. A CD tartalma . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 5. Konklúzió

62

1 ELŐSZÓ

1.

2

Előszó

Szakdolgozatom témájául a fraktálokat választottam, mely a matematika egy viszonylag új keletű, ám gyorsan teret hódított területe. Nem véletlen ez a népszerűség: a fraktálok ábrázolása nem csak izgalmas dolog, de nagyon látványos is, az internetről letölthető ingyenes szoftverekkel (pl. Chaos Pro) pedig a matematikában kevésbé otthonos érdeklődők is könnyedén sikerélményekhez juthatnak. A téma elméleti hátterének tárgyalása azonban komoly analízisbeli ismereteket igényel, én erre csak vázlatosan fogok kitérni, célom ugyanis valami egészen más. . . Olyan középiskolai pedagógusoknak készült ez a gyűjtemény, akik fakultáción, vagy szakkörön szívesen foglalkoznának e témával, még ha Ő maguk nem is jártasak benne ezidáig. Úgy gondolom, hogy a pedagógusok fontos feladata, hogy felkeltsék a diákok érdeklődését és olyan eszközökkel oktassanak, hogy azok a diákokat élményben részesítsék, hogy ráérezzenek a tanulás, a tudás örömére. Szakdolgozatom ehhez nyújt segítséget: ötleteket, eszközöket tartalmaz, melyekkel a fraktálok komoly elméleti ismertetése nélkül is olyan foglalkozások tarthatóak, melyeket egy középiskolás érthet és élvezhet. Itt rögtön képbe jön egy mostanában szerencsére egyre többet emlegetett fogalom, a készségfejlesztés is. A téma algoritmikus gondolkodást, előre tervezést, a rekurzió fogalmának értését igényli, és így egyben fejleszti is ezen területeket, melyeket a középiskolai tanulmányok nem, vagy csak kis mértékben tesznek próbára. Szakdolgozatomban első lépésben a téma bevezetésével találkozhatunk, gondolok itt a téma elméleti hátterének, a tanítás általam választott eszközeinek bemutatására. Megemlítek majd ötleteket is, hogy a tárgyalt fogalmakat hogyan lehet egy középiskolás számára -az ő szintjén- elmagyarázni. Nem célom azonban pontos óratervek elkészítése, pedagógiai tanácsok felhalmozása, a foglalkozások megtartásának pontos menetét már a tanárokra bízom. Írásom számottevőbb része konkrét fraktálok bemutatásáról szól. Az adott fraktál pontos definícióját a pedagógusoknak szánom, annak könnyebb nyelvezetre fordítása már az Ő dolguk. Ez egy nehéz feladat, érdemes a foglalkozás előtt átgondolni, hogy hogyan érdemes a diákoknak bemutatni az előállítási szabályt (mely meg lesz adva L-rendszerben is), hogy biztosan és pontosan megértsék. Ez után, egyes fraktáloknál kimondok néhány állítást és észrevételt, esetleg a bizonyítást is; hogy ezeket milyen formában mutatja be a tanár a diákoknak, hogy a bizonyítás pontos megértését is elvárja-e tőlük, teljesen a célközönség képzettségi szintjétől függ - így ezt megint csak a pedagógusra bízom. A szakkör célja első körben tehát az ide tartozó könnyebb matematikai fogalmak megértése, a példák megismerése. A másik, lényegibb cél viszont egy Imagine Logo projekt elkészítése, mellyel lehetőség van az egyes frak-

1 ELŐSZÓ

3

tálok különböző paraméterezésű kirajzolására. Szakdolgozatom tartalmazza az ehhez szükséges kódokat, sőt az elkészült programban lehetőség lesz tetszőleges fraktálok kirajzolására is, olyan eljárásokkal, melyeknek bemenete a Lindenmayer-rendszerben leírt előállítási szabály. A szakdolgozat törzsében tehát konkrét L-rendszerek leírása található meg, Logo kódjukkal és L-rendszerbeli leírásukkal együtt. • A Logo-s kód, magyar nyelvű, egyszerű struktúrájának köszönhetően megfelelő tálalás mellett- azt hiszem, mindenképpen érthető a tizenéves korosztály számára is, nehézséget most csupán a rekurzió fogalmának megértése okozhat, de pont az a cél, hogy a sok példán keresztül a diákok ráérezzenek erre is. Ennek ellenére, nem tartom jó ötletnek, hogy azon diákok, akik korábban nem foglalkoztak még Logo-val, rögtön a fraktálokkal kezdjenek. Olyan iskolákba ajánlom ezt a témakört, ahol a Logo-t szervezetten (tanrend keretein belül vagy szakkörön) oktatják, és olyan diákoknak, akik már rendelkeznek a Logo-s rajzolás magabiztos alapjaival. • A Lindenmayer-rendszer ismertetése -az egyszerűbb példák esetén- azt hiszem, megint csak megértethető a középiskolásokkal, a két leírás közti párhuzam azonban nem hinném, hogy elsőre és könnyen észrevehető lesz számukra. Amikor már értik az összes példát és a párhuzamot is, akkor lehet elkezdeni az L-rendszeres Logo kódok elkészítését. Javaslatom az oktató számára, hogy eleinte, az (L-rendszerben is leírt) definíció, az ábra ismertetése után magyarázza el az azt előállító kódot, és csak utána, ha a diákok már számos példát megértettek, kezdjék el közösen, lépésről lépésre kitalálni a kódokat, míg aztán önállóan is képesek lesznek megírásukra. Remélem, munkám sok szakkört tartó, tehetség-gondozásban és készségfejlesztésben részt vállaló pedagógus számára nyújt majd segítséget és ötleteket.

2 ELMÉLETI BEVEZETÉS

2.

4

Elméleti bevezetés

Ebben a fejezetben a tárgyalt téma elméleti hátterét mutatom be. A középiskolás korosztálynak ezek a témakörök nehezen emészthetőek, a pontos definíciók és tételek kimondása így felesleges számukra, sokkal fontosabb, hogy azokat megsejtsék és pár konkrét példán keresztül, vagy speciális esetekben megértsék (pl. az euklidészi síkon). Az ok, amiért itt mégis leírom őket az, hogy a tanár, aki majd szakdolgozatom anyagát felhasználja, biztos alapokon álljon, és ne kelljen az egyébként elég hosszadalmas szakirodalomból a témához elégséges, néhány fogalmat kikeresgélnie. Az interneten egyébként rengeteg téves dolog található a fraktálok témaköréből, mely talán abból adódik, hogy sok, a matematikához úgy általában is laikus érdeklődő kezdett el foglalkozni a témával. Ezért nagyon fontosnak tartom, hogy mielőtt bárki is elkezdene fraktálokat rajzolgatni, szerezzen elég ismeretanyagot a matematikai hátteréről. Ehhez nyújt segítséget ez a fejezet.


2.1.

5

A fraktálokról

A fraktálok leírását szolgáló pontos definíció a mai napig nem létezik. Számos matematikus próbálta már különböző eszközökkel megfogni eme ponthalmazok mibenlétét, de hibátlan megfogalmazás nem született, mindig akadt néhány kivétel. Hogyan képzeljük hát el őket? Tudni kell, hogy az elnevezés a latin fractus szóból származik, melynek jelentése töredezett, törött. Nem véletlen: a klasszikus geometriai alakzatoknál jóval bonyolultabb, összetettebb, töredezettebb ábrákról van szó. Sőt, igazából nem is lehet őket ábrázolni: a végtelenségig nő, vagy éppen törik a vonaluk. Így sem a toll, sem a számítógép nem jó eszköz a kirajzolásukhoz, hiszen minden esetben végtelenbe tartó határértékről van szó, mely miatt az ábra vonalai folyton finomodnak. (Ebből adódik az a fontos tulajdonságuk, hogy „a végtelenségig felnyagyíthatóak”.) Közismert, de téves definíciója a fraktáloknak a következő: 2.1.1. Helytelen definíció. „A fraktálok tört-dimenziós alakzatok.” Ehhez először is tisztázni kell, mi is az a dimenzió (erről a következő fejezet szól), majd pedig látni fogjuk, hogy bizony akadnak itt is ellenpéldák. A másik helytelen definíciót szüli a következő tény: sokan a fraktál szó hallatán önhasonló alakzatokra gondolnak. 2.1.2. Helytelen definíció. „A fraktálok az önhasonló alakzatok.” Mielőtt belemélyednénk ennek a pontatlan asszociációnak az értelmezésébe, megjegyezném, hogy az önhasonlóság definíciója körül is elég nagy a zűrzavar (főleg az interneten). Olvashatunk ugyanis több különböző definíciót is, azok azonban korántsem ekvivalensek. Ennek bővebb tárgyalásával a következő fejezetben foglalkozom. A lényeg tehát, hogy szó sincs a fraktál és az önhasonlóság fogalmának ekvivalenciájáról! Vannak önhasonló alakzatok, melyek nem fraktálok, és léteznek fraktálok, melyek nem önhasonlóak; az önhasonlóság bármely értelmében. A sok definícó-próbálkozás helyett sokkal ésszerűbb, ha a tulajdonságaik alapján próbáljuk meg leírni a fraktálokat: • A fraktálok szokatlan, bonyolult struktúrájúak, így véges eszközökkel nem is lehet őket lerajzolni. • Előbbinek ellenére, gyakran kevés adattal is leírhatóak (pl. L-systemmel).


6

• A fraktálok „a végtelenségig felnagyíthatóak”. • Többségük tört-dimenziós. • A fraktálok egyes részeit felnagyítva, sok esetben az eredetire emlékeztető alakzatokat kapunk. • Hausdorff-dimenziójuk általában nagyobb, mint topológiai dimenziójuk (Mandelbrot). Ezen felsorolás segítségével, azt hiszem, már nem is olyan nehéz eldönteni valamiről, hogy fraktál-e vagy sem. Ajánlom a pedagógusoknak, hogy ezen tulajdonságok ismertetését csak példák bemutatása mellett sorolja fel a diákoknak, valamint érdemesnek tartom, ha közvetlenül ez után, mesél egy kicsit a diákoknak a fraktálok előfordulásáról (természetben és a mindennapokban), valamint a felhasználási lehetőségekről.

Példa: bináris fa Vegyünk egy növényt, mely a következőképpen nő: a nulladik évben megnő a szára adott hosszúságúra. Következő évben a kezdő szár kettéágazik: az új ágak a már meglévő szárral +45◦ , illetve −45◦ -os szöget fognak bezárni, hosszuk pedig fele akkora lesz, mint a kezdő szár. A 2. évben a két kinőtt ág fog úgy viselkedni, mint az első szár, mindegyik növeszt 2-2 ágat, a leírt módon. Ez a folyamat ismétlődik a végtelenségig, minden előző évben nőtt ágból nő két fele hosszúságú ág.

1. ábra. Bináris fa növekedése Nézzük meg, mely jellemzők igazak a bináris fára: • Mivel a végtelenségig nőnek újabb ágak, valóban nem lehet őket lerajzolni. Igaz, az ágak feleződnek, így az ághossz limesze a végtelenben nulla lesz; de ne feledkezzünk meg a felnagyítás lehetőségéről.


7

• L-systemben valóban kevés adattal megadható, erről később lesz szó. • Akárhogy felnagyítjuk, mindig fogunk felfedezni újabb ágakat. • A dimenzióval szintén később foglalkozunk. • Az első szárra nőtt jobb és bal oldali részek pont olyanok, mint maga az egész növény (csak kisebbek). Ezt a példát fogom végigvinni a többi elméleti tudnivaló tárgyalásánál is.


2.2.

8

Önhasonlóság

Azért adtam ennek a tulajdonságnak egy külön fejezetet, mert ez egy egyszerű fogalom, így a középiskolások is könnyen megérthetik. Ezenkívül, ez a fogalom fontos kapcsolatban áll a Lindenmayer-rendszerekben leírható fraktálokkal. Az előbbiekhez jön még az is, hogy -mint már említettem-, a fraktálokat sokan, mint önhasonló ábrákat képzelik el. Ez abból adódik, hogy ez a fraktáloknak az a tulajdonsága, aminek népszerűségüket köszönhetik. Nagyon izgalmas jelenség, amikor egy fraktált akár a végtelenségig is felnagyítva, egy ugyanolyan halmazt kapunk, mint amilyen az eredeti volt. De ne szaladjunk ennyire előre. A hasonlóság fogalma már általános iskolában is előjön, persze csak pár gyakorlati alkalmazás formájában. Nézzünk egy pontos, de nem általános iskolás definíciót: 2.2.1. Definíció. (X, d) metrikus térben f : X → X függvény hasonlóság, ha bármely két képpont távolsága az eredeti pontok távolságának ugyanazon pozitív skalárszorosa lesz, vagyis: ∀x, y ∈ X : d(f (x), f (y)) = λ · d(x, y). λ skalár, a hasonlóság aránya. Hasonló ábrák tanulmányozása során megfigyelhető egy fontos kapcsolat mértékeik között, az úgynevezett hasonlósági tulajdonság, mely szintén előjön középiskolában, többnyire a hossz és a terület, esetleg a térfogat vizsgálatakor: 2.2.2. Állítás. Két hasonló alakzat esetén elmondható, hogy ha a hasonlóság aránya λ, és 0 < M (A) < ∞, akkor 0 < M (f (A)) < ∞ is fennáll, és ddimenziós mértékeikre: M (f (A)) = λd · M (A). A hasonlóság után már nincs messze az önhasonlóság szigorú értelemben vett definíciója1 : 2.2.3. Definíció. Az (X, d) metrikus tér H nem üres, zárt részhalmaza önhasonló, ha: m [ H= fi (H), m ≥ 2, i=1

ahol fi -k, i = 1 . . . m-re az X-en értelmezett, 0 < λ < 1 arányú hasonlóságok.2 1

A későbbiekben önhasonlóság alatt ezt fogom érteni, ez ugyanis a legelterjedtebb és leghasználhatóbb definíció. 2 H az {fi } Iterált Függvény-Rendszer=IFS attraktora.


9

Ez azt jelenti, hogy a halmaz előáll önmagához hasonló alakzatok uniójaként. A λ-ra vonatkozó megszorítás azért kell, mert anélkül minden halmazt önhasonlónak mondhatnánk. Speciálisan3 : egy síkbeli alakzat önhasonló, ha előáll önmaga kicsinyített másaiból. A bináris fa ebben az értelemben nem önhasonló (a gond az első szárral van). Felhasználva a 2.2.2 állítást önhasonló halmazokra: 2.2.4. Állítás. Tegyük fel, hogy H önhasonló halmaz, mely az {fi } IFS-hez tartozik, {λi } arányokkal. Ha az fi (H)-k diszjunktak, akkor a következő összefüggés áll fenn: M (H) =

m X

M (fi (H)) =

i=1

m X

λdi · M (H).

i=1

0 < M (H) < ∞ esetén leoszthatjuk mindkét oldalt M (H)-val, és így: m X

λdi = 1.

i=1

Ezzel szoros kapcsolatban áll egy másik kifejezés, mely tipikusan a fraktálok lehetséges jellemzője. 2.2.5. Definíció. Skála-invariánsnak4 mondjuk az (X, d) metrikus tér H részhalmazát, ha annak bármekkora felnagyítása esetén, van olyan kisebb része Hnak, mely hasonló az egész halmazhoz.

2. ábra. Önhasonló, de nem skála-invariáns síkidomok Könnyen látható, hogy a bináris fa rendelkezik ezzel a tulajdonsággal, hiszen felnagyítása során, mindig kapunk az eredetihez hasonló ágcsoportokat. 3

Mivel szakdolgozatomban felhozott példák mind síkbeliek, ezért ezentúl elég, ha a síkban gondolkodunk. 4 A skála-invariancia kifejezés használatos más tudományterületeken is. Mi most a matematikai értelmezésével foglalkozunk csak.


10

Az önhasonlóság előbb tárgyalt definíciója nem jellemez minden fraktált. A Wikipédia angol szószedeténél ezt a (tágabb értelemben vett) leírást olvashatjuk: 2.2.6. Definíció. Olyan halmazra mondjuk, hogy önhasonló, ami (teljesen vagy csak megközelítőleg) hasonlít egy részéhez. Ezt valahogy úgy kell érteni, hogy az egész alakzatnak olyasmi az alakja, mint egy vagy több részének. Ez persze (csakúgy, mint a definíció) egy elég pontatlan megfogalmazás, hiszen a „része” kifejezés nem egy matematikai fogalom. A bináris fáról mindenestre elmondhatjuk, hogy a kezdő szárra illeszkedő ágcsoportok hasonlóak az egész fához (méghozzá λ = 12 aránnyal). Ugyancsak a Wikipédián olvasható az önhasonlóság topológiai definíciója, melyet középiskolában tárgyalni szerintem felesleges. 2.2.7. Definíció. (X, T ) topologikus, kompakt tér önhasonló, ha létezik {fs }s∈S nem szürjektív homeomorfizmusok véges halmaza, melyre: [ fs (X). X= s∈S

Ezt már nehezebb belátni. Legyen a bináris fa F ; F 1, F 2 és az elágazási

3. ábra. Bináris fa topológiai önhasonlósága S pontok az ábrának megfelelően. Ekkor F = F 1 F 2; legyen f1 (F ) = F 1 és f2 (F ) = F 2. Kellenek f1 , f2 : F → F nem szürjektív homeomorfizmusok. f2 -t nem nehéz megtalálni, ez egy λ = 12 arányú hasonlóság. f1 -et már kicsit nehezebb. AB szakasz képe legyen az ABB1 töröttvonal. A B-ből induló baloldali ágcsoportot képezzük a B1-ből induló, szintén baloldali ágcsoportba. Ugyanígy, a B-ből induló, jobboldali halmaz képe pedig a B1-ből induló, jobboldali rész.


2.3.

11

Dimenzió-fogalmak

A dimenzió szó még nem szerepel a középiskolás anyagban, de azt azért mindenki tudja, hogy az egyenes egydimenziós, a sík kettő, a tér pedig három. Ehhez még azt is hozzá tudják a diákok kapcsolni, hogy eltérő dimenziójú halmazokat eltérő mértékekkel jellemzünk: az egyenes részhalmazait hosszal, a sík részhalmazait területtel, a tér részhalmazait térfogattal. Érdemes azért felhívni a figyelmüket arra, hogy amikor a kétdimenziós síkidomok kerületét számoljuk, akkor valójában a „határaikat” vizsgáljuk. Egy síkidom határa egydimenziós egyenesekből áll: így a kerület nem más, mint az oldalvonalak hossza. Ugyanígy a (háromdimenziós) poliéderek esetén: a felszín a határoló (kétdimenziós) síkidomok területe.

2.3.1.

Topológiai dimenzió

Szemléletesen megfogalmazva, egy halmaz dimenziója: egy pontjának leírásához szükséges független paraméterek száma (ezért van, hogy a vektorgeometriában sík esetén kettő, tér esetén három koordinátával adunk meg egy pontot). A topológiai dimenzió ezt a naív ötletet használja fel, értékei így csak természetes számok lehetnek. Egyes halmazoknál azonban nem bizonyult túl jónak ez a dimenzió-definíció. Tipikusan a fraktálok elég furcsán viselkedtek. A később tárgyalt Cantorhalmaz egy dimenziós mértéke (hossza) nulla, így nem lehet egydimenziós, ugyanakkor nulladimenziósnak sem mondható (hiszen jóval több, mint egy pont). Hasonlóan: a Sierpinski-háromszög „kerülete” (∼ hossza, egydimenziós mértéke) végtelen, tehát több kell legyen, mint egydimenziós, területe (kétdimenziós mérték) viszont nulla, így dimenziója kisebb kell legyen, mint kettő. Ez persze csak egy heurisztika volt, de önhasonló halmazokra használható, és a középiskolások számára egy szemléletes, érthető megközelítése a dimenziófogalmaknak. Így tehát arra a következtetésre juthatunk, hogy érdemes lenne a természetes számok közötti valós értékeket is felhasználni a dimenzió jellemzéséhez.

2.3.2.

Hausdorff-Besicovitch dimenzió

Az előbbi problémákat kiküszöbölendő, született meg az új mérték-definíció, mellyel jellemezhetőek már az előbb említett „furcsán viselkedő” halmazok is, értékeként megengedett ugyanis bármely valós szám. Ezen dimenziófogalom alapötlete a halmaz gömbökkel való lefedésén alapul, a „legkisebb fedés” esetén a gömbök sugaraiból számolhatjuk ki értékét.


12

2.3.2.1. Definíció. Az (X, d) metrikus tér H részhalmazának átmérője: diam(H) = sup{kx − yk : x, y ∈ H}. 2.3.2.2. Definíció. Az Ai halmazok a H halmaz ε-fedését adják, ha ∀i = 1, 2, . . .-re diam(Ai ) < ε és [ H⊆ Ai . i

2.3.2.3. Definíció. Az (X, d) metrikus tér H részhalmazának Hausdorffmértéke: X Hs (H) = lim inf{ (diam(Ai ))s : {Ai } a H halmaz ε-fedése}. ε→0+

i

Nem túl nehéz belátni a következő állítást. 2.3.2.4. Állítás. Egyértelműen létezik olyan s0 , melyre: ∀s > s0 :

Hs (H) = 0 és

∀s < s0 :

Hs (H) = ∞.

Ezen alapul a várt definícó. 2.3.2.5. Definíció. Az előbbi tételben szereplő s0 a H halmaz Hausdorffdimenziója.

2.3.3.

Hasonlósági dimenzió

Az előbb tárgyalt Hausdorff-dimenziót csupán azért említettem meg, mert a fraktálelmélet egyik alapfogalma. Középiskolásoknak azonban még korai ezzel foglalkozniuk, nincs meg a kellő tudásuk hozzá. Vannak azonban fraktálok, amelyeknél a Hausdorff féle dimenzió megegyezik az úgynevezett hasonlósági dimenzióval, melynek megértése sokkal egyszerűbb. 2.3.3.1. Definíció. Az 2.2.4 állításból kapott H halmaz hasonlósági dimenziója.

Pm

i=1

λdi = 1 összefüggésben d a

Ahhoz, hogy használjuk ezt a definíciót, kellene, hogy az állításban szereplő fi (H) halmazok diszjunktak legyenek, ez azonban elég ritka. Szerencsére segítségünkre van egy tétel, melyet felhasználva kibővülnek a lehetőségeink.


13

2.3.3.2. Definíció. Azt mondjuk, hogy teljesül a nyílthalmaz feltétel (OSC)5 , ha m [ ∃V 6= ∅ nyílt halmaz, hogy V ⊃ fi (V ), m ≥ 2. i=1

2.3.3.3. Állítás. Tegyük fel, hogy fi : R 7→ R, (i = 1 . . . m) λi arányú hasonlóságokra teljesül az OSC. Ekkor {fi } attraktorának Hausdorff-dimenziója P d megegyezik a hasonlósági dimenziója, mely továbbra is a m i=1 λi = 1 képletből számolható ki. Elég tehát keresni egy alkalmas V halmazt, az adott fi hasonlóságokhoz, és megmutatni, hogy teljesül rá a nyílthalmaz feltétel. Így nem jelent gondot, hogy az fi (H) halmazok nem teljesen diszjunktak. Szakdolgozatomban szereplő önhasonló fraktáloknál a függvények azonos aránnyal rendelkeznek (0 < λ1 = λ2 · · · = λm < 1). Így a következőképp egyszerűsödik d kiszámítása, ha H k darab önmagához hasonló, diszjunkt halmaz uniója: k · λd = 1 1 λd = = k −1 k d = logλ (k −1 ) d=

lg k . − lg λ

Tehát a számlálóban van k - vagyis, hogy hány önmagához hasonló részből áll a fraktál, a nevezőben pedig ennek a hasonlóságnak az aránya. A képletet felírhatjuk bármely alapú logaritmussal. A bináris fáról nem mondható el a 2.2.4 állítás, így hasonlósági dimenzióját nem tudjuk kiszámolni.

2.3.4.

Doboz-dimenzió

A doboz-dimenzió, másképpen Minkowski-Bouligand dimenzió, esetleg boxdimenzió is egy alternatív dimenzió-fogalom, melyet érdemes egy-két példán keresztül megvizsgálni, számolása azonban nehézkes és sok esetben pontatlan. Az eljárás a következő: helyezzünk az alakzatra egy négyzetrácsot (magasabb dimenzióban kockarácsot, stb.), majd számoljuk meg, hány cella kell 5

OSC: Open Set Condition rövidítése.


14

minimálisan az alakzat lefedéséhez. Utána nézzük meg, mi történik, ha csökkentjük a cellák méretét: pl. a felére. Könnyű látni, hogy az egydimenziós halmazok esetén megközelítőleg ekkor kétszer annyi cella kell a lefedéshez, míg kétdimenziós alakzatok esetén négyszer annyi (5. ábra)6 . Jelöljük a lefedő rácsok számát Nε1 (H)-val, és ε1 legyen egy olyan egynél kisebb pozitív tört, mely azt mutatja meg, hogy az első lefedésnél az egységmérték hanyadrésze a cella oldala. Egy Db dimenziós alakzatnál igaz, hogy ha ε2 = ε1 · α (0 < α < 1) a második lefedésnél alkalmazott rácsméret, akkor: Nε2 (H) = Nε1 (H) · α−dimB H . Tehát nemcsak azt tudjuk, hogy kisebb rácsnál nő a lefedések száma, hanem azt is, hogy ennek a növekedésnek a mértéke az alakzat dimenziójától függ. Tudni kell azonban, hogy ezek mind csak megközelítőleg igazak, valójában a rácsot egyre finomítani kell, hogy minél pontosabb értéket kapjunk. Figyelembe véve ezt, és átrendezve az előbbi egyenletet, megkapjuk a dobozdimenzió definícióját. 2.3.4.1. Definíció. Adott H halmaz doboz-dimenziója7 : dimB H = lim

ε→0

lg Nε (H) . − lg ε

Tudjuk, hogy nagyobb x = − lg ε érték esetén nagyobb lesz f (x) = lg Nε (H), de hogy mennyivel, az a lefedett alakzat dimenzójától függ. A logaritmusra azért van szükség, hogy egy elsőfokú függvényt kapjunk. Így ki tudjuk használni az f : − lg ε 7−→ lg Nε (H) függvény tulajdonságait: nincs más dolgunk, mint megnézni a függvény meredekségét.

Példa: Egyenes A 5. ábra alapján, vegyük egységhossznak a ciánkékkel színezett beosztások 1 . A vízszintes hosszát. Ekkor az első esetben ε1 = 71 , a másodikban ε2 = 14 vízszintes tengely értékei a 2.3.4.1 képlet nevezője, esetünkben x1 = − lg 17 ≈ 1 0.8451, x2 = − lg 14 ≈ 1.1461. A megfelelő függvényértékek a számlálóban szereplő kifejezésből, f (x1 ) = lg 7 ≈ 0.8451, f (x2 ) = lg 14 ≈ 1.1461. Ezt ábrázolva már nem okozhat nehézséget kiszámolni a függvény meredekségét, ami pontosan 1. (Lásd: 4. ábra.) 6 7

Ez függ a cellák méretétől, vagy az alakzat rácshoz viszonyított elhelyezkedésétől is. A nevezőben azért szerepel mínusz jel, mert 0 < ε < 1.


15

4. ábra. Egyenes és négyzetlap box-dimenziójának kiszámításához használt függvények

5. ábra. Egyenes és négyzetlap lefedése ráccsal Példa: Négyzetlap Bár az 5. ábrán csak a négyzet körvonalát jelöltem, tartsuk szem előtt, hogy ez egy négyzetlap, melynek topológiai dimenziója kettő, tehát a box-dimenzió értékétől elvárjuk, hogy ezzel megegyezzen. 1 Egységhossz, mint előbb, így ismét ε1 = 17 , és ε2 = 14 ; x1 ≈ 0.8451, x2 ≈ 1.1461. A függvényértékek a kiszínezett rácsoknak megfelelően most f (x1 ) = lg 49 ≈ 1.6902, f (x2 ) = lg 196 ≈ 2.2923. A meredekséget kiszámolva 2.0037-t kapunk, ami csak a kerekítés miatt nem lett pontos.

Ezen példáknál könnyű dolgunk volt, minden pont úgy viselkedett, ahogy azt vártuk. Sok esetben azonban nincs ilyen nagy szerencsénk.

Példa: Bináris fa Próbálkozzunk az előbbi módszerrel, és fedjük le az ábrát kétféle ráccsal. 1 1 , és ε2 = 28 , így x1 ≈ 1.1461, x2 ≈ 1.4472. Az első esetben Most ε1 = 14


16

58, a második esetben 125 rácsnégyzet kellett a fedéshez8 , így f (x1 ) ≈ 1.7634, f (x2 ) ≈ 2.0969.

6. ábra. Bináris fa lefedése A pontokat ábrázolva, a függvény meredeksége 1.1076, ami nem túl pontos eredmény. 1 cellaméret eseÉn lefedtem ezt az ábrát pixel méretű rácsokkal is, ε3 = 400 9 tén a lefedéshez Nε3 (B) = 1799 pixel kellett . Ekkor az f (x1 ), f (x3 ) pontokra illesztett egyenes meredeksége:

3.255 − 1.7634 lg Nε3 (B) − lg Nε1 (B) ≈ ≈ 1.0245 − lg ε3 − (− lg ε1 ) 2.6021 − 1.1461 A kiszámolt függvényértékekre illesztett egyenes vizsgálata helyett meg lehet próbálni a limeszt megtippelni. Nézzük sorban a hányadosokat, hogy megsejtsük a határértéket: lg Nε1 (B) 1.7634 = 1.5386 = − lg ε1 1.1461 lg Nε2 (B) 2.0969 = = 1.4489 − lg ε2 1.4472 lg Nε3 (B) 3.255 = = 1.2509 − lg ε3 2.6021 A konvergencia nem elég gyors. 8

Emlékezzünk rá, hogy azt mondtuk, hogy egydimenziós alakzatok esetén elméletileg kétszer annyi rács kell a fedéshez, ha fele akkora rácsméretet használunk. Gyakorlatilag ez függ a cellák elhelyezkedésétől. 9 ImLab nevű ingyenes programmal lehetőség van a különböző színű pixelek megszámolására, a Process/Statistics/Image Statistics menüpontokon keresztül.


17

Látható, hogy a bináris fánál egyik módszerrel sem kaptunk pontos eredményt, ezekből a számításokból legfeljebb arra a következtetésre juthatunk, hogy a dimenzió valahol egy körül van. A gond egyrészt a bináris fával van 10 , másrészt a módszer egyébként is, sok helyen pontatlan. Utóbbi szemléltetésére a [10] honlapon találni egy jó ábrát:

7. ábra. Egy tipikus box-dimenzió számolásánál kapott értékek.

10

Bebizonyítható, hogy a bináris fa box-dimenziója egy és végtelen mértékű, emiatt a konvergencia elég lassú.


2.4.

18

A Lindenmayer-rendszer

Aristid Lindenmayer (1925-1989) magyar származású, holland biológus és matematikus. A növények fejlődésének tanulmányozása céljából kidolgozott egy módszert, mellyel a növekedés folyamatát tudta rögzíteni. Ezzel egy eszközt adott a vonalas fraktálok szöveges leírásához11 , mely a „toll” mozgatásának irányát és hosszát megadó szimbólumokból áll. Lássuk, mely jelölések használhatóak12 : • F : Adott hosszú szakasz rajzolása. • G: Előrehaladás adott hosszal, vonal rajzolása nélkül. • X, Y : Ezen jelölések esetén, rajzolás szempontjából nincsen teendőnk. • +, −: Adott szöggel való elfordulás; pozitív, illetve negatív irányban. • [ , ] : Toll pozíciójának eltárolása verembe, ill. veremből való kiolvasása. • @λ: Az adott hossz növelése λ-szorosára. Ahhoz, hogy egy ábrát leírjunk ezen rendszerben13 , a következő struktúraelemeket kell megadnunk: • Axióma: a rendszer kezdeti állapota, vagyis a „nulladik lépés” (például egy vonal). • Szög: vagy egyszerűen fokban, vagy az a szám, mellyel 360◦ -ot osztva a kívánt szöget kapjuk. • Formula: ez tartalmazza az előállítás szabályát, az axiómából kiindulva ismételgetve be kell helyettesíteni az itt megadott módon az értékeket. Fraktáloknak ez a fajta megadása -a behelyettesítgetés miatt- rekurzión alapul, ez azt eredményezi, hogy a fraktálnak lesznek az eredeti alakhoz hasonló részei (2.2.6. definíció). 11

Gyakran használják a „Lindenmayer-rendszerek” kifejezést azon fraktálok gyűjtőneveként is, melyek leírhatóak ilyen módon. 12 Előfordulnak egyéb jelölések is, de nekünk elegek lesznek ezek. 13 A rendszer megnevezésére használatosak még a Lindenmayer-system, L-sys, L-rendszer kifejezések is.


19

Példa: bináris fa Nézzünk meg a már ismert bináris fát, hogy gyakorlatban is lássuk a fent leírtakat. Az talán elsőre világos, hogy a kiinduló állapot a kezdő ág, az axióma tehát: • Axióma: F A szög megadásával sincs gond: • Szög: 45◦ (másképpen 8, mivel 45 =

360 ) 8

A behelyettesítési szabály megadása már elgondolkodtató. lépésenként. Elsőként figyeljünk csak az elágazásokra:

Építsük fel

• Formula: F = F [+F ][−F ] Ez még nem nehéz, a formulát behelyettesítgetve megkapjuk az ágakat. Azok elágazását a „[” és „]” szimbólumok valósítják meg. 0. év: F 1. év: F [+F ][−F ] 2. év: F [+F ][−F ][+F [+F ][−F ]][−F [+F ][−F ]] Tovább fejlesztve az előbbi kódot, most már a szakaszok csökkenésére is figyeljünk: „@0.5” jelöli a hossz felezését. • Formula: F = F [[email protected] ][−@0.5F ] Nézzük meg ismét évekre bontva: 0. év: F 1. év: F [[email protected] ][−@0.5F ] 2. év: F [[email protected] ][−@0.5F ][[email protected] [[email protected] ][−@0.5F ]][−@0.5F [[email protected] ][−@0.5F ]]


20

Ezzel a leírással -bár megfelelő ábrát rajzol ki- az a gond, hogy bizonyos szakaszokon többször is áthalad a „toll”. Gondoljunk csak bele, a 2. évben 1 + 2 + 2 · 2 = 7 ága van a növénynek, míg a fenti leírás 9 db „F ” szimbólumot tartalmaz.14 Ennek elkerülése érdekében kell bevezetni az „X” jelölést is. • Axióma: F X • Szög: 45◦ (másképpen 8) • Formula: F = F ; X = @0.5[−F X][+F X] Ellenőrizzük le, helyes-e a szabály: 0. év: F X 1. év: F @0.5[−F X][+F X] 2. év: F @0.5[−F @0, 5[−F X][+F X]][+F @0, 5[−F X][+F X]] Ez már egy tökéletes leírása a növény növekedésének.

14

Érdemes lerajzolni, hogy hol lesznek többszörös ágak, és kitalálni miért. Ha rájövünk ennek okára, már azt is tudni fogjuk, Pn hogy a 3. évben a 15 ágat 27 szakasz fogja megvalósítani. Az n. évben a többlet 2 · i=1 2i .


2.5.

21

Imagine Logo

Az Imagine Logo a Logo „programozási nyelv” legújabb környezete, mely rengeteg új lehetőséget ad a korábbi Comenius Logo-hoz képest. Magáról a Logo nyelvről azt kell tudni, hogy kifejezetten oktatási célokra, tanároknak és diákoknak készült. Bármely környezete ingyenesen letölthető, a létrehozott munkák szabadon cserélhetnek gazdát. A könnyen érthető, magyar szintaktikájának, valamint felhasználóbarát környezetének köszönhetően már egész kiskorú diákoknak oktatható, nekik a teknőc megszemélyesítése, a programmal való kommunikáció azonnali, látványos eredménye teszi vonzóvá a program használatát. Kis korban inkább csak a teknőssel való rajzolást szokták oktatni, de mint látni fogjuk, már csak ennek a funkciónak a használata is sokféle felhasználhatóságot rejt magában. A programozási környezetekben megszokott eljárások és függvények itt tulajdonképpen azt jelentik, hogy a teknősnek megtanítunk egy új szót. Ez az új környezet rengeteg új funkciót is tartalmaz, úgy mint a web-szerkesztés és multimédiás alkalmazások, ezekkel mi azonban most nem foglalkozunk. Amiért én mégis ezt az újabb környezetet választottam, annak oka a (Comeniushoz képest sokkal jobb) stabilitása, valamint a változók széleskörű kezelési lehetősége. Nem szeretnék ennél többet mesélni az Imagine Logo oktatási lehetőségeiről, erről olvashatunk többek közt a hivatalos honlapon [13] is, ahonnan egyébként maga a program, és számos oktatási anyag is letölthető. Mindenesetre remélem, hogy gyorsan, és egyre szélesebb körben tért hódít majd, mint egy elengedhetetlen oktatási eszköz. Olyan tanároknak és diákoknak ajánlom e témakörrel való foglalkozást, akik már jártasak a Logo nyelv használatában, bár a programmal azt hiszem, gyorsan megismerkedhetünk. Ebben számos honlap, szakirodalom segítségünkre lehet [13] [14]. A mellékelt CD-n természetesen szerepel az egész projekt, ezt felhasználóként, és a kód után érdeklődő fejlesztőként is kipróbálhatjuk. Mivel az elkészült projektemet .exe kiterjesztéssel is elmentettem, lehetőség van a fraktálok kirajzolására a program telepítése nélkül is, ekkor viszont nem változtathatunk az eljárások paraméterein, ez pedig a mélység esetén rengeteg élménytől foszt meg minket. Amennyiben tehát a program installálása mellett döntünk, a telepítést követően a következő beállítások ajánlottak: • Ablak/Gombok ablak: Elhelyeztem pár beépített parancsot, melyek a gombokkal hívhatóak meg. Ezekkel példát láthatunk arra, hogy egy eljárást hogyan kell meghívni (hisz a kiadott parancs megjelenik alul, az írólapablakban; sőt a felfele nyíllal bemásolódnak a parancssorba a korábban kiadott parancsok, így elég a paramétereket átírni). • Ablak/Intéző: Itt láthatjuk a programot felépítő elemeket: eljárások,


22

változók, rajzlapelemek. Az eljárásokra duplán kattintva nézhetjük meg a kódjukat, illetve a meghívásukhoz szükséges paraméterlistát, ezeket igyekeztem találóan elnevezni, hogy programhasználatkor ne kelljen újra és újra fellapozni a később leírt eljárás-magyarázatokat.

8. ábra. Az Imagine Logo felülete A programmal rajzolt ábrák elmenthetőek a Lap/Rajzlapmentés menüponton keresztül, szakdolgozatomban lévő ábrák is mind így készültek, illetve az Imagine-hez járó Logomotion programmal. A rajzlapot amúgy úgy kell elképzelni, mint egy kétdimenziós, Descartes-féle koordinátarendszert. A vízszintes tengely −385-től +385-ig tart, míg a függőleges −300-tól +300-ig. A teknős alappozíciója (0; 0); kezdő iránya a vízszintes tengely pozitív irányába mutat. Ezen a síkon fogjuk a teknőst irányítani; amennyiben nem az adott intervallumon belüli értéket adunk meg -pl. túl nagy x vagy y értéket-, a teknős „átfut” a túloldalra (mintha a rajzlapot összehajtanánk egy tórusszá). Emiatt (385; −300) = (−385; 300). Szakdolgozatom minden későbbiekben tárgyalt fraktál Logo kódját tartalmazza majd, azok szűkszavú magyarázatával együtt. Annyit viszont előrebocsátanék, hogy ezen kódok nem a „végleges” ábrát (határértéket) rajzolják ki, csak bizonyos mélységig tudja a program a fraktálokat megjeleníteni, és így nagyításuk sem lehetséges. A pixelek okozta korlátok és a kerekítés miatt előfordulhat a rajzok pontatlansága, vagy nem megfelelő hossz megadásánál van, hogy az ábra folyton felülíródik, nem jelenik meg rendesen, esetleg végtelennek tűnő folyamatba kerül a teknős15 . Ilyen esetekben használjuk a fő eszközsorban található „Megállít” gombot. 15

Pl. kezd -150 -250 0 Sierpinski 300 13 (illetve magasabb szint)


23

Ahhoz, hogy a rajz a letörölt rajzlapra, a megfelelő helyre kerüljön, érdemes bármely kirajzoló eljárás előtt meghívni a kezd nevű (saját) eljárást; ennek három paramétere a teknős x és y koordinátája, és az elfordulási szöge. A programban lehetőség van arra is, hogy egy általános, szinte teljesen tetszőleges Lindenmayer-rendszert is kirajzoltassunk [15], annak előállítási szabályát megadva. A következőkben sorra veszem az idetartozó eljárások működését, használatukat bemutatom a már ismert bináris fán keresztül, illetve kitérek egyéb fontos tudnivalókra is16 . Ezzel a módszerrel kirajzolhatóak a később tárgyalt ábrák is, de ez nem teszi feleslegessé azok saját eljárását, hiszen azok több lehetőséget tartalmaznak, „okosabbak”, ugyanakkor talán egyszerűbbek is, ajánlatos azok oktatásával kezdeni, hisz az itt tárgyalt módszer mélyebb belegondolást, komolyabb szakmai hátteret igényel.

2.5.1.

Behelyettesítés

A helyettesítés eljárás egy bemeneti karakterláncba (string-be) helyettesíti be a szimbólumok L-rendszerben megadott formuláját. Ez az n-edik behelyettesítés előállításához kell majd. Bemenetként tehát a kezdő szöveget, valamint F, G, X, Y formuláit várja. Pl. „FX” bemeneti sztring esetén, F = F ; X = @0.5[−F X][+F X] szabályokkal a kapott eredmény „[email protected][-FX][+FX]”. Ennek pontos meghívása a projektben kicsit módosul: • a Logo nem támogatja a „ . [ ] ” karaktereket, helyettük „ , ( ) ” karakterek használandóak • speciális karakter használatára pipe-okkal („|” jelekkel) kell felhívni a program figyelmét (| . . . |) • mivel a program szavakat vár paraméterként, a sztringek elé ki kell tenni a „"” jelet • a fix paraméter-lista miatt meg kell adnunk azon szimbólumok helyettesítési értékét is, melyek esetleg nem is szerepelnek a kifejezésben (F, G, X, Y ) Tehát a fenti példa esetén: :be :fformula helyettesítés "FX "F

16

:gformula "G

:xformula :yformula "|@0,5(−FX)(+FX)| "Y

A leírást itt is a tanároknak szánom, a diákoknak való magyarázat jóvalta hosszabb, és részletesebb kell legyen.


24

Ennek hatására a program a következőt írja ki: „Nem tudom mit csináljak a(z) F@0,5(−FX)(+FX)-val. Nem mondtad meg, mit csináljak az eredménnyel.” Innen olvasható ki a megfelelő behelyettesítés során kapott sztring. Ha :be helyére az előbbi eredményt írjuk be, akkor a helyettesítés a következő szintet (2. év) adja vissza. Nézzük az eljárás pontos működését. A technika az, hogy levágom a bemenet első betűjét, megvizsgálom, hogy mi az, majd rekurzióval a maradék részt ugyanígy feldolgozom. Ha az előbbi első betű F, G, X, Y valamelyike, akkor az eredményben ezt a karaktert kicserélem a formulájára, majd tovább haladok. Ha egyéb karakter17 , akkor azt úgy hagyom, és vizsgálom tovább az első betű nélküli szöveget. Tehát a pontos kód: eljárás helyettesítés :be :fformula :gformula :xformula :yformula hakülönben üres? :be [er :be] [elágazás (első :be) [ f F [er szó :fformula helyettesítés en :be :fformula :gformula :xformula :yformula] g G [er szó :gformula helyettesítés en :be :fformula :gformula :xformula :yformula] x X [er szó :xformula helyettesítés en :be :fformula :gformula :xformula :yformula] y Y [er szó :yformula helyettesítés en :be :fformula :gformula :xformula :yformula] + [er szó "|+| helyettesítés en :be :fformula :gformula :xformula :yformula] - [er szó "|-| helyettesítés en :be :fformula :gformula :xformula :yformula] ( [er szó "|(| helyettesítés en :be :fformula :gformula :xformula :yformula] ) [er szó "|)| helyettesítés en :be :fformula :gformula :xformula :yformula] @ [er szó "|@| helyettesítés en :be :fformula :gformula :xformula :yformula] 0 [er szó "|0| helyettesítés en :be :fformula :gformula :xformula :yformula] 1 [er szó "|1| helyettesítés en :be :fformula :gformula :xformula :yformula] 2 [er szó "|2| helyettesítés en :be :fformula :gformula :xformula :yformula] 3 [er szó "|3| helyettesítés en :be :fformula :gformula :xformula :yformula] 4 [er szó "|4| helyettesítés en :be :fformula :gformula :xformula :yformula] 5 [er szó "|5| helyettesítés en :be :fformula :gformula :xformula :yformula] 6 [er szó "|6| helyettesítés en :be :fformula :gformula :xformula :yformula] 7 [er szó "|7| helyettesítés en :be :fformula :gformula :xformula :yformula] 8 [er szó "|8| helyettesítés en :be :fformula :gformula :xformula :yformula] 9 [er szó "|9| helyettesítés en :be :fformula :gformula :xformula :yformula] , [er szó "|,| helyettesítés en :be :fformula :gformula :xformula :yformula] ] ] vége

2.5.2.

Előállítás

Itt használjuk fel az előbbi eljárást: az előállítás már képes a formulákat többszörösen is behelyettesíteni a kezdő, illetve előzőleg kapott sztringbe, melynek így elég, ha az axiómát adjuk meg. Működésének elve szintén rekurzión, és a sztring „első” karakterének vizsgálatán alapul. Meghívása annyiban módosul 17

Feltételezem, hogy csak az { F G X Y ( ) + − @ 1 2 3 4 5 6 7 8 9 0 , } karakterhalmazból kerülnek ki a paraméterekben megadott sztringek betűi.


25

az előbbi eljáráséhoz képest, hogy itt a bemeneti sztringnek elég az axiómát megadni, valamint kibővült a paraméter lista :szinttel, melyben azt adhatjuk meg, hogy mely mélységű ábrát szeretnénk előállítani: előállít "FX "F "G "|@0,5(−FX)(+FX)| "Y 2 Ekkor az eredmény: F@0,5(−F@0,5(−FX)(+FX))(+F@0,5(−FX)(+FX)). Az eljárás kód a helyettesítés használata miatt lerövidül: eljárás előállít :axioma :fformula :gformula :xformula :yformula :n ha :n = 0 [eredmény :axioma] eredmény előállít (helyettesítés :axioma :fformula :gformula :xformula :yformula) :fformula :gformula :xformula :yformula :n-1 vége

2.5.3.

Kirajzolás

Ezt az eljárást már sokkal könnyebb megírni: nincs más dolgunk, mint feldolgolzni egy kapott szöveget, mely a fraktált L-rendszerben használatos szimbólumokkal, de már „készen” írja le. A 2.4. fejezetből már tudjuk, hogy melyik jelölés a toll milyen mozgását írja le. Amit nagyon fontos tudni a működéséről, hogy ennek az eljárásnak a :hossz paramétere nem ugyanaz, mint az egyes fraktálok kirajzolására írt eljárások :hossz paramétere! Azok ugyanis a fraktál „teljes” hosszát várják paraméterként, melyet intelligensen a szintnek megfelelően leosztanak, és valójában a :hossz valahányad részével dolgoznak (mint szakasszal). Itt viszont :hossz -t, mint F hosszát, vagyis az egységhosszúság pixelekben mért értékét kéri az eljárás. Magasabb szintnél értékét érdemes csökkenteni, különben a teknős kifut a képernyőről. Később minden említett fraktálnál adok egy példát arra, hogy milyen értékkel hívjuk meg ezt az eljárást, hogy a legoptimálisabb eredményt kapjuk. eljárás kirajzol :sor :hossz :szög ha nem üres? :sor [ elágazás első :sor [ f F [előre :hossz] g G [tollatfel előre :hossz tollatle] + [balra :szög] - [jobbra :szög] ... (Veremhasználat; erre majd a következő fejezet tér ki.) ] kirajzol elsőnélküli :sor :hossz :szög ] vége


26

Ez a kód sajnos nem tér ki a „@” szimbólum értelmezésére. Nem állítom, hogy a Logo-ban nincs lehetőség ezt megvalósítani, de mivel nem tudjuk előre, hány karaktert fog elfoglalni λ értéke, valamint nehézkes a különböző hosszak tárolása (ezt is veremmel lehetne megoldani), ezért ezt a részt nem írtam meg. Ezért, most a bináris fa egy olyan változatát fogom példaként bemutatni, ahol az ágak azonos hosszúak, sőt, változtattam a korábban megadott 45◦ -on:

9. ábra. Bináris fa 30◦ -kal, egyenlő ágakkal

kirajzol

:sor előállít "|FX| "F "G "|(−FX)(+FX)| "Y 4

:hossz 30

:szög 30

Lehet próbálgatni egyéb módosításokat is, például, ha „fúj a szél”: kirajzol

:sor :hossz előállít "|FX| "F "G "|(−−FX)(+FX)| "Y 8 30

:szög 10

10. ábra. Bináris fa 10◦ és 20◦ -kal, egyenlő ágakkal

2.5.4.

A verem adattípus

Az általános Lindenmayer-rendszerek kirajzolásánál, a „[” szimbólum használatakor el kell tárolni a teknős pozícióját, hisz a „]” jel után a teknősnek oda kell visszaugrania. Több egymásba ágyazott ilyen zárójelezésnél nem csak, hogy több adatot is őriznünk kell, de mindig a legutoljára eltárolt adatot kell újra felhasználnunk. Ennek megvalósítására érdemes létrehozni egy „vermet”, mely pontosan ennek megfelelően működik [12]: verembe helyezéskor mindig annak legtetejére kerül az elem, és a veremből műveletnél is a legfelső elemet


27

vesszük onnan el (hisz a verem elemei csak a veremtető mutatóval érhetőek el).

11. ábra. A verem működése Én a vermet a Logoban gyakran használt listával valósítottam meg (verem nevű globális változó), a veremkezelést pedig az ismert mondat, utolsó, utolsónélküli parancsszavakkal. Az x, y, i nevű globális változóim azt a célt szolgálják, hogy kiolvasva a verem három felső elemét ezekbe be tudjam állítani a teknőst a megfelelő pozícióba és irányba. A veremkezelést megvalósító eljárásaim: eljárás verembe :új állít! "verem mondat verem :új vége

Vagyis a verem változó új értéke verem és az :új -ban kapott érték egymásutánja lesz. eljárás veremből állít! "i utolsó verem állít! "verem utolsónélküli verem állít! "x utolsó verem állít! "verem utolsónélküli verem állít! "y utolsó verem állít! "verem utolsónélküli verem vége

Tehát a megfelelő változók a verem lista utolsó elemét veszik fel értékként. Egyszerre mindhárom adatot kiolvasom, emiatt viszont figyelni kell, hogy a kiolvasás a verem tulajdonságai miatt fordított sorrendben történjen. Ezeket az eljárásokat a már ismert kirajzolásnál használom, a megfelelő elágazásban, vagyis ha egy zárójelet kell feldolgozni: eljárás kirajzol :sor :hossz :szög ha nem üres? :sor [ elágazás első :sor [ ... ( [verembe xpoz verembe ypoz verembe irány] ) [veremből irány! i poz! lista x y] ... ] vége

3 KONKRÉT PÉLDÁK

3.

28

Konkrét példák

Ebben a fejezetben néhány közismert, és pár ritkább fraktált is be fogok mutatni, L-systemes felírásukkal és Logo kódjukkal együtt. A sorrendet igyekeztem lépcsőzetesen felépíteni; az egyszerűbb ábrákat módosítási lehetőségekkel színezni. Ha már belejöttek a diákok ezen fraktálok értelmezésébe és leprogramozásába, nem lesz nehéz nekik újabb, saját fraktálokat kitalálniuk, majd jellemezniük, ami nemcsak a kreativitásukat fejleszti, de sikerélményben is részesíti őket.

3 KONKRÉT PÉLDÁK

3.1.

29

Cantor-halmaz

A Cantor-halmaz kitalálója, mint neve is mutatja, a halmazelmélet atyja (Georg Ferdinand Ludwig Philipp Cantor ). Akkor ez az ábra még csak egy matematikai játéknak tűnt, jelentőségére és különleges tulajdonságaira elsőként Benoît Mandelbrot hívta fel a figyelmet. Szokás Cantor-pornak is hívni, hisz a limesz valójában egy „porszerű” képződmény. Ez a legkorábban felfedezett, egyben a legegyszerűbb fraktál.

12. ábra. Cantor 800 5

Definíció A hagyományos Cantor-halmaz R-nek egy olyan részhalmaza, mely legkönynyebben egy sorozat határértékeként adható meg. Legyen a kezdő elem: C0 = [0, 1]. Ebből C1 úgy nyerhető, hogy a [0, 1] szakasz középső harmadát kivesszük: 1 2 C1 = 0, ∪ ,1 3 3 és ehhez hasonlóan 1 2 1 2 7 8 C2 = 0, ∪ , ∪ , ∪ ,1 9 9 3 3 9 9 és így tovább. Könnyen látható, hogy ezek a halmazok csökkenőek: C0 ⊇ C1 ⊇ C2 . . . . Így a hagyományos Cantor-halmaz megadható, mint ezen Cn sorozat határértéke: \ C = lim Cn = Ck . n→∞

k∈N

Állítások 3.1.1. Állítás. A Cantor-halmaz teljes hossza nulla. Bizonyítás: Könnyen látható, hogy Ck , 2k db diszjunkt, zárt intervallumból áll, ezek hossza ( 31 )k ; így Ck teljes hossza ( 32 )k . A határérték: limk→∞ ( 23 )k = 0.

3 KONKRÉT PÉLDÁK

30

3.1.2. Állítás. Tetszőleges k-ra, ha [a; b] egyike a Ck -t alkotó zárt intervallumoknak, akkor ∀m ≥ k : a, b ∈ Cm , és így a-t és b-t a Cantor-halmaz is tartalmazza. Bizonyítás: Ez már az előállítási szabályból is következik. Legyen [a; b] ∈ Ck , akkor ez azt jelenti, hogy Ck+1 előállításánál (többek közt) ezt a szakaszt harmadoljuk: [a; a + 13 ], valamint [a + 23 , b] lép [a; b] szakasz helyére. Tehát [a; b] ∈ Ck ⇒ a; b ∈ Ck+1 . Ezt felhasználva Ck+1 -re, a; b ∈ Ck+2 . És így tovább, a; b ∈ C. 3.1.3. Állítás. Legyen x ∈ [0, 1]. Ekkor x pontosan akkor tartozik a hagyományos Cantor-halmazhoz, ha hármas számrendszerben felírt végtelen tizedestört alakja nem tartalmaz egyest. Bizonyítás: A hármas számrendszer onnan jött, hogy a meglévő szakaszokat mindig harmadoljuk, és így sokkal egyszerűbb az intervallum-határokat felírni. Nézzük először a C1 -hez tartozó számokat: C1 = [0, 31 ] ∪ [ 23 , 1]. Ugyanez hármas számrendszerben: C1 = [03 , 0.13 ]∪[0.23 , 13 ]. Tehát a tiltott számok 0.13 és 0.23 közt kell legyenek: ez csak úgy történhet, ha a „harmados pont” utáni első helyen 1 szerepel (kivéve 0.13 ). Egy tetszőleges x ∈ [0, 1] pont tehát akkor és csak akkor eleme C1 -nek, ha hármas számrendszerben felírt alakjában a pont utáni első helyen nem 1 áll. Mit lehet tenni a kivételt képező 0.13 -gyel? Írjuk fel végtelen alakba: 0.100000 . . .3 = 0.022222 . . .3 . Világos, hogy más tiltott számmal ezt nem játszhatjuk el, hiszen akárhogy leváltunk egy egyest ilyen módon kettesekre, egy másik egyes számjegy akkor is marad a felírásban. Menjünk tovább: C2 = [03 , 0.013 ] ∪ [0.023 , 0.13 ] ∪ [0.23 , 0.213 ] ∪ [0.223 , 13 ]. A harmadolás és a hármas számrendszer kapcsolata miatt, a tiltott számok, az előzőeken kívül most a 0.013 és 0.023 ; valamint 0.213 és 0.223 közti számok. Ezekről meg az mondható el, hogy a második pont utáni számjegy nem lehet 1; a kivétel most 0.013 és 0.213 , de ezek az előbbi módszerrel megint átírhatóak olyan végtelen alakba, hogy ne szerepeljen a számjegyei között 1. Más tiltott számmal ez megintcsak nem tehető meg. Ez az eljárás folytatódik, minden újabb Ck képzése során kitiltjuk egyik helyiértékről az egyest, és megmaradnak az előző tiltások is. A kivételek mindig olyan alakúak lesznek, hogy hármas számrendszerbeli felírásuk egy darab egyest tartalmaz, mely után csak nulla szerepel, és így mindig átírhatóak végtelen, csak 0-t és 2-t tartalmazó alakba.

A fraktál jellemzése 3.1.4. Állítás. A Cantor-halmaz önhasonló (a 2.2.3. definíció alapján).

3 KONKRÉT PÉLDÁK

31

Bizonyítás: Legyen H1 a C Cantor-halmaz 12 -től balra S eső részhalmaza, H2 pedig a jobbra eső részhalmaz. Ekkor nyilván C = H1 H2 . Ezen (egybevágó) halmazokról elmondható, hogy H1 = f1 (Cn ) és H2 = f2 (Cn ) diszjunkt halmazok, ahol f1 és f2Segy-egy λ = 31 arányú hasonlóság, különböző középpontokkal. Így C = f1 (H1 ) f2 (H2 ), teljesül a feltétel. 3.1.5. Állítás. A Cantor-halmaz hasonlósági dimenziója 0.6309. Bizonyítás: A hasonlósági dimenziónál levezetett képlet alapján (mivel a két képhalmaz diszjunkt): d=

lg 2 lg k = ≈ 0.6309. − lg λ − lg 31

Ez pont megfelel annak az eszmefuttatásnak, miszerint a Cantor-halmaz nem lehet nulla dimenziós, hiszen nem egy pont, de nem lehet egydimenziós sem, mert hossza nulla (3.1.1 állítás).

L-system és Logo kód L-systemes megadása nagyon egyszerű, hiszen itt nincs szög, nem kell fordulni, csupán az adott szakaszokat kell mindig lecserélni az előállítási szabálynak megfelelően. • Axióma: F • Szabály: F = F GF , G = GGG Ezzel a gondolatmenettel teljesen egybevág a Cantorhalmaz saját eljárása. eljárás Cantor :hossz :szint hakülönben :szint = 0 [előre :hossz] [ Cantor :hossz / 3 :szint - 1 tollatfel előre :hossz / 3 tollatle Cantor :hossz / 3 :szint - 1 ] vége

Meghívására példát láthatunk a 12. ábrán. Lehetőség van az általános L-systemet előállító eljárásokkal is kirajzolni: kezd -380 0 90 kirajzol előállít "F "FGF "GGG "X "Y 5 3 0 Az öt a legmagasabb szint, amit ebből a kétféle meghívásból a pixel-korlátok miatt ki lehet hozni.

3 KONKRÉT PÉLDÁK

3.2.

32

Sierpinski-háromszög

Definíció Vegyünk egy egyenlőoldalú háromszöget, mely tartalmazza a belsejét, oldalhossza legyen 1. Nevezzük el ezen kiinduló ábrát S0 -nak. Osszuk fel négy részre, az oldalfelező pontokat összekötő szakaszok felhasználásával. Az így kapott kisebb háromszögek oldalhossza 12 . Képezzük S0 -nak egy olyan részhalmazát, melyet a középső háromszög belsejének eltávolításávál nyerünk (tehát annak határvonala megmarad). Ez az S1 halmaz. Most a megmaradt három darab háromszöggel járunk el az előbbihez hasonló módon, felosztjuk őket négy-négy háromszögre az oldalfelező pontokat összekötő szakaszok mentén, majd a középső háromszögek belsejét szintén elhagyjuk. Az így keletkező halmaz S2 , az S1 részhalmaza. Folytatva az eljárást, megkapjuk Sn -t, az egymásból generált halmazok sorozatát. A halmazok megint csökkenőek: S0 ⊇ S1 ⊇ S2 . . . . A Sierpinski-háromszög ezen sorozat határértéke: \ S = lim Sn = Sk . n→∞

k∈N

Állítások 3.2.1. Állítás. Bármely Sm -hez tartozó háromszögek határvonala megmarad Sk -ban is, feltéve, hogy k ≥ m. Így S tartalmazza ezen határvonalakat. Bizonyítás: Mivel minden lépésben az előző halmaz háromszögeinek belső pontjainak egy részét távolítjuk csak el, az állítás triviális. 3.2.2. Állítás. A Sierpinski-háromszög területe nulla, míg „kerülete” végtelen18 . Bizonyítás: Az Sk halmaz 3k db, 2−k oldalhosszúságú háromszöget tartalmaz. A teljes területe így: q √ 3 1 · · 1 k 3 4 2k k −k 2 k 2 = 3 · (2 ) · . T (Sk ) = 3 · 2 4 18

Egy középiskolásnak azt, hogy nulla területet végtelen kerület határoljon, elég nehéz elképzelnie.

3 KONKRÉT PÉLDÁK

33

Ha k → ∞, ez az érték a nullába konvergál. Nézzük a „kerületet” a 3.2.1. állítás alapján: 3 K(Sk ) = 3k · 3 · 2−k = 3k+1 · 2−k = 3 · ( )k → +∞. 2 Ebből is látszik, hogy a területtel csak a kétdimenziós halmazok mértékét érdemes megadni, a Sierpinski-háromszög dimenziója tehát kevesebb kell legyen, mint kettő. Ugyanakkor a hossz sem egy jó mérőszáma, hiszen az végtelen, ami azt sugallja, hogy ez egy egynél nagyobb dimenziós alakzat. 3.2.3. Állítás. A Pascal-háromszög páratlan számait kiemelve, egy Sierpinskiháromszögre emlékeztető alakzatot kapunk (sőt, „végtelen nagy” Pascal-háromszögre mondhatjuk, hogy a Sierpinski-háromszög „végtelenített változata”).

13. ábra. A Pascal háromszög és a Sierpinski-háromszög kapcsolata Bizonyítás: Indukciót alkalmazunk. Először azt látjuk be, hogy az első 4 = 21+1 sor S1 -et adja. Ez nyilvánvaló, hisz ezekben a sorokban egyedül a 2 páros, pont középen (akár az ábra alapján is). A következő lépés, hogy belássuk: ha az első 2k+1 sor Sk -t adja, akkor az első 2k+2 sor Sk+1 -et. (Tehát Sk+1 úgy képződik, hogy az Sk -t alkotó első 2k+1 sort tovább folytatjuk, míg Sk+1 -et nem kapunk.) A sorok számával nincsen gond, Sk+1 kétszer annyi sorból áll, mint Sk , ami (mint S1 -nél) éppen 2k+1 ; hiszen Sk+1 a felső „háromszöget” tartalmazza alul kétszer is, egymás mellett, és mást nem. Az egyenlőoldalúság miatt nem nehéz észrevenni, hogy ahány sorból áll Sk , olyan széles (annyi számot tartalmaz) az utolsó, legalsó sora (tehát 2k+1 -et). Azt is könnyű látni, hogy mivel az Sk -hoz tartozó utolsó sor mind páratlan számból áll, ezért Sk+1 első újonnan kiírt sora (a 2k+1 + 1-edik), 2k+1 − 2 páros számot fog tartalmazni, egy-egy páratlan számmal körülvéve. Ez abból adódik, hogy két páratlan szám összege páros; a széleken pedig, a képzési szabálynak megfelelően, úgy jön ki a páratlan szám, hogy egyik oldalról az előző

3 KONKRÉT PÉLDÁK

34

sor páratlan számot tartalmaz, a másik oldal meg már a Pascal-háromszögön kívül esik, ahova képzeletben nullákat írhatunk. Az első új sorral tehát megvagyunk, ennek alapján nézzük, hogy lesz a középső rész lyukas. A második új sor felett 2k+1 − 2 darab páros szám állt, ezek alatt, mivel két páros szám összege páros, 2k+1 −3 db páros szám lesz, hogy ezeket mi veszi körül, az most nem fontos. Az eljárást folytathatjuk Sk+1 utolsó soráig, ahol már nulla darab páros szám áll. Az ok, amiért pont az utolsó sorra fogynak el a páros számok, az 2k+1 − (2k+2 − 2k+1 ) · 1 = 0 összefüggésből adódik. Tehát megvan a középső lyuk is. Már csak az kell, hogy a középső hiányzó rész két oldalán (a 2k+1 + 1, . . . , 2k+2 sorokban), miért Sk -val egybevágó alakzatok állnak. Az világos, hogy a Pascalháromszög szélén páratlan számok (egyesek) szerepelnek, így a két hiányzó rész egy-egy oldala adott. A másik oldalról viszont az előbb bizonyított páros számok határolják, melyet a paritás szempontjából nyugodtan tekinthetünk nulláknak. Mivel csak a két felette álló számtól függ a képzett szám paritása, ezért a két páros oldallal határolt háromszög teljesen független a többi elemtől, vagyis pont úgy viselkedik, mint az első 2k+1 sor, ami Sk -val volt ekvivalens. Ezzel beláttuk az összes sorra, hogy Sk+1 -gyel ekvivalens, amennyiben első 2k+1 sora Sk -val egyezett meg.

A fraktál jellemzése 3.2.4. Állítás. A Sierpinski-háromszög önhasonló. Bizonyítás: Legyenek f1 , f2 , f3 , λ = 21 arányú hasonlóságok. Ekkor Hi = fi (S) (1 = 1, 2, 3) az a három halmaz, ami az S1 -nél keletkezett három darab háromszögből lesz, a rekurzív lépéseket végtelenszer végrehajtva. Ekkor S = S 3 i=1 fi (S). 3.2.5. Állítás. A Sierpinski-háromszög hasonlósági dimenziója 1.585. Bizonyítás: Először azt kell belátni, hogy egyáltalán használható a hasonlósági dimenzió, hisz fi (S)-ek nem teljesen diszjunktak (egy-egy csúcsnál lévő határpontjuk közös). A 2.3.3.3. állítás alapján, kell keresnünk egy alkalmas V halmazt. Erre jó lesz S0 belső pontjaiból álló halmaz, így a levezetett képlet használható:

d=

lg k lg 3 = ≈ 1.585. − lg λ − lg 12

3 KONKRÉT PÉLDÁK

35

L-system és Logo kód A Sierpinski-háromszögnek több leírása is létezik L-systemben, ennek függvényében lekódolására is többféle lehetőség van, sőt Logo-ban szakaszok helyett háromszögeket is használhatunk. Ha úgy gondolkodunk, mint egy programozó, az a legegyszerűbb, ha azt mondjuk, hogy a nulladik lépésben egy háromszöget kell rajzolni, a további lépésekben pedig mindig a megfelelő pontokba ((0, 0); ( 12 , 0); ( 14 ; 12 )) egy-egy újabb, fele akkora háromszöget. Ennek Logo kódja egyszerű: eljárás háromszög :hossz ismétlés 3 [előre :hossz balra 120] ;színezéshez tollatfel balra 30 előre gyök 3 /4*:hossz tollatle töltőszín! 0 tölt tollatfel hátra gyök 3 /4*:hossz jobbra 30 vége eljárás Sierpinski :hossz :szint hakülönben :szint = 0 [háromszög :hossz] [ Sierpinski :hossz / 2 :szint - 1 tollatfel előre :hossz / 2 tollatle Sierpinski :hossz / 2 :szint - 1 tollatfel balra 120 előre :hossz / 2 jobbra 120 tollatle Sierpinski :hossz / 2 :szint - 1 tollatfel jobbra 120 előre :hossz / 2 balra 120 tollatle ] vége

Itt a tollatfel és tollatle parancsokra valójában nem lenne szükség, mert ha valaki ismeri az ábrát, tudja, hogy úgyis a háromszögek vonala mentén halad a teknős, így nem rajzol olyan vonalakat, ami elrontaná az ábrát. Ez alapján a Lindenmayer-kód el sem készíthető, mert be kéne vezetni hozzá egy új jelölést F helyett (ami a háromszöget rajzolja), és arra alkalmazni a rekurziót: így nem a szakaszt cserélgetnénk ki, hanem a háromszöget. • Axióma: H • Szög: 60◦ • Szabály: H = HGH + +G − −H − −G + +

3 KONKRÉT PÉLDÁK

36

Itt H tehát egy háromszöget kirajzoló jelölés lenne: H = +F −−F −−F −−+ (ráadásul annak is csak a körvonala, de ez végtelenbe tartás mellett nem számít, csak az egyes Sk -knál). Az előbbi leírással tehát az volt a gond, hogy erre a logikára alapozva nem írható le a szokványos szimbólumokkal. Ehelyett próbáljuk meg úgy felépíteni szakaszokból, hogy azokat az rekurzió során valami másra kicserélve eljussunk a kívánt alakzathoz. • Axióma: F − F − F − • Szög: 120◦ • Szabály: F = F − F − F − F F Ezzel megkapjuk a Sierpinski háromszöget a negyedik iterációig, de tükrözve a vízszintes tengelyre, és a legnagyobb baj, hogy a legbelső háromszögektől eltekintve a szakaszokon többször is átmegy a teknős, teljesen feleslegesen.

14. ábra. kirajzol előállít "|F-F-F-|"|F-F-F-FF|"G"X"Y 1 220 120 Hogy megoldjuk az előbbi problémát, ahelyett, hogy feleslegesen „megteszünk egy kört” -csak, hogy a megfelelő helyre jussunk- használhatunk vermet, és így nem kell újra átmenni a már kirajzolt szakaszokon: • Axióma: F − F − F − • Szög: 120◦ • Szabály: F = F [−F ]F Ez egy sokkal gazdaságosabb, és egyben egyszerűbb megadása a fraktálnak.

3 KONKRÉT PÉLDÁK

37

15. ábra. kirajzol előállít "|F-F-F-| "|F(-F)F| "G "X "Y 1 220 120 Módosulatok 3.2.1.

Sierpinski-szőnyeg

A háromszög előállításának elvét módosítva, szintén egy érdekes síkbeli fraktált kapunk, ha háromszög helyett az egységnégyzetből indulunk ki. Egy nagyon nem takarékos felírás19 : • Axióma: F − F − F − F − • Szög: 90◦ • Szabály: F = F [−F − F − F ]F [−F − F − F ]F [−F − F − F ]

16. ábra. Sierpinski_szőnyeg 500 4 Logo kódja megint nem az előbbi megadásra épül, hanem az egyszerűségre és átláthatóságra törekszik: 19

El lehet gondolkodni rajta, hogy mi a legoptimálisabb felírás.

3 KONKRÉT PÉLDÁK

38

eljárás négyzet :hossz ismétlés 4 [előre :hossz balra 90] ;színezéshez tollatfel balra 45 előre :hossz * gyök ( 2 ) / 2 töltőszín! 0 tölt hátra :hossz * gyök ( 2 ) / 2 jobbra 45 tollatle vége eljárás Sierpinski_szőnyeg :hossz :szint hakülönben :szint = 0 [négyzet :hossz] [ ismétlés 3 [Sierpinski_szőnyeg :hossz 3 :szint - 1 tollatfel előre :hossz tollatfel balra 180 előre :hossz jobbra 90 előre :hossz 3 jobbra 90 tollatle Sierpinski_szőnyeg :hossz 3 :szint - 1 tollatfel előre :hossz* 2 3 tollatle Sierpinski_szőnyeg :hossz 3 :szint - 1 tollatfel balra 180 előre :hossz * 2 3 jobbra 90 előre :hossz 3 jobbra 90 tollatle ismétlés 3 [Sierpinski_szőnyeg :hossz 3 :szint - 1 tollatfel előre :hossz tollatfel balra 180 előre :hossz balra 90 előre :hossz *2 3 balra 90 tollatle ] vége

3 tollatle]

3 tollatle]

3.2.1.1. Állítás. A Sierpinski-szőnyeg önhasonló, d ≈ 1.8928. Bizonyítás: Legyen H1 , . . . , H8 -k az a nyolc halmaz, melyek az SZ1 -et alkotó egybevágó négyzetlapokból lesznek az előállítás lépéseit végrehajtva. Ekkor f1 . . . f8 , λ = 13 arányú hasonlóságokra Hi = fi (SZ) (i = 1 . . . 8). Csakúgy, mint a háromszögnél, a szőnyeg esetén is elmondható, hogy minden SZi tartalmazza (legalább) a korábbi lépések során nyert határvonalakat, így SZ = S8 i=1 fi (SZ). A diszjunkció megint nem teljesül, a gond a határpontokkal van. A háromszöghöz hasonlóan, SZ0 belső pontjaira teljesül az OSC. d=

lg k lg 8 = ≈ 1.8928. − lg λ − lg 31

3 KONKRÉT PÉLDÁK 3.2.2.

39

Menger-szivacs

A Sierpinski-szőnyeg előállítása alapján, most egy egységkockából kell kiindulni. A kapott „téridom”, az előbbi leírással teljesen megegyező módon, 26 darab egybevágó halmazból áll, melyek az egész halmazhoz hasonlóak, szintén λ = 13 aránnyal. Az OSC teljesül az egységkocka belső pontjaira, így: d=

3.2.3.

lg 26 lg k = ≈ 2.9656. − lg λ − lg 31

Sierpinski-tetraéder

Érdekes lehet a Sierpinski-háromszög azon módosulata is, amikor háromszöglapok helyett szabályos tetraédereket használunk. Ekkor azonban módosul kicsit az eljárás: hisz a lépések során elhagyott pontok nem egy tetraédert alkotnak, mint az a négy-négy halmaz, ami megmarad [18]:

17. ábra. A Sierpinski-tetraéder az első lépés után A hasonlósági dimenzió használható a megszokott okok miatt, így: d=

lg 4 lg k = = 2. − lg λ − lg 12

Ez a fraktál egy jó ellenpélda arra a helytelen állításra, miszerint a fraktálok törtdimenziósak.

3 KONKRÉT PÉLDÁK

3.3.

40

Koch-görbe

Ez a fraktál Helge von Koch svéd matematikus nevéhez fűződik, aki először 1906-ban foglalkozott a görbe előállításával, mely hasonló a Cantor-poréhoz: itt is minden lépésben ki kell cserélni a szakaszokat valami másra.

18. ábra. Koch 700 1 és Koch 700 5

Definíció Legyen K0 egy egységnyi hosszú szakasz. Ebből K1 úgy nyerhető, hogy a szakasz középső harmadát egy töröttvonallal helyettesítjük, mintha annak két szakasza egy egyenlőoldalú háromszög egy-egy oldalát alkotná. K2 készítésénél a már meglévő szakaszok közepét helyettesítjük törtvonallal az előbb leírtakkal megegyezően, ezt a törtvonalat alkotó mindkét szakasz hossza 3−2 . A sorozat későbbi elemei a már leírt módszerrel nyerhetőek.

Állítások 3.3.1. Állítás. A Koch-görbe „alja” megegyezik a Cantor-halmazzal20 .

19. ábra. 3.3.1. Állítás Bizonyítás: Azt könnyű látni, hogy a Koch görbe alja biztosan tartalmazza a kérdéses pontokat. Azt kell tehát belátni, hogy más pontokat ezeken 20

A Koch görbe alján a határérték K0 -lal vett metszetét értjük.

3 KONKRÉT PÉLDÁK

41

kívül nem tartalmaz. Ehhez meg elég azt figyelni, hogy adott Ki esetén, a görbe „alján” keletkező kimetszéseket egy későbbi iteráció során keletkező szakaszok nem metszik-e. Módosítsuk az előállítási szabályt a következőképp: a kiindulási szakasz helyett vegyünk egy olyan H0 háromszöglapot, melynek alapja megegyezik K0 -lal, azon fekvő szögei pedig 30◦ -osak. A továbbiakban az ilyen háromszögeket cseréljük le rekurzióval négy-négy újabb háromszögre, oly módon, hogy Hi mindig Ki szakaszai fölé rajzolt háromszögek halmaza. Nyilvánvaló, hogy Ki ⊆ Hi az előállítás szabálya miatt, így a bizonyítást elég H-ra, a Hi halmazok határértékére kimondani.

20. ábra. A bizonyításhoz használt háromszöglapok K0 -ra és K1 -re teljesül az állítás, a háromszög(ek) K0 intervallummal vett metszete csak C0 illetve C1 pontjait tartalmazza. Tegyük fel, hogy egy Ki -re teljesül az állítás. Azt kell belátni, hogy ekkor Ki+1 re is teljesül. Ha Hi -re teljesül az állítás (Hi alja = Ci ), akkor ahhoz, hogy a következő lépés során keletkező szakaszok ezt ne rontsák el, elég az, hogy Hi+1 ⊆ Hi (ekkor tehát Hi+1 alja megegyezik Ci -vel). Ki+1 -ben ugyanis az új szakaszok nem metszik az újonnan és eggyel korábban eltávolított szakaszok helyét, így ezekkel nincs gond. Annak feltétele, hogy a korábban eltávolított szakaszok helyét se messék az új szakaszok, elég az, hogy Hi+1 maradjon Hi -ben, hiszen mivel az eltávolított szakaszok helyével diszjunkt volt Hi , így biztosan diszjunkt marad azzal Hi bármely részhalmaza is. A tartalmazást nem nehéz látni: a rekurzió során, a háromszöget mindig négy hasonló (harmadakkora) háromszöggel helyettesítettük. Ezek közül két hasonlóságnak a középpontja a korábbi háromszög alapjain fekvő két csúcs, ezzel tehát nincs gond, kettőn pedig eltolást, és egy-egy −60◦ -os illetve +60◦ -os for◦ ◦ gatást is elvégeztünk, de mivel 120 2−60 = 30◦ , a kis háromszögek elférnek a nagyobban. Ezzel bizonyítottuk, hogy a tartalmazás örökíti a Koch-görbe aljáról kimondott tételt, és mivel Hi ⊇ Hi+1 ⊇ . . . , ezért a határértékre is teljesül az állítás.

A fraktál jellemzése 3.3.2. Állítás. A Koch-görbe önhasonló.

3 KONKRÉT PÉLDÁK

42

Bizonyítás: Legyen H1 , . . . , H4 az a négy halmaz, melyek a K1 -et alkotó négy szakaszból lesznek. Ezek összesen három közös ponttól eltekintve diszjunktak, és előállnak K-n végrehajtott, λ = 13 arányú hasonlóságok képeként. Ekkor S K = 4i=1 fi (Hi ), teljesül a feltétel. 3.3.3. Állítás. A Koch-görbe hasonlósági dimenziója 1.2619. Bizonyítás: Mivel nem áll fenn a diszjunkció, kell keresni egy alkalmas V halmazt. Most már nincs olyan könnyű dolgunk, mint a Sierpinski változatainál, néhány próbálkozás után viszont megtalálható az a nyílt háromszöglap, melyet √ 3 1 a kiinduló szakasz fölé rajzolhatunk, 3 · 2 magassággal. A már ismert képlet alapján: lg k lg 4 d= = ≈ 1.2619 − lg λ − lg 31 Tehát a Koch-görbe „egy kicsit több”, mint egy egyenes.

L-system és Logo kód A görbe leírása Lindenmayer-rendszerben: • Axióma: F • Szög: 60◦ • Szabály: F = F + F − −F + F A Logo kód is erre építkezik: eljárás Koch :hossz :szint hakülönben :szint = 0 [előre :hossz] [ Koch :hossz / 3 :szint balra 60 Koch :hossz / 3 :szint jobbra 120 Koch :hossz / 3 :szint balra 60 Koch :hossz / 3 :szint ] vége

1 1 1 1

Kirajzolás az általános L-systemes eljárásokkal: kezd -380 0 90 kirajzol előállít "F "|F+F−−F+F| "G "X "Y 5 3 60

3 KONKRÉT PÉLDÁK

43

A hatodik szintnél a teknős már elakad, útközben elfelejti, merre is kellene tovább mennie :-). Az előbbi saját eljárás jobban bírja, csak a pixelek okozhatnak problémát (pl. egy helyben forgolódik a teknős, mert annyiszor osztotta :hossz -t, hogy nullát kapott eredményül).

Módosulatok Érdemes a sikeres kódolás után kísérletezgetni az előállítással. Apró módosítások is érdekes ábrákhoz vezethetnek.

3.3.1.

Cesaro

Nevezetes módosulata a Koch-görbének a Cesaro görbe, melynek generálása teljesen megegyezik az előzőével, de 60◦ helyett (általában) 85◦ -ot használunk. Persze meg lehet adni bármely más szöget is, de, hogy ne veszítsük el a jellegzetes struktúrát, ajánlott a (0; 90] intervallumban maradni. Bármely ilyen szögről elmondható ugyanis, hogy 180◦ − 2 · α = β, ahol β az egyenlő szárú háromszög szárak által bezárt szöge. Ez azt jelenti, hogy az egyik szár megrajzolása után 2 · α-t kell visszafordulni. Emiatt a fraktál továbbra is felírható Lindenmayer-rendszerben (hiszen egy szöget elég megadnunk), sőt, ez a felírás megegyezik a Koch-görbéjével, csupán a megadott szög változik (így aztán ugyanazon jellemzők mondhatóak el róla, mint előbb a Koch-ról).

21. ábra. α = 85◦ esetén a szögek alakulása Logoban való leprogramozásánál már egy kis trigonometriára van szükség, hogy kiszámoljuk a megfelelő oldalhosszúságot. Rekurzió során hívhatnánk egyszerűen a megadott :hossz parméterrel is a függvényt, de mi most, eltérve a Lindenmayer-rendszerben leírt rekurziótól, módosítjuk ezt a paramétert, mert

3 KONKRÉT PÉLDÁK

44

szeretnénk, hogy a fraktál mélységétől függetlenül, „teljes hossza” mindig a :hossz -ban megadott érték legyen, hogy ne kelljen számolgatnunk ahhoz, hogy az ábra biztosan kiférjen a rajzlapra.

22. ábra. :hossz és x viszonya Itt most általános esetben számolunk, hogy a függvényt meg lehessen hívni bármekkora :szög-gel. A kérdés tehát, hogy mekkora :hossz paraméterrel kell meghívnunk a rekurzió eljárását, az aktuális :hossz paraméterhez viszonyítva:

cos α =

:hossz − 2x :hossz :x= −1 2 2x :hossz x= . 2 cos α + 2

Ez alapján a Logo kód: eljárás Cesaro :hossz :szint hakülönben :szint = 0 [előre :hossz] [ Cesaro :hossz / ( 2 + 2 * balra :szög Cesaro :hossz / ( 2 + 2 * jobbra :szög * 2 Cesaro :hossz / ( 2 + 2 * balra :szög Cesaro :hossz / ( 2 + 2 * ] vége

3.3.2.

:szög

cos :szög ) :szint - 1 :szög cos :szög ) :szint - 1 :szög cos :szög ) :szint - 1 :szög cos :szög ) :szint - 1 :szög]

„Kochpihe”

Ha az előbbi görbét egy egyenlő oldalú „sokszög” oldalaiként használjuk, szép, hópihére hasonlító alakzatokat kapunk.

3 KONKRÉT PÉLDÁK

45

Az előállítás leírása függ attól, hogy hányoldalú sokszögből szeretnénk a pihét, sőt lehetséges, hogy Lindenmayer-rendszerben le sem lehet írni, mert α rögzített szöggel nem lehet teljesíteni a megfelelő forgásokat. Nekünk ugyanis az kell, hogy egy oldal kirajzolása után (ekkor a teknős 180◦ -os irányban áll) a teknőst a megfelelő α szögbe tudjuk forgatni, a forgás mértékét α skalárszorosával (λ ∈ Z) kifejezve. Ehhez α-nak a következőt kell teljesítenie: 180 + λ · α ≡ α

(mod 360)

.

23. ábra. A teknős iránya 180◦ az első oldal kirajzolása után, innen kellene α irányba fordulni

Háromszög esetén a λ = −2 jó megoldás, tehát az oldal kirajzolása után kétszer balra kell fordulni, 60◦ -kal: • Axióma: F − −F − −F − − • Szög: 60◦ • Szabály21 : F = F + F − −F + F Négyszög esetén λ = −1 elég (bár ez nem éppen hópihe-alakú): • Axióma: F − F − F − F − • Szög22 : 90◦ • Szabály: F = F + F − −F + F 21 22

Vajon mi történik, ha felcseréljük a + és − jeleket? Vigyázat, itt 90◦ áll, tehát a Cesaro-görbét is ezzel a szöggel rajzolja ki!

3 KONKRÉT PÉLDÁK

46

Meglepő módon az ötszöggel sincs gond, α = 180 − 360 = 108◦ , λ = 6 jó 5 ◦ megoldást ad. Persze a Cesaro-görbének nem szokás 90 -nál nagyobb szöget megadni, de azért itt érdemes kipróbálni az eredményt. • Axióma: F ++++++F ++++++F ++++++F ++++++F ++++++ • Szög: 108◦ • Szabály: F = F + F − −F + F A szabályos hatszög a fenti kongruencia alapján nem rajzolható ki, α = 120◦ miatt, de 120◦ helyett nyugodtan használhatunk 60◦ -ot is: • Axióma: F − F − F − F − F − F − • Szög: 60◦ • Szabály: F = F + F − −F + F További szabályos sokszögek kirajzolásának végiggondolását az olvasóra bízom. A Logo kóddal sokkal egyszerűbb lehet a dolgunk, ha kis cselhez folyamodunk. Meg lehetne ugyan írni az eljárást az egyes sokszögekre külön-külön, a Lindenmayer-rendszernek megfelelően, de könnyebb a dolgunk, ha egyszerűen csak kicserélgetjük a sokszög oldalait a Koch-görbékre. Így nemcsak egy eljárásban elintéztük az összeset, de kirajzolhatunk olyan variációkat is, amiket az előbb nem tudtunk. Ezenkívül szabad kezet kaptunk a szögeket illetően, a Koch-görbe szöge független a sokszög belső szögétől.

24. ábra. 3 és 5 ágú Kochpihe eljárás Kochpihe :hossz :szint :ág ismétlés :ág [Koch :hossz :szint jobbra egészhányados 360 :ág] vége

3 KONKRÉT PÉLDÁK 3.3.3.

47

Derékszögű Koch

Ismert módosítása a görbének az is, amikor kettő helyett három szakaszt rajzolunk a középső harmad helye fölé, melyek 90◦ -ot zárnak be egymással.

25. ábra. Koch_derékszöggel 700 1 és Koch_derékszöggel 700 5

Lindenmayer-rendszerben: • Axióma: F • Szög23 : 90◦ • Szabály: F = F + F − F − F + F Itt a kirajzol eljárás meghívásakor, már ötös mélység esetén is elveszik a teknős, a saját eljárás megint csak jobb, kódja teljesen az előbbi leíráson alapszik: eljárás Koch_derékszöggel :hossz :szint hakülönben :szint = 0 [előre :hossz] [ Koch_derékszöggel :hossz / 3 :szint - 1 balra 90 Koch_derékszöggel :hossz / 3 :szint - 1 jobbra 90 Koch_derékszöggel :hossz / 3 :szint - 1 jobbra 90 Koch_derékszöggel :hossz / 3 :szint - 1 balra 90 Koch_derékszöggel :hossz / 3 :szint - 1 ] vége

Mivel itt már nem négy, hanem öt részből áll a fraktál (hiszen megint önhasonló!), ennek megfelelően változik hasonlósági dimenziója is: egy kicsit közelebb került a két dimenzióhoz. 3.3.4. Állítás. A derékszögű Koch-görbe hasonlósági dimenziója 1.465. 23

Vajon mit kapunk 120◦ -nál?

3 KONKRÉT PÉLDÁK

48

Bizonyítás: Most is a kezdő szakasz fölé kell háromszöget állítani, a magasság 1 most 3·√ . 2 lg 5 lg k = d= ≈ 1.465. − lg λ − lg 13 3.3.4.

Koch-sziget

Szintén ismert módosulat az úgynevezett Koch-sziget, mely valójában négy módosított Koch-görbéből áll, hasonló módon, mint a Koch-pihénél. Nézzük előbb csak az alap görbét, mely segítségével keletkezik majd a sziget is. Az előállítási szabály leolvasható az alábbi ábráról is, így nem nehéz megadni L-rendszerben, és lekódolni Logoban.

26. ábra. Koch_dupladsz 700 1 és Koch_dupladsz 700 4

• Axióma: F • Szög: 90◦ • Szabály: F = F − F + F + F F − F − F + F eljárás Koch_dupladsz :hossz :szint hakülönben :szint = 0 [előre :hossz] [ Koch_dupladsz :hossz / 4 :szint - 1 jobbra 90 Koch_dupladsz :hossz / 4 :szint - 1 balra 90 Koch_dupladsz :hossz / 4 :szint - 1 balra 90 Koch_dupladsz :hossz / 4 :szint - 1 Koch_dupladsz :hossz / 4 :szint - 1 jobbra 90 Koch_dupladsz :hossz / 4 :szint - 1 jobbra 90 Koch_dupladsz :hossz / 4 :szint - 1 balra 90 Koch_dupladsz :hossz / 4 :szint - 1 ] vége

Ha nem a saját eljárást használjuk, hanem kirajzol t, akkor csak hármas mélységig bírja a rekurzió a paraméter-átadást. 3.3.5. Állítás. A Koch-sziget egy oldalának hasonlósági dimenziója 1.5.

3 KONKRÉT PÉLDÁK

49

Bizonyítás: V -nek megfelel egy olyan négyzet, melynek átlója a kiindulási szakasz. lg k lg 8 d= = = 1.5. − lg λ − lg 14 Mondhatni fél úton járunk az egy és a két dimenzió között. . . Ez után nincs más feladat, mint (akárcsak a pihe készítésénél), egy négyzet mentén elhelyezni négy ilyet, mint oldalakat. Logoban megintcsak érdemesebb az egyszerűbb megoldást választani, de az L-systemes leírással sem lenne nehéz leprogramozni: • Axióma: F + F + F + F • Szög: 90◦ • Szabály: F = F − F + F + F F − F − F + F Meghívása megint csak hármas szintig működik így, a túl hosszú, paraméterként átadott szavak miatt: kirajzol előállít "|F+F+F+F| "|F-F+F+FF-F-F+F| "G "X "Y 3 5 90

3 KONKRÉT PÉLDÁK

3.4.

50

Lévy fraktál

Definíció Az eljárás nagyon egyszerű: minden egyes lépésben, a szakaszok fölé és azok helyett egy derékszögű, egyenlőszárú háromszög két oldalát rajzoljuk.

27. ábra. Lévy 300 1 és Lévy 300 12

L-system és Logo kód L-rendszerben leírása: • Axióma: F • Szög: 45◦ • Szabály: F = +F − −F + Ez alapján meghívása: kirajzol előállít "|F| "|+F−−F+| "G "X "Y 9 15 45 Mint eddig is, közvetlenül erre építettem a Logo kódot: eljárás Lévy :hossz :szint hakülönben :szint = 0 [előre :hossz] [ balra 45 Lévy :hossz / gyök ( 2 ) :szint - 1 jobbra 90 Lévy :hossz / gyök ( 2 ) :szint - 1 balra 45 ] vége

3 KONKRÉT PÉLDÁK

51

A fraktál jellemzése Eddig olyan fraktálokkal foglalkoztunk, amikről ránézésre meg lehetett mondani, hogy önhasonlóak-e. Innentől kezdve olyan példákat fogok mutatni, melyekről nehéz megmutatni ezt a tulajdonságot, bizonyítás helyett inkább egy szemléletes ábrát mutatok csak az olvasónak. Amiért mégis sejthető, hogy ezen fraktálok is önhasonlóak, az az L-rendszeres felírásuk. Ami megnehezíti a dolgunkat, az a diszjunkció teljes megszűnése, a képhalmazok itt nehezen kivehetőek és szétválaszthatóak. Segítségképp írtam egy másik eljárást is erre a fraktálra, mely a két halmazt különbözőre színezi24 .

28. ábra. A Lévy-féle C görbe önhasonlósága Ehhez szükség van egy új paraméterre (:ksz ), mely a :szint kezdő értékét jegyzi meg, és két új globális változóra, egyikben az adott :szint-hez tartozó élszámot tárolom (s), a másikban pedig azt, hogy épp melyik élnél tartok (esz ). eljárás Lévy_öh :hossz :ksz :szint ; :ksz és :szint legyen ugyan az! ha :ksz = :szint [ állít! "s 1 állít! "esz 0 ismétlés :ksz-1 [állít! "s s*2] ] hakülönben :szint = 0 [ állít! "esz esz+1 hakülönben (esz <= s) [tollszín! "bíbor] [tollszín! "sötétkék] előre :hossz ] [ balra 45 Lévy_öh :hossz / gyök ( 2 ) :ksz :szint - 1 jobbra 90 Lévy_öh :hossz / gyök ( 2 ) :ksz :szint - 1 balra 45 ] tollszín! 0 vége

24

Azért két képhalmazból áll, mert a szakaszokat itt mindig két másik szakaszra cseréljük.

3 KONKRÉT PÉLDÁK

52

3.4.1. Állítás. A Lévy-féle C görbe hasonlósági dimenziója pontosan 2. Bizonyítás: Ahhoz, hogy kiszámítsuk a hasonlósági dimenziót, megint csak √ kell keresni egy alkalmas V halmazt, melyről elmondható, hogy a két λ = 22 arányú hasonlósággal (egy-egy alkalmas középponttal) előállított képhalmazának unióját tartalmazza V . Pár próbálkozás után alkalmasnak tűnik pl. egy három egység átmérőjű nyílt körlap. d=

lg 2 lg k = = 2. − lg λ − lg √12

Ez egy jó példa arra, hogy nem feltétlenül igaz, hogy egy fraktál mindig törtdimenziós.

3 KONKRÉT PÉLDÁK

3.5.

53

Terdragon

Ezzel a fraktállal akkor találkoztam először, amikor próbálgattam az általános L-system kirajzoló eljárást; a Lévy-féle görbéhez hasonló előállítási szabállyal saját fraktált szerettem volna kitalálni. Amikor elkészült, mindjárt nagyon meg is tetszett, és csak napok múltán, amikor a Sárkány-görbéről olvastam az interneten, jöttem rá, hogy ez már egy létező, sőt közismert fraktál.

29. ábra. Terdragon 600 1 30 és Terdragon 600 8 30

L-system és Logo kód Nézzük definíció helyett rögtön az L-rendszeres leírását: • Axióma: F • Szög: 30◦ • Szabály: F = +F − − − −F + + + +F − Meghívása hatos szintig működik. kirajzol előállít "|F| "|+F− − −−F+ + ++F−| "G "X "Y 6 15 30 A Logo kód is erre épül. Mivel működésének lényege kiolvasható az önhasonlóságot megmutató eljárásból, itt külön nem közlöm a kódot.

A fraktál jellemzése Önhasonlóság bizonyítása szintés külön eljárással: eljárás Terdragon_öh :hossz :ksz :szint :szög ; 30 fokkal kell meghívni ; :ksz és :szint legyen ugyan az! ha :ksz = :szint [

3 KONKRÉT PÉLDÁK állít! "s 1 állít! "esz 0 ismétlés :ksz-1 [állít!

"s ] hakülönben :szint = 0 [ állít! "esz esz+1 ha (esz <= s*3) [tollszín! "sötétkék] ha (esz <= s*2) [tollszín! "bíbor] ha (esz <= s) [tollszín! "zöld5] előre :hossz ] [ jobbra :szög terdragon_öh :hossz/gyök(3) balra 4*:szög terdragon_öh :hossz/gyök(3) jobbra 4*:szög terdragon_öh :hossz/gyök(3) balra :szög ] tollszín! 0 vége

54

s*3]

:ksz :szint - 1 :szög :ksz :szint - 1 :szög :ksz :szint - 1 :szög

30. ábra. A Terdragon önhasonlósága

3.5.1. Állítás. A Terdragon hasonlósági dimenziója pontosan 2. √

Bizonyítás: A három függvényünk most λ = 33 arányú hasonlóságok, V -nek most is alkalmas egy nyílt körlap, mondjuk három egység átmérővel. d=

lg k lg 3 = = 2. − lg λ − lg √13

3 KONKRÉT PÉLDÁK

3.6.

55

Cikk-cakk

Ez már azt hiszem, tényleg egy saját fraktál, C1 alakja miatt Cikk-cakknak neveztem el.

31. ábra. cikkcakk 400 1 60 és cikkcakk 400 6 60

L-system és Logo kód Előállítása hasonló, mint a Terdragoné, mégis, meglepően eltérő alakú halmazt kapunk. • Axióma: F • Szög: 60◦ • Szabály: F = +F − −F F + +F − Meghívása: kirajzol előállít "|F| "|+F−−FF++F−| "G "X "Y 5 15 60

A fraktál jellemzése A fraktálunk most négy, λ = tatja a következő eljárás:

1 2

arányú hasonló halmazból áll. Ezt megmu-

eljárás Cikkcakk_öh :hossz :ksz :szint :szög ; 60 fokkal kell meghívni ; :ksz és :szint legyen ugyan az! ha :ksz = :szint [ állít! "s 1 állít! "esz 0 ismétlés :ksz-1 [állít! "s s*4] ] hakülönben :szint = 0 [

3 KONKRÉT PÉLDÁK

56

állít! "esz esz+1 ha (esz <= s*4) [tollszín! "narancs] ha (esz <= s*3) [tollszín! "sötétkék] ha (esz <= s*2) [tollszín! "bíbor] ha (esz <= s) [tollszín! "zöld5] előre :hossz ] [ balra :szög Cikkcakk_öh :hossz/2 jobbra 2*:szög Cikkcakk_öh :hossz/2 Cikkcakk_öh :hossz/2 balra 2*:szög Cikkcakk_öh :hossz/2 jobbra :szög ] tollszín! vége

:ksz :szint - 1 :szög :ksz :szint - 1 :szög :ksz :szint - 1 :szög :ksz :szint - 1 :szög

0

32. ábra. A Cikk-cakk fraktál önhasonlósága

3.6.1. Állítás. A Cikk-cakk fraktál hasonlósági dimenziója pontosan 2. Bizonyítás: Mivel létezik a követelményeknek eleget tevő nyílt halmaz, d=

lg k lg 4 = = 2. − lg λ − lg 12

3 KONKRÉT PÉLDÁK

3.7.

57

Sárkány görbe

A Sárkány görbével először a NASA fizikusai foglalkoztak, John Heighway, Bruce Banks és William Harter. Az angol szakirodalomban gyakran emlegetik, mint ’Harter-Heighway dragon’, vagy egyszerűen csak ’Heighway dragon’. A köztudatban népszerűségre 1990-ben tett szert, az akkor megjelenő Michael Crichton regény, a Jurassic Park ugyanis megemlíti ezt a fraktált, sokan hívják emiatt ’Jurassic Park dragonnak’ is.

Definíció D0 az egységnyi hosszú szakasz. D1 az eredeti szakasz fölé, mint átfogóra emelt egyenlőszárú, derékszögű háromszög két befogója, elhagyjuk tehát az erdeti szakaszt - az átfogót. D2 készítésénél a már meglévő szakaszokat helyettesítjük a befogópárokkal, az előbb leírtakkal megegyezően. Ez azonban több lehetőséget is maga után von, hiszen a meglévő szakasz helyettesítése a törtvonallal kétféleképp, két irányból is történhet. A Heighway dragon annak a Dn sorozatnak a határértéke, ahol ez a helyettesítés ugyanazon mélységben egyszer egyik, egyszer pedig másik oldalról történik.

33. ábra. Heighway 400 1 1, Heighway 400 2 1 és Heighway 400 12 1

L-system és Logo kód Ennél a fraktálnál már nincs olyan egyszerű dolgunk, hiszen egyszer jobbra, egyszer pedig balra kell rajzolni a két szárat. Ehhez be kell vezetnünk az X és Y változókat, ezek fogják leírni ezt a két esetet, így ezeket felváltva kell használnunk. • Axióma: F X • Szög: 45◦ • Szabály: F = ”; X = +F X − −F Y +; Y = −F X + +F Y −

3 KONKRÉT PÉLDÁK

58

Ez alapján meghívása: kirajzol előállít "|FX| " "G "|+FX−−FY+| "|−FX++FY−| 9 15 45 A Logo-ban az X és Y változók helyett adunk az eljárásnak egy plusz paramétert, melyet a rekurzió során fog mindig mínusz egyszeresére változtatni. eljárás Heighway :hossz :szint :pari ; meghíváskor :pari 1 kell legyen! (-1-gyel elforgatott) hakülönben :szint = 0 [előre :hossz] [ balra :pari * 45 Heighway :hossz / gyök(2) :szint-1 1 jobbra :pari * 90 Heighway :hossz / gyök(2) :szint-1 (-1) balra :pari * 45 ] vége

A fraktál jellemzése Önhasonlóságát belátni ennek a fraktálnak sem egyszerű, hogy megmutassam, itt is egy külön eljárást írtam, melyben különböző színűre színezem az egyes halmazokat.

34. ábra. A Heighway-sárkány önhasonlósága

eljárás Heighway_öh :hossz :ksz :szint :pari ; meghíváskor :pari 1 kell legyen! (-1-gyel elforgatott) ; :ksz és :szint legyen ugyan az! ha :ksz = :szint [ állít! "s 1 állít! "esz 0 ismétlés :ksz-1 [állít! "s s*2] ] hakülönben :szint = 0 [ állít! "esz esz+1 hakülönben (esz <= s) [tollszín! "bíbor] [tollszín! "sötétkék]

3 KONKRÉT PÉLDÁK

59

előre :hossz ] [ balra :pari * 45 Heighway_öh :hossz / gyök(2) :ksz :szint-1 1 jobbra :pari * 90 Heighway_öh :hossz / gyök(2) :ksz :szint-1 (-1) balra :pari * 45 ] tollszín! vége

0

Talán nem meglepő, hogy az önhasonlóságról és a dimenzióról ugyanaz mondható el, mint a Lévy fraktálnál. Előállításuk teljesen ekvivalens, leszámítva a szakaszok irányát. Hasonlósági dimenziója tehát ennek a fraktálnak is 2.

Módosulatok 3.7.1.

Sierpinski dragon

Sierpinski háromszögére emlékeztető alakzatot kapunk, ha egy kisebb módosítást végzünk az előállítás szabályain. • Axióma: F X • Szög: 60◦ • Szabály: F =00

25

; X = +F Y − F X − F Y +; Y = −F X + F Y + F X−

Ennek írtam egy saját eljárást is, mert az előállít eljárás csak hatos mélységig bírja a rekurziót.

35. ábra. Heighway sárkányból Sierpinski dragon Ki lehetne számolni, hogy a hasonlósági dimenzió 1.585, de ez abból is adódik, hogy a görbe a Sierpinski-háromszöghöz konvergál.

25

A ” üressztringet jelöl, vagyis F helyére nem kerül semmi.

4 MELLÉKLETEK

4. 4.1.

60

Mellékletek Összefoglaló táblázat a dimenziókról

Fraktál

Hasonlósági dimenzió

Cantor-halmaz

lg 2 = 0.6309 lg 3

Koch-görbe

lg 4 = 1.2619 lg 3

Cesaro

lg 4 = 1.2619 lg 3

Derékszögű Koch

lg 5 = 1.465 lg 3

Koch-sziget egy oldala

lg 8 = 1.5 lg 4

Sierpinski-háromszög

lg 3 = 1.585 lg 2

Sierpinski-dragon

lg 3 = 1.585 lg 2

Sierpinski-szőnyeg

lg 8 = 1.8928 lg 3

Lévy

lg 2 √ =2 lg 2

Terdragon

lg 3 √ =2 lg 3

Cikk-cakk

lg 4 =2 lg 2

Heighway sárkánya

lg 2 √ =2 lg 2

Sierpinski-tetraéder

lg 4 =2 lg 2

Menger-szivacs

lg 26 = 2.9656 lg 3

4 MELLÉKLETEK

4.2.

61

A CD tartalma

• imaginelogo.zip Az Imagine Logo telepítőfájla, a [14] honlapról tölthető le. Feltelepítése ajánlott, az alábbi projekt ugyanis csak így futtatható. • Molnar_Katalin_L-rendszerek.IMP A foglalkozásokon elkészítendő Imagine Logo projekt, az elkészült eljárások kódja megtekinthető, meghívásukat gombok segítik, a paraméterek változtathatóak. • Molnar_Katalin_L-rendszerek.exe Az előbbi projektnek az Imagine Logo telepítését nem igénylő konverziója, nincs lehetőség a kódok megtekintésére, csak néhány eljárás hívható meg, fix paraméterekkel. • chaospro32.exe Fraktálok rajzolására alkalmas ingyenes szoftver, a [19] honlapról letölthető már ennél újabb változata is. A File/Fractal/LSystem menüponttal válthatunk át a Lindenmayer-rendszerekre, ezek előállítási szabályán a Windows/Formula Editor LSystem menüponton keresztül változtathatunk. • imlab.exe Képanalizáló program, a box-dimenzió kiszámolásához lehet segítség, meg lehet számolni vele a kép fekete színű pixeleit. Szabadon letölthető a [20] honlapról. • Molnar_Katalin_L-rendszerek.pdf A szakdolgozat szövege .pdf formátumban.

5 KONKLÚZIÓ

5.

62

Konklúzió

Rengeteg kihívást jelentett számomra ez a szakdolgozat, mégis élveztem elkészítését. Korábban sem LATEX-et, sem Imagine Logo-t nem használtam, így először ezekkel kellett megismerkednem. Az anyaggyűjtés sem volt egyszerű, az Elméleti bevezetésben szereplő matematikai hátteret nem volt könnyű összeszedni és eleinte nehézséget okozott az is, hogy felismerjem az interneten talált helytelen leírások hibáit, valamint, hogy egy rendszert alkossak a több helyről származó információkból. Próbáltam a fontos fogalmakat egymásra építve bemutatni, példákon keresztül, és könnyen érthetően. A megfelelő elméleti háttérrel már nem volt olyan nehéz kiigazodnom az egyes fraktálokon és megmutatnom tulajdonságaikat, definíciójukból pedig izgalmas volt kitalálni Logo és L-system kódjukat. Bár az egyes fraktálokat bemutató leírások elég népszerűek, remélem írásom nem lett sablonos, és sikerült egy egyedi szemszögből bemutatnom ezt a témakört: színesítve az egészet az informatikai háttérrel, valamint a Lindenmayer-rendszer és a kód közti párhuzam bemutatásával. Ami a szakdolgozatomban szerepel, az csak egy sűrített töredéke annak, amikről írhattam volna még ezen cím alatt. Ez alapján viszont már sokkal könnyebb továbbhaladni, akár ha újabb fraktáloknak az itt szereplő módszerekkel való jellemzéséről van szó, akár ha az elméleti háttér mélyítéséről. Ezúton szeretném megragadni az alkalmat arra is, hogy megköszönjem témavezetőmnek, Buczolich Zoltánnak, hogy mindig segítőkész és lelkiismeretes volt, és hasznos tanácsokkal látott el.

HIVATKOZÁSOK

63

Hivatkozások [1] Gerald A. Edgar: Measure, Topology, and Fractal Geometry [2] Bucholich Zoltán: Dinamikus rendszerek és fraktálok [3] Tilki Csaba: Fraktál alapú képtömörítés: Káosz és fraktálok programozói szemmel (Szakdolgozat, 2007) http://ganymedes.lib.unideb.hu:8080/dea/bitstream/2437/2385/1/ diplomamunka.pdf [4] Darida Sándor: Koch-görbéhez hasonló fraktálok vizsgálata (Szakdolgozat, 2009) http://www.cs.elte.hu/blobs/diplomamunkak/bsc_matelem/2010/ darida_sandor.pdf [5] Elek István: Porozitás, permeabilitás, fraktálgeometria http://lazarus.elte.hu/ elek/fooldal/cikkek/porperfrac.pdf [6] A Wikipédia számos szószedete: http://en.wikipedia.org/wiki/Main_Page [7] http://en.wikipedia.org/wiki/List_of_fractals_by_Hausdorff_dimension [8] http://math.rice.edu/ lanius/fractals/self.html [9] http://ecademy.agnesscott.edu/ lriddle/ifs/heighway/heighway.htm [10] http://local.wasp.uwa.edu.au/ pbourke/fractals/fracdim/ [11] http://classes.yale.edu/fractals/Software/boxdim.html [12] Szlávi Péter: Verem típuskonstrukció http://people.inf.elte.hu/szlavi/ [13] http://logo.sulinet.hu [14] http://imagine.elte.hu/ [15] http://www.sulinet.hu/tart/ncikk/Sed/0/32940/index.html [16] http://prog.berzsenyi.hu:8080/prog/View/logo/rekgorb [17] http://teamlabor.inf.elte.hu/logosecsetvonasok/lecke7.html [18] http://www.3d-meier.de/tut10/Seite20.html [19] http://www.chaospro.de/ [20] http://imlab.sourceforge.net/

Lindenmayer-rendszerek a középiskolában

Recommend Documents