Sisteme inteligente pentru învățarea algoritmilor Greedy și analiza statistică a [614760]

1
Sisteme inteligente pentru învățarea algoritmilor Greedy și analiza statistică a
impactului folosirii lor

Remus -Dragoș Albu , stud. an I CIG
FEAA, Universitatea din Craiova

Abstract : The specialists in education scienc e wanted to find new ways of teaching the
algorithms and to make their learning more attractive by their viewing and allowing students to
play with them as well as guiding them at every step. We will present several viewing tools that
support l earning methods for learning greedy algorithms . To make students understand t hese
algorithms requires (inter) active learning systems, because by making students learn by discovery,
they will feel stimulated to learn. We conducted a statistical anal ysis of the impact of the
implementation of information technologies on cognitive performance and on the motivation of
learning at school.

Introducere
Algoritmii și tehnicile de programare reprzintă esența Informaticii, dintotdeauna solicit ând o
atenți e deosebită . În trecut, ei erau predați în școli într -un mod pasiv, fapt pentru care unii elevi îi
învățau pe dinafară. Specialiștii în educație au fost înteresați în a găsi noi moduri de predare pentru
ca învăț area lor să devină mai atractivă, fiind nevoie de vizualizarea algoritmilor și de faptul ca
elevii să se poată juca cu ei, precum și de ghidarea lor la fiecare pas . Foarte multe sis teme de
vizualizare și animare a algoritmilor au fost construite, unele cu scopuri didactice explicite, pentru a
ajuta elevii să înțeleagă coportamentul algoritmilor.
Ne vor interesa acele instrume nte de vizualizare care suportă metode didactice pentru
învățarea -evaluarea algoritmilor de tip greedy. Deși ei sunt simpli, atingerea obiectivelor necesită
strategii de învățare grele. În manuale găsim doar descrierea algoritmilor greedy și apoi un set de
probleme, dar fiecare problemă constă în de -scriere, funcția de selecție optimă, demonstrarea
optimalității și analiza complexității, ori, pentru a -i face pe elevi să înțeleagă fiecare dintre acestea,
este nevoie de sisteme de învățare (inter)active, căci făcându -i pe elevi să învețe prin descoperire, ei
se vor simți stimulați pentru învățarea algoritmilor.
Algoritmii Greedy
Un algoritm greedy ia elementele în ordine, de fiecare dată pe cel considerat a fi „cel mai
bun”, conform unor anumite criterii, fără a ține cont de alegerile făcute înainte sau de cele ce se vor
face în viitor. Algoritmii greedy se numără printre cei mai direcți algoritmi posibili, vrând să
construiască într -un mod cât mai rapid soluția unei probleme. Ei se caracterizează prin luarea unor
decizii rapide, care duc la găsirea unei soluții potențiale a problemei. Nu întotdeauna asemenea
decizii rapide duc la o soluție optimă, trebuind concentrată atenția pe iden tificarea acelor anumite
tipuri de probleme pentru care se pot obține soluții optime.
Ideea de ba ză este simplă: având o problemă de optimizare, se va alege la fiecare pas decizia
cea mai favorabilă, fără a evalua global eficiența soluției, adică la fieca re pas se alege cel mai bun
candidat: [anonimizat], fără a studia alternativele disponibile în moment respectiv și
viabilita tea acestora în timp. D acă un candidat: [anonimizat], rămâne acolo, fără a putea fi
modificat, iar dacă este exc lus din soluție, nu va mai putea fi niciodată selectat drept un potențial
candidat. În general, există mai multe soluții posibile ale problemei, dintre acestea putându -se
selecta doar anumite soluții optime, conform unor anumite criterii. Scopul este de a găsi una dintre
acestea sau, dacă nu este posibil, atunci o soluție cât mai apropiată, conform criteriului optimal
impus. Rezultatul obținut este optim doar dacă un optim local conduce la un optim global. În cazul

