curs_06_hilbert.pdf

7/30/2019 curs_06_hilbert.pdf

1/18

Cursul 6

Curbe care trec prin toate punctele unui plan

1. Parcurgerea planului n Z-ordine

Sa consideram o baza de date bidimensionala cu doua chei de intrare pe care o putem reprezenta spatial ca un tablou dreptunghiular de elementedispuse pe m linii si n coloane, fiecare element fiind accesat prin precizarea a doiindici, x indicele de coloana, abscisa, si y indicele de linie, ordonata. Se pune

problema serializarii acestei bazei de date, a stocarii ei secventiale, ntr-un fisierpe disc, de exemplu.

Figura 1. Parcurgerea n Z-ordine.

Altfel spus, trebuie sa precizam o parcurgere a tabloului ntr-o anumita ordine,prin care sa accesam fiecare element o singura data, mai precis, sa stabilim ocorespondenta bijectiva ntre produsul cartezian

{0, 1, . . . , n 1} {0, 1, . . . , m 1}si multimea {0, 1, . . . , m n 1}.

1


2/18

Solutia cea mai simpla si cea mai des folosita este parcurgerea pe linii, de lastanga la dreapta si de sus n jos. Daca notam cu N rangul lui (x, y) n nsiruirea

(0, 0), (1, 0), . . . , (n1, 0), (0, 1), (1, 1), . . . , (0, m1), (1, m1), . . . , (n1, m1)atunci avem relatia

N = x + ny

si reciproc,

x = N mod n, y = (N x)/n.Aceast mod de parcurgere are doua puncte slabe: operatiile aritmetice impli-

cate n gasirea indicilor x si y nu sunt adecvate calculului pe biti si prin urmaresunt consumatoare de timp, iar parcurgerea nu este localizata, doua elemente

vecine n matrice se pot gasi oricat de departe n nsiruire vezi cazul a douaelemente aflate unul sub altul pe o coloana.

Aceste doua impedimente sunt nlaturate, macar partial, de parcurgerea nZ-ordine, care este, n esenta, forma bidimensionala a algoritmului de cautarebinara. Impartim matricea n doua benzi orizontale si doua verticale, obtinempatru regiuni pe care le parcurgem dupa un drum n forma literei Z: sus stanga dreapta, apoi jos stanga dreapta. Daca este necesar, fiecare regiune va fiparcursa tot n aceasta ordine (vezi Figura 1).

Figura 2. Algoritmul de intercalare binara

2


3/18

Este clar ca parcurgerea n Z-ordine are o localizare mai buna decat par-curgerea pe linii, avantajul principal consta totusi n algoritmul de determinare

a corespondenteiN (x, y)

sugerat de Figura 2, si anume: utilizand scrierea numerelor n baza 2, bit ii lui Nse obtin prin intercalarea bitilor lui x cu ai lui y. Justificarea este foarte simpla:la mpartirea initiala n doua benzi orizontale si doua benzi vericale, primul bital lui y precizeaza daca elementul (x, y) se afla n banda de sus sau n cea de jos,iar primul bit al lui x precizeaza daca el se afla n stanga sau n dreapta, asa canumararea pe doi biti

00, 01, 10, 11

da exact parcurgerea celor patru regiuni n Z-ordine. Aplicand recursiv procedeul

n fiecare regiune, obtinem exact algoritmul precizat.Sa notam urmatorul dezavantaj al metodei: n si m trebuie sa fie egale si deforma n = m = 2k.

In clasa C# urmatoare aplicam algoritmul de mai sus ca sa parcurgem nZ-ordine o retea de puncte din planul complex, mai precis, cele 22k puncte dinpatratul unitate [0, 1] [0, 1] de forma

z = (x + iy)/2k

cu x si y din {0, 1, . . . , 2k 1}.public class Z_orderBin : FractalForm

