La mulți ani România!

Lipsea, cred, un moment de genul acesta, ca să mă apuc să mai scriu ceva. Iar prin moment, nu înțeleg ocazia festivă, de a sărbători o zi națională, ci mai degrabă statul treaz, „în interes de serviciu”, pe la 4 dimineața.

Acum un an de zile, pentru prima dată în viață, dădeam un chef de 1 decembrie. Trebuia să fiu departe de țară, ca să aibă vreun sens pentru mine chestia asta. Departe de mine ideea de patriotism. La urma urmei, a fi patriot, înseamnă a crede că o națiune e superioară altora, din simplu motiv că te-ai născut tu în ea. Și hai să fim realiști, nu suntem superiori. Cu toate astea, român fiind, aparții unui grup.

Uneori ne merge rău, alteori ne merge bine. Nu poți să fii român part time. Nu poți să trăiești într-o țară, iar când auzi vorbindu-se de ea, să strâmbi din nas ca și cum ai mirosi brânza ce ai uitat-o într-un colț al frigiderului acum o lună de zile. Suntem un produs al acestui mediu. Suntem ceea ce suntem, pentru că cei din jurul nostru sunt ceea ce sunt. Personalitatea noastră s-a format printre oamenii de aici, iar dacă ne-am fi născut în altă parte, poate că acel copil, născut acolo, ar fi dus-o mai bine, dar persoana de aici, care se întreabă cum ar fi fost, nu ar fi existat niciodată.

Anunțuri
Published in: on Decembrie 1, 2010 at 06:23  Comments (1)  

Începe școala

Da, poate că era și timpul, nu că nu aș fi avut ceva mai bun de făcut, dar nu prea aveam unde să stau. M-am mutat vara asta… ca să mă exprim românește, ca țiganul cu cortul.

Am trecut prin căminul 2, ca să văd cum e la „cămin renovat”. Știți cum e? Păi imaginați-vă o cameră mică, de cămin. Apoi, mai imaginați-vă că în camera aia mai înghesui și o baie, mică și ea, dar care ocupă spațiul necesar unor dulapuri decente. Și ca treaba să fie românească, pentru baia respectivă se vor cumpăra cele mai ieftine robinete găsite pe piață, care pe mâna brutelor de studenți nu au nici o șansă. Și nu, nu vine nimeni să le repare, stați liniștiți.

În drumul dinspre căminul 2 înspre 7, am trecut și prin Gruia(mersi Marius), ca în urmă cu câteva zile să mă întorc în vechea mea cameră, de 3 ani de zile. Lipsit de compania bunilor lui tovarăși, gândacii, exterminați până la unul(sigur unul a mai rămas pe undeva), frigiderul nostru a cedat de plictiseală. Că tot veni vorba de chestii care cedează, iarna trecută, când m-am întors în cămin, mi-a cedat laptopul. Să fie oare conicidență?

Ca să renunț la nota pesimistă, hai să găsim un subiect mai vesel. De exemplu cel din titlu: începe școala. Yeeeeei! (nu cred că am exprimat bine sunetul pe care îl scoți când îți cade ceva pe picior, dar imaginați-vă ceva de genul). Am fost azi la primul laborator, unde nu a venit nimeni. Început promițător, la fel ca în anul 1(din nou coincidență)?

Uitându-mă la ce am mai postat în ultima vreme, îmi dau seama că mi s-au rărit destul de mult cugetările despre viață. Cred că abia acuma înțeleg cu adevărat o chestie citită pe undeva, mai demult: când un om suferă de lipsă de ocupație, începe să filosofeze. Începe să-i pese de încălzirea globală, de copii săraci din lumea a 3-a sau de ce și-a mai băgat Băsescu în ureche. Când ți se sfâșie inima de grija acestor lucruri, remediul e simplu(și e naturist): pune mâna și fă ceva. Apucă-te de un proiect personal, get a job(apropo, mai nou se angajează cocalari), sau măcar fă din când în când curat prin cameră(da, da, la tine mă refer, nu te fă că plouă).

Nu în ultimul rând, pentru a diminua riscul de a mă trezi cu piuneze prin așternut, tre să amintesc și de Wii-ul lui Giuri. Da mă e cu măușăn plus. Și e alb(deocamdată). Și nu mai zic nimic, că după aia se poate crede că îl laud pe bune.

Published in: on Septembrie 27, 2010 at 21:00  Lasă un comentariu  

Ne trebuie o monedă de 23 de bani

