LUCRARE METODICO ȘTIINȚIFICĂ PENTRU OBȚINEREA GRADULUI DIDACTIC I ÎN ÎNVĂȚĂMÂNT METODE DE ELABORARE A ALGORITMILOR, ASPECTE METODICE COORDONATOR… [302347]
UNIVERSITATEA DIN PITEȘTI
DEPARTAMENTUL PENTRU PREGĂTIREA
PERSONALULUI DIDACTIC
LUCRARE METODICO ȘTIINȚIFICĂ PENTRU OBȚINEREA
GRADULUI DIDACTIC I ÎN ÎNVĂȚĂMÂNT
METODE DE ELABORARE A ALGORITMILOR,
ASPECTE METODICE
COORDONATOR ȘTIINȚIFIC:
Conf. Univ. dr. Constantin Doru
CANDIDAT: [anonimizat]:
[anonimizat] 2019
CUPRINS
PREFAȚĂ…………………………………………………………………………………
INTRODUCERE………………………………………………………………………….
Capitolul 1
1.1. Algoritmi de căutare. Căutarea binară……………………………………………….
1.2. Sortări…………………………………………………………………………………
1.2.1. Sortarea prin numărare………………………………………………………….
1.2.2. Sortarea prin inserție direct……………………………………………………..
1.2.3. Sortarea prin inserție binară…………………………………………………….
1.2.4. Sortarea rapidă………………………………………………………………….
1.2.5. Sortarea prin selecție directă……………………………………………………
1.3. Liste.Algoritmi specifici……………………………………………………….…….
1.3.1. Inițializarea listei………………………………………………………………..
1.3.2. Alocarea memoriei……………………………………………………………..
1.3.3. Crearea………………………………………………………………………….
1.3.4. Adăugarea primului nod în listă…………………………………………………
1.3.5. Adăugarea unui nod în listă…………………………………………………….
1.3.6. Parcurgerea…………………………………………………………………….
1.3.7. Căutarea unui nod în listă………………………………………………………
1.3.8. Eliminarea unui nod din listă…………………………………………………..
1.4. Stiva…………………………………………………………………………………
1.4.1. Inițializarea stivei………………………………………………………………
1.4.2. Adăugarea unui nod în stivă…………………………………………………..
1.4.3. Extragerea unui nod din stivă…………………………………………………
1.4.4. Prelucrarea stivei……………………………………………………………….
1.5. Coada…………………………………………………………………………………
1.5.1. Inițializarea cozii……………………………………………………………….
1.5.2. Adăugarea unui nod în coadă………………………………………………….
1.5.3. Extragerea unui nod din coadă…………………………………………………
1.5.4. Prelucrarea cozii…………………………………………………………………
Capitolul 2
Metode și tehnici de programare
2.1. Metoda Divide Et Impera…………………………………………………………….
2.2. Metoda backtracking…………………………………………………………………
2.3. Metoda Greedy……………………………………………………………………….
2.4. Teoria grafurilor………………………………………………………………………
2.4.1. Grafuri neorientate……………………………………………………………..
2.4.2. Grafuri orientate……………………………………………………………….
Capitolul 3
[anonimizat]-evaluare
3.1. Obiectivele cercetării…………………………………………………………………
3.2. Metodele cercetării………………………………………………………………….
3.3. Organizarea cercetării……………………………………………………………….
3.4. Nivelul inițial al clasei……………………………………………………………….
3.5. Etapa experimentală…………………………………………………………………
3.6. Etapa finală………………………………………………………………………….
3.6.1. Analiza și interpretarea rezultatelor evaluării finale…………………………
3.6.2.Concluzii……………………………………………………………………….
RECOMANDĂRI EDUCAȚIONALE…………………………………………………..
ANEXE………………………………………………………………………………….
BIBLIOGRAFIE…………………………………………………………………………
Prefață
Lucrarea de față apare ca o necesitate intr-o lume aflată intr-o continuă schimbare și dezvoltare în care informatica ocupă un loc central.
[anonimizat] a elevilor, [anonimizat], de capacitatea acestora de asimilare a noilor cunoștințe și în funcție de experiența cadrului didactic. Acesta trebuie să ofere libertatea elevilor săi de a [anonimizat] a [anonimizat] a se implica în cadrul orelor de informatică, de a-și adduce propria contribuție în domeniu.
Această lucrare, cuprinde atât teorie, probleme, cât și o parte de cercetare. Am ținut cont și de faptul că tehnologiile informaționale sunt vitale pentru societatea de astăzi, de aceea informatica ocupă un loc important.
Lucrarea este structurată în trei capitole. În introducere sunt prezentate teorii cu privire la definiția algoritmilor, reprezentarea algoritmilor în pseudocod și structuri.
Capitolul I cuprinde implementarea unor algoritmi cu privire la căutarea binară, tipuri de sortări, liste, stive, cozi. Tot aici sunt prezentate și noțiuni teoretice cu privire la acești algoritmi.
Capitolul II conține metode și tehnici de programare și grafuri. Aici sunt prezentate: Divide Et Impera, Backtraking, Greedy și grafuri neorientate și orientate.
Capitolul III cuprinde o parte de cercetare.
Cartea conține la final o anexă cu fișe de lucru, tabele pe care le-am considerat destul de creative și atractive pentru înțelegerea noțiunilor prezentate, teste inițiale și teste finale.
Introducere
I.1. Ce este algoritmul?
I.1.1. Definiția unui algoritm
Un algoritm reprezintă succesiunea etapelor rezolvării unei problem, în ordinea parcurgerii lor, prin care se prelucrează un set de date de intrare, în scopul obținerii unor date de ieșire ( rezultate).
Orice algoritm trebuie să satisfacă următoarele proprietăți:
Să fie cât mai general, adică să acopere toate situațiile posibile.
Să fie bine definit, adică cerințele să fie clar,iar datele suficiente.
Să fie finit, adică să se incheie rezolvarea la un moment dat.
Să fie rezolvabil, adică să aibă cel puțin o soluție.
I.1.2. Obiectele cu care lucrează algoritmii
Orice algoritm folosește date si expresii. Datele sunt: constante și variabile.
O constantă este o dată a cărei valoare nu se modifică pe parcursul execuției programului.
Constantele sunt de mai multe tipuri:
Constante întregi: numere întregi cu sau fără semn.
Constante reale: valori raționale, cu virgulă zecimală și număr finit de zecimale.
Constante șir de caractere: șiruri de caractere cuprinse între apostrofuri care sunt alcătuite din caractere și spațiu.
Constante logice (booleene): se folosesc când întâlnim condiții și vom folosi cuvintele TRUE sau FALSE.
O variabilă este o dată a cărei valoare se poate modifica pe parcursul execuției programului.
Tipul unei variabile se referă la mulțimea valorilor pe care aceasta le poate primi:
Tipul întreg: numere întrgi cu sau fără semn.
Tipul real: numere reale cu virgula zecimală reprezentată de punct.
Tipul caracter: caractere cuprinse între apostrofuri.
Tipul șir de caractere: șiruri de caractere cuprinse între apostrofuri.
Tipul logic (boolean) : TRUE, FALSE.
Expresiile sunt alcătuite dintr-unul sau mai mulți operanzi legați între ei prin operarori. Operanzii pot fi constante și variabile.
Expresiile sunt de mai multe tipuri: aritmetice, logice (booleene).
I.2.Reprezentarea algoritmilor în pseudocod.
Un limbaj pseudocod se reprezintă în pseudocod sub forma unui text și folosește cuvinte cheie. Există numeroase tipuri de pseudocod, depinde de fiecare programator.
I.2.1. Exemplu de pseudocod
Vom prezenta în continuare un algoritm foarte simplu în pseudocod și anume suma a două numere reale.
Mai întâi trebuie să cunoaștem valorile celor două numere reale, care vor fi introduse de la tastatură. Acestea sunt datele de intrare și reprezintă două variabile. Vom spune că se citesc de la tastatură cele două valori. Pentru asta vom folosi cuvantul cheie CITEȘTE urmat de numele celor două variabile separate prin virgulă, rând care se încheie cu punct și virgulă.
În cazul nostru, putem numi cele două variabile a și b și vom avea:
citește a,b;
Pentru a calcula suma celor două numere, vom folosi instrucțiunea de atribuire, iar suma va fi notată cu S. Astfel, vom avea:
S=a+b;
După ce ne-a calculat valoarea sumei, calculatorul va trebui să ne arate rezultatul și pentru asta va folosi instrucțiunea de afișare SCRIE. Vom avea deci:
scrie S;
Iată,deci, primul nostru algoritm în pseudocod:
Algoritmul de mai sus poate fi simplificat astfel:
I.3. Structuri
Structura reprezintă o modalitate de a îmbina operațiile cu care lucrează algoritmii.
Programarea structurată este foarte importantă mai als în cazul algoritmilor foarte lungi și complecși.
Pentru a realiza orice program sunt suficiente următoarele trei tipuri de structuri:
liniară
alternativă( de selecție)
repetitivă.
I.3.1. Structura liniară
Exemplul prezentat anterior reprezintă un tip de structură liniară, în care fiecare operație se execută necondiționat, o singură dată.
I.3.2 Structura de selecție
I.3.2.1. Structura de selecție simplă
Această structură are următoarea sintaxă:
Principiul de funcționare este următorul:
se testează condiția dată de <expresie>.
dacă aceasta este adevărată, se execută <secvența1>.
în caz contrar, se execută <secvența2>.
Observații:
ramura altfel poate lipsi( în acest caz nu se execută nimic dacă <expresie> este falsă).
în cazul în care <secvența1> sau <secvența2> conține mai mult de o instrucțiune, acestea trebuie cuprinse între început și sfârșit.
Exemplu: Maximul a două numere întregi x și y citite de la tastatură.
citește x,y;
dacă x>y atunci max=x
altfel max=b;
scrie max.
I.3.2.2 Structura de selecție multiplă
De multe ori apare nevoia de a alege o secvență din mai multe posibile. Această alegere va putea fi făcută cu ajutorul unei variabile numită selector. Valorile selectorului se vor numi cazuri.
Observații:
cazurile reprezintă o valoare sau un set de valori ale selectorului.
fiecărui caz îi corespunde o secvență de instrucțiuni.
întreaga instrucțiune de selecție multiplă se va încheia cu cuvântul sfârșit.
Exemplu: Să se realizeze un program care citește de la tastatură două numere reale a și b, apoi afișează media aritmetică, suma pătratelor sau suma cuburilor celor două numere, în funcție de dorința utilizatorului.
I.3.3. Structuri repetitive
I.3.3.1. Structura repetitivă cu test inițial
Această structură are următoarea sintaxă:
cât timp <expresie> execută
<secvență de instrucțiuni>
Principiul de funcționare este următorul:
atâta timp cât este îndeplinită condiția dată de <expresie>, se execută <secvența de instrucțiuni>.
în cazul în care avem cel puțin două instrucțiuni, <secvența de instrucțiuni> va fi cuprinsă între început și sfârșit.
testarea condiției are loc la început, deci corpul poate să nu se execute niciodată.
Exemplu: Să se calculeze suma a n numere naturale citite pe rând de la tastatură, unde n are o valoare cunoscută.
I.3.3.2. Structura repetitivă cu test final
Aceasă structură are următoarea sintaxă:
Principiul de funcționare este următorul:
se repetă execiția secvenței de instrucțiuni până cand <expresie> devine adevărată.
deoarece testarea are loc la sfârșit, corpul se va executa cel puțin o dată.
Exemplu: Suma cifrelor unui număr natural.
I.3.3.3. Structura repetitivă cu număr fix de pași
Această structură are următoarea sintaxă:
Principiul de funcționare este urmatorul:
variabila contor numără pașii ciclului.
v1 și v2 sunt cele două valori extreme ale ciclului.
Exemplu: Număr prim.
Capitolul 1
1.1.Algoritmi de căutare. Căutarea binară
Enunț: Se dă un vector p=(p1,p2,…,pn) cu elementele ordonate crescător și o valoare c.Se cere să se verifice dacă c se găsește printre elementele vectorului p și să se returneze poziția elementului în șir, în caz afirmativ.
Rezolvare: Dacă c nu se află în vector se va afișa valoarea -1.
Vom reține capetele șirului în variabilele s și d. Vom afla elemental de pe poziția de mijloc și acesta va avea valoarea m =(s+d)/2. Dacă acesta este elemental căutat, atunci va fi afișat. Dacă p[m]<c, atunci vom continua căutarea în dreapta elementului de pe poziția de mijloc a șirului. Dacă p[m]>c, atunci vom continua căutarea în stânga.
Complexitatea algoritmului: În cel mai bun caz, algoritmul găsește elementul în O(1), atunci când acesta se află pe poziția de mijloc. În cel mai rău caz, vor fi efectuate log2(n) comparații.
Implementarea algoritmului:
#include<iostream>
using namespace std;
int n,cautat,p[10],m;
int caut (int s, int d)
{
if(s>d)
return -1;
else
{
m =(s+d)/2;
if (cautat==p[m])
return m;
if (cautat<v[m])
return caut(s,m-1);
else
return caut(m+1,d);
}
}
int main()
{
cout<<"n,cautat ";
cin>>n>>cautat;
cout<<"dati "<<n<<" elemente (in ordine crescatoare).\n";
for (int i=1;i<=n;i++)
cin>>p[i];
cout<<"elementul "<<p<<" a fost gasit pe pozitia: "<<caut (1,n);
return 0;
}
Fig.1 Algoritmul da căutare binară
Fig.2 Rularea algoritmului de căutare binară
1.2. Sortări
1.2.1. Sortarea prin numărare
Enunț: Se dă un tablou unidimensional care are n valori numere întregi. Vom sorta elementele în ordine crescătoare.
Rezolvare: Fie vectorul p. Vom găsi pentru fiecare element al vectorul numărul de elemente mai mici decât acesta. Numerele obținute vor fi memorate într-un vector t. Elementele lui p vor fi salvate temporar într-un vector s.
Implementarea algoritmului:
#include<iostream.h>
int p[25],s[25],t[25],numar,i,j;
void main()
{
cout<<”nr de elemente este urmatorul:”; cin>>numar;
for(i=0;i<n;i++) { cout<<”p[“<<i<<”]=”; cin>>p[i]; }
for(i=0;i<numar;i++) cout<<s[i]<<” “;
for(i=0;i<numar;i++)
s[i]=p[i];
for(i=0;i<numar;i++)
for(j=i+1;j<numar;j++)
if (p[i]<p[j])
t[j]++;
else t[i]++;
for(i=0;i<numar;i++)
p[t[i]]=s[i];
cout<<endl;
for(i=0;i<numar;i++) cout<<p[i]<<” “;
}
Fig.3 Sortarea prin numărare
Fig. 4 Rularea algoritmului de sortare prin numărare
1.2.2. Sortarea prin inserție directă
Enunț: Se dă un tablou unidimensional care are n valori numere întregi. Vom sorta elementele în ordine crescătoare.
Rezolvare: Se dă un vector a cu n numere naturale. Elementul a[2] se compară cu a[1] și încercăm să găsim poziția unde să se introducă. Dacă a[2]<a[1] atunci a[2] trebuie să fie înainte și îl mutăm pe a[1] pe poziția următoare. La un pas j avem vectorul sortat a[1],…,a[j-1] și îl inserăm pe a[j] astfel încât să păstrăm vectorul ordonat între 1 și j-1. Pentru aceasta, se compară a[j] cu elementele a[j-1], a[j-2], …, a[1] (în această ordine), mutând elementul de la poziția curentă cu o poziție la dreapta atunci când a[i]>a[j]. Când a[i]<=a[j] procesul de inserție se oprește, poziția la care se realizează inserarea fiind i+1.
Implementarea programului:
#include<iostream>
using namespace std;
int e[80], numar, i;
void inserare(int e[80], int numar)
{
int i, j, x;
for(i=2; i<=numar; i++)
{
x = e[i];
j = i-1;
while( j >= 1 && e[j] > x )
{
e[j+1] = e[j];
j–;
}
e[j+1] = x;
}
return;
}
int main(void)
{
cout<<"Dimensiunea tabloului este urmatoarea numar = ";
cin>>numar;
cout<<"Dati elementele tablourile: \n";
for(i=1; i<=numar; i++)
{
cout<<"e["<<i<<"] = ";
cin>>e[i];
}
inserare(e, numar);
cout<<"Tabloul ordonat crescator :\n";
for(i=1; i<=numar; i++)
cout<<e[i]<<" ";
}
Fig.5 Algoritmul de sortare prin inserție directă
Fig. 6 Rularea algoritmului de sortare prin inserție directă
1.2.3. Sortare prin inserție binară
Enunț: Se dă un tablou unidimensional care are n valori numere întregi. Vom sorta elementele în ordine crescătoare.
Rezolvare: Metoda de sortare prin inserție binară se deosebește de cea prin inserție directă prin modul de căutare al poziției de inserare. În metoda de inserție directă poziția se caută utilizând algoritmul de căutare liniară. Aici ea se determină folosind metoda de căutare binară, mult mai eficientă. Aceasta constă în înjumătățirea repetată a intervalului vizat până la găsirea locului căutat.
Implementarea programului:
#include<iostream>
using namespace std;
void ins_bin(int e[], int numar)
{
int i, j, stg, drp, m, aux;
for(i=2;i<=numar;i++)
{
aux=e[i];
stg=1;
drp=i-1;
while(stg<=drp)
{
m = (stg+drp) / 2;
if(e[m]>aux) drp=m-1;
else stg=m+1;
}
for(j=i; j>=stg+1; j–)
e[j]=e[j-1];
e[stg]=aux;
}
}
int main ()
{
int i,numar,e[30];
cout<<"Introduceti dimensiunea sirului: ";
cin>>numar;
cout<<"Dati elementele sirului:\n";
for(i=1;i<=numar;i++)
{
cout<<"e["<<i<<"]=";
cin>>e[i];
}
ins_bin(e,numar);
cout <<"Sirul ordonat este: ";
for(i=1;i<=numar;i++) cout<<e[i]<<" ";
}
Fig. 7 Algoritmul de sortare prin inserție binară
Fig. 8 Rularea algoritmului de sortare prin inserție binară
1.2.4. Sortarea rapidă (Quik Sort)
Enunț: Se dă un tablou unidimensional care are n valori numere întregi. Vom sorta elementele în ordine crescătoare.
Rezolvare: În practicã algoritmul de sortare cel mai rapid este Quicksort numitã sortare rapidã, care foloseste partitionarea ca idee de bazã. Este mai rapidã decât orice metodã de sortare simplã, se executã bine pentru fisiere sau tabele mari, dar ineficient pentru cele mici. Strategia de bazã folositã este "divide et impera", pentru cã este mai usor de sortat douã tabele mici, decât una mare. Algoritmul este usor de implementat, lucreazã destul de bine în diferite situatii si consumã mai putine resurse decât orice altã metodã de sortare în multe situatii. Fie tab un tablou cu n componente. Sortarea prin această metodă are la bază următorul principiu: practic tabloul este ordonat când pentru fiecare element din tablou v[poz], elementele situate la stânga sunt mai mici v[poz], iar cele din dreapta sunt mai mari sau egale decat v[poz]. Sortarea tabloului tab decurge astfel:
La un moment dat se prelucrează o secvență din vector cu indecși cuprinși între p si u
– se ia una din aceste componente, fie ea piv=v[p], care se consideră element pivot;
– se fac în tablou interschimbări de componente, astfel încât toate cele mai mici decât valoarea pivot să treacă în stânga acesteia, iar elementele cu valoare mai mare decât pivot să treacă în dreapta; prin această operație se va deplasa și valoarea pivot, astfel că ea nu se va mai gasi pe pozitia inițială ci pe o poziție corespunzătoare relației de ordine. Fie aceasta k.În urma acestui set de operații ,elementele din stânga sunt mai mici decât pivotal, dar nu neapărat și în ordine. La fel cele din dreapta sunt mai mari dar nu neapărat și în ordine.
Se continuă setul de operații similare, aplicând recursiv metoda pentru zona de tablou situată în stânga componentei pivot și pentru cea din dreapta acesteia;
– oprirea se face când lungimea zonei de tablou care trebuie sortată devine egala cu 1.
Implementarea programului:
#include <iostream.h>
#include <conio.h>
#include<stdlib.h>
int x[2000];
int n;
int poz(int p,int u)
{int piv,aux,k;
piv=x[p];
while (p<u)
{ if (x[p]>x[u]) {aux=x[p];
x[p]=x[u];
x[u]=aux;
}
if (x[p]==piv)
u–;
else p++;
}
k=p;
return k;
}
void quick(int p,int u)
{int k;
if (p<u) {k=poz(p,u);
quick(p,k-1);
quick(k+1,u);}
}
void main()
{clrscr();
cout<<"n=";
cin>>n;
for(int i=1;i<=n;i++)
{cout<<"x["<<i<<"]=";
cin>>x[i];
}
quick(1,n);
for(i=1;i<=n;i++)
cout<<x[i]<<' ';
getch();
}
Fig. 9 Algoritmul de sortare rapidă
Fig. 10 Rularea algoritmului de sprtare rapdă
1.2.5. Sortarea prin selecție directă
Enunț: : Se dă un tablou unidimensional care are n valori numere întregi. Vom sorta elementele în ordine crescătoare.
Rezolvare: Fiecare element v[i] se compara cu toate aflate dupa el. Daca se gaseste un element mai mic decat v[i] atunci acestea se vor interschimba. Cand v[i] si-a incheiat rolul de pivot, partea din vector pana la acesta nclusive, este sortata crescator.
Implementarea programului:
#include<iostream.h>
int v[25],n,I,j,aux;
void main()
{cout<<„nr de elemente=”;
cin>>n;
for(i=0;i<n;i++)
{cout<<„v[„<<i<<„]=”;
cin>>v[i];}
for(i=0;i<n;i++)
cout<<v[i]<<” „;
for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++)
if(v[i]>v[j])
{ aux=v[j]; v[j]=v[i]; v[i]=aux; }
cout<<endl;
for(i=0;i<n;i++)
cout<<v[i]<<” „;
}
Fig.11 Algoritmul de sortare prin selecție irect
Fig. 12 Rularea algoritmului de sortare prin selecție directă
1.3. Liste. Algoritmi specifici.
Vom considera că un nod al listei conține doar un câmp cu informație și câmpul pentru realizarea legăturii.
const unsigned Nmax=110;
typedef unsigned adr;
struct nod
{ int info; adr urm;}
nod lista [Nmax+1];
adr prim,ultim,p;
unsigned nr_elem,liber[Nmax];
Vom folosi și variabilele prim și ultim .Acestea reprezintă adresele în care sunt memorate primul și ultimul nod, variabila p care reprezintă adresa unui nod curent al listei(esate folosită pentru a parcurge lista), variabila n conține valoarea care se atribuie câmpului cu informații, variabila nr_elem reprezintă numărul de noduri ale listei, vectorul liber reprezintă o hartă a nodurilor libere( liber[p]=1 dacă nodul cu indicele p este liber sau liber[p]=0 dacă nodul cu indicele p este ocupat).
Observații:
listă vidă: deocamdată avem că nodurile prim și ultim nu există, iar indicii lor au valoarea NULL.
listă cu un singur nod: nodul prim este și nodul ultimo și nu mai este legat de niciun alt element.
listă plină: în acest caz nu mai există locații libere în vector și numai pot fi adăugate noduri.
1.3.1. Inițializarea listei
Se va crea lista vidă în care prim și ultimo nu există și vor avea valoarea NULL, iar elementele vectorului liber vor avea valoarea 1.
Implementarea algoritmului:
void init(adr &camp, adr &ultimo)
{ultim=prim=NULL; nr_elem=0;
for(adr p=1;p <=Nmax;p++) liber[p]=1;}
1.3.2. Alocarea memoriei
Vom adăuga noduri în listă și mai întâi trebuie allocate zone de memorie.
Implementarea algoritmului:
adr aloc_mem()
{adr p;
for(adr p=1;!liber[ p];p++)
liber[p]=0;nr_elem++;
return p;}
1.3.3. Crearea
Trebuie să cunoaștem adresa primului nod, de aceea vom adăuga primul nod în lista vidă:
1. Se adaugă primul nod (nodul prim).
2. Cât timp mai există informație execută: se adugă un nod în listă.
1.3.4. Adăugarea primului nod în listă
Spațiul alocat este prima poziție din vector( poziția cu indicele 0). Nodurile prim și ultim au valoarea 1. Nodul prim nu mai este legat de alt nod. Pșii sunt:
1. Se alocă memorie pentru nodul prim.
2. Se scrie informația în nodul prim.
3. Adresei de legătură a nodului prim I se adribuie valoarea NULL.
4. Nodului ultim I se atribuie adresa nodului prim.
Implementarea algoritmului:
void adaugp(adr &prim, adr &ul, int n)
{ prim=aloc_mem(); lista[prim].info=n; lista[prim].urm=NULL; ul=prim;}
1.3.5. Adăugarea unui nod în listă
Aici sunt trei cazuri:
adăugarea în fața primului nod.
adăugarea după ultimul nod.
adăugarea în interiorul listei.
În toate cele trei cazuri, adăugarea se poate realiza doar dacă lista nu este plină.
1. Adăugarea în fața primului nod.
Pașii sunt următorii:
1. Se alocă memorie pentru nodul p.
2. Se scrie informația în nodul p.
3. Dacă lista este vidă, nodul p adăugat va fi și ultimo.
4. Nodul p se leagă de nodul prim.
5. Nodul p devine nodul prim.
Implementarea algoritmului:
void adaugî(adr &prim; adr &ul; int n)
{ adr p; p=aloc_mem();
lista[p].info=n; lista[p].urm=prim;
if (este_vidă(prim)) ul=p;
prim=p;
}
2. Adăugarea după ultimul nod.
Pașii sunt următorii:
1. Se aloca memorie pentru nodul p.
2. Se scrie informația în p.
3. Nodul p este nod terminal.
4. Nodul ultimo se leagă de p.
5. Dacă lista este vidă, nodul p va fi și prim.
6. Nodul p devine nodul ultimo.
Implementarea algoritmului:
void adaugd(adr &prim; adr &ul; int n)
{adr p; p=aloc_mem();
lista[p].info=n; lista[p].urm=NULL;
lista [ul].urm=p;
if (este_vidă) prim=p;
ul=p;
}
3. Adăugarea în interiorul listei.
Se poate face în două feluri: după nodul din poziția q sau înainte de nodul din poziția q.
Adăugarea după nodul din poziția q:
Pașii sunt următorii:
1. Se alocă memorie pentru nodulp.
2. Se scrie informația în p.
3. Nodul p se leagă de succesorul nodului q.
4. Nodul q se leagă de nodul p care se adaugă.
5. Dacă q a fost ultimul nod, p devine nodul ultimo.
Implementarea algoritmului este următoarea:
void adaugă1(adr s; adr &ultim; int n)
{ adr p; p=aloc_mem();
lista[p].info=n; lista[p].urm=lista[q].urm; lista[s].urm=p;
if (lista[p].urm=NULL) ultim=p;}
Adăugarea în interiorul listei înainte de nodul din poziția s:
Vom găsi predecesorul nodului s de nodul p. Dar în listă nu vom insera nodul p înainte de nodul s, ci îl vom insera după el.
Pașii sunt următorii:
1. Se alocă memorie pentru nodul p.
2. Se copiază informația din nodul q în nodul p.
3. Se scrie în nodul q noua informație.
4. Nodul p se leagă de succesorul nodului q.
5. Nodul q se leagă de nodul p adăugat.
6. Dacă q a fost ultimul nod, nodul p adăugat devine nodul ultimo.
Implementarea algoritmului:
void adaugăf(adr q; adr &ul; int n)
{adr p; p=aloc_mem();
lista[p].info=lista[q].info< lista[q].info=n;
lista[p].urm=lista[q].urm; lista[q].urm=p;
if (lista[p].urm)==NULL) ul=p;
}
1.3.6. Parcurgerea
Se vizitează fiecare nod al listei, pornind de la primul nod.
Implementarea algoritmului:
void parcurge( adr prim)
{for(adr p=prim; p!=NULL; p=lista[p].urm)
}
1.3.7. Căutarea unui nod în listă
Putem căuta un nod care îndeplinește o anumită condiție sau un nod de pe o anumită poziție.
În primul caz, se parcurge lista începând de la primul nod pană se găsește nodul care îndeplinește condiția respectivă sau până s-a ajuns la finalul listei.
Implementarea algoritmului:
adr caut(adresa prim)
{for(adr p =prim;p!=NULL && !condiție; p=lista[p].urm)
return p;
}
În al doilea caz, se caută un nod care se găsește pe poziția poz. Se parcurge lista începând cu primul nod până când s-au parcurs poz noduri sau s-a ajuns la sfârșitul listei.
Implementarea algoritmului:
Adresa caut(adr prim, int poz)
{adr p=prim; int nr=1;
if (poz>nr_elem) return NULL;
else for(nr<poz; p=lista[p].urm; nr++)
return p;
}
1.3.8. Eliminarea unui nod din listă
Eliminarea se poate face numai dacă lista nu este vidă.
După eliminarea nodului respective, se va elibera zona de memorie a nodului eliminat.
Avem următoarele trei cazuri:
1. Eliminarea primului nod.
2. Eliminarea ultimului nod.
3. Eliminarea unui nod din interiorul listei.
1. Eliminarea primului nod.
Pașii sunt următorii:
1. Se salvează adresa nodului prim în q.
2. Succesorul nodului prim devine nodul prim.
3. Se eliberează zona de memorie de la adresa memorată în q.
Implementarea algoritmului:
void eliminăp(adr &prim)
{adr q=prim; prim=lista[prim].urm; eliberează(q);}
2. Eliminarea ultimului nod.
Pașii sunt următorii:
1. Se salvează adresa nodului ultimo în variabila q de tip adresa.
2. Se caută predecesorul ultimului nod prin parcurgerea listei de la primul la predecesorul nodului terminal.
3. Predecesorul nodului ultimo devine nod terminal.
4. Predecesorul nodului ultimo devine nodul ultimo.
5. Se eliberează zona de memorie de la adresa memorată în q.
Implementarea algoritmului:
void eliminău(adr prim, adr &ul)
{adr p,q=ul;
for (p=prim; lista[lista[p].urm].urm!=NULL< p=lista[p].urm)<
lista[p].urm=NULL;ul=p;eliberează(q);}
3. Eliminarea unui nod din interiorul listei.
Pașii sunt următorii:
1. Se salvează adresa succesorului lui p în variabila q de tip adresa.
2. Se copiază în nodul p toată informația din succesorul lui.
3. Se eliberează zona de memorie de la adresa memorată în q.
4. Dacă succesorul nodului p era nodul ultim, atunci nodul p devine nodul ultimo.
Implementarea algoritmului:
void el(adr p, adr &ul)
{adr q=lista[p].urm;
lista[p].info=lista[q].info<;lista[p].urm=lista[q].urm;
eliberează(q);
if (lista[p].urm==NULL)ul=p;}
1.4. Stiva
Accesul la nodurile stivei se face numai pe la vârf. Stiva se mai numește și LIFO (Last in First out), deoarece ultimul nod imserat este primul nod extras.
Implementarea stivei se poate face cu alocare înlănțuită sau cu alocare secvențială. Cea mai simplă implementare este cea secvențială- cu ajutorul unui vector. Elementele vectorului pot fi date elementare sau structure de date:
const unsigned Nmax=120;
typedef<tip data> nod;
nod stiva[Nmax+1], val;
unsigned vf,baza;
Variabilele vf și baza reprezintă indicle poziției celor două extremități. Variabila val este de același tip ca și informația din nodul stivi. Tipul nod poate fi un tip de bază sau un tip de structură de date.
Prelucrarea stive ise face de la vârf către bază.
Se prelucrează întptdeauna nodul din vârful stivei. Accesul la informația din acest nod se face cu stiva[vf].
1.4.1. Inițializarea stivei
Prin acest algoritm se creează stiva vidă, nodul vârf nu există, iar vf=NULL.
Implementarea algoritmului:
void init( unsigned &vf)
{vf=NULL;}
1.4.2. Adăugarea unui nod în stivă
Adăugarea se poate realize doar dacă stiva nu este plină.
Pașii sunt următorii:
1. Se alocă spațiu de memorie pentru noul nod, prin incrementarea vârfului listei.
2. Se atribuie nodului din vârf noua informație.
Implementarea algoritmului:
void adaugă(unsigned &vf, nod val)
{if (!vf=Nmax) {vf++; sriva[vf]=val;}
}
1.4.3. Extragrea unui nod din stivă
Putem elimina noduri din stivă doar dacă stiva nu este vidă. Nodul se elimină prin coborârea vârfului în stivă.
Implementarea algoritmului:
void extrage(unsigned &vf)
{if (!vf==NULL) vf–;}
1.4.4. Prelucrarea stivei
Prin aceasta, se consult informația din fiecare nod al stivei. Pentru a ajunge la un anumit nod, trebuie extrase toate nodurile până la acesta.
Implementarea algoritmului:
void prelucrare(unsigned &vf)
{while !vf==NULL) extrage(vf);}
1.5. Coada
Cele două extremități ale cozii se numesc cap și vârf( nodul prim) , respectiv sfârșit sau bază(nodul ultim).
Adăugarea se face prin nodul ultimo, iar extragerea unui nod se face numai prin nodul prim. Coada se mai numește și FIFO( First In First Out).
Implementarea cozii se poate face cu alocare înlănțuită sau cu alocare secvențială.
Cea mai simplă implementare este cea secvențială, cu ajutorul unui vector:
const unsigned Nmax=120;
typedef<tip data> nod;
nod coada[Nmax+1], val;
unsigned ultim, prim;
Prelucrarea unei cozi se face de la nodul prim către nodul ultim. Accesul la informația din acest nod se face cu coada[prim].
Pentru coada vidă( coada care nu are nici un nod) considerăm următoarea funcție:
int este_vidă( unsigned prim, unsigned ultim)
{return (ultim==NULL)//(ultim<prim);}
Pentru coada plină considerăm următoarea funcție:
int este_plină(unsigned ultim)
{return ultim==Nmax;}
1.5.1. Inițializarea cozii
Se creează coada care conține un nod. Nodurile prim și ultimo vor ava indicele 1, iar numărul de noduri k=1.
Implementarea algoritmului:
void init(unsigned &prim, unsigned &ultimo, unsigned &k, nod val)
{prim=ultim=1; k=1; coada[ultim]=val;}
1.5.2. Adăugarea unui nod în coadă
Putem adăuga un nod doar dacă coada nu este plină.
Pașii sunt următorii:
1. Se alocă spațiu pentru nodul care va fi adăugat.
2. Se atribuie nodului adăugat informație.
3. Se incrementează cu 1 numărul de elemente din coadă.
Implementarea algoritmului:
void adaugă(unsigned &ultim, unsigned &k, nod val)
{if(!este_plină(k))
{if (ultim==Nmax) ultim=1; else ultim++;
coada[ultim]=val< k++;}}
1.5.3. Extragerea unui nod din coadă
Pentru a extrage un nod din coadă, trbuie ca aceasta să nu fie vidă.
Pașii sunt următorii:
1. Se elibreazp spațiul ocupat de nod.
2. Se decrementează cu 1 numărul de elemente din coadă.
Implementarea algoritmului:
void extrage(unsigned &prim, unsigned &k)
{if (!este_vidă(k))
{if (prim==Nmax) prim=1; else prim++;
K–;}}
1.5.4. Prelucrarea cozii
Prin acest algoritm se consultă informația din fiecare nod al cozii. Deoarece nu poate fi consultată decât informația din capul cozii, pentru a ajunge la un nod, trebuie să se extragă toate nodurile până la el.
Implementarea algoritmului:
Void prelucrare(unsigned &prim, unsigned &k)
{while (!este_vidă(k)){extrage(prim,k);}}
Capitolul 2
Metode și tehnici de programare
2.1. Metoda Divide Et Impera
Această metodă este o tehnică prin care se împarte o problemă de dimensiune mare în mai multe probleme de dimensiune mică, până când problemele obținute se pot rezolva succesiv și independent. Apoi vom combina soluțiile pentru a obține, în final, soluția problemei date.
Exemplu: Fie șirul (x1,x2,…,xn). Împărțim șirul dat în două subșiruri (x1,x2,…,xm) și (xm+1,…,xn) și prelucrăm șirurile obținute. Deci am obținut două subprobleme de același gen.
Dar în prelucrarea șirului (x1,…,xm) avem următoarele situații:
subșirul se poate prelucra direct.
nu poate fi prelucrat direct și va fi descompus.
Analog pentru (xm+1,…xn). În continuare, pentru subșirurile obținute anterior putem avea aceleași situații. Această descompunere va dura până când obținem șiruri direct prelucrabile.
Așadar, la fiecare pas va fi analizat un subșir de forma (xp,…,xq). Presupunem că p,qN*, p,q{1,2…,n}, mN*, m{p,…,q-1} astfel încât prelucrarea șirului (xp,…,xq) să se poată face prelucrând subșirurile (xp,…,xm) și (xm+1,…,xq). Deci putem scrie un subprogram recursiv Divide_Et_Impera(p,q:integer) care ”tratează” subșirul (xp,…xq).
PROBLEME:
1) Să se determine maximul dintr-un șir de numere.
Fie șirul (v[1],v[2],…,v[n]), n numărul de elemente. Împărțim problema în două subprograme. Împărțim vectorul în două ”jumătăți de vector”: primul subvector va conține elementele aflate până la poziția d mijloc, iar al doilea elementele de după poziția de mijloc. Vom determina elementul maxim al fiecăruia din cei doi subvectori, apoi maximul întregului vector va fi maximul din cele două valori. Dar, dacă primul subvector nu s-a redus la un singur elemen, va trebui descompus în două jumătăți. La fel pntru al doilea subvector. Descompunerea va continua până obținem subvectori cu un singur element.
Presupunem că la un anumit pas studiem vectorul (v[p],…,v[q]). Vom plca de la vectorul inițial (v[1],…,v[n]), deci p=1, q=n. Poziția de mijloc este mij=[], iar subvectorii vor fi: (v[p],…,v[mij]) și (v[mij+1],…,v[q]).
Exemplu: Fie v=(-2,8,-3,5,1,-9), n=6. Notăm subvectorii obținuți (v1),(v2),(v11),…
P=1 2 3 4 5 6=q
mij:= []=3 => (v1)
(v2)
(v1) mij:=[]=2 => (v11)
(v12)
(v2) mij:=[]=5 => (v21)
(v22)
(v11) mij:= []=1 => (v111)
(v112)
(v21) mij:=[] =4 => (v211)
(v212)
Vom reconstitui soluția în ordine inversă:
max(v211)=4
max(v212)=0
max(v21)=max(v211,v212)=4
max(v111)=-3
max(v112)=7
max(v11)=7
max(v22)=-10
max(v2)=4
max(v12)=-4
max(v1)=7
max(v)=7
Observăm că vectorii au un singur element atuncicând p=q.
Implementarea algoritmului:
#include<iostream>
using namespace std;
int v[50],n;
int divide_max(int p,int q)
{
int mij,max1,max2;
if(p==q) return v[p];
else
{
mij=(p+q)/2;
max1=divide_max(p,mij);
max2=divide_max(mij+1,q);
if (max1>max2) return max1;
else return max2;
}
}
int main()
{
cout<<”n=”;cin>>n;
for(int i=1; i<=n; i++)
{ cout << "v["<<i<<"]=";
cin >>v[i]; }
cout <<"\n Valoarea maxima este:" << divide_max(1,n);
return 0;}
Fig.13 Maximul dintr-un șir de numere
Fig. 14 Rularea algoritmului de determinare a maximului dintr-un șir de numere
2) Problema turnurilor din Hanoi: Se dau trei tije X, Y, Z și n discuri de diferite dimensiuni pe tija X, în ordinea descrescătoare a diametrelor lor, formând un turn. Să se mute cele n discuri pe tija Y prin intermediul lui Z, respectând următoarele reguli:
– în fiecare mișcare se mută un singur disc.
– un disc nu poate fi așezat peste unul de diametru mai mic.
Simbolizăm prin MN mutarea de pe tija M pe tija N.
Se poate demonstra prin inducție matematică faptul că metoda necesită 2n-1 mutări.[1]
n=1 => mutarea XY
n=2 => Notăm cu D1 discul de la baza lui X și cu D2 discul de deasupra lui D1. Ne folosim de tija Z actfel:
mutăm pe D2 de pe X pe Z( mutarea XZ)
mutăm pe D1 de pe X pe Y( mutarea XY)
mutăm pe D2 de pe Z pe Y( mutarea ZY).
n>2 => – mutăm n-1 discuri de pe X pe Z, utilizând Y intermediară
mutarea discului rămas de pe X pe Y (XY)
mutăm cele n-1 discuri de pe Z pe Y prin X intermediară
Notăm H(n,X,Y,Z) mutarea a n discuri de pe X pe Y prin Z.
H(n,X,Y,Z)= XY, n=1
H(n-1,X,Z,Y), XY, H(n-1,Z,Y,X), n>1
Exemplu: n=2 => H(2,X,Y,Z)=H(1,X,Z,Y), XY, H(1,Z,Y,X)= XZ, XY, ZY.
Implementarea algoritmului:
include <iostream>
using namespace std;
char A,B,C;
int n;
void hann(int n, char A, char B, char C)
{
if (n==1) cout<<A<<B;
else
{
hann(n-1,A,C,B);
cout<<A<<B;
hann(n-1,C,B,A);
}
}
int main (void )
{
cout<<”n=”;cin>>n;
A=’a’; B=’b’; C=’c’ ;
hann(n,A,B,C);
}
Fig. 15 Turnurile din Hanoi
Fig. 16 Rularea algoritmului Turnurile din Hanoi
[1]. Ioan Odăgescu/Cristina Copos/Daniel Luca/Felix Furtună/Ion Smeureanu-Metode și tehnici de programare,p.125
2.2. Metoda backtracking
Această metodă se folosește în cazul problemelor în care soluția este un vector t=(t1,…tn)P=P1xP2…xPn, unde:
P1,P2,…,Pn sunt mulțimi finite și nevide, elementele lor aflându-se într-o relație de ordine bine stabilită.
între componentele t1,…,tn ale vectorului x sunt precizate relații ( condiții interne).
S se numește spațiul soluțiilor posibile.
soluțiile posibile ce îndeplinesc condițiile interne se numesc soluții rezultat.
o variană este:
se generează succesiv toate soluțiile posibile.
Pentru fiecare soluție posibilă generată se verifică dacă satisface condițiile interne și se rețin cele ce satisfac aceste condiții.
PROBLEME:
1) Problema celor opt dame: să se genereze toate așezările posibile a opt dame pe table de șah astfel încât acestea să nu se atace reciproc. Să se generalizeze problema pntru n dame pe o tablă de nXn.
#include <iostream.h>
#include <stdlib.h>
using namespace std;
int n,v[100],sol;
void afisare()
{int i,j;
sol++; cout<<"\n Solutia: "<<sol;
for (i=1;i<=n;i++)
{for (j=1;j<=n;j++)
if (v[i]==j) cout<<"D ";
else cout<<"_ ";
}
}
int valid(int k)
{int i;
for (i=1;i<=k-1;i++)
if ((v[i]==v[k])||(abs(v[k]-v[i])==(k-i)))
return 0;
return 1;}
int solutie(int k)
{if (k==n)
return 1;
return 0;}
void BK(int k)
{int i;
for (i=1;i<=n;i++)
{v[k]=i;
if (valid(k)==1)
{if (solutie(k)==1)
afisare();
else
BK(k+1);
}
}
}
int main()
{cout<<"n= ";cin>>n;
BK(1);
}
Fig. 17 Problema damelor
Fig. 18 Rularea algoritmului de așezare a damelor
2) Avem la dispoziție 6 culori: alb, galben, roșu, verde, albastru și negru. Să se precizeze toate drapelele tricolore care se pot proiecta, știind că trebuie respectate regulile:
Orice drapel are culoarea din mijloc galben sau verde;
Cele trei culori de pe drapel sunt distincte.
#include <iostream>
#include <fstream>
using namespace std;
int x[50],a[50][50];
int n, nrsol;
void citeste()
{ifstream f("fis.in");
f>>n;
int i,j;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
f>>a[i][j]; }
void scrie()
{ int i;
nrsol++;
cout<<endl<<"––––––-\n";
cout<<endl<<"Solutia "<<nrsol<<endl;
for(i=1;i<=n;i++)
cout<<i<<" ";
cout<<endl;
for(i=1;i<=n;i++)
cout<<x[i]<<" "; }
int valid(int k)
{ int i;
for(i=1;i<k;i++) if(a[i][k]==1 && x[i]==x[k])return 0;
return 1; }
void back(int k)
{ if(k==n+1)scrie();
else
for(int i=1;i<=4;i++)
{ x[k]=i;
if(valid(k))back(k+1);} }
int main()
{ citeste();
back(1);
return 0;
}
Fig. 19 Colorarea drapelului
Fig. 20 Algoritmul de colorare a drapelului
2.3. Metoda Greedy
Denumirea metodei provine din limba engleză, cuvântul ”greedy” însemnând ”lacom”. Se aplică în special la problem de maxim sau minim, la problem de optimizare. Presupunem că avem o mulțime A={x1,…,xn}, dorim să determinăm B⸦A, care să corespundă unor criteria date și să fie optimă.
Metoda Greedy presupune parcurgerea elementelor lui A, iar fiecare element va fi inclus în B dacă satisface criteriile. După includere, unele elemente pot fi eliminate pentru determinarea soluției optime.
Cei doi pași ai metodei sunt:
parcurge A; fie x elemntul current.
include pe x în B dacă satisface criteriile sau înlocuiește cu x un elememnt din B dacă astfel obținem soluția optimă.
PROBLEMA:
Cele mai mari două elmente ale unui șir.
#include<fstream>
using namespace std;
int main()
{
int n,a,max1,max2,i,t;
ifstream in(“maxi.in“);
ofstream out(“maxi.out”);
max1=max2=INT_MIN;
in>>n;
for(i=1;i<=n;i++)
{
in>>a;
if (a>max1) max1=a;
if(max2<max1)
{
t=max1; max1=max2; max2=t;
}
}
out<<max1<<’ ‘<<max2;
in.close();
out.close();
return 0;
}
Exemplu:
Tabel 1 Fișiere de intrare/ieșire
Fig. 21 Cele mai mari două elemente ale unui șir
Fig.22 Rularea algoritmului de determinare a celor mai mari două elmente ale unui șir
Fig. 23 Rularea algoritmului de determinare a celor mai mari două elmente ale unui șir
2.4. Teoria grafurilor
2.4.1. Grafuri neorientate
Numim graf neorientat o pereche ordonată de mulțimi G=(Y,V), unde Y este o mulțime finită și nevidă de elemente numită vârfuri sau noduri, iar V este o mulțime de perechi din Y numite muchii sau arce.
Exemplu de graf neorientat:
Fig. 24 Graf neorientat
Reprezentarea grafurilor se poaterealiza folosind matricea de adiacență, lista vecinilor sau vectorul de muchii.
Parcurgerea grafurilor se face în două moduri:
1. Metoda BF în lățime ( Breadth First).
Se pleacă de la un vârf inițial i, se vizitează vecinii lui i, apoi vecinii acestor vecini până când se vizitează toate vârfurile. Se folosește tipul coadă (alocată static).
Pentru exemplul de mai sus , BF: 1,2,3,4
Implementarea algoritmului:
#include<iostream>
using namespace std;
int a[30][30];
int cod[30],viz[30];
int i, n, el, pl, j, muchii, x, y, p, u;
int main()
{
cout<<"nr noduri = "; cin>>n;
cout<<"nr muchii="; cin>>muchii;
for(i=1; i<=muchii; i++)
{ cout<<"x ="; cin>>x;
cout<<"y=" ; cin>>y;
a[x][y]=1; a[y][x]=1; }
for(i=1; i<=n; i++) viz[i]=0;
cout<<" nodul de plecare este:"; cin>>pl;
viz[pl]=1; cod[1]=pl;
p=1; u=1;
while(p<=u)
{ el=cod[p];
for(j=1;j<=n;j++)
if((a[el][j]==1)&&(viz[j]==0))
{ u=u+1;
cod[u]=j;
viz[j]=1; }
p=p+1;
}
for(i=1; i<=u; i++) cout<<cod[i]<<" ";
}
Fig. 25 Metoda BF
Fig. 26 Rulare metoda BF
2. Metoda DF în adâncime (Depth First).
Se pleacă de la un vârf inițial I și se parcurge în ordine primul vecin al lui I (fie el j), apoi primul dintre vecinii lui j (dacă există). Dacă nu există, facem un pas înapoi și luăm următorul vecin al lui i( dacă există). Se folose;te tipul stiv[.
Pentru exemplul de mai sus, DF: 1,2,3,4.
Implementarea algoritmului:
#include<iostream>
using namespace std;
int a[40][40];
int cod[40],viz[40];
int i,n,plecare,j,muchia,x,y,u;
void parc_latime(int i)
{ for(int j=1;j<=n;j++)
if((a[cod[i]][j]==1)&&(viz[j]==0))
{ u=u+1;
cod[u]=j;
viz[j]=1; }
if(i<=u) parc_latime(i+1); }
int main()
{ cout<<"n="; cin>>n;
cout<<"m="; cin>>muchia;
for(i=1; i<=muchia; i++)
{ cout<<" x y "; cin>>x>>y;
a[x][y]=1;a[y][x]=1; }
for(i=1; i<=n; i++) viz[i]=0;
cout<<" nod de plecare"; cin>>plecare;
viz[plecare]=1;
cod[1]=plecare;
u=1;
parc_latime(1);
for(i=1;i<=u;i++)
cout<<cod[i]<<" "; }
Fig. 27 Metoda DF
Fig. 28 Rulare metoda DF
2.4.2. Grafuri orientate
Se numește graf orientat o pereche ordonată de mulțimi G=(X,U), unde X este o mulțime finită și nevidă de elemente numite noduri, iar U reprezintă o mulțime de perechi ordonate de elememte distinct din X numită mulțimea arcelor.
Exemplu:
Fig. 29 Graf orientat
Reprezentarea grafurilor orientate se face cu ajutorul matricei de adiacență, matricea nod-arc sau matricea drumurilor.
Algoritmul Roy-Warshall( pentru matricea drumurilor):
#include<fstream.h>
int k,r,p,x[80],a[80][80],p[80];
fstream f("graf1.in",ios::in);
fstream g("graf1.out",ios::out);
void citire()
{
int x,y;
f>>p>>r;
for(int i=1;i<=r;i++)
{
f>>x>>y; a[x][y]=1;
}
}
void roy_w()
{
int i, j, k;
for(k=1;k<=p;k++)
for(i=1;i<=p;i++)
for(j=1;j<=p;j++)
if(i!=j)
if(a[i][j]==0)
a[i][j]=a[i][k]*a[k][j];
}
void afisare()
{
for(int i=1;i<=p;i++)
{
g<<endl;
for(int j=1;j<=p;j++)
g<<a[i][j]<<" ";
}
}
int main()
{
citire();
roy_warshall ();
afisare();
}
Fig. 30 Algoritmul Roy-Warshall
Fig. 31 Rulare algoritmul Roy-Warshall
Fig. 32 Rulare algoritmul Roy-Warshall
Capitolul 3
Metode moderne versus metode tradiționale de predare-învățare-evaluare
3.1. Obiectivele cercetării
Scopul acestei cercetări este acela de a compara metodele didactice tradiționale cu metodele moderne de predare-învățare-evaluare, în vederea stabilirii impactului pe care acestea îl au asupra elevilor în procesul de învățământ.
Obiectivele cercetării sunt:
Stabilirea celor două clase de elevi care participă la cercetare.
Identificare nivelului inițial al elevilor prin intermediul unor teste inițiale.
Realizarea unui program de cercetare prin planificarea unor activități didactice specifice prin care să iasă în evidență îmbogățirea cunoștințelor elevilor.
Aplicarea unor metode care să dezvolte capacitatea de elaborare a algoritmilor de către elevi.
3.2. Metodele cercetării
Metoda observării: au fost realizate fișe de observare și scală de verificare.
Metoda exercițiului: elevii au primit fișe de lucru.
Învățarea prin descoperire: este tot o strategie tradițională care oferă elevilor posibilitatea de a dobândi cunoștințe prin muncă proprie.
Metoda ciorchinelui: în orele de recapitulare, elevii au realizat împreună cu profesorul un ciorchine specific lecției respective.
Turul galeriei: elevii au colaborat și au observat activitatea colegilor lor.
Brainstormingul: această metodă modernă ajută la crearea de idei inovatoare, folosind o exprimare liberă, fără bariere.
Conversația
Explicația
Problematizarea
Metoda cubului
Chestionare
Mozaicul
3.3. Organizarea cercetării s-a efectuat la Liceul Iulia Zamfirescu, din orașul Mioveni, pe două clase de elevi, aIX-a A și a IX-a C, în trei etape:
prima etapă a fost reprezentată de testări inițiale
etapa experimentală
etapa finală.
Pentru alegerea metodelor didactice potrivite trebuie să se aibă în vedere nivelul inițial al elevilor, mijloacele de care dispune laboratorul de informatică. Cu acestea trebuie stârnit interesul și creativitatea elevilor, dorința lor de afirmare, de asimilare de noi cunoștințe într-un domeniu de mare actualitate în zilele noastre.Există întotdeauna avantaje, dar și dezavantaje în alegerea metodelor, a mijloacelor, combinarea acestora, dar trebuie pus în balanță beneficiul acestora.
Cadrul didactic la disciplina informatică trebuie să fie tot timpul informat, să cunoască noutățile, elementele de actualitate, să știe să trezească interesul copiilor.
Societatea actuală este o societate informatizată, o societate care presupune utilizarea pe scară largă a tehnicilor informatice. În aceste condiții, școlii îi revine o sarcină importantă, aceea de a-i învăța și obișnui pe elevi cu noile tehnologii astfel încât să fie capabili să se integreze în societate după terminarea școlii.
3.4. Nivelul inițial al clasei.
Pentru a putea fi făcută o analiză comparativă, a fost stabilită clasa a IX-a A lot de control, cu un număr de 20 de elevi, dintre care 11 fete și 9 băieți(Tabel 1) și clasa a IX-a C lot experimental, cu un număr de 20 elevi, dintre care 9 fete și 11 băieți(Tabel 2).
Tabel2.Clasa a IX-a A
Tabel 3. Clasa a IX-a C
Toți elevii au vârsta de 15 ani și locuiesc în orașul Mioveni.
Elevii și-au însușit, ca și nivel inițial: aplicații cu structuri de bază, algoritmi elementari, prelucrarea unor secvențe de valori, mediul Code Blocks, fișiere text, noțiuni teoretice cu privire la datele structurate în tablouri unidimensionale.
Pentru identificarea nivelului elevilor, va fi dat un test inițial, cu ajutorul căruia profesorul va ști gradul de cunoaștere a noțiunilor de până acum ale elevilor.
TEST DE EVALUARE
Disciplina INFORMATICĂ
Clasa a IX-a
Care din expresiile de mai jos C/C++ este echivalentă cu expresia următoare:
((a>2) && (a<12)) || (a==b)
a. ((a>2) || (a<12)) && (a==b) b. !((a<=2) || (a>=12)) || (a==b)
c. ((a>2) || (a<12)) && (a!=b) d. !(a<2 || a>12) && (a!=b) (7p)
Se consideră algoritmul alăturat, descris în pseudocod:
citește număr
s=10;
cât timp număr>0 execută
dacă număr%10<s atunci
s=număr%10
altfel
s= -1
număr=[număr/10]
scrie s
Scrieți valoarea care se afișează, în urma executării algoritmului, dacă se citește pentru număr valoarea 1854. (13p)
Scrieți cea mai mare valoare de 3 cifre distincte care poate fi citită pentru număr astfel încât să se afișeze valoarea -1. (5p)
Scrieți în pseudocod un algoritm echivalent cu cel dat în care să se înlocuiască structura cât timp …..execută cu o structură repetitivă cu test final. (13p)
Scrieți programul C/C++ corespunzător algoritmului dat. (11p)
Se citesc două numere naturale x și y de la tastatură. Să se realizeze un program în C++, care determină cel mai mic multiplu al celor două numere. (16p)
Se citește un număr natural n de la tastatură. Să se realizeze un program în C++ care descompune în factori primi numărul n. (15p)
Din oficiu se acordă 10 puncte.
În urma aplicării testului inițial s-au evidențiat următoarele aspecte:
Clasa a IX-a A
media generală a clasei:7,77
ponderea(%) notelor sub 5(cinci) din numărul total al elevilor evaluați:0%
ponderea(%) notelor între 5 și 7 din numărul total al elevilor evaluați 30%
ponderea(%) notelor între 7 și 9 din numărul total al elevilor evaluați 45%
ponderea(%) notelor peste 9 din numărul total al elevilor evaluați 25%
Tabel 4.Note elevi clasa a IX-a A
Fig. 33 Clasa a IX-a A. Rezultate test inițial
Observăm din diagrama atașată că în jur de 40% din elevii acestei clase au lacune în pregătirea lor.
Clasa a IX-a C
media generală a clasei:7,49
ponderea(%) notelor sub 5(cinci) din numărul total al elevilor evaluați:0%
ponderea(%) notelor între 5 și 7 din numărul total al elevilor evaluați 45%
ponderea(%) notelor între 7 și 9 din numărul total al elevilor evaluați 40%
ponderea(%) notelor peste 9 din numărul total al elevilor evaluați 15%
Tabel 5.Note elevi clasa a IX-a C
Fig. 34 Tabel clasa a IX-a C . Rezultate test inițial
Observăm din diagrama atașată că în jur de 42% din elevii acestei clase au lacune în pregătirea lor.
Putem spune, în concluzie, că cele două loturi sunt aproximativ egale din punct de vedere al nivelului de cunoștințe.
Tot în aceată etapă a fost prezentat profesorilor de informatică prezenți la cerc, în primul semestru , în număr de 25 , un chestionar la care aceștia au răspuns online și au trimis rezultatul pe adresa de e-mail a profesorului de la clasă (Anexa 6) .
Răspunsurile la întrebarea 1 ”Folosiți metode moderne în activitatea didactică?” sunt redate în diagrama din fig.1:
Fig.35 Folosirea metodelor moderne în activitatea didactică
Analizând diagrama din fig.1, se poate observa că 59% dintre cadrele didactice care au participat la chestionar folosesc cu precădere metodele moderne în activitatea didactică și doar 8% dintre acestea nu utilizează aceste metode niciodată.
Ponderea răspunsurilor la întrebarea 2 ”Considerați că utilizarea metodelor moderne este importantă în activitatea didactică” sunt prezentate în diagrama din fig. 2:
Fig.36 Importanța utilizării metodelor moderne în activitatea didactică
Din diagrama de la fig. 2 se observă că peste jumătate dintre profesorii chestionați consideră că metodele moderne sunt absolut necesare pentru îndeplinirea obiectivelor și doar 5% nu acordă importanță acestor metode.
Răspunsurile la întrebarea 3 ”În opinia dumneavoastră, utilizarea metodelor moderne contribuie la creșterea performanțelor școlare ale elevilor” sunt exprimate în fig.3 de mai jos:
Fig. 37. Creșterea performanțelor elevilor cu ajutorul metodelor moderne
Răspunsurile cadrelor didactice la întrebarea 4. ”Ați dori ca în majoritatea lecțiilor să folosiți metodele moderne îmbinate cu cele tradiționale?”sunt exprimate în procente în diagrama din fig. 4:
Fig. 38 Folosirea metodelor moderne alături de cele tradiționale
Ponderea răspunsurilor la întrebarea 5 ”Care sunt metodele utilizate de dumneavoastră la clasă?”este prezentată în diagrama din fig 39:
Fig. 39 Metode utilizate frecvent
După cum se poate observa din diagrama de mai sus, aproape jumătate dintre profesorii participanți folosesc ”turul galeriei”, fiind considerată o metodă atractivă pentru elevi și ușor de folosit de către profesori. Astfel această metodă ocupă o pondere de 44%.
Se observă că o altă metodă, ”expunerea” ocupă un loc destul de important, cu un procentaj de 28%.
Conform răspunsurilor oferite la întrebarea 6 ”În ce procent recomandați folosirea metodelor moderne față de cele tradiționale?”, observăm fig.6:
Fig. 40 Metode moderne versus metode tradiționale
Argumentările cadrelor didactice au avut ca și punct comun rezultatele elevilor. Așadar
cadrele didactice care au considerat că metodele moderne contribuie la creșterea
performanțelor școlare au susținut că elevii sunt stimulați de aceste metode, care au un efect pozitiv asupra lor și asupra calificativelor obținute de aceștia, iar cadrele didactice care au suținut opusul au afirmat că un elev care vrea să învețe, va învăța indiferent de metodele folosite.
Sintetizând rezultatele obținute în urma aplicării chestionarului adresat cadrelor didactice, se
pot constata următoarele aspecte:
majoritatea cadrelor didactice chestionate folosesc metodele moderne în
cadrul activităților didactice
cea mai frecventă metodă folosită în activitatea didactică ”turul galeriei”
Astfel, se poate consta faptul că, deși aplicarea metodelor moderne necesită o
pregătire mult mai vastă și consumă mult mai mult timp decât alte metode, cadrele didactice tind să le utilizeze.
De asemenea, se poate observa că puține cadre didactice nu folosesc aceste metode,
deoarece nu le consideră folositoare sau nu se încred în rezultatele obținute în urma aplicării lor.
Însă, folosirea metodelor moderne rămâne la libera alegere a fiecărui cadru didactic,
putând fi folosite sau nu.
Tot în această etapă s-au analizat și produsele activității elevilor, precum fișe de lucru, elaborarea unor algoritmi la calculatoare, aplicații online de programare etc., pentru a le putea compara cu cele elaborate de către elevi până la finele experimentului.
3.5. Etapa experimentală
În urma rezultatelor obținute la testul inițial și după o atentă analiză a răspunsurilor oferite de către profesori la chestionar, s-a trecut la etapa principală a cercetării, și anume , etapa experimentală.
În cadrul acestei etape a fost introdus factorul experimental, și anume, utilizarea metodelor moderne în activitatea didactică în cadrul lotului experimental, cu scopul obținerii unor noi rezultate. În lotul de control vor fi folosite aceleași metode tradiționale, fără să se intervină în vreun fel în a schimba activitatea.
La începutul fiecărei lecții, lotul experimental a fost informat cu privire la folosirea unor metode moderne, profesorul explicându-se detaliat pașii pentru fiecare metodă.
Mai întâi au fost folosite metode mai ușor de implementat , cum ar fi metoda ciorchinelui , braimstorming-ul, metoda cubului, etc., iar pe parcurs au fost introduse și alte metode mai complexe pentru a mări gradul de înțelegere a noilor achiziții, dar și pentru a a verifica nivelor elevilor de a se adapta la noi cerințe educaționale. Bineînțeles că nu a fost folosită o singură metodă în cadrul unei activități didactice, ci metodele au fost combinate pentru a stârni interesul elevilor și pentru a stimula capacitatea acestora de intuiție și creativitate.
Experimentul s-a efectuat în cadrul următoarelor teme, unde s-au aplicat diferite metode moderne:
I. Algoritmi elementari, care cuprinde următoarele activități:
prelucrarea numerelor, de exemplu prelucrarea cifrelor unui număr, probleme de divizibilitate, calculul unor expresii simple
prelucrarea unor secvențe de valori, de exemplu determinare minim/maxim, verificarea unei proprietăți, calculul unor expresii în care intervin valori din secvență, generarea șirurilor recurente
II. Algoritmi fundamentali de prelucrare a datelor structurate în tablouri, care cuprinde următoarele activități:
parcurgerea tablourilor unidimensionale
interschimbarea
deplasarea și ștergerea de elemente
elemente distince
operații cu mulțimi
III.Căutarea binară
IV. Tehnici de sortare, care cuprinde următoarele activități:
sortarea prin numărare
sortarea prin inserție directă
sortarea prin inserție binară
sortarea rapidă
sortarea prin selecție.
În cadrul activităților didactice s-au utilizat predominant următoarele metode moderne:
o Metoda ciorchinelui;
o Metoda cubului;
o Metoda mozaicului;
o Braimstormingul;
o Știu/vreau să știu/am învățat;
o Harta conceptuală;
o Turul galeriei;
o Metoda Philips 6/6.
Foarte receptivi și entuziasmați au fost elevii de metoda mozaicului care a fost aplicată de cele mai multe ori, alături de alte metode tradiționale. Aceasta este o modalitate eficientă de învățare a conținuturilor și creează interacțiuni între elevi.
De exemplu, pentru verificarea însușirii tehnicilor de sortare, la sfârșitul capitolului, a fost aplicată metoda mozaicului. Elevii au fost împărțiți în grupe de câte cinci, notate cu 1, 2, 3, 4, 5. Tehnicile de sortare au fost grupate în patru fișe, fișa A, fișa B, fișa C, fișa D, fișa E. Fiecare elev primește câte o fișă ce conține unul din numerele de la 1 la 5 (Anexa 1). Elevii se vor regrupa în funcție de litera fișei primate, realizându-se astfel grupele de experți. Elevii vor rezolva fișele primate, apoi se vor întoarce cu soluțiile în grupurile inițiale. Aici vor explica și colegilor de grupă rezolvarea subiectelor acestora. Profesorul observă pe tot parcursul activității corectitudinea informațiilor, intervenind dacă este nevoie. La final se trec pe tablă toate rezultatele corcte obținute. Profesorul adresează elevilor săi și câteva întrebări pentru a verifica nivelul de înțelegere a informațiilor noi.
La finalul orei, elevii au fost foarte entuziasmați să observe că răspunsurile lor au fost corecte sau că au înțeles de la colegii lor rezolvarea subiectelor, rămânând chiar și în pauză pe acest subiect. Profesorul a observat implicarea elevilor, creativitatea acestora și dorința lor de afirmare. Gruparea și colaborarea elevilor, fișele noi de lucru, întoarcerea acestora în grupele inițiale pentru a transmite noile informații obținute și pentru a le primi pe cele ale colegilor lor, a stârnit interesul și curiozitatea elevilor.
De asemenea, metoda ciorchinelui a fost folosită de multe ori, alături de metode tradiționale, dar și de cele moderne, atât în lecțiile de evaluare, cât și în cadrul reactualizării cunoștințelor.
Prin această metodă elevii își fixează mai bine cunoștințele, toată clasa putând participa la tablă. Elevii vor gândi liber și deschis. De exemplu, la capitolul ”Algoritmi fundamentali de prelucrare a datelor structurate în tablouri”, elevii vor construi un ciorchine plecând de la cuvantul ”tablou unidimensional” (Anexa 2). Activitatea se va sfârși după epuizarea tuturor ideilor. Elevii sunt entuziaști pentru că pot scrie tot ce le trece prin minte, fără a fi judecați.
La finalul acestui capitol, profesorul a aplicat și metoda cubului.Desigur, elevilor li s-a cerut realizarea cubului acasa din carton. Pe fețele cubului, profesorul scrie cuvintele: descrie, compară, analizează, asiciază, aplică, argumentează. Elevilor li se va scrie un algoritm ce folosește tabloul unidimensional . Elevii vor fi împărțiți în șase grupe și fiecare grupă va lucra conform cuvântului care i-a picat, algoritmul respectiv. Desigur că nu toți elevii s-au descurcat perfect, dar dorința acestora de a cunoaște rezolvarea a fost clară (Anexa 3) .
Nici metoda turului galeriei nu a lipsit, o metodă destul de frumoasă, care îi antrenează pe elevi în găsirea răspunsului, formularea de concluzii pe baza rezultatelor colegilor.
La finalul lecției de predare ”Căutarea binară”, elevii primesc de la profesor sarcina de a rezolva o problemă la calculator (Anexa 4) . Aceștia vor fi grupați câte doi, își vor salva rezolvara în folderul personal , iar la semnalul profesorului grpuele vizitează celelalte calculatoare pe rând. Își iau notițe și fac comantarii vizavi de rezolvarea acestora.
După turul galeriei, elevii își reeexaminează propriile rezolvări în comparație cu celelalte și citesc comentariile făcute de colegii lor.
La lecția ”Prelucrarea numerelor”, elevii vor fi antrenați în folosirea metodei Brainstormingului. Profesorul pune întrebarea ”Cum putem realiza algoritmul ce calculează suma cifrelor unui număr?”. Acesta va scrie pe o planșă soluțiile ce vin de la elevii săi. Tot profesorul explică de ce este important acest algoritm, cât de mult ne ajută în rezolvarea și implementarea altor algoritmi.
Pe durata desfășurării activității, elevii au participat intens la dezbateri, fiind o activitate constructivă și creativă. Profesorul le-a amintit frecvent acestora timpul rămas pentru răspunsuri. Fiecare idee este acceptată, cel care a propus-o nu a fost corectat sau criticat, profesorul scriind-o pe planșă așa cum a fost enunțată. Ideea este de a avea o cantitate cât mai mare de idei. Atunci când timpul a fost epuizat, elevii mai pun întrebări, dar numai pentru clarificare, care este dată de cel care a enunțat ideea. La final, profesorul clarifică care idei au fost bune și care nu au fost la fel da satisfăcătoare, elevii își dau și ei cu părerea.
La lecția ”Prelucrarea unei secvențe de valori”, profesorul folosește tehnica ”Știu/vreau să știu/am învățat” (Anexa 5) . Elevii primesc o fișă prin care li se cere completarea unui tabel. Aceștia trec noțiunile pe care le cunosc, ceea ce doresc ei să mai știe, informații care să-i ajute în elaborarea altor algoritmi și ceea ce și-au însușiiit la finalul lecției. De exemple, marea majoritatea au scris ca și element cunoscut algoritmii de maxim și de minim, unii au dorit să cunoască algoritmul prin care se verifică dacă un număr este prim, cel prin care să se stabilească dacă un număr este par saqu este impar. În cea de-a treia coloană , elevii au trecut noile achiziții, în funcșție de cdeea ce cunoștea până atunci fiecare.
În cazxul împărțirii elevilor pe grupe, de fiecare dată profesorul utilizează metoda Philips 6/6, pentru împărțirea acestora în funcție de dorința lor.Astfel se vor forma grupe de câte șase elevi, hotărâre luată în șase minute.
3.6. Etapa finală
În cadrul acestei etape de cercetare cele două loturi au primit un test final de evaluare pentru a se compara rezultatele obținute în urma folosirii metodelor modern de predare-învățare-evaluare, cu rezultatele obținute în urma desfășurării activităților în mod tradițional (Anexa 7) . Prin această etapă s-a urmărit accentuarea diferențelor existente între două loturi implicate în cadrul experimentului, lotul de control și lotul experimental.
Testul a fost alcătuit din patru subiecte, formulate pe baza noțiunilor studiate pe parcursul anului școlar. Subiectele au fost atât legate de tablouri unidimensionale, cât și de algoritmi elementari.
Tot în această ultimă etapă s-a desfășurat și un concurs între cele două clase ( lotul experimental și lotul de control). Concursul a fost organizat tocmai în ideea de a urmări atât informațiile de care dispun toți elevii, dar și gradul de implicare al acestora. Acest concurs a constituit încă o modalitate de evidențiere a cunoștințelor și competențelor dobândite de cele două clase. De asemenea, s-au analizat și rezultatele elevilor, realizate în cadrului acestui concurs.
Elevii celor două clase au realizat și portofolii ce conțin următoarele elemente:
fișe de lucru
prezentări PowerPoint;
teme pentru acasă individual sau pe grupe
panouri
diverse activități online
chestionare
3.6.1. Analiza și interpretarea rezultatelor evaluării finale
Realizarea cercetării a adus cu sine și trezirea unei curiozități referitoarea la parcursul
demersului aturalmve, mai exact constatarea schimbărilor semnificative survenite în urma
introducerii factorului experiemental în cadrului lotului experimental.
Finalul cercetării a avut ca punct de plecare compararea rezultatelor inițiale ale elevilor cu rezultatele finale, precum și rezultatele obținute între cele două clase pe tot parcursul derulării experimentului.
Rezultatele finale, obținute de către elevii celor două loturi sunt prezentate în tabelul :
Tabel 6. Notele obținute la finalul cercetării
Din analiza datelor prezentate în atur se poate constata faptul că, rezultatele elevilor sunt
diferite de cele de la începutul cercetării, progrese înregistrându-se la ambele loturi (experimental și de control), însă rezultate mai semnificative se regăsesc la clasa a IX-a C, adică la lotul experimental, unde s-au aplicat metode atura pe parcursul activitățiilor didactice.
Dacă la începutul cercetării, 9 elevi din clasa a IX-a C au obținut notew între 5 și 7, 8 elevi au obținut note între 7 ți 9, 3 elevi note între nouă și 10 și niciun elev nu a obținut note sub 5, la finele demersului aturalmve, aceiași elevi au înregistrat un atural, adică 1 elev a
obținut notă între 5 și 7, 11 elevi au obținut note între 7 și 9, 8 elevi au obținut note între 9 și 10 și niciun elev nu a obținut note sub 5.
Situația descrisă mai sus se regăsește în fig. :
Fig. 41 Rezultatele elevilor clasei a IX-a C obținute la cele două testări.
Comparând rezultatele inițiale ale elevilor cu rezultatele obținute la finele cercetării, în
cadrul lotului experimental, adică a IX-a C, am constatat faptul că s-au înregistrat
progrese semnificative, în special în rândul elevilor care au obținut note între 9 și 10.
Numărul elevilor care au luat note între 7 și 9 a înregistrat o creștere semnificativă, adică
de la 7 elevi la 9 elevi. Dacă la începutul cercetării 9 elevi au obținut note între 5 și 7, la final
doar 1 elev a obținut acest calificativ. De asemenea, niciun elev nu a obținut note sub 5.
Reprezentarea grafică a rezultatele comparative, între cele două testări aplicate lotului de control se poate observa în fig. :
Fig. 42 Rezultatele elevilor clasei a IX-a A obținute la cele două testări.
Observăm din atural de mai sus că s-au obținut progrese și în cadrul lotului de control, dar nu atât de semnificative.
Un success și mai mare care vizează ambele loturi îl reprezintă lipsa notelor sub 5.
Rezultatele obținute de cele două loturi la testarea finală au fost prezentate atural în fig.:
Fig.43 Rezultatele obținute Fig.44 Rezultatele obținute
la testarea finală la testarea finală
Se poate constata faptul că 80% dintre elevii, care fac parte din lotul experimental au
obținut Note între 9 și 10, aturalm cu 9% dintre elevii, care fac parte din lotul de
control. Aceste rezultate reprezintă un atural pentru elevii clasei a IX-a C și, în același timp,
un atural pentru aplicarea metodelor atura în clasa respectivă.
De asemenea, rezultatele obținute în cadrul lotului experimental la finele demersului sunt
mult mai mari decât notele obținute în cadrul lotului de control. Cumulul Notelor între 59 și 10 și a notelor între 7 și 9 obținute în cadrul lotului experimental (90%) este ridicat față de cumulul notelor din lotul de control (73%), semnificând faptul că aplicarea metodele modern au avut un
impact favorabil asupra elevilor, ducând la creșterea semnificativă a rezultatelor acestora.
Lotul de control, clasa a IX-a A, și-a îmbunătățit rezultatele însă fără salturi majore față de
evaluarea inițială.
Rezultatele comparative între cele două loturi implicate în investigație pot fi observate în fig.:
Fig. 45Rezultatele obținute de cele două clase la evaluarea finală
Cele două loturi de elevi, implicate în demersul aturalmve, au suferit modificări
semnificative de-a lungul activitățiilor, din punct de vedere al creșterii calificativelor elevilor. În
ceea ce privește lotul de control, rezultatele au crescut însă nu cu aceași pondere semnificativă ca și lotul experimental. După cum se poate observa în fig. , există o diferență semnificativă între
numărul elevilor care au obținut note între 9 și 10 între cele două loturi investigative.
Analizând produsele activității elevilor, am putut constata o creștere semnificativă și
totodată calitativă, mai ales în ceea ce privește eșantionul experimental. Odată cu aplicarea
metodelor atura, elevii și-au îndreptat atenția mult mai mult spre sarcinile de lucru din
clasă . Astfel ei au început să se exprime mai clar și cu mai mare ușurință în comunicarea orală, activitățile practice la calculator , dar și în ceea ce privește rezolvarea fișelor de lucru de lucru etc., acestea fiind mult mai complete și mai organizate. De asemenea, reușesc să surprindă esențialul cerințelor, dar și să se bucure de propriile creații, dând dovadă de creativitate și responsabilitate.
Prin intermediul acestor analize comparative (tabele, grafice), am constatat faptul că ipoteza
de la care am pornit cercetarea s-a confirmat, deoarece în urma aplicării metodelor modern e în cadrul lotului experimental, rezultatele elevilor au crescut.
Elevii și-au însușit mult mai ușor cunoștintele și și-au format și dezvoltat deprinderi mai bune.
Drept urmare, în cadrul activitățiilor didactice desfășurate în viitor, ar fi de dorit să se utilizeze mult mai mult metodele atura, deoarece influențează pozitiv rezultatele elevilor.
Metodele atura ajută generația atura nu numai să învețe ”modern”, ci să ofere
elevului ceea ce acesta așteaptă și anume inovație, libertate de exprimare, creativitate, gândire
critic, dar și munca în echipe, lucru care consolidează și coeziunea clasei.
3.6.2. CONCLUZII
Introducerea metodelor atura, în cadrul învățământului românesc permite elevului și nu numai, formarea unor capacități și deprinderi folositoare, pentru înțelegerea și realizarea unor situații autentice, precum și transformarea acestuia într-un participant atura la viața
societății.
Astfel metodele atura oferă elevilor posibilitatea explorării unor noi domenii, dobândirii de noi cunoștințe și dezvoltării de noi competențe.
Învățământul modern promovează învățarea prin participarea activă, o învățare calitativă,
bazată pe sprijin reciproc, toleranță și atura, toate urmărind îndeplinirea aceluiași scop. De aceea,
învățământul de calitate, necesită o dezvoltare a elevilor din toate punctele de vedere, bazată pe
exersarea gândirii, inteligenței, imaginației și a creativității. Acest tip de învățare promovează
angajarea operațiilor gândirii și ale imaginației, devenind pentru elev niște instrumente de sprijin înrealizarea unei noi învățării. Pentru ca acest lucru să fie posibil, elevul trebuie adaptat acestei noi schimbări, învățat să își utilizeze competențele pe care le deține, astfel încât el să reacționeze
pozitiv, ceea ce va duce implicit la o dezvoltare atural.
Învățarea prin metode atura constituie un atural pentru toate aceste lucruri, urmărind dezvoltarea la elevi a gândirii democratice prin exersarea gândirii critice, deoarece fiecare elev învață prin intermediul criticii unui comportament sau a unei situații.
Educația este singura modalitate prin intermediul căreia se pot îmbina activitățiile de
învățare cu cele ludice, formând un univers, în care elevul este principalul personaj. Doar aici,
activitățiile de învățare dau naștere unei întregi povești de viață, prin intermediul căreia elevul
participă atura la propria sa dezvoltare.
Urmărind faptele din jurul atural, constatăm faptul că, problema tuturor problemelor este
comunicarea, neputința de comunica așa cum ne dorim, de a ne exprima fără teamă, fără rețineri
atunci când avem ceva de zis. Soluția acestei atural are la bază munca elevilor în grupe,
desfășurată în cadrul activitățiilor didactice, prin care elevii își formează cele mai importante
trăsături morale atural dar și negative și anume prietenia, solidaritatea, încrederea în sine dar și în ceilalți, responsabilitatea și aturalm față de munca celor din jur. Una dintre contribuțiile principale în realizarea și atingerea acestor trăsături o are educația civică, desigur află într-o strânsă corelație cu celelalte discipline de atura.
Informatica are ca și principal scop dezvoltarea și formarea la elevi a unor deprinderi și posibilități de elaborare a algoritmilor. Urmărește formarea unei atitudini responsabile și
conștiente atât față de sine cât și față de ceilalți, având ca și principal rezultat formarea unei
personalități libere și armoniase a elevului, cetățean în devenire, care să se poată integra în societate.
Ȋn ceea ce privește rezultatele obținute în urma desfășurării cercetării, se poate afirma faptul că ipoteza formulată s-a adeverit, adică folosirea metodelor atura în cadrul activităților didactice va avea ca rezultat întotdeauna creșterea rezultatelor la învățătură ale elevilor.
Elevii vor da dovadă de o mai mare ușurință, atât în ceea ce privește activitatea de învățare, cât și în ceea ce privește formarea unui limbaj și a unui comportament civic adecvat.
Prin intermediul acestei lucrări, am încercat să demonstrez eficența metodelor atura în cadrul demersului didactic, prin calitatea lor de a antrena elevii în procesul de
predare-învățare, prin capacitatea lor de a transforma un subiect pasiv într-un subiect atura, prin
interesul lor față de nevoie elevilor dar și față de nevoile cadrelor didactice.
Din rolul central pe care îl deținea cadrul didactic prin aplicarea metodelor tradiționale, odată cu implementarea metodelor atura rolul central revine elevului, cadrul didactic devenind doar un simplu supraveghetor, îndrumător. Accentul nu se mai pune pe ceea ce știe elevul, ci pe modul în care utilizează ceea ce știe, modul în care pune în practică cunoștințele deținute. Așadar, metodele atura nu sunt altceva decât o modalitate de apropiere a cadrului didactic de elev, o modalitate prin care informația devine mai accesibilă elevului, acesta înțelegând mult mai ușor conținutul informațional transmis. Informația va atura o curiozitate, pe
care elevul o va percepe ca atare, iar educația va atura o formă de manifestare, în care elevul va
deține rolul principal.
Recomandări educaționale
Ca și o concluzie asupra lucrări elaborate, dar și ca urmare a contactului cu anumite cadre
didactice,de exemplu atunci când au completat chestionarul, cu anumite activități practice, am constatat faptul că, fiecare elev este unic în felul său, activitatea de predare-învățare depinzând în mod direct de natura elevului și de dorința acestuia de implicare.
Drept urmare, din atural meu de vedere, cea mai bună recomandare educațională ar trebui
să vizeze, modul în care un cadru didactic aturalm o activitate tradițională într-o experiență de
viață, a cărui principal protagonist nu este altcineva decât elevul dornic de învățare.
ANEXE
Anexa 1
Fișă de lucru 1
1) Se consideră un vector v ce conține n numere naturale formate din cel puțin 2 cifre. Să se ordoneze crescător elementele vectorului, folosind sortarea prin numărare.
2) Se consideră un vector v ce conține n numere naturale formate din exact 3 cifre. Să se aranjeze elementele vectorului astfel:elementele care au prima cifră identică cu ultima cifră în fața vectorului urmate de celelalte elemente.
Fișă de lucru nr.2
1) Se consideră un vector v ce conține n numere naturale formate din cel puțin 2 cifre. Să se ordoneze crescător elementele vectorului, folosind sortarea prin inserție directă.
2) Se consideră un vector v ce conține n numere naturale formate din cel puțin 2 cifre. Să se ordoneze crescător elementele vectorului după cifra zecilor.
Fișă de lucru 3
1) Se consideră un vector v ce conține n numere naturale formate din cel puțin 2 cifre. Să se ordoneze crescător elementele vectorului, folosind sortarea prin inserție binară.
2) Din fișierul numere.in se citește de pe prima linie un număr natural n iar de pe următoarele linii se citesc n numere naturale ale unui vector v. Să se scrie un program care inserează înainte de fiecare element prim cel mai apropiat pătrat perfect mai mic decât el.
Fișă de lucru 4
1) Se consideră un vector v ce conține n numere naturale formate din cel puțin 2 cifre. Să se ordoneze crescător elementele vectorului, folosind sortarea prin selecție directă.
2) Construiți și afișați un vector cu numerele naturale mai mici sau egale cu n care au proprietatea de palindrom (n citit de la tastatură).
Fișă de lucru 5
1) Se consideră un vector v ce conține n numere naturale formate din cel puțin 2 cifre. Să se ordoneze crescător elementele vectorului, folosind sortarea rapidă.
2) Se consideră un vector a cu n elemente reale și două numere reale p și q. Să se scrie un program care copiază într-un vector b toate elementele din a aflate în intervalul [p,q] în ordinea în care apar ele în vector.
Anexa 2
Anexa 3
Se dă următoarea secvență:
int nș
for(i=1;i<=n;i++)
cin>a[i];
s=0;
for(i=1;i<=n;i++)
if (i%2=0))
s+=a[i];
cout<<s;
Descrie ce face algoritmul?
Compară acest algoritm cu altul asemănător făcut până acum?
Analizează ce se afișează pentru n=4 și elementele 8, -1, 3, 12.
Asociază acest algoritm cu alt algoritm asemănător lucrat până acum.
Aplică algoritmul și găsește un set de date de intrare pentru care algoritmul afișează 8.
Argumentează ce rol are condiția if (i%2=0)?
Anexa 4
Se citește un vector v cu n<=80, elemente numere atural formate din cel mult 9 cifre fiecare. Să se scrie un program care determină valoarea maximă și valoarea minimă din vector și de câte ori apare fiecare valoare în vector.
Anexa 5
Știu/vreau să știu/am învățat
Anexa 6
Chestionar adresat cadrelor didactice
Pag.1
Pag.2
Pag.3
Pag.4
Pag.5
Anexa 7
Evaluare finală la informatică
Clasa a IX-a
Se acord 1p din oficiu
Subiectul I. Care din următoarele afirmații sunt adevărate și care sunt false?
Justificați. (2 puncte)
Dimensiunea maximă a unui vector trebuie să fie o constantă.
Tipul elementelor unui vector poate fi doar un tip predefinit.
Un vector se poate inițializa în momentul declarării astfel:
int v[] = {2; 3; 4; 5; 6; 7}.
Elementele unui vector sunt numerotate de la 0.
Subiectul II. Fie următoarea secvență: (2 puncte)
int k=0,S=0;
for(int i=0; i<n;i++)
if ( v[i] >0)
{ S+ =v[i]; k++; }
cout<<S<<k;
Care vor fi valorile tiparite după execuția secvenței, dacă n=5 și elementele vectorului sunt:
v ={5, -8, -2, 6, 9}
Subiectul III. Se dă un vector cu n elemente, numere naturale. Afișați în ordine crescătoare valorile prime din vector. (3 puncte)
Subiectul IV. Alegeți varianta de răspuns care rezolvă corect și eficient tipărirea valorii maxime dintre două numere a și b citite de la tastatură: (2 puncte)
dacă a > b atunci scrie a c) dacă a > b atunci scrie a
altfel scrie b altfel dacă a < b atunci scrie b
sfârșit dacă altfel scrie ‘a = b’
sfârșit dacă
sfârșit dacă
dacă a > b atunci scrie a d) dacă a > b atunci
sfârșit dacă dacă b > a atunci scrie b
dacă a < b atunci scrie b sfârșit dacă b
BIBLIOGRAFIE
Odăgescu, I., Copos, C., Luca, D., Furtună, F., Smeureanu, I., (1994), Metode și tewhnici de programare, Editura Intact, București
Radu, L., ionescu, D., Țenea, C., (2011), Didactica informaticii, Editura Karta-Graphic, Ploiești
Miloșescu, M., (2011), Informatică, Manual pentru clasa a XI-a, Editura Didactică și pedagogică, București
Sorin, T,(1997), Bazele programării în C++, Editura L&S Infomat, București
Tomescu, I., (1975), Grafuri și programare liniară,, Editura didactică și pedagogică, București
Andonie R., Gârbacea I., (1995) , Algoritmi fundamentali, o perspectivă C++, Editura Libris,
Calude C., (1987)Teoria algoritmilor, Editura Universității București
Georgescu H., Livovschi L.,(1986) , Analiza și sinteza algoritmilor, Editura Științifică și Enciclopedică, București
Giumare C., Negreanu L., Călinoiu S., (1997), Proiectarea și analiza algoritmilor. Algoritmi de sortare, Editura All
Ivașc C., Prună M., (1995) , Bazele informaticii, Ed. Petrion
Negrescu L., (1997), Limbajul C și C++, Ed. Libris, Cluj
Pătrășcoiu O., Marian Gh., Mitroi N., Informatică – elemente de grafuri și combinatorică, metode, algoritmi și programe, Ed. All, București
Rancea D., Limbajul Pascal, (1999), Algoritmi fundamentali, Ed. Computer Libris Agora
Stoilescu D.,(1998), Manual de C/C++ pentru licee, Ed. Radial, Galați
Tomescu I.,(1994), Bazele informaticii (Manual pentru clasa a X), Ed. Didactică și Pedagogică
Tomescu I.,(1975), Grafuri și programare liniară, Ed. Didactică și Pedagogică
Tudor S.,(1996), Tehnici de programare, Ed. L&S Infomat
Wirth N.,(1976), Algorithms+Data Structures=Programs, Prentice Hall, Inc
*** www.didactic.ro
*** www.edu.ro
*** www.scribd.com
Copyright Notice
© Licențiada.org respectă drepturile de proprietate intelectuală și așteaptă ca toți utilizatorii să facă același lucru. Dacă consideri că un conținut de pe site încalcă drepturile tale de autor, te rugăm să trimiți o notificare DMCA.
Acest articol: LUCRARE METODICO ȘTIINȚIFICĂ PENTRU OBȚINEREA GRADULUI DIDACTIC I ÎN ÎNVĂȚĂMÂNT METODE DE ELABORARE A ALGORITMILOR, ASPECTE METODICE COORDONATOR… [302347] (ID: 302347)
Dacă considerați că acest conținut vă încalcă drepturile de autor, vă rugăm să depuneți o cerere pe pagina noastră Copyright Takedown.