Sistem Distribuit Pentru Dispozitive Android

SISTEM DISTRIBUIT PENTRU DISPOZITIVE ANDROID

*utilizat pentru generarea și studiul fractalilor*

"Clouds are not spheres, mountains are not cones, coastlines are not circles, and bark is not smooth, nor does lightning travel in a straight line."

Benoît Mandelbrot

Cuprins

Introducere

Proiectul prezentat în această lucrare are ca scop principal generarea și studiul fractalilor pe dispozitive Android asistate de servere folosite la procesare.

"Sistem Distribuit pentru Dispozitive Android utilizat pentru generarea și studiul fractalilor" este alcătuit din două părți: o aplicație Android care permite studiul fractalilor prin alegerea acestora, generarea lor și modificarea diverselor opțiuni și un program server scris în limbajul de programare C care rulează pe calculatoare ce utilizează sistemul de operare Linux.

Aplicația Android este folosită pentru generarea fractalilor în sistem Lindenmayer, fractali care pot conține șiruri de milioane de caractere.

Fractalii sunt forme geometrice complexe descrise prin formule simple. Termenul de "fractal" a fost inventat acum aproximativ 40 de ani, tot atunci apărând și geometria fractală. Folosind fractali, putem genera forme foarte asemănătoare cu cele din natură, de la structuri arborescente bidimensionale simple până la întregi peisaje tridimensionale.

Structurile fractale sunt generate de regulă pornind de la definiția lor de bază, care este iterată pentru a obține complexitatea dorită. Axioma (regula care descrie fractalul) este generația zero a acestuia, iar de fiecare dată când aceasta este iterată se obține o nouă generație. Fiecare generație devine mai complexă decât cea anterioară. Teoretic un fractal este infinit dar în practică această infinitate nu poate fi studiată sau măsurată. Cu toate acestea, fiecare generație a unui fractal este finită deci poate fi folosită pentru a-l studia.

Nevoia unui sistem distribuit apare la generarea fractalilor, aceștia fiind structuri complexe. Chiar dacă sunt definiți prin formule simple, generațiile acestora sunt calculate recursiv, ceea ce necesită atât timp cât și spațiu pentru procesarea si stocarea datelor. Timpul necesar pentru calcularea unui fractal poate fi teoretic redus prin împărțirea problemei de calcul la mai multe unități de procesare.

Astfel, dispozitivul Android care cere o generație a unui fractal se va putea conecta la unul sau mai multe resurse exterioare și va putea împărți datele de calculat la mai multe unități de procesare – calculatoare Linux. Fiecare nod va genera o parte a fractalului, trimițând rezultatele obținute înapoi la dispozitivul Android. Acesta va concatena rezultatele parțiale și va afișa fractalul selectat la generația dorită.

Folosirea unui sistem distribuit în acest mod are două efecte secundare pentru dispozitivul Android pe care rulează aplicația. În primul rând timpul de procesare se reduce prin folosirea resurselor externe de procesare, iar în al doilea rând, timpul de funcționare a bateriei poate fi mărit prin reducerea datelor procesate local – acesta însă este condiționat și de folosirea wireless-ului și a datelor trimise prin acesta.

Fractali

2.1 Introducere

Majoritatea sistemelor fizice din natură și multe din creațiile umane nu sunt forme geometrice regulare derivate din geometria standard a lui Euclid. Geometria fractală oferă mijloace aproape nelimitate de a descrie, măsura și prezice aceste fenomene naturale. Acest domeniu al matematicii apărut în anii 1970 dezvoltat mai ales de Benoît Mandelbrot.

Fig. 2.1 Setul Mandelbrot[1]

Cu toate că formele descrise de geometria fractală sunt foarte diferite de cele din geometria clasică, acestea au proprietăți similare iar la baza acestora stau tot generarea de forme, măsurarea acestora și definirea lor.

Matematica fractalilor își are rădăcinile în secolul 17, apărând odată cu ideea de recursivitate, continuând cu studiul funcțiilor continue, dar nu și diferențiale în secolul 19. În secolul 20 apare și conceptul de fractal, ca în secolul 21 să fie concepute și primele modele pe calculator.[1]

2.2 Definiție

Un fractal este un set matematic care afișează în mod normal tipare autosimilare.[2] Fractalii pot fi la fel, sau aproape la fel la diferite scări. Conceptul de fractali poate fi extins la ideea de un tipar detaliat care se repetă.[3]

Termenul de fractal poate fi mai semnificativ pentru artiști, decât pentru matematicieni. Conceptul matematic poate fi definit cu greu, chiar și de matematicieni, dar caracteristicile cheie pot fi înțelese chiar și de persoane fără cunoștințe matematice. Termenul a fost folosit prima oară de matematicianul Benoît Mandelbrot în 1975, provenind din limba latină, de la termenul "fractus" care se traduce în "frânt" / "rupt" / "întrerupt".[3] Acesta este folosit pentru a extinde conceptele teoretice a dimensiunilor fractale pentru tipare geometrice găsite în natură.

Fig. 2.2 Artă Fractală[2]

Există neînțelegeri asupra unei definiții formale a fractalilor. Mandelbrot îi descrie în felul următor "beautiful, damn hard, increasingly useful. That's fractals."[4] Descrierea evidentă este că un fractal este auto-similar infinit, iterat și o construcție matematică detaliată ce are o dimensiune fractală. Fractalii nu sunt tipare geometrice limitate, încât pot descrie chiar și procese în timp. Tiparele fractale cu diverse grade de auto-similare au fost generate și studiate ca și imagini, structuri și sunete, fiind găsite în natură, tehnologie, artă și drept.

2.3 Caracteristici

Una din descrierile publicate de Mandelbrot prezinta fractalii ca fiind o formă geometrică fragmentată sau aspră care poate fi împărțită în bucăți, fiecare din ele fiind cel puțin aproximativ o copie în miniatură a întregului.[3] Această definiție e ajutătoare, dar limitată. Specialiștii nu sunt de acord cu o definiție comună, dar majoritatea folosesc concepte de autosimilare și o relație aparte între fractal și spațiul ocupat de acesta.[3] Un punct de comun acord este că fractalii sunt caracterizați de dimensiuni fractale, dar, cu toate că această caracteristică cuantifică complexitatea, nu poate descrie și nici nu poate da informații legate de modul de construire a unui fractal.[5] Când Mandelbrot a folosit prima oară termenul de fractal, a fost pentru a defini acele forme geometrice care au dimensiunea Hausdorff-Besicovitch mai mare decât dimensiunea topologică.[6] Această specificație nu este însă întâlnită la fractalii umplutori de spațiu, cum ar fi curba Hilbert.

Conform lui Falconer, în loc să aibă o definiție strictă, fractalii ar putea avea următoarele caracteristici, împreună cu dimensiunea fractală și lipsa diferențiabilității:[7]

autosimilare, manifestată într-una din următoarele forme:

autosimilare exactă – fractalul este identic la orice scară (ex. fulgul Koch)

cvasi autosimilare – aproximează același tipar la diferite scări; poate conține copii deformate sau denaturate ale fractalului original (ex. setul Mandelbrot)

autosimilare statistică – repetă un tipar stocastic, astfel încât măsurile numerice sunt conservate ca statistici la orice scară (ex. fractalii generați aleator)[8]

autosimilare cantitativă – ca în seriile de timp[9]

scalare multifractală – caracterizată de mai mult de o singură dimensiune fractală sau de o regulă de scalare

o structură detaliată la scări arbitrari mai mici. O consecință a acesteia sunt proprietățile care apar ca efecte secundare[10]

neregularitate locală sau globală care nu poate fi descrisă prin geometria tradițională Euclidiană. Pentru imagini sau modele fractale, aceasta poate fi descrisă ca „o suprafață care se strânge în ceva neted”[11]

definiții simple și recursive

Aceste criterii formează orientări pentru descrierea fractalilor, prin excluderea anumitor cazuri, cum ar fi formele autosimilare care nu au trăsături de fractali. De exemplu, o linie dreaptă este autosimilară, dar nu și fractală, lipsindu-i detaliile și putând fi descrisă de geometria Euclidiană.[3]

2.3.1 Autosimilare

Caracteristica de autosimilare este înțeleasă prin mărirea imaginii inițiale în mod asemănător cu folosirea lentilelor pentru descoperirea unor detalii noi, inițial neobservabile. Atunci când ne referim la fractali, nu sunt descoperite detalii noi, părți din imaginea mărită fiind reprezentări identice a imaginii inițiale. Nu se schimbă nimic în reprezentarea fractalului, iar același tipar se repetă la infinit pentru majoritatea fractalilor, iar pentru ceilalți asemănarea este foarte mare. Autoasemănarea nu este un concept nou, acesta regăsindu-se spre exemplu în oglindirea infinită pentru oglinzile paralele. Diferența pentru un fractal este că tiparele reproduse trebuie să fie detaliate.[3]

Fig. 2.3 Autosimilare în fulgul Koch[3]

2.3.2 Dimensiunea Fractală

Fractalii se disting de formele geometrice clasice prin scalarea dimensiunilor. Dublarea lungimii muchiilor unui pătrat mărește aria de 4 ori, care înseamnă 2 la puterea a doua, din cauza faptului că un pătrat este bidimensional. De asemenea, dacă raza unei sfere este dublată, volumul ei crește de 2 la puterea a treia ori, fiind o formă tridimensională. Dacă lungimea primei dimensiuni a unui fractal este dublată, spațiul pe care fractalul îl ocupă se multiplică printr-un număr care nu este întreg, dimensiunea unui fractal aflându-se între două numere întregi.

Fig. 2.4 Dimensiunea Fractală pentru curba Koch (Imagine Obținută după 2 iterații)[4]

2.3.3 Detaliere

Idea de detaliere poate fi înțeleasă fără cunoștințe matematice. Faptul că un fractal are o dimensiune fractală mai mare decât dimensiunea topologică se referă la modul în care acesta este scalat, la modul în care sunt percepute și formele geometrice regulate. O linie regulată este, de exemplu, de 1 dimensiune. Dacă aceasta este divizată în 3 bucăți, fiecare cu lungimea de 1/3 din lungimea inițială, vor exista mereu 3 bucăți egale. În contrast, considerând o curbă fractală care are și o dimensiune fractală mai mare ca 1, în urma divizării va avea 4 bucăți de lungimi egale, fiecare 1/3 din lungimea inițială. Acest fapt se datorează necesității de a repeta tiparul inițial a fractalului.

2.3.4 Lipsa Diferențiabilității

Acest lucru poate duce la înțelegerea unei alte caracteristici a fractalilor, faptul că fractalii ca și ecuații matematice nu sunt diferențiabili. Mai exact, fractalii nu pot fi măsurați într-un mod tradițional.[3] De exemplu, la calcularea lungimii unei curbe fractale, segmentele care o alcătuiesc ar putea fi considerate prea mici pentru a fi măsurate. Dat fiind că un fractal este teoretic infinit, segmentele care îl alcătuiesc s-ar repeta și ar reapărea oricând am încerca să îl mărim pentru a-i să măsura detaliile. Chiar dacă acest lucru poate fi contra intuitiv, este modul în care fractalii funcționează.[3]

2.4 Generare și Simulare

Fractalii pot fi generați folosind programe pentru generarea fractalilor. Fiecare program poate avea una sau mai multe modalități de generare implementate.

2.4.1 Tehnici de Generare

IFS (Iterated Function System – sistem de funcții iterate) – folosesc reguli fixe de înlocuire; pot fi stocastice sau deterministe (ex. fulgul Koch, curba Peano, carpeta Sierpinski, Menger Sponge, curba Heighway Dragon).

Atractori stranii – folosesc iterațiile unei hărți sau soluțiile unui sistem cu ecuații diferențiale cu manifestări haotice

Sisteme Lindenmayer (L-system) – folosesc rescrierea șirurilor de caractere; pot semăna cu structuri arborescente, de exemplu plantele sau celulele biologice (neuronii sau celule imune), vene, structura plămânului, etc. sau cu tipare turtle graphics, cum ar fi curbele umplutoare de spațiu

Escape-time fractals – folosesc formule sau relații de recurență în fiecare punct din spațiu (cum ar fi planul complex); sunt de obicei cvasi autosimilari, cunoscuți și ca fractali orbitali (ex. setul Mandelbrot, setul Julia, fractalul Lyapunov, fractalul Nova, fractalul Burning Ship). Câmpurile vectoriale generate de 2 sau mai multe iterații ale acestor fractali pot da nașterea naștere unei forme fractale atunci când puncte (sau pixeli) sunt trecute prin acest câmp în mod repetat.

Fig. 2.5 Modalitate de Generare a unui Fractal cu IFS[5]

Fig. 2.6 Copac Generat cu un L-System[6]

Fig. 2.7 Fractalul Burning Ship – Generat în Spațiu Complex[7]

Fractali Aleatori – folosesc reguli stocastice; ex: Levy flight, self avoiding walk, peisaje fractale, copacul Brownian, mișcarea Browniană (fractali cu dendrite generați prin modelarea clusterelor cu agregație cu difuzie limitată sau cu reacție limitată)[8]

Reguli Finite de Subdiviziune – folosesc un algoritm recursiv topologic pentru rafinare, fiind asemănători cu procesul divizării celulare. De exemplu, procesul iterativ folosit pentru setul Cantor și carpeta Sierpinski, precum și subdivizarea centrului de greutate.

Fig. 2.8 Fractali Aleatori[8]

2.4.2 Simulare

Au existat numeroase generări ale modelelor fractale, dar numai până la o anumită scară, nu la infinit, rămânând în limitele practice de spațiu și timp. Modelele actuale pot simula fractali teoretici sau fenomene naturale cu trăsături fractale. În urma procesului de modelare se pot obține imagini artistice, rezultate pentru investigații sau referințe pentru analiza fractalilor. Imaginile și alte rezultate ale modelării fractalilor sunt numite la rândul lor fractali, chiar dacă nu posedă caracteristici fractale, cum ar fi mărirea unei porțiuni din imagine care poate să nu aibă caracteristici fractale.