Întrebare: ce faceți cu monedele pe care le primiți rest de la magazin? Și hai să nu ne gândim la cei mai fericiți dintre noi, pe care soarta i-a înzestrat cu un compartiment pentru monede la portofel. Să-i luăm de pildă, pe cei ca mine, care primesc în fiecare zi câte o mână de monede, apoi vin seara acasă, și le pun lângă celelalte monede, primite în zilele trecute. Și uite așa, se tot adună. Ieri am făcut fericită o vânzătoare de la non-stop, ducându-i la schimbat toata grămada, ce totaliza 15 RON(da, o sută cinzeci dă mii, numa metal). Privind la acea grămadă de monede, ce, pe zi ce trece, devenea deranjant de mare, am stat să mă gândesc care ar fi soluția pentru a diminua numărul de monede primite ca rest. Știu că se poate trișa, folosind cardul, dar încearcă să plătești cu cardul, atunci când iei pâine de la tanti de peste drum :P. În primul rând, am calculat câte monede primim în medie, ca rest, după ce cumpărăm ceva. Am făcut presupunerea că e la fel de probabil să primești orice sumă între 1 și 99 de bani, și am scris un mic script care să facă media(presupunând că vânzătoarea e suficient de amabilă să ne dea numărul minim de monede – just for other nerds: nu vă faceți griji, nu îi dăm bietei vânzătoare o problemă NP completă, ci alegem metoda greedy, care ce e drept, nu dă numărul minim de fiecare dată). Mi-a ieșit că pentru actualul sistem monetar(50, 10, 5 și 1 ban), primim în medie la un rest 4,94 monede. Dacă nu luăm în calcul monedele de 1 euro/dolar sau peste, americanii primesc în medie, ca rest, pentru o sumă cuprinsă între 1 și 99 de cenți, 4,16 monede(cu monede de 50, 25, 10, 5 și 1), iar cetățenii europeni din spațiul euro, doar 3,37 monede. Acuma nu vreau să fac din post-ul ăsta o nouă critică a sistemului românesc, aducând de pildă, ca argument, faptul că românii se simt mai nefericiți din cauză că au buzunarele mai grele(a trecut vremea când a avea buzunarul mare, era semn de prosperitate, acuma e semn că nu ai card), dar cifrele de mai sus vorbesc de la sine. Din fericire, am și soluția pentru a îmbunătăți semnificativ nivelul nostru de trai: o monedă de 23 de bani(cum secretul originalității e să-ți știi ascunde sursele, vă rog nu dați click aici). Cu o monedă de 23 de bani, numărul mediu de monede primite ca rest, devine 3,97. Practic am primi aproape cu o monedă mai puțin, de fiecare dată când cumpărăm ceva. .

Published in: on August 29, 2010 at 23:05  Comments (4)  

Cu bicicleta prin Cluj

Un pic nostalgic fiind, după Lyon, am aflat bucuros că și la noi în Cluj sunt biciclete. Pe unde? Pe lângă sala sporturilor, de la 10 dimineața la 10 seara. Se împrumută gratis, pentru 2 ore, doar pe baza buletinului și a unui formular ce se completează pe loc.

Am fost azi cu Vlad să le testăm. De fapt am vrut să mergem sâmbătă, dar de îndată ce a parcat Vlad mașina, a început să plouă. Ne-am întors peste o oră, după ce se oprise, dar l-au pus păcatele să parcheze pe același loc, și… ia ghiciți :P. Anyway, azi a fost vreme bună, și ne-am încercat iar norocul.

Prin Cluj cu bița

Prin Cluj cu bița

Ca să fac o comparație, nu mai aveam frâna de spate la mână, ci clasicul torpedou, al Pegasului din copilărie. Pare ceva mai fragilă decât bicicletele din Lyon(cică un sfert din ele s-au stricat în prima săptămână, dar trebuie să luăm în considerare și „finețea” noastră înnăscută), dar totuși nu a părut să necheze prea tare cu mine în șa.

O altă diferență e că la noi, bicicletele sunt strict pentru agrement, nu poți să mergi la servici, luând-o dintr-o stație și lăsând-o în alta. Momentan, avem un singur centru lângă sala sporturilor, dar încă sunt optimist: Poate într-o zi o să văd și prin Cluj tipi la costum și cravată, pedalând.

Partea plină a paharului e că ai voie să o ții 2 ore, nu plătești nimic, iar dacă întârzii, nu e așa mare bai.

Per ansamblu a fost o experiență agreabilă, o relaxare după servici, și o ocazie să mai explorez părți din scumpul nostru oraș(să nu uităm că sunt abia de 3 ani în Cluj). So… cine mai vine cu mine la o plimbare? 😀

P. S. Da, mi-am lăsat barbă. Și da, așa m-am trezit eu într-o dimineață, și am decis să o las să crească. Și în ciuda ei(și a începutului de chelie), o persoană care mă vede pentru prima dată, își dă seama că am doar 22 de ani(ok, arăt mai bătrân cu 2 luni).

Published in: on August 9, 2010 at 22:06  Comments (6)  

Lobby pentru calculatoriști

Acest mesaj se adresează colegilor de facultate, din anul 3, care la anul vor să urmeze specializarea Calculatoare. Pentru ceilalți cititori, îi rog să citească doar dacă sunt interesați să știe cum decurg lucrurile la poli.

Dragi colegi,