2
în care deciziile de la un pas influențeaz ă lista de decizii de la pasul următor, este posibilă obținerea
unei valori neoptimale. În astfel de cazuri, pentru găsirea unui optim absolut se ajunge la sol uții
supra -polinomiale. D acă se optează pentru o astfel de soluție, algoritmul t rebuie însoțit de
demonstrarea corectitudinii.
Metoda Greedy este destul de puternică și este aplicată cu succes unui spectru larg de
probleme : algoritmul de determinare a arborelui parțial de cost minim, algoritmul lui Dijkstra
pentru determinarea celor mai scurte drumur i pornind dintr -un vârf al unui graf, varianta continuă a
problemei rucsacului, problema spectacolelor, planificarea activităților etc.
Sisteme informatice inteligente folositoare predării -învățării -evaluării
1. Jhave – An algorithm visualization system
Acest sistem este foarte matur și are drept scop animarea algoritmilor, apărând ca o
consecință a faptului că vizualizarea algoritmilor crește capacitatea de înțlegere a acestora mai mult
decât simpla citirea a codului lor. Este bogat în conținut, cu setări și controale, suportând mulți
algoritmi inclusiv grafuri, sortări, hashing și diverse altele. Nu este foarte intercativ cu elevul, dar
are niște ferestre pop -up cu întrebări referitoare la pașii de derulare ai algoritmului, cu care se
încearcă atragerea atenț iei acestuia, precum și pseudocodul algorimului respectiv. Prezentăm capturi
din timpul rulării algoritmilor Prim, Kruskal, Dijkstra și Huffman cu ajutorul sistemului Jhave:

Figura 1 – Jhave: Algoritmul lui Prim

Figura 2 – Jhave: Algoritmul lui Kruskal

Figura 3 – Jhave: Algoritmul lui Dijkstra

Figura 4 – Jhave: Codificarea Huffman

3
2. Animal
Conține o bună colecție de de algoritmi de diferite categorii, incluzând backtracking,
criptografie, grafuri, căutare și sortare, arbori, hashing etc. Animațiile su nt vizualizate împreună cu
codul sursă într -unul dintre limbajele de programare. Nu este foarte interactiv cu elevul, furnizând
doar animația algoritmului, ceea ce face ca atenția elevului să nu fie reținută o durată foarte mare de
timp. Apoi, este dificil ă îmbunătățirea procesului de învățământ și verificarea învățării exacte sau
nu. Sistemul are numeroase controale și setări, suportă trei limbi străine (engleză, germană și
italiană). De asemenea, îi oferă posibilitatea profesorului să modifice valorile și proprietățile (de ex.
culoarea) animației. El este foarte bun atunci când elevul dorește să învețe un algoritm sau are
dificultăți în aceasta. Utilizatorul are control asupra zoom -ului și vitezei animației, în rest este doar
un elev pasiv. Prezentăm captu ri din timpul rulării algoritmilor Prim, Kruskal, Dijkstra cu ajutorul
sistemului Animal:

Figura 5 – Animal: Algoritmul lui Prim

Figura 6 – Animal: Algoritmul lui Kruskal

Figura 7 – Animal: Algoritmul lui Dijkstra
3. Visualization
Acest sistem este focusat pe animația algoritmilor, incluzând grafuri, sortări, greedy,
algoritmi numerici etc. Nu se pot face modificări ale imputurilor. Prezentăm capturi din timpul
rulării algoritmilor Kruskal, Dijkstra cu ajutorul sistemului Visualization:

4

Figura 8 – Visualization: Algoritmul lui Kruskal

Figura 9 – Animal: Algoritmul lui Dijkstra
4. GreedEx
Este un sitem bazat pe abordarea învățării prin descoperire, concentrându -se pe algoritmii
greedy. Se bazează pe două dintre problemele foarte frecvente în cazul abordării de tip greedy:
problema selectării activitățior și problema rucsacului ( Knapsack). Se folosește o metodă didactică
pentru predarea algoritmilor greedy, aceasta solicitând elevilor găsirea tuturor funcțiilor de selecție
care ar putea caracteriza u n algoritm greedy optim pentru o problem de optimizare data. Nu există
nicio abordare ghidată și nici nu sunt oferite întrebări, prin prisma cărora elevul să fie evaluat.
Practic, cu ajutorul acestui sistem, elevii învață prin descoperirea lor înșiși. Elev ii pot introduce
inputurile pentru probleme sau sistemul poate genera un input aleator. În dependență de funcția de
selecție (mărirea timpului de terminare, micșorarea timpului de start etc.), furnizată de către elev,
rezultatul este vizualizat de către s istem, lucru care înseamnă că ei pot „vedea” desfășurarea
algoritmului. Este furnizat, de asemenea, și pseudocodul corespunzător. Sistemul prezintă, în formă
tabelară de sumarizare, rezultatul diferitelor funcții de selecție. Prezentăm capturi din timpul r ulării
algoritmilor sistemului GreedEx:

Figura 10 – GreedEx: Planificarea activităților

Figura 11 – GreedEx: Problema ruxacului

5
Analiza statistică a impactului implementării tehnologiilor informaționale asupra
învățării algoritmilor de tip Greedy
A fost realizat un experiment pedagogic format din două părți: cel de constatare, respectiv
cel de formare. Experimentul de formare s -a realizat în anul școlar 2015 -2016 , în eșantionul
experimental fiind implicați 14 elevi de clasa a XI -a, iar în cel de con trol 9 elevi de clasa a XI -a,
respectiv în anul școlar 2016 -2017 , în eșantionul experimental fiind implicați 17 elevi, iar în cel de
control 11 elevi.
Experimentul de constatare a fost realizat în două faze: 1). Determinarea reperelor
metodologice de aplicare a tehnologiilor informaționale în procesul didactic, realizat în anul școlar
2014 -2015 , respectiv 2). Selectarea eșantioanelor experimentale și de control, prin verificarea
omogenității acestor eșantioane, în anii școlari 2015 -2016 și 2016 -2017.
În prima fază a experimentului de constatare a fost analizat standardul curricular la
disciplina Informatică cu privire la promovarea creativității și inovării prin utilizarea noilor
instrumente TIC, a fost examinată literatura de specialitate din domeniul proiectării algoritmilor și
tehnicilor și metodelor de programare și cea din domeniul psiho -pedagogic.
În anul școlar 2015 -2016, în cadrul primei faze a experimentului de constatare au fost
implicați 23 de elevi de clasa a XI -a, profil matematică -informat ică intensiv și neintensiv.
Din standardul curricular la disciplina Informatică au fost selectate subiectele: algoritmul lui
Dijsktra, algoritmul lui Prim și algoritmul lui Kruskal, care au fost predate la orele de curs și
laborator cu aplicare a TIC, creându -se lecții digitate, folosindu -se diverse tehnologii informaționale ,
celelalte lecții fiind abordate în manieră clasică, fără folosirea noilor tehnologii informaționale . La
sfârșitul anului, a fost aplicat un chestionar pentru evaluarea opinie i elevilor în ceea ce privește
folosirea tehnologiilor informaționale în procesul didactic la Informatică, în uma anali zei
răspunsurilor stabilindu -se că f olosirea tehnologiilor informaționale ajută la înțelegerea mai bine și
mai facilă a materiei de studi u, ajută la mai buna intera cțiune a profesorului cu elevii, că lecția în
care sunt folosite mijloace tehnice noi este mai atractivă, iar acestora face procesul didactic mai
dinamic m crescând motivația de a asculta și a se implica mai activ în procesul dida ctic, cantitatea
de informație acumulată în timpul orelor fiind mai mare decât în cadrul orelor cu predare
tradițională și pentru faptul că vizual se înțeleg mai bine subiectele discutate la oră, datorită
diversit ății de culori pusă la dispoziție , care ajută în procesarea mai bună a informației prezentate și
în conc entrare pe aspectele importante, precum și fptul că evaluarea se realizează rapid și corect.
Pe baza rezultatelor primei faze a experimentului de constatare a fost plasat materialul
electronic Informatică – Metoda Greedy , care include suport teoretic și practic – probleme
rezolvate, teste de evaluare, linkuri utile. A fost elaborat modelul pedagogic de predare -învățare –
evaluare a unității Informatică – Maetoda Greedy prin implementarea noilor te hnologii
informaționale, au fost revăzute și completate materialele didactice digitale utilizate în experimentul
de constatare, au fost create seturi de teste de evaluare formativ -interactivă, sumativă, finală.
A doua fază a experimentului de constatare s -a axat pe selectarea eșantioanelor
experimentale și de control, urmărindu -se omogenitatea acestora. Pentru formarea eșantioanelor de
control și experimental, mai întâi a fost preluată media anuală la Informatică din anul precedent a
fiecărui elev, apoi s -a calculat media pe așantion, urmărindu -se ca nivelul de pregătire să fie
aproximativ același pentru ambele eșantioane, și s-a verificat dacă nu există diferențe semnificative
între eșantionul de control și cel experimental.
Analiza statistică a datelor co lectate s -a făcut aplicându -se testele t și U Mann -Whitney
pentru două eșantioane independente. Calculele s -au realizat cu ajutorul aplicației PSPP, care oferă
o metodă simplă de organizare a bazelor de date, prezentarea elementelor la un nivel foarte înal t și
prezentarea rezultatelor în acord cu standardele APA ( American Psychological Association ).
Ipotezele de cercetare formulate au fost: H0: m 1=m 2 – Nu există diferențe semnificative între
media eșantionului experim ental și cea a celui de control, respectiv H1: m 1≠m 2 – Există diferențe
semnificative între media eșantionului experimental și cea a celui de control.

