Metode Interactive de Predare a Tehnicilor de Programare

Introducere

Atunci când suntem puși în față unei probleme pentru care trebuie să elaborăm un algoritmi de rezolvare a ei, de multe ori suntem în situația că „nu știm cum să începem”. Conform cu Horowitz și Sahni (Fundamentals of computer algorithms, Springer Verlag, 1978), „actul de creare a unui algoritm este o artă care nu va fi niciodată complet automatizat”. Cu alte cuvinte, nu va exista niciodată un algoritm pentru scrierea algoritmilor!

Arta de a elabora algoritmi pentru diverse problemele ce se cer a fi rezolvate, se bazează pe experiența acumulată anterior prin elaborarea altor algoritmi în rezolvarea unor probleme asemănătoare.

Ca în orice altă activitatea, există totuși câteva principii care ne pot ajuta în asemenea situații. Aceste principii (metode) generale, dacă sunt bine însușite, ne pot ajuta în nenumărate situații în care avem de rezolvat o problemă ca să elaborăm algoritmul pentru rezolvarea acelei probleme. Aceste metode sunt din ce în ce mai mult în atenția celor ce au rezolvat probleme cu ajutorul calculatorului. Sunt bine cunoscute metodele generale de elaborare a algoritmilor ca: metoda Greedy, metoda Backtracking, metoda Programării dinamice, metoda Branch and Bound, metoda Divide et impera, etc.

Unele dintre aceste metode sunt atât de generale încât mulți le folosesc frecvent ca reguli elementare de gândire (fără să cunoască fundamentarea lor teoretică ci bazându-se numai pe intuiție).

Majoritatea programatorilor care au depășit faza de inițiere în programare și au auzit de existența acestor metode generale de elaborare a algoritmilor sau „tehnici de programare” le-au privit cu un optimism exagerat crezând că ele îi vor scăpa de chinurile elaborării algoritmilor pentru problemele dificile. Probabil că în scurt timp ei au fost dezamăgiți constatând că, deși aceste tehnici le ușurau munca, nu întotdeauna, pentru o problemă dată, este ușor de identificat și aplicat „tehnica” adecvată.

De altfel, arta de a crea un algoritm nu va putea fi niciodată automatizată (Horowitz și Sahni) și, prin urmare, „tehnicile de programare” trebuie să fie privite doar ca niște metode generale de elaborare a algoritmilor aplicabile unor clase largi de probleme, astfel încât programatorul să nu mai fie nevoit să conceapă câte o metodă ad-hoc pentru fiecare problemă din clasa respectivă pe care o are de rezolvat. El nu trebuie decât să identifice clasa din care face parte acea problemă și să

particularizeze acea metodă generală de elaborare a algoritmilor pentru problema concretă pe care o are de rezolvat.

În multe situații o problemă concretă poate fi încadrată în mai multe astfel de clase, adică i se pot aplica mai multe metode de elaborare a algoritmilor. Astfel, unei probleme i se poate aplica, de exemplu, atât metoda Greedy cât și metoda Backtracking.

De astfel, se știe că algoritmii pentru rezolvarea unei probleme nu sunt unici. Ajunși în acest punct ne punem întrebarea în ce clasă să încadrăm problema dată pentru a o rezolva. Cei mai mulți aleg una din metodele cele mai ușoare de aplicat (cum ar fi, de exemplu, metoda Backtracking pentru care trecerea de la forma generală a metodei la o problemă concretă se face după un scenariu bine stabilit, această trecere făcându-se aproape mecanic, deci „aproape algoritmic”). Dar alegerea metodei cel mai ușor de aplicat nu conduce întotdeauna la rezolvarea optimă a problemei date.

În multe cazuri, alegerea metodei cel mai ușor de aplicat conduce la algoritmi mari consumatori de timp sau de memorie pentru execuția lor. De aceea, este bine să alegem acea metodă de elaborare a algoritmilor care conduce, pentru problema dată, la un algoritm optim, chiar dacă aplicarea acelei metode la probleme concrete este mult mai dificilă (de exemplu, metoda programării dinamice este mult mai dificil de aplicat, trecerea de la forma generală a metodei la o problemă concretă necesitând multă ingeniozitate și o înțelegere profundă a metodei). Cu toate acestea, parcurgând capitolele corespunzătoare III și IV, vă veți convinge că, în general, e de preferat (din punct de vedere al timpului de execuție) să aplicăm metoda Programării dinamice în locul metodei Backtracking pentru rezolvarea unei probleme date.

Tehnicile de programare s-au dezvoltat începând cu anii 1970 fiind studiate azi în multe școli și mai ales în instituțiile de învățământ superior, ele reprezentând un pas important pe care l-a înregistrat informatica în ultima vreme. Studierea și aplicarea lor în dezvoltarea lor în rezolvarea a cât mai multor probleme formează mintea tânărului programator, îi folosesc acestuia mult în viață. Din păcate, din diverse motive, acestui domeniu nu i se acordă toată atenția cuvenită.

Există o anumită categorie de probleme pentru care tehnicile de programare cunoscute nu duc la nici un rezultat. Acestea sunt problemele în care ordinul de complexitate al algoritmului nu este polinomial (practica impunându-i ca acceptabili numai pe aceștia). O excepție în acest sens putem să spunem că o face metoda Greedy dar se știe că aplicând această metodă nu avem siguranța că găsim soluția optimă ci o soluție apropiată de aceasta. Deci, prin aplicarea metodei Greedy practic renunțăm la optimalitatea soluției. Totuși, ce e de făcut atunci când aplicarea unei tehnici de programare cunoscute conduce la un algoritm al cărui ordin de complexitate este exponențialul? Tendința mondială din ultimii ani este de a renunța la obținerea soluției optime pentru problemele

practice și de a găsi algoritmi care conduc la o soluție apropiată de aceasta, dar pentru care să cunoaștem totuși marja de eroare. Acești algoritmi se găsesc în literatura de specialitate sub numele de algoritmi euristici.

De-a lungul timpului, oamenii de știință și-au dat seama din ce în ce mai mult că pentru a crea algoritmi performanți va trebui, ținând seama de esența divină a acestei lumi, să împrumutăm metodele care acționează deja în natură. În acest fel au apărut algoritmii neuronali și algoritmii genetici.

În concluzie, programarea unui calculator nu înseamnă doar translatarea unor instrucțiuni într-un limbaj recunoscut de calculator. Cunoașterea mai multor limbaje de programare nu este suficientă pentru a ști să programezi. Există tendința ca pentru o problemă dată să elaborăm un algoritm (plecând de la prima idee care ne vine în minte) în mod direct. Deși este natural, acest mod de a elabora algoritmi nu este cel mai potrivit, mai ales atunci când avem de-a face cu probleme mari care necesită prelucrarea unei mari cantități de informații. Desigur, acești algoritmi s-ar putea să funcționeze bine pe probleme mici, dar pot fi catastrofali pe probleme care au date de intrare de dimensiuni mari. Dacă, în plus, acești algoritmi trebuie rulați de mai multe ori, atunci apare cu atât mai mult necesitatea găsirii unor metode mai bune, mai rapide, chiar dacă algoritmul devine mai complicat și mai greu de înțeles. În ciuda faptului că se pierd ore din timpul programatorului, se poate câștiga uneori chiar și numai secunde din timpul calculatorului, dar care să răsplătească efortul depus.

În ultimii ani, tehnicile de programare au început să fie studiate cu mult interes și din ce în ce mai mult. Astfel, ele sunt cuprinse în aproape toate planurile de învățământ atât din licee cât și din facultățile de profil. Această lucrare se adresează tuturor acelora ce doresc să studieze în domeniul tehnicilor de programare: elevi, studenți, profesori, ingineri, tuturor persoanelor interesate. Conținutul lucrării este structurat în șapte capitole, fiecare capitol abordând câte una dintre aceste metode expuse

într-un mod didactic în așa fel încât ele să poată fi abordate de toate categoriile de cititori interesați.

Ceea ce s-a dorit prin realizarea acestei lucrări, a fost o structurare a materialului bibliografic pe care l-am avut la dispoziție pentru a constitui un fel de manual pentru toți cei ce vor să studieze în acest domeniu.

PARTEA I

TEHNICI DE PROGRAMARE

CAPITOLUL I ALGORITMII ȘI EFICIENȚA LOR

Înainte de a prezenta cele mai cunoscute metode generale de elaborare a algoritmilor, să trecem repede în revistă câteva aspecte privind algoritmii (ce este un algoritm, ce este o operație elementară, în ce constă eficiența unui algoritm ș.a.).

Ce este un algoritm

Noțiunea de algoritm este o noțiune forte veche. Cuvântul „algoritm” este de origine arabă. El derivă din numele matematicianului Abu Ja’far Mohammed ibn Mǔsâ al-Khowârizmî (autor persan, sec. VII-IX) care a scris o carte de matematică celebră intitulată „Kitab al jabr w’ai- muquabala” cunoscută în traducere latină ca „Algorithmi de numero indorum”, iar apoi ca „Liber algorithmi”, unde „algorithm” provine de la „al-Khowârizmî”, ceea ce literal înseamnă „din orașul Khowărizm”. Acest oraș se numește în prezent Khiva și el se află în Uzbechistan. În Evul Mediu, atât al-Khowârizmî cât și alți matematicieni înțelegeau prin algoritm o regulă pe baza căreia se efectuau calcule aritmetice. Astfel, în timpul lui Adam Riese (sec. XVI), algoritmii foloseau la: înjumătățiri, dublări, înmulțiri de numere. În lucrările lui Stifer („Arithmetica integra”, Nűrnberg, 1544) și Cardano („Ars magna sive de reguli algebraicis”, Nűrnberg, 1545) apar și alți algoritmi. Chiar și Leibnitz vorbește de „algoritmi de înmulțire”. Totuși, mult timp termenul de algoritm a rămas cu o întrebuințare destul de restrânsă, chiar și în domeniul matematicii.

Actul de naștere al teoriei funcțiilor recursive este semnat de Kronecker (în 1886) și Dedekind (în 1888) și conceptul de recursivitate devine indisolubil legat de cel de algoritm. Teoria recursivității și a algoritmilor începe să se constituie ca atare abia în deceniul al treilea și al patrulea ale secolului nostru, prin lucrările lui Skolem, Ackermann, Sudan, Gödel, Church, Kleene, Turing, Peter și alții.

În ultima vreme, ca rezultat al conexiunii dintre algoritm și calculator, gândirea algoritmică a căpătat o transformare uimitoare dintr-un instrument matematic particular, într-o modalitate fundamentală de abordare a majorității problemelor din domenii care, aparent, nu au nimic comun

cu matematica. Pentru algoritmi nu există o definiție așa cum și în matematică nu există o definiție pentru noțiunea de mulțime. Noțiunea de algoritm este o noțiune primară. Astăzi, prin algoritm se înțelege o metodă generală de rezolvare a unui tip de probleme, metodă ce se poate implementa pe calculator. Deci, un algoritm este compus dintr-o mulțime de pași, fiecare necesitând una sau mai multe operații. Prin urmare, în acest context, un algoritm este esența absolută a unei rutine. Operațiile, pentru a putea fi implementate pe calculator, trebuie să fie bine definite (adică să exprime foarte clar ce anume trebuie executat) și efective (ceea ce înseamnă că, cel puțin în principiu, o persoană dotată cu hârtie și creion trebuie să poată efectua orice pas într-un timp finit). Se consideră că un algoritm trebuie să se termine după un număr finit de operații într-un timp rezonabil (deci nu exagerat de lung, ca de exemplu, ani sau secole). De exemplu, aritmetica cu numere reale nu este efectivă deoarece unele numere sunt exprimabile prin secvențe infinite pe când, aritmetica cu numere întregi este efectivă.

Desigur, cel mai cunoscut algoritm este algoritmul lui Euclid pentru aflarea celui mai mare divizor comun a două numere întregi. Dar mai sunt și alți algoritmi foarte cunoscuți (ca, de exemplu, metodele învățate în școală pentru a înmulți / împărți două numere, pentru a extrage rădăcina pătrată dintr-un număr ș.a.). dar, ceea ce dă generalitate unui algoritm, este faptul că el poate opera nu numai cu numere. Astfel, este posibil chiar să construim anumite rețete culinare cu algoritmi, chiar dacă nu includ instrucțiuni ca: „adăugați sare după gust”. Practic, nu există domeniu în care să nu putem să descoperim sectoare ce funcționează algoritmic.

Prin program vom înțelege exprimarea unui algoritm într-un limbaj de programare cunoscut de un calculator.

Studiul algoritmilor cuprinde mai multe aspecte:

-Elaborarea algoritmilor. Actul de creare a unui algoritm este o artă ce se presupune creativitatea umană bazată pe o serie de reguli cunoscute (tehnici de elaborare a algoritmilor despre care vom discuta în această lucrare) și pe ingeniozitatea (intuiția, creativitatea) umană.

Reprezentarea algoritmilor. Algoritmii pot fi reprezentați prin mai multe metode: pseudocod, scheme logice, diagrame etc. În această lucrare noi vom utiliza un limbaj pseudocod foarte apropriat de limbajul Pascal ceea ce face să fie ușor de înțeles de către cititor, așa că nu vom mai expune sintaxa acestui limbaj pseudocod.

Corectitudinea algoritmilor. După elaborarea și reprezentarea sa, un algoritm trebuie să fie validat (să i se verifice corectitudinea) pentru a ne asigura că el funcționează corect, indiferent în ce limbaj de programare va fi implementat.

Analiza algoritmilor. Pentru o anumită problemă pot fi elaborați mai mulți algoritmi. Pentru a putea să decidem care dintre ei este cel mai bun, este nevoie să definim un criteriu de apreciere a valorii unui algoritm. În general, acest criteriu se referă la timpul de calcul și la memoria necesară unui algoritm. În această lucrare vom face și câteva analize din acest punct de vedere, dar scopul principal rămâne descrierea tehnicilor generale de elaborare a algoritmilor.

Elaborarea programelor. Un algoritm corect, de obicei, este implementat într-un limbaj de programare pentru a fi utilizat pe calculator. În practică, sunt cazuri când unii algoritmi sunt implementați în alt context (nu neapărat pe un calculator). Noi ne vom ocupa în mod special de algoritmi ce sunt implementați pe calculator.

Testarea programelor. Acest aspect constă din două faze: depanare și trasare.

Depanarea (debugging) este procesul ce constă în executarea programului de date de test și corectarea eventualelor erori. Prin depanare, așa cum afirma E.W. Dijkstra, putem evidenția doar prezența eroilor dar nu și absența lor. În schimb, demonstrarea faptului că un program este corect este mult mai valoroasă decât o mie de teste deoarece prin demonstrație se poate garanta că programul funcționează corect în orice situație.

Trasarea (profiling) este procesul de execuție a unui program corect pe diferite date de teste (bine alese) cu scopul de a determina timpul de calcul și memoria necesară. Rezultatele obținute în această etapă se pot compara, după aceea, cu rezultatele obținute în etapa de analiză a algoritmului.

Când avem de rezolvat o problemă, este important să ne decidem ce algoritm vom folosi pentru rezolvare. Răspunsul poate să depindă de mulți factori: dimensiunea exemplului de rezolvat, modul în care problema este prezentată, viteza și memoria disponibilă a echipamentului de calcul și așa mai departe. Să luăm ca exemplu aritmetica elementară. Să presupunem că avem de înmulțit două numere naturale folosind stilou și hârtie. Bineînțeles că vom fi imediat tentați să utilizăm algoritmul cunoscut: înmulțind fiecare cifră a înmulțitului cu deînmulțitul, iar rezultatul este trecut pe linii, cu o poziție la stânga și la final se adună aceste coloane și se obține rezultatul. Acesta este algoritmul „clasic” de înmulțire.

Cu toate acestea, există un algoritm destul de diferit pentru efectuarea aceluiași lucru, numit uneori „înmulțirea à la russe”. Scrieți deînmulțitul și înmulțitorul (de exemplu 45 și 19) unul lângă altul (ca în figura I.1) formând sub fiecare operând câte o coloană, conform următoarei reguli: se împarte numărul de sub deînmulțit la 2, ignorând fracțiile, apoi se înmulțește cu 2 numărul de sub înmulțitor. Această regulă se repetă până când numărul de sub deînmulțit ajunge să fie 1. În final se renunță la toate numerele din coloana înmulțitorului care corespund, pe linie, unor numere pare în

coloana deînmulțitorului iar numerele rămase din coloana înmulțitorului sunt adunate obținându-se astfel rezultatul înmulțirii. În cazul exemplului ales, obținem:

19+76+152+608=855

Fig. I.1. Înmulțirea „à la russe”

Cu toate că la început acest algoritm pare să fie amuzant, el este metoda esențială folosită în hardware-le majorității calculatoarelor pentru a efectua înmulțirile. Pentru a folosi această metodă, hardware-ul nu trebuie să știe decât să adune, să dubleze un număr și să împartă la doi (înmulțirea cu 2 și împărțirea la 2 realizându-se foarte simplu prin deplasări).

Menționăm că există și alți algoritmi pentru a înmulți două numere și unii dintre ei sunt foarte eficienți atunci când numerele de înmulțit sunt foarte mari (vedeți [1], [3] și [7] din bibliografia indicată). Acești algoritmi și mai sofisticați sunt de fapt mai înceți când operanzii nu sunt suficient de mari decât unii algoritmi simpli (ca cel prezentat mai sus).

Ajunși în acest punct, este important să decidem cum vom reprezenta algoritmul nostru. Dacă încercăm să-l descriem în limba maternă, vom descoperi rapid că limbajul natural nu este potrivit cu astfel de lucruri. Chiar descrierea noastră a unui algoritm simplu cum este înmulțirea à la russe nu este complet clară. Pentru a diminua confuzia, în viitor vom specifica algoritmul nostru

dându-i un program corespondent. Cu toate acestea nu ne vom conforma prin a folosi un anume limbaj de programare: în acest mod punctele importante ale algoritmului nu vor fi înoculate de relativitatea detaliilor neimportante de programare.

Vom folosi fraze în limba română în programul nostru oricând acesta arată o simplificare și claritate. Aceste fraze nu trebuie să fie confundate cu comentariile în program, care vor fi întotdeauna incluse între paranteze, acolade. Un cititor care este familiarizat cu Pascalu-ul, de exemplu, nu va avea nici o dificultate în a înțelege notațiile folosite în descrierea algoritmului nostru. De exemplu, aici este o descriere formală a înmulțirii à la russe:

Function russe (a,b)

array x,y

begin

{Inițializare} x[1]:=a; y[1] :=b i :=1

{Realizează cele două coloane} while x[i]>1 do

begin

end

x[i+1]:=x[i] div 2 {“div” reprezintă împărțirea întreagă} y[i+1]:=y[i] + y[i]

i:=i+1

{Adună numerele y[i] corespunzătoare numerelor x[i] impare}

prod:=0 while i >0 do

begin

end;

end return prod

if x[i] este par then prod:=prod + y[i]

Dacă sunteți un programator experimentat, probabil veți observa faptul că de fapt tablourile x

și y nu sunt absolut necesare și că acest program poate fi simplificat cu ușurință.

Pe de altă parte, următorul program, în ciuda unei asemănări izbitoare cu cel dat anterior, descrie un algoritm diferit dar tot pentru înmulțirea a două numere.

Function not-russe (a,b) array x, y

begin

{inițializare} x[1]:=a; y[1] :=b

i :=1

{Realizează cele două coloane} while x[i]>1 do

begin

end

x[i+1]:=x[i] – 1

y[i+1]:=b i:=i + 1

{Adună numerele y[i]}

prod:=0 while i>0 do

begin

end;

end return prod

if x[i]>0 then prod:=prod + y[i] i:=i-1

Observăm că acești doi algoritmi diferiți pot fi folosiți la rezolvarea aceleiași probleme (înmulțirea a două numere) și, pe de altă parte, pot fi folosite programe diferite în a descrie același algoritm. Este important să nu pierdem ideea că de fapt în această lucrare suntem interesați de algoritmi, nu de programele folosite în a-i descrie.

Probleme și cazuri

Înmulțirea à la russe nu este numai o cale de a înmulți 45 cu 19. Ea dă o soluție generală a problemei de a înmulți orice două numere întregi pozitive. Spunem că (45,19) este un caz (exemplu) al acestei probleme. Un algoritm trebuie să lucreze corect pentru orice caz (exemplu) al problemei pe care pretinde că o rezolvă. A arăta că un algoritm este incorect, avem nevoie de un exemplu al problemei pentru care acesta nu este în stare să găsească răspunsul corect (numit contraexemplu). Pe de altă parte, este mai dificil să dovedești corectitudinea unui algoritm. Când specificăm o problemă, este important să specificăm domeniul de definiție, adică setul de exemple ce vor fi luate în considerare. Astfel înmulțirea à la russe nu va funcționa dacă primul operând este negativ, deci algoritmul nu este valabil pentru (- 45,9), care nu este exemplu (caz) al problemei considerate.

Orice calculator real are o limită a dimensiunilor cu care se poate descurca. Aceste limite nu pot fi atribuite algoritmului pe care l-am ales să-l utilizăm. Cu alte cuvinte, dacă un calculator nu poate să lucreze cu numere întregi decât în limita dintre –32.768 și 32.767, aceasta nu înseamnă că algoritmul trebuie să țină seama de aceste limite. Algoritmul poate să fie corect pentru orice număr întreg (în particular, el va fi corect și pentru limitele impuse de hardware). Aici vedem încă o dată că este esențială diferența între programe și algoritmi.

Eficiența algoritmilor

În general, pentru o problemă pot fi elaborați mai mulți algoritmi.

Pentru a stabili care dintre ei este cel mai bun, este nevoie să definim un criteriu de apreciere a valorii unui algoritm. Acest criteriu se referă, în general, la timpul de calcul și la memoria necesară unui algoritm.

Câteva exemple practice

Să presupunem că se dau n numere și se cere să se găsească minimul dintre aceste numere.

Desigur, cele n numere pot fi memorate ca și componente ale unui vector. Algoritmul pentru această problemă este următorul:

unei variabile (pe care s-o numim min) i se va atribui valoarea primei componente;

se compară pe rând cu valoarea variabilei min fiecare dintre cele n-1 componente rămase, iar în cazul în care valoarea componentei respective este mai mică decât cea a variabilei min, variabilei min i se atribuie valoarea acelei componentei.

În pseudocod, algoritmul este:

function minim (v); begin

min:=v[1];

for i:=2 to n do

if v[i]<min then min:=v[i] minim:=min

end;

Desigur, timpul de calcul depinde, în primul rând, de numărul n de componente ale vectorului dat.

Pentru a estima timpul de calcul necesar ar trebui să inventariem toate instrucțiunile programului și să știm de câte ori se execută fiecare dintre ele (în funcție de n). Mai mult, ar trebui să cunoaștem cât durează execuția fiecărui tip de instrucțiune.

Observații. 1) Pentru fiecare problemă există un anumit număr n de date de intrare și de acest număr depinde de obicei timpul de execuție. Astfel:

pentru aflarea minimului (maximului), n reprezintă numărul de componente ale vectorului care se sortează;

pentru sortare, n reprezintă numărul de valori care se sortează;

pentru testul unui număr natural dacă este prim sau nu, n este chiar numărul;

pentru problema colorării hărților, n este numărul țărilor;

pentru generarea permutărilor, n reprezintă numărul de elemente ale mulțimii pentru care se generează permutările.

Nu putem ști întotdeauna cu exactitate de câte ori se execută

o instrucțiune ca să putem înmulți acel număr cu timpul cât durează execuția ei. De exemplu, pentru calculul minimului, nu putem ști cu exactitate de câte ori se execută atribuirea min:=v[i], deoarece această instrucțiunile se execută numai atunci când conținutul variabilei v[i] este mai mic decât al variabilei min. Cu toate acestea, putem considera că există o proporționalitate între valoarea n și numărul de execuții.

Timpul de execuție al unei instrucțiuni este dependent de calculatorul utilizat.

Majoritatea instrucțiunilor se execută de un număr de ori destul de mic astfel că timpul afectat pentru execuția lor este nesemnificativ și putem practic să-l neglijăm. De aceea, se alege o operație (instrucțiune) numită operație de bază și se constată de câte ori se execută aceasta. Cerința pentru operația de bază este ca numărul de execuții al acesteia să se poată calcula de la început pornind de la n.

Timpul de calcul estimat pentru un algoritm oarecare (Ordinul său de complexitate) se notează astfel:

O(număr estimat de execuție ale operației de bază) aceasta fiind o notație consacrată.

Dacă, de exemplu, un algoritm efectuează 2n2+5n+6 operații de bază, vom spune că acesta este un

algoritm al cărui ordin de complexitate este în O(n2) sau se mai spune că algoritmul are un timp de execuție pătratic.

Exemple.

Pentru aflarea minimului (maximului) dintre n valori, timpul de calcul estimat este în O(n).

Pentru generarea permutărilor (în cazul în care se consideră ca operație de bază generarea unei permutări) timpul de calcul estimat este în O(n!).

Pentru unele probleme nu putem preciza nici măcar numărul de execuții ale operației de

bază.

Exemplu. Sortarea prin interschimbare.În cazul în care vectorul este deja sortat, se execută n-1 comparații (se parcurge vectorul o singură dată). Dacă vectorul este asortat invers, se execută

n(n 1)

2

operații de bază (se parcurge vectorul de n ori).

În astfel de cazuri se poate considera:

timp minim de calcul;

timp mediu de calcul;

timp maxim de calcul.

De fiecare dată când trece timpul estimat se precizează despre care este vorba (minim, mediu sau maxim). În practică prezintă interes timpul mediu și timpul maxim.

Dacă timpul estimat este sub forma O(n), spunem că algoritmul este în timp liniar.

Dacă timpul estimat este sub forma O(nk), spunem că algoritmul este în timp polinomial.

Dacă timpul estimat este sub forma O(2n), O(3n) și așa mai departe spunem că algoritmul este în timp exponențial.

Un algoritm în timp O(n!) este asimilat unui algoritm în timp exponențial deoarece

În practică nu sunt admiși decât algoritmi în timp polinomial, deși nu este deloc indiferent gradul polinomului.

În concluzie, ori de câte ori avem de rezolvat o problemă, căutăm pentru aceasta un algoritm în timp polinomial. Mai mult, vom căuta un algoritm care să rezolve problema în timp polinomial de grad minim.

Exemple.

Pentru problema aflării minimului, operația de bază va fi comparația (fiind dat n se fac n-1 comparații pentru calculul minimului).

Pentru generarea permutărilor, alegerea operației de bază este greu de făcut. De exemplu, dacă aceasta este comparația, este greu de calculat numărul comparațiilor efectuate pentru a genera toate permutările. Din acest motiv putem considera ca operație de bază generarea unei permutări. Vom avea astfel n! Operații de bază (un număr foarte mare). Pentru generarea permutărilor există foarte mulți algoritmi. Alegerea ca operație de bază a comparației permite ca aceștia să fie comparați între ei, dar alegerea ca operație de bază a generării unei permutări nu permite aceasta.

În astfel de cazuri (când avem de ales între mai multe operații de bază), vom alege acea operație care corespunde cât mai bine scopului propus.

Considerații teoretice

Când avem o problemă de rezolvat, ideal este să găsim mai mulți algoritmi pe care să-i putem utiliza, iar dintre ei să-l alegem pe cel mai bun. Întrebarea care se pune este cum vom decide care dintre algoritmi să fie cel preferat. O modalitate empirică (sau a posteori) de a decide constă în a rezolva complet algoritmul și a-l încerca pe diferite exemple cu ajutorul calculatorului. Cel teoretic

(sau a priori) despre care discutăm în această lucrare constă în determinarea matematică a cantității de resurse (timp de execuție, spațiu de memorie etc.) necesare fiecărui algoritm ca o funcție a dimensiunii cazului (exemplului) considerat.

Dimensiunea (mărimea) unui caz (exemplu) x corespunde formal numărului de biți necesari reprezentării exemplului pe calculator, folosind o codificare precis definită și rezonabil de compactă. De obicei, folosim cuvântul „dimensiune” în sensul orice întreg într-un anume mod măsurat, ca de exemplu, numărul componentelor. De exemplu, când vorbim despre sortare, dimensiunea unui exemplu x va fi numărul de elemente de sortat, chiar dacă o singură componentă va ocupa mai mult de un bit când va fi reprezentată în calculator. Când vom vorbi despre probleme numerice, câteodată dăm eficiența algoritmului folosind termenul de valoare a exemplului, aceasta fiind considerată de fapt dimensiunea exemplului (care este numărul de biți necesari pentru a reprezenta această valoare în binar).

Avantajul analizei teoretice este că aceasta nu depinde nici de calculatorul folosit, nici de limbajul de programare și nici de priceperea programatorului. În plus, analiza teoretică salvează și timpul pierdut atât pentru programare cât și pentru testarea pe calculator a algoritmului care se dovedește în final ineficient. De asemenea, analiza teoretică ne permite să studiem eficiența unui algoritm folosind exemple de orice dimensiune. În cazul analizei empirice, diferite considerații practice ne obligă să testăm algoritmii noștrii numai pe exemple de dimensiuni moderate.

De asemenea, este posibil să analizăm algoritmii folosind o metodă hibridă. În acest caz, forma funcțiilor descriind eficiența algoritmilor este determinată teoretic, iar valorile numerice ale partenerilor sunt determinate empiric după aceea. Această analiză permite o predicție asupra comportării algoritmului pentru cazuri foarte mari, care nu pot fi testate. O extrapolare făcută doar pe bazele testelor empirice este mai puțin precisă, dacă nu chiar greșită.

Ajunși în acest punct, este natural să ne întrebăm ce unitate vom folosi în exprimarea eficienței teoretice a algoritmului. Aici nu poate fi pusă problema de a exprima această eficacitate în secunde, până când nu vom avea un calculator standard la care să se refere toate măsurătorile. Un răspuns la această întrebare este dat de principiul invarianței, potrivit căruia două implementări diferite ale aceluiași algoritm nu diferă în eficiență prin mai mult de o constantă multiplicativă.

Mai precis, dacă două implementări iau t1(n) și, respectiv, t2(n) secunde pentru a rezolva un caz de dimensiune n, atunci există întotdeauna o constantă pozitivă c astfel încât t1(n) ct2(n) pentru orice n suficient de mare.

Acest principiu este valabil indiferent de calculatorul folosit, indiferent de limbajul folosit și indiferent de priceperea programatorului (presupunând că el sau ea nu modifică actualmente algoritmul!). Astfel, schimbarea calculatorului ne poate permite să rezolvăm o problemă de 10 sau de 100 de ori mai rapid, dar schimbarea algoritmului ne poate aduce o îmbunătățire care să devină din ce în ce mai marcantă pe măsură ce mărimea cazului soluționat crește.

Revenind la problema referitoare la unitatea de măsură folosită în exprimarea teoretică a eficienței unui algoritm, ajungem la concluzia că nici nu avem nevoie de o asemenea unitate: vom exprima eficiența în limitele unei constante multiplicative.

Vom spune că un algoritm necesită un timp în ordinul lui t(n), pentru o funcție t dată, dacă există o constantă c și o implementare a algoritmului capabilă să rezolve fiecare caz al problemei într-un timp limitat superior de ct(n) secunde, unde n este mărimea cazului considerat. Folosirea secundelor în această definiție este chiar arbitrară, deoarece este suficient să modificăm doar constanta pentru a mărgini timpul la at(n) ani, sau la bt(n) microsecunde.

Datorită principiului invariației, orice altă implementare a algoritmului va avea aceeași proprietate, cu toate că de la o implementare la alta se poate modifica constanta multiplicativă. Mai târziu vom da un tratament mai riguros acestui concept cunoscut sub numele de notare asimptotică. Abia atunci va fi mai clar (pornind de la o definiție mult formalizată) de ce este mai bine să spunem că eficiența unui algoritm este „în ordinul” decât să spunem că eficiența sa este „de ordinul”.

Anumite ordine se găsesc așa de frecvent încât li s-a dat un nume. De exemplu, dacă un algoritm ia timp în ordinul n, unde n este dimensiunea exemplului de rezolvat, spunem că el ia timp liniar. În acest caz vorbim de asemenea despre un algoritm liniar. Similar, un algoritm este pătratic, cubic, polinomial sau exponențial dacă ia un timp în ordinul lui n2, n3, nk, respectiv cn, unde k și c sunt constante corespunzătoare.

Constantele multiplicative ascunse folosite în aceste definiții pot să dea naștere la unele pericole de interpretare greșită. Considerăm de exemplu, doi algoritmi ale căror implementări dacă le dăm mașinii, iau n2 zile și, respectiv, n3 secunde în a rezolva un exemplu de dimensiune n. Nu este decât un exemplu cerând mai mult de 20 de milioane de ani în a se rezolva acest algoritm pătratic depășind algoritmul cubic. Cu toate acestea, dintr-un punct de vedere teoretic, primul este cel asimptotic mai bun decât celălalt, adică performanțele lui sunt mai bune pe toate exemplele suficient de largi.

Celelalte resurse necesare pentru execuția unui algoritm, cum ar fi memoria, pot fi estimate teoretic în același mod. Este de asemenea interesant de studiat posibilitatea unui compromis între

timp și memorie: folosind mai mult spațiu de memorie câteodată ne permite să micșorăm timpul de calcul și invers. În această lucrare ne vom axa pe timpul de lucru.

În final, notați că algoritmii în baza 2 sunt așa de frecvent folosiți în analiza algoritmilor și de aceea le vom da o notație specială astfel: „lg n” este o abreviere pentru log2 n. Tot așa, mai este folosit „ln” și „log” pentru logaritmul natural și, respectiv, logaritmul în baza 10.

Cazul mediu și cazul cel mai nefavorabil

Timpul de execuție al unui algoritm poate varia considerabil chiar și pentru două exemple diferite de aceeași dimensiune. Pentru a ilustra aceasta, considerăm doi algoritmi elementari de sortare: inserția și selecția.

procedure insert (T[1…n]) begin

for i:=2 to n do

begin

x:= T[i]; j:= j-1

while j > 0 and x < T[j] do begin

end;

end

end T[j+1]:= x

T[j+1]:= T[j]

j:=j-1

procedure select (T[1…n]) begin

for i:=1 to n-1 do

begin

end;

end

minj:=i; minx:= T[i] for j:=i+1 to n do

if T[j]<minx then begin minj:=j; minx:=T[j] end T[minj]:=T[i]

T[i]:=minx

Simulați acești doi algoritmi pe vectorii T=[3,1,4,1,5,9,2,6,5,3], U=[1,2,4,5,6] și V=[6,5,4,3,2,1]

