Despre matematizarea excesivă a algoritmilor

Postarea aceasta are, aparent, mai mult sens pe blogul celălalt, tehnic. Din păcate, nu e vorba de aspectele tehnice ale algoritmicii, ci de niște metehne de la nivel uman – așa că ne întoarcem la Musca de pe parbriz să scriem despre ele.

Sunt într-o situație privilegiată. Am terminat facultatea de informatică din Brașov. De fapt e matematică-informatică dar o secție de ‘informatică pură’, lucru care mă face să mă laud, indiferent de consecințe, cu o diplomă de absolvent de informatică. În timp ce studiam la facultate am lucrat ca laborant la facultate și apoi am fost invitat să țin laboratoare de sisteme de operare. Am, în acest fel, o cunoaștere intimă a mediului universitar, dobîndită din ani de studiu dar și ani de muncă din cadrul staff-ului facultății.

Problema: zilele astea am fost pus față în față cu un curs de algoritmica grafurilor. Nu mi-a plăcut niciodată algoritmica grafurilor, și prima oară cînd a trebuit să dau examen la grafuri nu m-am prezentat (am fost prostul care nu a trecut pentru că nu s-a prezentat). În total, în cele din urmă, am ajuns să trec de patru ori acel examen într-o formă sau alta: de două ori în timpul facultății, apoi o dată la un master (neterminat de către mine) și a patra oară la masterul pe care l-am și terminat. Și am zis același examen de patru ori pentru că algoritmica grafurilor e o materie foarte ‘mică’ – cu foarte puține lucruri care să se preteze unui examen.

Dacă pînă acum nu am avut un răspuns, acum îl am. Știu de ce am urît materia aceea ani de-a rîndul, de ce mi s-a părut cea mai dificilă și încurcată materie. E foarte simplu, algoritmii sunt de neînțeles, explicațiile sunt stîngace și materia în sine este pe alocuri insuportabil de încîlcită. Ceea ce mă duce la o întrebare:

De ce atîta matematică în informatică? Știm cu toții răspunsul, dar nu prea îl articulăm. E atît de multă matematică în informatică pentru că, în realitate, nu există profesori de informatică. Nu există profesori în informatică ce la rîndul lor să pregătească alți profesori în informatică. Informatica e copilul nedorit al matematicii – e copilul rebel care nu ascultă de nimeni dar are mai mult succes în viață. Iar profesorii se comportă ca și cum copilul ar trebui să se întoarcă la casa lui și să se așeze.

Cursul pe care îl aveam în față avea atît de multă matematică pentru că nimeni nu vrea să explice lucrurile într-un limbaj natural, care apoi să fie transpus în algoritmi. Vectorii sunt ‘funcții’, indexarea începe de la 1, se lucrează cu mulțimi și datele se încarcă cu valoarea infinit (∞). La sfîrșitul algoritmului rezultatul e o mulțime – și nimic nu se returnează, nimic nu se dealocă, nimic nu se afișează.

Să luăm un exemplu. Algoritmul lui Prim, sau, mai bine zis, algoritmul DJP (Dijkstra-Jarnik-Prim)  care e prezentat în felul următor:

Care e problema? În primul rînd, prezentarea algoritmului e neinteligibilă, și cere asistență din partea cuiva capabil să înțeleagă algoritmul. Explicația algoritmului ia fix 20 de secunde și bate orice pseudocod – mi-a fost dată de către cineva foarte avizat în materie, dovadă că există ȘI alt fel de a explica problema. Explicația mi-a demonstrat faptul că totuși, profesorii care predau nu sunt pe lîngă problemă, numai că au un set de rigori auto-impuse care îi face să trăiască într-un alt univers. Un univers în care rigoare înseamnă demonstrație matematică.

Nimic mai greșit. Nu numai că rigoarea din punct de vedere al algoritmicii nu cere rigoare matematică, dar încercarea de matematizare a algoritmului îl face confuz, neinteligibil și mai complicat decît e necesar. Mai mult, demonstrațiile ‘ajutătoare’ nu ajută la absolut nimic – demonstrațiile teoremelor sunt arbitrare și, de fapt, nematematizate. Se folosește un surogat matematic nesatisfăcător – aparatul matematic folosit pentru demonstrație este neriguros și nu se bazează (precum materiile clasice, gen analiză matematică sau algebră) pe axiome și noțiuni de bază. Noțiunile se introduc arbitrar, demonstrațiile însele sunt arbitrare, teoremele sunt aproape amuzante prin încercarea lor de a părea riguroase și rezultatul final e un student confuzat.