{

Complex i = new Complex(0, 1);bool incrementare(int[] regBin, int dim)

{

int aux, k, transport;

transport = 1;

k = 0 ;

while (k < dim && transport == 1)

{

aux = regBin[k] + transport;

if (aux == 1)

{

regBin[k] = 1;

transport = 0;}

else //aux==2

{

regBin[k] = 0;

transport = 1;

k++;

}

}

if (k == dim) return false; //depasire registru

else return true;

3


4/18

}

void traseaza(ComList li)

{ int n = 0;

Complex z2, z1 = li.firstZet;

for (z2 = li.nextZet; !li.ended; z2 = li.nextZet)

{

setLine(z1, z2, getColor(++n / 5));

z1 = z2;

}

resetScreen();

}

public override void makeImage()

{

setXminXmaxYminYmax(-0.1, 1.1, 1.1, -0.1);int k = 5, dim = 2 * k;

int[] reg = new int[dim];

for (int h = 0; h < dim; h++)

reg[h] = 0;

ComList fig = new ComList();

fig.nextZet = 0;

while (incrementare(reg, dim))

{

//aflam x si y

double y = 0;

double p = 1;f o r ( i n t h = 2 * k - 1 ; h > 0 ; h - = 2 )

{

p *= 2;

y += (double)reg[h] / p;

}

double x = 0;

p = 1 ;

f o r ( i n t h = 2 * k - 2 ; h > = 0 ; h - = 2 )

{

p *= 2;

x += (double)reg[h] / p;

}fig.nextZet = x + i * y;

}

traseaza(fig);

}

}

In program generam scrierea binara a rangului N direct ntr-un registru pe 2kbiti, n vectorul

int[] reg = new int[dim];

pe care l initializam cu zero si apoi l incrementam cu metoda

4


5/18

bool incrementare(int[] regBin, int dim){...}

pana cand obtinem depasire de format. La fiecare pas obtinem coordonatele x siy ale punctului curent z prin dez-intercalarea bitilor lui N si memoram punctulz n lista fig. In final desenam traseul pastrat n lista.

O clasa care implementeaza algoritmul de intercalare binara de mai sus uti-lizand direct operatii pe biti este urmatoarea:

public class Z_orderPeBiti : FractalForm