și asigurați-vă că ați înțeles cum funcționează.

Observați că sortarea prin selecție plasează la fiecare pas câte un element direct pe poziția lui finală, în timp ce sortarea prin inserție consideră pe rând fiecare element al șirului și-l inserează în

subșirul ordonat creat anterior din elementele precedente (operația de inserare implicând deplasarea spre dreapta a unei secvențe).

Fie U și V doi vectori de câte n elemente astfel încât U este deja sortat în ordine crescătoare, iar V este deja sortat în ordine descrescătoare. Din punct de vedere al timpului de execuție, observăm că ambii algoritmi iau mai mult timp la sortarea lui V decât la sortarea lui U, astfel că V reprezintă cazul cel mai nefavorabil (nici un alt tablou de n elemente nu cere mai mult timp) iar U cazul cel mai favorabil.

Cu toate acestea, timpul cerut de algoritmul de sortare prin

selecție nu este foarte sensibil la ordinea originală a șirului de sortat: testul este executat de același număr de ori la fiecare exemplu. Variația în execuția timpului este datorată decât numărului de execuții a părții then a acestui test.

Pentru a verifica, programăm acest algoritm în Pascal. Găsim că timpul necesar sortării unui număr dat de elemente folosind sortarea prin selecție nu variază cu mai mult de 15% în funcție de ordinea inițială a elementelor pentru sortat. Timpul cerut de select (T) este pătratic, indiferent de ordinea inițială a elementelor.

Situația este destul de diferită dacă comparăm timpul luat de algoritmul de sortare prin inserție a șirurilor U și V. Pe de o parte, insert(U) este foarte rapid, deoarece condiția de control din ciclul while este întotdeauna falsă. De aceea algoritmul are o performanță liniară în timp. Pe de altă parte, insert(V) ia timp pătratic, deoarece ciclul while este executat de i-1 ori pentru fiecare valoare

i. Variația timpului de execuție este considerabilă, astfel că el crește odată cu creșterea numărului de elemente care vor fi sortate.

Dacă apar astfel de variații mari, atunci se pune problema cum putem vorbi de un timp de execuție care să depindă doar de mărimea cazului considerat?

De obicei considerăm cel mai nefavorabil caz al algoritmului,

acre este, pentru dimensiunea pe care o considerăm, aceea în care algoritmul lucrează pentru exemple ce iau cel mai mult timp. Astfel spunem că sortarea prin inserție ia un timp pătratic în cel mai rău caz. Acest tip de analiză este bun atunci când timpul de execuție al unui algoritm este critic.

De exemplu, dacă se pune problema să controlăm o centrală nucleară, este crucial să știm limita superioară a timpului de răspuns a sistemului, indiferent de exemplele particulare de rezolvat. Pe de altă parte însă, într-o situație când un algoritm este utilizat de mai multe ori pe multe exemple diferite, este poate mai important să știm media timpului de execuție a exemplelor de dimensiune n. Am vorbit că timpul luat de algoritmul de sortare prin inserție variază între ordinul lui n și n2. Dacă putem să calculăm media timpului luat de algoritm pentru n! Cazuri diferite față de ordinea inițială a

celor n elemente (presupunând că sunt toate diferite), vom avea ideea asupra timpului luat la sortarea unui șir cu ordine inițială aleatoare. Vom vedea că acest timp mediu este de asemenea în ordinea lui n2.Algoritmul de inserție ia timp un pătratic atât în medie cât și în cel mai rău caz, deși în anumite cazuri el poate fi mult mai rapid.

De obicei este mai greu de analizat purtarea medie a unui algoritm decât să analizăm purtarea lui în cel mai rău caz. Astfel, o asemenea analiză a purtării medii poate fi amăgitoare dacă de fapt cazurile de rezolvat nu sunt alese aleatoriu când algoritmul este folosit în practică. De exemplu, se poate întâmpla ca un algoritm de sortare să trebuiească să fie folosit ca o procedură internă într-un algoritm mult mai complicat, și din anumite motive, el trebuie apelat pentru sortarea unor elemente care sunt aproape deja sortate. În acest caz, ipoteza că fiecare din cele n! căi sunt diferite față ordinea inițială a celor n elemente este deja insuficientă. O analiză folositoare a comportării medii a unui algoritm necesită niște legi prioritare în distribuția exemplelor de rezolvat, și asta este normal o cerere nerealistă.

În ceea ce urmează ne vom concentra atenția mai mult asupra analizei celui mai rău caz.

Ce este o operație elementară

O operație elementară este o operație al cărei timp de execuție poate fi limitat superior de o constantă depinzând numai de implementarea particulară folosită (mașină, limbaj de programare). Deoarece suntem interesați de timpul de execuție al algoritmilor în limita unei constante multiplicative, în analiza eficienței acestor algoritmi vom lua în considerare numai numărul operațiilor elementare executate, nu și timpul exact de execuție cerut de fiecare dintre ele. Echivalent, spunem că operațiile elementare pot fi executate cu un cost unitar. În descrierea unui algoritm se poate întâmpla ca o linie a acestuia să corespundă unui număr variabil de operații elementare. De exemplu, dacă T este un șir de n elemente, timpul cerut în a calcula

x:=min {T[i]/1 i n }

crește cu n, deoarece această este o abreviație pentru x:=T[1]

for i:=2 to n do

if T[i]<x then x:=T[i]

Similar, unele operații matematice sunt prea complexe pentru a fi considerare elementare. Dacă ne este permis să evaluăm calculul factorialului și testul pentru divizibilitate la un cost unitar, trecând peste dimensiunea operanzilor, teorema lui Wilson va permite să testăm un întreg dacă este prim cu o eficiență surprizăntoare.

Function Wilson(n)

Begin

end;

{Intoarcere true daca si numai daca „n” este prim} if n divide exact (n-1)!+1 then return true

else return false

Putem considera adunarea și înmulțirea a fi operații cu cost unitar? În teorie, aceste operații

nu sunt elementare întrucât timpul necesar execuției lor crește cu lungimea operanzilor. În practică totuși este posibil, fără a greși, să le considerăm operații elementare atâta timp cât operanzii participanți au dimensiuni rezonabile în exemplele pe care ne așteptăm să le folosim. În cele ce urmează vom considera că adunările, scăderile, înmulțirile, împărțirile, operația modulo (restul împărțiri întregi), operațiile și atribuirile sunt operații elementare având un cost unitar.

De ce avem nevoie de algoritmi eficienți ?

În timp ce viteza de calcul a echipamentelor de calcul moderne devine din ce în ce mai mare, se pare că noi ne petrecem timpul încercând să descriem algoritmi din ce în ce mai eficienți. Se pune problema: oare nu ar fi mult mai ușor să așteptăm următoarele generații de calculatoare?

Pentru a clarifica acest aspect, începem prin a recunoaște că într-adevăr viteza de lucru a calculatoarelor moderne este foarte mare; de aceea vom presupune în continuare că lucrăm cu un calculator capabil să efectueze un milon de operații pe secundă. Tabel de mai jos indică timpul necesar pentru a efectua n2, n3, 2n, 3n operații cu ajutorul unui astfel de calculator.

Să presupunem că avem la dispoziția un algoritm al cărui timp de execuție pentru cazuri de mărime n este de 2n secunde. Din tabelul reiese că pentru n=20 algoritmul are nevoie de o secundă

iar pentru n=60 același algoritm are nevoie de 366 de secole. Dacă vom cumpăra un calculator de 100 de ori mai rapid, atunci timpul de rulare pentru n=50 ar fi 100 366 secole =3,66 secole (deci un timp tot neacceptabil).

Dar ce facem dacă avem de rezolvat cazuri pentru un n mult mai mare decât 50? Soluția nu poate fi alta decât găsirea unui alt algoritm mult mai eficient.

Principalul motiv pentru care unii algoritmii pot să ajungă la timpi de lucru practic infiniți, chiar pentru valori relativ mici ale lui n își găsește explicația în faptul că funcția exponențială f(n)=an cu a>1, crește extraordinar de repede și nu în lipsa de performanțe a calculatoarelor.

Conform celor de mai sus, este foarte indicat ca pentru o problemă dată să elaborăm algoritmi care să nu fie exponențiali. Sunt considerați „buni” algoritmii pentru care numărul operațiilor este polinomial (adică se poate exprima sub forma unui polinom în n, unde n este numărul datelor de intrare). Nu este posibil să evităm totdeauna algoritmii exponențiali; un exemplu îl constituie problema generării tuturor submulțimilor unei mulțimi având n elemente, când numărul rezultatelor este 2n și deci numărul de operații va fi inerent exponențial.

Poate vă întrebați dacă chiar este posibil în practică să accelerați la un așa grad un algoritm cu un timp de execuție nerezonabil încât el să devină rezonabil ca timp de execuție. De fapt, au fost nenumărate cazurile în care chiar pentru algoritmi bine stabiliți au fost făcute mai multe îmbunătățiri spectaculoase. Astfel, problema celor n dame și problema comis- voiajorului pot fi rezolvate atât prin metoda Backtracking (care este, așa cum vom vedea, o metodă cu timp de execuție exponențial) cât și prin alte metode (euristice, algoritmi probabiliști sau algoritmi genetici) ce au timpi de execuție mult mai mici. De exemplu, în capitolul VIII, veți găsi rezolvarea problemei celor n dame printr-un algoritm probabilist de tip Las Vegas ce rulează într-un timp surprinzător de mic chiar pentru valori foarte mari ale lui n.

Totuși nu este posibil să evităm totdeauna algoritmii exponențiali; un exemplu îl constituie problema generării tuturor submulțimilor unei mulțimi având n elemente, când numărul rezultatelor este 2n și deci numărul de operații va fi inerent exponențial.

Analiza eficienței algoritmilor

Până acum am dat un înțeles mai mult intuitiv situației când un algoritm necesită un timp într-un anumit ordin (liniar, polinomial, exponențial, etc). În continuare vom reveni cu o definiție puțin mai riguroasă însă fără a dezvolta și aparatul matematic necesar analizei eficienței algoritmilor (pentru aceasta puteți consulta [1], [2] sau [7] din bibliografia indicată).

Notația asimptotică

Fie N mulțimea numerelor naturale (pozitive sau zero) și R mulțimea numerelor reale. Notăm prin N+ și R+ mulțimea numerelor naturale, respectiv reale, strict pozitive, și prin R* mulțimea numerelor reale nenegative. Mulțimea de constante booleene {true, false} o notăm cu B.

Fie A un algoritm oarecare utilizat pentru rezolvarea unei probleme date. Putem considera că timpul de lucru necesar algoritmului A este o funcție:

t: N R*

care are ca domeniu de definiție mulțimea N a numerelor naturale (pozitive sau zero) ce reprezintă numărul de componente (date de intrare) sau, uneori, dimensiunea datelor de intrare, iar codomeniul este mulțimea R* a numerelor reale nenegative ce reprezintă timpii necesari algoritmului pentru prelucrarea datelor de intrare respective. Prin urmare, funcția t asociază fiecărui set de date de intrare (care are un anumit număr n de componente sau o anumită dimensiune n) un număr real nenegativ ce reprezintă timpul necesar algoritmului A pentru a determina soluția problemei în cazul cel mai nefavorabil, deci

n t (n)

Când sunt puși în discuție mai mulți algoritmi (ca de exemplu, algoritmii A, B și C) vom adăuga notației t a funcției timp un indice (tA, tB, tC) pentru a sugera cărui algoritm îi este asociată funcția respectivă.

Pentru o anumită problemă dată este foarte greu să determinăm expresia pentru funcția t. Totuși, să considerăm că pentru un algoritm oarecare am reușit să determinăm expresia pentru funcția t și fie aceasta

t(n)=2n2 +5n+6

Am văzut deja că pentru un astfel de algoritm se spune că are ordinul de complexitate O(n2). În acest caz putem să considerăm că n2 este tot o funcție pe care s-o notăm cu f

f: N R*

De fapt, notația O(n2) vrea să scoată în evidență care este termenul dominant al expresiei 2n2

+5n+6 în sensul că, atunci când n este foarte mare, termenul n2 este cel care are valoarea cea mai mare (dominantă), deci, începând de la un n0 finit și bine ales, valoarea expresiei 2n2 +5n+6 este mai mică decât valoarea expresiei cn2 (unde c este o constantă reală strict pozitivă). De exemplu, dacă luăm n0=2 și c=6 avem că:

2n2 +5n+6 cn2, nn0

sau, revenind la notațiile anterioare, avem că :

n0N și cR+ astfel încât t(n) cf(n), nn0

Prin urmare, putem spune că O(n2) este de fapt o mulțime definită astefel:

O(n2)={t: N  R* /n0N, cR+ astfel încât

t(n) cf(n), nn0 }

pe care o numim ordinul lui f și care nu este altceva decât mulțimea tuturor funcțiilor t mărginite superior de un multiplu real pozitiv al lui f, pentru valori suficient de mari ale argumentului n.

Vom conveni să spunem că t este în ordinul lui f (sau, echivalent, t este în O(f) sau tO(f) chiar și atunci când valoarea f(n) este negativă sau nedefinită pentru anumite valori n<n0 (valori care nu ne interesează din punct de vedere al timpului estimat pentru algoritm deoarece sunt valori mai mici decât n0)). În mod similar, vom vorbi despre ordinul lui f chiar și atunci când valoarea t(n) este negativă sau nedefinită pentru un număr finit de valori ale lui n; în acest caz vom alege un n0 suficient de mare, astfel încât, pentru n<n0, acest lucru să nu mai apară.

De exemplu, vom vorbi despre ordinul lui n/log n chiar dacă pentru n=0 și n=1 funcția nu este definită.

Dacă notăm cu O(1) ordinul funcțiilor mărginite superior de funcția constantă, obținem ierarhia:

O(1)O(log n) O(n) O(n log n) O(n2) O(n3) O(2n)

Vom căuta în general să găsim cea mai simplă funcție f astfel încât tO(f). Prin urmare, totdeauna dorim să obținem un algoritm corespunzător unui ordin cât mai „la stânga” în ierarhie.

În concluzie, notația O(f) se utilizează pentru a limita superior timpul necesar unui algoritm, măsurând eficiența acelui algoritm.

Uneori este util să estimăm și o limită inferioară a acestui timp. În acest scop, definim mulțimea:

(f)={t:N  R* /n0 N, cR+ astfel încât t(n) cf(n), nn0 }

Există o anumită dualitate între notațiile O(f) și (f) și anume, pentru două funcții oarecare f,g: N

 R*, avem: fO(g), dacă și numai dacă g(f).

O situație fericită este atunci când timpul de execuție al unui algoritm este limitat, atât inferior cât și superior, de către un multiplu real pozitiv al aceleiași funcții.

Introducem notația

(f)=O(f)(f)

numită ordinul exact al lui f. Pentru a compara ordinele a două funcții, notația nu este însă mai puternică decât notația O, în sensul că relația O(f)=O(g) este echivalentă cu (f)= (g).

Există situații în care timpul de execuție al unui algoritm depinde simultan de mai mulți parametri. Astfel de situații sunt tipice pentru anumiți algoritmi care operează cu grafuri și în care timpul depinde atât de numărul de vârfuri, cât și de numărul de muchii. În aceste situații notația asimptotică se generealizează în mod natural și pentru funcții cu mai multe variabile. De exemplu, pentru o funcție arbitrară f:NN R* definim O(f)={ f:NN R* / m0, n0 N, cR+ astfel încât t(m,n)cf(m,n), mm0, nn0}

Similar, se poate defini și notația asimptotică inferioară pentru funcții de două variabile precum și pentru funcții cu mai mult de două variabile.

CAPITOLUL II METODA GREEDY

Metoda Greedy (lacom) este una dintre cele mai simple metode generale de elaborare a algoritmilor și este folosită la rezolvarea problemelor de optimizare. De fapt, metoda Greedy este un algoritm de tip „constructiv” în sensul că, în rezolvarea problemei, se pornește de la o soluție posibilă (inițială), soluție posibilă (inițială), soluție care apoi se îmbunătățește ajungându-se la rezultatul dorit pas cu pas.

Pentru a ne fi mai ușor să înțelegem metoda Greedy, vom considera mai întâi un exemplu simplu prin care vom pune în evidență caracteristicile esențiale ale algoritmilor de tip Greedy.

O problemă prototip

Problema 2.1. (Problema lacomului) Un om ajunge cu barca pe o insulă pustie. Acolo, spre surprinderea sa, găsește mai multe metale prețioase (aur, argint etc.), câte un lingou din fiecare metal, și se hotărăște să le ia cu barca. În barcă el nu poate să transporte decât o anumită greutate maximă (cunoscută) și pe care n-o poate depăși pentru că altfel barca s-ar scufunda. Bineînțeles că barca sa este înzestrată cu un cântar cu care poate să cântărească metalele și mai are și un dispozitiv cu care poate să taie din fiecare lingou cât cântărește. El nu e sigur că la efectuarea unei alte curse pe insulă ar mai găsi metalele rămase așa că, fiind foarte lacom și cunoscând valoarea fiecărui lingou în întregul său (deci nu prețul unitar), dorește să ia în barca sa metalele prețioase astfel încât, atunci când va ajunge acasă, să obțină un profit maxim prin vânzarea lor.

Soluție. Mai întâi să observăm că, de exemplu, lingoul de argint privit ca un întreg poate să aibă valoarea mai mare decât cel de aur (dacă el are o greutate mult mai mare decât a celui de aur). Cu toate acestea, logica omului lacom, dornic să obțină un profit maxim, va fi să aleagă pentru a pune în barca sa mai întâi acel lingou care are prețul unitar cel mai mare (de exemplu, aurul) și nu lingoul cel mai valoros în întregul său. Dacă greutatea lingoului respectiv depășește greutatea maximă suportată de barcă, atunci el va tăia din acel lingou numai o parte egală cu greutatea suportată de barcă și problema sa e rezolvată. Dacă greutatea lingoului este mai mică decât greutatea maximă suportată de barcă, atunci el va pune în barcă acel lingou în întregime după care va încerca să pună un nou lingou (cel care are prețul unitar cel mai mare dintre cele rămase) și așa mai departe. Am putea să spunem că barca „înghite” tot ce e mai valoros pe unitatea de greutate.

Plecând de la această rezolvare practică a problemei, să încercăm o formalizare a modului de rezolvare și apoi să trecem la elaborarea programului Pascal pentru rezolvarea sa.

Fie GM greutatea maximă ce poate fi transportată cu barca, m1,m2,…..,mn greutatea fiecărui obiect iar v1,v2,…..,vn valoarea obținută pentru fiecare din cele n lingouri.

Dacă notăm cu xi masa din obiectul i ce va fi pusă în barcă este clar că xi este un număr mai mic sau cel mult egal cu mi oricare ar fi i. Să notăm cu p1,p2,…..,pn prețurile unitare (prețurile pe unitatea de masă) ale metalelor (adică pi =vi /mi oricare ar fi i).

Astfel, problema se poate reformula:

Să se determine valorile xi astfel încât să maximizați x1p1+ x2p2+………. +xnpn

cu condiția:

x1+x2+……….+xnGM Este clar că,dacă

m1+m2+……….+mn=GM atunci soluția este

xi=mi, i, 1i n.

Dar acesta este un caz particular și nu ne interesează. Presupunem în continuare că această sumă este strict mai mare decât GM, adică:

m1+m2+………+mn>GM

Condiția pentru soluția optimă se rescrie atunci:

n

xi =GM

i 1

Problema pe care ne-o punem este să găsim un criteriu după care să alegem obiectele care trebuie puse în barcă, adică să putem hotărî pe care dintre obiectele i sau j este mai avantajos să-l alegem. Sunt posibile următoarele criterii de optimizare:

vi>vj

mi>mj

vi/mi>vj/mj (adică pi>pj)

Pentru a evolua eficiența lor, vom lua un exemplu:

n=3; GM=20; v1=25; v2=24; v3=15; m1=18; m2=15; m3=10.

Soluțiile obținute folosind cele trei criterii sunt:

Mai eficient este criteriul 3 și prin urmare vom proceda astfel încât obiectele să fie alese în ordinea vi/mi>vi/mi+1 (adică în ordinea descrescătoare a prețului pe unitatea de masă). Din aceasta e și criteriul pe care omul îl intuiește a fi cel mai bun.

Pentru scrierea programului Pascal, să notăm cu A mulțimea lingourilor care se află pe insulă. Cu B să notăm mulțimea lingourilor (inclusiv fracțiuni din lingouri) ce sunt încărcate în barcă. Lingourile se caracterizează prin denumirea metalului din care sunt turnate, masa lingoului și valoarea fiecăruia dintre ele. Pentru descrierea lingourilor putem să utilizăm în Pascal tipul articol iar pentru mulțimile A și B vom utiliza vectori. Procedura greedy acționează asemănător cu un om lacom: alege (procedura alege) din mulțimea A a lingourilor de pe insulă pe cel care are prețul unitar cel mai mare după care verifică dacă este posibil (procedura posibil) să-l pună în barcă iar dacă răspunsul este afirmativ (adevărat) atunci el este adăugat (procedura adauga) la celelalte lingouri din barcă (în întregime sau numai o parte din el în funcție de capacitatea bărcii rămasă disponibilă). Iată și programul:

program Barca

uses crt;

type art=record metal:string; masa:real; valoare:real

end;

lingou=array [0…..9] of art;

var

n:integer; {Numarul de obiecte} GM :integer ; {greutatea maxima} A,B:lingou;

i:integer;

procedura greedy (var A: lingou; var n:integer; var B:lingou) var

crb:real; {Capacitatea ramasa in barca} x:art;

vb:Boolean;

procedure allege (var A:lingou; i:integer; var x:art); var

begin

j:integer; t:art;

for j:=i to n do

begin

if A[i].valoare/A[i].masa<A[j].valoare/A[j].masa then begin

t.metal:=A[i].metal; t.masa:=A[i].masa; t.valoare:=A[i].valoare; A[i].metal:=A[j].metal;

A[i].masa:=A[j].masa; A[i].valoare:=A[j].valoare; A[j].metal:=t.metal; A[j].masa:=t.masa; A[j].valoare:=t.valoare

end;

end; x.metal:=A[i].metal; x.masa:=A[i].masa; x.valoare:=A[i].valoare;

end

procedure posibil (var B:lingou; var x:art; var vb:boolean); begin

end;

if crb>0

then vb:=true else vb:=false

procedure adaug (var B:lingou; var x:art); begin

B[i].metal:=x.metal; if crb>x.masa

then begin

B[i].masa:=x.masa; B[i].valoare:=x.valoare; crb:=crb-x.masa

end ;

if (crb>0) and (crb<x.masa) then begin

B[i].masa:=crb; B[i].valoare:=crb*x.valoare/x.masa; crb:=0

begin

end;

end;

crb:=GM;

for i:=1 to n do

begin

allege (A,i,x);

end; begin

clrscr;

end

posibil (B,x,vb);

if vb=true then adaug (B,x)

write (‘Introduceti numarul de obiecte:’); readln (n); write (‘Introduceti greutatea maxima:’); readln (GM); write (‘ Introduceti metalul, masa si valoarea:’);

writeln (‘ = = = = = = = = = = = = = = = = = = = = = = = = = = ’);

for i:=1 to n do

begin

write (‘Metalul:’); readln (A[i].metal);

write (‘ Masa si valoarea:’); readln(A[i].masa, A[i].valoare) end;

greedy (A,n,B); writeln;

writeln (‘Pe barca sunt incarcate:’);

writeln (‘ = = = = = = = = = = = = = = = = = = = = ’);

writeln (‘ Metalul masa valoarea’);

writeln (‘ = = = = = = = = = = = = = = = = = = = = ’); i:=1;

while B[i].masa<>0 do

begin

writeln (‘->’, B[i].metal:9,B[i].masa:8:2,’’,B[i].valoare:82); i:=i+1

end.

end;

repeat until keypressed

Observație. Se constată că prin utilizarea instrucțiunii for se încearcă punerea în barcă a

tuturor celor n lingouri cu toate că s-ar putea ca după câteva iterații (adică după ce am pus numai câteva lingouri în barcă) barca să fie deja încărcată așa că iterațiile următoare nu mai au nici un sens. Prin urmare, programul poate fi optimizat utilizând în locul instrucțiunii for o instrucțiune repeat până ce în barcă nu mai poate fi pus nimic (adică vb are valoarea false). Optimizați programul operând această modificare.

Tipul de probleme la care se aplică metoda Greedy

Plecând de la exemplul studiat, putem să generalizăm și să spunem că metoda Greedy se aplică în rezolvarea problemelor de tipul:

„Se dă o mulțime A, finită, ce conține n date de intrare cerându-se să se determine o submulțime B a sa (B A) care să îndeplinească anumite condiții pentru a fi acceptată; cum în general există mai

multe astfel de mulțimi, se mai dă și un criteriu conform căruia, dintre submulțimile acceptabile (numite soluții posibile) să alegem una singură ca rezultat final (numită soluție optimă )”

Soluțiile posibile au următoarea proprietate:

Dacă B este soluție posibilă și C este inclusă în B, atunci și C este soluție posibilă. Vom presupune că mulțimea vidă întotdeauna soluție posibilă.

În cazul problemei prototip, mulțimea A este mulțimea lingourilor aflate pe insulă iar mulțimea B este mulțimea lingourilor care sunt puse în barcă. La început B este mulțimea vidă iar la fiecare pas al algoritmului este adăugat la mulțimea B câte un element (câte un lingou) luat din mulțimea A. Întrucât se urmărește obținerea unei soluții optime (profit maxim) această adăugare nu se face la întâmplare ci respectând un anumit criteriu de selecție a elementelor din mulțimea A ce urmează să fie incluse în mulțimea B (prețul unitar cel mai mare).

Mecanismul general

Să observăm mai întâi că elementele mulțimii A se comportă ca niște candidați pentru a intra în submulțimea B ce reprezintă soluția problemei și, prin urmare, putem spune că mulțimea A este o mulțime de candidați.

Inițial mulțimea B (a candidaților selectați) este vidă. Așa cum am văzut și din studiul problemei prototip, dintre toți candidații la un moment dat există unul care este cel mai promițător dintre cei încă nefolosiți (neincluși în mulțimea B) așa că va trebui să existe o subrutină (alege) care să-l aleagă pe acesta. O altă subrutină (posibil) va trebui să verifice dacă prin includerea canditatului cel mai promițător în mulțimea B se obține o soluție posibilă (nu neapărat optimă). Dacă da, atunci o altă subrutină (adauga) va adăuga candidatul respectiv la mulțimea B.

Acesta este, de altfel, modul de gândire al unui întreprinzător particular care urmărește câștigul imediat. Cu toate că el acționează simplist, metoda sa îl poate conduce la rezultate foarte bune în afaceri tocmai datorită simplității ei. El alege în fiecare moment afacerea care promite cel mai mare câștig cu speranța că afacerile sale vor duce la cele mai bune rezultate.

Acești algoritmi sunt numiți lacomi deoarece la fiecare pas procedura Greedy nu face altceva decât să aleagă cea mai bună pradă la momentul respectiv pe care o înghite fără a-și face griji în ce privește viitorul. Nu se răzgândește niciodată: un candidat odată inclus în soluție, el rămâne acolo pentru întotdeauna iar dacă la un pas al algoritmului un candidat a fost respins el nu va fi reconsiderat la acel pas.

Algoritmul este următor: Procedure Greedy (A,n,B)

B:=multimea vida for i:=1 to n do

begin

call allege (A,i,x) {x este elementul care se adauga la solutia partiala anterioara}

call posibil (B,x,vb) {vb este o variabila booleana: vb=1 daca prin

adaugarea lui x obtinem o solutie posibila}

end;

if vb=1 end

then call adauga (B,x)

Așadar, se pleacă de la soluția vidă. Se alege, pe rând, într-un anumit fel un element din A reales la pașii precedenți. Dacă adăugarea lui la soluția parțială anterioară conduce la o soluție posibilă, construim noua soluție posibilă prin adăugarea elementului ales.

Procedura alege furnizează elementul x=aj edin mulțimea formată din elementele ai, ai+1,……,an care au rămas nealese din A și efectuează interschimbarea lui ai cu aj.

Procedura posibil furnizează în variabila v valoarea 1 (adevărat) dacă B reunită cu mulțimea formată din elementul x este o soluție posibilă și 0 (fals) în caz contrar.

Procedura adauga înlocuiește pe B prin B reunit cu mulțimea formată din elementul x.

Observații. 1) Dacă procedura posibil efectuează verificări date prin enunțul problemei, lucrurile sunt mai complicate în cazul procedurii alege în care trebuie să stabilim un criteriu conform căruia alegerea, în final, să conducă la soluția optimă. În cazul problemei prototip am utilizat ca și criteriu pentru alegerea elementelor din A, alegerea lingoului pentru care prețul unitar este cel mai mare.

2) Pentru rezolvarea problemei prototip alese ordinea în care am considerat elementele din mulțimea A a fost stabilită în mod dinamic la fiecare pas al algoritmului Greedy. Bineînțeles că această ordine ar fi putut fi stabilită încă de la început (static) printr-o subrutină (prel) care să prelucreze în așa fel mulțimea A, a lingourilor aflate pe insulă, în ordinea descrescătoare a prețului lor unitar. De fapt, în general, procedura prel efectuează o permutare a elementelor mulțimii A (pe care o considerăm reprezentată de un vector A cu n componente). Procedura Greedy în această situație, este următoarea:

Procedura Greedy (A,n,B) call prel (A)

B:=multimea vida for i:=1 to n do

begin

call posibil (B,a,vb) {vb este o variabila booleana: vb=1 daca

prin adăugarea lui ai obținem o soluție posibila}

end;

end

if vb=1

then call adauga (B,a1)

Se observă că ambele proceduri Greedy urmează aceeași idee, dar diferă doar prin ordinea efectuării anumitor operații.

II. 4. Complexitatea algoritmilor Greedy

Mecanismul tehnicii Greedy conduce la aceeași timp de calcul.

Să presupunem că mulțimea din care se face alegerea are n elemente și că soluția are tot n elemente (cazul maxim). Se fac n alegeri, la fiecare alegere se fac n teste, rezultă un algoritm cu timp O(n2).

De multe ori, este necesar ca elementele mulțimii A să fie sortate, pentru ca apoi să alegem din acestea, iar sortarea necesită un timp minim O(nlog2n). Însă sortarea se efectuează la început. Prin urmare, acest timp se adună, deci nu influențează rezultatul.

Avantajul timpului polinomial conduce la necesitatea utilizării tehnicii Greedy. Din alt punct de vedere, nu tuturor problemele li se pot aplica algoritmi de acest tip.

Pentru problemele pentru care nu se cunosc algoritmi care necesită timp polinomial, se caută soluții, chiar dacă nu optime, dar apropiate de acestea, dar care au fost obținute în timp util. Multe din aceste soluții sunt obținute cu metoda Greedy. Astfel de algoritmi se numesc algoritmi euristici (despre ei vom discuta în capitolul VI).

CAPITOLUL III METODA BACKTRACKING

În capitolul II am văzut că algoritmii Greedy nu consideră niciodată candidații. În continuare vom studia metoda Backtracking (a căutării cu revenire) care este o metodă tot ”constructivă” dar, spre deosebire de metoda Greedy, ea are această proprietate că revine asupra valorilor nealese.

Două exemple prototip

Problema 3.1. Fie două mulțimi de litere S1={A,B,C}și S2={M,N}.Se cere să se determine acele perechi (x1,x2) cu x1 S1 si x2 S2 cu proprietatea că dacă x1 este A sau B, atunci x2 nu poate fi N.

Soluție. Pentru această problemă sunt posibile următoarele șase soluții:

(A,M), (A,N), (B,M), (C,M), (C,N).

Dintre acestea numai patru îndeplinesc condițiile din enunțul problemei

(A,M), (B,M), (C,M), (C,N).

acestea numindu-se soluții rezultat. Prin urmare aceste soluții ale problemei sunt numai acelea care îndeplinesc condițiile interne.

Observație. Soluțiile problemei se regăsesc printre elementele produsului cartezian S1 x S2.

Acest produs cartezian se mai numește și spațiul soluțiilor posibile.

Problema 3.2 (Pronosport). Fie un joc de tip Pronosport la care, pentru simplitate vom considera că în discuție sunt doar 4 meciuri. Să presupunem ca o persoană dorește să participe la acest joc, plecând cu convingerea ca în variantele câștigătoare nu pot exista mai mult de două meciuri nule (cu pronostic X), iar la ultimul meci gazdele nu câștigă; pentru aceasta, ea dorește să găsească variantele care îndeplinesc aceste condiții.

Soluție. Prin urmare, problema cere determinarea unor vectori x=(x1,x2,x3,x4), în care valorile componentelor sunt pronosticuri (X,1 sau 2 ) pentru cele patru meciuri. Rezultă ca pentru aceasta problema spațiul soluțiilor posibile este produsul cartezian S1xS2xS3xS4, unde S1=S2=S3=S4={1,x,2}. Un asemenea vector, pentru a fi soluție rezultat, trebuie să îndeplinească următoarele două condiții interne :

în vector nu pot să apară mai mult de două pronosticuri X;

ultima componentă poate fi doar X sau 2.

Desigur, există mai mulți vectori care îndeplinesc aceste condiții, ca de exemplu :

(X,1,2,X), (1,2,1,2) etc.

O modalitate directă de rezolvare a problemei este următoarea : se generează pe rând toate cele 34= 81 soluții posibile și se aleg cele care satisfac condițiile din enunț. Să observăm însă ca dacă în loc de 4 meciuri vom considera 13 meciuri, așa cum se întâmplă în realitate, vor exista 313

= 1.594.323 variante, adică un număr foarte mare de soluții posibile. Mai precis, numărul soluțiilor posibile, deci și timpul de lucru, depind exponențial de lungimea n a vectorului.

Astfel, în cazul general, chiar pentru │Si│=2, i timpul necesar este O(2n), deci

exponențial.

Tipul de probleme la care se aplica metoda Backtracking.

Așa cum am văzut deja,metoda Backtracking se aplică la probleme în care soluția se poate reprezenta sub forma unui vector.

x=(x1,x2,……xn) S1 x S2 x…….x Sn,

unde mulțimile S1, S2,………Sn sunt mulțimi finite având s1, s2………. respectiv sn elemente (unde am notat cu și cardinalul mulțimii Si, adică numărul de elemente pe care le conține mulțimea Si).

Pentru fiecare problemă concretă sunt date anumite relații între componentele x1, x2,……..,xn ale vectorului x, anumite condiții interne.

Mulțimea finita S1 xS2 x…..x Sn (pe care o s-o notăm cu S) se numește spațiul soluțiilor posibile.