După cum știți, în urma discuțiilor cu domnul Nedevschi și doamna Potolea, s-a ajuns la consensul de a ni se permite libertatea de a alege ce materii dorim să urmăm în anul 4, în cadrul specializării alese, cu anumite restricții. Trecând peste faptul că această libertate o are orice student dintr-o universitate decentă din vest, o să vă prezint în continuare cum stau lucrurile.

Până anul trecut, opțiunile erau reduse la două liste de materii. Aveai un trunchi comun, apoi pentru restul materiilor se alegea între două liste. Metoda asta mi s-a părut foarte proastă, deoarece dacă dorești să alegi o anumită materie(exemplu personal: vreau să fac licența cu un anumit profesor), vei fi obligat să iei celelalte materii la pachet.

Eu nu vreau să fac semestrul următor vreo materie cu Baruch, și cred că nimeni nu vrea. Unii i-ar putea lua apărarea că e un profesor corect… corect pe naiba. L-am întrebat la curs în ce ordine să mergem la colcviu, și răspunsul a fost ceva de genul: ”Prima semigrupă să meargă de la 4, cealaltă de la 6. Chiar dacă în timpul semestrului ați mers și altfel, aș dori ca la colocviu să veniți cum trebuie”. Ajuns la 6 la colocviu, stimabilul profesor avea următoarea problemă: avea n foi, iar în sală erau n+1 drone. Așa că soluția găsită a fost ca ultimele 3 drone să plece acasă, printre care s-a numărat și subsemnatul. Nu conta că subsemnatul era alfabetic, în a doua jumătate a grupei, după lista domnului Baruch aveam mai multe prezențe de la 4, așa că trebuia să îi ghicesc intenția și să vin atunci. Cine s-ar fi putut gândi să multiplice(chiar și prin copiere manuală) unul dintre subiecte, pentru ca toate cele 3 drone rămase să-și poată da colocviul. Și ca să nu se supere o dornă, chiar dacă avea 2 subiecte, a preferat să le amâne pe toate 3 pe vineri.

Dragii mei colegi, așa suntem tratați la poli, și exemplul de mai sus nu e unul singular. Problema vine de sus, fiindcă banii se dau pe numărul de studenți, nu pe calitate. E și normal că interesul e să fie cât mai mulți, și să fie tratat ca un grup, ca o cireadă de vaci de muls, și nu ca indivizi.

Totuși, în urma discuțiilor avute, am obținut un grad mai mare de individualism: Toate materiile opționale sunt în perechi. Din fiecare pereche, studenții își vor putea alege câte o materie. Nu e ca și la universitățile din afară, unde studenții trebuie să își aleagă materii încât să totalizeze numărul de credite(nouă oricum creditele nu ne folosesc la nimic, sunt doar decorative), dar este un pas în plus spre libertate. Ceea ce s-ar putea să pună însă bețe în roate acestui proiect, este sistemul informatic, conceput special să ne trateze în turme, nu individual. Deoarece fiecare student aparține unei grupe, și grupele trebuie să aibe aceleași materii, e cam greu să se introducă în calculator individualismul descris mai sus. Dacă acest lucru nu va fi posibil, atunci măcar se va ține cont de opțiunile noastre, încât cele două liste să fie pe măsura acestora.

O să vă prezint în continuare opțiunile alese de mine și o parte din colegi, împreună cu motivele alegerilor. Vă invit să discutăm aceste opțiuni, pentru a ne putea pune cât mai mulți de acord. Dacă un grup suficient de mare de studenți cu medii mari vor alege aceleași materii, sunt foarte mari șanse să putem forma o grupă care să avem materiile respective.

  • Opțional 1: Calcul paralel și distribuit. Pe lângă faptul că alternativa e Baruch, am înțeles că materia e chiar ok, profa e de treabă. Nu cred că vor fi multe discuții la punctul acesta.
  • Opțional 2: Proiectarea sistemelor de operare. Profesorul care predă această disciplină este Adrian Coleșa, după părerea mea unul din cei mai OK profesori de la poli. Materia e destul de interesantă, și în plus, alternativa este domnul Gorgan, unde examinarea este destul de strictă(cei din seria a 2-a, să întrebe colegii din prima serie despre SPG).
  • Opțional 3: Sisteme de recunoaștere a formelor. Materia aceasta cred că are legătură cu PI, mie mi s-a părut destul de interesant, și cred că reprezintă ceva de viitor, indiferent ce domeniu ați alege în continuare. Ca o bilă neagră pentru alternativă, Proiectarea translatoarelor ar fi o continuare la LFT, unde cu toată bunăvoința domnului Negrescu, nu cred că s-a învățat mare lucru. Oricum, nu știu cât de multă lume e interesată de minunata lume a compilatoarelor(nu am fost sarcastic la remarca anterioară).
  • Opțional 4: Marketing. Aici să fiu sincer am fost tentat să aleg Cultura și civilizația europeană, deoarece îmi place istoria, dar totuși marketing-ul e ceva mai util. Și la examinare, am auzit că se face similar cu management-ul, și e mai puțin de memorat.
  • Opțional 5: Programare paralelă. Tendința în domeniul calculatoarelor este de a lucra distribuit, pe mai multe sisteme. Această materie întregește gama de cunoștințe pe care trebuie să le avem, legate de ramura respectivă.
  • Opțional 6: Proiectarea rețelelor de calculatoare. Din nou, tendința din domeniul nostru dă toate argumentele. Și bazele de date au importanța lor, dar cred că rețelistica primează.