{

Complex i = new Complex(0, 1);

void traseaza(ComList li)

{int n = 0;


for (z2 = li.nextZet; !li.ended; z2 = li.nextZet)

{


z1 = z2;

}

resetScreen();

}

public override void makeImage()

{ setXminXmaxYminYmax(-0.1, 1.1, 1.1, -0.1);

int k = 6; // atentie: 0 < k < 15

uint nrPuncte = 1u


6/18

Figura 3. class Z orderBin

Revenind la fractali, ne propunem sa generam curbele date de parcurgerilen Z ordine prin transformari geometrice, pe baza urmatoarei proprietati deautosimilaritate observate n Figura 3: pentru fiecare k, n etapa de ordin kavem n patratul unitate o parcurgere din coltul din stanga sus pana n coltuldin dreapta jos. Daca reducem totul la scara 1/2 cu centru n c0 centrulpatratului initial , translatam de patru ori patratelul obtinut asfel ncat c0

sa ajunga pe rand n c2, c3, c1 si c4 n aceasta ordine si racordam n formade Z cele patru parcurgeri, vom obtine curba de ordin k + 1.Urmatoarea clasa implementeaza metoda transformarilor geometrice pentru

obtinerea parcurgerilor n Z-ordine.

public class Z_order : FractalForm {

static Complex i = new Complex(0, 1);

static Complex c0 = (1 + i) / 2;


static Complex c2 = (1 + 3 * i) / 4;



6


7/18

//sk(z)=c0+0.5*(z-c0) +(ck-c0)=ck+0.5*(z-c0)

Complex s1(Complex z) { return c1 + 0.5 * (z - c0); }

Complex s2(Complex z) { return c2 + 0.5 * (z - c0); }Complex s3(Complex z) { return c3 + 0.5 * (z - c0); }

Complex s4(Complex z) { return c4 + 0.5 * (z - c0); }

void transforma(ref ComList li) {

ComList rez = new ComList();

Complex z;

for (z = li.firstZet; !li.ended; z = li.nextZet)

rez.nextZet = s2(z);




rez.nextZet = s1(z);for (z = li.firstZet; !li.ended; z = li.nextZet)


li = rez;

}

void traseaza(ComList li){

initScreen();

//trasam chenarul

Color col = getColor(0);

setLine(0.0, 1.0, col);

setLine(1.0, 1 + i, col);

setLine(1 + i, i, col);setLine(i, 0.0, col);

//desenam curba curenta

int n = 0;


for (z2 = li.nextZet; !li.ended; z2 = li.nextZet){


z1 = z2;

}

}

public override void makeImage() {

setXminXmaxYminYmax(-0.1, 1.1, -0.1, 1.1);

ComList fig = new ComList();fig.nextZet = c0;

for (int k = 0; k < 5; k++){

transforma(ref fig);

traseaza(fig);

if (!resetScreen()) return;

delaySec(1);

}

}

}

7


8/18

Daca n figura initiala avem numai punctul z0, vom obtine la fiecare etapaexact curbele generate de programul precedent

Figura 4. class Z order

Observam ca, pentru k din ce n ce mai mare, curbele noastre trec printr-oretea din ce n ce mai deasa de puncte din patratul unitate. Ne ntrebam dacanu cumva acest sir de curbe converge la o curba care trece prin toate punctelepatratului. Raspunsul este pozitiv si a fost dat n anul 1904 de matematicianul

francez Henri Lebesgue (1875 - 1941), utilizand o parametrizare analitica a curbeilimita. Demonstratia fiind laborioasa si greu de urmarit, n sectiunea urmatoarevom prezenta pe larg un alt exemplu de astfel de curb a, care, desi este mai dificilde desenat, are o demonstratie a convergentei sirului de curbe iterate mai usorde nteles!

8


9/18

2. Curba lui Hilbert

Primul exemplu de curba care umple un patrat (mai precis, o aplicatie con-tinua si surjectiva z : [0, 1] [0, 1][0, 1]), a fost dat n 1890 de Giuseppe Peano,printr-o constructie analitica (pe baza scrierii numerelor n baza trei), fara niciun caracter intuitiv geometric. Acest exemplu, care poate fi considerat primulfractal nebanal, a pus problema fundamentarii riguroase a notiunii de dimensiunea unei figuri geometrice.

Mai tarziu multi alti matematicieni au gasit astfel exemple, dintre ei DavidHilbert fiind primul care a dat, n 1891, o modalitate geometrica de generare aunei astfel de curbe. Alte exemple au fost date, printre alt ii, de E. H. Moore n1900, Henri Lebesgue n 1904 si Waclaw Sierpinski n 1912. Astazi multe dintreaceste curbe poarta denumirea de curba a lui Peano, un termen generic pentru

curba care umple planul.

Figura 5. Curba lui Hilbert. Figura initiala

In continuare vom studia curba lui Hilbert, pe care am ntalnit-o deja lasisteme Lindenmayer, si pe care acum o vom prezenta folosind metoda trans-formarilor geometrice.

9


10/18

Sa presupunem ca la un moment dat avem trasata o curba oarecare n patratulunitate, care pleaca din vecinatatea coltului din stanga jos si ajunge n preajma

coltului din dreapta jos (vezi Figura 5). Micsoram ntreaga figura la scara 1/2,o rotim, o oglindim daca e nevoie si o translatam de patru ori, pozitionand ca nFigura 6 patratelele obtinute, si racordam cele patru arce astfel ncat sa obtinemo noua curba care pleaca din vecinatatea coltului din stanga jos si ajunge npreajma coltului din dreapta jos. Repetam apoi la nesfarsit aceste operatii,obtinand astfel un sir de curbe despre care David Hilbert a aratat ca, indiferent

Figura 6. Curba lui Hilbert. Figura transformata

de curba initiala, sirul converge la o curba continua unic determinata care treceprin toate punctele patratului unitate, curba care astazi i poarta numele.

O clasa C# care sa implementeaze metoda descrisa poate fi obtinuta imediatdin clasa Z order prezentata mai sus, actualizand numai definitiile si ordinea deaplicare a transformarilor geometrice s1, s2, s3 si s4:

static Complex i = new Complex(0, 1);

static Complex ipe2 = i / 2;


10


11/18



static Complex c3 = (3 + 3 * i) / 4;static Complex c4 = (3 + i) / 4;

Complex s1(Complex z) {

return c1 + ipe2 * (ipe2 + (z - ipe2).conj - c0);

}


return c2 + 0.5 * (z - c0);

}


return c3 + 0.5 * (z - c0);

}