6
S-au aplicat testele t și U Mann -Whitney pentru verificarea existenței diferențelor
semnificative între mediile eșantioanelor experimental și de control.
Testul t – este utilizat pentru testarea diferenței dintre mediile aceleiași variabile dependente
măsurate pe două eșantioane formate din subiecți diferiți. Dacă cele două eșantioane au aceleași
varianțe, compararea mediilor se poate face conform formulei:
, unde
n1, n 2 reprezintă numărul de subiecți din fiecare eșantion, m 1, m 2 reprezintă mediile celor două
eșantioane, s 1, s 2 reprezintă abaterile/deviația standard pentru fiecare eșantion. În experimentul
nostru, s 1≠s2, caz în care s -a folosit o formulă ajustată pentru testul t:
, formulă în care,
înlocuind datele pentru anul școlar 2015 -2016, se obține:
. Deci, s -a obținut t<t cr, adică se menține ipoteza
nulă H0: m 1=m 2 – nu există diferențe semnificative între media eșantionului experimental și cea a
celui de control și se respinge ipoteza H1.
S-a aplicat și testul neparametric U Mann -Whitney, care este unul dintre cele mai aplicate
teste de analiză statistică a date lor din sfera neparametrică, el nefiind sensibil la distribuția datelor,
ci doar la numărul cazurilor. Determinarea valorii exacte a testului statistic se face ordonând
crescător sau descrescător datele, apoi se calculează rangurile. Suma rangurilor, pentr u fiecare grup
de cercetare, a fost
, respective
, iar suma totală a rangurilor a fost
. Reiese că testul U Mann -Whitney este nesemnificativ, deci
se menține ipoteza de nul formulată, pentru eșantioanele din anul școlar 2015 -2016. Analog se
procedează și pentru anul școlar 2016 -2017.
Experimentul de formare s-a realizat timp de doi ani școlari: 2015 -2016 și 2016 -2017.
În anul școlar 2015 -2016, procesul didactic pentru eșantionul experimental, format din 14
elevi, a fost astfel elaborat încât să fie axat pe implementarea noilor tehnologii informatice, iar
pentru eșantionul de control, format din 9 elevi, acesta a fost ax at pe metodele clasice.
Metodele aplicate în cadrul orelor au fost: problematizarea, metoda clasei inversate,
învățarea prin decoperire, metoda instruirii reciproce , au fost discutate și completate împreună cu
elevii aspectele neclare acestora, fiind apli cată și metoda instruirii reciproce . Pentru facilitarea
învățării individuale, a fost realizat un curs electronic care a fost plasat pe serverul OC SS. Actul
didactic a fost organizat și sub forma unor prelegeri intensificate, care stimulează dezvoltarea
gândirii critice la elevi și care permite integrarea evaluării interactive în timpul orelor, conducând la
monitorizarea asimilării materialelor de către elevi în timpul orei și, implicit, în funcție de
răspunsurile elevilor, la ajustarea demersului didactic la necesitățile acestora. De asemenea, în
timpul orelor, mai ales cele de laborator, elevii au avut posibilitatea de a interacționa individual cu
tehnologiile informaționale utilizate. Cu ajutorul serverului OCSS au fost trimise elevilor
materialele preluc rate în cadrul orelor: lecții interactive create de profesor în diferite formate,
codurile programelor eleborate în comun cu elevii, sarcini individuale. Prin intermediul aceluiași
mediu a fost realizat și feedbackul, au fost expediate rezolvările sarcinil or individuale, care, apoi, au
fost și prezentate de fiecare elev. În cadrul unității de învățare, au fost realizate trei evaluări sub
formă de test – au fost administrate aceleași teste atât grupei experimentale, cât și grupei de control.
Analiza statis tică a rezultatelor experimentale
În cadrul cercetării au fost colectate o serie de seturi de date: rezultatatele/notele elevilor la
cele trei teste de evaluare sumativă și notele de la testul final. Aceste date au fost supuse operațiilor
de clasificare, o rdonare, analiză, interpretare pentru evidențierea unor legități/dependențe.