Fractalii modelați pot include sunete, imagini digitale, tipare electrochimice, ritmuri circadiene, etc. Tiparele fractale au fost reconstruite într-un model tridimensional, numit în mod obișnuit modelare "in silico" (simulat pe calculator). Modelele fractale sunt create folosind software-uri de specialitate care implementează tehnici asemenea celor menționate mai sus. Natura recursivă a unor tipare este evidentă în unele cazuri – ramura unui copac sau frunzele unei ferigi sunt replici în miniatură a întregului, nu neapărat identice, dar similare. În mod asemănător, fractalii aleatori au fost folosiți pentru descrierea sau crearea multor obiecte neregulate din natură. O limitare a modelării fractalilor este că asemănarea unui model fractal cu un fenomen natural nu este dovada faptului că fenomenul care este modelat este format de un proces similar cu algoritmul de modelare.

2.5 Fenomene Naturale și Domenii cu Fractali

Fractali aproximativi au fost găsiți în natură cu trăsături de autosimilare vaste, dar finite. Conexiunea dintre fractali și frunze este folosită de exemplu pentru a determina cantitatea de carbon conținută în copaci.[13]

Fig. 2.9 Fractali 3D[9]

Exemple de fenomene pentru care trăsăturile fractale sunt evidente sau anticipate sunt: rețele de râuri, șirurile de munți, cratere, fulgere, țărmuri, valurile oceanelor, ananas, diverse legume, colorația animalelor, fulgi de zăpadă, flori de gheață, cutremure, bătăile inimii, ADN-ul, percepțiile psihologice subiective, etc.

Fig. 2.10 Fulger[10] (stânga) și Flori de gheață[11] (dreapta)

În artă, fractalii au fost folosiți de către pictorul american Jackson Pollock. Cu toate că picturile acestuia par să conțină stropiri haotice, analiza pe calculator a găsit tipare fractale în creațiile acestuia.[14] Decalcomania, tehnică ce presupune presarea vopselii între două suprafețe poate produce tipare fractale.[15] Ron Eglash a determinat că unele tipare sunt găsite în textilele, sculpturile sau chiar și frizurile Africane. Mai mult, în arhitectura lor, casele circulare apar în cercuri de cercuri, iar cele dreptunghiulare în dreptunghiuri de dreptunghiuri.[16]

În tehnologie, aceștia sunt folosiți pentru antene fractale, transistoare fractale, determinarea creșterii urbane, procesare digitală de imagini, peisaje fractale, compresoare de semnal și imagine, noua generație de muzică, design-ul jocurilor video, grafica pe calculator, tricouri sau alte articole de modă, search and rescue, patologie, geologie, geografie, seismologie, analiză tehnică, etc.

Fig. 2.11 Antene Fractale[12]

Fractalii sunt folosiți și în drept. Dacă o regulă sau un principiu al dreptului este conceptualizat ca definirea un zone bidimensionale de conduită, conduită înăuntrul căreia trebuie să fie licită și înafara căreia trebuie să fie ilicită, se poate observa că granița zonei respective trebuie să fie un fractal. Acest lucru este necesar datorită potențialului de excepții și extensii infinite și recursive necesare pentru a acomoda toate variațiunile posibile.[17]

2.6 Sisteme Lindenmayer

2.6.1 Definiție

Un L-System, sau sistem Lindenmayer este un sistem de rescriere paralelă și un tip de gramatică formală. Un L-System este format dintr-un alfabet de simboluri care poate fi folosit în alcătuirea șirurilor de caractere ce au diverse scopuri, o colecție de reguli de producție care expandează fiecare simbol într-un șir de caractere, o axiomă inițială de la care se pornește și un mecanism de translatare a șirurilor generate în structuri geometrice.

Sistemele Lindenmayer au fost introduse și dezvoltate în 1968 de Aristid Lindenmayer, biolog și botanist teoretician, la universitatea din Utrecht din Ungaria. Lindenmayer a folosit L-Systems pentru a descrie comportamentul celulelor din plante și pentru a modela procesul de creștere a plantelor. Astfel de sisteme au fost folosite și pentru a modela morfologia unor varietăți de organisme[18] și poate genera fractali autosimilari, cum sunt și sistemele de funcții iterate.

Inițial, Lindenmayer a studiat tiparele în creșterea diverselor tipuri de alge, cum ar fi bacteria albastră/verde Anabaena catenula. Sistemele Lindenmayer au fost folosite la început pentru a studia creșterea organismelor multicelulare simple, și pentru a ilustra relații dintre celulele vecine ale unei plante. Mai târziu, sistemul a fost folosit pentru a descrie plante mai mari și structuri arborescente mai complexe.

Fig. 2.12 Exemple de Structuri Generate cu diverse L-Systems[13]

2.6.2 Structura

Natura recursivă a regulilor unui L-System determină autosimilarea și din acest motiv formele fractale sunt ușor de descris prin acest sistem. Plantele și formele organice cu aspect natural sunt ușor de definit, iar prin creșterea nivelului de recursie acestea cresc și devin mai complexe. Sistemele Lindenmayer sunt de asemenea populare în generarea vieții artificiale.

Gramaticile unui L-System sunt foarte similare gramaticilor semi-Thue (sau celor din ierarhia Chomsky). Sistemele Lindenmayer sunt cunoscute ca sisteme L parametrice, definite de tuplul

G = (V, w, P)

unde

V este alfabetul – un set de simboluri care conțin elemente înlocuibile (variabile).

w este axioma – un șir de simboluri din V care definește starea inițială a sistemului.

P este un set de reguli de producție – definesc modul în care variabilele pot fi înlocuite cu combinații dintre variabile și constante. O producție conține două șiruri: predecesorul și succesorul.

Regulile unui sistem L sunt aplicate iterativ, de la axiomă (starea inițială). La fiecare iterație sunt aplicate oricât de multe reguli posibile simultan. Aceasta este principala diferență dintre un L-System și un limbaj formal generat de o gramatica formală. Dacă regulile de producție ar fi aplicate pe rând, am genera un limbaj, și nu un L-System. Așadar, un sistem Lindenmayer este un subset strict al limbajelor.

Un L-System este independent de context dacă fiecare regulă de producție face referință doar la simboluri individuale, nu și la vecinii acestora. Acestea sunt specificate printr-o gramatică prefixată sau regulată. Dacă o regulă depinde nu numai de un simbol, ci și de vecinii acestora, sistemul devine dependent de context.

Dacă există exact o singură regulă pentru fiecare simbol, atunci sistemul este determinist. Un L-System determinist și independent de context este numit sistem D0L. Dacă există mai multe reguli și fiecare este aleasă cu o anumită probabilitate la fiecare iterație, atunci L-System este numit stocastic.

Pentru a folosi un astfel de sistem pentru generarea imaginilor, este necesar ca simbolurile din sistem să reprezinte elemente grafice. Pentru a realiza imaginea finală, se pot folosi metode de desenare de genul "turtle graphics" (asemănătoare cu cele folosite în limbajul de programare Logo).

2.6.3 Exemplu

În continuare, este prezentat modul original în care Lindenmayer a folosit un L-System pentru a modela creșterea unei alge.

variabile: A B

constante: fără

axioma: A

reguli: A -> AB; B -> A

ceea ce are următorul rezultat:

n = 0 : A

n = 1 : AB

n = 2 : ABA

n = 3 : ABAAB

n = 4 : ABAABABA

n = 5 : ABAABABAABAAB

n = 6 : ABAABABAABAABABAABABA

n = 7 : ABAABABAABAABABAABABAABAABABAABAAB

n = 8 : ABAABABAABAABABAABABAABAABABAABAABABAABABAABAABABAABABA

n = 0 – A – reprezintă starea inițială sau axioma

n = 1 – AB – este aplicată regula A -> AB, iar noul șir devine AB; regula B -> A nu a putut fi aplicată, simbolul B neexistând în șirul inițial

n = 2 – ABA – se aplică ambele reguli o singură dată

… – se continuă până la generația dorită; se poate observa că A-ul produce o copie a lui și un B, care este la rândul lui transformat în A în următoarea generație

n = 0: A

/ \

n = 1: A B

/ | \

n = 2: A B A

/ | | | \

n = 3: A B A A B

/ | | | \ | \ \

n = 4: A B A A B A B A

Dacă numărăm lungimea fiecărui șir de caractere de la fiecare gnerație, putem obține șirul lui Fibonacci: 1 2 3 5 8 13 21…

2.6.4 Tipuri de Gramatici

O varietate de tehnici au fost dezvoltate pe baza sistemului Lindenmayer care pot fi folosite combinat. Printre acestea se numără și gramaticile stocastice, dependente de context și parametrice.

2.6.4.1 Gramatici stocastice

Modelul prezentat până acum este determinist, adică pentru orice simbol din alfabetul gramaticii există o singură regulă de producție, care este mereu aleasă și produce același rezultat. Una din alternative este specificarea mai multor reguli de producție pentru oricare simbol, fiecare regulă având propria probabilitate de aplicare. De exemplu următoarea regulă deterministă

A -> AB

poate fi transformată într-o regulă probabilistică:

A (0.5) -> AB

A (0.5) -> A

Strict legat de această producție, oricând trebuie rescris simbolul "0", există o șansă de 50% ca prima regulă (cea inițială) să fie aplicată și o șansă de 50% ca simbolul să nu se schimbe în timpul producției. La folosirea unei gramatici stocastice într-un context evoluționar, este indicată încorporarea unui element aleator în genotip, astfel încât proprietățile stocastice ale imaginii rămân constante între generații.

2.6.4.2 Gramatici dependente de context

O regulă de producție dependentă de context ține cont nu numai de simbolul care trebuie modificat, ci și de simbolurile care apar înainte și după acesta. De exemplu următoarea regulă:

B < A > C -> AA

transformă simbolul "A" în șirul "AA", dar numai în cazul în care "A" se află între "B" și "C", ca în șirul:

…BAC…

Ca și regulile stocastice, există multiple reguli pentru simboluri în contexte diferite. Dacă niciuna din reguli nu poate fi aplicată, este aleasă implicit regula identitate, iar simbolul nu se schimbă. Dacă există reguli dependente de context și reguli independente de context în aceeași gramatică, regulile dependente de context au precedență.

2.6.4.3 Gramatici parametrice

În gramaticile parametrice, fiecare simbol din alfabet are o valoare asociată. Un simbol împreună cu lista de parametrii este numit un modul, iar șirul unei gramatici parametrice este o serie de module. Un exemplu de șir poate fi:

a(1,2)b(1,0)a(0,5)

Parametrii pot fi folosiți de funcțiile de desenare, dar și de regulile de producție. Regulile de producție pot folosi parametrii în două moduri: ca o condiție care determină dacă regula poate fi aplicată sau pentru a modifica parametrii generației următoare. De exemplu:

a(x, y) : x = 0 -> a(1, y+1)b(0,1)

Modulul a(x, y) va fi transformat după această regulă de producție, numai dacă este îndeplinită condiția x = 0. De exemplu, regula va fi aplicată pentru a(0, 1), dar nu și pentru a(1, 1).

În partea de transformare a regulii, pot fi afectați și parametrii. În exemplul anterior, modulul b(x, y) este adăugat la șirul de caractere, cu parametrii inițiali (2, 3). De asemenea, parametrii din modulul inițial sunt schimbați. Modulul

a(0, 2)

devine

a(1, 3)b(0, 1)

încât parametrul x din a(x, y) este transformat în 1, iar parametrul y este incrementat cu o unitate.

Gramaticile parametrice permit calcularea lungimilor și unghiurilor în gramatică, și nu în turtle graphics așa cum fac celelalte. De asemenea, poate fi dată vârsta ca și parametru al unui modul pentru a aplica diferite reguli în funcție de vârsta unui segment al plantelor, permițând animații ale întregului ciclu de viață.

2.7 Turtle Graphics

2.7.1 Definiție

Turtle Graphics este un termen folosit în grafica pe calculator, fiind o metodă de programare a graficii vectoriale care folosește un cursor ("turtle") într-un plan cartezian. Turtle Graphics este principala modalitate de desenare a sistemelor Lindenmayer.

Turtle-ul are trei atribute:

locație

direcție

un stilou, cu atribute pentru culoare și grosime

Turtle-ul se mișcă cu comenzi relative la propria lui poziție, cum ar fi "înainte 10 pixeli" sau "rotire la stânga cu 90 de grade". Stiloul poate fi și el controlat, prin setarea culorii sau a grosimii.

Pornind de la aceste concepte, putem construi forme geometrice complexe, cum ar fi triunghiuri, pătrate, cercuri, și alte figuri compuse. În combinație cu controlul mișcării, proceduri și recursie, ideea de turtle graphics este folositoare în sistemele Lindenmayer pentru generare de fractali.

Fig. 2.13 Fractal Desenat cu Turtle Graphics[14]

2.7.2 Istoric

Turtle graphics este asociat mai ales cu limbajul de programare Logo. Seymour Papert a adăugat suport pentru acesta în anii 1960, pentru a permite utilizatorilor să controleze un turtle robot, proiectat să îndeplinească funcții de desenare cu un stilou atașat. Geometria turtle funcționează diferit de geometria carteziană, adresată prin coordonate. În primul rând, aceasta este vectorială (cu distanță și direcție relativă față de punctul curent), spre deosebire de sisteme cu adresare de coordonate. Folosirea geometriei turtle în locul unei geometrii tradiționale simulează mișcarea a unui robot turtle.

2.7.3 Turtle Robot

Turtles reprezintă o clasă de roboți educaționali dezvoltați din anii 1940 (în mare parte sub cercetătorul William Grey Walter) și folosiți în pregătirea pentru domeniile știința calculatoarelor și inginerie mecanică. Aceștia sunt dezvoltați cu o carapace emisferică (de obicei transparentă) și un sistem de propulsie capabil de întoarceri la câteva grade. Roboții mai pot conține și senzori pentru ocolirea obstacolelor, iar dacă sunt destul de sofisticați pot percepe mediul înconjurător.

Fig. 2.14 Turtle Robot[15]

Acestea vin cu un stilou încorporat care permit programatorilor să creeze design-uri pe foi de hârtie.

2.7.4 Turtle Graphics în Fractali

