Psihologia concursurilor de informatică/0 Cuvânt înainte

From Algopedia
Jump to: navigation, search

⇦ înapoi la Psihologia concursurilor de informatică

Cuvânt înainte

În ultimii ani s-au tipărit la noi în țară foarte multe culegeri de teorie și probleme de programare. Fiecare din ele acoperă diverse domenii ale informaticii. Unele își propun să inițieze cititorul în tainele diverselor limbaje de programare, altele pun accentul mai cu seamă pe tehnicile de programare și structurile de date folosite în rezolvarea problemelor. În general, cele din prima categorie conțin exemple cu caracter didactic și exerciții cu un grad nu foarte sporit de dificultate, iar celelalte demonstrează matematic fiecare algoritm prezentat, însă neglijează partea de implementare, considerând scrierea codului drept un ultim pas lipsit de orice dificultate.

Desigur, fiecare din aceste cărți își are rostul ei în formarea unui elev bine pregătit în domeniul informaticii. De altfel, citirea volumului de față presupune cunoașterea temeinică a conținutului ambelor tipuri de materiale enumerate mai sus. Totuși, pornind de la observația că scrierea unui program impune atât conceperea algoritmului și demonstrarea corectitudinii, cât și implementarea lui, ambele etape fiind complexe și nu lipsite de obstacole, am considerat necesară scrierea unui nou volum care să trateze simultan aceste două aspecte ale programării.

În afară de aceasta, după cum și titlul lucrării o spune, cartea se adresează pasionaților de informatică și celor care au de gând să participe la concursurile și olimpiadele de informatică. Concursul include apariția unui factor suplimentar care răstoarnă multe din obișnuințele programării „la domiciliu”: timpul. Autorul a avut la dispoziție patru ani ca să descopere pe propria piele importanța acestui factor. Și, mai mult decât durata de timp în sine a concursului - care la urma urmei este aceeași pentru toți concurenții - contează capacitatea fiecăruia de a gestiona bine acest timp.

Dacă în fața calculatorului de acasă, cu o sticlă de Coca-Cola alături și casetofonul mergând, este într-adevăr un lucru lăudabil să justificăm matematic fiecare pas al algoritmului, să nu ne lăsăm înșelați de intuiție și să scriem programul fără să ne grăbim, alocându-ne o jumătate din timp numai pentru depanarea lui, în schimb în timp de concurs lucrurile stau tocmai pe dos. De demonstrații riguroase nu se mai ocupă nimeni, intuiția este la mare preț și de nenumărate ori este criteriul care aduce victoria, iar timpul de-abia dacă este suficient pentru implementarea programului, despre depanare nemaiîncăpând discuții. În multe cazuri, cele două etape ale programării - conceperea și implementarea algoritmului - încep să se bată cap în cap. Uneori avem la dispoziție un algoritm foarte puternic, dar nu știm cum s-ar putea implementa, alteori acest algoritm nu face față volumului maxim de date de intrare, iar alteori ne dăm seama că am putea foarte ușor să scriem un program, dar nu suntem în stare să demonstrăm că el ar merge perfect. Foarte des se renunță la implementarea algoritmilor de complexitate optimă, care sunt alambicați și constituie adevărate focare de „bug”-uri, preferându-se un algoritm mai lent dar care să se poată implementa rapid și fără dureri de cap. Mulți olimpici pierd clasa a IX-a, poate chiar și pe a X-a descoperind aceste lucruri. Cartea de față își propune să le mai ușureze drumul.

S-a presupus cunoscut limbajul de programare Pascal, cu toate instrucțiunile și procedurile sale standard. În carte există multe surse în limbajul C standard. Am preferat acest lucru, deși la concursuri se recomandă programarea în Pascal, pentru că am sperat că un elev familiarizat cu limbajul Pascal va citi fără dificultate o sursă C și pentru că am dorit ca această carte să fie și un exercițiu de C, al cărui număr de utilizatori la nivelul liceului este destul de redus. Surse în Pascal există numai acolo unde se urmărește punerea în evidență a unei anumite subtilități a limbajului.

Tehnicile de programare s-au presupus cunoscute în esență, astfel încât am trecut direct la unele optimizări, la exemple de folosire a lor și la compararea lor, respectiv la prezentarea unor criterii în funcție de care să optăm pentru folosirea fiecăreia. De asemenea, am renunțat la definirea termenilor de graf, arbore, vector, matrice, listă, stivă și a tuturor celorlalte structuri de date de bază. Am considerat interesantă prezentarea pe larg numai a heap-urilor și a tabelelor de dispersie (hash), care sunt mai rar folosite și de aceea mai puțin cunoscute. În sfârșit, am presupus cunoscută noțiunea de complexitate a unui algoritm, deoarece în toate problemele se face calculul complexității.

Cartea prezintă interes și pentru problemele pe care le cuprinde. Ele nu sunt banale (de fapt, majoritatea au avut onoarea de a da bătăi de cap concurenților la olimpiade) și pot fi lucrate acasă de către elevi pentru menținerea în formă. Tocmai de aceea, am urmărit ca, ori de câte ori am propus o problemă spre rezolvare, enunțul să fie dat în aceeași formă pe care ar fi avut-o la un concurs: clar, detaliat, cu specificarea formatului datelor de intrare și ieșire și cu un exemplu sau două. Singura diferență este că, de regulă, la concursuri și olimpiade se precizează numai timpul limită admis pentru un test; în carte am considerat folositor să se specifice și o complexitate optimă a algoritmului care rezolvă problema, deoarece timpul de execuție variază în funcție de resursele calculatorului și de limbajul de programare folosit, deci e un criteriu mai puțin semnificativ. Timpul destinat implementării unei probleme este în general egal cu cel care s-a acordat la concursul unde a fost propusă respectiva problemă.

În sfârșit, consider că programatorii care își propun să scrie aplicații de mari dimensiuni ar avea destul de multe lucruri de învățat din acest volum, deoarece am inclus și detalii privind structuri de date mai neobișnuite sau gestionarea economică a memoriei.

Sper să nu închideți această carte cu sentimentul că mai bine n-ați fi deschis-o.