Soluțiile posibile care satisfac condițiile interne se numesc soluții rezultat.

Ceea ce ne propunem este de a determina toate soluțiile rezultat (cu scopul de a le lista sau de a alege dintre ele una care maximizează sau minimizează o eventuala funcție obiectiv dată).

Întrucât, metoda (e adevărat, simplă) de a determina soluțiile rezultat prin generarea într-un mod oarecare a tuturor soluțiilor posibile și de a verifică dacă ele satisfac condițiile interne este costisitoare din punct de vedere al timpului de execuție (determinarea tuturor soluțiilor posibile durează foarte mult ) și prin urmare nu este utilă vom utiliza o altă metoda, mult mai eficientă, cunoscută sub numele de metoda Backtracking.

Mecanism general

Metoda Backtracking urmărește să evite generarea tuturor soluțiilor posibile. În acest scop elementele vectorului x=( x1, x2,……..,xn) primesc pe rând valori în ordinea crescătoare a indicilor, în sensul ca lui xk i se atribuie o valoare numai dacă au fost atribuite deja valori lui x1, x2, …..,xk-1. Mai mult, odată stabilită o valoare pentru xk-1. Aceste condiții stabilesc situațiile în care are sens să trecem la calculul lui xk, neîndeplinirea lor exprimând faptul că oricum am alege xk…….,xn nu vom putea ajunge la o soluție rezultat, adică o soluție pentru care condițiile interne să fie satisfăcute (deci condițiile de continuare sunt strict necesare pentru obținerea unor soluții ).

Astfel, dacă în problema 3.2 componentele x1 și x2 au primit amândouă valoarea X, atunci lui x3, nu i se poate atribui această valoare (pentru a nu încălca restricția ca numărul maxim de pronosticuri X să fie cel mult 2).

Evident ca în cazul neîndeplinirii condițiilor de continuare va trebui să facem o altă alegere pentru xk sau, dacă Sk a fost epuizată, se încearcă să se facă o nouă alegere pentru componentă precedenta xk-1 a vectorului (ceea ce înseamnă că micșoram pe k cu o unitate) după care facem o nouă alegere pentru xk etc. Această revenire (prin micșorarea lui k ) da numele metodei, ilustrând faptul că atunci când nu putem avansa, urmărim înapoi secvența curentă din soluție. Este evident ca între condițiile de continuare și condițiile interne există o strânsă legătură. O bună alegere pentru condițiile de continuare are ca efect o reducere a numărului de calcule. Faptul că valorile curente v1,v2,…..,vk-1 ale lui x1,x2,….,xk-1 satisfac condițiile de continuare nu este suficient pentru a garanta că se va obține o soluție ale cărei prime k-1 componente coincid cu valorile v1,v2,…..,vk-1. Astfel în cazul problemei 3.2, chiar dacă valorile curente pentru x1 și x2 sunt X, iar pentru x3 este 1 (deci aceste valori îndeplinesc condițiile de continuare), totuși (X,X,1,1) nu este soluție. De obicei condițiile de continuare reprezintă restricția condițiilor interne la primele k componente ale vectorului. Este evident că în cazul k=n condițiile de continuare sunt chiar condițiile interne.

Prin metoda Backtracking, orice vector soluție este construit progresiv, începând cu prima componentă și mergând către ultima, cu eventuale reveniri asupra valorilor atribuite anterior (cu unul sau mai puțini pași înapoi, atâta timp cât este posibilă revenirea). Prin atribuiri sau încercări de atribuire eșuate din cauza nerespectării condițiilor de continuare, anumite valori sunt ”consumate” (reamintim că x1,x2,……,xn primesc valori în mulțimile finite S1,S2,….,Sn ). Vom nota cu Ck mulțimea valorilor consumate deja la momentul curent pentru componenta xk (evident Ck Sk).

O descriere completă a metodei se poate face prin precizarea în momentul în care se încearcă atribuirea unei valori componentei xk a următoarelor elemente:

valorile curente v1,v2,…..,vk-1 ale componentelor x1,x2,……,xk-1;

mulțimile C1,C2,……Ck-1 de valori consumate pentru fiecare dintre componentele x1,x2,……,xk-

1;

Putem să sintetizăm această descriere printr-un tabel numit configurație având următoarea formă:

O astfel de configurație are următoarea semnificație:

componentele x1,x2,……,xk-1 au primit valorile v1,v2,…..,vk-1 în încercarea de a construi un vector soluție;

aceste valori satisfac condițiile de continuare;

pentru componenta xk urmează să se facă o încercare de atribuire a unei valori; deoarece valorile consumate până în acest moment pentru xk sunt cele din Ck componenta xk urmează a primi o valoare vk Sk \Ck.

valorile consumate pentru componentele x1,x2,……,xk-1 sunt cele din mulțimile C1,C2,……, respectiv Ck-1, cu precizarea că valorile curente

v1,v2,…..,respectiv vk-1 sunt considerate consumate, deci apar în mulțimile C1,C2,……, respectiv Ck-1 ;

pentru componentele xk+1, xk+2,……,xn nu s-a consumat nici o valoare și prin urmare Ck+1=Ck+2=……=Cn=;

până în acest moment au fost deja construite:

eventualele soluții de forma (v1,v2,…..,vk-1, ck,…) cu ck Ck;

eventualele soluții de forma (c1,c2,….,ck.-1,…..) cu (c1,c2,….,ck.-1) C1 C2 …..Ck-1 și (c1,c2,….ck-1) (v1,v2,….vk-1).

De exemplu, în construirea variantelor jocului de pronosport cu patru meciuri din problema 3.2, pentru k=4 configurația:

are semnificația:

se încearcă a se construi variante ce încep prin (X,X,2)

tripletul (X,X,2) satisface condițiile de continuare (deoarece până acum varianta nu are mai mult de două pronosticuri nule);

urmează o încercare de atribuire prin care x4 ar urma să primească una dintre valorile din mulțimea S4 \ C4 = {X,1,2,}\ {X}={1,2}, bineînțeles dacă vor fi satisfăcute condițiile de continuare (pentru această problemă este vorba chiar de condițiile interne, fiind vorba de ultima componentă x4);

d) C1={X}, C2={X}, C3={X,1,2},C4={X};

componentele xk+1, xk+2,…..,xn nu există (k+1=5 și n=4), deci în cazul de față, acest subpunct nu are obiect;

până în acest moment au fost construite deja:

soluții de forma (X,X,2,?), adică soluția (X,X,2,2);

soluțiile de forma (X,X,X,?), (X,X,1,?) adică soluția (X,X,1,2).

Aplicarea metodei Backtracking începe în situația în care nici o valoare nu a fost consumată și se încearcă o atribuire asupra primei componente. Acest lucru este specificat prin configurația inițială, a cărei formă este:

în care toate mulțimile Ck sunt vide. Denumirea acestei configurații este justificată prin semnificația sa conform subpunctele a) –f).

Configurațiile soluție au forma:

cu semnificația că vectorul (v1,v2,….vn) este soluția a problemei, conform subpunctelor a) și b). De exemplu, pentru problema 3.2, configurația.

are semnificația că vectorul (X,X,1,2) este o soluție a problemei (deci, este o configurație soluție).

O configurație, în cursul aplicării metodei Backtracking poate fi obiectul a patru tipuri de modificări, prezentate în cele de urmează.

Atribuie și avansează. O modificare de acest tip are loc atunci

când Ck Sk (deci, mai există valori neconsumate pentru xk) iar valoarea aleasă vk Sk\ Ck are proprietatea că v1,v2,….vk-1,vk satisfac condițiile de continuare. În acest caz valoarea vk se atribuie lui xk și este adăugată mulțimii Ck (adică este considerată consumată), după care se avansează la componenta următoare xk+1. Această modificare a configurației date este notată prin vk și are următorul efect:

De exemplu, în problema cu jocul de pronosport avem următoarele modificări de configurații:

Prin care pornind de la configurația inițială, primele două componente au primit valori (pronosticul nul) ce satisfac condițiile de continuare. Observăm că, la fiecare modificare, bara verticală s-a deplasat spre dreapta cu câte o poziție, ceea ce indică avansul.

Încercare eșuată. O astfel de modificare are loc atunci când, ca și în cazul anterior, mai există valori neconsumate pentru xk, dar de data aceasta valoarea aleasă vk Sk\ Ck face ca v1, v2,…vk-1,vk să nu verifice condițiile de continuare. Într-o asemenea situație valoarea vk este adăugată mulțimii Ck (este deci consumată), dar nu se avansează la componenta următoare. Modificarea este notată prin vk și are numărul efect:

În problema 3.2. considerată ca exemplu, procesul de modificare continuă prin:

Deoarece încercarea de a atribui pe X lui x3 a eșuat, se observă că bara verticală a rămas pe aceeași poziție.

Revenire. O modificare de acest tip are loc atunci când Ck = Sk (deci toate valorile pentru xk au fost consumate). În această situație se revine la componenta xk-1 încercând atribuirea unei noi valori pentru această componentă. Este important de remarcat că pentru această nouă valoare a lui xk-1 se vor încerca ulterior toate valorile posibile pentru xk deci revenirea la xk-1 trebuie însoțită de reconsiderarea valorilor consumate {Ck va deveni mulțimea vidă}. Modificarea este notată prin  și are următorul efect:

unde prima modificare este o revenire (x3 urmează să capete o nouă valoare iar pentru x4 vor fi încercate ulterior toate valorile posibile).

Revenire dpă construirea unei soluții . O modificare de acest tip are loc atunci când toate componentele vectorului au primit valori ce satisfac condițiile interne, adică a fost construită o soluție. În această situație se revine din nou la situația în care ultima componentă xn urmează să primească alte valori (dacă mai există) pentru construirea altor soluții. Modificarea este notată prin

<<< și are următorul efect:

În problema considerată, au loc modificările:

Care pun în evidență și două configurații soluție.

Observație. Revenirea după construirea unei soluții este de fapt un caz particular de revenire.

Într-adevăr, dacă nu imaginăm că vectorul x are o componentă suplimentară xn+1 care nu poate lua nici o valoare (adică Sn+1=), atunci o configurație soluție poate fi văzută ca o configurație obișnuită în care k=n+1. Deoarece Sn+1=mulțimea de valori este epuizată și deci se revine la componenta anterioară printr-o modificare de tipul În practică, condiția k=n+1 este cea utilizată de obicei pentru a sesiza obținerea unei soluții.

O importantă problemă este aceea a încheierii procesului de căutare a tuturor soluțiilor. Având în vedere că S1,S2,…..Sn sunt mulțimi finite, iar prin modificările succesive de configurație, rezultă că la un moment dat se va ajunge la următoarea configurație:

numită configurație finală . În acest caz ar trebui să aibă loc o revenire (deoarece toate valorile pentru x1 au fost consumate), adică o deplasare a barei verticale la stânga. Deoarece acest lucru nu este posibil, procesul de obținere a soluțiilor se va încheia aici. Dacă ne imaginăm că vectorul x mai are o componentă suplimentară x0 în extremitatea stângă, atunci deplasarea barei verticale către stânga are loc și în cazul configurației finale, trecându-se la o configurație în care k=0. În practică această condiție este utilizată de obicei pentru a sesiza finalul procesului de construire a tuturor soluțiilor.

Înainte de a trece la prezentarea metodei Backtracking sub formă de algoritm este util să urmărim și problema 3.1. modificările de configurație care au loc:

Observăm că procesul de obținere a vectorilor soluție prin metoda Backtracking este ușor de programat deoarece orice modificare de configurație nu afectează decât puține elemente și anume indicele k al componentei din dreapta barei (cea care urmează să primească o valoare), componenta x2 și mulțimea Ck de valori consumate. Algoritmul corespunzător este următorul:

Procedure Backtracking

Initializeaza multimile de valori S1,S2,….Sn

{Construieste configuratia initiala:} k:=1

C1,C2,……..Cn: = mulțimea vida

while k>0 do {Configuratia nu este finala} begin

if k=n+1

then {Configuratia este de tip solutie} begin

Retine solutia x=(x1,x2,…..,xn)

k :=k-1{Revine dupa construirea unei solutii}

else

end

if Ck<>Sk

then {Mai exista valori neconsumate} begin

Alege o valoare vk din Sk\Ck Ck:=CkU {vk}

if v1,…vk satisfac conditiile de continuare then {Atribuie si avanseaza}

begin xk:=vk;k:=k+1 end else {Incercare esuata}

end

else {Revenire}

begin

end

end

Ck:= multimea vida k:=k-1

Observăm că programarea algoritmului de mai sus se simplifică mult dacă se consideră că mulțimile de valori S1,S2,….Sn sunt de forma:

S1={1,2,…,s1}, S2={1,2,…,s2},……, Sn={1,2,…,sn} deci fiecare mulțime Sk este formată din

primele sk numere naturale, începând cu 1. Prin urmare mulțimea Sk poate fi reprezentată simplu prin numărul său de elemente sk. Se presupune de asemenea că valorile pentru fiecare componentă xk vor fi alese în ordine crescătoare.

În această situație, fiecare mulțime de valori consumate Ck este de forma {1,2,…vk} și drept consecință poate fi reprezentată doar prin valoarea vk. Cum vk este numărul elementelor mulțimii Ck,această mulțime este vidă dacă și numai dacă vk=0.

Cele de mai sus permit înlocuirea în algoritm a mulțimilor cu numere ; mai mult linia a doua a configurațiilor devine inutilă, ea putând fi dedusă din valorile componentelor x1,x2,…xk.

În multe probleme mulțimile în care pot lua valori componentele vectorului sunt toate

identice cu o mulțime finită oarecare S cu s elemente, codificată astfel: S={1,2,….,s}

În acest caz, procedura corespunzătoare este:

Procedure Backtracking;

var k,i: integer;

begin

k :=1;

for i :=1 to n do x[i]:=0; {Construieste configuratia initiala} while k <>0 do {Configuratia nu este finala}

if k=n+1

then {Configuratia este de tip solutie} begin

retsol ; {Retine solutia}

k :=k-1 {Revenire dupa construirea unei soluii}

end

else if x[k]<s

then {Mai exista valori neconsumate pentru x[k]} begin

x[k]:=x[k]+1;{S-a ales valoarea urmatoare} if continuare (k)

then k:=k+1 {Avanseaza}

end;

end

else {Revenire}

begin x[k]:=0; k:=k-1 end

Procedura Backtracking apelează:

-procedura retsol care reține soluția, adică valorile vectorului x. În mod concret, aceasta poate însemna listarea soluției, compararea ei cu soluțiile precedente (dacă, de exemplu căutăm soluția optimă) etc.

-funcția continuare (k) verifică dacă valorile primelor k componente ale vectorului x satisfac condițiile de continuare; în caz afirmativ este întoarsă valoarea true, iar în caz contrar valoarea false.

De exemplu, programul de mai jos generează soluțiile jocului de pronosport prezentat în problema 3.2. Mulțimea S conține elementele 1,2,3, în loc de X, 1, respectiv 2.

Program pronosport;

const n=4; s=3;

var x: array [1..n] of 0..s;

procedure retsol;

var i: integer;

begin

write (‘Varianta:’); for i:= 1 to n do case x[i] of

1: write (‘X’);

2: write (‘1’);

3: write (‘2’);

end;

end; writeln

function continuare (k: integer): Boolean; var nx {numarul de pronosticuri x},

i : integer ;

begin

end;

nx:=0;

for i:= 1 to k do

if x[i]=1 then nx:=nx+1;

continuare :=(nx<= 2) and ((k<>4) or (x[k]<>2))

procedure Backtracking;

var k,i: integer;

begin

k:=1; for i:=1 to n do x[i]:=0; while k <>0 do

if k =n+1

then begin retsol; k:=k-1 end else if x[k]<s

then begin

end

x[k]:=x[k]+1;

if continuare (k)then k:=k+1

begin end.

end;

Backtracking

else begin x[k]:=0; k:=k-1 end

III.4. Complexitatea algoritmilor Backtracking

Dacă mulțimile S1,S2,…..,Sn au același număr s de elemente, timpul necesar este O (Sn), deci exponențial. Dacă mulțimile S1,S2,…..,Sn nu au același număr de elemente, atunci putem să luăm min { s1,s2,…..,sn } și să notăm această valoare cu m iar max { s1,s2,…..,sn } să o notăm cu M. Atunci, timpul necesar este cuprins între O (mn) și O (Mn), prin urmare tot exponențial.

Prin urmare, metoda Backtracking, este în general, ineficientă având complexitate exponențială. Ea se utilizează totuși în situațiile în care se pot face optimizări în procesul de căutare, evitând, într-o etapă cât mai timpurie a analizei, căile care nu duc la soluție. Există și situații când rezolvarea prin metoda Backtracking nu poate fi înlocuită prin alte metode mai eficiente cum ar fi, de exemplu, problemele în care se cer toate soluțiile acceptabile.

Deci, având un timp de execuție exponențial, utilizarea metodei Backtracking se justifică numai atunci când nu cunoaștem o altă metodă cu eficiență mai mare sau avem de rezolvat probleme în care se cere generarea tuturor soluțiilor.

Backtracking generalizat (în plan)

Fie un caroiaj având m linii și n coloane ca cel din figura III.2.

Figura III.2. Exemplu de caroiaj.

Să presupunem că un mobil (piesă de șah, robot etc.)pleacă din punctul (pătratul) inițial (i0, j0), unde i0 reprezintă numărul liniei, iar j0 reprezintă numărul coloanei și că el se deplasează conform unor reguli sintetizate (memorate) în doi vectori di și dj având o dimensiune d dată, cu următoarea semnificație: dacă mobilul se află în punctul de coordonare (i,j), el se poate deplasa doar într-unul dintre punctele (i+di[k],j +dj[k]), k=1,2,….,d, bineînțeles cu condiția ca să nu iasă din caroiaj.

De exemplu, să presupunem că mobilul se poate deplasa doar astfel:

cu o poziție la dreapta pe aceeași linie;

cu o poziție la stânga pe aceeași linie;

cu o poziție în sus pe aceeași coloană;

cu o poziție în jos pe aceeași coloană.

Ca urmare a acestor posibilități de mișcare a mobilului, vom avea: di = (0,0,1,-1) și

dj = (1,-1,0,0),

astfel că, de exemplu, pentru k=2 vom avea di[k]=0 și dj[k]=-1 ceea ce are următoarea semnificație: mobilul se deplasează zero linii și o coloană în jos (semnul minus indicând mișcarea mobilul la stânga și în jos iar semnul plus indicând mișcarea la dreapta și în sus).

În practică apar de nenumărate ori astfel de situații și, mai mult, în unele probleme, se consideră că anumite pătrate ale caroiajului sunt ” ocupate ” (ceea ce înseamnă că mobilul nu poate fi plasat prin deplasări succesive într-un astfel de pătrat). Bineînțeles că pătratul inițial se presupune că nu este ocupat.

Frecvent se întâlnesc probleme ce constau în:

simularea mișcării mobilului;

determinarea pătratelor în care mobilul poate să ajungă prin deplasări permise;

determinarea unei succesiuni de deplasări în urma cărora mobilul poate să ajungă într-un punct (if, jf) dat, dacă o astfel de succesiune există;

determinarea celei mai scurte succesiuni de deplasări în urma cărora mobilul poate să ajungă într-un punct (if, jf) dat, accesibil din punctul inițial (traseul optim).

Astfel de probleme pot fi rezolvate și prin aplicarea metodei Backtracking

(dar în unele situații sunt mult mai eficiente alte metode cum ar fi, de exemplu metoda Branch and Bound).

Pentru rezolvarea unor astfel de probleme cu metoda Backtracking, vectorului x întâlnit până acum în acest capitol va avea în continuare o nouă semnificație. Elementele sale vor lua valori în mulțimea {1,2,…,d} iar semnificația sa este următoarea: dacă după k mutări mobilul a ajuns în poziția (i,j), atunci după următoarea sa mutare, mobilul va ajunge în poziția (i+di[x[k]], + dj[x[k]]). Cu alte cuvinte, vectorul x va conține numărul de ordine al deplasărilor permise (adică va conține indicele la care s-a ajuns în tablourile di și dj).

Funcția continuare va fi tot o funcție booleană ce permite să determinăm dacă o anumită încercare de deplasare este permisă, adică nu se ajunge la vreuna dintre eventualele poziții ocupate și nu se iese din caroiaj.

Procedura Backtracking este asemănătoare cu cele utilizate anterior în acest capitol numai că vor apare în plus în ea variabilele i și j cu semnificația că (i,j) este poziția curentă a mobilului.

Să aplicăm toate la o problemă concretă.

Problema 3.5. (Săritura calului). Fie dată o ”tablă de șah”, de dimensiunea n n. Se pleacă cu un cal din poziția (1,1), adică din colțul din stânga sus. Nefiind interzisă nici o poziție, se cere să se efectueze cu calul, conform regulilor de șah, o succesiune de mutări astfel încât calul să treacă o dată numai o dată prin fiecare pătrat al tablei de șah.

Soluție. Ca urmare a posibilităților mișcării calului, vom avea: di= (1,2,2,1,-1,-2,-2,-1) și

dj= (2,1,-1,-2,-2,-1,1,2).

Se va utiliza o matrice a. Pentru ca verificările efectuate de funcția continuare să fie mai ușoare, vom ”borda” matricea a cu două prime linii, cu două ultime linii, cu două prime coloane și cu două ultime coloane, pătratele noi introduse prin bordare intrând în categoria celor ocupate (interzise). Bordarea s-a făcut cu câte 2+2 linii și 2+2 coloane deoarece calul poate să sară cu câte două pătrățele la dreapta sus, stânga sau jos. Drept urmare, liniile și coloanele vor fi numerotate cu – 1,0,1,…,n,n+1,n+2. Ne propunem ca în final matricea a să ilustreze traseul calului, deci să conțină

elementele 1,2,…n2 astfel încât o săritură a calului de pe o poziție pe poziția următoare să

corespundă la numere succesive în matrice. Pozițiile interzise vor primi valoarea –1, iar cele libere (pozițiile efective ale tablei de șah) vor primi valoarea 0 (aceste inițializări fiind efectuate de procedura inițializare). Prin urmare, calul poate să treacă în poziția (i,j) dacă și numai dacă a[i,j]=0.

Pentru a evita determinarea de soluții simetrice, vom pune a[2,3]=2 și vom începe cu k=2, a[1,1]=1 și a[2,3]=2. De altfel vom urmări determinarea unei singure soluții pentru că și așa timpul de execuție va fi destul de mare chiar pentru valori mici ale lui n (ca de exemplu, pentru n=8 execuția programului durează circa o oră). Deficiența acestui algoritm constă în faptul că ordinea de deplasare a calcului plecând din poziția inițială este prestabilită prin vectorii di și dj, fixați de la început.

Procedura backtracking se termină când au fost ocupate toate cele n2 câmpuri ale tablei de

șah.

Backtracking recursiv

Până aici am studiat numai varianta iterativă pentru metoda Backtracking. În continuare vom aborda modalitatea de implementare recursivă a metodei Backtracking.

Presupunem că toate cele n mulțimi în care pot lua valori componentele vectorului sunt identice cu mulțimea finită S={1,2,…,s}. În această situație, variantă recursivă a procedurii Backtracking este următoarea:

begin

Procedure Backtracking (k: integer);

var i: integer;

if k=n+1

then retsol {Retine solutia} else for i:=1 to s do

begin

end;

end

x[k]:=i;

if continuare (k)

then Backtracking (k+1)

Parametrul k din această procedură reprezintă numărul de ordine al componentei lui x ce urmează să primească o valoare din S. Pentru inițierea procesului de generare a soluțiilor, în unitatea de program care inițiază procesul backtracking se va utiliza apelul:

Backtracking (1)

Problema 3.6. (Colorarea hărților). Fie dată o hartă ca cea din figura III.3, în care sunt prezentate schematic 6 țări T1,T2,…..,T6, dintre care unele au granițe comune.

Figura III.3. O hartă cu 6 țări.

Presupunând că dispunem doar de trei culori (galben, albastru și roșu), se cere să se

Determine toate variantele de colorare a hărții, care să respecte condiția ca orice două țări vecine (care au frontieră comună) să fie colorate diferit.

Soluție. Pentru a memora relația de vecinătate dintre țări este folosită matricea vecin definită

prin:

Pentru harta din figura III.3, matricea vecin corespunzătoare este următoarea:

Problema poate fi generalizată ușor la o hartă cu n țări ce trebuie colorată {cu restricția menționată} folosind un număr dat de s culori.

Programul Pascal e următorul.

Program Colorare_harta; const n=6; s=3;

var vecin:array[1..n,1..n] of boolean; x: array[1..n] of 0..s;

pocedure retsol;

var i:integer; begin

write (‘O varianta este:’); for i:=1 to n do

case x[i] of

1:write (’g’);

2:write (’a’);

3:write (’r’);

end;

writeln

end;

function continuare (k: integer): boolean var i:integer;

b:boolean;

begin

b;=true; i:=1;

while b and (i<k) do begin

end;

b:=not (vecin[k,i] and (x[k]=x[i])); i:=i+1

continuare: =b

end;

procedure citeste;

var i,j:integer; begin

for i:=1 to n do

for j:=1 to n do vecin[i,j]:=false;

for i:=1 to n do

begin

write (‘ Tara’, i:2, ‘este vecina cu tarile:’); read(j); while j<>0 do

begin

end

writeln

end;

end

vecin[i,j]:= true; vecin[j,i]:= true; read(j)

procedure backtracking (k:integer); var i:integer;

begin

if k=n+1

then retsol

else

for i:=1 to s do

begin

begin

end;

citeste;

end

x[k]:=i;

if continuare (k) then backtracking (k+1)

end.

writeln (‘Tara: 1 2 3 4 5 6 ’);

backtracking (1)

Să considerăm cazul particular a trei țări astfel:

și a două culori: galben și alb (deci n=3 și s=2). Diferitele ipoteze ale procedurii backtraking vor fi notate cu backtraking (k), cu k=1,2,3,4. Evident, pentru k=1,2,3, procedura backtraking (k) va apela procedura backtraking (k+1), iar la reîntoarcerea din procedura backtraking (k+1) în backtraking (k) (reîntoarcere cauzată fie de epuizarea valorilor posibile pentru xk+1, fie de situația k=n+1), ipoteza procedurii backtraking (k+1) este distrusă.

Efectul apelului backtraking (1) din programul principal este următorul:

se crează o ipoteză a procedurii backtraking (1); x[k] primește valoarea1;

se crează o ipoteză a procedurii backtraking (2); x[2] primește valoarea1 (care este neconvenabilă deoarece funcția continuare întoarce rezultatul false), iar apoi valoarea2;

se crează o ipoteză a procedurii backtraking (3); x[3] primește valoarea1;

se crează o ipoteză a procedurii backtraking (4); drept rezultat fiind afișată soluția:

g a g

se revine la procedura backtraking (3); x[3] primește valoarea2; (neconvenabilă);

se revine în procedura backtraking (2);

se revine în procedura backtraking (1); x[1] primește valoarea2;

se crează o nouă ipoteză a procedurii backtraking (2); x[2] primește valoarea1;

se crează o nouă ipoteză a procedurii backtraking (3); x[3] primește valoarea1 (neconvenabilă) și apoi valoarea 2;

se crează o nouă ipoteză a procedurii backtraking (4); drept rezultat fiind afișată soluția:

a g a

se revine la procedura backtraking (3); iar apoi în procedura backtracking (2); x[2] primește valoarea 2 (neconvenabilă);

se revine la procedura backtracking (1), iar apoi în programul principal.

Variante ale metodei backtracking

Până acum am prezentat metoda Backtracking în forma sa standard. În practică se întâlnesc nenumărate „abateri” de la această formă standard a metodei Backtracking, dintre care cele mai uzuale sunt următoarele:

soluția x poate avea un număr variabil de componente (deci nu neapărat n);

dintre soluții trebuie aleasă una care să maximizeze (minimizeze) o funcție de cost iar această soluție se va numi soluție optimă.

Problema care urmează ilustrează ambele aspecte menționate mai sus.

Problema 3.7. (Subșir maxim). Fie dat un vector a cu n

componente întregi. Să se determine un subșir al lui a (ale cărui elemente sunt luate dintre componentele vectorului a nu neapărat unul imediat după celălalt) de lungime maximă, subșir ale cărui elemente sunt în ordine crescătoare. Mai precis se caută cea mai mare valoare k pentru care există indicii x[1]<x[2]<….<x[k] astfel încât a[x[1]]<a[x[2]]<…<a[x[k]].

Exemplu. Pentru n=7 și a=(1,2,5,3,9,4,7,8), se obțin k=6, o secvență

de indici satisfăcând condițiile date fiind 1,2,4,6,7,8, căreia îi corespunde subșirul (1,2,3,4,7,8) format din elemente ale vectorului a care sunt în ordine crescătoare (în vectorul luat ca exemplu ele sunt îngroșate).

Soluție. O soluție va fi un vector x ce conține secvența de indici ai

tabloului a cu restricțiile menționate în problemă și care satisfac în plus condiția că el nu mai poate fi suplimentat în plus cu încă o componentă. Astfel, pentru exemplul dat, cazul particular x=(1,2,3,7,8) este considerat soluție (soluția în acest caz fiind subșirul (1,2,5,7,8) corespunzător indicilor dați de x ); în schimb x=(1,2,3) nu este soluție, deoarece poate fi supliment, de exemplu, cu componenta7. Lungimea efectivă va fi memorată în variabila k.

Funcția de cost atașează soluții lungimea sa.

În variabila kf va fi memorată lungimea unei soluții optime, iar

soluția optimă va fi memorată în vectorul xf. Vom pune inițial kf=0, urmând ca de fiecare dată când determinăm o soluție x de lungime k să verificăm dacă k>kf, în caz afirmativ actualizând pe xf și kf (acest lucru realizându-l procedura retsol).

Cerința problemei ca indicii să fie în ordine crescătoare impune ca pentru k>1, inițializarea pentru x[k] să fie:

x[k]:=x[k-1]

Pentru a ușura verificările realizate de funcția continuare vom introduce două componente suplimentare: a[0] care va fi inițializată cu –maxint și respectiv: a[n+1]care va fi inițializată cu maxint; în acest mod putând identifica ușor faptul că o secvență crescătoare de indici x[1]<x[2]<…x[k] nu poate fi suplimentată, verificând condiția x[k]<n+1.

Urmează programul Pascal ce rezolvă problema prin metoda Backtracking în modul prezentat mai sus.

Program Subsiruri_cresc.

uses crt;

var a,x,xf:array[0..100] of integer; n,kf,i:integer;

function continuare (k:integer): boolean; begin

continuare:= a[x[k-1]]< a[x[k]]

end;

procedure retsol (k:integer); begin

if k>kf then begin kf:=k; xf:=x end

end;

procedure backtacking; var k,i:integer; begin

x[0]:=0; k:=1; x[1]:=0;

while k>0 do

if x[k]<n

then

begin

x[k]:=x[k]+1;

if continuare (k)

then

if x[k]=n

then

else

end

begin

retsol (k); k:=k-1

end

begin

k:=k+1;

x[k]:=x[k-1] end

begin

end;

else k:=k-1

writeln (‘n=’); readln (n);

writeln (‘Introduceti elementele vectorului’); for i:=1 to n do read (a[i]);

a[0]:= -maxint; n:=n+1; a[n]:=maxint; kf:=0; backtacking;

writeln (‘O secventa crescatoare de lg. max. este’); for i:=1 to kf-1 do write (a[xf[i]]:4);

writeln; writeln (‘si are lungimea’, kf-1:3); repeat until keypressed

end.

CAPITOLUL IV

METODA PROGRAMARII DINAMICE

Mulți programatori au tendința de a rezolva problemele netriviale de informatică prin metoda Backtracking fără a se gândi la eficiența soluției obținute in acest fel. Datorită timpului de răspuns foarte mare, de cele mai multe ori aceste soluții nu pot fi folosite în practică decât pentru exemplele foarte simple. Soluțiile eficiente pot fi descoperite doar după o analiza minuțioasa a problemei și obținerea unor astfel de soluții cere adesea o inventivitate deosebită din partea utilizatorului. Există însă situații când rezolvarea prin metoda Backtracking nu poate fi înlocuită prin alte metode mai eficiente. Astfel de situații apar pentru problemele în care se cer toate soluțiile acceptabile. În schimb, dacă se cere numai soluția optimă din mulțimea soluțiilor acceptabile, atunci uneori poate fi utilizată metoda Programării dinamice care este una din metodele ce prezintă mari dificultăți în aplicare, ea necesitând multă ingeniozitate și o înțelegere profundă a sa pentru a o putea aplica.

Exemplu prototip

Problema 4.1. (Problema diligenței).Cu mult timp în urmă, un comis voiajor avea de efectuat o călătorie între doua orașe din vestul sălbatic. Să presupunem că în vestul sălbatic erau 10 orașe (numerotate de la 1 la 10 ca in figura IV.1) între care se putea călători numai cu diligența. În fiecare oraș comis voiajorul trebuia să coboare din diligența și să ia o altă diligență spre un alt oraș. Fie 1 orașul din care pleacă comis voiajorul si 10 orașul destinației în care trebuie să sosească el.

Desigur, pentru a realiza această călătorie (din orașul 1 până în orașul 10, fixate) comis- voiajorului putea să aleagă (etapă cu etapă) orașele intermediare prin care să treacă. Traseele (rutele) pe care le putea urma comis-voiajorului sunt indicate în figura IV.1 prin săgeți orientate în sensul deplasării sale.

Figura IV. Traseele comis- voiajorului pentru călătorie

Se observă că această călătorie poate avea loc în patru etape:

în prima etapa el se afla în orașul 1 și poate să călătorească spre orașele 2,3 sau 4;

în a doua etapă el se afla în unul din orașele 2,3 sau 4 și poate să călătorească spre unul din orașele 5,6 sau 7;

în etapa a treia el se afla în unul din orașele 5,6 sau 7 și poate să călătorească spre unul din orașele 8 sau 9;

în etapa a patra el se află în unul din orașele 8 sau 9 și poate să călătorească spre orașul destinație 10.

În acele vremuri și în acele locuri o călătorie era destul de periculoasă existând posibilitatea ca diligența să fie atacată de bandiți. Prin urmarea călătorilor cu diligența li se ofereau polițe de asigurare pe viață. Costul unei polițe de asigurare pentru fiecare etapa era proporțional cu siguranța rutinei respective așa ca traseul cel mai sigur era cel care avea costul poliței de asigurare cel mai mic. Întrucât comis-voiajorul era un om foarte prudent și prin urmare era foarte interesat de securitatea vieții sale, bineînțeles ca el s-a asigurat în fiecare etapă a călătoriei sale.