Nimeni nu are nimic de cîștigat din situația asta. Încercarea de rafinare a aparatului matematic pentru satisfacția matematicienilor este, în acest caz, distructivă. Demonstrațiile acestea ar trebui să rămînă în cîmpul matematicilor pur teoretice. Trebuie înțeles o dată pentru totdeauna că pseudocodul nu e un limbaj de programare; îmi e din ce în ce mai clar că nu e nici măcar un limbaj în care să descrii algoritmi, tocmai pentru că aspectele dificile ale unui algoritm pot fi ascunse într-o singură linie care ascunde real dificultatea de implementare. Exemplul meu favorit este pseudocodul pentru sortarea în O(log n). Nu știați de el?

PROGRAM Sortare log n
BEGIN
Citește n, v
Sortează v în log n
Afișează v
END

Algoritmul e auto-suficient – e clar scris, și pot demonstra cu același aparat matematic că e corect. Vă invit să faceți implementarea acestui algoritm.

Nu e cazul algoritmului lui Prim prezentat mai sus – dar e cazul altor algoritmi scriși ‘matematizat’. E o dovadă că informatica e un copil răzlețit de casă, care ar trebui situat mai degrabă în zona ‘inginerească’ decît în zona teoretică. Aspectele practice nu trebuie ignorate.

Mai spun, de asemenea că grafurile nu sunt excepțiile notabile, sunt și regula. De aceea se fac două semestre de limbaje formale și de teoria compilatoarelor la sfîrșitul cărora studenții nu numai că nu știu să scrie un parser, dar nici nu rămîn cu cunoștințele necesare pentru a intra real în scrierea unui compilator (exact obiectul cursurilor). Sau cursuri de sisteme de operare la sfîrșitul cărora studentul nu știe ce e un sistem de operare, care sunt funcțiile lui și cum se implementează așa ceva.

În cele din urmă, obsesia cu matematizarea informaticii nu poate să fie decît dăunătoare pe termen lung. Algoritmii nu sunt rigoare matematică – sunt idei. Sunt în cadrul mult mai maleabil al filosofiei, al gîndirii pure și nedemonstrabile. Mai mult algoritmii pot fi greșiți în mod absolut, dar corecți pentru problema și datele cunoscute. Algoritmii lucrează la nivel conceptual superior – și descompunerea lor e la fel de utilă ca studierea unei reacții chimice din punct de vedere al fizicii. Se poate face, dar efortul e uriaș și în cele din urmă inutil. Iar proporția de complexitate e cam aceeași cu a folosi numărul lui Avogadro comparat cu 1 mol. Comparați în orice afirmație folosirea următoarelor exprimări: 6,022 137 7×1023 particule și “1 mol”.

La fel este și informatica. O simplificare, o aplicare a fundamentelor matematice. Așa cum chimia nu invalidează utilitatea fizicii, la fel informatica nu invalidează utilitatea matematicii. Dar încercarea aberantă de a exprima informatica matematic duce la situațiile absurde în care un student de informatică, absolvent cu nota zece, nu știe să scrie un parser, sau să găsească drumul cel mai scurt într-o rețea.

Ce soluții vedeți voi pentru studenții ce studiază informatica?

PS: Și da, știu, algoritmul de sortare în log(n) e o himeră.

Comments