În cazul sistemelor Lindenmayer, majoritatea simbolurilor din alfabetul gramaticii descriu o regulă pentru Turtle Graphics. Pentru o gramatică deterministă, valorile de desenare sunt stabilite de la început.

Să presupunem următorul sistem:

variabile : 0 1

constante : [ ]

axioma : 0

reguli : 1 -> 11; 0 -> 1[0]0

După a doua iterație șirul care descrie fractalul devine 11[1[0]0]1[0]0. În simbolurile din acest șir avem instrucțiuni pentru turtle graphics, fiecare caracter având atribuită o operație de desenare diferită. Pentru acest exemplu, turtle-ul urmează următoarele instrucțiuni:

0 : desenează un segment care se termină în frunză

1 : desenează o linie

[ : reține (push) poziția și unghiul, rotește la stânga cu 45 de grade

] : preia (pop) poziția și unghiul, rotește la dreapta cu 45 de grade

Push și pop fac referire la o stivă LIFO (push și pop sunt normal separate de instrucțiunile de rotație). Atunci când turtle-ul întâlnește simbolul "[", salvează poziția și unghiul curent, ce vor fi restaurate la întâlnirea simbolului "]". Instrucțiunea pop restituie cea mai recentă valoare salvată. Prin aplicarea regulilor de mai sus, obținem imaginea unui copac.

Fiecare gramatică poate atribui propriilor simboluri instrucțiuni diferite. Pentru a evita folosirea unei gramatici cu reguli necorespunzătoare, se folosesc de obicei următoarele reprezentări:[19]

F mișcare înainte cu lungimea unei linii și desenarea liniei

G mișcare înainte cu lungimea unei linii, fără a desena linia

+ rotire stânga cu valoarea unghiului de rotație

– rotire dreapta cu valoarea unghiului de rotație

| inversarea direcției (rotire cu 180 grade)

[ salvează (push) starea curentă a desenului în stivă (poziție, unghi, etc)

] restaurează (pop) starea curentă (ultima stare salvată) a desenului din stivă

# incrementează grosimea liniei cu incrementul pentru grosimea liniei

! decrementează grosimea liniei cu incrementul pentru grosimea liniei

@ desenează un punct cu raza de lungimea unei linii

{ deschide un poligon

} închide un poligon și umple-l cu culoarea de umplere

> multiplică lungimea unei linii cu factorul de scală a lungimii unei linii

< împarte lungimea unei linii la factorul de scală a lungimii unei linii

& schimbă semnificația lui "+" cu "-"

( decrementează unghiul de întoarcere cu incrementul pentru unghiul de întoarcere

) incrementează unghiul de întoarcere cu incrementul pentru unghiul de întoarcere

În toate explicațiile de mai sus, instrucțiunile sunt aplicate pentru valori stabilite de la început. De exemplu lungimea unei linii, sau unghiul de întoarcere au valori inițiale date prin program. Pentru a aplica regula de întoarcere cu un unghi, se va considera punctul pi punctul curent al turtle-ului și pf punctul către care se face desenarea. Pentru a determina pf se aplică următoarele formule:

xf = xi + lungime * sin(radiani)

yf = yi – lungime * cos(radiani)

unde xi și yi sunt coordonatele lui pi, iar xf și yf sunt coordonatele lui pf, lungimea este distanța între cele două puncte și radiani reprezintă valoarea unghiului de rotație în radiani.

Un sistem însă nu este obligatoriu să aibă semnificații grafice pentru fiecare simbol. Pot exista și simboluri care doar ajută la producerea generațiilor prin aplicarea regulilor de producție unice. De exemplu, în următoarea gramatică, X și Y sunt astfel de simboluri. Mai mult, dacă un simbol este regulă de desenare nu înseamnă neapărat că acesta nu poate fi și variabilă implicată în determinarea următoarelor generații.

Dragon Curve

variabile : X Y

constante : F + –

axiomă : FX

reguli : X -> X+YF; Y -> FX-Y

unghi : 90

lungime : variabilă

Fig. 2.15 Fractalul Dragon Curve Generat de un Sistem Lindenmayer și Desenat prin Metoda Turtle Graphics[16]

2.8 Curbe Fractale

O curbă care se îndoaie și se răsucește oricât de mărită ar fi este o curbă fractală. Aceasta are o dimensiune fractală cu valoarea între 1 și 2. De regulă, o curbă fractală este generată ca limită a secvenței de curbe poligonale (c1, c2, …), unde fiecare pas cn este obținut din predecesorul acestuia, cn-1, printr-un proces local. Prin localitatea procesului se înțelege că o mică parte din cn este aproape de, și determinată doar de o mică parte din cn-1. De exemplu, pentru Terdragon Curve, fiecare muchie din cn-1 este înlocuită de alte 3 muchii în cn care sunt în apropierea muchiei cn-1, iar poziția și orientarea acesteia depind numai de poziția și orientarea muchiei din cn-1. Pentru a formaliza noțiunea de localitate, putem spune că o curbă poate fi generată cu un L-System.[20]

2.8.1 Curbe Umplutoare de Spațiu

Curbele umplutoare de spațiu sunt cazuri speciale de fractali. Nu poate exista o curbă umplutoare de spațiu diferențiabilă, această proprietate putând pune o limită asupra vitezei de întoarcere a curbei.

În analiza matematică, o curbă umplutoare de spațiu este o curbă care se întinde pe un întreg pătrat bidimensional (sau mai general, pe un hipercub de n dimensiuni). Giuseppe Peano (1858 – 1932) a fost primul care a descoperit o astfel de curbă, iar din această cauză curbele umplutoare de spațiu în două dimensiuni sunt numite câteodată și curbe Peano. Această denumire nu trebuie însă confundată cu denumirea curba Peano, exemplul specific găsit de Peano. În 1890, Peano a descoperit o curbă densă, auto-intersectată, numită azi Peano curve, care trece prin fiecare punct al pătratului în care este generată.

2.8.1.1 Definiție

Intuitiv, o curbă continuă în 2, 3 sau mai multe dimensiuni poate fi definită ca o cale a unui punct în continuă mișcare. Pentru a elimina orice neclaritate cu privire la această noțiune, Jordan a introdus în 1887 următoarea definiție: O curbă cu puncte finale este o funcție continuă a cărui domeniu este în intervalul unitate [0, 1].

La modul cel mai generic, gama unei asemenea funcții se poate afla într-un spațiu arbitrar topologic, dar cele mai studiate cazuri sunt în spațiul bidimensional – curba planară sau în spațiul tridimensional – curba spațială.

De multe ori, curba este identificată prin gama sau imaginea funcției (setul tuturor valorilor posibile ale funcției), în loc să fie identificată în funcție însăși. Este de asemenea posibilă definirea unor curbe fără puncte de final care să fie o funcție continuă pe axa reală – sau în intervalul deschis (0, 1).

2.8.1.2 Modul de Construire a unei Curbe Umplutoare de Spațiu

Fie C spațiul Cantor 2ℕ.

Începem cu o funcție h din spațiul Cantor C pe întregul interval unitate [0, 1]. Restricția funcției Cantor asupra setului Cantor este un exemplu pentru funcția h. De la aceasta, obținem o funcție continuă H din produsul topologic C x C pe întregul pătrat unitate [0, 1] x [0, 1] prin setarea H(x, y) = (h(x), h(y)).

Deoarece setul Cantor este homeomorfic produsului C x C, există o bijecție continuă g din setul Cantor pe produsul C X C. Compunerea f a funcțiilor H și g este o funcție continuă care mapează setul Cantor pe întregul pătrat unitate. În mod analog, putem folosi teorema care zice că fiecare spațiu metric compact este o imagine continuă a setului Cantor pentru obținerea funcției f.

În final, putem extinde funcția f la o funcție continuă F a cărui domeniu este întregul interval [0, 1]. Aceasta poate fi făcută ori prin folosirea teoremei Tietze de extensie asupra fiecărei componente din f, sau prin simpla extindere a lui f în mod linear – astfel încât pe fiecare interval deschis (a, b) șters din construcția setului Cantor, definim partea extinsă din F pe (a, b) ca fiind segmentul drept din interiorul pătratului unitate care unește valoarea f(a) cu f(b).

2.8.1.3 Proprietăți

Dacă o curbă nu este injectivă, atunci se pot găsi două subcurbe ale curbei, care se intersectează, fiecare obținută folosind imaginile a două puncte disjuncte din domeniul curbei (segmentul unitate). Cele două curbe se intersectează dacă intersecția imaginii lor nu este vidă. Termenul de intersecție a două curbe nu se referă neapărat la faptul că acestea se suprapun. Termenul poate fi folosit și dacă acestea fac contact fără a fi suprapuse, de exemplu printr-o linie adiacentă.

O curbă continuă care nu se auto-intersectează nu poate umple pătratul unitate deoarece aceasta va deveni homeomorfică de la intervalul unitate, la pătratul unitate (orice bijecție continuă de la un spațiu compact la un spațiu Hausdorff este homeomorfică). Dar un pătrat unitate nu are niciun punct de tăiere, deci nu poate fi homeomorfic pe intervalul unitate, în care toate punctele, mai puțin cele terminale sunt puncte de tăiere.

Încă de la clasicele curbe umplutoare de spațiu, Peano curve și Hilbert curve, unde două subcurbe se intersectau în sensul teoretic, există contact fără existența suprapunerii. O curbă umplutoare de spațiu poate fi în orice loc auto-suprapusă dacă curbele aproximative sunt auto-suprapuse. Aproximările unei curbe auto-suprapuse pot fi auto-ocolitoare. În 3 dimensiuni curbele aproximative auto-ocolitoare pot conține chiar și noduri matematice. Curbele aproximative rămân în spațiul restrâns al unui spațiu de n dimensiuni, dar mărimea lor poate crește fără granițe.

2.8.1.4 Teorema Hahn-Mazurkiewicz

Teorema Hahn-Mazurkiewicz conține următoarea caracterizare a spațiilor care sunt imagini continui ale curbelor: Un spațiu topologic Hausdorff este o imagine continuă a intervalului unitate dacă și numai dacă acesta este un spațiu complet separabil, compact, conectat și conectat local. Spațiile care sunt imagini continue ale intervalului unitate mai sunt denumite și spații Peano.

2.8.2 Exemple de Curbe Fractale

2.8.2.1 Fulgul Koch

Fulgul Koch (cunoscut și sub denumirea de steaua Koch sau insula Koch) este o curbă fractală, unul din primii fractali definiți. Acesta este bazat pe curba Koch, care a apărut în 1904, într-o lucrare scrisă de matematicianul suedez Hedge von Koch.

Construire

Fulgul Koch poate fi construit începând cu un triunghi echilateral, la care se modifică recursiv fiecare segment în următorul mod:

se divide segmentul în 3 segmente de dimensiuni egale

se desenează un triunghi echilateral care are segmentul din centru obținut la punctul 1. ca bază și vârful în exterior

se șterge segmentul care este baza triunghiului obținut la pasul 2.

După prima iterație, rezultatul obținut este conturul unei hexagrame. Fulgul Koch reprezintă limita atinsă prin aplicarea pașilor descriși mai sus de mai multe ori. Curba Koch, descrisă original de Koch este construită doar cu una din cele 3 laturi ale triunghiului de la care se pornește. Cu alte cuvinte, trei curbe Koch formează un fulg Koch.

Proprietăți

Curba Koch are o lungime infinită, lungimea totală a curbei crescând cu o treime la fiecare iterație. Fiecare iterație creează de patru ori mai multe segmente decât iterația următoare, iar lungimea pentru fiecare este o treime din lungimea segmentului la generația anterioară. Așadar, lungimea curbei după n iterații va avea o mărime de ori mai mare decât perimetrul triunghiului original, lungime nemărginită, pentru că n tinde la infinit.

Dimensiune fractală a curbei lui Koch este , mai mare decât dimensiunea unei linii de 1, dar mai mică decât dimensiunea unei curbe umplutoare de spațiu, de 2.

După fiecare iterație, numărul de laturi ale fulgului Koch crește de 4 ori, deci numărul de laturi după n iterații este dat de:

Dacă triunghiul echilateral original are laturi de lungimea s, lungimea fiecărei laturi din fulgul Koch după n iterații este:

iar perimetrul fulgului va fi:

La fiecare iterație un nou triunghi este adăugat la fiecare latură a iterației anterioare, deci numărul de triunghiuri adăugate la iterația n este:

Aria fiecărui nou triunghi adăugat într-o iterație este de 9 ori mai mică decât aria triunghiurilor din iterația anterioară deci aria fiecărui triunghi la iterația n este:

unde a0 este aria triunghiului inițial. Aria totală adăugată în iterația n este deci:

Aria totală a fulgului după n iterații este:

de unde rezultă:

Având în vedere că numărul de iterații n tinde la infinit, limita perimetrului este:

având în vedere că , limita ariei este

pentru că .

Deci aria fulgului Koch este din aria triunghiului original. Exprimată în lungimea s a unei muchii din triunghiul original, aria devine: . Cu toate acestea, nu este corect să presupunem că perimetrul fulgului Koch este infinit, deoarece nu este uni-dimensional, deci nu poate fi măsurat ca o linie unidimensională. O măsură dimensională de există, dar nu a fost încă calculată. Numai limitele inferioare și superioare au fost inventate până acum.

Reprezentare în sistem Lindenmayer

Alfabet: F

Constante: +, –

Axioma: F–F–F

Reguli: F -> F+F–F+F

În care unghiul de întoarcere este de 60 de grade.

Fig. 2.16 Primele 5 Generații ale Fulgului Koch

Curba Koch – Reprezentare în sistem Lindenmayer

Una din cele trei laturi ale fulgului Koch reprezintă curba Koch. Pentru desenarea acesteia se folosește următorul sistem Lindenmayer:

Alfabet: F

Constante: +, –

Axioma: F

Reguli: F -> F+F–F+F

În care unghiul de întoarcere este de 60 de grade.

Fig. 2.17 Primele 5 Generații ale Curbei Koch

2.8.2.2 Curba Dragon Heighway

Heighway Dragon este o curbă fractală auto-similară ce poate fi aproximată prin metode recursive, cum ar fi sistemele Lindenmayer.