Să notăm cu c (i,j) costul unei polițe de asigurare pentru a merge cu diligența din orașul i până în orașul j și să presupunem ca aceste costuri sunt cele date de următoarele tabele:

la etapa I:

– la etapa a II-a:

– la etapa a III-a:

– la etapa a IV-a:

Se pune întrebarea : care traseu a fost ales de comis-voiajorul ca fiind cel mai sigur pentru securitatea vieții sale ?

Soluție. Desigur, traseul cel mai sigur este cel care are costul total de asigurare (adică suma costurilor polițelor de asigurare plătite la fiecare etapă) cel mai mic așa că problema este de fapt de a minimiza costul total al polițelor de asigurare.

Se observă că, la alegerea traseului optim pentru călătoria sa. comis-voiajorul trebuie să adopte o strategie de luare a deciziilor la fiecare etapă a călătoriei (constând în alegerea orașului următor spre care să se îndrepte dintre cele care îi sunt permise la acea etapă) astfel încât costul total al polițelor de asigurare plătit pe acel traseu să fie minim.

O strategie evidentă la prima vedere ar fi de a alege la fiecare etapă orașul spre care polița asigurare este cea mai ieftină. Urmând aceasta strategie, la prima etapa comis-voiajorul ar alege orașul 2 întrucât dintre orașele spre care poate să meargă la acea etapă (orașele 2,3 sau 4) ruta spre 2 are polița de asigurare cea mai ieftină. În cea de-a doua etapă, aflându-se în orașul 2 va alege orașul 6 (dintre orașele 5,6 sau 7) ca fiind cel spre care polița de asigurare e cea mai ieftină. Continuând tot așa, va rezulta traseul 1-2-6-9-10 cu costul total al polițelor de asigurare 2+4+3+4=13.

Totuși, această strategie nu conduce la o soluție optimă (traseul găsit nefiind cel mai ieftin). De exemplu, traseul 1-4-6-9-10 are costul total 3+1+3+4=11fiind mai ieftin decât traseul găsit cu strategia de mai sus (care este de fapt o strategie Greedy și am văzut ca strategia Greedy nu conduce totdeauna la o soluție optimă).

Negăsirea celui mai ieftin traseu cu această strategie se datorează faptului ca o decizie pe care o luăm la o anumită etapa afectează nu numai valoarea costului total ci determină și orașul în care va ajunge și din care va pleca în etapa următoare comis-voiajorului, afectând în acest fel deciziile de la etapele viitoare. De exemplu, dacă în prima etapă am decis ca orașul destinație să fie 2,am restrâns posibilitățile de alegere de la etapa a doua, nemaiputând alege la acea etapa decât trasee care pleacă din 2.

Dacă prima etapă am fi făcut o alegere aparent mai proastă și anume orașul 4, în continuare, din orașul 4 am fi putut să alegem orașul 6,obținând traseul 1-4-6 cu costul 3+1=4 mai bun decât traseul 1-2-6 cu costul 2+4=6.

Din cele prezentate s-ar părea ca, pentru rezolvarea problemei, este necesar să se găsească toate traseele posibile dintre orașul 1 și orașul 10 (ceea ce ne duce cu gândul la metoda Backtracking), să li se calculeze costul și să se aleagă traseul sau costul cel mai mic. Pentru exemplul ales sunt 18 trasee posibile, dar într-un caz real (când numărul de trasee este foarte mare) găsirea tuturor posibilităților ar duce la un număr de calcule foarte mare.

Există, din fericire, și un alt mod de abordare al problemei care reduce enorm numărul de calcule. Acest mod de a găsi soluția optimă printr-un număr redus de calcule este oferit de Programare dinamică.

În esența, Programarea dinamică pornește de la o parte mai mică din problema inițială (o subproblemă) și se gasește soluția optimă pentru aceasta problema mai mică. Apoi, aceasta subproblemă este largită gradat (dinamic) rezultând o noua problema (care este tot o subproblemă a problemei inițiale) găsind și pentru aceasta soluția optimă bazându-se pe soluția optimă de la subproblema precedentă și tot așa până când este rezolvată problema inițială în întregul ei.

Pentru problema noastră, vom porni cu problema mai mică data de situația când comis- voiajorul aproape și-a încheiat călătoria și mai are de parcurs o singura etapă. Soluția optimă pentru aceasta problema mai mică este evident de a merge din orașul curent (oricare ar fi acesta) în orașul destinației 10. La fiecare din interațiile următoare problema este lărgită crescând cu unu numărul de etape pe care il mai are de parcurs comis-voiajorul până să-și încheie călătoria. Problema curentă, la fiecare interație, este de a găsi la acea etapă, astfel încât costul traseului pe care îl găsește să fie cel mai mic (optim).Se observă că soluția optimă pentru o anumită subproblema curentă poate fi găsită relativ ușor dacă ne folosim de rezultatul obținut la iterația precedentă. Să încercăm în continuare să vedem care sunt detaliile implicate de o astfel de abordare a problemei.

Vom nota cu dk decizia pe care trebuie să o luăm la fiecare etapa k (k=1,2,3,4). Variabila dk va avea ca valori numărul orașului pe care putem să-l alegem ca destinație la etapa k (de exemplu, pentru etapa 2, variabila d2 poate lua ca valori pe 5,6 sau7). Astfel, traseul ales va fi 1 d1 d2

d3 d4, unde d4=10. Să notăm cu fk (s,dk) costul total al traseului optim care poate fi găsit pentru etapele care au mai rămas, dacă comis-voiajorul se află în orașul s, gata să parcurgă etapa k și a ales ca oraș destinație pentru această etapă (a k-a) orașul dk.

Dându-se k (etapa pe care tocmai trebuie să o înceapă comis-voiajorul ) și s (orașul în care se află înainte de a începe această etapă) există, în general, mai multe orașe dk, pe care le poate alege

ca destinație la acea etapă (deci dk poate să ia mai multe valori).Prin urmare, dacă k și s sunt fixați, atunci fk (s,dk) reprezintă o funcție de o variabilă dk.

Pentru fiecare dk,fk (s,dk) va reprezenta costul total al traseului optim, care poate fi găsit pentru etapele care au mai rămas, dacă comis – voiajorul se află în orașul s, gata să parcurgă etapă k

și a ales ca oraș destinația pentru aceasta etapă orașul dk. Vom nota cu d*

valoarea lui dk

care

minimizează funcția fk (s,dk), iar cu f * (s) valoarea minimă corespunzătoare a lui fk

(s,dk) când

dk=d* Deci f* (s) va fi costul celui mai bun (ieftin) traseu (până la orașul 10) care poate fi găsit

dacă comis- voiajorul este gata să înceapă etapa k și se află în orașul s înainte de a începe etapa k, căci dintre toate valorile fk (s,dk) care reprezintă costul optim pe care îl putem obține dacă alegem ca

destinația intermediară dk, cel obținut pentru alegerea lui d* ,este cel mai mic, valoarea lui fiind f*

k k

(s). Din punct de vedere matematic, cele menționate mai sus se exprimă astfel:

f* *

k (s)= min fk(s,dk)=fk(s,d k) (1)

dk

Evident, costul total al traseului optim care poate fi găsit pentru etapele care au mai rămas, dacă comis-voiajorul se află în orașul s, gata să parcurgă etapa k, și a ales ca oraș destinația pentru aceasta etapa orașul dk,fk (s,dk), este costul poliței de asigurare pentru o călătorie între orașele s și dk (adică c[s,dk]) care se adaugă la costul celui mai bun traseu până în orașul 10, care poate fi găsit dacă comis –voiajorul este gata să înceapă etapa k+1 și se află în orașul dk,fk+1 (dk)+c[s,dk]

Unde valoarea c[s,dk] este data de tabelele precedente pentru c[i,j] putând i=s și j=dk.

Înlocuind fk(s,dk) din (2) în (1), obținem următoarea relație de recurență:

f* *

k(s)=min (f k+1 (dk) + c [s,dk])

dk

Observăm că formula de recurență (3) pentru k=4 are nevoie de valoarea f*

(d ) adică f* (d ). Dar

k*1 k 5 4

cum orașul destinație este 10, putem considera că în situația în care comis-voiajorul se află în acest oraș el este gata să înceapă etapă a cincea și că costul acestei etape este 0 pentru ca el nu mai are de străbătut nimic în această etapă.

5(10)=0

Obiectivul nostru este să găsim pe f * (1) și traseul corespunzător.

Într-adevăr, f1(1) reprezintă costul celui mai bun traseu (până la orașul 10) care poate fi găsit dacă

comis – voiajorul se afla în orașul 1 și este gata să înceapă prima etapă. Programarea dinamică se va găsi această valoare, calculând succesiv valorile f* (s),f* (s),f* (s),f* (s) pentru fiecare oraș s

4 3 2 1

posibil la etapa respectivă, folosind formula de recurență (3).

Când comis-voiajorul mai are o singură etapă de parcurs (k=4), traseul său este complet determinat de orașul curent s în care se află (8 sau 9) și de destinația sa finală dk=10. La această etapă el nu poate să facă nici o alegere, fiind un singur oraș destinație (dk=10).Traseul său va fi s

10, iar f* (s)=f (s,10)=f* (10)+c[s,10]=0+c[s,10]. Tabelul următor sintetizează soluția pentru k=4:

4 4 5

k=4

Când comis- voiajorul mai are încă două etape de parcurs (k=3), soluția necesită ceva mai

multe calcule. Înainte de a începe etapa a treia, comis voiajorul se poate afla în orașele 5,6 sau 7 și va trebui să calculăm f* (5), f* (6), f* (7). De exemplu, conform formulei (3), avem:

3 3 3

f* *

3(5)=min (f 4(d3) +c[5,d3])

d3{8,9}

deoarece în această etapă poate fi ales ca oraș intermediar 8 sau 9 (d3 poate fi 8 sau 9 )-Ținând cont de valoarea lui f* (s) calculată mai înainte, obținem

3(5)=min (1+3, 4+4)=4

această valoare realizându- se pentru d3=8. Pentru s=6 și s = 7 se procedează similar obținând astfel soluția problemei pentru k = 3 dată de tabelul următor:

k=3

Pentru etapa următoare (k = 2) formula de recurență (3) este :

f* *

2(s)=min (f 3(d2)+c[s,d2])

d2{5,6,7}

unde s poate fi 2,3 sau 4. Obțineți:

k=2

În sfârșit, pentru etapa k=1 avem de calculat:

f* *

și se obține:

1(s)=min (f 2(d1)+c[1,d1])

d1{2,3,4}

k=1

Întrucât f* (1)=11, rezultă ca cel mai ieftin traseu are valoarea 11. Acum putem să indentificăm și

traseele optime. Cum d*

este 3 sau 4, rezultă că la prima etapă (k=1) trebuie ales ca oraș

intermediar 3 sau 4. Să presupunem că am ales a doua etapă avem , deci trebuie să alegem orașul 5 ca oraș intermediar. La etapa a treia pentru avem și deci vom alege pe 8 ca oraș intermediar. În ultima etapă pentru avem . Prin urmare, traseul va fi 1-3-5-8-10.

Alegând la prima etapă d* =4, se vor mai găsi alte două trasee optime (1-4-5-8-10 și 1-4-6-9-10).

Toate aceste trasee au costul total 11.

Tipul de probleme la care se aplică metoda. Programării dinamice

În cele ce urmează, vom trece de la particular la general, definind caracteristicile generale ale unei probleme ce se poate rezolva cu metoda Programării dinamice și vom defini în ce constă metoda în sine.

Medota Progrămării dinamice se aplică problemelor în care este necesara parcurgerea unui număr bine determinat de etape pentru a găsi soluția optimă iar la fiecare etapă este necesară luarea unei decizii. Așadar, se cere găsirea acelui șir de decizii (deciziile sunt interdependențe) care

conduce la soluția optimă. Prin urmare, o problemă poate fi încadrată în clasa problemelor rezolvabile cu metoda Programării dinamice, dacă la ea se pot indentifica următoarele caracteristici: 1.Problema se poate împărți în etape iar la fiecare etapă e necesară luarea unei decizii.

De exemplu, și problema diligenției a fost imparțită în cele patru etape (necesare comis- voiajorului pentru a face călătoria), iar la fiecare etapa era necesară luarea unei decizii cu privire la alegerea următorului oraș destinație.

În mod similar, orice problema de Programare dinamică cere luarea unei secvențe de decizii interdependențe, fiecare decizie fiind corespunzatoare unei etape a problemei.

Fiecărei etape îi este asociat un număr de stări.

Pentru problema diligenției stările asociate fiecărei etape erau orașele s în care se putea afla comis-voiajorul înainte de a începe o anumită etapă a calatoriei. În prima etapă singura stare asociată era orașul 1, în cea de-a doua etapă stările asociate erau orașele 2,3 și 4 s.a.m.d.

Definirea stărilor unei probleme oarecare depinde, în general, de problema respectiva. Totuși, putem defini starea unei probleme ca fiind o mulțime de parametri ce descriu complet situația problemei la un moment dat. În cazul problemelor de programare dinamică, stările asociate unei etape vor fi o descriere a situațiilor în care se poate afla sistemul descris de problema la acea etapă. Numărul de stări nu este neaparat același pentru toate etapele, el putând să difere de la o etapa la alta. Din punct de vedere al programarii, o stare este o structură de date. Ea va descrie situația problemei la un moment dat.

Luarea unei decizii la fiecare etapa are ca efect transformarea stării în care se află problema la acea etapa într-o stare corespunzătoare etapei următoare. Orice trecere de la o stare asociată unei etape la o stare asociată etapei următoare are un cost. Luând un șir de decizii (câte una la fiecare etapă), se realizează un șir de transformări care asigura trecerea problemei din starea inițiala în starea finală.

Prin combinarea într-un mod specific problemei a costurilor fiecarei transformări de șir, unui astfel de șir de transformări, care face trecerea dintr-o stare inițială într-o stare finală, i se asociază un cost total. Dar acum oricărui șir de decizii îi corespunde un șir de transformări, rezultă ca unui șir de decizii i se poate asocia un cost, și anume costul total al șirului de transformări determinat de șirul de decizii.

De exemplu, pentru problema diligenței, trecerea de la starea curentă (orașul în care se află comis-voiajorul la un moment dat ) într- o stare corespunzătoare etapei următoare (orașul în care se va afla comis-voiajorul la etapa următoare) se face prin luarea unei decizii. Aceasta trecere dintr-o

stare asociată unei etape într-o stare asociată etapei următoare, adică trecerea de la un oraș la altul are un cost, și anume costul poliței de asigurare pentru a cea călătorie.

Pentru problema diligenței, starea inițială este orașul din care pleacă comis-voiajorul (la prima etapă) adică orașul 1, iar stare finală este orașul în care trebuie să ajungă ( la ultima etapă) adică 10. Prin luare unui șir de decizii, adică alegerea orașelor intermediere de la fiecare etapă, se realizează trecerea de la starea inițială (orașul 1) la starea finală (orașul 10).Costul total al unui astfel de șir de decizii este costul total al asigurării și el se obține prin adunarea costului poliței de asigurare plătite la fiecare etapa. În cazul acestei probleme modul specific de combinare a costurilor fiecarei transformări dintr-un șir pentru a obține costul întregului șir de transformări este însumarea. 4.Problema cere găsirea unui șir de decizii, astfel încât ele să determine un șir de transformări de la starea inițială la starea finală al cărui cost total să fie optim (maxim sau minim).

Astfel, problema diligenței cere găsirea unui șir de decizii (șirul de orase intermediare, cate unul la fiecare etapa) astfel încât călătoria de la orașul 1 (starea inițială) la orașul 10 (starea finală), să aibe costul total al asigurării minim.

5.Pe lângă caracteristicile de mai sus, pentru a putea aplica metoda Programării dinamice unei probleme trebuie să fie satisfăcut și principiul optimalității.

El constă în faptul că, fiind dată starea curentă la o anumită etapă, în șir de decizii optim pentru etapele care au mai ramas este independent de șirul de decizii care au fost luate la etapele

anterioare. Mai precis, pentru o problema având n etape, daca

d1 , d2 ,…., dn

este un șir optim de

decizii care transformă starea inițială s0 în stare finală sn, atunci fie șirul de decizii d2,…,dn este optim pentru problema cu n-1 etape cu s1 ca stare inițială și sn ca stare finală, fie șirul de decizii d1,…dn-1 este optim pentru problema cu n-1 etape cu s0 ca stare inițială și sn-1 ca stare finală, sau,mai general, oricare ar fi i aparținând mulțimii{1,2…,n-1}, șirul de decizii d1,…,di este ete optim pentru problema cu i etape, cu s0 ca stare inițială și s1 ca stare finală, iar șirul de decizii di,….,dn este optim pentru problema ci n-1 etape,cu si ca stare inițială și sn ca stare finală.

În cazul problemei diligienței este evident că este satisfacut principiul optimalității.

În concluzie, metoda Programării dinamice se aplică problemelor de optim în care soluția poate fi privită ca rezultatul unui șir de decizii d1,d2,…,dn. În general fiecare decizie depinde de deciziile deja luate și nu ete unic determinată. Să observăm ca în cazul metodei Greedy fiecare

decizie care se ia ete unică. Un șir de n decizii d1,d2,…,dn luate deja în cele n etape ale procesului poartă numele de politică. Când o politică trece sistemul din starea initiala s0, se face o analiză retrospectivă.

În afara de aspectul descris de mai sus, pentru aplicarea metodei mai este necesar să fie satisfăcut principiul optimalității (formulat R.E Bellman) al carui enunț este următorul : daca d1, d2,…,dn este un șir optim de decizii care transformă starea inițială s0 în starea finală sn, trecând prin stările intermediare s1,s2,….,sn-1, atunci șirul de decizii d2,…dn este optim pentru s1 ca stare inițială si sn ca stare finală.

Mai general, principiul optimalității cere ca pentru orice șir optim de decizii d1,d2,…,dn pentru perechea de stari (s0,sn) si pentru orice i {1,…,n-1}, să rezulte ca (d1,….,di ) este șir optim de decizii pentru perechea de stări (s0,si ) sau (d I+1,…..,dn ) este șir optim de decizii pentru perechea de stări (si,sn ).Și mai general, principiul optimalității cere ca ambele șiruri să fie optimale.

Odată verificată o forma a principiului optimalității, metoda Programării dinamice constă în a scrie relațiile de recurență corespunzătoare și apoi a le rezolva.

În general, relațiile de recurență sunt următoarele două tipuri:

Fiecare decizie di depinde de deciziile di-1.Spunem că în acest caz ca se aplică metoda înainte.Deciziile vor fi luate în ordinea dn,dn-1,……d1.

Fiecare decizie di depinde de deciziile d1,….,di-1.În acest caz spunem că va aplica metoda înapoi. Deciziile vor fi luate în ordinea d1,d2,…,dn.

Sunt mai rare situațiile în care fiecare decizie di depinde atât de deciziile

d1,…,di-1 cât și deciziile di+1,….,dn. Spunem în acest caz ca se aplică metoda mixtă.

Mecanism general

Am văzut până acum care sunt caracteristicile esențiale pe care trebuie să le aibă o problema și care sunt condițiile pe care trebuie să le îndeplinească pentru a se încadra în clasa problemelor de programare dinamică. Să vedem acum ca trebuie făcut pentru a rezolva o astfel de problemă.

1.Conceperea procedurii care să rezolve o problema de programare dinamica trebuie facută în așa fel înacât să găsească o strategie optimă de luare a deciziilor pentru întreaga problema, adică trebuie să gasească decizia optimă ce trebuie luată la fiecare etapa și pentru fiecare stare posibilă în care se poate afla problema la acea etapa.

La problema diligenței pentru fiecare etapă i am construit câte un tabel în care pentru fiecare stare s posibilă la acea etapă, este înscrisă decizia optima d.i.

Se va proceda în mod analog pentru orice problemă de programare dinamică, adică, se va construi câte un tabel pentru fiecare etapă i, în care pentru fiecare s posibilă la acea etapă, se va memora decizia optimă d*I și costul fi (s) care se obține luând această decizie.

În vederea construirii acestor tabele se vor folosi o relație recursivă, care să permită ca, la o anumită etapă, construirea tabelului să se facă pe baza tabelelor de la alte etape, calculate anterior.

Pentru problema diligenției relatia de recursivă este relația (3) ce permite calculul tabelului de la etapa k pe baza celui de la etapa k+1.

În general, pentru orice problemă de programare dinamică se poate găsi o relație recursivă, a carei formă depinde de la problema la problema.

Cu toate că relațiile recursive depind foarte mult de condițiile concrete ale problemei, și în consecință diferă foarte mult de la o problemă la alta, încercăm totuși să dăm căteva linii directoare care să vă ghideze atuci când ajungeți la acest pas al unei probleme de programare dinamică.

Mai întâi, să vedem care sunt elementele între care va trebui să găsim o relație recursivă. La fiecare etapă, indiferent în ce stare ne-am afla la acea etapă, trebuie să alegem între mai multe alternative, deci să luăm o decizie. Să presupunem că suntem la etapa k și că ne aflăm în starea s. Să notam cu d o variabilă care ia valori în mulțimea alternativelor din care avem de ales în situația aceasta.Dacă pentru d precizăm o valoare, înseamnă că am luat o decizie, deci am facut o alegere. De aceea d se va numi variabilă de decizie. Dacă plecăm din starea s la etapa k și facem alegerea d, am vrea să știm care este costul care se obține. Mai întâi facem observația ca acest cost nu este o singură valoare, pentru ca această valoare depinde de deciziile pe care le vom lua la etapele viitoare. Dacă am calculat toate valorile ce se pot obține pentru toate deciziile posibile ulterioare și facem acest lucru pentru orice stare s de la orice etapă k, am face ceea ce se cheamă o cautare exhaustivă, adică a explora toate alternativele de a trece din starea inițială în starea finală și am alege alternativă cu costul optim. Cum, de obicei, sunt foarte multe alternative, complexitatea acestui mod de abordare este foarte mare și deci ineficiență (un astfel de program de tip backetracking ar trebui să ruleze foarte mult pentru a găsi o soluție).În schimb, putem să considerăm ca etapele viitoare se vor lua deciziile cele mai bune si atunci ne intereseaza costul optim care se poate obtine plecand din starea s la etapa k și făcând alegerea d. Să notăm această valoare cu fk(s,d). Dintre toate acele decizii ce le putem lua în starea s de la etapa k, ne interesează acea decizie d care obține costul optim, adică

acea valoare a lui d care minimizează sau maximizează funcția fk(s,d) privită ca funcție în d. Să notam această cea mai buna decizie cu d*.Vom nota cu fk(s) costul cel mai bun care se poate obține pornind din starea s de la etapa k, luând cea mai buna decizie d*.Deci, vom avea:

sau

fk*(s) =min {fk(s,d)}

d

f*k(s)= max {fk(s,d)} d

iar d* este acel d care realizează minimul sau maximul.

Acestea sunt elemente (adică fk*(s)) între care va trebui să scriem relația recursivă.

Va trebui să găsim niște elemente k și s pentru care să putem calcula direct valoarea f*k(s), iar pentru celelalte să putem defini această valoare în funcție de alte valori f*i(su).

Relațiile recursive obținute pot fi oricât de complexe.

Pentru problema diligenței, relația recursivă e destul de simplă, valoarea lui f* de la o etapa k și o stare s deprinzând doar de valorile f de la etapa k+1 pentru stările posibile la acea etapă. În alte probleme valorile de la o etapă pot să deprindă de valorile lui f de la mai multe etape și pentru diverse stări.

Ordinea de considerare a etapelor în cadrul procedurii de programare dinamica care va rezolva problema este determinata de forma relației recursive găsite.

Astfel, dacă valorile lui f de la o anumită etapă k depind doar de valorile lui f de la etapele viitoare (k+1,k+2 s.a.m.d ), atunci procedura va porni de la etapa n (ultima), valorile de la această etapă nedeprinzând de nimeni, apoi se vor calcula valorile f de la etapa n-1, apoi de la etapa n-2 și așa mai departe până se va ajunge la etapa 1(printre stările căreia se va afla si starea inițială,ceea care ne interesează).În literatura de specialitate acest mod de parcurgere al stărilor se numește backword.

În schimb, dacă valorile lui f de la etapa k depind doar de valorile lui f de la etapele anterioare (k-1,k-2 s.a.m.d ) atunci procedura va porni de la prima etapa, valorile de la această etapă nedepinzând de nimeni, apoi se vor calcula valorile f de la etapa 2, apoi la etapa3 și așa mai departe până se va ajunge la etapa n (printre stările căreia se va afla și starea finală, cea care ne interesează).În literatura de specialitate acest mod de parcurgere al stărilor se numește forword.

Există și situația mai complexă când valorile lui f depind de valori ale lui f atat de la etape anterioare cât și de la etape viitoare (în acest caz ordinea de considerare a etapelor deprinzând strict de relația recursivă).

Mai mult, se poate intâmpla să fie considerată o etapă pentru a se calcula valorile lui f numai pentru anumite stări s, iar apoi după trecerea prin alte etape să se revină la etapa respectivă pentru a se calcula valorile lui f pentru alte stări etc.

Acum, după ce relațiile au fost scrise, se poate trece la scrierea programului care rezolva problema.

Se vor concepe structuri de date adecvate care să poată să reprezinte o stare a problemei de la o etapă oarecare.

Este necesară construirea a doua tablouri F[k,s] va reprezenta pe fk (s), deci va fi un numar care va reprezenta costul cel mai bun care se poate obține plecând din starea s la etapa k și luând cea mai buna decizie posibilă, adică F [k,s].D[k,s] va reprezenta pe d*, deci va memora cea mai bună decizie care se poate lua la etapa k daca ne aflam in starea s,adica D[k,s].Elementele lui D[k,s] vor fi structuri de date care să poată reprezenta o decizie.

Ceea ce ne interesează pe noi este să găsim cel mai bun cost care se poate obține plecând din starea ințială care se află la o etapă a problemei (de obicei 1 sau n ).

De asemenea, ne interesează și șirul de decizii care trebuie urmat pentru a obține acest cost.Costul cautat va fi F[ei, sare_inițială] iar șirul de decizii va putea fi refăcut cu ajutorul tabloului D*.Cu ei am notat etapa inițială.

În vederea găsirii valorii lui F* [ei,starea_inițială] și a valori lui D* ne vom folosi de relațiile

recursive găsite. Programul nu trebuie decât să parcurgă tabloul F* și în timp ce îl parcurge, să-l completeze (și pe el și pe D*), până când ajunge să completeze poziția (ei, starea_inițială).Modul de parcurgere este dictat de relațiile recursive existente.

Mai precis, se vor completa mai întâi acele propoziții (k,s) pentru care valoarea F*[k,s] se poate calcula direct, adică nu depinde de nimeni. Apoi se va parcurge tabloul în așa fel încât când se ajunge să se completeze orice poziție (k,s) pe baza tuturor pozițiilor (i,su) deja completate și de care depinde (recursiv) calculul lui F*[k,s].

Observații :1) Odată ce aveți relațiile recursive, s-ar putea să fiți tentați să scrieți o procedura recursivă cu care să calculați valoarea F* [ei, satrea_inițială. Acest lucru nu este eficient, deoarece s-a repetat inutil multe calcule. În schimb, prin completarea unui tabel, o valoare de care este nevoie se va calcula o singură dată. Mai precis, motivul ineficienței este același ca cel pentru care o procedură recursivă pentru calculul șirului lui Fibonacci este ineficientă (și acolo eficiența se obține tot completând un tablou, adică un vector de la stanga la dreapta ).

2) La un moment dat s-ar putea să nu fie nevoie de întreg tabloul F*, deoarece ne interesează doar valoarea lui F*[ei,starea_inițială].Într-adevăr, la un moment dat nouă ne trebuie doar

valorile de care depinde F*[k,s] iar dacă aceste valori nu sunt multe, le putem reține și în alte structuri de date decât în tablou.

Compararea metodei Programării dinamice cu metoda Greedy. Complexitatea metodei Programării dinamice.

Atunci când soluția unei probleme este privită ca rezultatul unei secvențe de decizii poate fi folosită atât metoda Programării dinamice cât și metoda Greedy dar trebuie să fim foarte atenți când este bine să folosim una dintre ele și când pe cealaltă. Deoarece ambele metode pot exploata principiul optimalității este posibil să aplicăm în mod eronat metoda Greedy atunci când este necesar de fapt aplicarea Programării dinamice (metoda Greedy exploatând insuficient principiul optimalității) sau s-ar putea să fim tentați să elaborăm o soluție prin metoda Programării dinamice acolo unde este suficientă o soluție prin metoda Greedy.

De exemplu, în cazul problemei rucsacului (problema 2.6) avem două situații. În prima situație, pentru orice obiect i, se poate lua orice fracțiune 0xi1 din el,iar a doua situație, xi{0,1}, adică orice obiect poate fi incărcat numai în întregime în rucsac. Corespunzător acestor două situații, obținem problema continuă a rucsacului,respectiv,problema discretă a rucsacului(numită și problema 0/1 a rucsacului).Să notăm cu vi valoarea și cu mi greutatea fiecărui obiect i(oricare ar fi i). Este evident ca persoana cu rucsacul va selecta obiectele astfel încât să maximizeze funcția obiectiv.

n

f(x)= 

i 1

vixi

unde x=(x1,x2,…….,xn), verifică condiția

n



i 1

mixi M

Desigur, soluția acestei probleme poate fi privită ca rezultatul unei secvențe de decizii (persoana decide pentru început asupra valorii xi, apoi asupra valorii x2 și așa mai departe astfel încât, printr-o secvență optimă de decizii, să maximizeze funcția obiectiv).

În cazul problemei continue a rucsacului se poate aplica cu succes metoda Greedy selectând la fiecare pas,cât timp este posibil în întregime,obiectul pentru care raportul vi/mi este maxim. Putem să presupunem (fară a restrânge generalitatea) că:

vi/g1v2/g2……..vn/gn

Se poate demonstra că prin utilizarea acestui algoritm Greedy obținem soluția optimă și că aceasta este de forma x*=(1,1,……,x* ,0,0…..,0), k fiind un indice, 1kn, astfel încât 0xk1.

Deci în situația problemei continuie a rucsacului, algoritmul Greedy găsește secvența optimă de decizii luând la fiecare pas câte o decizie care este optimă locală. Dacă nu considerăm timpul necesar sortării inițiale a obiectelor, timpul este de ordinul n.

În schimb, în cazul problemei continue a rucsacului, algoritmul Greedy nu conduce totdeauna la rezultatul dorit. Un contrexemplu în această situație ar fi cel pentru m=(1,2,3), v=(6,10,12) si M=5, când algoritmul Greedy furnizează soluția (1,1,0), în timp ce soluția optimă este (0,1,1).

În această situație metoda Greedy nu poate fi aplicată deoarece este generată o decizie (x1=1) optimă local dar care nu este însă optimă și global.Cu alte cuvinte, la primul pas, nu avem suficientă informație pentru a decide asupra valorii lui x1. Strategia Greedy exploatează insuficient principiul optimalității, considerând ca într-o secvență optimă de decizii, fiecare decizie (și nu fiecare secvență de decizii, cum procedează programarea dinamică) trebuie să fie optimă. Problema discretă a rucsacului se poate rezolva prin metoda Programării dinamice în această situație exploatându-se complet principiul optimalității. Spre deosebire de problema continuă a rucsacului, pentru problema discretă a rucsacului nu se cunoaște nici un algoritm polinominal de rezolvare a sa.

În concluzie, metoda Greedy generează o singură secvență de decizii, exploatând incomplet principiul optimalității pe când metoda Programării dinamice generează mai multe secvențe de decizii (ținând cont de principiul optimalității, se consideră însă doar subsecvențele optime,acestea combinându-se în soluția optimă finali).Cu toate că numărul total de secvențe de decizii sunt d posibilitați, atunci sunt posibile dn secvențe de decizii) algoritmi de programare dinamică sunt de cele mai multe ori polinominali,această reducere a complexității datorându-se utilizării principiului optimalității.Aceasta este diferența esențială între metoda Greedy și metoda Programarii dinamice.

O altă caracteristică importantă a Programării dinamice este că subsecvențele optime se memorează, evitându-se astfel recalcularea lor.

CAPITOLUL V

METODA DIVIDE ET IMPERA

Metoda Divide et impera (împarte și stăpânește) este o tehnică specială prin care se pot rezolva anumite probleme bazându-se pe un principiu extrem de simplu: descompune ( divide) problema inițială în două sau mai multe subprobleme mult mai ușor de rezolvat (de stăpânit), care se rezolva iar soluția pentru problema inițială se obține combinând soluțiile subproblemelor în care au fost descompuse și ele, la rândul lor, în alte subprobleme la fel cum a fost descompusă problema inițială. Procedeul de descompunere poate continua până când se ajunge la subprobleme care admit o rezolvare imediată.

Dorința cerinței ca problema inițială să se poată descompune în subprobleme în mod repetat, numărul de probleme carora li se aplică această metodă este relativ mic.

Exemplu prototip

Problema 5.1.(Mergesort-sortarea prin interclasare). Fie a un vector cu n componente întregi. Să se asorteze crescător vectorul a utilizând sortarea prin interclasare.

Soluție Să studiem mai întâi problema interclasării care are enunțul ce urmează.

Se dau doi vectori a și b cu m și n componente numere reale, sortați crescător(descrescător).Să se formeze din aceștia un al treilea vector c,cu m+n componente, sortate crescător(descrescător).

Pentru rezolvare, simbolizăm cu i indicele elementului la care s-a ajuns în primul vector, cu j indicele la care s-a ajuns în al doilea vector și cu k indicele elementului care urmează a fi scris în cel de-al treilea vector.

Atata timp cât i este mai mic sau egal cu m și j ete mai mic sau egal cu n, comparăm a[i] cu b[j] și în funcție de rezultat procedăm astfel:

dacă a[i] < b[j] atunci c[k] va lua valoarea lui a [i], iar valorile variabilelor i și k

vor crește cu 1;

astfel,c[k] va lua valoarea lui b[j], în timp ce valorile variabilelor j și k vor crește cu 1.

După ce unul din cei doi vectori a fost parcurs în totalitate și scris în c, vectorul rămas se va copia în c.

Exemplu Fie a= {1,3,5,9} și b ={2,4}

– i=1, j=1, k=1

– a=[1]<b[1], deci c[1]=1, i=2, k=2;

– a=[2]>b[1], deci c[2]=1, j=2, k=3;