7
Pentru eșantionul experimental, anul școlar 2015 -2016, a fost calculat coeficientul de
asimetrie/indicatorul Fisher pentru evaluările summative și pentru evaluarea finală, acesta fiind
pozitiv pentru fiecare test, deci există o distribuție ușor asimetrică spre dreapta:

S-a calculat coeficientul de asimetrie al lui Fisher pentru evaluările summa tive și pentru
evaluarea finală și pentru eșantionul de control, anul școlar 2015 -2016, acesta fiind pozitiv pentru
fiecare test, existând o distribuție asimetrică spre dreapta, fiind înregistrate mai multe note mici:

Pentru an ul școlar 2016 -2017, coeficientul de asimetrie al lui Fisher pentru cele trei teste de
evaluare sumativă și testul de evaluare finală, pentru cele două eșantioane a fost:

S-a constatat că, pentru anul școlar 2016 -2017, procentul elevilor cu note de peste 8,5 la
testele de evaluare sumativă și la testul de evaluar e finală a fost de 52%, 35%, 88%, 94% pentru
eșantionul experimental, respectiv de 45%, 54%, 45%, 72% pentru eșantionul de control.
S-au aplicat asupra eșantioanelor participante, pentru anii școlari 2015 -2016 și 2016 -2017,
testele statistice paramatric p entru eșantioane independente t și neparametric U Mann -Whitney.
Analizând datele pentru anul școlar 2016 -2017, se observă că rezultatul testului Levene este
nesemnificativ F(26)=0,04, iar p=0,851>0,05, deci este satisfăcută condiția de omogenitate a
varianțelor. S -a obținut t=2,81>t cr=2,056, deci există diferențe semnificative între mediile
eșantioanelor experimental și cel de control, adică se menține ipoteza H 1 și se respinge ipoteza nulă
H0. De asemenea, se constată îndeplinirea relației Lower<Mean Difference<Upper – -0,95< -0,55< –
0,15 (care sunt limitele intervalului de încredere cu probabilitatea de 95% și diferența dintre mediile
eșantioanelor examinate) și cum 0 ∉(-0,95 ; -0,15), este demonstrat că diferența dintre mediile
eșantionului experimental și media eșantionului de control este semnificativă. De asemenea , se
observă că U=46,5, z=2,41, p=0,016<0,05, adică se confirmă existența diferențelor semnificative
între eșantionul experimental și eșantionul de control, deci aplicarea testului U Mann -Whitney
eșantioanelor din anul școlar 2016 -207 respinge ipoteza H 0 și menține ipoteza H 1.
Analiza rezultatelor testului t, prin prisma mărimii efectului, conduce la c oncluzia că efectul
produs prin introducerea și folosire tehnologiilor informaționale asupra performanțelor elevilor din
eșantionul experimental, anul școlar 2016 -2017, a fost foarte puternic (d≥1), conform indicatorului
d al lui Cohen, caracterizat de diferența standardizată dintre medii, respectiv de la moderat spre
puternic (0,30≤r≤0,50), conf orm indicatorului r, bazat pe gradul de asociere dintre variabile. Pe de
altă parte, marimea efectului calculată pe baza rezultatelor obținute prin aplicarea testului U
MannWhitney indică faptul că implementarea tehnologiilor informaționale a avut un efect de la
moderat spre puternic (0,30≤r≤0,50) asupra performanțelor elevilor din eșantionul experimental,
anul școlar 2016 -2017.
Determinarea relațiilor între mediile mai multor grupuri sau mediile aceluiași grup în diverse
situații se face folosind testele d e contrast sau comparațiile, prin care se poate determina tendința
unui anumit eșantion.