Cunoscut și sub numele de Harter-Heighway Dragon sau Jurassic Park Dragon, aceasta a fost investigată inițial de fizicienii de la NASA John Heighway, Bruce Banks și William Harter. A fost descrisă de Martin Hardner într-o coloană din "Mathematical Games" în 1967. Multe din proprietățile sale au fost publicate de Chandler Davis și Donald Knuth.

În limbaj natural poate fi descrisă în modul următor: începând de la un segment de bază, se înlocuiește fiecare segment cu 2 segmente echivalente cu un unghi drept între el, rotite la 45 de grade față de segmentul înlocuit, alternativ la stânga și la dreapta.

Aceasta mai poate fi descrisă și prin următorul sistem de funcții iterate:

cu un set de puncte inițiale .

Folosind perechi de numere reale, funcțiile anterioare se transformă în:

Plierea Dragonului

Dacă urmărim o iterație a curbei Heighway Dragon de la un capăt la celălalt, găsim o serie de întoarceri de 90 de grade unele la stânga și altele la dreapta.

Dacă notăm cu S (stânga) și D (dreapta) întoarcerile acestei, pentru primele câteva iterații obținem:

iterația 1: D

iterația 2: D D S

iterația 3: D D S D D S S

iterația 4: D D S D D S S D D D S S D S S

Ceea ce sugerează următorul tipar: fiecare iterație este formată din iterația anterioară, la care se adaugă un D la coadă, apoi se copia iterația originală, se întoarce în oglindă, se interschimbă fiecare literă, apoi se adaugă după ultimul D.

Acest tipar ne dă o metodă pentru determinarea direcției la a n-a întoarcere în secvența curbei Dragon Heighway. În primul rând, se scrie n sub forma k2m, unde k este un număr impar. Direcția celei de-a n-a întoarcere este determinată prin rezultatul k modulo 4, adică restul împărțirii lui k la 4. Dacă rezultatul este 1, atunci cea de-a n-a întoarcere este către dreapta. Dacă rezultatul este 3, atunci întoarcerea este către stânga.

De exemplu, pentru a determina a 76376-a întoarcere:

76376 = 9547 * 8

9547 = 2386 * 4 + 3

deci 9547 % 4 = 3

de unde rezultă ca întoarcerea este către stânga

Dimensiune

În ciuda aspectului neregulat, fractalul poate fi încadrat într-un dreptunghi de dimensiuni simple, cu latura de 1, respectiv 1.5. Acestea sunt însă doar limite, nu și valorile actuale.

Fig. 2.18 Limitele Încadrării Curbei Dragon[17]

Suprafața acestuia este la fel de simplă: dacă segmentul inițial are valoarea 1, atunci suprafața are valoarea . Acest rezultat apare ca urmare a proprietății sale de pavare.

Curba nu se întretaie niciodată.

Cea mai evidentă auto-similaritate în curba Dragon Heighway poate fi observată ca repetiții la de grade ale acluiași tipar micșorat cu .

Dimensiunea sa fractală poate fi calculată: . Acest lucru îl încadrează la curbele umplutoare de spațiu.

Granița sa are o lungime infinită, ținând cont că acesta crește cu un factor similar la fiecare iterație.

Dimensiunea fractală a graniței a fost aproximată numeric de Chang și Zhang. Aceasta poate fi găsită și analitic:[21] ; ca rezultat al ecuației

Reprezentare în sistem Lindenmayer

Alfabet: X, Y

Constante: F, +, –

Axioma: FX

Reguli: X -> X+YF+; Y -> -FX-Y

În care unghiul de întoarcere este de 90 de grade.

Fig. 2.19 Primele 9 Generații ale Curbei Dragon

Terdragon

Acesta este limita următorului sistem de funcții iterate:

unde: și

Reprezentare în sistem Lindenmayer

Alfabet: F

Constante: +, –

Axioma: F

Reguli: F -> F+F-F

În care unghiul de întoarcere este de 120 de grade.

Fig. 2.20 Primele 9 Generații ale Curbei Terdragon

2.8.2.3 Curba Levy C

Curba Levy C este un fractal descris de Ernesto Cesaro în 1906 și de Georg Faber în 1910, dar care acum poartă numele matematicianului francez Paul Levy, care a fost primul care i-a descris proprietățile de auto-similare și care a furnizat o reprezentare geometrică, care a încadrat-o în aceeași clasă de curbe ca și curba Koch. Este un caz special al curbei cu perioadă dublă, curba de Rham.

Construcția prin L-System

La folosirea unui sistem Lindenmayer, construcția curbei Levy începe cu o linie dreaptă. Din aceasta este construit un triunghi isoscel cu unghiuri de 45, 90 și 45 de grade folosind latura originală ca ipotenuză. Linia originală este apoi înlocuită de celelalte două laturi ale acestui triunghi.

La a doua iterație, fiecare din cele două linii reprezintă baza pentru un nou triunghi isoscel cu unghi drept și sunt înlocuite de laturile triunghiurilor care le formează. Deci, după două iterații curba ia forma a 3 laturi dintr-un dreptunghi, cu lungimea liniei originale, dar cu lățimea doar la jumătate.

La fiecare iterație ulterioară, fiecare linie este înlocuită de alte două laturi ale unui triunghi isoscel. După n iterații, curba are 2n linii, fiecare mai mică decât originalul cu un factor de 2n/2.

Curba fractală care este limita acestui proces infinit este curba Levy C. Își ia numele de la reprezentarea sa grafică a unei litere C foarte decorate. Aceasta este asemănătoare cu detaliile fine ale copacului Pitagora.

Dimensiunea sa fractală este estimată la 2 (conține seturi deschise), iar granița are o dimensiune de 1.9340.

Construcția IFS

La folosirea unui sistem de funcții iterate (IFS, sau mai degrabă metoda IFS a jocului haosului) construcția curbei C este mai ușoară. Este nevoie de un set de două reguli: două puncte într-un plan (translatorii), fiecare asociat cu un factor de scară de . Prima regulă este rotația la 45 de grade, iar a doua rotația la -45 de grade. Setul va itera un punct (x, y) prin alegerea aleatoare a oricare două reguli și folosirea parametrilor asociați cu regula de scalare / rotație și translatare a punctului cu o funcție de transformare 2D.

Prin formule:

de la un set de puncte inițiale .

Reprezentare în sistem Lindenmayer

Alfabet: F

Constante: +, –

Axioma: F

Reguli: F -> +F–F+

În care unghiul de întoarcere este de 45 de grade.

Fig. 2.21 Primele 9 Generații ale Curbei Levy C

2.8.2.4 Triunghiul Sierpinski

Triunghiul Sierpinski (cunoscut și ca garnitura Sierpinski sau sita Sierpinski) este un fractal cu forma generală de triunghi echilateral, divizat recursiv în triunghiuri echilaterale mai mici. Original a fost construit ca o curbă, și este unul din exemplele de seturi autosimilare. Este denumit după matematicianul polonez Waclaw Sierpinski, dar a apărut ca tipar decorativ cu multe secole în urma lucrării acestuia.

Construire

Există mai multe modalități de a construi triunghiul Sierpinski.

Prin ștergere de triunghiuri, triunghiul Sierpinski poate fi construit ca un triunghi echilateral prin ștergerea repetată a subseturilor triunghiulare.

Se începe cu un triunghi echilateral.

Se divide în patru triunghiuri echilaterale mai mici și se șterge cel din mijloc.

Se repetă pasul 2 pentru fiecare din triunghiurile rămase.

Fiecare triunghi eliminat este din punct de vedere topologic un set deschis. Acest proces de eliminare recursivă a triunghiurilor este un exemplu de regulă de subdiviziune finită.

Proprietăți

Pentru numărul întreg al dimensiunii d, la dublarea unei laturi dintr-un obiect, 2d copii sunt create. (exemplu 2 copii pentru obiecte unidimensionale, 4 copii pentru obiecte bidimensionale, etc). Pentru triunghiul Sierpinski, la dublarea laturii se creează 3 copii ale acestuia. Așadar, triunghiul Sierpinski are o dimensiune fractală de , care provine de la rezolvarea ecuației 2d = 3 pentru d.

Aria triunghiului Sierpinski tinde la 0. Aria rămasă după fiecare iterație este clar 3/4 din aria inițială, deci pentru un număr infinit de iterații va rezulta o arie cu valoarea 0.

Punctele triunghiului Sierpinski au o caracterizare simplă în coordonate Barycentrice. Dacă un punct de coordonate (0.u1u2u3…, 0.v1v2v3…, 0.w1w2w3…) este exprimat în numere binare, atunci punctul este în triunghiul Sierpinski numai și numai dacă ui + vi + wi = 1 pentru toți i.

Reprezentare în sistem Lindenmayer

Alfabet: X

Constante: F, +, –

Axioma: FXF++FF++FF

Reguli: X -> ++FXF–FXF–FXF++

În care unghiul de întoarcere este de 60 de grade.

Fig. 2.22 Primele 5 Generații ale Triunghiului Sierpinski

Curba Vârf de Săgeată Sierpinski

Curba Sierpinski vârf de săgeată este o curbă fractală asemănătoare ca formă și cu limită identică cu triunghiul Sierpinski.

Aceasta arată că triunghiul Sierpinski poate fi construit ca o curbă în plan. Este format prin modificarea repetată a curbelor mai simple, analog cu construcția fulgului Koch.

Se începe cu o singură linie.

Se înlocuiește repetat fiecare linie din curbă cu 3 linii mai scurte, cu un unghi de 120 de grade între două segmente consecutive, iar primul și ultimul segment din linie sunt paralele, respectiv la un unghi de 60 de grade cu segmentul original.

Aceasta desenează un triunghi echilateral cu găuri triunghiulare la intervale egale. Punctul de terminare al curbei este mereu același.

Reprezentare în sistem Lindenmayer

Alfabet: X

Constante: F, +, –

Axioma: YF

Reguli: X -> YF+XF+Y; Y -> XF-YF-X

În care unghiul de întoarcere este de 60 de grade.

Fig. 2.23 Primele 8 Generații ale Curbei Vârf de Săgeată Sierpinski

2.8.2.5 Curba Peano

În geometrie, curba Peano este primul exemplu de curbe umplutoare de spațiu descoperite, descoperită de Giuseppe Peano în 1980. Curba lui Peano este densă în pătratul unitate și a fost folosită de Peano pentru a construi o funcție continuă de la intervalul unitate la pătratul unitate, motivat de rezultatele anterioare ale lui Georg Cantor.

Construcție

Curba Peano poate fi construită dintr-o serie de pași, unde al i-lea pas construiește un set Si de pătrate și o secvență Pi de centre de pătrate din setul și secvența de la pasul anterior. Considerăm cazul de bază S0 care constă dintr-un singur pătrat unitate și P0 este o secvență de un singur element ce reprezintă punctul central.

La fiecare pas i, fiecare pătrat s din Si-1 este partiționat în 9 pătrate mai mici de dimensiuni egale, pentru care punctul central c este înlocuit de subsecvențe învecinate ale centrelor celor 9 pătrate mai mici. Această secvență este formată prin gruparea celor 9 pătrate mai mici în 3 coloane, ordonând centrele învecinate în fiecare coloană, apoi ordonând coloanele de la o parte a pătratului la cealaltă, în așa fel încât distanța dintre fiecare pereche de puncte consecutivă din subsecvență este egală cu lungimea laturii pătratelor mai mici. Există 4 astfel de ordonări posibile:

trei centre din stânga de jos în sus, trei centre din mijloc de sus în jos, și trei centre din dreapta de jos în sus

trei centre din dreapta de jos în sus, trei centre din mijloc de sus în jos, și trei centre din stânga de jos în sus

trei centre din stânga de sus în jos, trei centre din mijloc de jos în sus, și trei centre din dreapta de sus în jos

trei centre din dreapta de sus în jos, trei centre din mijloc de jos în sus, și trei centre din stânga de sus în jos

Între aceste 4 ordonări, cea pentru s este aleasă în așa mod încât distanța între primul punct al ordonării și predecesorii săi din Pi să fie egală cu lungimea laturii pătratelor mai mici. Dacă c a fost primul punct în această ordonare, atunci prima dintre aceste 4 ordonări este aleasă pentru cele nouă centre care înlocuiesc c.

Curba Peano însăși este limita curbelor din secvența de centre de pătrate, întrucât i tinde la infinit.

Variante

În toate definițiile curbei Peano, este posibilă executarea unora sau a câtorva pași prin transformarea centrelor fiecărei linii de 3 pătrate astfel încât să fie continuă, în locul centrelor fiecărei coloane de pătrate. Aceste alegeri pot duce la mai multe variante ale curbei Peano.

Curba Hilbert este o variantă mai simplă a aceleiași idei, bazată pe subdivizarea pătratelor în 4 pătrate mai mici, decât în 9.

Reprezentare în sistem Lindenmayer

Alfabet: L, R

Constante: F, +, –

Axioma: L

Reguli: L -> +RF-LFL-FR+; R -> -LF+RFR+FL-

În care unghiul de întoarcere este de 90 de grade.

Fig. 2.24 Primele 5 Generații ale Curbei Peano

2.8.2.6 Curba Hilbert

Curba Hilbert este o curbă fractală umplutoare de spațiu, continuă descrisă prima oară de matematicianul german David Hilbert in 1891 ca o variantă a curbelor umplutoare de spațiu descoperite de Giuseppe Peano.

Ca toate curbele fractale, dimensiunea sa fractală este 2, mai exact imaginea sa e pătratul unitate, a cărui dimensiune este 2 în orice definiție a dimensiunii; grafului lui este un set compact homeomorfic pentru intervalul unitate închis, cu dimensiunea Hausdorff 2.

Hn este a n-a aproximație pentru limita curbei. Lungimea Euclidiană a lui Hn este , adică crește exponențial cu n, în timp ce rămâne în granița unui pătrat cu arie finită.

Aplicații și algoritmi de mapare

Atât curba Hilbert, cât și aproximările ei discrete sunt folositoare pentru ca oferă o mapare între spațiul uni și bi dimensional care conservă localitatea destul de bine. Dacă (x, y) sunt coordonatele unui punct din interiorul pătratului unitate și d este distanța pe lângă curbă până în punctul respectiv, atunci punctele care au valori apropiate d, au de asemenea valori apropiate (x, y). Conversia nu este însă mereu adevărată. Vor exista câteodată puncte în care coordonatele (x, y) sunt aproape, dar distanțele lor d sunt la distanță, așa cum e inevitabil la maparea unui spațiu 2D la 1D.