– a=[2]<b[2], deci c[3]=3, i=3, k=4;

– a=[3]>b[2], deci c[4]=4, j=3, k=5;

vectorul b a fost trecut in c în întregime, în continuare urmând a se copia ceea ce a rămas neparcurs din vectorul a în vectorul c(c[5]=5).

Vom utiliza acest altgoritm de interclasare în vederea sortării unui vector.

Observații: 1)Un vector cu o singură componentă este un vector sortat.

2)Pentru a sorta (crescător) un vector cu două componente, acestea se compară între ele și, dacă prima este mai mare decât cea de a doua, locurile lor se inversează.

Altgoritmul de sortare prin interclasare se bazează pe următoarea idee: pentru a sorta un vector n componente îl împărțim în doi vectori care, odată sortați, se interclasează. Conform strategiei generale Divide et impera, problema este descompusă în alte două subprobleme de același tip și, după rezolvarea lor, rezultatele se combină (în particular se interclasează).Descompunerea unui vector în alți doi vectori de una sau două componente.

În programul ce urmează, procedura prel sortează un vector de maxim două componente;

comb interclasează rezultatele; divimp implementează strategia generală a medodei studiate.

Program Sortint ;

type vector =array[1…10] of integer; var a:vector;

n,i:integer;

procedure prel(p,q:integer; var a:vector);

{Sorteaza vectorul a[p],….,a[q], furnizand rezultatul in a} var t:integer;

begin

end;

if a[p]>a[q]

then

begin

end

t:=a[p] ; a[p] :=a[q]; a[q]:=t

procedure combina (p,q,m:integer; var a:vector);

{Interclaseaza subsirurile deja sortate a[p],…,a[m] și a[m+1],….,a[q],}

{furnizand rezultatul sortarii in subsirul a[p],….,a[q]} var b:vector;

begin i:=p;

i,j,k:integer;

j:=m+1; k:=1;

while (i<=m) and (j<=q) do if a[i]<=a[j]

then

if i<=m

then

else

begin

end begin

end;

b[k]:=a[i]; i:=i+1;

k:=k+1

b[k]:=a[j]; j:=j+1;

k:=k+1

for j:=i to m do

begin

k:=1;

else

end

for i:=j to q do

begin

end;

b[k]:=a[j]; k:=k+1

b[k]:=a[i]; k:=k+1

for i:=p to q do begin

end;

end

a[i]:=b[k]; k:=k+1

procedure diviz (var p,q,m:integer);

{Furnizeaza valoarea „m” ca partea intreaga inferioara a lui (p+q)/2} begin

m:=(p+g) div 2

end

procedure divimp (p,q:integer; var a:vector);

{Procedura divide et impera} var m :=integer ; begin

if (q-p)<=1

begin

then else

prel (p,q,m) ; begin

diviz (p,q,m) ;

divimp (p,m,a);

divimp (m+1,q,a);

combina (p,q,m,a)

end end;

write (‘Dati lungimea vectorului n=’); readln (n);

{Citirea vectorului} for i:=1 to n do

begin

write (‘a[‘,i,’]=’); readln (a[i])

end;

{Afisarea vectorului sortat} for i:=1 to n do writeln (a[i]) end.

Tipul de probleme la care se aplică metoda Divide et impera.

În cele ce urmează, vom trece de la particular la general, definind caracteristicile generale ale unei probleme ce se poate rezolva cu metoda divide et impera și vom defini în ce constă metoda în sine.

Metoda Divide et impera se aplică problemelor care pot fi descompuse în subprobleme în mod repetat până se ajunge la subprobleme a caror rezolvare este imediată și permit ca prin combinarea soluțiilor acestor subprobleme să se obțină soluția problemei inițiale.

Metoda Divide et impera (”desparte și stăpânește”) constă în împărțirea repetată a unei probleme de dimensiune mai mare în două sau mai multe subprobleme de același tip urmată de combinarea soluțiilor subproblemelor rezolvate pentru a obține soluția problemei inițiale.

Mecanism general

Am văzut până acum care sunt caracteristicile esențiale pe care trebuie să le aibă o problemă și care sunt condițiile pe care trebuie să le îndeplinească pentru a se încadra în clasa problemelor ce pot fi rezolvate cu metoda Divide et impera.Să vedem acum ce trebuie făcut pentru a rezolva o astfel de problemă.

Procedure Divimp (p,q,a) if q-p<=eps

then call prel (p,q,a) else

begin

call diviz (p,q,m) call Divimp (p,m,b)

call Divimp (m+1,q,c) call comb (b,c,a)

end end; Procedura trebuie apelată prin:

Call Divimp (1,n,a)

în a obținându-se rezulatatul final.

În acest algoritm, eps este lungimea maxima a unei secvențe {ap,…aq} notată prescurtată (p,q), pentru care prelucrarea se poate face direct, fără a mai fi necesara împărțirea în subprobleme.

Procedura prel realizează prelucrarea secvențelor de acest tip, furnizând rezultatul în a.

Procedura comb realizează combinarea rezultatelor b,c ale prelucrării a două secvențe vecine (p,m) și (m+1,q), obținându-se rezultatul a al prelucrării secvenței (p,q).

Valoarea m este obținută apelând procedura diviz.

Complexitatea metodei Divide et impera

Să presupunem că avem un algoritm A cu timp pătratic ce permite rezolvarea unei subprobleme a problemei inițiale. Fie c o constantă, astfel încât timpul pentru a rezolva o problemă de marimea n cu ajutorul algoritmului A este tA(n) cn2. Să presupunem că este posibil să rezolvăm problema inițială prin descompunerea sa în trei subprobleme, fiecare de mărimea [n/2]. Fie k o constantă, astfel încât timpul necesar pentru descompunere și recompunere este t(n) kn. Folosind vechiul algoritm A și ideea de descompunere –recompunere a subproblemelor, obținem un nou algoritm B, pentru care:

tB(n)=3tA([n /2])+t(n) 3c((n+1)/2)2+kn=3/4cn2+(3/2 +d)n+3/4c

Când n este suficient de mare, termenul ¾ cn2 domină pe ceilalți, ceea ce înseamnă că algoritmul B este în esența cu 25% mai rapid decât algoritmul A. Cu toate acestea, prin algoritmul B nu am reușit să schimbăm ordinul de complexitate al algoritmului A, algoritmul B fiind tot pătratic.

Dar procedeul de descompunere – recompunere continuă în mod recursiv așa că se obține un nou algoritm recursiv C cu ajutorul căruia se ajunge la subprobleme care nu sunt, mai mari decât prag n0 pentru care bineânțeles că folosim spre rezolvare algoritmul A. Algoritmul C va avea timpul:

În concluzie, prin tehnica Divide et impera se reușește o reducere importantă a timpului de execuție.

CAPITOLUL VI METODE EURISTICE

Am văzut că mulți dintre algoritmii prezentați până acum au o comportare exponențială în ce privește timpul de execuție, fapt care face uneori total neeficientă utilizarea lor. Din acest motiv adesea se acceptă – pentru problemele respective –utilizarea unor algoritmi despre care nu se știe sau nu s-a demonstrat deocamdată că sunt optimali, dar care furnizează rezultatele acceptabile, într-un timp mai scurt.

VII.1.Descrierea generală

Un altgoritm se numește euristic dacă are următoarele proprietăți:

– de obicei furnizează soluții „bune”, dar nu neapărat optimale;

– este ușor de implementat și permite obținerea rezultatelor într-un timp rezonabil (în orice caz mai scurt decât cel cerut de orice algoritn exact cunoscut).

În elaborarea algoritmilor euristici, una din ideeile frecvente utilizate constă în descompunerea procesului de căutare a soluției (soluțiilor ) optime în mai multe subprocese (etape) succesive, fiecare dintre aceste subprocese constatând dintr-o optimizere.

Deoarece alegerea unei soluții optime la o anumită etapă poate împiedica atingerea în final a unei solutii optime a întregii probleme (cu alte cuvinte, optimizarea locală nu implică,în general, optimizarea globală), este evident că o asemenea strategie nu poate conduce întotdeauna la o soluție optimă. Observăm că regăsim un principiu asemănător cu principiul Greedy. Prin urmare, un algoritm elaborat pe baza metodei Greedy și care furnizează o soluție care nu este optimă (sau nu putem demonstra optimalitatea ei) este un algoritm euristic.

Pentru a elabora în mod sistematic un algoritm euristic, este

convenabil să se pună în evidență toate condițiile pe care le satisface o soluție exactă, după care aceste condiții să se împartă conform anumitor criterii în două (sau mai multe) clase. Două asemenea criterii sunt:

facilitatea satisfacerii condițiilor enunțate

-necesitatea satisfacerii conditiilor enunțate

În cazul primului criteriu (facilitatea ) se pot considera următoarele două clase de condiții

condiții ușor de îndeplinit ;

condiții dificil de îndeplinit;

În asemenea situații se poate accepta satisfacerea numai a condițiilor

din prima clasă (cele ușor de îndeplinit), cu condiția ca ele să fie suficient de cuprinzătoare pentru a se obține o soluție posibilă (chiar dacă nu neapărat optimă).Bineânteles că în această situație este necesar să se demonstreze că rezultatul obținut este o soluție posibilă.

În cazul celui de al doilea criteriu (necesitatea), condițiile pot fi împărțite în :

condiții necesare, în sensul că neândeplinirea lor împiedică obținerea unei soluții posibile a problemei

condiții pentru care se poate aceepta un compromis, în sensul că ele pot fi înlocuite

cu alte condiții ce permit apropierea de o soluție optimală(eventual chiar obținerea unei soluții optimale).

În asemenea situații, satisfacerea condițiilor din primă clasă este

obligatorie, iar calitatea soluției depinde în mare măsură de compromisul adoptat pentru condițiile din a doua clasă.

Observații 1) Algoritmii euristici sunt folositori și în situația în care ei sunt utilizați o singură dată (sau de puține ori), caz în care efortul de determinare a unei soluții optime este prea mare față de câștigul obținut.

2) Deși algoritmii euristici pot la prima vedere să șocheze un matematician pur, situația este de cele mai multe ori exact inversă.Într-adevăr, toții algoritmii din analiza numerică (încadrată în matematica pură) furnizează soluții aproximative chiar teoretic, fără a pune la socoteală propagarea erorilor de rotunjire, care sunt greu controlabile și pot schimba uneori un proces convergent într-unul divergent.

VII.2.Exemple

Problema 7.1(Problema comis-voiajorului) Fie G=(X,V) un graf neorientat în care oricare două vârfuri diferite ale grafului sunt unite între ele printr-o muchie, căreia i se asociază un cost strict pozitiv. Se cere să determinăm un ciclu care să înceapă dintr-un vârf oarecare al grafului, să treacă exact o dată prin toate celelalte vârfuri și să se întoarcă în vârful inițial, ciclu care să îndeplinească în plus condiția că are un cost minim (costul unui lanț fiind definit ca suma costurilor atașate muchiilor componente).

Soluție Toți algoritmi ce conduc la soluția optimă pentru această problemă, o furnizează într- un timp de execuție de ordin exponențial. În continuare va fi prezentat un algoritm euristic ce

necesită pentru determinarea soluției unui timp polinominal. El se bazează pe următoarea strategie Greedy dacă (v0,v1,…,vk) este lanțul deja construit, atunci avem următoarele situații:

dacă s-a trecut prin toate vârfurile grafului adică {v0,v1,….,vk}=X, atunci se adaugă în sfârșit și

muchia (vk,v0) care încheie de fapt construcția ciclului;

dacă nu au fost parcurse toate vârfurile grafului, adică {v0,v1,…,vk}=X, atunci se va adăuga acea muchie (vk,vk+1) care are costul minim și pentru care vk+1{v0,v1,….,vk}.