Aștept în continuare păreri pro și contra. Deasemnea aș dori să știu câți ar fi de acord cu materiile mai sus menționate, eventual dacă aveți alte păreri, așa că nu vă sfiiți la comment-uri. Până la urmă fiecare este liber să completeze ce dorește în cererea depusă, și sincer sper ca opțiunile să fie respectate. În caz contrar, sper să avem cât de cât o uniformitate, pentru a nu fi forțați din nou să alegem materii pe care chiar nu le vrem.

Published in: on Mai 26, 2010 at 22:51  Comments (15)  

Indecidabilitate și intractabilitate

Continuând seria de posturi de cultură generală pentru programatori(am mai zis că nu sună bine în română), o să încerc să alunec puțin dinspre tehnic înspre filosofic.

Este de bun simț să admitem că știința progresează, dovadă că în fiecare război se găsesc noi mijloace de ucide oameni(dacă ne gândim bine, și calculatoarele au fost construite tot cu ocazia războiului). Cu toate că progresează, în secolul 20 s-a ajuns la concluzia că știința nu ne va putea da niciodată toate răspunsurile.

O expresie filosofică a acestui adevăr o aduce Blaga, afirmând că nu putem trece, cu ajutorul cunoașterii, de limita impusă de Marele Anonim. O abordare mai pragmatică și recunoscută de lumea științifică vine de la Kurt Gödel, care prin 1931, arată nu numai că sistemul nostru de axiome este incomplet, ci și că nu avem cum să construim unul complet.

Ce înseamnă acest lucru? Păi axiomele sunt niște adevăruri pe care se bazează toate cunoștințele noastre. Pornind de la aceste axiome ca fundație, începem să construim: cărămidă cu cărămidă, găsim noi teoreme, dar la un moment dat vrem să punem undeva o cărămidă și nu putem, pentru că acolo lipsește fundația, și fără fundație nu putem construi. Nici o problemă, s-ar zice, mai punem fundație(aka acceptăm noi axiome), dar la un moment dat iar ajungem într-un punct unde nu putem construi. Gödel a demonstrat că în afară de sistemele triviale, oricâtă fundație am avea, tot nu vom putea construi orice. La un moment dat, se va enunța o teoremă, despre care nu vom putea ști dacă e adevărată sau nu, oricât ne-am strădui.

Revenind la calculatoarele noastre, nu știu câți și-au pus întrebarea ”Ce se poate calcula?” sau ”La ce întrebări ne poate răspunde calculatorul?”. Din mulțimea de întrebări posibile, nu o să le alegem pe cele de genul ”what is the answer to life the universe and everything”… asta e ușoară, răspunsul e 42(întrebați pe google dacă nu mă credeți). Ne vom lega de acum încolo de întrebările la care se poate răspunde cu DA sau nu, numite și probleme de decizie. Exemple de astfel de întrebări sunt ”Este 25 mai mare ca 20?”sau ”Se poate găsi un drum pe harta României, care să treacă prin fiecare oraș o singură dată?” sau încă ”Dacă rulăm algoritmul ăsta, o să se termine vreodată?”.

Evident, pentru întrebări de genul primeia, răspunsul se găsește imediat. Sărim deocamdată peste a doua, și ne uităm la cea de-a 3-a. Ca să o exprimăm mai precis, vrem să scriem un program care să analizeze un alt program, și să ne spună dacă se termină, sau buclează la infinit. Tot prin anii ’30, Alan Turing a demonstrat că un astfel de program nu se poate scrie. Spunem deci, că această problemă este indecidabilă. Desigur, putem să rulăm efectiv programul care se cere analizat, iar dacă se termină am câștigat: putem răspunde cu certitudine DA. Dacă în schimb după 10 minute sau după 10 luni, programul tot rulează, nu avem de unde ști dacă face calcule utile și la un moment dat va ajunge la rezultat, sau s-a împotmolit într-o buclă infinită.

Dacă ne întoarcem la a doua întrebare, care pentru cunoscători se numește problema ciclului Hamiltonian, observăm că putem găsi o soluție: încercăm fiecare drum posibil în parte, iar la un moment dat, fie am epuizat toate drumurile, fie am găsit un drum cu proprietatea cerută. Deși această abordare va da până la urmă un răspuns la întrebare, avem de încercat o groază de variante. Mai rău, pentru cei ce au citit postul anterior din această categorie, putem spune că algoritmul are o complexitate exponențială, adică să zicem că avem un calculator suficient de rapid care să rezolve problema pentru un anumit număr de orașe în timp rezonabil, dacă mai introducem chiar și un număr foarte mic de orașe în ecuație, nu se va mai găsi răspuns într-un timp acceptabil.