return c4 - ipe2 * (ipe2 + (z - ipe2).conj - c0);}

Figura 7. Curba lui Hilbert. Forma clasica

11


12/18

In cazul n care curba initiala se reduce la un singur punct, centrul patratului,se obtin iteratele clasice ale curbei lui Hilbert reprezentate n Figura 7.

Pentru a da o demonstratie riguroasa a existentei curbei lui Hilbert, avemnevoie de un alt mod de constructie, si anume generarea prin metoda motiveloriterate. Dupa cum stim metoda consta n nlocuirea, la fiecare iteratie, a uneifiguri, baza, cu o alta figura, motivul, n care sa se regaseasca ntr-o forma saualta, eventual de mai multe ori, baza pentru reluarea iter arii.

Figura 8. HilbertMotiveIterate. Baza (k=0).

In cazul nostru, consideram baza formata dintr-un patrat orientat z1z2z3z4(vezi Figura 8) care la fiecare etapa este nlocuit cu motivul format din 4 patratede latura njumatatita, dispuse si parcurse asa cu reiese din Figura 9.

La fiecare etapa vom forma o lista de patrate, orice patrat z1z2z3z4 fiindpastrat n lista numai prin trei puncte, z1, z0 si z4, n aceasta ordine, unde z0este centrul patratului. Evident ca z2 si z3 pot fi regasite prin calcul. Aceastametoda de stocare, pe langa economia de memorie, are avantajul ca pune nevidenta si parcurgerea generata de segmentele z1z0 si z0z4 (rosu si albastru) din

12


13/18

patratul de baza, care se racordeaza n mod automat la construirea motivului,formand parcurgerea de ordin urmator.

Figura 9. HilbertMotiveIterate. Motivul (k=1).

Aceasta nlantuire a tripletelor succesive z1z0z4 si z

1z

0z

4, data de egalitateaz4 = z

1, permite ca n lista fiecare triplet nou sa fie memorat numai prin douavalori, z0 si z

4, noul punct initial z

1 fiind precedentul punct final z4.

public class HilbertMotiveIterate : FractalForm {

static Complex i = new Complex(0.0, 1.0);void transforma(ref ComList li) {

ComList rez = new ComList();

Complex z0, z1, z2, z3, z4;

rez.nextZet = z1 = li.firstZet;

for (z0 = li.nextZet; !li.ended; z0 = li.nextZet){

z4 = li.nextZet;

z 3 = 2 * z 0 - z 1 ;

z 2 = 2 * z 0 - z 4 ;

rez.nextZet = (z1 + z0) / 2;


13


14/18


rez.nextZet = z0;

rez.nextZet = (z0 + z3) / 2;rez.nextZet = (z3 + z4) / 2;


rez.nextZet = z4;

z1 = z4;

}

li = rez;

}

void traseazaPatrate(ComList li) {

Complex z0, z1, z2, z3, z4;

initScreen();

Color col = Color.White;

z1 = li.firstZet;for (z0 = li.nextZet; !li.ended; z0 = li.nextZet){

z4 = li.nextZet;

z 3 = 2 * z 0 - z 1 ;

z 2 = 2 * z 0 - z 4 ;

setLine(z1, z4, col);




setLine(z1, z0, Color.Red);

setLine(z0, z4, Color.Blue);

z1 = z4;}

resetScreen();

}

public override void makeImage(){

setXminXmaxYminYmax(-0.25, 1.25, -0.25, 1.25);

ComList fig = new ComList();

fig.nextZet = 0;

fig.nextZet = 0.5 + 0.5 * i;

fig.nextZet = 1;

traseazaPatrate(fig);

for (int k = 1; k < 3; k++) {

transforma(ref fig);traseazaPatrate(fig);

delaySec(0.5);

}

}

}