Despre matematizarea excesivă a algoritmilor — 12 Comments

  1. Ai uitat sa o zici si pe aia cu queriurile mysql scrise de mana, pe foaie. Sau aia cu referat, scris de mana, pentru arhitectura (pentru ca stim cu totii, copy/paste se poate face doar la calculator, conceptul de copy/paste s-a nascut de cand cu calculatorul, inainte toate lucrarile erau originale, pentru ca trebuia sa mergi la biblioteca sa cauti carti si sa stai ore in sir sa conspectezi; nu poti sa faci copy/paste dintr-o carte; aia e blasfemie).

    Nu stiu cum ai fost tu la facultate, dar eu nu simt ca as fi la o facultate de informatica. Ma simt complet deconectata de calculator. Ori e prea multa matematica, ori mi se da nota pe ortografie. Daca nu as fi avut nevoie de diploma, nu as fi dat bani pentru asa ceva. E o investitie extrem de proasta.

    Ma asteptam sa mi se ceara teorie, un oarecare nivel de abstractizare, dar si ceva practica. Sa trebuiasca sa fac niste proiecte. Un rahat. Singurul proiect pot sa il fac acum la OOP, pentru care nici macar nu conteaza ce fel de proiect e atata timp cat stiu ce e cu el. Inteleg ca se copiaza mult si calitatea studentilor lasa de dorit, dar hai sa mai vedem si ce e cu calitatea profesorilor, care e si ea execrabila.

    Si nu inteleg de ce in ceea ce priveste predatul de teme sunt atat de multe reguli, insa examenul e cea mai usoara chestie. Pot sa il dau de o mie de ori si nu am cum sa nu il trec la un moment dat. Pot sa il iau si cu 10 desi eu habar nu am ce fac la materia respectiva.

    La asta duc pana la urmarile regulile astea tampite.

    Cat despre lf, doar de la tine am auzit ca ar avea ceva legatura cu compilatoarele. Nici nu stiu de unde sa apuc materia aia.

    Si mai sunt altele, dar cred ca i made my point so far.

    P.S. Queriuri scrise de mana??? Really??? Wtf???

    • Sunt de acord cu tine că multe lucruri lasă de dorit la facultatea asta – în fond, nu e nici cea mai tare din lume. Sunt mulți oameni care sunt depășiți de materiile pe care le predau, un sentiment care încă mai rezistă după atîția ani – și eu l-am avut cînd am făcut facultatea, și nu numai eu. La ID cerințele sunt și mai slabe pentru că pînă la urmă cei care vin la ID nu vor și nu sunt capabili (90%) să dea un examen pe bune. Dezinteresul domină, și nu numai la informatică în Brașov.

      Cum bine ai notat tu, accentul nu e pus pe practică. Mă așteptam să fie mai mult accent pe partea practică, dar, din nou, lucrurile scapă de sub control. AM observat niște îmbunătățiri (da, era și mai rău), dar am avut și niște dezamăgiri. Mai țin însă minte ce dezamăgire cruntă am avut cînd, punînd accentul pe practică atunci cînd am ținut laboratorul de SO, studenții mi-au dat cu flit și au abandonat baricadele – am rămas cu doi-trei oameni care veneau doar ca să nu mă supăr eu.

      Unde vreau să ajung e că nu e numai vina profesorilor. E vina întregului mediu universitar – și tu și eu suntem supărați că suntem obligați să ne asociem cu mediul universitar actual, și cu faptul că diploma pe care o să o iei are fix valoarea pe care i-o dai tu în postarea asta. Nu avem acces la ceva mai bun. Dar țin să mai zic că există și diamante în noroi aici – și pot să-ți enumăr niște oameni care merită respect pentru munca și eforturile depuse.

      Din păcate acele diamante nu o să dea mai multă valoare diplomei mele și eforturilor pe care le-am depus. Aici e tragedia. Diploma acum nu mai are valoare pentru că s-a coborît la nivelul învățămîntului de masă. Nu pentru că eu nu aș fi muncit pentru ea, ci pentru că cei din jurul meu mi-au devalorizat-o. E vina mea, a profesorilor… a tuturor.

  2. Stiu ca sunt si diamante in noroi, dar nu vezi ca si oamenii respectivi sunt legati de maini pentru ca nu pot trece peste consensul impus de acesti dinozauri care troneaza peste facultatea asta? Si ma rog, pot sa o extind pe asta si sa spun chiar peste invatamantul romanesc.

    Cat despre studenti, ca tot avem discutia asta de prea multa vreme, sunt studentii pe care acesti profesori ii merita. Tu erai doar un laborant. Dar hai sa vorbim de profesorul titular pe materia respectiva.(sa nu il numim, ca sa nu ne strice ziua) El e cel care conteaza. Daca el isi face treaba cum si-o face, poti sa vii tu cum vrei in ce feluri vrei, studentii nu isi vor da interes pentru ca stiu regulile cui trebuie sa le urmeze la nenorocitul de examen. Si acelea nu sunt ale tale.

    Si ca sa iesim si din sfera universitara, te formeaza de mic sa fii asa. Sa urmezi reguli imbecile, sa nu le comentezi, sa nu le disputi, te penalizeaza aspru daca o faci, trebuie sa fii atent sa nu le provoci crize de isterie pentru ca multi functioneaza si pe baza de mood-swings, si de cele mai multe ori, predau materia la ore ca si cum abia asteapta sa termine odata sa isi poata bifa in carnetel cat au mai acoperit. In fata acestor fapte, orice elev, oricat de entuziasmat ar fi, isi cam baga picioarele si face doar minumul necesar. Sau ma rog, in liceu si generala minimul necesar sa aiba note bune sa promoveze pana la o facultate. Dar in facultate, minimul necesar cat sa treaca examenele.

    De la un punct incolo e clar si vina lor, they should know better and try and do more. Dar de ce as vrea eu personal sa scriu mai mult de 20 fix(20 fiind minimul) queriuri pt tema mea la baze de date? De ce as vrea sa scriu altele decat din cele mai usoare? Da-mi un motiv bun.

    Daca invat, invat pentru mine si pentru ca vreau sa fiu buna. In nici un caz nu voi depune eforturi serioase pentru aceasta facultate.

    Si asa ies oamenii astia din facultati, merg la job, acolo fac treaba la fel de scarbiti, de mantuiala si apoi se mira lumea ca Romania e de cacat. Normal ca e, romanii fac totul in scarba sau de mantuiala. Nu toti, sa nu exagerez, dar majoritatea da.

  3. S-ar putea din partea profesorilor incercarea cultivarii interesului elevilor pe care ii au, fata de materiile predate, prin diverse metode. Tot de la profesori, m-as astepta sa nu ramana blocati intr-un singur timp si spatiu da fiind ca lucrurile se schimba, evolueaza, generatiile sunt diferite. Dar vezi tu, aici problema devine mai adanca pentru ca vorbim de invatamant de stat si oricat de mult ar vrea profesorul sa faca diferit, el are totusi o norma, el trebuie sa termine anumite taskuri intr-un timp dat. Exista reguli generale, date de sus, la care se supun toti.

    Cu alte cuvinte, solutia pe care o vad eu e privatizarea scolilor. Sa se rupa complet de stat. La privat, lucrurile se discuta altfel. Vorbim de competitie, in primul rand, care e un motivator excelent pentru a te face sa dai ce e mai bun, pentru a te face sa te perfectionezi, cum ar zice americanul, sa stay on your A game.

    Aceasta lehamite generala vine de la faptul ca stim cu totii ca nu putem schimba nimic real. in acest sistem de stat. Atat timp cat regulile se dau de sus, de undeva, un loc invizibil pentru noi, noi cu cine ne luptam de fapt?? Mergem dupa superiori pana ajungem unde?? Si cel care a dat legea respectiva a vizitat scoala/facultatea noastra? A inteles ce facem noi aici si ca aici lucrurile trebuie facute altfel din x,y, z motive? Nu, normal ca nu. it doesn’t work like that.

    Pune-i pe profi la o scoala privata, unde parintii cotizeaza mai serios. Si vom vedea atunci cum mai e cu lehamitea si cat va mai fi de greu sa te plangi de conditiile de invatare, si cat de greu va mai fi sa obtii cu adevarat o schimbare. Plus sa nu mai vorbim de calitatea diplomelor. Nu va mai fi asa de usor sa intri oriunde, oricum, therefore diploma obtinuta nu va mai fi doar hartie igienica cum e acum (desi anumite tipuri de hartie igienica recunosc ca nu le-as da pe o diploma de la o facultate romaneasca :)) ).

    Asta e singura solutie pe care o vad. Atfel, putem arunca vina pe profi, pe studenti, pe guvern, pe satana, nu conteaza. Nu se poate schimba nimic intr-un astfel de sistem. E batut in cuie si nici daca vrei sa urli la cineva, nu stii la cine mama dracului sa urli, asa ca ajungem sa urlam cu toii unii la ceilalti, degeaba.

    Privatizare de scoli si de facultati FTW!!

    • Sunt de acord cu ce zici – dar trecerea de sub administrația unui sistem dezinteresat în cea a unui sistem concurențial a produs, la noi, mai multă corupție decît e cazul. Da, trecerea trebuie făcută, sunt de acord. Aștept cu nerăbdare să văd asta întîmplîndu-se la noi. Pînă acum, însă, primii pași au fost dezamăgitori; facultățile private sunt mult mai proaste decît cele de stat.

      E o problemă sistemică ce se întîmplă la noi. Nimeni nu știe cine și ce impune. Dar toți presupun că anumite lucruri sunt impuse de sus. Limitările sunt subînțelese, și probabil de-aici senzația de neputință pe care o avem cu toții cînd ne confruntăm cu statul român.

      Da, sunt de acord… e necesară trecerea învățămîntului în sistem privat – cu urmărirea unor performanțe reale.

    • Dacă se poate și cu penalizarea aspră a celor care se laudă cu X lucrări publicate pe conferință, lucrari din care o parte unele sunt de fapt ale studenților de la master/doctorat ai acelor profesori, altele sunt rescrieri ale unor lucrări mai vechi iar altele pur și simplu nu există.

  4. Normal ca e facut totul mai prost, pentru ca noi nu stim sa functionam inafara unui sistem de stat. Noi stim doar sa urmam reguli, asta suntem invatati sa facem de mici, de acasa si apoi din scoli.

    Atat stim, atat facem. Acum probabil ai facultati private doar cu numele si bineinteles, taxa, in care probabil se incearca replicarea modus operandi-ului facultatilor de stat si nimic mai mult. (nu stiu sigur daca asa e, pentru ca nu am fost niciodata intr-o facultate privata, ma ghidez aici dupa ce am auzit din partea unor studenti din cadrul unei astfel de facultati si dupa intuitia mea).

    Eu vorbesc aici de scoli care incurajeaza cunoasterea, dezvoltarea creativitatii, nu uciderea sistematica a spiritului unui copil. Pentru ca asta fac acum. Teste standardizate, reguli impuse de sus de la mama dracu, o completa rupere de realitate, netinandu-se cont pana la urma de faptul ca acei copii au nevoie de niste skilluri reale, pentru a functiona in lumea de afara. Uite, de exemplu, multi stau si invata pe de rost chimie, sau formule de mate, sau fizica in liceu, cati stiu insa sa scrie corect, sau si mai rau, sa isi exprime corect un argument intr-o dezbatere?? E important sa stii sa scrii corect, e important sa stii sa te exprimi, e important sa stii sa comunici cu alti oameni, pana la urma vei interactiona cu ei in orice directie te vei duce. Chimia, fizica sau formulele de mate, mai putin. Sunt interesante si alea nu zic nu (mie mi-a placut chimia in mod special), dar nu in felul in care sunt impuse si predate in scoli. E mai important sa stii sa vorbesti decat sa stii teorema lui pitagora (yeeeeeeeeeeeeeeeeeees, i said it, muahahahahahaha!!!)(am zis de pitagora pentru ca eu alte teoreme nu cred ca stiu :)), sa mi se scuze lipsa de knowledge in ale matematicii, nu m-a pasionat subiectul).

    Sau literatura…Ce bataie de joc sunt orele de literatura romana…Trebuie sa inveti pe de rost comentarii tip si sa le reproduci la un examen cretin (bacalaureat), fara sa ai o parere proprie? Vorbim aici de arta, vorbim aici de subiectivism, de cand e okay sa dai doar o singura interpretare unui text literar si sa iti permiti sa spui ca aceasta e singura interpretare corecta?

    Si multe altele. Pana la urma, punctul meu de vedere e mai bine exprimat in povestioara aceea din linkul postat de Mithrandir. Foarte interesanta lectura, desi trista.

    • Eu ți-am zis că ar trebui să se revină la trivia: gramatică, logică și retorică. Asta ar trebui să fie materiile de bază. Normal că nu e nevoie de atîtea cunoștințe absurde pe care le băgăm pe gîtul oamenilor prin prezentul sistem de învățămînt. Dar o reîntoarcere la trivia ar cere o schimbare completă de mentalitate. Și o schimbare completă a societății. Cine mai are curaj să facă acum asta?

      Recomand și eu Lockhart’s Lament. Foarte bună povestea, și foarte corectă.

  5. Pingback: Despre învățămîntul academic român, și eșecul lui în lume | dorinlazăr.ro