Datorită acestei proprietăți de localitate, curba lui Hilbert este des folosită în știința calculatoarelor. De exemplu, gama de adrese IP folosite de calculatoare poate fi mapată într-o imagine folosind curba Hilbert. Codul pentru generarea imaginii ar mapa de la 2D la 1D pentru găsirea culorii fiecărui pixel, iar curba Hilbert este folosită câteodată deoarece păstrează adresele IP apropiate una de alta în imagine. O fotografie fără culori poate fi convertită într-o imagine alb-negru cu valorile rămase de la fiecare pixel adăugate la pixelul următor pe curba Hilbert. Codul pentru aceasta va mapa de la 1D la 2D, iar curba Hilbert e folosită câteodată pentru că nu creează tipare care distrag atenția ce ar putea fi vizibile cu ochiul liber dacă ordinea ar fi simplu de la stânga la dreapta. Curbele Hilbert în dimensiuni mai mari sunt o instanță a generalizării codurilor Grey și sunt câteodată folosite pentru scopuri similare, pentru motive similare. Pentru baze de date multidimensionale, ordinea Hilbert a fost propusă în locul ordinii Z, având comportament mai bun de prezervare a localității. De exemplu, curba Hilbert este folosită pentru compresia și accelerarea indecșilor R-tree. Au fost folosite și pentru compresia depozitelor de date.

Este posibilă implementarea eficientă a curbelor Hilbert chiar și atunci când spațiul de date nu formează un pătrat. Mai mult, există diverse posibilități de generalizare a curbelor Hilbert la dimensiuni mai mari.

Reprezentare în sistem Lindenmayer

Alfabet: X, Y

Constante: F, +, –

Axioma: X

Reguli: X -> XFYFX+F+YFXFY-F-XFYFX; Y -> YFXFY-F-XFYFX+F+YFXFY

În care unghiul de întoarcere este de 90 de grade.

Fig. 2.25 Primele 7 Generații ale Curbei Hilbert

2.8.2.7 Curba Moore

Curba Moore este o curbă fractală umplutoare de spațiu, variantă a curbei Hilbert. Mai precis, este versiunea buclată a curbei Hilbert și poate fi văzută ca o uniune de patru copii de curbe Hilbert combinate astfel încât punctele din capete să coincidă. Având în vedere că este o curbă umplutoare de spațiu, dimensiunea fractală a acesteia este 2.

Reprezentare în sistem Lindenmayer

Alfabet: L, R

Constante: F, +, –

Axioma: LFL-F-LFL

Reguli: L -> +RF-LFL-FR+; R -> -LF+RFR+FL-

În care unghiul de întoarcere este de 90 de grade.

Fig. 2.26 Primele 5 Generații ale Curbei Moore

2.8.2.8 Curba Sierpinski

Curba Sierpinski este o curba fractală, umplutoare de spațiu, închisă, descoperită de Waclaw Sierpinski, care în limita umple complet pătratul unitate. Ca toate curbele umplutoare de spațiu are o dimensiune fractală de 2.

Lungimea Euclidiană este de

adică crește exponențial cu n peste orice limită, unde limita pentru a ariei închise de Sn este 5/12 a pătratului.

Utilizări

Curba este mai folositoare în diverse aplicații practice, fiind mai simetrică decât alte curbe umplutoare de spațiu studiate. De exemplu, este folosită pentru construcția rapidă a unei construcții rapide a unei aproximări pentru soluția problemei vânzătorului ambulant (care cere cea mai scurtă secvența a unui set de puncte dat): euristica este simpla vizitare a punctelor în aceeași secvență în care apar în curba Sierpinski. Pentru aceasta, sunt necesari doi pași: în primul rând se calculează o imagine inversă a fiecărui punct de vizitat, apoi se ordonează valorile. Această idee a fost folosită pentru construirea sistemelor de rute pentru vehicule comerciale pe baza a numai cardurilor din Rolodex.

O curbă umplutoare de spațiu este o hartă continuă a intervalului unitate pe un pătrat unitate și astfel o (pseudo) inversare mapează pătratul unitate la intervalul unitate. Un mod de construire a pseudo-inversului este următorul. Fie colțul din stânga jos (0, 0) care corespunde la 0.0 (și 1.0). Apoi colțul din stânga sus (0, 1) trebuie să corespundă la 0.25, colțul din dreapta sus (1, 1) la 0.50, iar colțul din dreapta jos (1, 0) la 0.75. Harta inversă a punctelor din interior sunt calculate, profitând de structura recursivă a curbei.

Reprezentare în sistem Lindenmayer

Alfabet: X

Constante: F, +, –

Axioma: F+XF+F+XF

Reguli: X -> XF-F+F-XF+F+XF-F+F-X

În care unghiul de întoarcere este de 90 de grade.

Fig. 2.27 Primele 5 Generații ale Curbei Sierpinski

2.8.2.9 Curba Gosper

Curba Gosper, cunoscută și sub numele de curba Peano-Gosper, denumită după Bill Gosper, cunoscută și ca flowsnake este o curbă umplutoare de spațiu. Construcția fractalului este asemănătoare cu construcția curbei Dragon și a curbei Hilbert.

Proprietăți

Spațiul umplut de curbă este denumit și insula Gosper. Insula Gosper poate fi teselată. 7 copii ale insulei Gosper pot fi unite pentru a obține o formă similară, dar scalată cu un factor de în toate dimensiunile. Prin construirea acestei teselări, obținem următoarea generație a curbei Gosper. Curba poate tesela tot planul de care aparține și în același timp ea însăși umple planul.

Reprezentare în sistem Lindenmayer

Alfabet: X, Y

Constante: F, +, –

Axioma: FX

Reguli: X -> X+YF++YF-FX–FXFX-YF+; Y -> -FX+YFYF++YF+FX–FX-Y

În care unghiul de întoarcere este de 60 de grade.

Fig. 2.28 Primele 5 Generații ale Curbei Gosper

Sisteme Distribuite

Un sistem distribuit este un sistem software în care componentele conectate într-o rețea de calculatoare comunică unele cu altele și își coordonează acțiunile trimițând mesaje.[22] Componentele interacționează cu un scop comun.

Caracteristici comune ale unui sistem distribuit sunt:

concurența componentelor

lipsa unui ceas global

căderi independente ale sistemului[22]

Un program software care rulează într-un sistem distribuit se numește program distribuit, iar programarea distribuită este procesul de scriere pentru astfel de programe.[23] Există alternative pentru trimiterea mesajelor, cum ar fi conectori RPC sau cozi de mesaje. Un scop important al sistemelor distribuite este transparența locală.

Calculul distribuit se poate referi, pe lângă sisteme distribuite, și la folosirea acestora pentru a rezolva probleme de calcul. În calculul distribuit, o problemă este divizată în mai multe task-uri, fiecare fiind rezolvat de unul sau mai multe calculatoare care comunică prin trimiterea de mesaje.

Termenul de distribuit a făcut inițial referire la rețele de calculatoare distribuite fizic într-o zonă geografică. Astăzi termenul este folosit pentru procesele autonome care rulează pe același calculator și interacționează prin mesaje. Următoarele proprietăți sunt cele mai des întâlnite:

există mai multe entități autonome, fiecare cu memorie proprie[24]

entitățile comunică prin mesaje[25]

Entitățile computaționale mai poartă și denumirea de calculatoare sau noduri.

Un sistem distribuit are un scop comun, cum ar fi rezolvarea unei probleme complexe. Există și posibilitatea ca fiecare calculator să aibă nevoi individuale, iar scopul întregului sistem distribuit devine coordonarea resurselor partajate sau furnizarea serviciilor de comunicație către utilizatori.

Alte caracteristici comune pentru sisteme distribuite includ:

toleranța la erori pentru calculatoare individuale

structura sistemului (topologia, latența, numărul de calculatoare) nu este cunoscut, acesta putând fi constituit din diferite tipuri de calculatoare și legături, putându-se schimba în timpul execuției unui program distribuit.

fiecare calculator are o viziune limitată și incompletă asupra întregului sistem; fiecare calculator poate cunoaște doar o parte a intrării.

3.1 Istoric

Folosirea proceselor concurente care comunică prin trimiterea de mesaje își are rădăcinile în arhitecturi de sisteme de operare studiate în anii 1960. Primele sisteme distribuite de uz general au fost LAN-urile, de exemplu Ethernet, inventat în 1970. ARPANET, predecesorul Internet-ului, a fost introdus în anii 1960, iar e-mail-ul ARPANET a apărut în anii 1970. E-mail-ul a devenit cea mai de succes aplicație a ARPANET, fiind probabil cel mai vechi exemplu de sistem distribuit pe scară largă. Alte exemple de rețele de calculatoare includ Usenet și FidoNet, ambele folosite pentru suportul sistemelor distribuite. Studiul sistemelor distribuite a devenit o ramură în știința calculatoarelor la sfârșitul anilor 1970 și începutul anilor 1980. Prima conferință, "Simpozion în Principiile Calculului Distribuit" datează în 1982, iar echivalentul European, "Simpozionul Internațional în Calculul Distribuit" a fost ținut in 1985.

3.2 Aplicabilitate

Principalele motive pentru folosirea unui sistem distribuit includ:

Natura în care este construită aplicația poate necesita utilizarea unei rețele care conectează mai multe calculatoare: de exemplu, datele produse într-o locație, necesare în altă locație.

Există cazuri în care folosirea unui calculator este posibilă, dar folosirea unui sistem distribuit este mai benefică din diverse motive practice. De exemplu, poate fi mai eficientă din punct de vedere al costului folosirea mai multor calculatoare cu performanță scăzută decât a unui singur calculator de ultimă generație. Un sistem distribuit poate fi mai fiabil decât un singur calculator, încât nu există un punct unic de cădere. Mai mult, un sistem distribuit poate fi mai ușor de extins decât un sistem monolitic.

Sistemele distribuite sunt folosite într-o varietate de domenii, incluzând:

telecomunicații

rețele de telefonie

rețele de calculatoare – Internet

rețele wireless cu senzori

algoritmi de rutare

aplicații în rețea

world wide web și rețele punct la punct

jocuri MMO și comunitățile de realități virtuale

baze de date distribuite și sisteme distribuite pentru management-ul bazelor de date

sisteme de fișiere în rețea

procesarea controlului în timp real

sisteme de control al avioanelor

sisteme de control industriale

calcul paralel

calcul științific

generarea distribuită în grafica pe calculator

3.3 Arhitecturi

Există diverse arhitecturi hardware și software folosite pentru sistemele distribuite. La un nivel jos, este necesară interconectarea mai multor procesoare cu un fel de rețea indiferent că rețeaua respectivă este printată pe o placă de circuit sau creată din dispozitive și cabluri cuplate. La un nivel mai înalt, este necesară interconectarea proceselor care rulează pe procesoarele respective cu ajutorul unui sistem de comunicație.

Programarea distribuită se încadrează în mod obișnuit într-una din următoarele categorii de arhitecturi: server-client, arhitectura pe 3 straturi, arhitectură pe n straturi, obiecte distribuite, cuplare ușoară sau cuplare strânsă.

server-client

codul client contactează serverul pentru date și apoi formatează și afișează rezultatele obținute

arhitectură pe 3 straturi

arhitectura pe 3 nivele transferă inteligența clientului într-un nivel de mijloc, pentru a putea fi folosiți clienți fără stare. Acest lucru simplifică desfășrurarea aplicației. În această categorie se încadrează majoritatea aplicațiilor web

arhitectura pe n straturi

se referă la aplicațiile web care trimit cererile unor servicii specializate. Acest tip de aplicații sunt responsabile pentru succesul serverelor de aplicații

cuplare strânsă

se referă la mașini care lucrează în strânsă legătură împreună, executând un proces partajat în paralel. Task-ul este divizat în părți pentru fiecare nod, apoi reunit pentru a crea rezultatul final

punct-la-punct

nu există o mașină specială care să administreze rețeaua sau să furnizeze servicii. Toate responsabilitățile sunt divizate uniform între mașini care pot fi clienți sau servere

bazate pe spațiu

se referă la o infrastructură care creează iluzia, prin virtualizare, a unui singur spațiu de adrese. Datele sunt replicate transparent în conformitate cu nevoile aplicației. Este realizată decuplarea în timp, spațiu și referință

Un alt aspect de bază pentru arhitecturile sistemelor distribuite este metoda de comunicație si coordonare a lucrului între procesele concurente. Procesele pot comunica, prin protocoale de pasare a mesajelor, direct unele cu altele, într-o manieră master/slave. Alternativ, o arhitectură axată în jurul unei baze de date poate facilita calculul distribuit fără comunicația interprocese, numai prin utilizarea unei baze de date comune.

3.4 Fundamente Teoretice

3.4.1 Modele

Multe din task-urile care am dori să le automatizăm cu ajutorul calculatoarelor sunt de tipul întrebare-răspuns: dorim să punem o întrebare, iar calculatorul va produce un răspuns. În teoria științei calculatoarelor asemenea task-uri sunt numite probleme computaționale. Formal, o problemă computațională constă în instanțe împreună cu soluții pentru fiecare instanță. Instanțele sunt întrebările care le punem, iar soluțiile sunt răspunsurile dorite la întrebările respective.

Știința calculatoarelor teoretică încearcă să înțeleagă care probleme computaționale pot fi rezolvate de un calculator și cât de eficient. Tradițional, o problemă poate fi rezolvată de un calculator numai dacă putem proiecta un algoritm care să producă o soluție corectă pentru oricare instanță. Algoritmul poate fi implementat ca un program software care rulează în mod normal: programul citește o instanță a problemei din intrare, face anumite calcule, apoi produce o soluție la ieșire.