Partea cu adevărat proastă la problema de mai sus este că nici până în zilele noastre nu s-a găsit vreo abordare mai bună, care să rezolve problema în timp polinomial. Singurul lucru care mai salvează cât de cât situația este faptul că dacă cineva găsește din întâmplare un drum, putem verifica destul de repede(în timp polinomial) dacă soluția este corectă sau nu. De fapt, foarte multe probleme cu care ne întâlnim în practică au proprietatea de a li se putea verifica soluția în timp polinomial. Vom nota această clasă de probleme cu NP. Desigur, în această clasă de probleme intră și cele simple, care se pot rezolva în timp polinomial, a căror clasă o notăm cu P, deci avem P \subseteq NP.

Una dintre problemele mileniului, pentru care se oferă un premiu de 1 milion de dolari, este verificarea dacă e incluziune strictă, sau avem egalitate, între cele două clase de probleme. Partea care stă în calea egalității, e un anumit grup de probleme, numite NP-complete, sau intractabile, de genul celei amintite mai sus, pentru care nu s-a găsit încă un algoritm polinomial, dar nici nu s-a putut demonstra că nu ar exista. Este surprinzător faptul că toate aceste probleme, din domenii atât de diferite, se pot reduce în timp polinomial una la alta. De exemplu, dacă reușim să găsim o soluție în timp polinomial la problema împărțirii unei mulțimi de numere, în două mulțimi cu sume egale(pentru olimpicii la info care cred că au soluția, trebuie să repet că vreau timp polinomial, nu pseudopolinomial), vom putea rezolva în timp polinomial și problema ciclului Hamiltonian amintită mai sus.

Acest fapt remarcabil, posibilitatea reducerii, ne ușurează de multe ori viața în practică. Când întâlnim o problemă la care nu putem găsi soluție în timp polinomial, putem încerca să o reducem la o problemă NP-completă cunoscută, iar dacă reușim reducerea, înseamnă că am întâlnit o problemă cu care informaticienii și matematicienii se confruntă fără succes de decenii, și probabil ar fi cazul să ne petrecem timpul cu ceva mai util, de exemplu să încercăm să dăm o soluție aproximativă, sau să facem un backtracking cât mai optimizat.

Concluzia pe care cititorul ar trebui să o tragă din cele citite mai sus, este că nu orice problemă se poate rezolva cu ajutorul calculatorului, și chiar și pentru cele care se pot rezolva, nu putem găsi tot timpul o rezolvare care să dea soluția în timp acceptabil. Cu toate acestea, putem construi soluții imperfecte, care să ajute utilizatorul, și care să încerce să se apropie cât mai mult de perfecțiune.

Published in: on Februarie 19, 2010 at 16:53  Comments (3)  

Atenție la țepe cu telefonul

Scriu postul acesta pe fugă, fiindcă am de prins un tren, însă consider necesar să avertizez lumea despre persoanele care dau țepe cu telefonul.

M-a sunat un tip, care zicea că e de la Cosmote, și că în urma unei promoții am câștigat o reducere la abonament cu 50%, minute în plus și alte minunății. Yupiii… Pentru a activa acest premiu, trebuie doar să tastez *444* … nu mai stiu ce, apoi un număr de telefon, pe care mi-l dictează el.

Dacă nu v-ați prins deja, ăsta e serviciul pentru a încărca o cartela cu credit, și fiind pe abonament, poți să încarci cu destul de mult… cîteva miloane chiar. Mișto, nu?

Din fericire eu m-am prins, și i-am notat numărul. Îl pun aici, just for fun, în speranța că vreun nebun va da de el și se va apuca să îl hărțuiască: 0769.14.26.21.

Partea și mai faină e că numărul fiind de cartelă, ”glumețul” nostru nu poate fi prins. La relații cu clienții mi-au spus că trebuie să mă duc la un magazin de-al lor, să completez o plângere, ș.a.m.d. Iar eu am un tren de prins.

Tot ce pot să fac este să scriu chestia asta pe blog, în speranța că cineva o va citi, și nu va lua țeapă când va fi sunat(deși cred că cititorii mei sunt mai inteligenți decât ai lor, așa că nu vor fi probleme).

Published in: on Februarie 10, 2010 at 15:06  Lasă un comentariu  

The big O

Fiindcă în viața reală nu prea se mai întâmplă nimic intersant, am decis să scriu o serie de articole legate de calculatoare. Asta și deoarece temele abordate de mine până acum nu se prea potrivesc cu titlul blogului ”Just a coder”. Categoria nou creată se numește ”General knowledge for programmers”(parcă nu ar suna bine în română), și doresc să scriu o serie de post-uri, despre concepte des întâlnite în viața de coder, dar de care lumea se cam sperie. Posturile din această categorie nu se vor exhaustive, nici măcar pe departe. Tot ce doresc să prezint e un skimming prin conceptele abordate, după care cititorul interesat poate da un search pe Google pentru a se documenta corespunzător.