8

S-a observat că există o creștere liniară a performanțelor școlare, dar mediile eșantionului de
control sunt mai mici decât cele ale eșantionului experimental. Deci, s-a demonstrat, prin
prelucrarea datelor statistice, că utilizarea în procesul de predare -învățare -evaluare a tehnologiilor
informaționale, a resurselor interactive, a avut rol benefic pentru eșantionul experimental, elevii
înregistrând rezultate mai bun e comparativ cu cei din eșantionul de control. Astfel, ipoteza
cercetării a fost confirmată.
Concluzie
În aceast studiu am încercat prezentarea unor mijloace didatice digitale utile procesului de
studiere a algoritmilor de tip Greedy și care pot conduce la creșterea eficinței strategiilor didactice
interactive și la obținerea rezultatelor școlare mai bune. Ideea centrală rezidă în aceea că
implemetarea tehnologiilor informaționale are impact major și randament crescut, comparativ cu
metodele și tehnologiile clasice, atât din punct de vedere cognitiv sau al evaluării, c ât și din cel al
motivației învățării.
Cercetarea pedagogică, a condus, în baza analizei stati stice, la concluzia că implementarea
modelului centrat pe implementarea tehnologiilor informaționale în procesul didactic a contribuit la
înregistrarea unei creșteri cubice a performanțelor școlare pentru elevii din eșantionul experimental,
comparativ cu cei d in eșantionul de control, precum și la i dentificarea dependenței dir ecte dintre
modelul didactic interactiv, cu integrarea tehnologiilor informaționale în procesul didactic, și
creșterea gradului de pregătire al elevilor.
Putem conchide că obiectivele cercetării au fost îndeplinite, soluționându -se problema
determinării fu ndamentelor teoretico -metodologice ale eficientizării procesului de studiere a
algoritmilor de tip Greeedy prin implementarea tehnologiilor informaționale.
Bibliografie
1. Galles, David – https://www.cs.usfca.edu/~galles/visualization/
2. Labăr, Adrian Vicențiu (2008). SPSS pentru științele educației . Iași: Editura Polirom
3. Naps, T. L. , Jhave: Supporting algorithm visualization , IEEE Computer Graphics and
Applications, vol. 25, no. 5, pp. 49 -55, sept. 2005
(https://pdfs.semanticscholar.org/c82a/0c72128cfbed3a3c79aae2de971fc0241866.pdf ).
4. Opariuc -Dan C. (2011) . Statistica aplicată în științele socio -umane. Analiza asocierilor și a
diferențelor statistice . Cluj -Napoca: Editura ASCR
5. PSPP (https://www.gnu.org/software/pspp/manual/pspp.html )
6. PSPP User’s Guide. GNU PSPP Statistical A nalysis Software Release 0.10.2 .
(https://www.gnu.org/software/pspp/manual/pspp.pdf )
7. Roling, G.; Freisleben, B., Animal: A System for Supporting Multiple Roles in Algorithm
Animation , Journal of Visual Languages and Computing (2002), vol. 13, no. 2, pp. 341 -542
(https://pdfs.semanticscholar.org/9d58/b9dde8ee4b6ba8c531d03db8f09b77bca841.pdf ).
8. Shaffer, C. A.; Cooper, M. L.; Alon, A. J. D.; Akbar, M.;Stewart, M.; Ponce, S.; Edwards, S. H.,
Algorithm Visualization: The State of the Field , ACM Transactions on Computing Education, Vol.
10, No. 3, Article 9, Pub. date: August 2010 ( http://www.cs.utep.edu/makbar/papers/TOCE.pdf ).
9. Velázquez -Iturbide, J. Angel; Debdi, Ouafae; Esteban -Sanchez, Natalia; Pizarro, Celeste,
GreedEx: A Visualization Tool for Experimentation and Disc overy Learning of Greedy Algorithms ,
IEE Transactions on Learning Technologies, vol. 6, no. 2, April -June 2013, pp. 130 -143
(https://www.computer.org/csdl/trans/lt/2013/02/tlt 2013020130.pdf ).