Domeniul calculului concurent sau distribuit studiază întrebări similare ori pentru mai multe calculatoare, ori pentru un singur calculator care execută procese care interacționează. Ne putem întreba ce probleme computaționale pot fi rezolvate eficient în acest mod. Nu putem însă preciza ce însemnă mai exact rezolvarea problemei în cazul sistemelor distribuite sau concurente: de exemplu, care este task-ul din algoritm și care este echivalentul lui pentru un sistem distribuit?

Cu toate că ne putem ridica probleme pentru mai multe calculatoare, task-urile rulate în același calculator pot prezenta probleme asemănătoare.

Algoritmi paraleli în memoria partajată

toate calculatoarele au acces la o memorie partajată. Designer-ul de algoritm alege programul executat de fiecare calculator

unul din modele teoretice folosite este mașinile cu acces aleator paralel. Modelul clasic presupune acces sincron la memoria partajata

un model care este mai apropiat de comportamentul mașinilor multiprocesor este cel care folosește memorie partajată asincronă.

Algoritmi paraleli în modelul de trimitere a mesajelor

designer-ul de algoritm alege structura rețelei, dar și programul executat de fiecare calculator

sunt folosite modele precum circuite booleene și rețele de sortare. Un circuit boolean poate fi văzut ca o rețea de calculatoare: fiecare poartă este un calculator care rulează un program extrem de simplu. În mod similar, o rețea de sortare poate fi văzută ca o rețea de calculatoare: fiecare comparator este un calculator

Algoritmi distribuiți în trimiterea de mesaje

designer-ul de algoritmi alege numai programul software. Toate calculatoarele rulează același program. Sistemul trebuie să funcționeze corect indiferent de structura rețelei

un model comun este graful cu o stare finită pe fiecare nod

În cazul algoritmilor distribuiți, problemele computaționale sunt de obicei legate de grafuri. De obicei graful care descrie structura rețelei de calculatoare este instanța problemei.

3.4.2 Exemplu

Se consideră problema de găsire a culorii unui graf dat, G. Diferite domenii pot aborda problema diferit:

Algoritmi Centralizați

graful G este codificat ca un șir de caractere, iar șirul este dat ca intrare pentru un calculator. Programul caută culoarea grafului, codează culoarea ca șir de caractere și trimite rezultatul.

Algoritmi Paraleli

graful G este din nou codificat ca un șir de caractere. Mai multe calculatoare pot accesa același șir de caractere în paralel. Fiecare calculator se poate concentra pe o parte a grafului, căutând culoarea pentru acea zonă.

este pus accentul pe calculul performant care exploatează puterea de procesare a mai multor calculatoare în paralel.

Algoritmi Distribuiți

graful G este structura rețelei de calculatoare. Există câte un calculator pentru fiecare nod al grafului G și câte o legătură de comunicare pentru fiecare muchie a lui G. Inițial, fiecare calculator cunoaște numai vecinii imediați din graful G. Calculatoarele schimbă mesaje pentru a cunoaște structura lui G. Fiecare calculator produce propria culoare ca ieșire.

principala centrare constă în coordonarea operațiilor unui sistem distribuit arbitrar.

În timp ce domeniul programării paralele se concentrează pe alte obiective față de domeniul programării distribuite, există foarte multe interacțiuni între cele două. De exemplu, algoritmul Cole-Vishkin de colorare a grafurilor a fost prezentat inițial ca un algoritm paralel, dar aceeași tehnică poate fi folosită în mod direct ca un algoritm distribuit.

Mai mult, un algoritm paralel poate fi implementat ori ca un algoritm într-un sistem paralel (care folosește memorie partajată) ori într-un sistem distribuit (care folosește trimiterea de mesaje). Tradițional, granițele dintre algoritmi paraleli și distribuiți nu coincid cu granița între sisteme paralele și distribuite.

3.4.3 Măsuri de complexitate

În algoritmi paraleli există o altă resursă înafară de timp și spațiu, și anume numărul de calculatoare. Într-adevăr, există un compromis între timpul de execuție și numărul de calculatoare: problema poate fi soluționată într-un timp mai scurt dacă există mai multe calculatoare conectate în paralel care pot rezolva problema.

În analiza algoritmilor distribuiți operațiile de comunicare sunt mai importante decât pașii de comunicare. Cel mai simplu exemplu de sistem distribuit este posibil un sistem asincron unde toate nodurile operează într-o manieră lockstep. În cadrul fiecărei runde de comunicații, toate nodurile paralele primesc ultimul mesaj de la vecinii lor, fac o prelucrare locală arbitrară, apoi trimit noi mesaje către vecinii lor. Într-un astfel de sistem, una din măsurile de complexitate centrale este numărul de runde de comunicații sincrone necesare pentru rezolvarea task-ului.

Această măsură de complexitate este strâns legată de diametrul rețelei. Fie D diametrul rețelei. Pe de o parte, orice problemă computațională poate fi rezolvată într-un sistem sincron distribuit în aproximativ 2D runde de comunicare. Preluarea informațiilor dintr-o locație (D runde), soluționarea problemei, și informarea celorlalte noduri asupra soluției (D runde).

Pe de altă parte, dacă timpul de rulare al algoritmului este mult mai mic decât D runde de comunicație, atunci nodurile din rețea trebuie să producă rezultatul fără a avea posibilitatea obținerii informațiilor legate de părți distante din rețea. Cu alte cuvinte, nodurile trebuie să ia decizii globale consistente bazate pe informații disponibile doar de la vecinii lor apropiați. Mulți algoritmi distribuiți au un timp de rulare mult mai mic decât D runde. Una din principalele obiective în domeniu este cunoașterea problemelor care pot fi soluționate de asemenea algoritmi.

Alte măsuri comune folosite sunt numărul totali de biți transmiși în rețea (complexitatea de comunicare).

3.4.4 Alte probleme

Problemele de calcul tradiționale au următoarea perspectivă: dacă punem o întrebare, un calculator (sau un sistem distribuit) procesează respectiva întrebare pentru un anumit timp, apoi produce un răspuns și se oprește. Cu toate acestea, există și situații în care nu am vrea ca sistemul să se oprească vreodată. Exemple de astfel de probleme includ: problema filozofilor la cină, și alte probleme de excluziune mutuală. În astfel de cazuri, sistemul distribuit trebuie să coordoneze în mod continuu resursele partajate folosite, astfel încât să fie evitate conflicte sau deadlock-uri.

Există și provocări fundamentale care sunt unice sistemelor distribuite, cum ar fi provocările legate de toleranța la erori, probleme de aprobare unanimă, și auto-stabilizarea. Multe cercetări se concentrează pe înțelegerea naturii asincrone a unui sistem distribuit:

sincronizatorii pot fi folosiți să ruleze algoritmi sincroni în sisteme asincrone

ceasurile logice furnizează o ordine cazuală a evenimentelor "happened-before"

algoritmii de sincronizare a ceasului furnizează ștampile de timp fizice consistente la nivel global

3.4.5 Proprietățile sistemelor distribuite

Până acum, concentrarea a fost pe un sistem distribuit care rezolvă o anumită problemă. Cercetarea complementară reprezintă studiul de proprietăți al unui sistem distribuit dat.

Problema opririi este un exemplu analog din domeniul calculului centralizat: avem un program și un task care decide dacă acesta se oprește sau rulează la infinit. Problema opririi este indecidabilă pentru cazul general, iar înțelegerea naturală a comportamentului unei rețele de calculatoare este cel puțin la fel de grea ca și înțelegerea comportamentului unui singur calculator.

Cu toate acestea, există multe cazuri care sunt decidabile. În special, este posibilă determinarea comportamentului unei rețele de mașini cu stări finite. Un exemplu poate fi dacă o anume rețea de mașini cu stări finite care interacționează poate ajunge la deadlock. Această problemă este decidabilă, dar este probabil să nu existe un algoritm eficient (de orice tip) care să rezolve problema pentru rețele mari.

3.5 Alegerea Coordonatorului

Alegerea coordonatorului (numită câteodată și alegerea liderului) este metoda prin care se desemnează un singur proces ca și organizatorul unui task distribuit între mai multe calculatoare (sau noduri). Înainte de începerea task-ului, niciun nod nu cunoaște cine va fi coordonatorul task-ului, și nici nu vor putea comunica cu coordonatorul curent. După ce a fost rulat un algoritm de alegere a coordonatorului, fiecare nod din rețea va recunoaște un anumit nod ca fiind coordonatorul task-ului.

Nodurile din rețea comunică între ele pentru a decide cine va intra în starea de "coordonator". Pentru aceasta, este nevoie de o metodă care distruge simetria dintre ele. De exemplu, dacă fiecare nod are identități unice și comparabile, atunci nodurile își pot compara identitățile și pot decide ca nodul cu cea mai mare identitate este coordonatorul.

Definiția acestei probleme este adesea atribuită lui LeLann, care o formalizează ca o metodă de creare a unui nou token într-o rețea inelară în care token-ul a fost pierdut.

Algoritmii de alegere a coordonatorului sunt proiectați în așa fel încât să fie economi în funcție de numărul de biți transmiși și timpul necesar transmiterii acestora. Algoritmul sugerat de Gallager, Humblet și Spira pentru grafuri general neorientate a avut un impact puternic în proiectarea algoritmilor distribuiți în general, câștigând premiul Dijkstra pentru o lucrare importantă în calculul distribuit.

Au fost sugerați mulți alți algoritmi pentru diverse grafuri de rețea, cum ar fi inele neorientate, inele unidirecționale, grafuri complete, grid-uri, grafuri Euler orientate, precum și altele. O metodă generală care decuplează problema familiei de grafuri de proiectarea algoritmului de alegerea coordonatorului, a fost sugerată de Korach, Kutten și Moran.

Pentru a fi coordonate, sistemele distribuite adoptă conceptul de coordonatori. Problema alegerii coordonatorului este alegerea unui proces dintr-un grup de procese pe diferite procesoare într-un sistem distribuit care să îndeplinească rolul de coordonator central. Există mai mulți astfel de algoritmi pentru rezolvarea problemei.

Algoritmul Bully

La folosirea algoritmului Bully, toate procesele trimit mesaje coordonatorului curent. Dacă nu există un răspuns într-un anumit interval, procesul încearcă să se auto-aleagă ca lider.

Algoritmul lui Chang și Roberts

Algoritmul lui Chang și Roberts (sau "Algoritmul Inelelor") este un algoritm de alegere pe baza inelelor, folosit pentru găsirea procesului cu cel mai mare număr unic de identificare.

3.6 Aplicabilitatea Sistemelor Distribuite în Android. Offloading

Datele necesare pentru procesarea unui fractal la orice generație au o complexitate care crește exponențial cu numărul generației. Acest lucru nu pune o problemă pe dispozitivele Android la generațiile inițiale ale oricărui fractal, dar poate încetini considerabil aplicația sau generarea fractalilor pentru generații ulterioare.

Așadar, potențialul unei aplicații de generat fractali este constrâns de resursele de calcul ale unui dispozitiv Android, cum ar fi procesorul, memoria și capacitatea de stocare care sunt toate limitate în comparație cu cele ale unui calculator. Pentru a trece peste aceste limitări, o abordare comună folosită azi comercial este Software as a Service (SaaS), în care aplicațiile mobile (care rulează nativ sau în web) sunt proiectate să colaboreze cu un server web. Cu toate că această abordare permite serverelor cu putere mare de procesare sa proceseze task-uri complexe în fundal, dezvoltatorii trebuie să implementeze un software pentru partea de server și să găzduiască servere ei însăși. Costurile dezvoltării și mentenanței unei perechi server-client este cu mult mai mare decât costul unei aplicații standalone, cost care limitează resursele dezvoltatorilor pentru crearea și dezvoltarea unor noi aplicații pe baza aceluiași model.

Ideal, dezvoltatorii ar trebui să se concentreze pe dezvoltarea aplicațiilor client fără să țină cont de mecanismul de offloading. Componentele care necesită putere mare de procesare ar trebui să fie automate și trimise în mod transparent la un server gazdă, ce este menținut de un furnizor separat. Implementarea care este cel mai aproape de o astfel de viziune este cyber-furajarea, a cărui scop este trimiterea task-urilor complexe dintr-o aplicație mobilă către un surogat prin WiFi. Un surogat poate fi un calculator din apropiere sau chiar un alt dispozitiv mobil cu putere de procesare nefolosită mai mare decât al dispozitivului care rulează aplicația. Cu toate că cyber-furajarea a fost introdusă de mai mult de un deceniu, și a atras interesele cercetătorilor, conceptul nu a fost încă pus în practică. Un număr de posibile obstacole includ: lipsa calculatoarelor surogat, lipsa unui sistem de securitate atât pentru client, cât si pentru surogat, dificultatea de a decide trimiterea optimă a task-urilor, necesitatea de a modifica aplicația și de a încorpora mecanismul de offloading în sistemul de operare a clientului.[26]

4. Descrierea Aplicației

Proiectul "Sistem Distribuit pentru Dispozitive Android" permite generarea și studiul fractalilor pe dispozitivele Android. Acesta este realizat din două părți: o aplicație Android care conține comenzile pentru generarea și customizarea fractalilor și permite vizualizarea acestora și un program server scris în C care rulează pe calculatoare Linux.

Scopul principal al aplicației este reducerea timpului de generare a fractalilor prin trimiterea comenzilor și instrucțiunilor de desenare la unul sau mai multe programe server care se vor ocupa cu procesarea task-urilor complexe, consumatoare de timp.

Fig. 4.1. Fractalii care pot fi Generați Folosind Aplicația

4.1 Aplicația Android

Aplicația Android poate genera fractali definiți în sistem Lindenmayer, selectați dintr-o listă de 60 de fractali predefiniți. Pentru fiecare există o serie de proprietăți ce pot fi modificate pentru obținerea altor versiuni ale aceluiași fractal. Aceștia sunt generați într-un proiect ce facilitează comparația între diverși fractali, dar și între mai multe variante ale aceluiași fractal. Proiectul poate fi salvat ulterior ca fișier imagine.

Aplicația conține trei activități, fiecare cu un scop bine definit.

4.1.1 Activitatea cu Meniul Principal

Prima activitate cu care utilizatorul interacționează este cea care conține meniul principal. Această activitate este setată ca launcher și este primul ecran care apare la deschiderea aplicației.

Această activitate conține 2 butoane: "New Project" și "Connections".