Să notăm cu n numărul vârfurilor grafului G(adică n= X . Fie C matricea

pătrată de ordin n în care c[i,j] 0 este costul atașat muchiei (i,j). Vom nota prin cost (un număr real pozitiv) costul lanțului deja construit și la care urmează să adăugăm eventual o nouă muchie, prin p un vector cu n componente (unde p[i] este 0, respectiv 1, dacă vârful i nu aparține respectiv aparține, lanțului deja construit), iar prin ciclu, un vector cu n+1 componente care va conține în ordine vârfurile lanțului deja construit (vom nota prin nc numărul vârfurilor existente în ciclul la pasul curent). Cu vc vom nota vârful curent iar cu vu notăm vârful următor (ce urmează a fi vizitat). Atunci, programul Pascal pentru problema comis- voiajorul este următorul:

Program Comis_voiajorul; uses crt;

const n=5;

type matrice= array[1…n,1…n] of real; var c:matrice;

ciclu :array[1..n+1] of byte; i,j: byte;

cost: real; procedure cv (i: integer);

var k, nc, vc, vu, w: byte; p:array [1…n] of byte; cmin:real;

begin

for k:=1 to n do p[k]:=0;

ciclu[1]:=i; nc:=1; p[i]:=1; cost:=0; vc:=i; for k:=1 to n-1 do

begin

cmin:=maxint; for w:=1 to n do

if (p[w]=0) and (c[vc,w]<cmin) then

begin

end ;

cmin:=c[vc,w] ;

end ;

ciclu[k+1] :=vu ; cost :=cost+cmin ; p[vu] :=1 ; vc :=vu

end; begin

clrscr;

ciclu[n+1] :=i ; cost :=cost+c[vc,i]

for i:=1 to n do

begin

end;

writeln (‘Costurile de la varful’,i:2,’la celelalte varfuri ’); for j :=1 to n do

read (c[i,j])

writeln (‘Introduceti varful din care pleaca comis-voiajorul:’); readln (i);

cv (i);

writeln (‘Ciclul gasit este:’); repeat until keypressed

end.

Se observă că dacă aplicăm algoritmul descris de acest program (în care esențială este procedura cv,ce implementează o strategie de tip Greedy) pentru graful din figura VII.1 a plecând din vârful i=1, se obține ciclul din figura VII.1 b, având costul 14.

VII.1. Exemplu de graf și cicluri pentru problema 7.1.

Acest ciclu nu este optim, deoarece de exemplu ciclul din figura VII.1c are costul 13.

Se poate constata foarte ușor că algoritmul utilizat de program respectă condiția necesară ca să obținem un ciclu plecând din vârful i, trecând exact o dată prin fiecare din celelalte vârfuri și

întorcându-ne în vârful i. În schimb pentru condiția ca ciclul să fie de cost minim s-a acceptat compromisul alegerii la fiecare pas a muchiei de cost minim (optimul local).

Dacă analizăm complexitatea algoritmului descris, se constată mai întâi citirea matricii C necesită un timp în ordinul O(n2). Se observă ușor că și procedura cv necesită un timp tot în ordinul O(n2) deoarece acolo întâlnim două cicluri for incluse unul în celălalt. Acest ordin constituie o margine inferioară a eficacității oricărui alt algoritm de rezolvare a problemei deoarece el este egal cu ordinul de mărime al numărului de operații de citire a datelor.

Programul poate fi înbunătățit dacă se realizează reluarea succesivă a procedurii cv pentru un număr m {2,….,n} De vârfuri dinstincte, reținând soluția de cost minim. Mai mult, dacă pentru un vârf inițial din cele alese se ajunge la un moment dat la un lanț de cost mai mare decât cel al ciclului de cost minim obținut prin aplicarea procedurii cv pentru vârfurile inițiale deja considerate, se va întrerupe completarea acestui lanț și se va trece la aplicarea procedurii pentru vârful inițial

următor. Prin urmare, timpul cerut de această variantă este cel mult de ordinul O(mn2) adică cel

mult O(n3).Această înbunătățire poate să ajungă, pentru graful luat ca exemplu, la considerarea drept vârf inițial a vârfului 2, ceea ce conduce la ciclul din figura VII.2,al cărui cost este 10.

Fig.VII.2. Un ciclu optim

Exemplul acesta arată că reluarea cu mici modificări a unui algoritm euristic poate compensa într-o anumită măsură neajunsurile sale.

Problema 7.2 (Execuția lucrărilor de către mai multe procesoare)

Fie n procesoare P1,P2,…..,Pn și m lucrări L1,L2,….,Lm independente care trebuiesc efectuate cu ajutorul acestor procesoare, în următoarele condiții:

procesoarele pot funcționa simultan;

orice lucrare poate fi efectuată de către orice procesor;

o lucrare a cărei execuție este inițiată de un procesor este continuată de aceasta până la terminarea sa.

Cunoscând duratele t1,t2,….,tm necesare executării celor m lucrări, se cere o programare a lucrărilor la procesoare astfel încât ele să se termine (în ansamblul lor) cât mai repede.

Soluție O programare este bine definită de un vector L=(Li1,Li2,…, L im) cu {i1,i2,…,im}={1,2,….m}dacă sunt satisfăcute condițiile :

primul procesor devenit liber preia prima lucrare neprogramată din L;

dacă două sau mai multe procesoare devin libere simultan, cel care preia primul o lucrare este cel de indice minim;

procesoarele intră în funcțiune fără vreo întârziere.

Să consideram drept exemplu situația a trei procesoare și a 6 lucrări având în ordine duratele t1=2, t2=5, t3=8, t4=1, t5=5, t6=1. Programarea L= (L2, L5, L1, L4, L6, L3),conform căreia executarea lucrărilor cere timpul T1=12, este ilustrată sugestiv în figura VII.

L 2

P1 5

L5

Fig. VII. 3 Un exemplu de planificare a lucrărilor

După cum se vede procesoarele P1 și P2 stau mult timp neocupate, astfel încât programarea indicată are puține șanse de a fi optimă.Într-adevăr, o programare mai bună este programarea L= (L3, L2, L5, L1, L4, L6),ilustrată în figura VII.4.care necesită timpul T2=8.

P1 L3

8

P2 L5 L1

P3 L5 L4 L6

Fig.VII.4 Un exemplu de planificare mai bună a lucrărilor

Mai mult,această programare este chiar optimă, deoarece durata lucrării L3, este egală cu 8, deci durata oricărei programări este cel puțin egală cu 8.

O procedură euristică foarte simplă pentru rezolvarea problemei discutate constă în programarea lucrărilor în ordinea descrescătoare a duratei lor. În cazul exemplului studiat se obține chiar programarea optimă L descrisă mai sus.

Să observăm însă că în general procedura euristică descrisă mai sus nu conduce la programarea optimă. Fie drept exemplu cazul a două procesoare și a 5 lucrări, cu timpii t1=3, t2=3, t3=2, t4=2, t5=2. În figura VII.5 apar programarea (L1, L2, L3, L4, L5) obținută conform algoritmului euristic și programarea optimală (L1, L2, L3, L4, L5), timpii fiind 7, respectiv 6.

P1 L1 L3 L5 P1 L1 L2

3 2 2 3 3

P2 L2 L4 P2 L3 L4 L5

Fig.VII.5 Exemplu de programare euristică neoptimă

După cum se vede, ca și în exemplul anterior, condiția ca durata efectuării lucrărilor să fie minimă- condiție mai greu de satisfăcut a fost înlocuită cu condiția efectuării prioritare a lucrărilor cu durate mai mari.

Să mai observăm că uneori putem renunța la condiția că procesoarele să intre în funcție fără vreo întârziere. Astfel în cazul primului exemplu, programarea L2, rămâne optimală chiar dacă amânăm începerea lucrării L1 cu o unitate de timp.

O altă strategie frecvent utilizată pentru elaborarea algoritmilor euristici constă în modificarea locală (parțială) a unei soluții date. Astfel în cazul ciclului din figura VII.1b dacă înlocuim porțiunea (5,3,4,1) din ciclul cu (5,4,3,1), obținem tot un ciclu, dar cu un cost mai mic.

În încheiere menționăm că o caracteristică generală a algoritmilor euristici este marea lor sensibilitate la schimbări ale datelor inițiale ale unei probleme. Mai precis schimbări mici ale datelor pot avea drept efect apropierea dar și îndepărtarea simțitoare a soluției de soluția optimală. Sunt tipici în acest sens mulți algoritmi din analiza numerică, un exemplu fiind prezentat în continuare.

Problema 7.3(Maximul unei funcții pe un interval) Fie dată o funcție f:[a,b] R; se cere determinarea maximului M a funcției pe acest interval.

Soluție O procedură euristică constă în următoarele

împărțim intervalul [a,b] în părți n egale (fie h= b a )

n

determinăm punctele de „maxim local” ca fiind acele puncte x1=a+hi pentru care f(xi-

1) f(xi) f(xi-1) și îl alegem pe cel care produce o valoare maximă pentru funcția f.

Ținând cont că algoritmul nu depinde de funcția f în totalitatea ei ci numai de valorile ei în punctele a, a+h, a+2h,…,b este evident că schimbările (de exemplu translatările) foarte mici ale funcției f pot antrena modificarea substanțială a valorii maxime furnizate de algoritmul euristic.

Problema 7.4 (Colorarea unui graf). Fie G=(X,V) un graf neorientat, al cărui vârfuri trebuie colorate astfel încât oarecare două vârfuri adiacente să fie colorate diferit. Problema este de a obține o colorare cu un număr minim de culori.

Soluție Vom folosi următorul algoritm Greedy alegem o culoare și un vârf de pornire arbitrar, apoi considerăm vîrfurile rămase, încercând să le colorăm, fără a schimba culoarea. Când nici un vârf nu mai poate fi colorat, schimbăm culoarea și pornim cu vârful 2, lorându-l cu maro. Mai putem colora cu maro și vârful 5.

Fig.VI.6 Un exemplu de graf pentru colorat

Deci ne-au fost suficiente două culori. Dacă colorăm vârfurile în ordinea 1,5,2,3,4, atunci se obține o colorare cu trei culori. Se observă încă o dată că aplicând strategia Greedy nu obținem decât o soluție euristică, care nu este în mod necesar soluția optimă a problemei. Cum toți ceilalți algoritmi cunoscuți care rezolvă optim această problemă sunt exponențiali și deci, practic, nu pot fi folosiți pentru cazuri mari, acest algoritm Greedy euristic propus ne interesează mai mult deoarece el este simplu și eficient, furnizându-se o soluție acceptabilă intr-un timp mult mai scurt.

Un caz particular al problemei colorării unui graf este celebra problemă a colorării hărților o hartă oarecare trebuie colorată cu un număr minim de culori, astfel încât două țări cu frontieră comună să fie colorate diferit.

Celebritatea problemei constă în faptul că, în toate exemplele întâlnite, colorarea s-a putut face ce cel mult 4 culori. Aceasta în timp ce, teoretic, se putea demonstra că pentru o hartă oarecare are nevoie de cel mult 5 culori.

Cu câțiva ani în urmă s-a demonstrat pe calculator faptul că orice hartă poate fi colorată cu cel mult 4 culori. Aceasta este prima demonstrație pe calculator a unei teoreme importante.

Acestei probleme i se pot atașa un graf planar astfel : fiecărui vârf îi corespunde o țară, iar două vârfuri adiacente reprezintă țări cu frontieră comună și astfel se poate rezolva ca un caz particular al problemei 7.4.

Problema colorării unui graf poate fi interpretată și în contextul planificării unor activități. De exemplu, să presupunem că dorim să executăm simultan o mulțime de activități, în cadrul unor săli de clasă. În acest caz, vârfurile grafului reprezintă activități, iar muchiile unesc activitățile

incompatible. Numărul minim de culori necesare pentru a colora graful corespunde numărul de săli necesare.

Problema 7.5(Săritura calului ). Fie dată o “tablă de șah”, de dimensiune nxn. Se pleacă cu un cal din poziția (1,1), adică din colțul din stânga sus. Nefiind interzisă nici o poziție, se cere să se efectueze cu calul, conform regulilor de șah, o succesiune de mutări astfel încât calul să treacă o dată și numai o dată prin fiecare pătrat al tablei de șah.

Soluție Problema a fost rezolvată și în capitolul III prin metoda Backtracking, dar am vazut că pentru o valoare a lui n nu foarte mare (de exemplu 8) timpul de calcul este foarte mare.

De aceea este interesantă rezolvarea acestei probleme utilizând o euristică Greedy. Ideea constă în următoarele calul pornește din poziția (1,1) iar la fiecare pas alegem acea mutare care plasează calul într-o poziție din care, la următoarea mutare, avem cât mai puține posibilități de a muta din nou.

O explicație (nu o demonstrație) a acestei idei ar fi următoarea calul ocupă poziții cât mai puțin accesibile (care cu altă ocazie ar fi greu de atins).Acesta este un principiu interesant care ar merita să fie încercat și pentru alte probleme.

PARTEA II

METODE INTERACTIVE DE PREDARE

Capitolul I

CONSIDERAȚII METODICE

Metode interactive de predare

Predarea tradițională în sensul în care profesorul ține o prelegere, face o demonstrație, iar rolul elevilor este acela de a urmări, nu produce învățare decât în foarte mică măsură. Este insuficient pentru învățare dacă în timpul orei elevii doar ascultă explicațiile profesorului și văd o demonstrație făcută de profesor. Cauza acestui fenomen, ține de însuși funcționarea creierului. Creierul nu funcționează ca un DVD sau casetofon. Creierul nu este un simplu receptor de informație. Creierul funcționează asemenea unui computer, acesta din urmă a fost proiectat și creatdupă modelul de funcționare al creierului.

Pentru ca un computer să înceapă să funcționeze trebuie să apăsăm butonul de pornire. În cazul în care învățătoarea este „pasivă”, butonul „pornire” al creierului nostru este activat. Unui computer îi este necesar pentru a fi în stare de funcționare de un soft adecvat pentru a interpreta datele introduse și creierul nostru are nevoie să facă unele conexiuni cu ideile ancoră deja cunoscute. Când învățarea este „pasivă”, creierul nu face aceste legături. Un computer nu reține informația procesată decât dacă acționăm butonul „salvare”. Creierul nostru trebuie să testeze informația sau să o explice altcuiva pentru a o stoca.

Profesorii își inundă elevii cu propriile lor gânduri profunde și bine organizate. Profesorii recurg prea des la explicații și demonstrații de genul „haisațiarătcum”. Desigur că, prezentarea poateface o impresie imediată asupra creierului, dar în absența unei memorii excepționale, elevii nu pot reține prea mult pentru perioada următoare. Un profesor, oricât de strălucit orator ar fi, nu se poate substitui creierelor elevilor și deci nu poate face activitatea care se desfășoară individual în mintea fiecăruia. Elevii înșiși trebuie să organizeze ceea ce au auzit și văzut intr-un tot ordonat și plin de semnificații. Dacă elevilor nu li se oferă ocazia discuției, a investigației, a acțiunii și eventual a predării, învățarea nu are loc.

Învățarea presupune înțelegerea, iar aceasta înseamnă mai mult decât cunoașterea faptelor.

Elevii construiesc cunoașterea pe baza a ceea ce deja cunosc sau cred.

Elevii formulează noile cunoștințe prin modificarea și raționarea conceptelor lor curente și prin adăugarea de noi concepte la ceea ce cunosc deja.

Învățarea este mediată de mediul social în care elevii interacționează unii cu alții.

Învățarea eficientă necesită preluarea de către elevi a controlului asupra propriei învățări.

Transferul, respectiv capacitatea de a aplica cunoștințe în situații noi este afectat de gradul în care elevii învață pentru înțelegere și învață cu înțelegere.

Fără îndoială, este adevărat că acela care învață trebuie săși construiască cunoașterea prin intermediul propriei înțelegeri și că nimeni nu poate face acest lucru în locul său. Dar nu este mai puțin adevărat că această construcție personală este favorizată de interacțiunea cu alții care la rândul lor învață. Dacă elevii își construiesc cunoașterea proprie ei nu o fac singuri. Să nu uităm că omul este fundamental social.

Adevărata învățare este aceea care permite transferul achizițiilor în contexte noi. Este nu doar simplu activă, individual activă ci interactivă. Reciprocitatea este un stimulent al învățării, când acțiunea comună este necesară, când reciprocitatea este activată în cadrul unui grup în vederea obținerii unui rezultat, atunci par să existe procese care stimulează învățarea individuală și care conduc pe fiecare la o competență cerută de constituirea grupului. Gruparea și sarcinile în care membrii grupului depind unul de celălalt pentru realizarea rezultatului urmărit arată că:

elevii se implică mai mult în învățare decât în abordările frontale sau individuale.

elevii odată implicați își manifestă dorința de a împărtăși celorlalți ceea ce experimentează, iar aceasta conduce la noi conexiuni în sprijinul înțelegerii.

elevii acced la înțelegerea profundă atunci când au oportunități de a explica și chiar preda celorlalți colegi ceea ce au învățat.

Mozaicul presupune următoarele etape:

Împărțirea clasei în grupuri eterogene de 4 elevi, fiecare dintre aceștia primind câte o fișă de învățare numerotată de la 1 la 4. Fișele cuprind părți ale unei unități de cunoaștere.

Prezentarea succintă a subiectului tratat.

Explicarea sarcinii care constă în înțelegerea întregii unități de cunoaștere.

Regruparea elevilor, în funcție de numărul fișei primite, în grupuri de experți: toți elevii care au numărul 1 vor forma un grup s.a.m.d..

Învățarea prin cooperare a secțiunii care a revenit grupului din unitatea de cunoaștere desemnată pentru oră: elevii citesc, discută, încearcă să înțeleagă cât mai bine, hotărăsc modul în care pot preda ceea ce au înțeles colegilor din grupul lor original.

Revenirea în grupul inițial și predarea secțiunii pregătite celorlalți membrii.

Trecerea în revistă a unității de cunoaștere prin prezentare orală cu toată clasa.

Exemplu de activitate de învățare: Obiectul: Limba și Literatura Română Subiectul : Părțile de propoziție ( recapitulare)

Elevii sunt împărțiți în grupe de câte patru.

Fiecare primește un număr 1; 2; 3; 4; și câte o fișă de lucru individuală (fiecare fișă conține după caz următoarele ATRIBUTUL, COMPLEMENTUL, SUBIECTUL, PREDICATUL) Elevii se regrupează după numărul pe care lau primit, de exemplu toși elevii care au grupa numărul 1 formează o grupă, toți elevii care au numărul 2…, toți elevii care au numărul 3…, toți elevii care au numărul 4….

Astfel grupați ei lucrează în grupul lor, se consultă acolo unde nu știu sau au nelămuriri, dacă este cazul sunt ajutați de învățător.

După ce au finalizat fișa de lucru, elevii se regrupează ca la început și devin EXPERȚI în grupul lor. Le prezintă și colegilor conținutul fișei, le dau lămuririle necesare acolo unde este cazul.

Învățătorul monitorizează activitatea elevilor.

CUBUL Metoda presupune explorarea unui subiect din mai multe perspective. Sunt recomandate următoarele etape:

o Realizarea unui cub pe ale cărui fețe sunt scrise cuvintele: descrie, compară, analizează, asociază, aplică, argumentează.

Anunțarea temei.

Împărțirea clasei în 6 grupe, fiecare dintre ele examinând o temă de pe fețele cubului.

Descrie: culorile, formele, mărimile etc. Compară:ce este asemănător, ce este diferit. Analizează:spune din ce este făcut.

Asociază:la ce te îndeamnă să te gândești? Aplică:la ce poate fi folosită?

Argumentează:pro sau contra și enumeră o serie de motive care vin în sprijinul afirmației tale. o Redactarea finală și împărtășirea ei celorlalte grupe.

Afișarea formei finale pe tablă. Clasa aIIIa Exemplu de activitate de învățare: Obiectul: Limba și Literatura Română Tema: Adjectivul(consolidare)

Elevii sunt împărțiți în 6 grupe.

Fiecare din cele 6 grupe șia ales ca simboluri următoarele jetoane: ursuleț, minge, mașinuță, clovn, zar, păpușă( toate aceste simboluri reprezintă jucării).

Învățătoarea le prezintă elevilor un cub care are desenat pe fiecare latură una din jucăriile amintite mai sus, pe care va trebuii să:

ursulețul DESCRIE

mingea COMPARĂ

mașinuța ANALIZEAZĂ

clovn ASOCIAZĂ

zar APLICĂ

păpușăARGUMENTEAZĂ

Toate aceste operațiuni elevii le vor face pe fișe, fiecare echipă va primii o fișă conform simbolului ales.

După ce elevii vor lucra pe echipe aceste fișe, vor venii la tablă, bineînțeles un reprezentant al fiecărei echipe, care va prezenta colegilor rezultatele finale ale fișelor de lucru.

Ciorchinele Este o metodă de brainstorming neliniară care stimulează găsirea conexiunilor dintre idei, presupune următoarele etape:

Se scrie un cuvânt sau temă care urmează a fi cercetat în mijlocul tablei.

Se notează toate ideile care vin în minte în legătură cu tema respectivă în jurul acestuia, trăgânduse linii între acestea și cuvântul inițial.

Pe măsură ce se scriu cuvinte se trag linii între toate ideile care par a fi conectate.

Activitatea se oprește când se epuizează toate ideile. Clasa a IIa Obiectul: Cunoașterea mediului Tema: Animalele(recapitulare)

Elevii sunt împărțiți în grupe de câte 6 elevi.

Fiecare echipăprimește câte o fișă, care are scris în centrul ei, intr-un oval, animale domestice/animale sălbatice din țara noastră/animale sălbatice din alte zone ale lumii.

Elevii trasează pe fișă săgeți din acel oval, scriind animalele care fac parte din acea categorie.

După ce au finalizat fișa elevii, cei care au fost desemnați experți, vin la tabla și prezintă întregii clase, animalele din acea categorie, pe care a reușit să le găsească.

Turul galeriei Presupune evaluarea interactivă și formativă a produselor realizate de grupul de elevi. 1.În grupuri de 3 sau 4, elevii lucrează întâi la o problemă care se poate finaliza intr-o diagramă.

Produsele sunt expuse pe pereții clasei.

La semnalul profesorului, grupurile se rotesc prin clasă, pentru a examina și a discuta fiecare produs.

După turul galeriei, grupurileîși reexaminează propriile produse prin comparație cu celelalte. Clasa aIIa Obiectul: Cunoașterea mediului Tema: Animalele(recapitulare)

Elevii sunt împărțiți în grupe de câte 6.

Ei vor primii plicuri cu jetoane care au reprezentate animale domestice/animale sălbatice din țara noastră/animale sălbatice din alte zone ale lumii. Elevii vor trebui să realizeze machete cu aceste jetoane.

Fiecare membru al echipei va avea ceva de lucru în echipă. Unul decupează, altul lipește, fixează pe suport, verifică, ajută.

Aceste machete se expun în clasă elevii trec pe rând analizează, macheta își notează pe un carnețel ceea ce este bun și ceea ce nu este realizat bine, dacă este cazul, la sfârșit se fac aprecieri și daca este cazul se fac și unele critici constructive.

Dezvoltări recente pentru a spori eficacitatea sistemelor educative

În căutarea unor soluții pentru a spori eficacitatea sistemelor educative, în ultimele decenii tot mai mulți cercetători siau îndreptat atenția asupra locusului unde se produce învățarea; centrarea pe elev nu reprezintă decât flamura pe care o poartă deschizătorii unui drum la carebtrudesc specialisti de diferite culori și nuanțe, formați la școli de gândire diferite, cu viziuni teoretice, ipoteze și obiective uneori foarte distanțate.

Caracteristicile platformei comune, cristalizate în disputa cu reprezentanțții “obiectivismului”, sunt sintetizate astăzi în răspunsurile la cele patru întrebări fundamentale:

Ce este învățarea?

Ce reprezintă procesul de învățare?

Care este rolul educatorului în procesul de învățare?

Ce poate face educatorul pentru a îndeplini acest rol?

Învățarea: Cunoasterea este construită de oameni și nu există în afara minții umane.

Elevii își construiesc înțelegerea. Ei caută sensul și încearcă să descopere regularitatea și ordinea chiar în absența unei informații complete. Constructivismul are în vedere construirea cunoasterii în timp ce obiectivismul se ocupă în special de obiectul cunoasterii.

Procesul de învățare: Învățarea este un proces activ. Informația poate fi impusă din exterior, dar nu și înțelegerea; aceasta trebuie să vină din interior. Învățarea este determinată de o interacțiune complexă între cunoasterea existentă a subiecților, contextul social și problema de rezolvat. Instruirea se referă la asigurarea subiecților cu o situație de colaborare în care ei să aibă atât mijloacele, cât și oportunitatea de a construi o nouă înțelegere.

În acest proces o atenție deosebită se acordă problemei de rezolvat, elementul căreia i se cere să stimuleze explorarea și reflecția necesară pentru construirea cunoasterii. Se consideră că o problemă corespunzătoare ar trebui să dispună de următoarele atribute:

să solicite construireasi testarea unor predicții,

să poată fi rezolvată fără echipamente costisitoare,

să aibă o complexitate realistă, normală,

să fie relevantă și interesantă pentru subiecți.

A doua caracteristică a procesului este interacțiunea dintre subiecți; lucrul în comun pentru rezolvarea problemei îi oferă fiecăruia posibilitatea de asi testa și ameliora înțelegerea pe parcursul interacțiunii.

Rolul educatorului. Constructivismul are nevoie de un educator care să–i ajute pe elevi să devină participanți activi în învățare. Educatorul trebuie să stimuleze dezvoltarea subiecților oferindule sarcini pe care ei să le poată îndeplini numai cu ajutor, adică în zona proximei dezvoltări.

Ce poate face educatorul. Intr-o sinteză a bogatei literaturi dedicate acestei probleme se menționează următoarele atribute ale educatorului constructivist:

încurajează și acceptă autonomia și inițiativa elevilor,

foloseste o mare varietate de materiale, înclusiv date brute, surse primare, materiale interactive și îi încurajează pe elevi să le utilizeze,

se interează de cunoasterea de către elevi a conceptelor, înainte de a le împărtăsi cunoasterea proprie,

îi încurajează pe elevi să angajeze dialogul cu educatorul sau cu ceilalți colegi,

încurajează tentativele elevului de explorare a cunoasterii și de a pune întrebări colegilor,

îi angajează pe elevi în experiențe care pun în lumină contradicții cu cunoasterea inițială, stimulând apoi discuția,

le asigură elevilor timp pentru construirea relațiilor și crearea metaforelor,

apreciază nivelul de cunoastere prin aplicații și rezultatele la sarcini “deschise”.

În esență, sarcina educatorului este să creeze și să mențină un context de “rezolvare de probleme”, în care elevii săsi construiască propria lor cunoastere, avândul pe educator drept ghid.

Este de la sine înțeles că orientarea spre o abordare constructivistă a educației nu poate, și nici nu îsi propune, să rezolve toate problemele învățământului. Cercetările din acest domeniu încearcă să ducă mai departe cunoasterea umană și să sugereze căi de a ameliora practica scolară. Am putea spune că momentul reprezintă un pas semnificativ în ceea ce priveste

scientizarea pedagogiei. Nu este lipsit de interes faptul că multe institute de cercetare siau definit transant poziția de pe care îsi vor desfăsura investigațiile în prima perioadă a acestui secol. Astfel, cunoscutul Institute for Learning Technologies (Columbia University) îsi precizează intr-un material programatic – “Pedagogy for the 21st Century” – punctele de plecare și jaloanele orientative ale demersului investigativ pe care îl va întreprinde în anii ce vin. Astfel, ILT consideră că specialistii domeniului converg spre ideea că pentru secolul XXI o scoală de dimensiuni mici, în care activitatea educativă poate fi structurată în raport cu nevoile și interesele elevilor – va fi mai eficientă și mai competitivă; activitatea elevilor trebuie să fie orientată de proiecte la definirea cărora ei au participat și săi implice intr-un real travaliu intelectual, nu în exerciții de memorare. ILT promovează deschis constructivismul, considerând că acesta reprezintă în momentul de față o colecție de teorii și idei (unele complementare, altele – exclusiviste) cu privire la diferite problem ale pedagogiei.

Impactul asupra educației a noilor concepte, arii curriculare si strategii

În abordarea problemelor ridicate de gândirea și practica educațională – aflate intr-o fază incipientă a transformării paradigmei tradiționale literatura de specialitate este marcată de numeroase viziuni/poziții/recomandări, uneori divergente. Pentru un proiect ca cel de față se impune

– ca punct de plecare – realizarea unui cadru de referință comun, coerent, care să le permită atât formatorilor, cât și cursanților construirea unei viziuni teoretice asupra procesului educațional, la nivelul gândirii și practicii actuale.

Ne propunem să definim atât conceptele de bază ale teoriei și practicii educaționale: competențe, competențecheie, centrare pe elev, cât și ariile problematice, corespunzătoare, implicate în procesul educațional. Desi vehiculate intens în literatura domeniilor „educație”, „învățământ” – aceste concepte generează uneori confuzii fie datorită faptului că sunt decodificate diferit, fie exemplificărilor care de multe ori nu corespund atributelor conceptului în cauză. La aceste situații se adaugă pentru unii termeni (denumiri de concepte) „pecetea istoriei” sau a „spațiului lingvistic”:

unul și acelasi concept este reprezentat de termeni diferiți fie pe verticala timpului, fie pe orizontala spațiului lingvistic (uneori pe ambele axe).

Competențe

Fiind pus în situația de a proiecta un proces educațional în asa fel încât să aibă ca rezultat formarea unor competențe în fața profesorului apar obstacole teoretice: care este accepția conceptului „competență”, prin ce demersuri didactice se poate forma etc.

În ceea ce priveste definirea conceptului „competență”, literatura domeniului ne oferă o varietate de poziții/abordări. Definiției de largă generalitate a „competenței” (ansamblu de) comportamente potențiale (afective, cognitive și psihomotorii) de care dispune un individ pentru a realiza o activitate – Ph. Perrenoud îi oferă mai multă concretețe în cadrul de referință educațional, definind

„competența”, drept capacitatea de a acționa eficace intr-o anumită situație, capacitate care se bazează pe cunostințe (declarative, procedurale, condiționale), mobilizândule, utilizândule, integrândule pentru a face față situației. Considerând „competența” o potențialitate generică a spiritului uman, Perrenoud subliniază “(competențele)…nu apar spontan numai ca urmare a maturizării sistemului nervos; potențialitățile individului nu se transformă în competențe efective decât pe măsura învățării/ exersării; genetic, omul este dotat să vorbească, dar pentru a transforma acest potențial în competență el trebuie să învețe să vorbească…”.

Referinduse la opoziția termenilor competență – performanță, se menționează că performanța observată reprezintă numai un indicator al competenței.

D`Hainaut (1988) defineste competența drept “ansamblu de savoirs, savoirsfaire și savoirêtre (a sti, a sti să faci, a sti să fii) care permit exercitarea convenabilă a unui rol, a unei funcții sau a unei activități”.

În anii 80, psihologii britanici (Working Group on Vocational Qualifications, 1986) cad de acord asupra unei definiții fundamentale a competenței: „abilitatea de a face o activitate oarecare la un standard prestabilit”, marcând diferențierea de “cunoastere”: “competența se referă la ceea ce oamenii pot face, mai curând decât la ceea ce ei cunosc”. De aici decurgeau următoarele implicații:

competența presupune o activitate, deci trebuie să existe un context,

competența reprezintă un rezultat care pune în evidență ce poate face o persoană, deci nu trebuie să descrie procesul de învățare prin care a trecut subiectul,

pentru a măsura abilitatea de a face ceva este necesară definirea unor standarde clare și accesibile, care să permită măsurarea și acreditarea performanței,

competența este măsura a ceea ce poate cineva la o anumită dată.

Perrnoud face și o diferență între competențe și cunostințe procedurale (a sti să faci): orice cunostință procedurală reprezintă o competență; dar, o competență poate fi mai complexă, deschisă, mai flexibilă decât o cunostință procedurală și mai articulată la cunostințele teoretice; o cunostință procedurală poate funcționa ca resursă mobilizabilă de mai multe competențe diferite, de nivel mai înalt (cu o structură mai complexă).

Nici o resursă nu aparține exclusiv unei singure competențe, în măsura în care ea poate fi mobilizată de alte competențe. În acelasi timp, o competență poate funcționa ca resursă pentru competențe mai complexe. B. Rey (1996) precizează că deoarece orice competență face față unei familii de situații (imbricare/dezvoltare/diferențiere), competențele sunt transversale, iar operarea cu analogii declansează transferul. După Perrnoud „Această funcționare cognitivă ține, în acelasi timp, atât de repetitivitate, cât și de creativitate, deoarece competența mobilizează amintirea experiențelor trecute, dar se degajează de ele, pentru a iesi din repetiție, pentru a inventa soluții parțial originale, care răspund, în măsura posibilului, la singularitatea situației prezente…”; mai mult, „Acțiunea competentă este o invenție bine temperată, o variațiune pe teme parțial cunoscute, o manieră de a reinvesti deja trăitul, deja văzutul, deja înțelesul sau stăpânitul, pentru a face față situațiilor destul de inedite pentru care simpla repetiție să fie inadecvată și destul de familiare pentru ca subiectul să nu se simtă total dezarmat.”

Evoluția sistemelor educative spre dezvoltarea competențelor reprezintă, pentru Perrnoud, o ipoteză demnă de cea mai mare atenție, dar această evoluție este extrem de dificilă întrucât presupune transformări radicale în programe, didactică, evaluare, în instituții, precum și în profesia de educator, în viziunea asupra atributului de “elev”; transformările vor provoca rezistența pasivă și activă, la toate nivelurile, a tuturor celor interesați să mențină o practică (cu care sunt obisnuiți) sau avantajele unor poziții.

Progresele în aria conceptuală „competențe” au impus și clarificările corespunzătoare înpalierul

„evaluării” a ceea ce poate fi considerat o competență; ca răspuns au fost cizelateevaluarea autentică și standardele de performanță.

Competențe cheie

Globalizarea și modernizarea – atribute esențiale ale dinamicii societății contemporane – îi solicită individului reacții/activități/atitudini din ce în ce mai complexe și mai variate, competențe care implică atât cunostințe (factice și procedurale), cât și mobilizarea resurselor psihosociale intr-un context particular. Ca răspuns la normala întrebare „Care ar putea fi competențele de care avem nevoie pentru a reusi în viață și pentru a contribui la buna funcționare a societății?” nu este posibilă întocmirea unor liste a tuturor competențelor de care ar trebui să dispună cineva în diverse contexte și în diverse stadii ale vieții sale; în schimb, poate fi prefigurat un ansamblu de cunostințe, deprinderi, atitudini și valori, care permit activități/performanțe în plan individual și social, facilitând reacții adecvate la exigențele unui larg evantai de contexte, importante pentru întreaga populație. Acest ansamblu ar cuprinde ceea ce denumim competențecheie (CC).

Prima cercetare de amploare cu finalizări pasibile de utilizare în practica educațională proiectul DeSeCo (Definition and Selection of Competencies: Theoretical and Conceptual Foundation – Definirea și selectarea competențelor: fundamentare teoretică și conceptuală), întreprinsă de OCDE (Organizația pentru dezvoltare și cooperare economică), încearcă să identifice un ansamblu restrâns de competențecheie, plecând de la teza fundamentală conform căreia fiecare competență trebuie:

să contribuie la obținerea de rezultate importante pentru societate și membrii ei,

săl ajute pe individ să răspundă la exigențele importante intr-un larg evantai de contexte,

să fie importantă pentru toți indivizii și nu numai pentru specialisti.

Proiectul DeSeCo sia propus să creeze un cadru conceptual care să permită identificarea CC de o manieră fundamentată și să amelioreze calitatea evaluărilor internaționale a competențelor adolescenților.

Programul DeSeCo detaliază activitățile de cercetare lărgind problematica CC:

Ce se înțelege prin CC, deprinderi etc? Cum pot fi conceptualizați și descrisi acesti termeni?

Ce noțiuni referitoare la natura ființei umane și societății trebuie să servească în calitate de punct de plecare pentru definirea și selecția CC?

Cum ar putea perspectivele diferitelor discipline academice să contribuie la înțelegerea și elaborarea unui set de CC?

Ce CC sunt necesare pentru a înțelege și acționa în diferite domenii, inclusiv cel economic, politic, social, familial, al relațiilor interpersonale publice și private, dezvoltării personale etc.?

În ce măsură CC sunt imutabile cu referire la condițiile sociale, economice și culturale?

În ce măsură este posibilă identificarea CC independent de vârstă, sex, status, activitate profesională etc.?

Cum poate această discuție stiințifică să contribuie la ameliorarea politicii și practicii educaționale?

Care este rolul politicii și practicii educaționale în definirea, selectarea și descrierea deprinderilor în calitate de CC?

Care este rolul instituțiilor sociale în transmiterea competențelor către populație?

Care este rolul educației, cu instituțiile și procesele sale specifice scoli și instruire în dezvoltarea CC?

Care este rolul altor surse potențiale de achiziție a competențelor – cum ar fi prietenii, părinții, mediul profesional, media, organizațiile religioase și culturale?

În ce măsură pot fi modificate sabloanele de transmitere? Cu alte cuvinte, în ce măsură transmiterea de CC poate fi controlată de politicile educaționale?

Care este relevanța ideilor emergente despre CC pentru dezvoltarea și interpretarea indicatorilor desemnați să evalueze competențele populației? (D.S. Rychen, L.H. Salganik, 2004, p.6).

Ipoteza fundamentală a acestei investigații presupune că CC reprezintă rezultatul mai multor factori având la nivelul de bază viziunea asupra lumii (incluzând societatea și individul), care afectează decisiv identificarea CC. Plecând de la acest cadru de referință, au fost identificate trei CC generice și sau formulat patru elemente relevante pentru definirea și selectarea CC.

Cele trei competențecheie generice:

a activa autonom și reflexiv,

a folosi interactiv instrumente (entități fizice, limbajul, cunostințele, legile etc.)

ca se asocia și funcționa în grupuri sociale.

Elemente relevante pentru definirea și selectarea competențelorcheie:

CC sunt multifuncționale,

CC sunt transversale în raport cu domeniile sociale (variatele sectoare ale vieții umane),

CC se referă la o complexitate mentală de nivel înalt,

CC sunt În acest context s-a impus să se caute răspunsuri fundamentate nu numai la ce competențe ar fi necesare pentru toți membrii societății, ci și din ce ar trebui să consiste

aceste competențe, care, asa cum se marcase la Consiliul de la Lisabona, trebuiau elaborate în perspectiva educației continue.

În martie 2000, Consiliul European lansase la Lisabona un document de strategie prin care se fixa ca finalitate a Uniunii Europene realizarea celei mai competitive și dinamice economii bazate pe cunoastere, capabile să susțină o crestere economică cu mai multe și mai bune locuri de muncă și cu o mai mare coeziune socială. Educației europene îi revenea sarcina de a se adapta la provocările noii societăți, solicitarea expresă a Comisiei fiind elaborarea unui cadru european pentru definirea noilor deprinderi fundamentale (basic skills) de format prin educație

continuă (lifelong learning).

Acest cadru de referință trebuie să acopere:

tehnologiile informatice și comunicaționale,

cultura tehnologică,

limbile străine,

educația antreprenorială,

deprinderile sociale.

În 2002 Consiliul European adoptă la Barcelona un program de lucru detaliat pentru atingerea acestor obiective până în 2010, realizând și o extindere a listei de deprinderi fundamentale:

literacy and numeracy foundation skills (a sti să scrie și să socotească deprinderi de bază),

basic competences in mathematics, science and technology (competențe de bază în matematică, stiințe și tehnologie),

ICT and use of technology (TIC și folosirea tehnologiei),

learning to learn (a învăța să învețe),

social skills (abilități sociale),

entrepreneurship (abilități antreprenoriale),

general culture (cultură generală).

Comisia a stabilit grupe de experți pentru fiecare arie problematică; grupul de lucru pentru CC a început să lucreze în 2001, principalul obiectiv fiind “identificarea și definirea noilor deprinderi și cum ar putea fi integrate mai bine în curriculumuri, menținute și achiziționate dea lungul vieții” (Key Competences for Lifelong Learning, 2004).

Prin primul său Raport (febr.2002) Grupul de lucru CC introduce un cadru de referință cu opt CC, având corelate cunostințele, deprinderile și atitudinile corespunzătoare, construit pe bazaurmătoarelor principii directoare:

Cadrul de referință este prima încercare la nivel european de a alcătui o listă cuprinzătoare si echilibrată de CC necesare împlinirii personale, incluziunii sociale și profesionale în societatea cunoasterii. Scopul lui este să servească drept instrument de referință pentru decidenții în politicile educaționale și pentru cei responsabili de crearea oportunităților de învățare la toate stadiile de educație continuă.

Termenii „competență” și „competențăcheie” sunt preferați față de „deprinderi fundamentale/ de bază” care a fost considerat prea restrictiv. „Competența” se referă la o combinație de deprinderi, cunostințe, aptitudini și atitudini; totodată ea include dispoziția de

a învăța.

Definind „competența” în termeni largi, nu este posibil și nici relevant ca în cele mai multe

domenii de competențe să facem distincția dintre „nivelele de bază” și cele „superioare” de dezvoltare ale unei competențe.

Măsurarea nivelului de formare a celor mai multe dintre aceste competențe este destul de limitat. În lumina celor de mai sus, Cadrul European de Referință pentru CC în educația continuă formulează următoarea definiție a CC pe care o considerăm concluzia.

Definiție „ansamblul multifuncțional transferabil de cunostințe deprinderi și atitudini de care toți indivizii au nevoie pentru împlinirea și dezvoltarea personală, pentru incluziune și muncă. Ele ar putea fi dezvoltate până la finele scolarizării obligatorii sau a formării, și ar putea acționa ca fundament pentru învățarea ulterioară ca parte a educației continue” (Key Competences, 2004, p.6).

Progresele realizate în definirea conceptelor de „competență” și „competențăcheie” fac posibilă o analiză fundamentată a procesului instructiveducativ desfăsurat în instituțiile de învățământ, cu relevarea modalităților de abordare a unui curriculum bazat pe competențe, având în vedere toate implicațiile unei astfel de viziuni. Paradigma educațională tradițională a intrat însă atât de adânc în modul de a gândi educația încât sunt deja ani buni de când pe toate meridianele pedagogice se resimt eforturile cercetătorilor, instituțiilor, decidenților și practicienilor de a găsi răspunsul cel mai promițător la întrebareacheie: „Cu ce să începem?”.

Documentele UE oferă jaloane orientative pentru activitatea cadrelor didactice care fac primii pasi spre centrarea pe elev. Un exemplu: „… În cadrul acestei abordări, activitatea didactică este centrată pe elev, iar rolul cadrului didactic este de a organiza sarcinile legate de rezolvarea problemelor, de a ghida înțelegerea elevilor și de a sprijini proiectele bazate pe învățarea prin colaborare.

Îndeplinind acest rol, profesorii îi ajută pe elevi să creeze, să implementeze și să evalueze proiecte și soluții. Abordarea implică și o structurare diferită a colectivului de elevi. Orarul și structura clasei sunt mai dinamice, elevii lucrând în grupuri, pe perioade mai lungi de timp. Pentru a ghida elevii astfel încât acestia să înțeleagă conceptele cheie, profesorii vor utiliza instrumente tehnologice cu aplicativitate largă, specifice diferitelor discipline – simulări, proiecții, vizualizări în domeniul stiințelor, instrumente de analiză a datelor în domeniul matematicii, jocuri de rol în domeniul stiințelor sociale….” (Standarde de competență în domeniul TIC pentru cadrele didactice (SCCDTIC) Module de standarde de competență. UNESCO, 2008)

Centrarea pe învățare/elev

Centrarea pe învățare/pe elev „cuplează” focalizarea pe caracteristicile individuale ale elevului (ereditate, experiență, background cognitiv, afectiv, psihomotor, interese, nevoi, perspective) cu focalizarea pe strategiile/tacticile și tehnologiile educaționale cele mai eficiente pentru asigurarea unui înalt nivel al motivației în construirea cunoasterii pentru fiecare elev.

În literatura domeniului cele două componente apar mai întâi în calitate de paradigmeindependente a) Centrare pe învățare, și b) Centrare pe elev (CPE) – fiecare având attribute specifice.

Elementele caracteristice pentru Centrare pe învățare:

Elevii îsi construiesc cunoasterea, realizează sintetizarea informației și integrării ei în deprinderile generale de cercetare, comunicare, gândire critică, rezolvare de problem s.a.m.d.

Accentul se pune pe utilizarea capacității de a comunica eficient pentru a aborda problemele și ariile emergente în contexte reale.

Rolul profesorului este de antrenor și mediator.

Profesorul și elevii evaluează împreună învățarea.

Predarea și evaluarea sunt întrețesute.

Evaluarea este folosită pentru a promova și a diagnostica învățarea.

Accentul se pune pe generarea unor teme mai bune și a unei învățări fără erori.

Învățarea dorită este evaluată direct prin lucrări, proiecte, performanțe, portofolii s.a.

Abordarea este compatibilă cu o investigare interdisciplinară.

Profesorul și elevul învață împreună. (După: Huba, Mary E. & Freed. Jann E. 2000)

Alte studii/organisme/instituții detaliază anumite paliere ale ariei “centrare pe elev/student”; astfel, Consiliul Facultăților din Arizona, definind acest concept, îi enumeră drept specific (dar nu îl limitează la ele) următoarele practice educaționale:

Învățarea colaborativă în grup, în ora de curs și în afara ei;

Cercetarea și descoperirea individuală (a studentului); Cercetarea și descoperirea realizate împreună (de student și facultate);

Învățarea prin activitati bazate pe definirea unor probleme;

Învățare asincronă la distanță;

Învățare interactivă sincronă la distanță;

Activități de învățare prin exersare (Handson);

Experiențe la fata locului (“onsite field”);

Tutoriale autoreglabile (selfpaced)2

Poziții de luare în evidență a unor caracteristici ale elevilor pot fi urmărite până în

antichitate, dar abia în secolul trecut începe să se prefigureze conceptul de „centrare pe elev” în opoziție cu „centrarea pe profesor”: Carl Rogers, promotorul lui „client centered counseling” (consiliere centrata pe client), introduce această abordare în teoria educației, dar i se asociază și poziții ale altor pedagogi sau psihologi – Frobel, Piaget, Malcom Knowles.

Abordată de pe diverse poziții (filosofice, psihologice, sociopedagogice, instituționale, empiriste, pragmatice etc.), problematica CPE dinamizată, pe de o parte, de rezultatele cercetărilor de psihologie și psihofiziologie si, pe de altă parte, de posibilitățile/ strategiile noi apărute în zona de intersecție omcomputer – reprezintă un evantai larg de fațete, cu specificități „locale”, dar și cu trăsături comune.

Din literatura domeniului se desprind următoarele trăsături caracteristice generale ale CPE:

participarea activă a elevilor/studenților (e/s) la construirea propriei cunoasteri;

e/s îsi construiesc cunoasterea pe baza cunostințelor și deprinderilor avute;

e/s înțeleg expectanțele și sunt încurajați să folosească autoevaluări ale progresului propriu;

e/s lucrează în colaborare;

e)e/s decid asupra componenței grupurilor și a modului de lucru

e/s îsi monitorizează propriul demers de învățare pentru a înțelege cum se construieste cunoasterea și pentru asi dezvolta strategii de învățare;

e/s au o motivație intrinsecă pentru atingerea scopurilor pe care și leau propus;

activitatea e/s reprezintă o învățare autentică;

pentru e/s învățarea reprezintă o căutare activă a sensului;

profesorii recunosc existența unor stiluri diferite de învățare;

k)profesorii îi ajută pe e/s să depăsească dificultățile formulând întrebări pentru ai orienta spre soluția corectă.

Puse în fața eficienței scăzute a învățământului tradițional cu centrarea pe profesor/pe predare, unele state au întreprins acțiuni de amploare pentru a reorienta politicile educaționale și practica scolară. Astfel, în anii ’90, American Psychological Association în parteneriat cu Midcontinent Regional Educational Laboratory elaborează, la cererea Presedintelui SUA, un important studiu – LearnerCentered Psychological Principles: A Framework for School Redesign and Reform (Principiile psihologice ale centrării pe student/Cadru pentru redefinirea scolii și reformă).

Principiile enunțate în acest studiu reprezintă o viziune ideală bazată pe experiența acumulată și integrează rezultatele pertinente din mai multe domenii ale psihologiei (psihologia clinică, experimentală, socială, organizațională, a dezvoltării umane), educației, sociologiei, antropologiei și filosofiei.

Prima formă (1993) cuprindea 12 principii; în 1997 apare o formă revizuită cu subtitlul

„Revision prepared by a Work Group of the American Psychological Association’s Board of Educational Affairs (BEA)” în care numărul principiilor ajunge la 14; ele se referă la elev și la procesul de învățare, relevând factorii interni care țin de elev și sunt sub controlul acestuia, dar țin cont și de factorii externi (de mediu sau context) care interacționează cu factorii interni.

Studiile și rapoartele de cercetare publicate în ultimii ani scot în evidență un evantai extreme de larg de abordări concrete ale CPE la nivelul practicii educaționale – comparativ cu centrarea pe profesor structura specifică a demersului, controlul demersului de învățare, (auto)evaluarea, motivația învățării, construirea cunoasterii, autonomia e/s, interacțiunea e/sprofesor, stilul de învățare, metacogniția, specificitatea softului educațional, rolul consilierului scolar, regândirea pregătirii viitoarelor cadre didactice și a managerilor etc.

Transpunerea acestor principii în practica educațională presupune un ansamblu de măsuri extrem de complex, plurinivelar, implicând decizii la nivelul politicii educaționale, curriculumului, mijloacelor de învățământ si, mai ales, reprofesionalizării psihopedagogice a educatorilor intr-o viziune în concordanță cu capacitățile solicitate de activitățile specifice noilor roluri.

Din aceste studii și rapoarte rezultă că CPE reprezintă o abordare eficientă (S.J. Lea et alii, 2003); în acelasi timp, se subliniază faptul că principiul individualizării nu poate merge la extrem, întrucât nu poate fi creată o abordare specifică pentru cazuri unice (B. Simon, 1999)

Eficiența procesului de instruire

Nici un educator nu seamănă cu altul, nici o clasă nu seamănă cu alta, nici o lecție nuseamănă cu alta. Cui, cărui fapt, cărui moment, demers sau instrument îi atribuim eficiența lecției/ a procesului educațional?

Un răspuns „atoatecuprinzător” este greu de formulat, pentru că fiecare educator îl va avea pe al său, determinat de particularitățile contextului în care lucrează, precum și de propria viziune pedagogică. Mai mult, criteriile pot varia în dependență de scopul urmărit, precum și de alte variabile. Bogata literatură a domeniului scoate în evidență diversi factori care, în anumite condiții, sporesc eficiența instruirii. Analiza acestor studii / cercetări a permis relevarea unor elemente / jaloane / principii care ar trebui avute în vedere / respectate în proiectarea unei instruiri eficiente. Sar putea spune că aceste principii reprezintă un gen de standarde instrucționale de cea mai largă generalitate pentru proiectarea și evaluarea activităților din procesul educațional. (Le redăm sintetic după: Astleitner, H. Principles… 2005.)

Principiul 1

Orientarea spre o învățare reflectivă / reflexivă. În decursul instruirii elevului / studentului (e/s) trebuie să i se ofere posibilitatea de a reflecta asupra învățării. Învățarea reflexivă reprezintă un proces activ de construire a cunoasterii, prin care conținutul memoriei (mediat de procesele gândirii) se transformă, se lărgeste, se conectează, se structurează sau se creează. Acest

obiectiv poate fi atins prin realizarea caracteristicilor fundamentale ale unei bune instruiri:

implementarea unor metode neperturbatoare;

respectarea unui ritm adecvat al instruirii și o secvențiere care să ofere e/s și educatorilor timpul necesar pentru a gândi și a pune întrebări;

prezentarea conținutului și sarcinilor de o manieră organizată și clară;

varierea metodelor de instruire dea lungul diferitelor faze ale instruirii;

focalizarea consecventă a instruirii pe obiectivele predării și oferirea posibilităților de exersare;

luarea în considerare a diferențelor individuale și a progresului în învățare;

stabilirea unui climat socioemoțional adecvat între e/s și educator.

Principiul 2.

Suport multiplu în plan cognitiv, motivațional și emoțional. O instruire bună nu numai că îi ajută pe e/s în gândire și învățare, ci îi și motivează și le oferă un context emoțional adecvat.

Instruirea produce efecte cognitive dacă sunt definite obiectivele, dacă este activată cunoasterea anterioară, dacă este prezentat un conținut stimulativ, dacă procesul de învățare este ghidat, feedbackul la sarcină este dat, progresul în învățare este evaluat și transferul cunoasterii este garantat. Instruirea îi motivează pe e/s dacă atenția este trezită, dacă relevanța conținutului este evidențiată, autoîncrederea întărită, satisfacția față de rezultatele învățării este obținută.

Principiul 3.

Luarea în considerație a particularităților individuale ale e/s. Instruirea și evaluarea achizițiilor sunt deosebit de eficiente dacă e/s sunt asistați în relevarea particularităților individuale si, în plus, când sunt ajutați săsi elimine lipsurile. E/S sunt mai performativi în învățare dacă instruirea se adaptează la particularitățile lor.

Principiul 4.

Achiziția și aplicarea cunoasterii în contexte variate. Instruirea scolară este focalizată de la bun început pe însusirea fundamentelor: cunostințe declarative (concepte, fapte) și procedurale (reguli) care trebuie să devină o parte a memoriei e/s în modele corecte, structurate și interconectate. Pentru a putea fi folosită flexibil această cunoastere, este necesară o aplicare și evaluare repetată în situații practice. Astfel de situații/ cazuri trebuie să varieze în dificultate, în corespondența lor cu cazurile reale și în nivelul ghidării.

Principiul 5.

Dezvoltarea și evaluarea cunostințelor fundamentale, dar și stimularea operațiilor superioare ale gândirii (higherorder skills). Cunostințele fundamentale trebuie prezentate cu exemple ilustrative, împreună sarcini de rezolvat și soluții. Procesele de gândire analitică sunt stimulate când e/s este solicitat să descompună elementele (de conținut disciplinar), să le compare, să le evalueze și să le explice. Gândirea creativă poate fi susținută când e/s i se cere săsi imagineze elemente ale cunoasterii și să dezvolte produse proprii. Gândirea analitică și cea creativă pot fi antrenate prin activitati de rezolvare de probleme constând din descoperirea/relevarea problemei (care este problema aici?), definirea problemei (care sunt componentele problemei?), formularea unei strategii de rezolvare, alocarea resurselor (de ce avem nevoie pentru rezolvare?) și evaluarea soluției.

Cunostințele, gândirea și capacitatea de a rezolva problem trebuie să reprezinte o parte integrată a evaluării achizițiilor.

Principiul 6.

Stimularea capacităților argumentative. Pentru o argumentare reusită este necesară identificarea, construirea și evaluarea argumentelor. Metodele de instruire care susțin argumentarea: activitățile de grup cu proceduri structurate, listările pro și contra (de ex., avantaje și dezavantaje), chestionarele privind cunostințele (de ex., ce cunostințe sunt disponibile, ce s-a învățat?), sintetizarea (de ex., ideea principală a unui text), fisele de lucru pentru stimularea gândirii, dezbaterile pe o problemă controversată, învățarea problematizată, organizatorii grafici.

Principiul 7.

Proiectarea și ghidarea învățării autocontrolate. Prin autocontrolul învățării se înțelege că e/s îsi controlează / reglează acest proces în raport cu obiectivele date și că îsi selectează activitățile pentru a ameliora rezultatele. Totusi, pentru o învățare autocontrolată reusită, e/s trebuie să dispună de strategii de învățare generale și specifice care pot fi învățate din lecțiile la diferite discipline (de ex., luare de note, deprinderi de învățare, memorare, învățare colaborativă, managementul proiectului, prezentarea rezultatelor).

Principiul 8.

Sporirea eficienței învățării. Eficiența învățării reprezintă raportul dintre resursele / eforturile investite și rezultatele obținute. Învățarea de mare eficiență apare când e/s lucrează cu sarcini provocatoare, dar fără săi supraîncarce; astfel de sarcini țin de cunoasterea precedentă, dar solicită și cunostințe sau deprinderi noi.

Principiul 9.

Trezirea și menținerea interesului. E/S sunt interesați când cred că reprezintă o parte importantă a grupului sau când demonstrează competență intr-un domeniu, când pot săsi definească propriile obiective sau când pot lucra protejați de compararea cu alți e/s. În ceea ce priveste conținutul disciplinar, trebuie săi fie ilustrată importanța pentru viața și scopurile urmărite de e/s.

Principiul 10.

Intensificarea sentimentelor pozitive. Simpatia între e/s poate fi sporită prin diverse strategii, cum ar fi: intensificarea relațiilor, promovarea unor interacțiuni, stabilirea unor structuri de învățare cooperativă și implementarea unor programe de colaborare. Plăcerea poate fi sporită prin prefigurarea unor evenimente, realizarea unor oportunități/ materiale pentru studiul individual, utilizarea umorului sau a jocurilor educative bazate pe simulare.

Principiul 11.

Diminuarea sentimentelor negative. Pentru a diminua teama, invidia și supărarea apărute în timpul instruirii – pot fi folosite diverse strategii: asigurarea succesului în învățare, acceptarea greselilor, folosirea momentelor de relaxare (pentru a diminua teama); încurajare comparației prin referință la cadrul autobiografic sau criterial și nu la standardele sociale, instaurarea unei evaluări și notări consistente și transparente, evitarea privilegiilor (pentru diminuarea invidiei); stimularea controlului supărării, exprimarea / rezolvarea supărării de o manieră constructivă, neacceptarea niciunei forme de manifestare a supărării.

Principiul 12.

Instaurarea respectului și responsabilității. Scoala are misiune de a forma la e/s

deprinderi generale de comportament social, bazate pe respect și responsabilitate pentru / față de ceilalți, mediu, societate, în general. Astfel de valori și atitudini corelate pot fi obținute dacă se creează anumite condiții: crearea unei comunități ai cărei membri au grijă unul de altul, folosesc reguli democratice în luarea deciziilor, răspunzând la întrebări privind dezvoltarea propriei personalități, integrând subiecte controversate în predare.

Principiul 13.

Utilizarea materialelor de autoinstruire. Pentru a susține o învățare autocontrolată este nevoie de materiale speciale, care dispun de o argumentare a rațiunii pentru care ar trebui studiate, o descriere a precunoasterii necesare pentru a înțelege conținutul nou și modul în care va fi însusit, o consecventă orientare spre obiectivele învățării, o structură clară a conținutului, sarcini de lucru care permit e/s săsi testeze cunoasterea, o ghidare a învățării prin întrebări și informații marginale, pre și postorganizatori tematici, un fond de exerciții variate ca dificultate împreună cu soluțiile lor (complete, incomplete sau multiple), ilustrații care contribuie la înțelegerea conținutului, precum și atribute ale textului care facilitează căutarea, organizarea și integrarea cunoasterii.

Din specificitatea elementelor prezentate ce concluzii se pot trage cu privire la caracteristicile instruirii eficiente?

eficientă

Instruirea eficientă poate fi surprinsă, conceptualizată în cadrul de referință al

pedagogiei (stiințelor educației), atributele ei putând fi promovate/preluate creativ în practica scolară.

Instruire eficientă reprezintă rezultatul atât al cunoasterii de care dispune educatorul, cât și al artei/abilității de a folosi o strategie/ o metodă/ un procedeu la

momentul oportun și la o situație dată.

Demersul instruirii îi solicită educatorului să ia decizii, evaluând obiectiv situația și valorificândusi competența profesională și resursele de care dispune.

Educatorul trebuie săl considere/vadă pe e/s ca o persoană autonomă, cu particularități care îl diferențiază de ceilalți

Utilizarea tehnologiei informației și comunicațiilor(tic) în procesul educațional

Documentele menționate fac parte din principalele răspunsuri la provocările societății cunoasterii. Numeroase colective de specialisti, institute de cercetare, organizații și grupuri adhoc încearcă să prefigureze direcțiile de dezvoltare ale societății și să construiască/proiecteze/descopere imaginea unui proces educațional acoperind întreaga perioadă de viață a individului – educația continuă (long life education) care să poată facilita integrarea în societate, proces fundamentat pe datele oferite de stiințele educației și în a cărui desfăsurare să poată fi folosit întregul evantai al tehnologiei informației și comunicațiilor. Din datele confirmate prin cercetare și practica scolară utilizarea TIC favorizează procesul de învățare prin următoarele atribute:

Prin activitățile provocatoare multisenzoriale, multidisciplinare utilizarea TIC îi motivează pe elevi; sunetul, culoarea, miscarea stimulează registrul senzorial, amplificând tonusul atenției și facilitând menținerea informației în memoria de lucru / de scurtă durată.

Oferă acces la resurse informaționale din afara clasei, scolii, disciplinei, culturii specifice, ariei geografice, momentului istoric etc.

Prin recurgerea la imagini, sunete, animații, simulări, se facilitează înțelegerea / achiziția unor concepte abstracte.

Activitatea de căutare a surselor de informații stimulează curiozitatea, explorarea și cercetarea, favorizând formularea de ipoteze și de teme / subiecte / probleme de investigare proprie.

Prin interacțiunea personală cu softuri educaționale specifice se oferă posibilitatea exersării individuale și individualizate necesare pentru formarea unor deprinderi, atingerea unor nivele performative/standardizate, recuperarea unor segmente instrucționale, revederea unor capitole/ teme din propria arie curriculară sau a altei discipline etc.

Prin diversele interacțiuni colaborative în rezolvarea unor probleme / sarcini de lucru / proiecte etc. se facilitează procesul de asimilare a cunoasterii

Totodată, noile tehnologii pot contribui la o sporire semnificativă a eficienței procesului educațional prin posibilitățile de pregătire/ perfecționare/ reprofesionalizare pedagogică pe care le oferă cadrelor didactice active sau în curs de formare. Referitor la această problemă este necesară sublinierea unei concluzii comune, de primă importanță, rezultată din cercetările efectuate pe diverse meridiane geografice: dotarea unităților scolare cu TIC nu conduce automat la sporirea eficienței procesului educațional; nici inițierea computerială a cadrelor didactice, necesară (ca punct de plecare), nu este suficientă. Pentru a obține rezultate superioare unei predări tradiționale (chiar și folosind TIC) se impune o proiectare a acestui proces (de învățare) folosind potențialul specific al tehnologiilor, adecvat strategiilor respective. Cercetările menționate și observațiile cumulate conduc la o imagine evolutivă, cu diferențierea a cinci niveluri de integrare/asimilare și utilizare performativă a TIC în procesul educațional:

primul nivel: utilizarea punctiformă a unor echipamente,

al doilea nivel: integrarea (justificată) în predarea tradițională,

al treilea nivel: modificarea metodei de predare în dependență de TIC,

al patrulea nivel: modificarea rolului profesorului,

al cincilea nivel: proiectarea procesului plecând de la un model/o teorie pedagogic(ă), selectată în raport cu obiectivele curriculare.

Atât pentru a promova și facilita, cât și a pentru a armoniza procesul de pregătire si reprofesionalizare pedagogică a cadrelor didactice, proiectul UNESCO "Standarde de competență în domeniul TIC (SCCDTIC)" elaborează în 2008 sub acest titlu comun trei documente:

Cadru pentru politici educaționale,

Module de standarde de competență,

Recomandăripentru implementare.

Plecând de la premiza conform căreia intr-un mediu educațional modern și eficient, tehnologia le dă elevilor posibilitatea:

să devină capabili să utilizeze tehnologiile informației sicomunicațiilor,

să caute, să analizeze și să evalueze informații,

să rezolve probleme și să ia decizii,

să utilizeze în mod creativ și eficient instrumente specifice productivității,

săcomunice, să colaboreze, să editeze și să creeze,

să devină cetățeni informați, responsabili și implicați, autorii au considerat că "personajul" cheie care îi ajută pe elevi săsi dezvolte aceste abilități este cadrul didactic.

De aici decurge și necesitatea ca toți profesorii să fie pregătiți să desfăsoare astfel de activități cu elevii lor "Atât programele de dezvoltare profesională a cadrelor didactice, cât și programele de pregătire a viitoarelor cadre didactice trebuie să conțină numeroase experiențe legate de tehnologii în toate aspectele formării". In acest spirit au fost elaborate standardele și resursele în cadrul acestui proiect; ele oferă îndrumări în special pentru planificarea programelor și a ofertelor de formare pentru a îndeplini un rol esențial în dezvoltarea abilităților de utilizare a tehnologiilor.

Proiectul SCCDTIC oferă (în această primă fază) un cadru complet pentru standardele de competență ale cadrelor didactice în domeniul tehnologiilor informației și comunicării prin:

referiri la cadrul politicilor care stau la baza acestora (Cadru pentru politici educaționale),

examinareacomponentelor reformelor educaționale și elaborarea unor seturi de competențe pentru cadrele didactice care să corespundă diverselor abordări la nivel de politici și componentelor reformelor educaționale (Module de standarde de competență),

o descriere detaliată a competențelor specifice care trebuie dobândite de cadrele didactice în cadrul fiecărui modul (Recomandări pentru implementare). În încheierea acestui prim capitol se impun și câteva clarificări/ discriminări /precizări privind termeni/concepte care în literatura de specialitate dispun de atribute ce diferă de la un autor la altul; aici ne vom mărgini doar la sintagma "tehnologiile informației și comunicațiilor (TIC).

Sintagma "tehnologia informației și comunicațiilor (TIC)", în sensul cel mai larg, acoperă facilitățile și echipamentele de tipul computerelor, telefoanelor (inclusiv, cele mobile), removable media, radioul sau alte echipmente comunicaționale de înaltă frecvență, televiziunea, dispozitivele digitale sau analogice de înregistrare (inclusiv DVD și video), camerele de filmat, fotocopiatoarele, imprimantele (sau alte aparate de acest gen), rețelele electronice, internetul, posta electronică și

serviciile web (Adaptare după: University of Southern Queensland, Division of ICT Services. (Standard) ICT Glossary and Definitions (2008).

Un alt plan al discriminărilor conceptuale derivă din interpretarea relațiilor dintre cele două componente (atribute specifice) ale sintagmei „informației” / „comunicațiilor”; cele două ipostaze, reprezentate grafic, pun în lumină două modalități diferite de a identifica o tehnologie.

Proiectarea softului educațional – considerați generale

Proiectarea unui SE presupune mai multe etape ce diferă prin caracterul activității grupurilor de specialisti implicați în acest proces. Prima etapă o reprezintă proiectarea pedagogică (design educațional), moment în care se defineste și se concretizează o anumită strategie educațională. În cea de a doua etapă, cea de realizare informatică/grafică/interfață, această strategie este transpusă intr-un program de instruire (SE), având toate caracteristicile funcționale solicitate prin proiectul pedagogic.

Proiectarea pedagogică recomandări generale – jaloane

Diversitatea tipurilor de soft “educational precum și specificitatea demersurilor/ strategiilor/căilor prin care proiectantul îsi propune săl conducă pe elev spre atingerea obiectivului propus, permit doar recomandări generale; concretețea opțiunii proiectantului în ceea ce priveste tipul de soft pe care doreste săl realizeze va determina respectarea și a altor elemente din panoplia stiințelor educației. Pentru a evita ambiguitățile textului am luat aici ca “numitor comun” softullecție. La câteva din celelalte categorii ne vom referi în cel de al doilea subcapitol.

Înainte de a trece la subiectul enunțat se impune să atragem atenția asupra diferențelor, ca “locus” (de rulare a SE), existente între un computer (desktop), laptop, notebook, platformă s.a. (în dezvoltare) si, în special între computerul individual și platforme, întrucât ultimele sunt construite după un model care impune respectarea unor condiții proprii.

În acelasi timp, considerăm că în momentul în care ați luat hotărârea de a proiecta un soft educațional și deja gândiți la modul în care veți proceda, ar fi util să mai aruncați o privire spre bogată arie a tehnologiilor care ar putea deveni suportul tehnic al unui soft educațional și alegețil pe cel corespunzător scopului urmărit, mai ales dacă doriți să proiectați un SEI a cărui utilizare să nu depindă de existența unei platforme.

Recomandările generale vizează atât elementele din aria pedagogiei, cât și cele din ariile disciplinare, comunicaționale, evaluare, feedback, funcționale.

Aria pedagogică:

Proiectați un SE numai dacă intenția dv. este motivată. Ce avantaje pentru elevi ar aduce în procesul educațional?

Primul pas ar trebui săl constituie o verificare a cunoasterii grupuluițintă. Puteți enumera trei caracteristici ale populației de elevi cărora le este adresat softul dv.?

Utilizarea computerului nu mai poate reprezenta în sine o motivație pentru elev. Ce tehnici motivante ați gândit să folosiți?

Interacțiunea îi oferă elevului oportunități pentru a reacționa la un conținutdisc iplinar. Cum gândiți să variați interacțiunea și să asigurați frecvența ei? O puteți realiza corelată/ dependentă de obiectiv?

Combinarea a două sau mai multe obiecte media (text, video imagini, audio) pentru a da forma de exprimare a unui conținut poate asigura înțelegerea mai bine decât un text. Când aveți posibilitatea să folosiți diferite combinații, cum vă decideți să procedați?

Aria disciplinară:

Conținutul trebuie să coreleze/susțină/acopere obiectivele curriculumului pentru elevii vizați. Obiectivele softului pe care doriți săl proiectați sunt definite operațional? Pe baza lor pot fi elaborate instrumente de evaluare?

Descrieți prerechizitele, atât cele referitoare la conținutul disciplinar, cât și cele computeriale.

Informația disciplinară trebuie să corespundă cu obiectivele, să fie completă, detaliată la nivelul obiectivelor, să folosească terminologia acceptată.

Structurați informația disciplinară de o manieră logică*, dar când veți opta pentru o anumită strategie uneori va trebui să constatați că o structură “logică” a informației disciplinare nu corespunde cu structura demersului pe care îl proiectați.

Comunicare/ format:

Limbajul folosit să corespundă nivelului de pregătire a elevului și adecvat conținutului. Nu folosiți termeni tehnici decât dacă sunt relevanți pentru conținutul disciplinar.

Utilizați o formatare standardizată: facilitează preluarea și înțelegerea informației.

Imaginea de suprafață/ interfața vizibilă:

Fiți constienți de importanța imaginii de pe ecran: este “lookul” softului.

Nu îngrămădiți ecranul: el trebuie să fie un suport al învățării, nu un distractor!

Aveți un inventar de modalități de atragere a atenției asupra unor anumit informații?

Folosițile de o manieră uniformă.

În modul de prezentare (texte, grafice, imagini fixe/animate, audio, video) care susține învățarea culorile sunt folosite adecvat? (De ex., Rosul și albastrul, fiind la extremele spectrului vizibil, sunt culorile cele mai dificil de perceput!)

Cum ați gândit controlul pe care elevul îl va avea programului? În afară de reacțiile determinate de parcurgerea “standard” a programului, se oferă și un control funcțional – întreruperea (cu reluare amânată), întoarcerea la o secvență parcursă, accesarea unui “help”, vizualizarea distanței parcurse.

Modul în care se încheie interacțiunea cu softul are un impact important asupra elevului.

Cum credeți că veți rezolva această secvență pentru a amplifica impactul pozitiv asupra elevului?

Evaluarea:

Este important să diferențiem evaluarea “formativă” /pe parcurs (constatarea momentului care se află elevul în învățare/ construirea cunoasterii, pentru a regla acest proces/ interacțiunea) de evaluarea “sumativă” prin care se marchează nivelul de performanță (în raport cu obiectivul curricular) reusit de elev.

Ar fi util să încercați a construi itemii de control / evaluare formativă de o manieră gradată, luând ca scală ierarhică secvențe din taxonomia BloomAnderson.

Nu uitați: evaluarea formativă se face dea lungul întregului demers (în cazul dat: parcurgerea softului).

Feedbackul. După reacția elevului la sarcina de lucru formulată în soft programul trebuie să ofere căi în dependență de specificitatea obiectivelor urmărite corectitudinea răspunsului, atragerea atenției asupra modului de rezolvare (cu trimiterea la o sarcină similară), stimulare prin remarcarea progresului, ajutor pentru înțelegerea sarcinii de lucru, evaluare etc.

Proiectarea pedagogică –detalieri

În acest subcapitol ne vom opri la câteva din elementele pe care trebuie să le stăpânească un adevărat designer și dezvoltator; de stăpânirea și utilizarea lor adecvată scopului stability depinde în mare măsură eficiența softului/ procesului proiectat.

Eficiența unui soft educațional depinde și de obiectele multimedia din care este alcătuit. Grafice, diagrame, hărți, template, organizatoare de diverse feluri toate aceste obiecte pot fi

interactive și pot spori implicarea elevului. Vestea bună este că o diversitate extremă de astfel de structuri există pe net.

Organizatori grafici

Organizatorul grafic (OG) este un instrument de comunicare vizual care evidențiază relațiile dintre fapte, termeni, idei. Diversitatea formelor de relații a generat un larg evantai de OGi, structurate pe grupe in dependență de tipul relației sau de specificitatea domeniului de aplicare.

În procesul educațional tradițional OGi sunt folosiți îndeosebi în prezentarea de către profesor a conținutului disciplinar; valoare lor deosebită apare intr-un demers de construire a

cunoasterii, atunci când informația nouă este reprocesată intr-un context care o corelează cu elemente deja însusite, sau de dirijare a reprocesării.

După cum se subliniază intr-o recentă lucrare autohtonă (Joița, Elena. Formarea

pedagogică a profesorului. Instrumente de învățare cognitivistconstructivistă. Bucuresti: EDP, 2007, p.2122) "Organizatorii grafici scot în evidență moduri de prezentare a diferitelor relații între termeni, idei, concepte, factori, cauzeefecte intr-o problemă care trebuie cunoscută rațional, cum se vizualizează procesarea informațiilor (cognitivism). Iar reprezentarea grafică este imaginea globală, de ansamblu a problemei, ca produs final, ca artifact (construcționism) al construcției

înțelegerii respectivei sarcini, problema. […] Subliniinduse funcționalitatea lor în raport cu construcția cunoasterii, acesti organizatori și apoi reprezentări, devin instrumente utile construirii înțelegerii, învățării independente sau în grup a studentului/elevului. "

Sub o forma sau alta, OGi pot fi folosiți la începutul procesului educațional/lecției (de ex., o hartă conceptuală din care să rezulte relația dintre componente), pe parcursul interacțiunii cu elevii (OGi în raport cu scopul urmărit) sau la finele lecției (OGi de reorganizare

/sintetizare/comparare/integrare a conținutului disciplinar. În momentul de față numeroase firme, asociații profesionale, instituții de învățământ, organizații oferă (contra cost sau gratuit) prin internet o mare diversitate de instrumente utile pentru un demers educațional având ca principală notă definitorie „construirea cunoasterii”. Pentru aI facilita profesorului selectarea celui mai potrivit OG, binecunoscuta Google ne oferă linkuri spre OGi structurați în raport cu tipul de procesare a informației: descriere, comparare/contrastare, clasificare, secvențiere, cauzală, decizională.

Aveți nevoie de un simplu tabel, de un ceas care să marcheze trecerea timpului la un test, de o diagrama de orice fel, o templată nu mai este nevoie să o faceți dumneavoastră, ea există cu siguranță pe net. O căutare pe Google și puteți găsi: Clock, Cluster/Word Web, Describing Wheel,

EChart, Fact and Opinion, Five W's Chart, Flow Chart, FourColumn Chart, Garden Gate, Goal Reasons Web, Hierarchy chart, IceCream Cone, Idea Rake, Idea Wheel, Inverted Triangle, ISP Chart, KWHL Chart, KWL Chart, KWS Chart, Ladder, Observation Chart, Persuasion Map, Planning Chart, Problem Solution Chart, Progress Report, Sandwich, Sense Chart, Sequence Chart, Spider Map, StepbyStep Chart, Story Map 1, TChart, ThinkPairShare, Ticktacktoe, Time Line, TimeOrder Chart, Tree Chart, Venn Diagram.

Dintre softurile de firmă care ne oferă gratuit posibilitatea de a le folosi graficele pentru a ne construi OGi, Google ne recomandă, printre altele Edraw Mind Map, cu multe exemple, si template.

Feedbackul în procesul educațional

Luând ca primă referință procesul educațional, un rol de feedback (pentru elev) îl poate avea orice mijloc prin care elevul este înstiințat (de profesor sau pe altă cale) despre calitatea/corectitudinea răspunsului la sarcină, reacției la un stimul. Pozitiv, negativ sau neutral, feedbackul poate fi exprimat verbal, în scris sau prin expresii faciale, gesturi sau alte căi.

Oferindui elevului informații despre o anumită acțiune și rezultatul ei raportat la un criteriu de acceptabilitate, feedbackul asigură dirijarea informației din nou către elev în asa fel încât performanța acestuia poate fi comparată cu performanța planificată.

Limitândune la aria „soft educațional interactiv”, poate fi identificat drept feedback o informație oferită de SEI în timpul interacțiunii prin care elevul este informat despre calitatea / corectitudinea reacțiilor / răspunsurilor sale la sarcinile de lucru.

În dependență de scopul urmărit, și în SEI, feedbackul poate fi imediat sau distanțat, precum și particularizat ca orientare asupra învățării. Complexitatea zonei de intersecție a evantaiului extrem de larg al tipurilor de feedback cu un alt larg evantai al variabilelor procesului educațional a trezit interesul multor cercetători dea lungul ultimelor trei decenii; prin numeroase cercetări experimentale au fost relevate date utile pentru ameliorarea demersului educațional.

Una dintre cele mai complete metaanalize a domeniului (Shute, J. Valerie. Focus on Formative Feedback, 2007) pune în lumină și relevă consistența relațiilor dintre variatele tipuri si niveluri ale feedbackului și nivelul de impact asupra învățării. Feedbackul formativ este considerat drept informația comunicată elevului, intenționată să modifice gândirea sau comportamentul elevului pentru ameliorarea învățării.

Cele câteva elemente din aria problematică a feedbackului educațional abordate sintetic în paginile acestui subcapitol încearcă să releve rolul important pe care îl are feedbackul în procesul

educațional. Se poate spune, fără a gresi, că feeedbackul reprezintă un mecanism de dirijare a învățării; o dirijare pentru a spori eficiența procesului prin orientarea eforturilor elevului spre acțiunile cele mai adecvate scopului urmărit. În pedagogie, mecanismul, specific sistemelor cu comandă și control, sia găsit o primă legiferare teoretică în paradigma behavioristă, desi în literatura domeniului este surprins în diferite recomandări. Astfel, în studiile privind o abordare a învățării în viziune constructivistă, printre alte recomandări se strecoară și unele ce presupun un mecanism de tip feedback.

Puncte de sprijin

Utilizarea unor puncte de sprijin (scaffolding) se consideră că este necesară pentru a facilita învățarea, îndeosebi la introducerea elevilor intr-o temă nouă.

Ca strategie, scaffoldingul îsi are originea în conceptul “zonei proximei dezvoltări” din teoria socioconstructivistă promovată de Lev Vîgotski. Scaffoldingul include o largă varietate de tipuri / strategii; în exemplul următor (adaptare după Beth Lewis. Scaffolding Instruction Strategies, 2010), autorul are drept cadru de referință învățământul elementar:

activarea cunostințelor deja însusite,

oferirea unui context motivațional pentru a amplifica interesul sau curiozitatea elevilor pentru tema respectivă,

fragmentarea unei sarcini complexe în pasi mai mici/accesibili,

prezentarea unui exemplu de produs asemănător celui dorit, înainte de a trece la rezolvarea sarcinii,

modelarea procesului de gândire a elevilor prin "gândeste cu voce tare",

oferirea unor hints / sugestii sau a unei soluții parțiale a problemei,

folosirea unor indicii verbale pentru a facilita răspunsurile elevilor,

învățarea de către elevi a unor cântece sau instrumente mnemonice pentru a facilita memorarea unor evenimente sau proceduri importante,

facilitarea angajamentului și participării elevilor,

prezentarea unei timeline istorice pentru a oferi contextul învățării,

utilizarea unor organizatori grafici, oferind un cadru vizual pentru asimilarea noilor informații,

ghidarea elevilor în formularea unor predicții privind rezultatele activității pe care o desfăsoară,

formularea de întrebări în timpul citirii pentru a încuraja o investigare mai profundă,

sugerarea unor strategii posibile de folosire independentă,

modelarea unei activități pentru elevi înainte ca ei să solicite să desfăsoare aceeasi activitate sau una similară,

solicitarea elevilor să contribuie cu experiența lor care corelează cu subiectul studiat. Reactivarea cunostințelor deja însusite, pe baza cărora se va continua construirea cunoasterii, poate fi structurată intr-un set anticipator, transpus intr-un organizator grafic adecvat care poate oferi căi de abordare a noului conținut disciplinar.

Procesarea cognitivă a informației

Sarcina de lucru ce însoțea Sinteza 2 solicită realizarea unor momente (ale demersului educațional, la o lecție) care să exprime / exemplifice “construirea cunoasterii” (de către elev) si rolul profesorului în crearea ambientului necesar. “Construirea cunoasterii“ reprezintă problema cheie a designului educațional, întrucât de modul în care este înțeleasă depind soluțiile la toate palierele unui proces educațional eficient.

Cadrul referențial al Proiectului PCSE îsi propune să asigure proiectarea unor instrumente care să aibă în vedere “construirea cunoasterii” ca jalon orientativ. Primul pas pentru “formatorul designer educațional” îl constituie descifrarea traseului pe care îl parcurge informația pentru a atinge nivelul de “cunoastere”, care sunt “stațiile” acestui traseu, ce se întâmplă pe acolo, ce “cutume” se practică etc.

În subcapitolul precedent, am redat (E. Joița, 2006) mecanismele evidențiate de psihologia cognitivă, structurate de o manieră care să surprindă esența procesării informației pe

„traseulînvățării”. În rândurile care urmează încercăm să completăm imaginea acestui „traseu” apropiindo de cerințele determinate de obiectivele proiectului: formarea de profesori creatori de soft pentru un proces educațional focalizat pe construirea cunoasterii. În primul rând se impune să precizăm accepția unor termeni utilizați: „procesarea informației”, „cogniție”, „procesarea cognitivă

/ a informației”.

În psihologie „cogniția” (lat. cognoscere, „a cunoaste”) se referă la procesele mentale, descriind comportamentul prin termeni de procesare sau funcții.

Scoala / direcția teoretică derivată din abordarea cognitivă, curent dominant în psihologia contemporană – cognitivismul – „a întredeschis blackboxul” behaviorismului la finele deceniului al saselea, oferind la orizont o imagine a elevului ca procesor de informație, aidoma computerului.

Traseul procesării informației începe cu prima formă de reacție a organismului uman iritabilitatea o proprietate biologică generală prin care ființele vii recepționează influențele externe și răspund la ele printro modificare internă. Ca urmare, organismul sia dezvoltat (dea lungul evoluției) sensibilitatea proprietate psihică de a recepționa și diferenția factorii externi, excitanți este „prima formă de psihic care stă însă la baza celorlalte procese superioare de relaționare a individului la mediu”.

Excitația reprezintă o modificare locală sub influența stimulului; transmiterea acestui mesaj nervos spre centrii care înregistrează aceste experiențe este realizată prin ceea ce denumim senzație. Stimulii sunt detectați și codați; în acest mod organismul poate asigura adaptarea conduitelor.

Dacă senzația constituie doar o simplă experiență constientă asociată stimulilor, percepția se află la nivelul imediat superior: ea analizează, interpretează și integrează senzațiile cu alte informații senzoriale. Ca proces mental de interpretare și organizare a senzațiilor, percepția reprezintă deja o experiență constientă asupra obiectelor și a relațiilor obiectelor.

Prelucrarea primară a informațiilor se încheie cu reprezentarea – mecanism psihic de reexprimare a informațiilor, mecanism care permite „reflectarea și cunoasterea obiectului în absența lui, dar cu condiția ca acesta să fi acționat cândva asupra organelor de simț”.

Mecanismele psihice de prelucrare primară a informațiilor – excitația ► senzația ► percepția ► reprezentarea – constituie canalul de legătură cu realitatea; pe baza experienței senzoriale oferite de aceste mecanisme, se construieste (prin modelare culturală și integrare socioculturală) intelectul un sistem superior de procese, activități, relații superioare. La acest nivel are loc o prelucrare secundară a informațiilor, specifică pentru fiecare componentă intelectului: a) gândire, b) memorie, c) imaginație.

Procesarea cognitivă abordează în viziunea sa întregul ansamblu prefigurat mai sus, dar numai în planul mecanismelor mentale de procesare a informației întrucât ea descrie comportamentul în termeni de mecanisme sau funcții proprii procesării. Aceste mecanisme ale procesării cognitive, de care depinde eficiența învățării, pot fi dezvoltate/ameliorate, fapt care le justifică termenul de „deprinderi cognitive” (cognitive skills) sau „deprinderi mentale” (mental skills).

Ele sunt acele deprinderi pe care le folosim: Să fim atenți și să reținem informația, b) să procesăm, să analizăm și să stocăm fapte și sentimente, c) să creăm imagini mentale, să citim cuvinte și să înțelegem concepte.

Cercetările desfăsurate în ultimele decenii au scos în evidență cele mai importante elemente pentru reusita învățării:

atenția,

memoria de lucru,

viteza de procesare, d)memoria de lungă durată,

procesarea vizuală,

procesarea auditivă,

logica și raționamentul.

O sintetică descriere a rolului lor în realizarea învățării (după Ken Gipson. Op. Cit.): ATENȚIA: te menține să implicat in sarcină, chiar și în prezența unui distractor. Atenția distribuită îți permite să acționezi/răspunzi la două sau mai multe solicitări în acelasi timp. NB! Inabilitatea de a sta o lungă perioadă de timp„în sarcină” sau cu sarcini multiple, de a ignora distractorii, va afecta/limita alte deprinderi cognitive, cu impact asupra învățării scolare.

MEMORIA DE LUCRU: reține informația pentru scurte perioade de timp.

NB! Învățarea suferă dacă informația nu poate fi reținută atât cât este necesar pentru a o folosesti cât este necesar.

VITEZA DE PROCESARE: ritmul în care creierul „manipulează” informația. NB! Dacă procesul este lent, se poate pierde informația din memoria de lucru înainte de a fi utilizată.

MEMORIA DE LUNGĂ DURATĂ: stocarea și regăsirea informației. NB! O MLD săracă/ restrânsă generează reacții și concluzii gresite.

PROCESAREA VIZUALĂ: abilitatea de a percepe, analiza și gândi în imagini vizuale.

Vizualizarea este crearea de imagini mentale.

NB! O vizualizare săracă afectează negativ înțelegerea unor sarcini/probleme, de ex. În matematică.

PROCESARE AUDITIVĂ: perceperea, analiza și conceptualizarea a ceea ce se aude; una din principalele deprinderi necesare pentru a învăța citirea și pronunțarea.

NB! Dacă analiza sunetelor este slabă, pronunțarea cuvintelor va fi dificilă și generatoare de erori.

LOGICĂ SI JUDECATĂ: deprinderi de a judeca, prioritiza și planifica.

NB! Nivelul scăzut al acestor deprinderi va afecta activități scolare ca problemsolvingul, învățarea matematicii.

„Traseul” pe care îl parcurge informația, domeniul principal de studiu al psihologiei cognitive contemporane îl constituie memoria (stocarea și regăsirea informației), modelul „stadial” (AtkinsonShiffrin, 1968) bucurânduse de o largă recunoastere. Conform acestui model, informația este procesată și stocată în trei stadii succesive. Desi dea lungul ultimelor trei decenii au fost elaborate modele care nuanțează/ detaliază/modifică poziții ale acestui model, în psihologia

cognitivă sau conturat câteva principii generale acceptate de cei mai mulți specialisti ai domeniului; primul dintre ele (deosebit de important pentru proiectantul de SEI!) se referă la capacitatea limitată a sistemului mental: volumul de informație ce poate fi procesată de sistem este limitat.

La nivelul registrului senzorial corpul dispune de receptori specializați care traduc o formă de energie (a excitației) în alta (electrică) recunoscută de creier. Acest proces (memorie senzorială) este de scurtă durată : sub 1 sec. pentru văz (memorie iconică), sub 5 sec. pentru auz (memorie echoică). NB! Este foarte important ca elevul să fie atent la informația din acest stadiu inițial pentru a putea fi transferată în memoria de scurtă durată.

Două căi de a facilita acest proces: a) elevul acordă mai multă atenție dacă stimulul (informația) se prezintă intr-o formă interesantă, și b) dacă stimulul activează elemente/ structure cunoscute.

În memoria de scurtă durată (MSD) denumită și memoria de lucru, informația intrată (datorită atenției acordate stimulului extern sau conexiunii cu ceva intern, cunoscut) va avea o viață scurtă (1520 sec.) dacă nu este repetată, fapt care o va face disponibilă până la 20 min.

Pentru menținerea informației în MSD două căi: organizarea și repetarea. În designul educațional se utilizează îndeosebi următoarele tipuri de organizare: a) clasificare a componentelor: parte/întreg, categorială sau conceptuală, b) secvențială cronologică; raport cauzăefect; c) relevanță idei sau criterii centrale unificatoare, d) tranzițională (conectivă) cuvinte sau fraze folosite pentru a indica schimbări calitative în timp.

O altă limită se referă la numărul de informații (unități de informații) coexistente la un moment dat în MSD. Bazânduse pe datele obținute experimental, G. A. Miller (1956) stabileste limita „7+2”, dar cercetările mai recente consideră că „5+2” se apropie mai mult de realitate. Huit suține că este necesar să relevăm informația importantă: “Dacă unii elevi pot procesa concomitent numai trei unități de informație, să fim siguri că sunt cele mai importante trei” În ceea ce priveste repetarea (rote rehearsal), se consideră că pentru a fi eficientă ea trebuie făcută după ce începe uitarea.

Memoria de lungă durată (MLD) este cel de alt treilea „lăcas”, la care, pentru a ajunge, informația din MSD trebuie să fie supusă unor procesări, dintre care cele mai des utilizate sunt subsumate ariei “elaborare”:

crearea unei imagini mentale (imaging),

localizarea (method of loci) – conectarea ideilor sau faptelor care trebuie reamintite cu elemente familiare,

cuvinte ancoră (pegword method) conectarea ideilor sau faptelor care trebuie reamintite cu cuvinte cu care au un element comun,

rime (rhyming) – informația care trebuie reamintită se structurează rimată,

litere inițiale (initial letter) – prima literă a fiecărui cuvânt dintro listă este folosită pentru a crea o frază.

Stocată în MLD, informația este supusă unei organizări structurale – declarative, procedurale sau/si imagistice, care vor facilita dezvoltarea gândirii si, în general, a întregului ansamblu de capacități umane care vor constitui notele definitorii ale personalității.

GÂNDIREA

Ca mecanism de prelucrare, interpretare și evaluare a informațiilor, cea mai importantă trăsătură distinctivă a psihicului uman, “gândirea produce modificări de substanță ale informației cu care operează […] antrenează toate celelalte disponibilități și mecanisme psihice în realizarea procesului cunoasterii” și “reintroduce propriile produse (idei, concepții, teorii) în circuitul informațional, devenind, în felul acesta, un declansator al unor noi procese intelectuale” (M. Zlate, 2006, pp. 233234)

Gândirea operează asupra informațiilor furnizate de senzații, percepții și reprezentări fiind mediată de informațiile stocate în memorie și mijlocită de limbaj și de propriile ei produse. Gândirea are două laturi:1. Latura informațională, cuprinzând: imagini, concepte, prototipuri, simboluri, modele mintale; 2. Latura operațională, cuprinzând:

operații fundamentale: analiza și sinteza, abstractizarea și generalizarea, comparația, concretizarea logică,

operații instrumentale: algoritmice, euristice, reproductive, productive și

particularizate în funcție de domeniul cunoasterii.

Aceste laturi sunt strâns legate una de alta: operațiile acționând asupra informațiilor dau nastere structurilor cognitive ale gândirii (care variază de la individ la individ în complexitate, flexibilitate, desăvârsire sau adaptivitate). Mai mult, după cum subliniază Ion Mânzat (2007) operațiile menționate „apar în perechi sau în blocuri interacționiste – analitico sintetice, abstractive concretizatoare, inductiv deductive astfel încât gândirea se miscă în toate sensurile, proprietatea de a opera simultan în sensuri opuse fiind o caracteristică a gândirii omenesti”

STRATEGII

A. Definirea conceptului

La nivelul procesului educațional pe care profesorul îl proiectează, desfăsoară si evaluează, strategia poate fi definită drept plan de acțiune pentru atingerea unui anumit scop specificând ce se va face, unde și când, pentru atingerea scopului stabilit.

Datorită marii diversități de scopuri – atât prin specificitatea disciplinară, cât și prin nivelul de complexitate – termenul de „strategie” este folosit uneori (în literatura domeniului) pentru elemente subordonate unei strategii (tactici, instrumente etc.) sau pentru arii de interferență (metode).

O strategie poate folosi diverse tehnici pentru realizarea unor demersuri (obiective imediate), folosind un instrumentariu tehnologic adecvat (material didactic, softuri, laboratoare etc.)

Ca și în arta militară, strategia se referă la scop, iar tacticile – la modul concret de acțiune. Se poate spune că strategia și tacticile fac legătura între finalități și mijloacele de realizare

După cum era de asteptat, nota definitorie extrem de largă a conceptului strategie a permis să se adune sub umbrela ei numeroase grupe de demersuri închegate după criterii diferite atât pe o axă orizontală, cât și pe cea verticală, dincolo de diferențierea dintre strategiile de predare (teaching strategies) și cele de învățare (learning strategies). Evident, fiecare poartă amprenta viziunii personale sau de apartenență, a poziției instituționale, a nivelului de instruire sau a specificului populației de elevi.

Astfel, cu referiri directe la practica scolară, în Classroom Instruction That Works (R. J. Marzano, D. J. Pickering & J. E. Pollock, 2001) este descris un ansamblu de nouă strategii eficiente, atestate prin cercetare :

Identificarea similarităților și diferențelor. Procedee eficiente pentru compararea si clasificarea itemilor: vizualizarea grafică și folosirea diagramelor Venn, a hărților conceptuale. Aplicații: compararea, clasificarea și crearea de metafore și analogii.

Rezumarea și luarea notelor. Prin relevarea esențialului și redarea intr-o formă proprie se obține o mai bună înțelegere. Aplicații: Elaborarea unui set de reguli pentru crearea unui sumar.

Antrenarea efortului și asigurarea recunoasterii. Efortul și recunoasterea reflectă atitudinile si convingerile elevilor; ei pot învăța săsi schimbe convingerile pentru a intensifica efortul. Aplicații: Încurajarea elevilor care țin un jurnal cu evidența săptămânală a eforturilor si reusitelor.

Tema de acasă și practica. Posibilitate de a extinde învățarea în afara lecției din clasă. Aplicații: Comunică elevilor dacă sarcina de lucru dată acasă este pentru exersare sau ca pregătire pentru tema viitoare.

Reprezentări nonlingvistice. Cunoasterea se prezintă în două forme – lingvistic și vizual. Folosirea ambelor forme amplifică eficiența procesului. Aplicații: Incorporează cuvinte și imagini folosind simboluri pentru a reprezenta relații.

Învățarea cooperativă. Activitatea cooperativă în grupe mici produce un efect pozitiv asupra învățării. Aplicații: Variază dimensiunea grupelor și obiectivele. Centrează activitatea pe procesare de grup, responsabilitate individuală și de grup, interdependență pozitivă, interacțiune facetoface.

Formularea/stabilirea obiectivelor și oferirea feedbackulul.

Stabilirea obiectivelor orientează direcția învățării. Aplicații: Formulează un obiectiv fundamental pentru o temă apoi încurajează elevii săsi personalizeze acest obiectiv prin identificarea ariilor de interes față de el. Realizează un feedback regulat si specific.

Generează și testează ipoteze. Cercetarea arată că pentru această strategie o abordare deductivă (predicții pe baza unei reguli generale) este eficientă. Aplicații: Solicităle elevilor să prezică ce sar întâmpla dacă un aspect al unui sistem familiar (de ex. transportul) ar suferi o modificare.

Puncte de sprijin, întrebări și organizatori cognitivi (Cues, Questions, and Advance Organizers). Din cercetare rezultă importanța acestor instrumente, prezentate înaintea experienței de învățare. Aplicații: O scurtă pauză după formularea întrebării va spori adâncimea/ calitatea răspunsurilor date de elevi. Variază stilul organizatorilor conceptuali.

Autorii subliniază că aceste strategii demonstrează o deosebită eficiență când sunt implementate în sisteme care încurajează colaborarea între educatori și elevi, precum și în care fiecare reprezintă o parte a unui ansamblu construit corespunzător. Aceste strategii sunt, de asemenea, deosebit de eficiente când sunt folosite în structurisuport (supportive environments) în care se au în vedere aspectele / necesitățile emoționale, sociale și fizice ale elevilor și în care fiecare capacitate individuală este recunoscută, susținută, dezvoltată. În încheiere se oferă o listă a lucrărilor dedicate cercetărilor recente în acest domeniu.

Pentru o facilă orientare a celor interesați (în primul rând, cadrele didactice și cercetătorii) au fost realizate diverse glosare (generale sau pe arii restrânse – disciplinare, populație scolară etc.).

Pentru cunoscătorii de limbă franceză recomandăm o utilă listă orientativă Les strategies d’enseignement et d'apprentissage cu peste 60 de strategii, în prezentare sumară, însoțită de

atenționarea "Elles ne conviennent pas forcement a tout les matieres ni a tout les personalites": www.pedagonet.com/other/STRTGIE.htm.

În literatura autohtonă, o excelentă caracterizare plastică a strategiei prin prisma didacticii o realizează cunoscutul pedagog Constantin Cucos (în: Pedagogie generală. Teoria generală a procesului de învățământ 1. Conceptul de didactică): " Strategia este un semn al raționalizării și al dorinței de reusită, de eficientizare și de pragmatizare a demersurilor didactice." În analiza strategiilor didactice, autorul se opreste și la diferitele criterii de clasificare (cu trimitere la Iucu,

Instruirea scolară. Perspective teoretice și aplicative. Iasi: Polirom, 2001):

după domeniul conținuturilor instrucționale adiacente: strategii cognitive; strategii psihomotrice; strategii afectivatitudinale; strategii mixte;

după operațiile cognitive predominante: strategii inductive (pe traiectul de la concret la abstract); strategii deductive (de la abstract la concret); strategii analogice (bazate prin translarea

unor note sau explicații de la un domeniu la altul); strategii transductive (prin apelul la raționamente

mai sofisticate de natură metaforică, eseistică, jocuri de limbaj etc.); strategii mixte (prin imbricarea

procedeelor de mai sus).

după gradul de structurare a sarcinilor de instruire: strategii algoritmice (pe bază de structuri fixe, repetitive de acțiuni mintale sau de altă natură); strategii semiprescrise (cu register largi privind libertatea de intervenție, privind schimbarea traiectelor etc.);

Fazele de dezvoltare ale unuii soft educational

În cadrul acestui material neam referit în diverse moduri la softul educațional, l-am denumit lecție interactivă, multimedia, conținut electronic, digital etc. În general lecție este, în contextul scolar, conținutul unui demers educațional de 50 de minute.

Pentru aceste «lecții» profesorul poate pregăti, folosind aplicațiile informatice puse la dispoziție în acest proiect, softuri pe care să le ruleze în clasă. El poate dezvolta unul sau mai multe softuri pentru aceeasi tema. În literatura de specialitate și în practica dezvoltatorilor un astfel de soft este denumit obiect de învățare reutilizabil. În cadrul acestui proiect vom numi, un astfel de obiect, moment.

Un moment este format dintr-un cadru (un ecran) pe care, folosind indicațiile scenariului, profesorul va concatena diverse resurse multimedia cum ar fi: texte, diagrame și hărți interactive, simulări, experimente interactive, exerciții, teste cât și jocuri educaționale.

Aceste resurse multimedia sunt în număr de 13: text, surse adiționale de informații (ex: adrese de web), imagini, hartă, diagramă, material audio, animație, simulare, material interactiv, rezolvare de probleme, joc educativ, test (evaluare).

Ideea principală a acestor „momente” este împărțirea conținutului educațional (asa cum este prezentat în programa scolară) în părți mici care pot fi reutilizate în diferite medii de învățare oferind toate informațiile necesare pentru planificarea unei lecții sau a unui curs.

Momentele:

Sunt unități de învățare mai mici, cu o durată cuprinsă în mod normal între 5 și 10 minute.

Sunt autonome – fiecare obiect de învățare poate fi folosit independent

Sunt reutilizabile – un singur obiect de învățare poate fi reutilizat în mai multe context educaționale pentru mai multe scopuri

Pot fi grupate – momentele pot fi grupate în colecții mai mari de conținut, inclusiv structure tradiționale de curs

Sunt produse pentru a fi utilizate în mai multe medii virtuale de învățare

Sunt usor de modificat / actualizat

Fiecare moment are atribute didactice bine definite și obiective operaționale clare, dedicate temei pe care o abordează și cerute de programa scolară în baza căreia se lucrează. Avantajul abordării modulare a învățării este posibilitatea de a structura cursuri, plecând de la curriculă, dar pentru diverse nivele de înțelegere și receptare.

Varietatea materialelor didactice constituie suportul necesar unei activități didactice eficiente în care elevul contribuie activ la construcția propriei cunoasteri, este obligat să dea un continuu feedback și să ia decizii.

Înțelegerea noțiunilor are loc printr-o varietate de metode definite de interactivitate, cooperare, comunicare. Gradul de asimilare și înțelegere la nivelul noțiunilor fiind net superior celui dintrun demers pedagogic clasic, întregul proces bazându-se pe formarea unei structuri în care elevul învață să învețe, accentul fiind pus pe dezvoltarea gândirii critice.

Softurile fiind materiale complementare de instruire, ele nu înlocuiesc ci se adaugă, completează și îmbunătățesc strategiile didactice.

Un beneficiu major al acestor softuri este posibilitatea de a transforma o realitate virtuală în spațiu educațional. În acest spațiu se pot desfăsura activități care nu pot avea loc intr-un spațiu clasic

de învățare: experiențe sau experimente periculoase sau imposibil de realizat în realitate, simulări de procese și fenomene, călătorii și vizite virtuale la obiective geografice, stiintifice sau culturale etc.

În general softul educațional rezultă în urma unui proces elaborat de proiectare care are o fază inițială numită Inițializarea temei și trei mari etape de dezvoltare, fiecare având propriile cerințe:

Design educațional

Proiectarea interfeței și Modelul de accesibilitate

Dezvoltarea tehnică a resurselor multimedia și Integrare informatică Aceste etape prezintă propria lor dinamică, având, fiecare dintre ele, importanța lor în definirea globală a produsului final.

Inițializarea temei

Subiectul fiecărui moment este stabilit de profesor și urmăreste curriculumul aprobat pentru materia respectivă. Profesorul poate dezvolta un moment sau o secvență de momente în acord cu modul în care doreste să îsi desfăsoare / structureze lecția la clasă.

După stabilirea temei pentru moment / secvența de momente se dă răspunsul la o întrebare cheie: Suportul informatic furnizează un surplus de calitate transmiteriiprimirii informațiilor conținute în tema aleasă? Cu alte cuvinte este posibil ca informația furnizată să fie asimilată mai usor și pentru o perioadă mai îndelungată de timp folosind TIC? Cum trebuie să fie prezentarea multimedia a temei pentru a deveni un ajutor real pentru elevi?

Problema nu este de a anima un subiect ci de a contribui la procesul de învățare prin obiective precise cu rezultate ce pot fi cuantificate, folosind noile tehnologii. În această fază sunt stabilite structura scenariul și tipul de software pentru fiecare moment, făcându-se primul pas spre dezvoltarea lecției.

Este posibil ca în scenariul stiințific să apară modificări pe parcursul etapelor următoare dar structura trebuie stabilită încă de la început ca să armonizeze obiectivele propuse cu posibilitățile abordării multimedia. Lecția trebuie să răspundă în primul rând nevoilor pedagogice având în vedere ca produsul final este un produs didactic și nu informatic sau tehnologic.

Design educațional

Platforma teoretică a acestei faze a fost detaliată în capitolele precedente. Pentru un

scenariu eficient profesorul trebuie să țină cont de toate indicațiile primite dar, în acelasi timp, este chemat să îsi folosească experiența și creativitatea pentru prefigurarea unei strategii si concretizarea

acesteia intr-un demers instrucțional prin parcurgerea căruia la elev se produce învățarea, adică atingerea unor obiective specifice, prestabilite.

Design instrucțional pentru un soft educațional este o corelare a acțiunii însumate a unui număr de resurse multimedia cu obiectivele operaționale propuse în scopul producerii efectului educațional scontat. Această corelare se face folosind orientările moderne ale teoriilor pedagogic cu privire la rolul elevului, paradigmele educaționale noi, determinate de abordările constructiviste si centrarea pe elev, focalizarea pe învățare și nu pe predare prezentate în capitolele precedente.

Ca și în practica învățământului obisnuit, proiectarea unui demers instrucțional implică și o doză de subiectivism legat de experiența didactică a celui care proiectează. Dar, dincolo de acest fapt există o serie întreagă de elemente, cunoasterea și utilizarea cărora poate facilita proiectarea, poate asigura coerența demersului și spori eficiența produsului. Aceste elemente de tehnologie didactică se referă la: definirea obiectivelor operaționale urmărite, analiza populațieițintă, opțiunea pentru strategia pedagogică, definirea interacțiunii (toate aceste probleme au fost abordate din punct de vedre teoretic în capitolele precedente).

Definirea obiectivelor operaționale

Prima operație pe care o întreprindem în proiectarea unui soft educațional este aceea de a ne clarifica ce anume dorim să apară la elev ca rezultat al învățării. Rezultatul învățării îl reprezintă o schimbare, o modificare a comportamentului, apariția unei noi reacții; acest comportament este observabil și se poate cuantifica.

Obiectivele definite ne servesc pentru a defini interactivitatea și a construi instrumentele de evaluare formativă și sumativă, ca principale jaloane orientative în stabilirea strategiei didactice precum și pentru motivarea elevului. Pentru facilitarea acestei prime operații se utilizează

Taxonomia lui Bloom revizuită de Anderson și Krathwohl (2001) corelată cu ideea ca produsul acestui demers este un soft educațional obținut prin concatenarea unor resurse multimedia.

Analiza populației țintă

Prin caracteristici ale populațieițintă se înțelege o serie de factori personali (structura cognitivă, nivelul de dezvoltare cognitivă, capacitatea intelectuală, aspecte ale stilului cognitiv, factori motivaționali și atitudinali, situaționali (sociopsihologici și didactici) care pot varia de la un grup la altul. Intr-o măsura în care dispunem de date relevante pentru toți acesti factori, putem proiecta un soft adaptat la caracteristicile populației respective. De obicei adaptarea softului se realizează în raport cu nivelul de scolarizare și pregătire disciplinară.

Strategia pedagogică

Strategia folosită este în paradigmă constructivistă. Putem constata extraordinara suprapunere între această platformă și posibilitățile oferite de un demers educațional bazat pe resurse multimedia. Acesta este motivul pentru care paradigma constructivistă poate fi folosită cu succes în definirea unei strategii pedagogice a softurilor educaționale.

Definirea interacțiunii

Având obiective clar definite și operaționalizate, decizii neambigue în ceea ce priveste resursele materiale (resursele multimedia) și de conținut (conținutul stiințific), se poate trece la definirea și descrierea interacțiunii.

Importanța momentului decurge din faptul că acum se concretizează intențiile pedagogice ale proiectantului. El transpune în secvențele programului strategia didactică pentru care a optat (demers deductiv sau inductiv, învățare prin descoperire, rezolvare de probleme, drill and practice etc.) și va integra posibilități de individualizare.

În raport cu strategia adoptată, concatenarea resurselor se realizează în ansambluri de mărimi variabile moduli, care acoperă o anumită zonă conceptuală (de conținut) a disciplinei în cauză.

Reacția elevului la o solicitare a computerului conduce, de regulă, la o determinare a următoarei solicitări s.a.m.d. Există, deci un feedback (de confirmare, corecție, explicitare, diagnoză sau elaborare) și o anumită reglare la nivelul/în interiorul unităților de interacțiune. În acelasi timp, se pot realiza evaluări după parcurgerea fiecărui moment (evaluare modulară) sau la nivelul întregului conținut al unui curs (evaluare finală), care pot oferi datele necesare unei reglări la aceste niveluri: raportarea performanțelor elevilor la indicatorii obiectivelor (eventual, notarea lor), sugestii pentru utilizarea unor materiale adiacente, de recuperare, dezvoltare a potențialului creativ etc., cât și informații relevante pentru dezvoltatorii softului.

Concentrarea procesului de învățare asupra subiectului implică o viziune simplă și distinct din partea proiectantului – subiectul nu “învață o aplicație” sau “dintro aplicație”, ci utilizează u obiect educațional de sprijin în vederea dobândirii unor cunostințe intr-un domeniu anume care nu este legat de computere.

Această fază din dezvoltarea unui produs educațional multimedia aduce clarificări asupra majorității problemelor care apar dintre care enumerăm:

Respectarea particularităților individuale și sociale ale elevului, “particularizarea” softtului astfel încât să satisfacă nevoile subiectului, vârsta, stilul de cunoastere, aspirațiile etc., si de asemenea contextul sociocultural;

Atingerea unei dinamici a instruirii corecte, prin menținerea echilibrului psihologic atractivcaptivant, prin corelarea secvențelor aplicației la dificultatea materialului, la

conținutul iconic / simbolistic / abstract, la tipul formal / nonformal de educație, la unitățile de învățământ, la planurile de învățământ, la ritmul de predare, efortul disponibil, atenția, oboseala, stresul etc. ale subiectului;

Corelarea timpului și a gradului de interactivitate cu interfața, conform cu caracteristicile mesajului de instructaj asteptat din partea și provocat subiectului; textul, grafica, animațiile, informația audiovideo sau procedeele combinate vor depinde de particularitățile senzoriale si de percepție optime al utilizatorului receptor la un moment dat;

Adaptarea la condițiile aplicației colective a produsului software, luând în considerare că, sub influența fenomenelor și efectelor psihologice și sociale, acelasi subiect poate acționa în mod diferit intr-o comunitate decât atunci când va fi singur; în acest caz, se recomandă să se creeze o bancă de articole în faza de cercetare și un suport de autostandardizare în faza de utilizare.

Toate aceste principii / indicații / standarde vor fi utilizate pentru crearea unui scenariu. Profesorul va utiliza o templată profesionistă (InfoPath) în care va defini drumul de parcurs pentru dezvoltarea softului.

Profesorul îsi va selecta si/sau dezvolta resursele multimedia pe care le va salva intr-un folder special.

Proiectarea interfeței și Modelul de accesibilitate

Profesorului îi este pusă la dispoziție aplicația EDU Integrator care are definite în structura sa Interfața și Modelul de accesibilitate (în acest caz modelul de navigare).

Această fază de dezvoltare a unui soft educațional este intr-o proporție considerabilă făcută de aplicație.

Profesorul trebuie să definească diverse componente ale interfeței care pot varia de la un soft la altul legate de culori, fonturi și aranjarea în pagină.

Oferim mai departe câteva indicații legate de trei probleme importante legate de proiectare interfeței referitoare la designul vizual:

Organizare vizuală

Valoare estetică. Definiții de design visual

Folosirea culorilor

Organizare vizuală

Interacțiunea didactică dintre program și utilizator / elev se realizează printro interfață

ce permite corecta interpretare a reacțiilor utilizatorului și reglarea procesului conform unei strategii stabilite. Pentru a asigura cantitativ și calitativ sarcinile de lucru, softurile educaționale trebuie să aibă niveluri de interactivitate ridicată, cel puțin 50% din aplicații trebuie să fie interactive. Interactivitatea de navigare nu este considerată interactivitate în sens pedagogic.

Organizarea informației se face prin poziționarea textului față de imagine, stabilirea ponderii textului față de imagine și sunet, evitarea suprapunerii ferestrelor adiacente, prezentarea informațiilor în ferestre semnalizate în text etc. Textul va fi aliniat astfel încât informația esențială să fie prezentată în partea superioară, stângă a ecranului.

Momentele vor avea o interfață standardizată în care nu se foloseste derularea paginii.

Întreaga informație a unui moment didactic poate fi accesată printro navigare rapidă utilizând doar linkuri care se deschid cu usurință ferestre în ecranul principal.

Grafica trebuie să ofere standardizare și consistență în folosirea unui stil. Această cerință se referă la producerea unui aranjament care să permită focalizarea rapidă și fără ezitări pe elementele importante. Acesta trebuie să fie păstrat identic pentru toate secvențele materialului educațional multimedia.

Pentru coerența procesului didactic o serie de cerințe de design sau accesibilitate trebuie să fie standardizate pentru a asigura predictabilitate și regularitate, adică pentru a asigura confort elevului pe de o parte dar și pentru a îl ajuta în procesul învățării

realizarea textului: caracteristicile fontului (mărime, culoare, efecte) asigură lizibilitatea optimă (la distanța de 60/70 cm de ecran)

standardizarea interfeței pentru toate obiectele pentru a crea un mediu comun de învățare care să asigure confortul elevului

organizarea informației pe ecran: poziționarea textului față de imagine, evitarea suprapunerii ferestrelor adiacente etc.

utilizarea culorilor conform recomandărilor medicale și psihogice

respectarea unor proceduri standard pentru toate softurile educaționale

asigurarea unui sistem de help local

Toate ecranele lecției asigură unui sistem de ajutor local standardizat. Ajutorul este de două tipuri:

Ajutor (help) de navigare prin lecție care oferă indicații sub formă de text acolo unde butoanele de navigare nu sunt foarte intuitive și des folosite

Ajutor (help) contextual oferă indicații despre modul în care trebuie parcurse diversele itemuri de învățare

Instrucțiunile sunt standardizate, clare, simple ele pot fi înțelese de elevi cu abilități computeriale reduse, sunt scrise succint intr-o formulare fără echivoc. Formulările și definițiile urmăresc standardele internaționale.

Valoare estetică. Definiții de design visual

Grafica trebuie să urmărească câteva principii ale web designului:

Principiul unității – toate părțile unui ecran trebuie să formeze un întreg; unitatea poate fi perturbată de chenare, de prea multe tipuri de caractere, de culori distribuite

necorespunzător sau de o încărcare a paginii;

Principiul varietății – aspectul trebuie să fie variat și contrastant pentru a învinge monotonia; se pot folosi caractere variate, spațiu alb și spațiu tipărit, blocuri cenusii de text înviorate de subtitluri s.a.;

Principiul echilibrului – echilibrul este esențial între ilustrație, text, titlu și alte resurse multimedia prezente pe ecran;

Principiul ritmului – se poate obține senzația de miscare, chiar și în cazul unei ecran static; un mijloc simplu este identitatea paragrafelor, privirea fiind condusă de la un paragraf la altul;

Principiul armoniei – ecranul nu trebuie să conțină elemente de contrast subite, supărătoare sau bruste;

Principiul proporției – se referă în special la corpul de literă folosit pentru diferite lățimi ale textului: cu cât coloana de text este mai lată, cu atât dimensiunea literei este mai mare, si invers;

Principiul gamei coloristice – poate fi folosit în designul grafic, ținând cont de efectele fiziologice și psihologice ale culorilor și de senzațiile pe care acestea ni le creează;

Principiul accentuării – conform căruia, dacă se accentuează totul, nimic nu mai iese în evidență; aceasta se întâmplă când se abuzează, de pildă, de literele aldine sau când se folosesc prea multe majuscule. Contrastul este totusi necesar, ținând cont însă de celelalte legi și de aplicarea lor corespunzătoare.

Toate resursele multimedia folosite trebuie să aibă o calitate bună: atât rezoluția imaginilor cât și calitatea sunetului vor urmări standardele folosite pe web și în aplicațiile utilizate peste web.

Aspectul vizual are o contribuție semnificantă la o înțelegere clară a fiecărei informații oferite, fiind în conformitate cu normele psihopedagogice și considerând particularitățile elevilor.

Structura grafică respectă atât directivele valabile în designul instrucțional cât si recomandările standardelor, normelor și convențiilor specifice în domeniul de design al interfețelor

(dezvoltate în urma unei amănunț_C_o_m_m_eite cercetări psihologice) ca de exemplu în ceea ce priveste ergonomia ecranului sau funcționalitatea programului.

Simplitate

Autorii de softuri au tendința să includă prea multe detalii. Este indicat ca o pagină să conțină ideile principale și linkuri de acces de tip "pentru mai multe informații…".

Câteva cercetări care au analizat comparativ textele 'dense' și cele conținând doar ideile principale (prin eliminarea a 40% din conținutul primelor) au ajuns la concluzia că nivelul de reținere a informațiilor rămâne acelasi, în timp ce durata unei sesiuni de lucru / învățare se scurtează semnificativ în cazul textelor 'prelucrate'.

Includerea listelor și tabelelor pentru structurarea conținutului

Un tabel poate rezuma informații complexe intr-o manieră ce favorizează întelegerea. Sugestiile de aranjare a listelor sunt utile pentru un aranjament vizual eficient:

folosirea 'bulinelor' de marcare a fiecărui item sau numerotării identate

aranjarea listelor se va face vertical

alinierea va fi la stânga

Poziționarea în ordinea importanței

Informațiile vor fi poziționate în pagină în ordinea importanței și relevanței lor, locul privilegiat fiind în stânga, sus (pentru indivizii din culturile europeană, americană care sunt obisnuiți să parcurgă vizual materialele intr-o formă de Z).

Gruparea elementelor dupa semnificație

Acest principiu include câteva sugestii de 'topografia' paginii. Elementele subsumate aceleiasi idei trebuie să fie demarcate de alte elemente sau grupuri de elemente prin folosirea spațiilor libere, casetelor cu cadru, culorilor diferite și altor modalități de grupareetichetare.

Constanța poziției acestor grupuri de elemente în contextul vizual general al aplicației facilitează distingerea / recunoasterea lor.

Spațiere

Este indicat ca textul propriuzis să ocupe între 25 și 50% din spațiul total al paginii.

Evidențierea unităților de text prin folosirea atributelor: text subliniat, îngrosat sau caractere aldine. O culoare diferită scoate în evidență anumite informații considerate importante. Spațierea dintre linii va ține cont de mărimea corpului de literă.

Echilibru și simetrie

Textul trebuie distribuit echilibrat în pagină și ponderat prin includerea de grafice și imagini.

Avalansa de informații brute, neprelucrate din punct de vedere vizual, este contraindicată, conducând la dezorientarea utilizatorilor.

Utilizarea adecvată a culorilor

Constatarea că utilizarea unui câmp cromatic variat sporeste randamentul activității intelectuale a propulsat și diversificat cercetările despre influența culorilor asupra psihicului uman. O îmbinare adecvată de culori este un element important al materialelor de prezentare.

Culorile se pot utiliza la nivelul textului, la nivelul ilustrațiilor și pentru fundal. Utilizarea

culorii se justifică în primul rând funcțional, însă determină în mare măsură estetică (caracterul si ținuta materialelor) si, implicit, prestanța întregului software.

La nivelul textului

În cazul utilizării corespunzătoare a contrastelor cromatice, precizia și rapiditatea percepției si memorării informațiilor transmise creste cu 4050% comparativ cu contrastele simple în albnegru. Cercetările psihologice asupra contrastelor cromatice au stabilit următoarea ordine descrescătoare de intensitate a contrastelor cromatice pentru text din punct de vedere al lizibilității de la distanță și al preferinței în procesul de reținere de informații:

negru pe galben;

verde pe fond alb;

rosu pe fond alb;

albastru pe fond alb;

alb pe fond albastru;

negru pe fond alb;

galben pe fond negru;

alb pe fond rosu;

alb pe fond verde.

La nivelul ilustrațiilor

Utilizarea culorilor sporeste valoarea de semnificație. Cititorul receptează, prelucrează si interpretează o ilustrație color mult mai rapid și mai eficient decât o ilustrație în tonuri de gri.

Simbolurile indiciale care semnalează vizual prezența unui continut de un anumit tip

(meniu, informații utile, linkuri recomandate, atenționări etc.) îsi vor îndeplini mai bine funcția orientativă prin apelul la culori folosite constant și ținând seama de semnificațiile convenționale (galben precauție, rosu atenție etc.).

Există, desigur, și imagini care au efect mai mare dacă sunt în tonuri de gri. Fotografiile albnegru sunt deseori (când reprezintă acțiuni) mai pregnante, mai elocvente și mai sugestive, mai dramatice decât cele color; portretele albnegru pun mai bine în valoare expresia unei persoane.

Însa un grafic, o histogramă, o schemă sau o harta vor fi mult mai bine puse în evidență prin culori și devin astfel mai usor lizibile, mai puțin obositoare.

Ordinea contrastelor cromatice recomandate pentru grafice și scheme este următoarea:

albastru pe alb;

negru pe galben;

verde pe alb;

negru pe alb;

verde pe rosu.

Fundalul (backgroundul)

Diferențierea cromatică a paginilor fiecarei secțiuni sau teme se poate dovedi foarte utilă în orientarea generală în materialul de prezentare al softului.

Dar cel mai important aspect al utilizării culorii pentru fond se referă la funcția culorilor de influențare a conduitei, prin declansarea de trăiri afective, intenții, atitudini pozitive.

Semnificațiile și efectele culorilor

Efectele principalelor culori asupra psihicului le recomandă pentru folosirea în diverse situații de prezentare a unui material:

Rosu: stimulator general, provoacă, incită la acțiune, îndeosebi în plan psihomotor, stimulator intelectual, activare, mobilizare, facilitează asociațiile de idei. Este specifică tipului activ, autonom, locomotor, competitiv, operativ.

Portocaliu: stimulator emotiv, senzație de apropiere, culoare sociabilă, mai activă decât galbenul, lasă impresia de optimism, veselie; pe suprafețe întinse poate fi iritant.

Galben: stimulează și întreține starea de vigilență, sporeste capacitatea de mobilizare si concentrare a atenției, predispune la comunicativitate; dă senzația de căldură și intimitate. Caracteristică tipului activ, proiectiv, expansiv, investigativ și cu un nivel ridicat de aspirație. Privită mult timp, dă senzația de oboseală, dar în tonuri palide este suportabilă.

Verde: efect de liniste, bună dispoziție, relaxare, meditație, echilibru, siguranță; facilitează deconectarea nervoasă. Caracterizează tipul pasiv, defensiv, autonom, reținut. Exprimă concentrare, siguranță, introspecție, autoevaluare.

Albastru: favorizează dezvoltarea proceselor de inhibiție și de încetinire a ritmului activității; îndeamnă la calm și reverie, concentrare și liniste interioară, seriozitate, meditație. În exces, conduce la depresie. Se caracterizează prin "profunzimea trăirilor și sentimentelor". Caracteristică pentru tipul pasiv, senzitiv, perceptiv.

Violet: efect stimulator, nelinistitor și descurajator; dă senzația de gravitate. Semnificația psihologică este de tristețe, melancolie, penitență.

Negru: efecte psihologice de neliniste, reținere, depresie, introversie; impresie de adâncime, plinătate și greutate; semnificație psihoafectivă de tristețe, sfârsit, singurătate, despărțire. Poate fi utilizată ca element de delimitare, contrast sau fond pentru celelalte culori.

Alb: efecte de expansivitate, usurință, suavitate, robustețe, puritate, răceală; exprimă pace, împăcare, liniste, inocență, curățenie, sobrietate.

Bibliografie

Răzvan Andonie, Ilie Gârbacea, Algoritmi fundamentali – o perspectivă

C + +, Editura Libris, Cluj- Napoca, 1995.

Tudor Bălănescu, Șerban Gavrilă, Horia Georgescu, Marian Gheorghe, Liviu Sofonea, Ion Văduva, Programarea în limbajele Pascal și Turbo Pascal, vol. I și II, Editura Tehnică, București, 1992.

Gilles Brassard, Paul Bratley, Algorithmics – Theory and Practice, Prentice- Hall, Englewood Cliffs, 1988.

Valentin Cristea, Irina Atanasiu, Eugenia Kalisz, Valeriu Iorga, Tehnici de programare, Editura Teora, București, 1994.

S.M. Ermakov, Metoda Monte Carlo și probleme înrudite, Editura Tehnică, București, 1976.

E. Horowitz, S. Sahni, Fundamentals of Computer Algorithms, Computer Science Press, Rockville, 1978.

Leon Livovschi, Horia Georgescu, Sinteza și analiza algoritmilor, Editura științifică și enciclopedică, București, 1986.

Mihai Mocanu, Gheorghe Marian, Costin Bădică, Carmen Bădică, 333 probleme de programare,

Editura Teora, București, 1994.

Profesorul creator de soft educational 2010 Siveco.

Doina Rancea, Limbajul Turbo Pascal, Editura Libris, Cluj- Napoca, 1993.

Tudor Sorin, Tehnici de programare, Editura Teora, București, 1994.

Tudor Sorin, Tehnici de programare și structuri de date, vol. III (Branch and Bound, Programare dinamică, Greedy), Editura L&S INFO-MAT, București, 1994.

Tudor Sorin, Tehnici de programare, Editura L&S INFO-MAT, București, 1996.

Ion Văduva, Modele de simulare cu calculatorul, Editura Tehnică, București, 1977.

Colecția revistei Gazeta de informatică.

Revista Ziggy, Editura L&S INFO-MAT, București, 1996 (Marius Popescu, Programare dinamică).

PC REPORT, nr. 32, mai 1995, Ioan Iacob, Algoritmi genetici.

18 Ioan Odăgescu, Cristina Copos, Daniel Luca, Felix Furtună, Ion Smeureanu, Metode și tehnici de programare, Editura Intact, București, 1994.