Post-ul de azi se referă la notația asimptotică, numită în engleză ”the big O notation”, și se adresează în special celor care au nedumeriri atunci când aud că un algoritm are complexitatea O(n^2), în timp ce altul are doar O(n \log n).

Complexitatea unui algoritm nu e altceva decât o măsură a numărului de operații pe care algoritmul îl face. Să zicem că avem un algoritm care găsește elementul maxim dintr-un vector oarecare(sau dacă vreți, listă).

Dacă cititorul s-a încumetat să ajungă până aici, probabil îi este familiar conceptul de vector, și știe că pentru a determina elementul maxim, trebuie să inițializeze o valoare cu primul element, apoi să o compare pe rând cu celelalte. Mai concret vorbind, dacă vrem să aflăm care este cel mai înalt elev din clasă, le cerem să intre pe rând pe ușă, punându-l pe primul drept etalon. De fiecare dată când intră cineva mai înalt decât etalonul, elevul mai înalt devine etalon. Evident, ultimul elev rămas drept etalon este cel mai înalt din clasă.

Până acum probabil ne-am dat deja seama că numărul de operații depinde de numărul de elemente din vector, sau de numărul de elevi din clasă, pe care în general îl notăm cu n. Mai exact, operațiile efectuate pentru determinarea maximului sunt comparații, în număr de n-1(deoarece pe primul element nu avem cu cine îl compara). Cu toate acestea, vom zice că algoritmul are complexitatea O(n), și nu O(n-1). În primul rând, acel 1 nu este relevant, pentru că oricum programul va face anumite operații de inițializare, pe care nu trebuie să le luăm în calcul, și în al doilea rând, faptul că îl luăm doar pe n, ne simplifică mult calculele, și ne ajută de multe ori să ”vedem” mai bine problema.

Așa cum multă lume își poate imagina, la apelul unei funcții care face ceva util, se fac anumite operații(punere parametri de apel și adresă de întoarcere pe stivă, inițializare variabile, etc. – dacă aceste operații nu sunt cunoscute, cititorul nu trebuie să își facă griji, deoarece sunt irelevante în acest post -). Vine atunci întrebarea ”de ce aceste operații nu se iau în considerare când măsurăm complexitatea?”. Răspunsul este că această complexitate nu trebuie să ne dea numărul exact de pași efectuați de algoritm, ci ne interesează mai mult cum se modifică acest număr de pași, dacă dimensiunea datelor problemei se modifică.

De exemplu, dacă avem un algoritm cu complexitate O(n), care rulează pentru n=1000, timp de 10 secunde, și îl mărim pe n cu 1, folosind regula de trei simplă, obținem un timp de execuție de 10.01 secunde, care practic nu diferă în mod vizibil de primul. Chiar dacă îl dublăm pe n, vom dubla doar timpul de execuție, la 20 de secunde, care rămâne tot în limitele rezonabile.

Să ne închipuim acum un algoritm de complexitate O(2^n), care rulează tot pentru n=1000 timp de 10 secunde. Dacă îl mărim pe n doar cu 1, cunoscând că 2^{n+1} = 2 \cdot 2^n, ne dăm seama că timpul de execuție se dublează. Dacă îl mărim pe n cu 10 doar, adică de la 1000 la 1010, timpul de execuție va crește de 2^{10} = 1024 ori, adica de la 10 secunde la aproape 3 ore. Timpul este încă rezonabil, dacă lucrăm la o problemă suficient de importantă, cât să merite să așteptăm 3 ore, dar ce ne facem de exemplu dacă ne trece prin cap să dublăm dimensiunea datelor problemei? Astfel de probleme se numesc probleme intractabile, și vom discuta mai multe despre ele într-un post viitor.

Am observat mai sus că pentru calcularea complexității unui algoritm, nu trebuie să ținem cont de constantele aditive care apar, deoarece acestea nu influențează semnificativ numărul de operații, atunci când dimensiunea datelor problemei se modifică. Vestea bună este că ”big O” ne scapă nu doar de constantele aditive, ci și de alte neplăceri.

Să luăm un alt exemplu, calcularea sumei elementelor de deasupra diagonalei principale, a unei matrici. Aceste elemente sunt în număr de 1 + 2 + \ldots (n-1) = \dfrac{n(n-1)}{2}, deci acesta este numărul de adunări pe care îl vom face. Dacă scriem acestă valoare sub formă polinomială, avem \dfrac{1}{2} n^2 - \dfrac{1}{2} n. Ca să trecem la notația asimptotică, trebuie să-l luăm doar pe n la puterea cea mai mare, fără a ”căra” după noi constantele multiplicative, aditive, sau puteri mai mici ale lui n, deoarece pentru valori suficient de mari ale acestuia, doar puterea cea mai mare din polinom va contribui semnificativ la creșterea numărului de operații. Vom obține complexitatea pentru această problemă O(n^2). Denumirea de notație asimptotică vine de la conceptul de asimptotă din matematică, dar n-o să intru în detalii aici.