Butonul "New Project" creează un dialog pentru alegerea dimensiunilor unui proiect nou. După introducerea dimensiunilor dorite, și confirmarea acestora, se va deschide o nouă activitate cu un proiect gol.

Butonul "Connections" pornește activitatea de gestionare a conexiunilor.

Fig. 4.2. Activitatea cu Meniul Principal

4.1.2 Dialogul pentru Alegerea Dimensiunilor Proiectului

Acest dialog apare la selectarea butonului "New Project" din activitatea principală și permite introducerea dimensiunilor ce reprezintă lățimea și înălțimea pentru un nou proiect. Dimensiunile introduse sunt în pixeli, iar după confirmare, acestea sunt trimise către activitatea de proiect care folosește dimensiunile respective pentru a crea un nou spațiu de lucru.

Fig. 4.3. Dialogul pentru Alegerea Dimensiunilor Proiectului

4.1.3 Activitatea cu Conexiuni

Aplicația se poate conecta la unul sau mai multe servere pentru reducere timpului necesar pentru generarea fractalilor. Această activitate ajută la gestionarea conexiunilor cu servere C din Linux.

Fig. 4.4. Activitatea pentru Gestionarea Conexiunilor

Prin selectare butonului "Create Connection" se poate crea o nouă conexiune. Conexiunea creată va fi adăugată la lista de conexiuni din activitate. Fiecare conexiune cerută va apărea cu roșu până când aceasta va fi disponibilă, moment în care își va schimba culoarea în verde. Orice conexiune poate fi închisă oricând prin selectarea butonului "Disconnect" din dreptul conexiunii respective. Acționarea butonului va trimite un mesaj la server care va deconecta clientul (aplicația Android care cere deconectarea). După închidere, aceasta va dispărea din listă.

După ce s-au creat sau distrus toate conexiunile dorite, se poate folosi butonul back sau up pentru a reveni în activitatea anterioară, fie aceasta activitatea cu meniul principal, fie activitatea de proiect. Conexiunile active își vor menține starea după părăsirea activității.

4.1.4 Dialogul pentru Conexiuni Noi

Pentru a crea o nouă conexiune, va apărea un dialog în activitatea de gestionare a conexiunilor. Acesta permite introducerea ip-ului pentru serverul cu care se dorește stabilirea unei conexiuni. După introducerea și confirmarea ip-ului, se va trimite o cerere la portul 28288 din server pentru o nouă conexiune.

Fig. 4.5. Dialogul pentru Conexiunea cu Serverul

4.1.5 Activitate de Proiect

Principala activitate din aplicație este cea de proiect, care permite generarea și editarea fractalilor, precum și salvarea rezultatului obținut ca imagine. La pornirea activității este creat un canvas cu dimensiunile pentru lățime și înălțime introduse în dialogul anterior.

Fig. 4.6. Activitatea de Proiect

Pe lângă canvas, activitatea mai conține și o listă cu toți fractalii care pot fi generați. Aceasta poate fi închisă sau deschisă prin selectarea capului de listă "New Fractal". Pentru a genera un fractal, se va selecta acesta din listă. După selectare, acesta va apărea în canvas, cu colțul din stânga sus la coordonatele (0, 0) ale canvasului, având proprietăți implicite. Fractalul poate fi mutat oriunde în canvas prin selectarea și tragerea acestuia.

Fig. 4.7. Adăugarea unui Nou Fractal

După generarea unui fractal, lista de noi fractali va fi închisă, în locul acesteia apărând o listă cu proprietățile fractalului. Pentru fiecare fractal, există o serie de proprietăți implicite, care pot fi observate la generarea acestuia. Orice proprietate poate fi modificată într-o gamă de valori. Pentru a modifica orice proprietate, se pot folosi butoanele de "+" și "-" din dreptul acesteia. Numărul dintre cele două reprezintă valoarea curentă a proprietății.

Pentru a schimba valoarea unei proprietăți cu mai mult de o unitate, se va da click oriunde pe proprietate, înafara butoanelor de incrementare și decrementare, "+", respectiv "-". După această comandă, va fi adăugată la activitate o bară pentru selectarea valorilor. Se va folosi un seek bar pentru a schimba valoarea oriunde în gama definită.

Proprietățile pentru culoare pot fi schimbate prin selectarea culorii de minim și de maxim. Acestea se comportă diferit față de celelalte proprietăți, încât deschid un dialog în care se pot modifica elementele unei culori.

4.1.6 Dialogul pentru Selectarea Culorii

Dialogul pentru selectarea culorii este folosit atât pentru culorile componente ale unui fractal, cât și pentru culoarea de fundal al întregului canvas. Acesta permite selectarea unei culori prin modificarea componentelor acesteia. Se vor modifica valorile pentru alpha, roșu, verde și albastru, componente care pot lua valori între 0 și 255, folosind un seek bar pentru fiecare. Rezultatul poate fi vizualizat într-un View din stânga acestora. După confirmare, culoarea va fi aplicată în locul dorit.

Fig. 4.8. Schimbarea Proprietății de Culoare prin Dialogul de Alegerea Culorii

4.1.7 Meniul pentru Activitatea de Proiect

Activitatea de Proiect conține un meniu cu 4 opțiuni: "View Connections", "Change Background", "Remove Selected Fractal" și "Save Image".

Fig. 4.9. Meniul pentru Activitatea de Proiect

Prima opțiune, "View Connections", permite vizualizarea conexiunilor existente și crearea noilor conexiuni prin deschiderea activității de gestiune a conexiunilor.

A doua opțiune, "Change Background", deschide un dialog pentru selectarea culorii de fundal. Dialogul este descris la punctul 4.1.6. Marginile activității sunt colorate cu o culoare inversă din punct de vedere a valorii componentelor culorii de fundal. Aceeași culoare din margini este folosită și pentru încadrarea fractalului selectat.

A treia opțiune, "Remove Selected Fractal" permite ștergerea fractalului selectat din canvas, dacă există vreun fractal selectat. Această opțiune este definitivă și nu poate fi anulată.

A patra opțiune, "Save Image" permite salvarea canvasului pe care s-au generat fractali într-un fișier imagine. Fișierul va fi salvat în directorul rădăcină al dispozitivului Android cu extensia ".png", cu numele "fractal" urmat de un șir numeric ce reprezintă data și ora curentă.

4.2 Programul Server

Programul server este scris în C și rulează pe calculatoare Linux. Acesta este un program în linie comandă. După rularea acestuia, serverul va aștepta clienți pentru conectare. La începutul rulării, programul va afișa ip-ul calculatorului pe care rulează.

Fig. 4.10. Programul Server Rulat în Ubuntu

4.3 Comunicația Client-Server

Proiectul implementează o arhitectură de tipul client-server. Clienții sunt programele Android care generează fractali și au nevoie de putere de procesare, iar serverele sunt programe în C care rulează pe calculatoare Linux. Între aplicația Android și serverul C se trimit mesaje care conțin informații despre fractali.

După ce minim un client Android este conectat la server, serverul va aștepta șiruri de caractere ce conțin informații despre un fractal, va parsa șirul respectiv și va genera fractalul (mai exact partea din șir corespunzătoare ce descrie fractalul la o generație ulterioară), apoi va trimite rezultatul înapoi la client.

Pentru a putea trimite o parte din șir la fiecare client, aplicație trebuie în primul rând să se asigure că există destule caractere pentru a trimite câte patru părți la fiecare din serverele cu care este conectată. Astfel, aplicația va genera local atâtea generații câte are nevoie pentru a obține un șir destul de lung. Calculul este făcut încât fiecare fir de execuție de pe fiecare server va primi minim 10 caractere.

Se consideră următorul caz: aplicația este conectată la 2 servere, iar fiecare server poate rula 4 fire de execuție, deci sunt necesare în total 2 * 4 = 8 părți ale șirului ce descrie un fractal. Pentru acest exemplu, se va folosi următorul sistem Lindenmayer care descrie curba Levy C:

variabile: F

constante: +, –

axioma: F

reguli: F -> +F–F+

Nu ne interesează momentan alte proprietăți ale fractalului, cum ar fi unghiul de rotație sau lungimea de desenare, întrucât acestea sunt folosite doar la desenarea fractalului, nu și la generarea acestuia.

Se cere obținerea fractalului la generația 10. Teoretic, vor exista 10 iterații locale, începând de la axioma sistemului la care se adaugă cât mai multe reguli posibile. Pentru a ne folosi de procesarea distribuită în acest caz, trebuie să trimitem 8 șiruri diferite de procesare. Se poate observa că axioma (șirul de caractere inițial) "F" conține un singur caracter, deci nu poate fi împărțit la 8 fire de execuție diferite. Pentru modul în care este implementată aplicația, se cer minim 10 caractere trimise pentru fiecare fir de execuție. Deci avem nevoie în total de un șir cu minim 2 * 4 * 10 = 80 de caractere.

Pentru a obține prima generație cu minim 80 de caractere, se va itera local șirul până la o generație corespunzătoare. Altfel, se obțin următoarele șiruri de caractere local:

n = 0: F

n = 1: +F–F+

n = 2: ++F–F+–+F–F++

n = 3: +++F–F+–+F–F++–++F–F+–+F–F+++

n = 4: ++++F–F+–+F–F++–++F–F+–+F–F+++–+++F–F+–+F–F++–++F–F+–+F–F++++

n = 5: +++++F–F+–+F–F++–++F–F+–+F–F+++–+++F–F+–+F–F++–++F–F+–+F–F++++–++++F–F+–+F–F++–++F–F+–+F–F+++–+++F–F+–+F–F++–++F–F+–+F–F+++++

Deci prima generație obținută care conține mai mult de 80 de caractere este a 5-a generație, cu 156 de caractere. Acestea vor trebui împărțite la 8 fire de execuție, deci fiecare fir de execuție va conține minim 156 / 8 = 19 caractere. Pentru că împărțirea șirului exact la 8 are un rezultat număr real, 19.5, se va lua partea întreagă pentru primele șiruri de caractere, iar la ultimul șir se va trimite restul de caractere rămase. Deci 7 * 19 = 133 caractere vor fi trimise primelor 7 fire de execuție, iar restul de 156 – 133 = 23 vor fi trimise la ultimul fir de execuție.

Așadar, șirul de la generația a 5-a va fi împărțit în următorul fel:

+++++F–F+–+F–F++

–++F–F+–+F–F+++

–+++F–F+–+F–F++

–++F–F+–+F–F+++

+–++++F–F+–+F–F

++–++F–F+–+F–F+

++–+++F–F+–+F–F

++–++F–F+–+F–F+++++

În care primele 4 șiruri vor crea câte un fir de execuție pentru primul server, iar ultimele 4 vor crea fire de execuție pe cel de-al doilea server.

Fiecare șir de caractere care descrie o parte din fractal va trebui să conțină, pe lângă șirul care descrie fractalul și alte elemente suplimentare, incluzând un id pentru păstrarea ordinii în care trebuie recompus, numărul generațiilor care au rămas de iterat, dar și regulile cu care fractalul va fi iterat. Pentru primul șir de caractere se va trimite următorul mesaj:

#fl#0#+++++F–F+–+F–F++#5#F@+F–F+#

Se poate observa că în mesaj există mai multe token-uri despărțite prin caracterul "#". Acestea reprezintă următoarele:

fl – faptul că mesajul trimis este un fractal

0 – poziția în șirul final

+++++F–F+–+F–F++ – partea din fractal care trebuie iterată, care devine noua axiomă pentru server

5 – numărul de iterații care au rămas de obținut

F@+F–F+ – singura regulă de producție aplicată, în care caracterul "F" se transformă în "+F–F+"

După primirea mesajului serverul va parsa șirul de caractere primit și va aplica regulile din acesta pe șirul fractal de câte ori este necesar. După obținerea rezultatului dorit, se va trimite un mesaj înapoi la clientul Android, având următoarea structură:

#fl#0#<sir>

unde:

fl – indică faptul că s-a trimis un șir ce descrie un fractal.

0 – indică poziția subșirului în șirul care descrie fractalul

<sir> – este șirul fractal cu instrucțiuni de desenat

Când aplicația primește un șir care este imediat după ultimul șir desenat, îl va desena direct. Primul șir care va fi desenat este șirul cu numărul de ordine 0. Până la primirea acestui șir, se vor pune într-o coadă de așteptare celelalte șiruri. După ce s-a desenat șirul 0 se verifică respectiva coadă de așteptare pentru existența șirului 1. Dacă acesta există, se va desena și se vor face verificări pentru restul șirurilor. Dacă acesta nu există, vor fi puse în coadă toate șirurile primite până la primirea șirului 1. Se va repeta procesul până când vor fi recuperate și desenate toate celelalte șiruri care urmează să fie primite de la servere.

4.4 Etape de Realizare a Sistemului

1. Aplicația inițială

Scopul inițial al proiectului a fost crearea unei aplicații Android pentru generarea fractalilor. Inițial, a fost implementată o aplicație Android care desena fractalii linie cu linie, la primele câteva generații. Acest mod era limitat pentru figuri complexe și greu de modificat pentru implementarea fiecărui fractal.

2. Implementarea unui sistem Lindenmayer

Pentru a generaliza modul de implementare a fractalilor, s-a ales folosirea unui sistem Lindenmayer, care descrie structurile fractale doar prin câteva reguli. Acesta urmează aceleași principii de desenare pentru toți fractalii, iar pentru generarea diferiților fractali nu este necesară decât modificarea axiomei și a regulilor de producție.

3. Opțiuni pentru fractali

Pentru că un fractal poate avea mai multe opțiuni, incluzând lungimea unei linii de desenare sau mărimea unghiului dintre linii, în aplicație a fost adăugate diverse opțiuni pentru a modifica fractalul. Pentru aceeași axiomă și reguli se pot obține acum noi fractali doar prin modificarea proprietăților acestora.

4. Viteza de generare

S-a observat că la generații mai complexe, generarea fractalilor poate dura. Acest lucru se datorează lipsei resurselor, care nu se regăsesc într-un dispozitiv Android. Un calculator ar fi mult mai indicat pentru generarea acestora. Așadar, s-a decis folosirea unui calculator care rulează Ubuntu și implementarea unui program server care să aștepte clienții Android să se conecteze la el și să trimită datele pentru procesarea fractalilor.