Pentru fiecare k = 0, 1, 2 . . . obtinem la etapa k o curba Ck sub forma de liniepoligonala rosu albastra, care pleaca din varful z1 = 0 al patratului unitate siajunge n z4 = 1. Pentru a arata ca acest sir de curbe defineste o curba limita,trebuie mai ntai sa precizam ce reprezentari parametrice avem n vedere pentru

14


15/18

curbele Ck, adica sa precizam un sir de aplicatii continue

zk : [0, T]C, k = 0, 1, 2, . . . ,

astfel ncat, pentru fiecare k, punctul curent zk(t) sa parcurga complet curba Ckpentru t [0, T], unde T > 0 este fixat arbitrar. Cum orice curba Ck poate fiparcursa n mai multe feluri, va trebui sa alegem pentru fiecare cate o anumitaparcurgere zk.

Curba limita va fi data atunci de functia limit a punctual a, daca exista, asirului de functii (zk)k, adica de functia z : [0, T] C definita de egalitatea

z(t) = limk

zk(t),

pentru fiecare t [0, T].

Figura 10. HilbertMotiveIterate. Parcurgerea de ordin k=2

Pentru arata ca functia limita defineaste o curba C, va trebui sa demonstramca este functie continua, dar pentru aceasta convergenta punctuala, definita maisus, nu este suficienta. Un sir punctual convergent de functii continue se poate

15


16/18

rupe prin trecere la limita, de exemplu sirul de functii continue zk(t) = tki, cu

t [0, 1], are functia limita

z(t) = limk

zk(t) = limk

tki =

