codul qr și game of life

duminică, 24 feb. 2013, 19:41

Așa-zisul cod QR reprezintă o metodă de codificare a informației digitale astfel încât aceasta să poată fi decodificată ulterior cu ușurință — rapid și fără erori — cu ajutorul unui senzor optic, e.g. o cameră foto. Nu-i cu nimic diferit conceptual de un cod de bare, având însă avantajul că admite o densitate a informației ceva mai ridicată. În particular, e mult mai ușoară stocarea unui șir de caractere ASCII sau Unicode sub forma QR decât cu ajutorul codurilor de bare clasice, cum ar fi EAN sau ce se mai găsește în mod normal pe etichetele produselor aflate în comerț.

Game of Life este un automat celular faimos, descoperit de către matematicianul John Horton Conway. Regulile automatului sunt oarecum intuitive, și în plus configurațiile inițiale pot duce la evoluții „haotice”, posibil utile pentru modelarea în domenii precum cel al biologiei, economiei sau fizicii — numele „Game of Life” nu e ales tocmai la întâmplare. O particularitate interesantă pentru calculatoare și teoria informației este aceea că unele din „structurile” simple din Game of Life pot fi folosite pentru a construi mașini Turing. Dincolo de asta, e greu de zis ce mai ascunde automatul cu pricina. (mai mult…)

să scriem împreună un simulator de automate celulare (iii)

duminică, 18 nov. 2012, 14:56

Am pus până acum bazele unui simulator de automate celulare și apoi am ajuns la o implementare funcțională conform unor specificații. Pe scurt, am obținut o mașinărie capabilă de a primi la intrare un șir de celule „goale” sau „umplute” (fiecare), prelucrându-l inductiv și obținând la fiecare pas de inducție un alt șir de celule cu aceleași proprietăți. Zisa mașinărie nu prelucrează celulele arbitrar, ci pe baza unui set de reguli care iau în calcul valoarea celulei și a vecinilor direcți, stabiliți după ordinea din șir. Putem privi șirul de șiruri rezultat fie ca pe o secvență de evenimente, fie ca pe un „covor” care are pe prima linie primul șir de celule, pe a doua șirul următor și așa mai departe.

Uneltele folosite până acum ne-au permis să vizualizăm datele doar în cel de-al doilea mod. Exemplele relevă astfel șabloane fractale precum cel al triunghiului Sierpinski, imagini regulate sau care se autoreglează „în jos”, sau dimpotrivă, reprezentări profund neregulate [i] care aduc a „randomness”. Acest al doilea mod de vizualizare oferă deci o privire sintetică asupra evoluției unui automat celular elementar oarecare.

Putem însă la fel de bine să folosim Haskell și unele din bibliotecile grafice avute la dispoziție pentru a vizualiza rezultatele în primul mod. Având la dispoziție o listă de stări, deci o listă de liste de celule, putem afișa o stare sub forma unui cadru într-o animație, extinzând astfel evoluția pe axa timpului. Propun astfel ca o celulă să fie afișată sub forma unui „petic” de 20 x 20 pixeli dintr-o imagine, după cum urmează: o celulă având valoarea E va fi reprezentată printr-un pătrat alb, în timp ce o celulă F va avea asociat un pătrat umplut cu negru. „Peticele” care formează o stare vor fi concatenate de la stânga la dreapta într-o imagine/cadru cu înălțimea 20 și lățimea 20 x lungimea șirului. (mai mult…)

  1. Studiul regularității automatelor celulare elementare plecând de la stări inițiale aleatoare a dus la împărțirea acestora în patru clase distincte. E demn de menționat și faptul că regularitatea de un anumit fel și interacțiunea între celule fac ca anumite automate celulare să fie echivalente computațional cu o mașină Turing. [↩]

să scriem împreună un simulator de automate celulare (ii)

duminică, 4 nov. 2012, 14:17

Data trecută am discutat câteva aspecte generale legate de automatele celulare și am implementat o funcție care va sta la baza implementării zisului simulator. Aceasta se numește nextCell și întoarce valoarea unei celule după un pas în funcție de valoarea sa și de cea a vecinilor, și în primul rând de numărul care specifică pe scurt regulile de producție ale automatului elementar. Să punem din nou pe foaie signatura funcției:

nextCell :: Elementary -> (Cell, Cell, Cell) -> Cell