A fost implementat un protocol de comunicație între cele două componente capabil de transmiterea tuturor informațiilor. Dar acest lucru nu era de ajuns, întrucât calculatorul server nu era folosit la maxim. Deci, în locul trimiterii tuturor informațiilor pentru un fractal, s-a împărțit șirul care îl descria, în 4 șiruri care vor fi procesate pe fire de execuție diferite în server.

Mai mult, sistemul a fost extins astfel încât aplicația să se poată conecta la mai multe calculatoare server, către care va trimite 4 părți din șirul care descrie fractalul.

Pentru a nu face aplicația neutilizabilă în cazul în care nu există niciun server disponibil dispus să preia task-urile pentru procesare, fractalul va fi generat ca până acum, local.

5. Gestionarea Conexiunilor

Odată cu implementarea claselor care facilitează conexiunea la un server, s-a creat și o activitatea care să le poată gestiona. Aceasta permite crearea unor noi conexiuni cu mai multe servere, în funcție de IP-ul acestora, dar și deconectarea de fiecare server în parte.

6. Salvarea rezultatelor

Proiectul a fost implementat de la început pe un canvas, dar acesta avea dimensiuni fixe și nu permitea customizare. Așadar, a fost introdus în primul rând un dialog pentru setarea dimensiunilor proiectului, apoi o opțiune pentru modificarea culorii de fundal. Acum se pot genera unul sau mai mulți fractali pe un canvas de dimensiuni customizabile.

Dar, acest lucru nu a fost de ajuns și a mai fost introdusă o opțiune care salva starea curentă a canvas-ului într-un fișier imagine. Fișierul este salvat în directorul rădăcină, accesibil utilizatorului, cu un nume evident. Numele fișierului conține cuvântul "fractal", împreună cu data și ora la care a fost generat, dar și cu extensia ".png".

7. Ștergerea Fractalilor

Pentru că proiectul se comportă asemenea unei aplicații de desenat cu entități, s-a introdus și opțiunea ce permite ștergerea unui fractal. La selectarea acestuia, acesta poate fi nu doar mutat, ci și șters.

8. Suportul aplicației pentru ecrane multiple

Pentru că Android este o platformă răspândită pe foarte multe dispozitive, fiecare cu configurație proprie, a fost necesară crearea unui layout care să se adapteze pe mărimile ecranelor tuturor dispozitivelor. Așadar, acolo unde a fost cazul au fost create valori pentru dimensiuni diferite, iar acolo unde simpla modificare a valorilor nu a fost de ajuns, s-a definit un întreg layout care să corespundă și altor mărimi.

Fig. 4.11. Aplicația Rulată pe alt Dispozitiv

Concluzii

Folosirea fractalilor poate ajuta în mai multe domenii, dar în funcție de complexitatea lor, generarea acestora poate dura o perioadă mare de timp. Chiar și dacă aceștia sunt descriși printr-un simplu sistem de rescriere a șirurilor de caractere, după câteva generații parcurgerea completă a șirurilor ce îi descriu poate ajunge la câteva minute.

Sistemele Lindenmayer pot fi folosite pentru a studia forme naturale, având o oarecare limitare. Acestea pot fi extinse atât prin regulile de generare, cât și prin regulile de desenare. Iar pentru a putea genera forme de o complexitate medie, se paote implementa doar un subset din acestea.

Folosirea unui sistem distribuit pentru generarea fractalilor poate reduce considerabil timpul necesar prelucrării acestora, chiar și pe un dispozitiv Android. Cu toate acestea, atunci când decidem să folosim alte calculatoare pentru procesare trebuie să ținem cont de datele necesare pentru generare. Prea multe calculatoare cu o putere de procesare slabă, folosite pentru un fractal cu reguli reduse și o generație scăzută, pot îngreuna generarea acestuia, atât timp cât datele pot fi obținute prin task-uri rapide și ușor de realizat chiar și pentru un procesor slab.

Pe de altă parte, dacă se cere un fractal la o generație avansată, se pot folosi un număr mai mare de calculatoare, dar și aici avem o limită superioară la care adăugarea mai multor calculatoare poate constitui un mare dezavantaj.

În concluzie, generarea fractalilor poate fi asistată de un sistem distribuit, însă datele de prelucrat trebuie trimise astfel încât acesta să nu îngreuneze obținerea rezultatului final.

Referințe

[1] Trochet, Holly (2009). "A History of Fractal Geometry". MacTutor History of Mathematics.

[2] Gouyet, Jean-François (1996). Physics and fractal structures.

[3] Mandelbrot, Benoît B. (1983). The fractal geometry of nature. Macmillan.

[4] Mandelbrot, Benoît. "24/7 Lecture on Fractals".

[5] Karperien, Audrey (2004). Defining microglial morphology: Form, Function, and Fractal Dimension.

[6] Albers, Donald J.; Alexanderson, Gerald L. (2008). "Benoît Mandelbrot: In his own words". Mathematical people : profiles and interviews.

[7] Falconer, Kenneth (2003). Fractal Geometry: Mathematical Foundations and Applications. John Wiley & Sons, Ltd. xxv.

[8] Vicsek, Tamás (1992). Fractal growth phenomena. Singapore/New Jersey: World Scientific.

[9] Peters, Edgar (1996). Chaos and order in the capital markets : a new view of cycles, prices, and market volatility.

[10] Spencer, John; Thomas, Michael S. C.; McClelland, James L. (2009). Toward a unified theory of development: connectionism and dynamic systems theory re-considered. Oxford/New York: Oxford University Press.

[11] Mandelbrot, Benoît B. (2004). Fractals and Chaos. Berlin: Springer.

[12] Frame, Angus (3 August 1998). "Iterated Function Systems". In Pickover, Clifford A. Chaos and fractals: a computer graphical journey : ten year compilation of advanced research. Elsevier.

[13] "Hunting the Hidden Dimension." Nova. PBS. WPMB-Maryland.

[14] Taylor, Richard; Micolich, Adam P.; Jonas, David. "Fractal Expressionism: Can Science Be Used To Further Our Understanding Of Art?".

[15] Frame, Michael; and Mandelbrot, Benoît B.; A Panorama of Fractals and Their Uses

[16] Eglash, Ron (1999). "African Fractals: Modern Computing and Indigenous Design". New Brunswick: Rutgers University Press.

[17] Stumpff, Andrew (2013). "The Law is a Fractal: The Attempt to Anticipate Everything" 44. Loyola University Chicago Law Journal.

[18] Grzegorz Rozenberg and Arto Salomaa. The mathematical theory of L systems (Academic Press, New York, 1980).

[19] Paul Bourke. An Introduction to Fractals. May 1991.

[20] Geoffrey Irving, Henry Segerman. Developing fractal curves. Version 1, October 31, 2012.

[21] Jarek Duda. "The Boundary of Periodic Iterated Function Systems". The Wolfram Demonstrations Project. Recurrent construction of the boundary of dragon curve.

[22] Coulouris, George; Jean Dollimore; Tim Kindberg; Gordon Blair (2011). Distributed Systems: Concepts and Design (5th Edition). Boston: Addison-Wesley.

[23] Andrews (2000). Dolev (2000). Ghosh (2007)

[24] Andrews (2000), Dolev (2000), Ghosh (2007), Lynch (1996), Peleg (2000)

[25] Andrews (2000), Ghosh (2007), Peleg (2000)

[26] Eric Chen, Satoshi Ogata, Keitaro Horikawa. Offloading Android Applications to the Cloud without Customizing Android

Link-uri Imagini

[1] http://www.math.utah.edu/~pa/math/mandelbrot/large.gif

[2] http://farm8.staticflickr.com/7412/11365016196_e8a1915bc1_o.jpg

[3] http://paulbourke.net/fractals/fracdim/exact.gif

[4] http://www.learner.org/courses/mathilluminated/images/units/5/1087.png

[5] http://upload.wikimedia.org/wikipedia/en/8/86/Ifs-construction.png

[6] http://igm.rit.edu/~nd/sims/trees.png

[7] http://upload.wikimedia.org/wikipedia/commons/f/f4/Burning_Ship_Left.jpg

[8] http://seeingcomplexity.files.wordpress.com/2011/02/levy-flight.jpg

[9] http://upload.wikimedia.org/wikipedia/commons/7/74/Dragon_trees.jpg

[10] http://fractal.weebly.com/uploads/7/3/7/4/737477/2797414.jpg

[11] http://upload.wikimedia.org/wikipedia/commons/thumb/0/0a/Frost_patterns_2.jpg/1024px-Frost_patterns_2.jpg

[12] http://www.tsc.upc.es/fractalcoms/images/2.jpg

[13] http://upload.wikimedia.org/wikipedia/commons/a/af/Fractal_weeds.jpg

[14] http://www.keesmoerman.nl/img/turtle2.gif

[15] http://upload.wikimedia.org/wikipedia/commons/0/07/Turtle_draw.jpg

[16] http://hollymath.files.wordpress.com/2013/06/dragon_curve.gif

[17] http://upload.wikimedia.org/wikipedia/commons/8/80/Dimensions_fractale_dragon.gif

Bibliografie

Albers, Donald J.; Alexanderson, Gerald L. (2008). „Benoît Mandelbrot: In his own words”

Andrews, Gregory R. (2000). „Foundations of Multithreaded, Parallel, and Distributed Programming”

Bourke, Paul (1991). „An Introduction to Fractals”

Chen, Eric; Ogata, Satoshi; Horikawa, Keitaro. „Offloading Android Applications to the Cloud without Customizing Android”

Coulouris, George; Dollimore, Jean; Kindberg, Tim; Blair, Gordon (2011). „Distributed Systems: Concepts and Design (5th Edition)”

Duda, Jarek. „The Boundary of Periodic Iterated Function Systems”

Eglash, Ron (1999). "African Fractals: Modern Computing and Indigenous Design"

Falconer, Kenneth (2003). „Fractal Geometry: Mathematical Foundations and Applications”

Frame, Angus (1998). "Iterated Function Systems"

Frame, Michael; and Mandelbrot, Benoît B. „A Panorama of Fractals and Their Uses”

Ghosh, Sukumar (2007). „Distributed Systems – An Algorithmic Approach”

Gouyet, Jean-François (1996). „Physics and fractal structures”

Grzegorz Rozenberg and Arto Salomaa (1980). „The mathematical theory of L systems”

Hohlfeld, Robert G.; Cohen, Nathan (1999). „Self-similarity and the geometric requirements for frequency independence in Antennae”

Irving, Geoffrey and Segerman, Henry (2012). „Developing fractal curves”

Karperien, Audrey (2004). „Defining microglial morphology: Form, Function, and Fractal Dimension”

Mandelbrot, Benoît B. (1983). „The fractal geometry of nature”

Mandelbrot, Benoît B. (2004). „Fractals and Chaos”

Mandelbrot, Benoit (2006). „24/7 Lecture on Fractals”

Nova (2008). „Hunting the Hidden Dimension”

Peters, Edgar (1996). „Chaos and order in the capital markets : a new view of cycles, prices, and market volatility”

Spencer, John; Thomas, Michael S. C.; McClelland, James L. (2009). „Toward a unified theory of development : connectionism and dynamic systems theory re-considered”

Stumpff, Andrew (2013). „The Law is a Fractal: The Attempt to Anticipate Everything”

Taylor, Richard; Micolich, Adam P.; Jonas, David (2010). „Fractal Expressionism: Can Science Be Used To Further Our Understanding Of Art?”

Trochet, Holly (2009). „A History of Fractal Geometry”

Vicsek, Tamás (1992). „Fractal growth phenomena”

Bibliografie

Albers, Donald J.; Alexanderson, Gerald L. (2008). „Benoît Mandelbrot: In his own words”

Andrews, Gregory R. (2000). „Foundations of Multithreaded, Parallel, and Distributed Programming”

Bourke, Paul (1991). „An Introduction to Fractals”

Chen, Eric; Ogata, Satoshi; Horikawa, Keitaro. „Offloading Android Applications to the Cloud without Customizing Android”

Coulouris, George; Dollimore, Jean; Kindberg, Tim; Blair, Gordon (2011). „Distributed Systems: Concepts and Design (5th Edition)”

Duda, Jarek. „The Boundary of Periodic Iterated Function Systems”

Eglash, Ron (1999). "African Fractals: Modern Computing and Indigenous Design"

Falconer, Kenneth (2003). „Fractal Geometry: Mathematical Foundations and Applications”

Frame, Angus (1998). "Iterated Function Systems"

Frame, Michael; and Mandelbrot, Benoît B. „A Panorama of Fractals and Their Uses”

Ghosh, Sukumar (2007). „Distributed Systems – An Algorithmic Approach”

Gouyet, Jean-François (1996). „Physics and fractal structures”

Grzegorz Rozenberg and Arto Salomaa (1980). „The mathematical theory of L systems”

Hohlfeld, Robert G.; Cohen, Nathan (1999). „Self-similarity and the geometric requirements for frequency independence in Antennae”

Irving, Geoffrey and Segerman, Henry (2012). „Developing fractal curves”

Karperien, Audrey (2004). „Defining microglial morphology: Form, Function, and Fractal Dimension”

Mandelbrot, Benoît B. (1983). „The fractal geometry of nature”

Mandelbrot, Benoît B. (2004). „Fractals and Chaos”

Mandelbrot, Benoit (2006). „24/7 Lecture on Fractals”

Nova (2008). „Hunting the Hidden Dimension”

Peters, Edgar (1996). „Chaos and order in the capital markets : a new view of cycles, prices, and market volatility”

Spencer, John; Thomas, Michael S. C.; McClelland, James L. (2009). „Toward a unified theory of development : connectionism and dynamic systems theory re-considered”

Stumpff, Andrew (2013). „The Law is a Fractal: The Attempt to Anticipate Everything”

Taylor, Richard; Micolich, Adam P.; Jonas, David (2010). „Fractal Expressionism: Can Science Be Used To Further Our Understanding Of Art?”

Trochet, Holly (2009). „A History of Fractal Geometry”

Vicsek, Tamás (1992). „Fractal growth