Ar trebui ca deja să ne fi prins de șmecherie : pentru a calcula complexitatea unui algoritm, putem număra operațiile efectuate, fără a ține cont de detalii, iar acea valoare, deși oarecum aproximativă, ne va da o bună estimare a creșterii numărului de operații, la creșterea dimensiunii datelor problemei.

O ultimă chestiune, pentru a răspunde la o întrebare pe care unii cititori și-ar putea-o pune: ”Cum numărăm operațiile, de ajungem uneori la logaritmi, în formula complexității?”. Pentru a răspunde la această întrebare e necesar să cunoaștem conceptul de arbore binar. Chiar dacă o problemă nu specifică în mod explicit această structură, rezolvarea o poate sugera, prin împărțirea structurii de date în două jumătăți egale, și aplicarea algoritmului pe fiecare jumătate. Astfel, devine necesară parcurgerea unui astfel de arbore de la rădăcină, până la o frunză, ceea ce face ca numărul de operații să fie proporțional cu înălțimea acestuia. Un exercițiu pe care îl las pe seama cititorului care nu a adormit încă, este verificarea sau demonstrarea faptului că înălțimea unui arbore binar echilibrat este de ordinul \log_2 n, unde n este numărul de noduri al arborelui.

Published in: on Februarie 5, 2010 at 01:54  Lasă un comentariu  

Student Erasmus la Lyon – partea a IX-a (epilog)

Pe un forum de întrebări și răspunsuri, am găsit odată o referire la secțiunea ”Erasmus Lyon” din blogul meu, ca ”bazat pe o poveste adevărată”. Fericit că totuși povestea mea se bazează pe întâmplări reale, și nu pe vreun film văzut(dacă tot aș plagia, aș plagia o carte, fiindcă filmele le vede toată lumea), m-am decis să o închei acum, la vreo lună după întoarcere.

Era vreo 5 dimineața, când Cipri își trăgea troler-ur greu, de 30 de kilograme(pe atunci n-avea de unde să-i cunoască greutatea, dar avea să o afle mai târziu) prin zăpada depusă cu o noapte înainte. Orașul părea mai primitor ca niciodată, parcă tocmai pentru a-i face în ciudă că pleacă. Metrou, TGV, Paris, din nou metrou, și iată-ne așteptând autobuzul spre aeroport, într-o zonă din Paris, care semăna cu o zonă oarecare dintr-un oraș românesc. Atmosfera românească s-a simțit mai ales când eroul nostru a încercat să urce în autobuz, și mișcându-se încet, din cauza troler-ului, în îmbulzeala generală n-a mai prins loc, fiind nevoit să meargă peste 15 minute, în autobuzul cu italieni. Ajuns la aeroport, se crezu scăpat, dar cum birocrația are un braț mai lung decât legea, îl ajunse și acolo, trimițându-l de la o coadă la alta, pentru a-și plăti excedentul de bagaj, despre care abia acum află cât cântărea. Deși erau niște cozi imense, funcționarii nu se grăbeau. Atunci când Cipri a cerut cuiva să se grăbească, fiindcă va pierde avionul, i s-a răspuns să stea liniștit, că nu pleacă avionul nici unde(varianta ardelenească ar fi fost ”poate să plece, că la mine-i biletul”). Și într-adevăr, nici avionul nu s-a grăbit să plece.  Pilotul a asigurat totuși pasagerii că nu va fi întârziere mare, fiindcă bate un vânt din spate, care va purta avionul mai repede… foarte liniștitor. După câteva turbulențe în aer și o întârziere rezonabilă, Cipri ajunse pe aeroportul din Cluj, unde Vlad îl aștepta cu mașina. Prima mașină în care a pus piciorul, după 4 luni de zile.

După toate peripețiile de pe drum, au urmat două săptămâni de stat acasă. Două săptămâni care au început foarte bine, revăzându-mi familia, dar după care am găsit noi profunzimi în vorba lui George Bernard Shaw ”A perpetual holiday is a good working definition of hell”.

După două săptămâni fără net, când în sfârșit a ajuns la Cluj, laptopul meu a cedat nervos. Mai exact, a cedat lipitura făcută la Lyon, și într-o dimineață, tot ce am putut face a fost să constat decesul, și să-mi iau pe un stick documentele mai importante, folosind restul de baterie rămasă.

Mergând să echivalez materiile, am trecut întâi pe la decanat, de unde am fost trimis la secretariatul catedrei, unde ia ghiciți pe cine am întâlnit? Am fost foarte surprins să văd că de data asta e mult mai amabilă, distinsa noastră secretară, ca și cum ar fi fost ceva putred la mijloc. Și desigur că a fost. A trebuit să merg pe la toți profesorii la care am avut de echivalat, să îmi semneze o cerere(din fericire nu au fost mulți, ca să mă pot bucura și eu de sesiunea din țară). Și după toată plimbarea, tot nu a fost mulțumită, fiindcă la o materie aveam cu un punct mai puțin decât nota care se echivalează cu 10, așa că iar a trebuit să vorbesc cu profesorul, să-mi echivaleze dumnealui, personal.