Mai departe dorim să extindem această funcționalitate la o așa-zisă „latice”, adică la un șir de celule, pe care noi îl vom reprezenta printr-o listă. Cu alte cuvinte vrem, cunoscând numărul automatului celular, să luăm pe rând fiecare celulă dintr-o listă dată împreună cu vecinii ei la momentul t și să obținem starea celulei la momentul t + 1. Implementarea acestei operații e un pic mai dificilă decât ar părea la o primă vedere, din cauza unor limitări cărora le sunt supuse listele ca model de reprezentare. Să explicăm pe scurt câteva din aceste limitări. (mai mult…)

să scriem împreună un simulator de automate celulare (i)

duminică, 14 oct. 2012, 12:06

Automatele celulare au reprezentat o noutate prin anii ’40-’60, la momentul descoperirii lor de către Ulan și von Neumann. În anii ’70-’80 conceptul a devenit iarăși un subiect de interes datorită cercetărilor (mai degrabă empirice) făcute de Stephen Wolfram și alții pentru a reprezenta și studia diverse trăznăi precum modele ale fizicii digitale sau ale vieții. În anii 1990-2010 descoperirile în cadrul domeniului merg într-un ritm lent, însă nu încetează a se ivi. Cu toate acestea automatele celulare rămân o unealtă educațională extrem de utilă, dată fiind puterea de reprezentare care stă la baza lor. Am arătat deja cum putem modela cu ajutorul acestora un fenomen comun prezent în natură și în mediile sociale, ne mai rămâne doar să punem în practică conceptele prezentate.

Pentru a putea atinge scopul articolului, acela de a construi un simulator de automate celulare, avem nevoie de unelte ajutătoare. Acestea pot fi după caz plăci de textolit, tranzistoare, lămpi, ansambluri hidraulice sau piese LEGO; va trebui însă să mă credeți pe cuvânt că cea mai simplă cale de a implementa un automat celular este scrierea unui program, orice astfel de mașinărie teoretică fiind echivalentă cu cel puțin un subset al unui automat Turing. Din motive în principal egoiste, dar și pentru că doresc să împing mintea cititorului într-un anumit șablon de gândire, aleg să scriu programul care simulează automate celulare în Haskell; nu în C, Python, Java, Ruby sau ce alte fetișuri mai au programatorii în ziua de astăzi, ci într-un limbaj funcțional, care poate transpune în mod natural concepte matematice elementare precum funcțiile în construcții care mai apoi vor rula pe calculator.

Există deci câteva motive pentru care merită să parcurgeți articolul de față și pe cele ce-i vor urma: (mai mult…)

dinamica traficului, un model

duminică, 5 aug. 2012, 17:29

DEX dă termenului de trafic o definiție particulară și cvasi-improprie:

TRAFÍC, traficuri, s. n. 1. Totalitatea transporturilor de mărfuri sau de persoane care se fac pe o anumită cale de comunicație, cu anumite mijloace de transport, într-un interval de timp și în condiții precizate. ♦ Totalitatea legăturilor de telecomunicație stabilite într-un anumit interval de timp și în anumite condiții tehnice.

În fapt traficul este sinonim cu conceptul abstract de transport, care presupune un spațiu S al cărui obiect o (nu neapărat unicul) poate fi mutat de la un punct x_1 către un alt punct x_2. Mutarea va duce astfel la transformarea lui S într-un alt spațiu, tot S, însă cu poziția lui o schimbată [i]. Ținând cont de faptul că două obiecte distincte o_1, o_2 \in S nu pot ocupa aceeași poziție la un moment dat – sau, dacă ar fi să ne luăm după definiție, în același spațiu dat -, dorim să modelăm transportul unei mulțimi (posibil infinite) de obiecte prin S.

Complexitatea deloc redusă a problemei prezentate mai sus mă obligă să îi aduc simplificări acesteia din urmă. Cazul particular ilustrativ în acest sens este o găselniță a unor matematicieni și calculatoriști celebri – printre care se numără și John von Neumann -, anume automatul celular – mai cu seamă cel unidimensional, ale cărui proprietăți le voi enunța în cele ce urmează. (mai mult…)

  1. A se observa că definiția face complet abstracție de natura spațiului sau a obiectelor aflate într-însul. La urma urmei nu ne interesează dacă avem de-a face cu vaci, saci de făină sau biți, elementele ce țin de detaliu – cum ar fi de exemplu un protocol de transport – fiind lăsate în totalitate implementării. [↩]
« Articole mai vechi