{0, pentru t [0, 1)i, pentru t = 1,

care este evident discontinua.Din acest motiv vom cauta ca sirul de functii (zk)k sa fie uniform converget

la z, adica sa avemlimk

supt[0,T]

|zn(t) z(t)| = 0.Se stie ca daca toti termenii unui sir uniform convergent sunt functii continue,limita sa este continua.

Pentru a fixa modul de parcurgere al curbelor Ck, reanalizam acum metoda

lor de constructie. Observam ca fiecare aplicare a motivului mareste de 4 orinumarul patratelor implicate si le njumatateste lungimea laturii, iar o data cuaceasta numarul de segmente rosii si albastre se mareste de patru ori dar culungimile micsorate de doua ori, dublandu-si astfel lungimea totala. Deducemimediat ca la fiecare etapa k avem, nainte de aplicarea motivului, o retea formatadin 4k patrate Pk de latura lk = 1/2

k, n fiecare patrat curba Ck avand exactdoua segmente, ea fiind prin urmare formata din 2 4k segmente cu lungimeatotala Lk = 2

kL0 = 2k

2.Deorece fiecare curba Ck este o linie poligonala cu un numar finit de laturi

avand fiecare lungime finita, putem considera parcurgerile cu viteza vk constanta

n modul, fiecare latura fiind parcursa de punctul curent zk(t) printr-o miscarerectilinie uniforma, data de o lege orara de forma

zk(t) = t + ,

cu || = vk = 2k

2/T. Constantele complexe si se pot determina n modunic din conditiile de racordare, din aproape n aproape, astfel ncat functiazk : [0, T] C sa fie continua si sa parcurga linia poligonala Ck.

Din modul de constructie rezulta ca fiecare patrat Pk are un colt de intraresi unul de iesire pe unde intra n patrat, respectiv ies, toate parcurgerile zn cun k. Punctul zk+1(t) se misca de doua ori mai repede decat zk(t), iar ninteriorul fiecarui patrat Pk parcurge o lungime dubla fata de zk(t), rezulta ca

cele doua puncte traverseaza patratulP

k n tot atatea unitati de timp. Deoarecetoate parcurgerile pornesc simultan din acelasi punct z = 0 si ajung simultann acelasi punct z = 1, urmeza ca ele sunt sincronizate astfel ncat n fiecarepatrat Pk punctele curente zk(t) si zk+1(t) intra n acelasi moment k prin coltulsau de intrare, parcurg apoi separat doua, respectiv opt segmente din liniile lorpoligonale, si parasesc patratul de baza Pk tot simultan, prin coltul sau de iesire.In tot acest timp punctele zk(t) si zk+1(t) se gasesc n interiorul patratului Pksi prin urmare distanta dintre ele este mai mica decat diagonala acestuia. Amaratat astfel ca

|zk+1(t) zk(t)| lk

2 =

2

2k,

16


17/18

pentru orice t [0, T].Deoarece seria numerica

k=0

22k

este convergenta, din criteriul lui Weierstrass urmeaza ca seria de functii

z0(t) +k=0

(zk+1(t) zk(t))

este uniform convergenta pe [0, T], si o data cu ea este uniform convergent sirulsumelor sale partiale

z0(t) + (z1(t) z0(t)) + + (zn(t) zn1(t)) = zn(t).

Pana acum am aratat astfel ca sirul de functii continue (zk)k este uniformconvergent pe [0, T] la o functie continua z care defineste astfel o curba C. Mairamane de aratat ca C trece prin toate punctele patratului unitate.

Din proprietatea de sincronizare descrisa mai sus stim ca fiecare patrat Pkare un colt prin care intra n patrat, la acelasi moment k, toate parcurgerile deordin n k. Deducem ca sirul (zn(n))n este constant de la k ncolo, si deci

z(k) = limn

zn(k) = zk(k) Pk.Am aratat astfel ca C trece prin orice patrat Pk, pentru orice k 0.

Fixam acum n mod arbitrar un punct z [0, 1] [0, 1] si ne propunem sadovedim existenta unui t

[0, T] astfel ncat z(t) = z. Este evident ca, pentru

orice ordin k 0, punctul z se afla cel putin n interiorul sau pe laturile unuipatrat de ordin k, notat n continuare Pk. Din cele aratate mai sus, stim capentru Pk exista un moment

k [0, T] astfel ncat z(k ) Pk, de aici urmeazaca distanta dintre punctele z si z(k ) este mai mica decat diagonala patratuluiP

k, care le contine. Asadar

|z(k ) z|

2

2k,

pentru orice k 0, de unde rezultalimk

z(k ) = z.

Sirul (k )k fiind marginit, are cel putin un subsir (

kn)n convergent la un t din

intervalul [0, T]. Folosim acum continuitatea functiei limita z si demonstramegalitatea dorita:

z() = z( limn

kn) = limnz(kn) = z

.

In concluzie, am aratat ca sirul iteratelor Ck converge ntr-un sens bine pre-cizat la o curba continua C care trece prin toate punctele patratului [0, 1] [0, 1].Este usor de vazut ca, daca n etapa initiala n locul curbei C0 formata din douasegmente consideram orice alta curba de lungime finita, 0 < L0 < +, carepleaca din z = 0 si ajuge n z = 1, sirul iteratelor Ck va tinde la aceeasi limita

17


18/18

C, deoarece aceasta este unic determinata de ordinea de trecere prin punctele deintrare/iesire ale patratelor Pk, ordine care nu depinde de curba initiala.

Desenarea prin degradeuri de culoare a curbei C curba lui Hilbert prezen-tata n Figura 11, a fost obtinuta printr-o usoara modificare a codului claseiHilbertMotiveIterate.

Figura 11. HilbertMotiveIterate. Parcurgerea de ordin k=10

18

Date post:	14-Apr-2018
Category:	Documents
Upload:	stefan-caraiman
View:	215 times
Download:	0 times

curs_06_hilbert.pdf

Documents