Tot întors de la Erasmus, am putut vedea marele avantaj de a sta la cămin. În mod normal, studentul, când se întoarce după 4 luni, chiar pe finalul semestrului, e cam în plop cu materia, acesta fiind și cazul meu. Chiar dacă am avut la dispoziție toate materialele de curs, nu a fost același lucru cu a-mi bate la cap colegii, și rezultatul a fost că am reușit într-o săptămână să-mi termin proiectul la grafică, săptămână la începutul căreia mi-a cedat și laptopul.

Ar trebui să închei, vorbind despre impresia generală… dar cred că v-au ajuns 9 capitole. Restul, rămâne de descoperit pentru cine ar vrea să încerce. Va trebui să mă credeți pe cuvânt că merită. Singurul regret pe care îl am, sunt oamenii din Lyon, care mi-au fost aproape, în cele 4 luni, și pe care cine știe când(dacă) o să-i mai văd.

– The End –

Published in: on Ianuarie 24, 2010 at 22:39  Comments (3)  

Student Erasmus la Lyon – partea a VIII-a

Mai am câteva zile și plec acasă. O să plec cu ceva emoții, ce e drept, fiindcă din ce am auzit, zilele trecute foarte multe zboruri au fost amânate, din cauza ninsorii. Știu că sună tentant să-mi petrec Crăciunul în Paris(de acolo trebuie să iau avionul), dar aș prefera să las experiența asta pentru alt an.

Au trecut aproape patru luni, de când am ajuns aici la Lyon. Patru luni care au trecut ca patru zile. Patru zile în care s-au petrecut așa de multe lucruri, că dacă mă întreabă cineva cum a fost, încercând să formuleze un răspuns mintea mea face stack overflow, și răspund „fain”. Despre o parte din întâmplările de aici, am încercat să scriu. Am scris pentru alții, care poate sunt indeciși dacă vor să încerce experiența Erasmus sau nu și pentru Cipri din viitor, care poate va fi un bătrân senil și n-o să-și mai amintească.

Zilele trecute a început să plece lumea. Abia acuma îmi dau seama că sunt oameni care mi-au fost apropiați, și pe care n-o să-i mai văd, sau o să-i mai văd doar în trecere(vorba unei bune prietene de aici, „chiar dacă ne mai vedem, n-o să mai fie același context”). Când am plecat de acasă, am știut că o să mă întorc și o să găsesc lucrurile așa cum le-am lăsat, sau pe aproape(nu aveam în minte să regăsesc același președinte și același premier, dar partea plină a paharului e că românii sunt un popor care știu să acorde a doua șansă). În schimb, chiar dacă o să mă întorc în Lyon – și sigur o să mai vin, măcar în vizită – nu voi mai întâlni aceiași oameni.

Revenind la trecut, adică la ultima lună, în care nu am mai scris, pot spune că a fost una destul de ocupată. În mod normal, sesiunea de examene e în ianuarie, dar fiindcă în ianuarie, am și sesiunea în țară, mi-am dat examenele săptămâna asta. Profesorii au fost foarte înțelegători, nu au avut nimic împotrivă să dau examenele mai repede.

Spre deosebire de sistemul românesc, sesiunea de examene aici ține o singură săptămână. La prima vedere, pare puțin, dar nu e. În sistemul românesc, avem nevoie de 3 sau 4 săptămâni de sesiune, pentru că la examene se cere de obicei să se reproducă lucruri făcute la curs, seminar, sau subiectul de anul trecut, vopsit(nu generalizez). În consecință, chiar dacă studentul a fost la cursuri, a studiat în timpul semestrului, are nevoie de câteva zile pentru a memora acele lucruri. La ENS, în afară de examenul de franceză, toate examenele au fost „cu cărțile pe față”, adică avem voie să folosim materialele de curs. Subiectul este dat în așa fel încât să oblige studentul să-și folosească procesorul, nu hardul, și în plus se testează și capacitatea de decizie. Sunt prea multe exerciții, pentru a putea fi rezolvate în timp util(la parțial la algoritmică, de exemplu, cel mai bun a făcut cam jumătate), și atunci studentul trebuie să își dea seama ce poate face în timp util, și să sară peste părțile pe care le consideră dificile.

Pe lângă examene, la evaluare mai contează la anumite materii și temele de casă. Partea care mi s-a părut amuzantă e că deși am colegi foarte buni, care iau studiul în serios, au tendința de a-și începe tema cu câteva zile înainte de deadline, apoi să ceară o prelungire a acestuia. Dacă tot am ajuns la partea cu temele, profit de ocazie ca să mă laud puțin: am reușit să fac două teme de 20 😀 , dintre care la una, pentru că nu mi-a zis nimeni că am voie să o scriu de mână, și pentru că implica multe calcule matematice, am scris 22 de pagini in \LaTeX.

Vă urez sărbători fericite, și toate cele bune!

Published in: on Decembrie 19, 2009 at 14:23  Comments (2)