Algoritmi Elementari
I. Introducere
Depindem de tehnologie și de calculatoare din ce în ce mai mult. Din această cauză, informatica este o disciplină de bază în sprijinirea evoluției noilor tehnologii. Pentru profesorii de informatică una dintre cele mai mari provocări o reprezintă atragerea elevilor către o disciplină ce implică o muncă constantă și dorința de a descoperi lucruri noi, de a face conexiuni cu lumea reală. Cum reușim să îi motivăm, cum reușim să îi convingem că nu va exista o lume fără tehnologie sau fară informaticieni? Trebuie să demonstrăm elevilor că informaticieni buni nu sunt doar elevii de excepție ci toți elevii care încearcă să abordeze creativ problemele din viața de zi cu zi.
Lucrarea de față propune o astfel de abordare a procesului instructiv-educativ din cadrul orelor de informatică. Lucrarea este structurată în două părți: prima parte – dedicată algoritmilor elementari – conține trei capitole: algoritmi elementari, algoritmi de sortare și algortimi din teoria grafurilor; partea a doua – de metodică – cuprinde aspecte teoretice și practice legate în principal de metoda proiectului.
Astfel, în prima parte, am prezentat noțiunea de algoritm, proprietățile algoritmilor precum și unele elemente de calculabilitate și complexitate. Capitolul Algoritmi de sortare prezintă cei mai cunoscuți algoritmi utilizați în rearanjarea elementelor unui vector. Pentru fiecare algoritm am facut o scurtă prezentare, am discutat despre complexitatea acestuia și am dat implementarea în limbajul de programare C++, utilizând aplicația software Code::Blocks. În capitolul Algoritmi din teoria grafurilor, am prezentat noțiunile teoretice despre grafurile neorientate și orientate, incluzând algorimi elementari pentru lucrul cu aceste noțiuni, implementați în C++. Majoritatea noțiunilor prezentate în acest capitol au fost utilizate în partea de metodică, fiind structura de bază pentru temele de proiect realizate la clasă.
Partea a doua cuprinde o prezentare a metodei proiectului, exemple de teme pentru proiecte, exemple practice realizate la clasă precum și o interpretare a rezultatelor implementării acestei metode la clasă.
II.1. Algoritmi elementari
II.1.1. Definirea și caracteristicile algoritmilor
Un algoritm (cuvântul are ca origine numele matematicianului persan Al-Khwarizmi) înseamnă în matematică și informatică o metodă sau o procedură de calcul, alcătuită din pașii elementari necesari pentru rezolvarea unei probleme sau categorii de probleme. De obicei algoritmii se implementează în mod concret prin programe de calculator. Din diverse motive există și algoritmi încă neimplementați, teoretici.
Nu există o definiție general acceptată pentru noțiunea de algoritm . De aceea există mai multe descrieri și caracterizari.
Prin algoritm înțelegem o mulțime ordonată și finită de pași care ajută la rezolvarea unei clase de probleme. Fiecare pas dintr-un algoritm implică efectuarea unor operații. Pentru a fi implementate pe un calculator, într-un anumit limbaj de programare, aceste operații trebuie să fie definite și efective.
Principalele caracteristici ale algoritmilor sunt: corectitudinea, finitudinea, generalitatea și completitudinea.
Există diferite criterii de clasificare a algoritmilor. De exemplu, după modul de administrare a rezultatelor în raport datele de intrare și cu cele intermediare, algoritmii se împart în: algoritmi iterativi și algoritmi recursivi
Studiul algoritmilor cuprinde următoarele etape:
1. Elaborarea algoritmilor (ceea ce implică stabilirea unor tehnici de elaborare (reguli) care, împreună cu creativitatea (intuiția) utilizatorului vor duce la soluția adecvată).
2. Exprimarea algoritmilor (se poate recurge la limbajul natural, la scheme logice, la limbaje de tip pseudocod sau de programare (universale sau specializate). De asemenea, se impune utilizarea unui anumit stil de programare (legat nu de un anumit limbaj de programare, ci de tipul limbajului și de modul de abordare a problemei)
3. Validarea algoritmilor (demonstrarea matematică a corectitudinii, independent de implementare)
4. Analiza algoritmilor (în general, se evalueaza timpul de calcul și/sau la memoria necesară)
5. Testarea programelor (care constă din depanare (debugging) și verificare (profiling).
II.1.2. Modele de calculabilitate
O procedură efectivă este o mulțime finită de acțiuni a căror execuție se termină într-un timp finit și care implică o cantitate finită de date pentru a obține un rezultat, mereu același pentru date identice.
Încercarea de definirea a noțiunii de algoritmi a condus, între anii 1930 – 1940, la apariția mai multor modele de calculabilitate:
Funcțiile -calculabile (Alonzo CHURCH și Stephen Cole KLEENE)
Mașinile Turing (Alan TURING)
Funcțiile general recursive (Kurt GÖDEL)
Sistemele Post, inclusiv mașina Post-Turing (Emil Leon POST)
Algoritmii normali Markov (N.N. MARKOV)
Lambda calculul
Definiție
O λ-functie este definită de o lambda-expresie care exprimă acțiunea funcției în argumentele ei.
Exemple: funcția f(x)=x+2: λ x. x + 2 .
numărul f(3): (λ x. x+ 2) 3
Mașina Turing
Mașina Turing este compusă din următoarele elemente (Gontineac, 08):
o bandă infinită de hârtie împărțită în locații care pot conține fiecare câte un singur caracter
un cap de citire-scriere, care se poate mișca deasupra benzii, la stânga sau la dreapta
o unitate de control, care dispune de un număr finit de reguli care indică mașinii ce să facă in fiecare moment în funcție de simbolul curent citit de pe bandă și de starea curentă a mașinii.
Structura mașinii Turnig:
Matematic, mașina Turing este definită ca fiind un sistem ( , , Q, q0, F, ) unde:
este o mulțime finită, nevidă numită alfabet de intrare
este o mulțime finită, nevidă numită alfabetul benzii
, și ;
Q este o mulțime finită, nevidă numită mulțimea stărilor mașinii
q0 Q este starea inițială
F Q este mulțimea stărilor finale (de acceptare sau de respingere)
: Q x Q x x { L , R } este funcția de tranziție, unde L denotă deplasarea la stânga iar R denotă deplasarea la dreapta a cursorului mașinii.
II.1.3. Reprezentarea algoritmilor
Există numeroase variante de reprezentare a algoritmilor. În general, cu cât acestea sunt mai sugestive pentru oameni, cu atât sunt mai greu de înțeles și interpretat pentru sistemele de calcul și invers. Cele mai frecvent folosite metode reprezentare sunt:
descrierea în limbajul natural
schemele logice
pseudocodul
limbajele de programare
II.1.4. Complexitatea algoritmilor
În rezolvarea cu ajutorul calculatorului a oricărei probleme se trece prin cele trei etape:
Analiza teoretică a problemei
Proiectarea algoritmului de soluționare
Implementarea algoritmului într-un program executabil pe calculator
Calcularea complexității algoritmilor are două abordări: abordarea teoretică și abordarea practică.
Abordarea practică:
Este realizată la nivelul implementării pe calculator
Este o metodă naturală și practică care revine la măsurarea cât mai exactă a duratei de execuție a programului
Este dependentă de limbajul de programare, performanțele hardware ale calculatorului
Abordarea teoretică:
Este realizată la nivelul algoritmului
Este ideală, robustă și independentă de:
performanțele hardware
modelul de calculabilitate
modelul
În calcularea duratei de execuție a unui program s-au impus două criterii esențiale (atât la nivelul practic cât și la nivelul teoretic):
datele de intrare
programele (algoritmii) fără subprograme (subalgoritmi)
Astfel, durata execuției unui program depinde de:
dimensiunea datelor de intrare
configurația datelor de intrare:
alfabetul de codificare
structura de date
instanța concretă a problemei
particularitățile sistemului de calcul:
limbajul de programare
performațele hardware
Calcularea timpului de rulare al programelor utilizează facilitățile oferite de elementele hardware, sistemele de operare, limbajele de programare etc.
Măsurarea exactă a timpului de execuție a programului de calculator nu este un criteriu valid pentru a descrie dificultatea / complexitatea rezolvării problemei.
O măsură mult mai utilă a timpului de execuție este dată de numărul pașilor elementari necesari execuției unui algoritm.
Nu există o masură universală pentru evaluarea timpului de execuție al tuturor algoritmilor.
Principalul criteriu este dimensiunea datelor de intrare, dată de:
lungimea
numărul lor
1. Lungimea datelor de intrare
Se disting două metode principale de evaluare a complexității algoritmilor după lungimea datelor de intrare:
(U) costul uniform
(L) costul logaritmic
Abordarea solvabilității problemelor prin costul uniform are următoarele avantaje:
complexitatea timp revine la a determina numărul total de operații executate pentru obținerea rezultatului
complexitatea spațiu revine la a determina numărul total de variabile utilizate pentru obținerea rezultatului
Abordarea solvabiliății problemelor prin utilizarea măsurii logaritmice implică calcularea costului oricărei operații elementare ca fiind suma dimensiunilor reprezentărilor binare ale operanzilor. Se pot adauga și dimensiunile reprezentării binare a adreselor locațiilor de memorie unde sunt depuse valorile operanzilor. Metoda aceasta este general adoptată în analiza complexității algoritmilor.
2. Numărul datelor de intrare
Distingem două tipuri de probleme:
Probleme care tratează date numerice
Probleme care tratează alte obiecte:
formule logice,
grafuri,
polinoame,
automate ,
gramatici etc
Timpul exact de execuție a unui algoritm poate fi o expresie foarte complexă. Acest timp de execuție este doar aproximat printr-o expresie mai simplă, conținând numai termenul de ordinul cel mai mare și către care tinde asimptotic (putem ignora termenii de ordin inferior și coeficienții deoarece, pentru intrări mari, aceștia sunt dominați de termenii de ordin superior).
II.1.5. Algoritmi elementari
În continuare sunt prezentați următorii algoritmi (Sorin, 08) (Miloșescu, 06):
Algoritmul de interschimbare a două valori
Algoritmul de calculare a valorii maxime dintr-un șir de n valori ( respectiv calcularea minimului)
Algoritmii de prelucrare a cifrelor unui număr:
Creare unui număr din cifre date
Extragerea unui număr
Crearea răsturnatului unui număr
Algoritmul pentru calcularea c.m.m.d.c a două numere
Algoritmul lui Euclid
Algoritmul lui Manna (cu scăderi succesive)
Algoritmul pentru verificarea primalității unui număr
Algoritmul pentru generarea divizorilor unui număr
Algoritmi pentru conversii între baze de numerație
Algoritmul pentru generarea șirurilor recurente
Algoritmul de interschimbare a două valori
Sunt date două valori care vor fi interschimbate
O rezolvare se poate realiza prin utilizarea unei variabile auxiliare care memorează temporar una din valorile citite
O altă rezolvare implică operații algebrice elementare (scăderi și adunări) prin care se interschimbă valorile inițiale
Utilizând o variabilă auxiliară
#include <iostream>
using namespace std;
int main()
{
int a,b,aux;
cout<<"a=";cin>>a;
cout<<"b=";cin>>b;
aux=a;
a=b;
b=aux;
cout << "a=" <<a<< endl;
cout << "b=" <<b<< endl;
return 0;
}
Prin scăderi succesive
#include <iostream>
using namespace std;
int main()
{
int a,b;
cout<<"a=";cin>>a;
cout<<"b=";cin>>b;
a=a-b;
b=b+a;
a=b-a;
cout << "a=" <<a<< endl;
cout << "b=" <<b<< endl;
return 0;
}
Algoritmul pentru determinarea valorii maxime/minime
Sunt citite de la tastatură mai multe numere
Prima valoare citită este considerată ca fiind maximă (minimă)
Se verifică după citirea fiecăre valori dacă este îndeplinită condiția de ordine; dacă acesta nu este îndeplinită, valoarea curentă va fi considerată ca fiind maximă (minimă)
Valoarea determinată este afișată
N numere citite
#include<iostream>
using namespace std;
int main()
{
int n,i,a,maxi;
cout<<"n=";cin>>n;
maxi=0;
for(i=1;i<=n;i++)
{
cout<<"a=";cin>>a;
if(a>maxi) maxi=a;
}
cout<<"valoarea maxima este "<<maxi<<endl;
return 0;
}
Mai multe numere citite
#include<iostream>
using namespace std;
int main()
{
int maxi,a;
cout<<"a=";cin>>a;
maxi=a;
while(a!=0)
{
cout<<"a=";cin>>a;
if(a>maxi) maxi=a;
}
cout<<"valoarea maxima este "<<maxi<<endl;
return 0;
}
Algoritmi pentru prelucrarea cifrelor unui număr
Crearea unui număr din cifre date
Se citesc pe rând cifrele unui număr
Se adaugă în cadrul numărului; adăugarea poate fi realizată la începutul sau la sfârșitul numărului
Se afișează numărul creat
Adăugarea cifrelor la sfârșitul numărului
#include<iostream>
using namespace std;
int main()
{
int c,nr;
nr=0;
cout<<"c=";cin>>c;
while((c>=0)&&(c<=9))
{
nr=nr*10+c;
cout<<"c=";cin>>c;
}
cout<<"numarul creat este "<<nr;
return 0;
}
Adăugarea cifrelor la începutul numărului
#include<iostream>
using namespace std;
int main()
{
int c,nr,p;
nr=0;
p=1;
cout<<"c=";cin>>c;
while((c>=0)&&(c<=9))
{
nr=nr+c*p;
p=p*10;
cout<<"c=";cin>>c;
}
cout<<"numarul creat este "<<nr;
return 0;
}
Extragerea cifrelor unui număr
Dat fiind un număr cu mai multe cifre, se dorește extragerea cifrelor acestuia
Cât timp nu se ajunge la valoarea 0, prin împărțiri succesive se poate obține fiecare cifră
#include<iostream>
using namespace std;
int main()
{
int n,c;
cout<<"n=";cin>>n;
while(n!=0)
{
c=n%10;
cout<<c<<endl;
n=n/10;
}
return 0;
}
Calcularea răsturnatului unui număr
Răsturnatul unui număr se obține prin citirea/scrierea cifrelor acestuia în ordine inversă
Se utilizează cei doi algoritmi de mai sus, de extragere a cifrelor și de creare a unui număr din cifre date pentru a calcula răsturnatul unui număr
#include<iostream>
using namespace std;
int main()
{
int n,nr,c;
cout<<"n=";cin>>n;
nr=0;
while (n!=0)
{
c=n%10;
nr=nr*10+c;
n=n/10;
}
cout<<"inversul numarului este "<<nr;
return 0; }
Algoritmul pentru calcularea c.m.m.d.c a două numere
Fiind date două numere naturale, se va calcula cel mai mare divizor comun
Există doi algoritmi de calcul: algoritmul lui Euclid și algoritmul lui Manna
Algoritmul lui Euclid utilizează împărțirea cu rest pentru a calcula divizorul; acesta este ultimul rest diferit de 0
Algoritmul lui Manna utilizează operația de scădere până când cele două valori sunt egale, valoarea fiind cel mai mare divizor
Algoritmul lui Euclid
#include<iostream>
using namespace std;
int main()
{
int a,b,r;
cout<<"a=";cin>>a;
cout<<"b=";cin>>b;
while(b!=0)
{
r=a%b;
a=b;
b=r;
}
cout<<"c.m.m.d.c "<<a;
return 0;
}
Algoritmul lui Manna
#include<iostream>
using namespace std;
int main()
{
int a,b;
cout<<"a=";cin>>a;
cout<<"b=";cin>>b;
while(a!=b)
{
if (a>b)
a=a-b;
else
b=b-a;
}
cout<<"c.m.m.d.c "<<a;
return 0;
}
Algoritmul pentru verificarea primalității unui număr
Se verifică dacă un număr n nu are divizori
Se încearcă împărțirea numărului la valori cuprinse între 2 și
Este posibil să se realizeze împărțirile până la
Varianta 1
#include<iostream>
using namespace std;
int main()
{
int n,t,i;
cout<<"n=";cin>>n;
i=2;
t=1;
while(i<n/2&&t)
if(n%i==0)
t=0;
else
i++;
if(t==1)
cout<<"numarul este prim";
else
cout<<"numarul nu este prim";
return 0;
}
Varianta 2
#include<iostream>
using namespace std;
int main()
{
int n,i,t;
cout<<"n=";cin>>n;
if (n%2==0)
t=0;
else
{
i=3;
t=1;
while (i<n/2 && t)
if (n%i==0)
t=0;
else
i+=2;
}
if(t==1)
cout<<"numarul este prim";
else
cout<<"numarul nu este prim";
return 0;
}
Algoritmul pentru generarea divizorilor unui număr
Fiind dat un număr natural, divizorii acestuia se pot calcula prin împărțiri succesive la valori cuprinse între 1 și numărul dat
Pentru a utiliza mai puțină memorie, se vor realiza împărțirile până la , deoarece următorii divizori sunt multiplii primilor
#include<iostream>
using namespace std;
int main()
{
int n,i;
cout<<"n=";cin>>n;
for(i=2;i<=n/2;i++)
if(n%i==0)
cout<<i<<endl;
return 0;
}
Algoritmi pentru conversii între baze de numerație
Conversia unui număr din baza zecimală într-o bază oarecare, este realizată prin împărțiri succesive
Conversia dintr-o bază oarecare în baza zecimală este realizată prin ridicarea la putere a cifrelor citite și adăugarea la numărul zecimal
Din baza 10 într-o bază b
#include<iostream>
using namespace std;
int main()
{
int n10,b,p,c,nb;
cout<<"n10=";cin>>n10;
cout<<"b=";cin>>b;
p=1;
nb=0;
while (n10!=0)
{
c=n10%b;
n10=n10/b;
nb=nb+p*c;
p=p*10;
}
cout<<"numarul in baza b este "<<nb;
return 0;
}
Din baza b în baza 10
#include<iostream>
using namespace std;
int main()
{
int n10,c,b;
cout<<"b=";cin>>b;
cout<<"c=";cin>>c;
n10=0;
while ((c>=0)&&(c<=b))
{
n10=n10*b+c;
cout<<"c=";cin>>c;
}
cout<<"numarul in baza 10 este "<<n10;
return 0;
}
Algoritmul pentru generarea șirurilor recurente
Cel mai cunoscut șir recurent este șirul lui Fibonacci: 1, 1, 2, 3, 5, 8, 13, 21, …….
Se folosesc două variabile care au inițial valoarea 1, acestea sunt utilizate în calcularea celui de-al treilea termen după relația de recurență:
Generarea șirului lui Fibonacci
#include<iostream>
using namespace std;
int main()
{
int n,i,a1,a2,a3;
cout<<"n=";cin>>n;
a1=1;
a2=1;
cout<<a1<<" ";
cout<<a2<<" ";
for(i=3;i<=n;i++)
{
a3=a1+a2;
cout<<a3<<" ";
a1=a2;
a2=a3;
}
return 0;
}
II.2. Algoritmi de sortare
Sunt algoritmi care rearanjează elementele unui vector, astfel încât între acestea să existe o relație de ordine (ordonarea poate fi crescătoare sau descrescătoare).
Sortarea se poate face în același vector sau utilizând un vector auxiliar. Cei mai cunoscuți algoritmi de sortare sunt:
Algoritmul de sortare prin numărare
Algoritmul de sortare prin metoda bulelor
Algoritmul de sortare prin selecția directă
Algoritmul de sortare prin inserție:
Algoritmul de sortare prin inserare
Algoritmul de sortare prin inserarea directă
Algoritmul de sortare prin inserarea rapidă
1. Algoritmul de sortare prin numărare:
Se folosesc trei vectori cu aceeași dimensiune:
Vectorul sursă
Vectorul destinație
Vectorul numărător
Elementele din vectorul sursă se copiază în vectorul destinație
Vectorul destinație respectă relația de ordine
Pentru a ști poziția în care se copiază elementul, se parcurge vectorul sursă și se numără câte elemente sunt mai mici decât el
Fiecare element din vectorul numărător corespunde unui element din vectorul sursă și reprezintă poziția lui din vectorul destinație
Complexitatea algoritmului este liniară (Zaharie, 14) (Sorin, 08)
using namespace std;
#include<iostream>
int main()
{
int a[20],b[20],n,i,j,k[20]={0};
cout<<"n=";cin>>n;
for(i=1;i<=n;i++)
{
cout<<"a["<<i<<"]="; cin>>a[i];
}
for(i=1;i<n;i++)
for(j=i+1;j<=n;j++)
if(a[i]>a[j])
k[i]++;
else
k[j]++;
for(i=1;i<=n;i++)
b[k[i]+1]=a[i];
for(i=1;i<=n;i++)
cout<<b[i]<<" ";
return 0;
}
2. Algoritmul de sortare prin metoda bulelor:
Se parcurge vectorul și se compară fiecare element cu succesorul lui
Dacă nu sunt în ordine, se interschimbă
La fiecare interschimbare, se reia parcurgerea verctorului de la început
Algoritmul se oprește dacă la o parcurgere completă nu se realizează nici o interchimbare
Complexitatea algoritmului este polinomială (Zaharie, 14) (Sorin, 08)
using namespace std;
#include<iostream>
int main()
{
int a[20],n,i,aux,t=0;
cout<<"n=";cin>>n;
for(i=1;i<=n;i++)
{
cout<<"a["<<i<<"]="; cin>>a[i];
}
while(!t)
{
t=1;
for(i=1;i<=n;i++)
if(a[i]>a[i+1])
{
aux=a[i];
a[i]=a[i+1];
a[i+1]=aux;
t=0;
}
}
for(i=1;i<=n;i++)
cout<<a[i]<<" ";
return 0;
}
3. Algortimul de sortare prin selecție directă:
Se aduce pe prima poziție elementul cu valoarea cea mai mică din vector
Se caută apoi elementul cel mai mic din cele rămase
Acesta se aduce pe poziția a doua
Apoi se realizează același lucru cu al treilea element
Procedeul continuă până la ultimul element din vector
Complexitatea algoritmului este polinomială (Zaharie, 14) (Sorin, 08)
using namespace std;
#include<iostream>
int main()
{
int a[20],n,i,j,aux;
cout<<"n=";cin>>n;
for(i=1;i<=n;i++)
{
cout<<"a["<<i<<"]="; cin>>a[i];
}
for(i=1;i<n;i++)
for(j=i+1;j<=n;j++)
if(a[i]>a[j])
{
aux=a[i];
a[i]=a[j];
a[j]=aux;
}
for(i=1;i<=n;i++)
cout<<a[i]<<" ";
return 0;
}
4. Algoritmul de sortare prin inserare:
Se folosesc doi vectori cu aceeași dimensiune:
Vectorul sursă
Vectorul destinație
Elementele din vectorul sursă sunt copiate în vectorul destinație în poziția corespunzătoare
Se respectă relația de ordine în vectorul destinație
Elementele din vectorul destinație sunt deplasate la dreapta
Complexitatea algoritmului este polinomială (Zaharie, 14) (Sorin, 08)
using namespace std;
#include<iostream>
int main()
{
int a[20],n,i,j,b[20],k;
cout<<"n=";cin>>n;
for(i=1;i<=n;i++)
{
cout<<"a["<<i<<"]="; cin>>a[i];
}
b[1]=a[1];
for(i=2;i<=n;i++)
{
j=1;
while((j<=i-1)&&(a[i]>b[j]))
j++;
for(k=i;k>j-1;k–)
b[k]=b[k-1];
b[j]=a[i];
}
for(i=1;i<=n;i++)
cout<<b[i]<<" ";
return 0;
}
5. Algoritmul de sortare prin metoda inserării directe
Se folosesc doi subvectori, obținuți din vectorul inițial
Se aplică procedeul de la metoda inserării
Complexitatea algoritmului este polinomială (Zaharie, 14) (Sorin, 08)
using namespace std;
#include<iostream>
int main()
{
int a[20],n,i,j,aux;
cout<<"n=";cin>>n;
for(i=1;i<=n;i++)
{
cout<<"a["<<i<<"]="; cin>>a[i];
}
for(i=2;i<n;i++)
{
aux=a[i];
j=i-1;
while(j>0&&aux<a[j])
{
a[j+1]=a[j];
j–;
}
if(aux>=a[j])
a[j+1]=aux;
else
{
a[2]=a[1];
a[1]=aux;
}
}
for(i=1;i<=n;i++)
cout<<a[i]<<" ";
return 0;
}
6. Algotimul de sortare prin metoda inserării rapide:
Se împarte vectorul în doi subvectori
Căutarea poziției pentru a insera elementul în subvectorul destinație se face prin algoritmul de căutare binară
Subvectorul destinație se împarte în doi subvectori și se examinează relația de ordine dintre elementul de la mijlocul subvectorului și elementul curent
Divizarea continuă până la găsirea poziției în care se va insera elementul curent
Complexitatea algoritmului este polinomială (Zaharie, 14) (Sorin, 08)
using namespace std;
#include<iostream>
int main()
{
int a[20],n,i,aux,st,dr,m,j;
cout<<"n=";cin>>n;
for(i=1;i<=n;i++)
{
cout<<"a["<<i<<"]="; cin>>a[i];
}
for(i=2;i<=n;i++)
{
aux=a[i];
st=1;
dr=i;
while(st<dr)
{
m=(st+dr)/2;
if(aux<a[m])
dr=m-1;
else
st=m+1;
}
j=i-1;
while(j>=st)
{
a[j+1]=a[j];
j=j-1;
}
a[st]=aux;
}
for(i=1;i<=n;i++)
cout<<a[i]<<" ";
return 0;
}
II.3. Algoritmi teoria grafurilor
II.3.1. Grafuri neorientate
II.3.1.1. Introducere
Se știe că proteinele reprezintă cărămizile structurale ale organismului. Fiecare celulă din corpul uman conține mii de proteine de mai multe tipuri, responsabile cu îndeplinirea diferitelor funcțiuni ale celulei. De exemplu, transmiterea senzațiilor tactile (cum ar fi durerea) este intermediată de diferite tipuri de proteine (plecând de la celulele senzoriale receptoare unde are loc recepția unei lovituri până la nivelul creierului, prin intermediul unei rețele de celule nervoase). În interiorul organismului uman există rețele de celule nervoase formate din celule aranjate una în continuarea celeilalte, care transmit senzația de durere sub forma unui impuls nervos.
Dacă am dori să calculăm viteza de reacție a unui organism la o durere, am putea să transformăm rețelele de proteine (Sedgewick et al, 08) în structuri de date, numite grafuri neorientate. Astfel, o rețea de proteine poate fi mapată informatic sub forma unui graf neorientat, în care fiecare proteină reprezintă un nod iar legăturile dintre ele reprezintă muchiile.
II.3.1.2. Definiții
Un graf neorientat este o pereche ordonată (V, E) unde V={v1,v2,….vn} este o mulțime finită nevidă de elemente numite noduri (sau vârfuri) iar E o mulțime de perechi neordonate din V de forma (vi,vj) unde i≠j, numite muchii. Notăm graful cu G=(V, E) (Sorin et al, 06).
Într-un un graf neorientat G=(V, E) dacă (vi,vj) ϵ E atunci (vj,vi) ϵ E (dacă există muchie de la nodul vi la nodul vj atunci se consideră că există muchie și de la nodul vj la nodul vi).
Un nod este un element al mulțimii V, unde G=(V, E) este un graf neorientat.
O muchie este un element al mulțimii E ce unește două noduri din V, unde G=(V, E) este un graf neorientat.
Într-un graf neorientat G=(V, E) nodurile distincte vi,vj ϵ V sunt adiacente dacă există muchia (vi,vj) ϵ E.
Într-un graf neorientat G=(V, E) muchia (vi,vj) ϵ E este incidentă cu nodurile vi,vj ϵ V.
Într-un graf neorientat G=(V, E) prin gradul unui nod v se înțelege numărul de muchii incidente cu nodul v. Se notează cu d(v) și este un număr natural.
Un nod cu gradul 0 se numește nod izolat. Un nod cu gradul 1 se numește nod terminal.
Exemplu:
Fie graful G=(V,E) din figura alăturată:
Atunci:
Numărul de noduri: n=6
Numărul de muchii: m=8
Mulțimea muchiilor: E={(1,2); (1,3); (1,5); (2,3); (2,4); (2,5); (3,4); (3,5); (4,5)},
Gradele nodurilor: d(1)=3, d(2)=4, d(3)=4, d(4)=3, d(5)=4; d(6)=0
Noduri izolate: 6
Noduri terminale: nu există
Relații utile:
Dacă un graf neorientat are n noduri și m muchii atunci suma gradelor tuturor nodurilor este 2m:
d(1)+d(2)+ …… +d(n)=2m
În orice graf G există un număr par de noduri de grad impar
Componente ale unui graf: Lanț. Circuit.
Într-un graf neorientat G=(V,E) se numește lanț o succesiune de noduri L=[v1, v2,…,vp], cu proprietatea că oricare două noduri consecutive sunt adiacente, adică (vi, vi+1) ϵ E pentru 1≤i<n.
v1, vp se numesc extremitățile lanțului.
Lungimea unui lanț este dată de numărul de muchii din care este format (p-1).
Într-un graf neorientat G=(V,E) se numește lanț elementar lanțul care conține numai noduri distincte.
Într-un graf neorientat G=(V,E) se numește circuit un lanț în care primul nod coincide cu ultimul (Bărbăcioru, 12).
Circuitul este elementar dacă este format doar din noduri distincte, excepție făcând primul și ultimul. Lungimea unui circuit nu poate fi egală cu 2.
Exemplu:
Fie graful G=(V,E) din figura alăturată:
În graf avem:
Numărul de noduri: n=5
Numărul de muchii: m=7
Dacă alegem nodul 1 ca nod inițial și nodul 3 este ca nod final avem:
Un lanț L=[1,2,4,2,5,3] de lungime 5
Un lanț elementar L=[1,5,2,4,3] de lungime 4
Un circuit poate fi {1,2,5,2,3,5,1} de lungime 6
Un circuit elementar {1,2,3,5,1} de lungime 4
Graf parțial. Subgraf
Un graf parțial al unui graf neorientat G=(V, E) este un graf G1=(V, E1), cu proprietatea că E1 E.
Din graful neorientat se suprimă cel puțin o muchie astfel, graful parțial are aceleași noduri și o parte din muchii.
Un subgraf al unui graf neorientat G=(V, E) este un graf G1=(V1, E1), cu proprietățile V1Vși E1E, iar muchiile din E1 sunt muchiile din E care sunt incidente numai cu noduri din mulțimea V1.
Din graful neorientat se suprimă cel puțin un nod și muchiile adiacente cu acesta.
Exemplu:
Cazuri particulare
Se numește graf regulat un graf neorientat în care toate nodurile au același grad.
Se numește graf complet un graf neorientat G=(V, E) în care oricare două noduri sunt adiacente.
Exemplu
După cum se poate observa și în exemplul de mai sus, nu este obligatoriu ca un graf regulat să fie complet. În schimb, un graf complet este obligatoriu graf regulat.
Relații utile:
Într-un graf neorientat complet cu n noduri gradul fiecărui nod este n-1.
Într-un graf neorientat complet cu n noduri și m muchii există relația: .
Există grafuri neorientate cu n noduri.
Exemplu
Fie graful complet alăturat G=(V, E).
Graful G are 6 noduri, gradul fiecărui nod este egal cu 5.
Numărul de muchii poate fi calculat cu ajutorul formulei:
Graf conex. Componentă conexă
Un graf neorientat G=(V, E) este graf conex dacă pentru orice pereche de noduri (x,y) există un lanț care le unește.
Din definiția de mai sus se deduce că un graf cu un singur nod este, prin definiție, conex.
Exemplu
Fie graful G=(V, E) cu 5 noduri.
Acesta este conex deoarece orice pereche de noduri poate fi unită printr-un lanț.
Fie G=(V, E) un graf neorientat și G1=(V1, E1) un subgraf al său. G1 se numește componentă conexă a grafului G dacă:
Între oricare două noduri din V1 exită un lanț
Nu există nici un alt subgraf a lui G care să îndeplinească prima condiție
Un nod izolat este, prin definiție o componentă conexă a unui graf neorientat.
Exemplu
Fie graful G=(V, E) cu 6 noduri.
Graful de mai sus are 3 componente conexe:
{2,3,4};{1,5} și {6}
Graf Hamiltonian
Într-un graf neorientat G=(V, E) se numește lanț hamiltonian un lanț elementar care conține toate nodurile unui graf.
Într-un graf neorientat G=(V, E) se numește circuit hamiltonian un circuit elementar care trece o singură dată prin toate nodurile grafului.
Un graf neorientat care admite un circuit hamiltonian se numește graf hamiltonian.
Teoremă: Dacă G=(V, E) este un graf neorientat cu n noduri (n≥3) și gradul fiecărui nod este mai mare sau egal decât atunci graful G este hamiltonian
Exemplu
Fie graful G=(V, E) cu 8 noduri
Un lanț hamiltonian este L=[1,3,2,4,6,5,7,8]
Un circuit hamiltonian este {1,2,3,4,5,6,7,8,1}
Deci graful G este hamiltonian
Graf Eulerian
Într-un graf neorientat G=(V, E) se numește lanț eulerian un lanț care conține fiecare muchie o dată și numai o dată.
Într-un graf neorientat G=(V, E) se numește circuit eulerian un lanț eulerian în care extremitățile coincid.
Un graf neorientat care conține un circuit eulerian se numește graf eulerian.
Teoremă: Un graf neorientat fără vârfuri izolate este eulerian, dacă și numai dacă este conex și gradele tuturor vârfurilor sunt numere pare.
Condiție necesară și suficientă: Un graf este eulerian dacă și numai dacă oricare vârf al său are gradul par.
Exemplu
Fie graful G=(V,E) cu 6 noduri
Un ciclu eulerian este {1,4,3,5,6,4,2,1}
Grafuri bipartite
Fie un graf neorientat G=(V, E). Graful G se numește bipartit dacă există două submulțimi A, B V astfel încât:
(mulțimile A și B nu au nici un punct comun);
(reuniunea mulțimilor A și B o constituie mulțimea V);
toate muchiile grafului au o extremitate în A și cealaltă în B.
Fie un graf neorientat G=(V, E). Graful G se numește bipartit complet dacă este bipartit și are în plus proprietatea că pentru orice nod x din A și orice nod y din B există muchia (x, y).
Exemple
a) Graful G=(V,E) cu 7 noduri este bipartit:
b) Graful este bipartit complet dacă are forma:
II.3.1.3. Memorarea grafurilor neorientate
Cele mai cunoscute forme de memorare ale unui graf neorientat sunt:
matricea de adiacență
listele de adiancență
vectorul muchiilor
Matricea de adiacență
Fiind dat un graf neorientat G=(V, E), cu n noduri, pentru memorarea acestuia se definește o matrice pătratică Anxn cu elemente numere binare astfel încât:
Proprietăți:
Elementele de pe diagonala principală sunt egale cu 0.
Este o matrice simetrică.
Suma elementelor pe linia i (sau coloana i) este egală cu gradul nodului i.
Dacă toate elementele pe linia i și coloana i sunt egale cu 0 atunci nodul este izolat.
Dacă toate elementele sunt egale cu 1 mai puțin cele de pe diagonala principală atunci înseamnă că graful este complet.
Suma tuturor elementelor din matrice este egală cu dublul numărului de muchii
Dacă numărul de muchii este mic, utilizarea matricei de adiacență este ineficientă.
Pentru a ușura munca programatorului, graful neorientat va fi memorat într-un fișier text astfel: pe prima linie se află numărul de noduri n, iar pe următoarele m linii se află muchiile grafului.
Exemplu
Fie graful G=(V,E)
În graful din alăturată avem:
Numărul de noduri: n=6
Numărul de muchii: m=8
Mulțimea muchiilor:
E={(1,2);(1,3);(1,5);(2,3);(2,4);(2,5);(3,4);(3,5);(4,5)},
Fișierul text graf.txt care conține graful este:
Matricea de adiacență asociată grafului este:
Citirea unui graf neorientat din fișierul text graf.txt și construirea matricei de adiacență se realizează utilizând subprogramul de mai jos. Deoarece același subprogram este apelat în mai multe programe, este utilă crearea unui fișier header care să fie inclus în programele următoare.
Fișierul graf.h este (Sorin et al, 06):
void citiren(char nume_fis[20], int a[20][20], int &n)
{
int i,j;
ifstream f(nume_fis);
f>>n;
while(f>>i>>j)
{
a[i][j]=1;
a[j][i]=a[i][j];
}
f.close();
}
Listele de adiacență
Pentru a memora un graf neorientat G=(V, E) cu n noduri, se crează un vector cu n elemente, fiecare element fiind nodul de început al listelor de adiacență. Se memorează apoi nodurile adiacente cu fiecare element al vectorului.
Se utilizează tipul de dată înregistrare pentru alocarea dinamică a memoriei și pentru generarea vectorului ce reține adresele de început a listelor de adiacență alocate dinamic.
Sintaxa este:
struct nod
{
int info;
nod *urm;
};
Exemplu
Fie graful G=(V,E)
În graful alăturat avem:
Numărul de noduri: n=6
Mulțimea muchiilor:
E={(1,2);(1,3);(1,5);(2,3);(2,4);(2,5);(3,4);(3,5);(4,5)}
Fișierul text graf.txt care conține graful este:
Citirea unui graf neorientat din fișierul text graf.txt și construirea listelor de adiacență alocate dinamic se realizează utilizând subprogramul de mai jos. Deoarece același subprogram este apelat în mai multe programe, este utilă crearea unui fișier header care să fie inclus în programele următoare.
Fișierul graf1.h este:
void cit_la_dinamic(char nume_fis[20], nod *l[50], int &n)
{
nod *p;
int i,j;
ifstream f(nume_fis);
f>>n;
while(f>>i>>j)
{
p=new nod;
p->urm=l[i];
p->info=j;
l[i]=p;
p=new nod;
p->urm=l[j];
p->info=i;
l[j]=p;
}
f.close();
}
Vectorul muchiilor
Fiecare muchie a grafului poate fi privită ca o înregistrare cu două componente: cele două vârfuri care constitue extremitățile muchiei. Graful în ansamblul său, este o mulțime de muchii.
Se utilizează tipul de date întregistrare pentru a crea vectorul muchiilor. Câmpurile înregistrării sunt extremitățile muchiilor.
Sintaxa:
struct muchie
{
int x,y;
} ;
muchie m[dim];
Exemplu:
Fie graful G=(V,E)
În graful din figura alăturată avem:
Numărul de noduri: n=6
Mulțimea muchiilor: E={(1,2);(1,3);(1,5);(2,3);(2,4);
(2,5);(3,4);(3,5);(4,5)}
Fișierul text graf.txt care conține graful este:
Citirea unui graf neorientat din fișierul text graf.txt și construirea listei muchiilor se realizează utilizând subprogramul de mai jos. Deoarece același subprogram este apelat în mai multe programe, este utilă crearea unui fișier header care să fie inclus în programele următoare.
Fișierul graf2.h este:
void cit_muchii(char nume_fis[20], muchie v[20], int &n)
{
int i,j,k=1;
ifstream f(nume_fis);
f>>n;
while(f>>i>>j)
{
v[k].x=i;
v[k].y=j;
k++;
v[k].x=j;
v[k].y=i;
k++;
}
f.close();
}
II.3.1.4. Parcurgerea grafurilor
Reprezintă vizitarea tuturor nodurilor unui graf. Pentru a reuși vizitarea tuturor nodurilor, graful trebuie să fie conex. Parcurgerea eficientă a grafurilor este esențială deoarece mulți algoritmi se bazează pe vizitarea tuturor nodurilor.
Există două modalități consacrate de parcurgere și anume: parcurgerea în lățime (Breath First – BF) și parcurgerea în adâncime (Depth First – DF).
Ambele parcurgeri au următoarea strategie:
Se alege aleatoriu un nod inițial v
Se vizitează toate nodurile adiacente cu v
Dacă există noduri care nu au fost vizitate, se consideră ca fiind nodul de început v și se reia pasul 2 pentru noul nod v
Parcurgerea în lățime (Breath First – BF)
Se vizitează toate nodurile grafului astfel:
Se vizitează nodul v
Se vizitează toate nodurile adiacente cu v
Se vizitează toate nodurile adiacente cu cele anterioare care nu au fost vizitate
Se continuă vizitarea până când nu mai sunt noduri de vizitat
Algoritmul BF
Se inițializează un vector logic cu valoarea 0
Se inițializează coada cu valoarea de început
Pentru acest nod, se trec în coadă toate nodurile adiancente cu el
Pentru toate aceste noduri, se marchează ca fiind vizitate
Se afișează nodurile adiacente
Se extrage primul nod din coadă
Exemplu
Fie graful G=(V, E) cu 7 noduri
Pentru graful alăturat avem parcurgerile:
Nodul de pornire 1: 1, 2, 3, 5, 4, 6, 7
Nodul de pornire 6: 6, 4, 2, 7, 1, 3, 5
Nodul de pornire 3: 3, 1, 5, 2, 4, 6, 7
Parcurgerea în adâncime (Depth First – DF)
Se vizitează toate nodurile grafului începând de la v astfel:
Se vizitează nodul v
Se vizitează un nod x adiacent cu v care nu a fost vizitat încă
Se vizitează un nod y adiacent cu x care nu a fost vizitat încă
Se continuă până când nodul curent nu mai are nici un nod adiacent nevizitat
Se întoarce la un nod care mai are noduri adiacente nevizitate
Se parcurg astfel toate nodurile grafului
Algoritmul DF:
Se inițializează vectorul vizitat cu valoarea 0
Se memorează în stivă nodul v și se marchează ca fiind vizitat
Se trece la următorul nod adiacent cu nodul inițial și se adaugă în stivă
Dacă nodul curent nu mai are noduri adiacente nevizitate, se scoate din stivă
Exemplu
Fie graful G=(V, E) cu 7 noduri
Pentru graful alăturat avem parcurgerile:
Nodul de pornire 1: 1,6,7,4,2,5,3
Nodul de pornire 6: 6, 5,3,1,2,7,4
Nodul de pornire 3: 3,7,4,2,5,1,6
Estimarea timpului de execuție pentru algoritmii de parcurgere a unui graf:
BF și DF utilizând matricea de adiacență au ordinul O(n2)
BF și DF utilizând listele de adiacență au ordinul O(m)
II.3.1.5. Algoritmi elementari pentru grafuri neorientate
Citirea matricei de adiacență și afișarea acesteia (Sorin, 08)
Fie graful neorientat G=(V, E):
Fișierul text în care se memorează graful este:
using namespace std;
#include <iostream>
#include<fstream>
#include "graf.h"
int i,j;
int main()
{
citiren("graf.txt",a,n);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
cout<<a[i][j];
cout<<endl;
}
return 0;
}
Memorarea listelor de adiacență alocate dinamic.
using namespace std;
#include<iostream>
#include<fstream>
#include"graf1.h"
nod *l[50];
int n,i;
int main()
{
cit_la_dinamic("graf.txt", l,n);
for (i=1;i<=n;i++)
{
cout<<"noduri adiacente cu "<<i<<endl;
while(l[i])
{
cout<<l[i]->info<<" ";
l[i]=l[i]->urm;
}
cout<<endl;
}
return 0;
}
Memorarea listei muchiilor
using namespace std;
#include<iostream>
#include<fstream>
#include"graf2.h"
muchie v[20];
int n,i;
int main()
{
cit_muchii("graf.txt",v,n);
cout<<"lista muchiilor este"<<endl;
for(i=1;i<=n;i++)
cout<<v[i].x<<" "<<v[i].y<<endl;
return 0;
}
Parcurgerea BF cu matricea de adiacență (Sorin, 08)
using namespace std;
#include<iostream>
#include<fstream>
#include"graf.h"
int coada[20], s[20], i_c=1,sf_c=1,i;
void bf(int nod)
{
coada[i_c]=nod;
s[nod]=1;
while(i_c<=sf_c)
{ i=1;
while(i<=n)
{ if(a[coada[i_c]][i]==1&&s[i]==0)
{ sf_c++;
coada[sf_c]=i;
s[i]=1;
}
i++;
}
cout<<coada[i_c]<<endl;
i_c++;
} }
int main()
{
int x;
citiren("graf1.txt",a,n);
cout<<"dati nodul de pornire ";cin>>x;
bf(x);
return 0; }
Parcurgerea DF recursivă cu matricea de adiacență (Cerchez et al, 06)
using namespace std;
#include<iostream>
#include<fstream>
#include"graf.h"
int s[20];
void df_r(int nod)
{
int i;
cout<<nod<<" ";
s[nod]=1;
for(i=1;i<=n;i++)
if(a[nod][i]==1&&s[i]==0)
df_r(i);
}
int main()
{
int x;
citiren("graf1.txt",a,n);
cout<<"dati nodul de pornire ";cin>>x;
df_r(x);
return 0; }
II.3.2. Grafuri orientate
II.3.2.1. Introducere
Utilizarea site-urilor de socializarea pentru interacționare este una din cele mai comune modalități de comunicare la ora actuală. Dar cum funcționează aceste site-uri? Care este modelul matematic și informatic pe baza căruia sunt sugerați prietenii? Cum este posibilă afișarea aceleași postări mai multor utilizatori?
Site-urile de socializare, gen Facebook, folosesc grafurile orientate pentru a sugera prieteni și a putea afișa aceeași postare mai multor utilizatori, doar pe baza relațiilor dintre ei (Sedgewick et al, 08). Astfel, utilizatorii site-ului de socializare pot fi considerați nodurile grafului orientat, iar legăturile dintre ei, arcele grafului. În acest fel, putem vizualiza cum o postare a unui utilizator sursă poate ajunge ca o notificare la un utilizator care nu este în legătura directă cu acesta, acest lucru fiind posibil datorită conexiunilor unidirecționale sau bidirecționale cu alți utilizatori comuni.
II.3.2.2. Definiții
Se numește graf orientat perechea ordonată G = (V, A), unde V={v1,v2,….vn} este o mulțime finită și nevidă de elemente numite vârfuri (sau noduri), iar A este o mulțime de perechi ordonate de elemente de forma (vi,vj) unde i≠j din V numite arce (Sorin et al, 06).
Dacă există arcul (vi,vj) nu înseamă că există neaparat și arcul (vj,vi).
Grafurile orientate se mai numesc și digrafuri. Grafurile orientate sunt un caz particular al grafurilor neorientate.
În graful orientat G = (V, A), vârfurile distincte vi, vj ϵ V sunt adiacente dacă există cel puțin un arc care le unește.
În graful orientat G = (V, A) dacă există arcul (vi,vj) ϵ A, vom spune că este incident spre exterior cu vi și spre interior cu vj.
În graful orientat G = (V, A) dacă există arcul (vj,vi) ϵ A, vom spune că este incident spre exterior cu vj și spre interior cu vi.
Într-un graf orientat G = (V, A) se numește gradul interior al unui vârf v numărul arcelor incidente spre interior cu v și se notează d-(v).
Într-un graf orientat G = (V, A) se numește gradul exterior al unui vârf v numărul arcelor incidente spre exterior cu v și se notează d+(v).
Relație utilă:
Suma gradelor interioare a tututor nodurilor unui graf este egală cu suma gradelor exterioare a tuturor nodurilor unui graf și este egală cu numărul de muchii din graf.
d-(1)+d-(2)+…..+d-(n)=d+(1)+d+(2)+……+d+(n)=m
Exemplu
Fie graful G=(V,A):
În exemplul din figura alăturată avem:
Numărul de noduri n=6
Mulțimea arcelor A={(1,2); (1,3); (1,5); (2,3); (2,4); (3,4); (4,1); (5,1); (5,2)}
numărul de arce m=9
Gradele nodurilor:
Gradele interioare d-(1)=2, d-(2)=2, d-(3)=2, d-(4)=2, d-(5)=1, d-(6)=0
Gradele exterioare d+(3)=2, d+(2)=2, d+(3)=1, d+(4)=1, d+(5)=2, d+(6)=0
Noduri izolate: 6
Noduri terminale: nu există
Componentele grafurilor. Drum. Ciclu.
Într-un graf orientat G=(V, A) se numește drum o succesiune de noduri D=[v1, v2,…,vp], cu proprietatea că oricare două noduri consecutive sunt adiacente, adică (vi, vi+1) ϵ A pentru 1≤i<n.
v1, vp se numesc extremitățile drumului.
Lungimea unui drum este dată de numărul de muchii din care este format (p-1).
Un drum în care toate vârfurile sunt distincte se numește drum elementar.
Într-un graf orientat, un drum în care vârful inițial coincide cu vârful final și care conține numai arce distincte se numește ciclu.
Exemple:
Fie graful G=(V,A):
În graf avem:
Numărul de noduri n=5
Mulțimea arcelor A={(1,2); (1,3); (1,5); (2,3); (2,4); (3,4); (4,1); (5,1); (5,2)}
Numărul de arce m=9
Un drum este: D=[1,5,2,3,4]
Un ciclu este C={1,2,3,4,1}
Graf parțial. Subgraf
Un graf parțial al unui graf orientat G=(V, A) este un graf G1=(V, A1), cu proprietatea că A1 A.
Din graful orientat se suprimă cel puțin un arc, graful parțial are aceleași număr de noduri.
Un subgraf al unui graf orientat G=(V, A) este un graf G1=(V1, A1), cu proprietățile V1Vși A1A, iar muchiile din A1 sunt muchiile din A care sunt incidente numai cu noduri din mulțimea V1.
Din graful orientat se suprimă un nod și arcele incidente interior și exterior cu acesta.
Exemple
Cazuri particulare
Un graf orientat se numește complet dacă oricare două vârfuri distincte sunt adiacente (câte un arc pentru fiecare direcție).
Se numește graf turneu un graf orientat cu proprietatea că între oricare două vârfuri distincte există exact un arc.
Exemple:
Proprietăți:
În cazul grafurilor orientate, pentru o mulțime de n vârfuri date putem avea grafuri complete.
În orice graf turneu există un drum elementar care conține toate vârfurile grafului.
Orice graf turneu este graf complet.
Graf conex. Componente conexe
Un graf orientat G=(V, A) este graf conex dacă pentru orice pereche de noduri (x,y) există un drum care le unește.
Din definiție se deduce că un graf alcătuit dintr-un singur nod este graf conex.
Exemplu
Fie graful G=(V,A) cu 5 noduri și 5 arce. Graful este conex deoarece există un drum care unește orice pereche de noduri din graf.
Fie G=(V, A) un graf orientat și G1=(V1, A1) un subgraf al său. G1 se numește componentă conexă a grafului G dacă:
Între oricare două noduri din V1 există un drum
Nu există nici un alt subgraf a lui G care să îndeplinească prima condiție
Un nod izolat este, prin definiție o componentă conexă a unui graf orientat.
Exemplu
Fie graful G=(V,A) cu 5 noduri și 4 arce
Componentele conexe ale grafului sunt:
{3,4};{1,2,5};{6}
Graf tare conex.Componente tare conexe
Un graf orientat G=(V, A) este graf tare conex dacă pentru orice pereche de noduri (x,y)ϵV există un drum de la x la y.
Fie G=(V, A) un graf orientat și G1=(V1, A1) un subgraf al său. G1 se numește componentă tare conexă a grafului G dacă:
Între oricare două noduri din V1 exită un drum
Nu există nici un alt subgraf a lui G care să îndeplinească prima condiție
Exemple
Grafuri ponderate
În numeroase situații practice modelate cu ajutorul grafurilor, fiecare muchie/arc a/al grafului are asociat un anumit cost sau o anumită pondere (de exemplu, lungimea cablului necesar pentru conectarea a două calculatoare într-o rețea, costul de transport pe o anumită rută, profitul obținut dintr-o anumită tranzacție etc.).
Graful G=(V, E) (orientat sau neorientat) însoțit de o funcție 𝑐: 𝐸 → 𝑅, prin care se asociază fiecărei muchii/arc din graf un număr real se numește graf ponderat sau rețea.
Pentru a reprezenta un graf ponderat trebuie să reținem și costurile asociate muchiilor/arcelor.
II.3.2.3. Memorarea grafurilor orientate
Cele mai cunoscute forme de memorare ale unui graf orientat sunt:
matricea de adiacență
listele de adiancență
lista arcelor
matricea ponderilor (costurilor)
Matricea de adiacență
Fiind dat un graf orientat G=(V, A), cu n noduri, pentru memorarea acestuia se definește o matrice pătratică Anxn cu elemente numere binare astfel încât:
Proprietăți:
Elementele de pe diagonala principală sunt egale cu 0.
Matricea nu este neapărat simetrică.
Suma elementelor pe linia i este egală cu gradul exterior al nodului i d+(i).
Suma elementelor pe coloana i este egală cu gradul interior al nodului i d-(i).
Dacă toate elementele pe linia i și coloana i sunt egale cu 0 atunci nodul este izolat.
Dacă toate elementele sunt egale cu 1 mai puțin cele de pe diagonala principală atunci înseamnă ca graful este complet.
Suma tuturor elementelor din matrice este egală cu numărului de arce.
Dacă numărul de arce este mic, utilizarea matricei de adiacență este ineficientă.
Pentru a ușura munca programatorului, graful orientat va fi memorat într-un fișier text astfel: pe prima linie se află numărul de noduri n, iar pe următoarele m linii se află arcele grafului.
Exemplu:
Fie graful G=(V,A)
În graful din figura alăturată avem:
Numărul de noduri: n=6
Numărul de arce: m=9
Mulțimea arcelor:
A={(1,2);(1,3);(1,5);(2,3);(2,4);(3,4);(4,1);(5,1);(5,2)}
Fișierul text graf.txt care conține graful este:
Matricea de adiacență asociată grafului este:
Citirea unui graf orientat din fișierul text graf.txt și construirea matricei de adiacență se realizează utilizând subprogramul de mai jos. Deoarece același subprogram este apelat în mai multe programe, este utilă crearea unui fișier header care să fie inclus în programele următoare.
Fișierul graf3.h este (Sorin et al, 06):
void citireo(char nume_fis[20], int a[20][20],int &n)
{
int i,j;
ifstream f(nume_fis);
f>>n;
while(f>>i>>j)
a[i][j]=1;
f.close();
}
Listele de adiacență
Pentru a memora un graf orientat G=(V, A) cu n noduri, se crează un vector cu n elemente, fiecare element fiind nodul de început al listelor de adiacență. Se memorează apoi nodurile adiacente cu fiecare element al vectorului.
Se utilizează tipul de dată înregistrare pentru alocarea dinamică a memoriei și pentru generarea vectorului ce reține adresele de început a listelor de adiacență alocate dinamic.
Sintaxa este:
struct nod
{
int info;
nod *urm;
}; nod l[50];
Exemplu
Fie graful G=(V, A)
În graful din figura alăturată avem:
Numărul de noduri: n=6
Numărul de arce: m=9
Mulțimea arcelor:
A={(1,2);(1,3);(1,5);(2,3);(2,4);(3,4);(4,1);(5,1);(5,2)}
Fișierul text graf.txt care conține graful este:
Citirea unui graf orientat din fișierul text graf.txt și construirea listelor de adiacență alocate dinamic se realizează utilizând subprogramul de mai jos. Deoarece același subprogram este apelat în mai multe programe, este utilă crearea unui fișier header care să fie inclus în programele următoare.
Fișierul graf4.h este:
void cit_la_dinamic(char nume_fis[20], nod *l[50], int &n)
{
nod *p;
int i,j;
ifstream f(nume_fis);
f>>n;
while(f>>i>>j)
{
p=new nod;
p->urm=l[i];
p->info=j;
l[i]=p;
}
f.close();
}
Lista arcelor
Fiecare arc al grafului poate fi privit ca o înregistrare cu două componente: cele două vârfuri care constitue extremitățile arcului. Graful în ansamblul său, este o mulțime de arce.
Se utilizează tipul de date întregistrare pentru a crea vectorul arcelor. Câmpurile înregistrării sunt extremitățile arcelor.
Sintaxa:
struct arc
{
int x,y;
} ;
arc a[dim];
Exemplu:
Fie graful G=(V,A)
În graf avem:
Numărul de noduri: n=6
Numărul de arce: m=9
Mulțimea arcelor:
A={(1,2);(1,3);(1,5);(2,3);(2,4);(3,4);(4,1);(5,1);(5,2)}
Fișierul text graf.txt care conține graful este:
Citirea unui graf orientat din fișierul text graf.txt și construirea listei muchiilor se realizează utilizând subprogramul de mai jos. Dacă același subprogram este apelat în mai multe programe, este utilă crearea unui fișier header care să fie inclus în programele următoare.
Fișierul graf6.h este:
void cit_arce(char nume_fis[20], arc a[20], int &n)
{
int i,j,k=1;
ifstream f(nume_fis);
f>>n;
while(f>>i>>j)
{
a[k].x=i;
a[k].y=j;
k++;
}
f.close();
}
Matricea ponderilor (costurilor)
Fiind dat un graf orientat G=(V, A), cu n noduri, pentru memorarea acestuia se atașează fiecărui arc o pondere (un cost) se definește astfel o matrice pătratică Anxn:
Matricea ponderilor forma 1
Matricea ponderilor forma 2
Exemplu
Fie graful G=(V,A)
În graful din figura alăturată avem:
Numărul de noduri: n=6
Numărul de arce: m=8
Mulțimea arcelor:
A={(1,2);(1,3);(1,5);(2,3);(2,4);(3,4);(4,1);(5,2)}
Fișierul text graf.txt care conține graful este:
Citirea unui graf orientat din fișierul text graf.txt și construirea matricei de adiacență se realizează utilizând subprogramul de mai jos. Deoarece același subprogram este apelat în mai multe programe, este utilă crearea unui fișier header care să fie inclus în programele următoare.
Fișierul graf5.h este:
const float pinf=1.e20;
void cit_cost(char nume_fis[20], float a[20][20], int &n)
{
int i,j;
float c;
ifstream f(nume_fis);
f>>n;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(i==j)
a[i][j]=0;
else
a[i][j]=pinf;
while(f>>i>>j>>c)
a[i][j]=c;
f.close();
}
II.3.2.4. Parcurgerea grafurilor
Există două modalități consacrate de parcurgere și anume: parcurgerea în lățime (Breath First – BF) și parcurgerea în adâncime (Depth First – DF). Algoritmii de parcurgere sunt similari cu cele de la grafurile neorientate. Acestea au fost prezentate în capitolul anterior.
II.3.2.5. Drumuri de cost minim
Algoritmii existenți pentru determinarea drumurilor optime în grafuri se împart în două mari categorii: algoritmi pentru drumuri minime și algoritmi pentru drumuri maxime (Lucanu, 15).
Acești algoritmi sunt pentru două categorii de probleme și anume:
determinarea drumurilor optime de sursă unică (sursă unică, destinații multiple)
determinarea drumurilor optime între toate perechile de vârfuri (surse multiple, destinații multiple)
Cei mai cunoscuți algoritmi pentru calcularea drumurilor optime în grafuri sunt:
Algoritmul Dijkstra: determină drumurile minime cu sursă unică în grafuri care admit doar costuri pozitive
Algoritmul Dantzig: determină drumurile minime cu sursă unică în grafuri care admit doar costuri pozitive
Algoritmul Bellman-Ford: drumuri minime cu sursă unică în grafuri care admit costuri negative, dar fără circuite de cost negativ
Algoritmul Roy-Floyd (Floyd-Warhall): drumuri minime între oricare două noduri
Algoritmul Bellman-Kalaba: drumuri maxime cu sursă unică și număr fixat de pași
Algoritmul Floyd-Warshall: drumuri maxime între oricare două noduri în grafuri fără circuite
În continuare vor fi prezentați trei algoritmi: algoritmul lui Dijkstra, algoritmul Roy-Floyd și algoritmul Bellman-Ford.
1. Algoritmul lui Dijkstra
Este un algoritm care calculează drumurile minime dintr-un graf de la un nod la toate celelalte noduri din graf. Algoritmul funcționează atât pe grafuri conexe cât și pe grafuri neconexe. Daca nu există nici un drum de la nodul de start la un alt nod al grafului atunci algoritmul lui Dijkstra va raporta, lipsa oricărui drum între cele două noduri. Algoritmul utilizează metoda Greedy generând drumurile minime în ordinea crescătoare a lungimilor (Crețu, 15).
Algoritmul se aplică pentru următorul tip de problemă:
Fiind dat un graf orientat G=(V, A), să se determine pentru toate vârfurile xi dacă există drum de la x0 la xi și lungimea celui mai scurt drum precum și unul dintre drumurile minime de la x0 la xi.
Date de intrare:
Algoritmul pornește de la un graf orientat și ponderat cu n noduri
De asemenea, există un nod de start aparținând grafului – acesta este nodul de la care se doreste aflarea drumurilor minime până la celelalte noduri din graf
Date de ieșire:
un tablou D cu n valori, conținând distanțele minime de la nodul de start la toate celelalte noduri din graf
se mai poate obține arborele drumurilor minime – acesta este un arbore reprezentat sub forma unui tablou T cu n valori (vectorul tata din reprezentarea arborilor)
Algoritmul Dijkstra (Rebedea et al, 15, a):
Pasul 1: Se pornește din x0 nodul se marchează ca vizitat. Se calculează cel mai scurt drum de la x0 la unul din celelalte vârfuri ale grafului este dat de arcul (x0,xj) de lungime minimă.
Pasul 2: Se calculează valorile pentru vectorul D (lungimile tuturor drumurilor de la nodul x0 la toate celelalte noduri la un moment dat) din matricea costurilor A. În același timp, se completează vectorul T cu valorile nodurilor care au un cost finit al drumului de la x0 la ele.
Pasul 3: Dintre nodurile neselectate, se alege cel cu distanța cea mai mică, xk, se marchează nodul ca vizitat și se actualizează vectorul D utilizând acest nod intermediar xk. Astfel, se verifică dacă drumul care trece prin acest nod intermediar are costul mai mic (D(j)>D(xk)+A(xk,j)), dacă da, se înlocuiește costul și se modifică vectorul T. Se repetă acest pas până când nu mai există noduri neselectate.
Pasul 4: Se trasează toate drumurile de la fiecare nod la x0
Algoritmul lui Dijkstra pseudocod:
pentru fiecare j V(G) execută
D[j] ∞
T[j] 0
sfârșit pentru
D[x0]0
S
QV(G) //Q este o coadă conținând toate nodurile neselectate
cât timp Q0 execută
xk minim(Q)
SS { xk }
pentru fiecare j vecin cu u execută
dacă D[j]D[xk]+A(xk,j) atunci // se verifică distanța mnimă
D[j]D[xk]+A(xk,j)
T[j] xk
sfârșit dacă
sfârșit pentru
sfârșit cât timp
2. Algoritmul lui Roy-Floyd
Este un algoritm care calculează drumurile minime dintr-un graf de la un nod oarecare la toate celelalte noduri din graf. Dacă nu există nici un drum de la nodul de start la un alt nod al grafului atunci algoritmul va raporta, lipsa oricărui drum între cele două noduri. Algoritmul utilizează metoda Divide et Impera de calculare.
Algoritmul se aplică pentru următorul tip de problemă:
Fie G=(V, A) un graf orientat, unde V are n elemente (n noduri) și A are m elemente (m muchii) memorat prin matricea ponderilor. Se cere să se determine toate drumurile de cost minim între oricare două noduri din graf .
Date de intrare:
Algoritmul pornește de la un graf orientat și ponderat cu n noduri
Se utilizează matricea costurilor A
Date de ieșire:
Lungimile tuturor drumurilor din graf
Un drum între două noduri selectate
Algoritmul lui Roy-Floyd (Rebedea et al, 15, c):
Pasul 1: Se generează matricea ponderilor de forma I. Memorându-se doar drumurile directe între oricare două noduri din graf
Pasul 2: Se încearcă pentru oricare pereche de noduri i, j să se obțină drumuri mai scurte trecând prin noduri intermediare k (kϵ1…n). Se compară lungimea lanțului a[i,j] cu lungimea lanțului care trece prin k: dacă a[i,j] > a[i,k]+a[k,j] atunci a[i,j] ←a[i,k]+a[k,j]
Pasul 3:Pentru două noduri citite x, y se cere să se reconstituie un lanț optim de la x la y.
Algoritmul Roy-Floyd pseudocod:
pentru k←1,n execută
pentru i←1,n execută
pentru j←1,n execută
dacă (A[i][k]≠INF și A[k][j]≠INF) atunci
dacă A[i][j]>A[i][k]+A[k][j] atunci
A[i][j] A[i][k] + A[k][j]
sfârșit dacă
sfârșit dacă
sfârșit pentru
sfârșit pentru
sfârșit pentru
3. Algoritmul Bellman-Ford
Algoritmul Bellman-Ford determină drumurile de cost minim dintre un nod desemnat ca sursă (plecare) și restul nodurilor accesibile lui chiar dacă există costuri negative pe arce. Aceste rezultate sunt furnizate numai în situația în care nodul de plecare nu face parte dintr-un circuit de cost negativ.
Algoritmul se aplică pentru următorul tip de problemă:
Se consideră un graf orientat G=(V, A) și o funcție de cost c : A R. Mulțimea V conține n vârfuri. Se desemnează un nod p de plecare. Pentru orice nod jV se cere determinarea drumului de cost minim de la p la j. Se vor detecta situațiile în care există circuite de cost negativ care includ nodul p.
Strategia algoritmului este aceea de minimizare succesivă a costului drumului minim de la nodul de plecare la orice alt nod din graf, până la obținerea costului minim. Această operație se face prin verificarea posibilității ca fiecare arc (i,j)U să participe la minimizarea distanței de la p la j. Operația se face cu o trecere completă prin toate arcele grafului.
Algoritmul Bellman-Ford pseudocod (Rebedea et al, 15, b):
pentru fiecare v V(G) execută
D[v] ∞
T[v] 0
sfârșit pentru
D[nod]0
pentru i=1,n-1 execută
dacă D[v]D[u]+A[u,v] atunci
D[v]D[u]+A[u,v]
T[v]u
sfârșit dacă
sfârșit pentru
pentru fiecare arc (u,v)A(G) execută
dacă D[v]D[u]+A[u,v] atunci
returnează Fals
sfârșit dacă
sfârșit pentru
returnează Adevarat
Algoritmul returnează Adevarat dacă și numai dacă graful nu conține circuite de cost negativ accesibile din sursa p și Fals în caz contrar.
II.3.2.6. Algoritmi elementari pentru grafuri orientate
Citirea matricei de adiacență
using namespace std;
#include<iostream>
#include<fstream>
#include"graf3.h"
int a[20][20],n,i,j;
int main()
{
citireo("graf.txt",a,n);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
cout<<a[i][j]<<" ";
cout<<endl;
}
return 0; }
Citirea listelor de adiacență
using namespace std;
#include<iostream>
#include<fstream>
#include"graf4.h"
nod *l[50];
int n,i;
int main()
{
cit_la_dinamic("graf.txt", l,n);
for (i=1;i<=n;i++)
{
cout<<"noduri adiacente cu "<<i<<endl;
while(l[i])
{
cout<<l[i]->info<<" ";
l[i]=l[i]->urm;
}
cout<<endl;
}
return 0; }
Citirea cu lista arcelor
using namespace std;
#include<iostream>
#include<fstream>
#include"graf6.h"
arc a[20];
int n,i;
int main()
{ cit_arce("graf.txt",a,n);
cout<<"lista arcelor este"<<endl;
for(i=1;i<=n;i++)
cout<<a[i].x<<" "<<a[i].y<<endl;
return 0; }
Citire cu matricea ponderilor
using namespace std;
#include <iostream>
#include<fstream>
#include "graf5.h"
int i,j,n;
float a[20][20];
int main()
{
cit_cost("graf2.txt",a,n);
for(i=1;i<=n;i++)
{for(j=1;j<=n;j++)
if(a[i][j]==pinf)
cout<<'\236'<<" ";
else
cout<<a[i][j]<<" ";
cout<<endl;}
return 0;
}
Drumuri de cost minim
Algoritmul lui Dijkstra (Cerchez et al, 06):
using namespace std;
#include<iostream>
#include<fstream>
#include"graf5.h"
float a[20][20], d[20], mini;
int s[20],t[20], n,i,j,r,poz;
void drum(int i)
{
if(t[i])
drum(t[i]);
cout<<i<<" ";
}
int main()
{
cit_cost("graf2.txt",a,n);
cout<<"r=";cin>>r;
s[r]=1;
for(i=1;i<=n;i++)
{
d[i]=a[r][i];
if(i!=r)
if(d[i]<pinf)
t[i]=r;
}
for(i=1;i<=n-1;i++)
{
mini=pinf;
for(j=1;j<=n;j++)
if(s[j]==0)
if(d[j]<mini)
{
mini=d[j];
poz=j;
}
s[poz]=1;
for(j=1;j<=n;j++)
if(s[j]==0)
if(d[j]>d[poz]+a[poz][j])
{
d[j]=d[poz]+a[poz][j];
t[j]=poz;
}
}
for(i=1;i<=n;i++)
cout<<d[i]<<" ";
cout<<endl;
for(i=1;i<=n;i++)
if(i!=r)
if(t[i])
{
cout<<"distanta de la "<<r<<" la "<<i<<" este: "<<d[i]<<endl;
drum(i);
cout<<endl;
}
else
cout<<"nu exista drum de la "<<r<<" la "<<i<<endl;
return 0;
}
Algoritmul Roy-Floyd (Sorin et al, 06):
using namespace std;
#include<iostream>
#include<fstream>
#include"graf5.h"
float a[20][20];
int n,i,j;
void drum(int i, int j)
{
int k=1, gasit=0;
while ((k<=n)&& !gasit)
{
if(i!=k && j!=k && a[i][j]==a[i][k]+a[k][j])
{
drum(i,k);
drum(k,j);
gasit=1;
}
k++; }
if(!gasit) cout<<j<<" ";
}
void scriu_drum(int nod_ini,int nod_fin)
{
if(a[nod_ini][nod_fin]<pinf)
{
cout<<"drumul de la "<<nod_ini<<" la "<<nod_fin<<" are lungimea "<<a[nod_ini][nod_fin]<<endl;
cout<<nod_ini<<" ";
drum(nod_ini,nod_fin);
}
else
cout<<"nu exista drum de la "<<nod_ini<<" la "<<nod_fin;
}
void lung_drum()
{ int i,j,k;
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(a[i][j]>a[i][k]+a[k][j])
a[i][j]=a[i][k]+a[k][j];
}
int main()
{ cit_cost("graf2.txt",a,n);
lung_drum();
scriu_drum(5,3);
return 0; }
III.1. Considerații metodice
III.1.1. Despre competențele secolului XXI
Educația, ca funcție deopotrivă socială și economică, are un rol fundamental în dobândirea de către cetățenii europeni a competențelor cheie necesare pentru adaptarea la aceste schimbări.
Idealul educațional, ca element reglator al noului curriculum nu mai are în vedere „formarea forței de muncă” ci dezvoltarea liberă integrală a individului uman (Bercu et al, 10). Competențele cheie sunt necesare oricărui individ pentru formarea și dezvoltarea personală, cetățenie activă, muncă și incluziune socială.
Cele opt domenii ale Competențelor cheie sunt:
Comunicarea în limba maternă
Comunicare în limbi străine
Competențe în matematică și competențe elementare în științe și tehnologie
Competențe în utilizarea noilor tehnologii informaționale și de comunicație
Competențe pentru a învăța să înveți
Competențe de relaționare interpersonală și competențe civice
Spirit de inițiativă și antreprenoriat
Sensibilizare culturală și exprimare artistică
III.1.2. Taxonomia lui Bloom
Dicționarul explicativ al limbii române definește învățătura ca fiind un precept la care se ajunge prin experiență practică sau pregătire teoretică.
Școala constructivistă urmărește învățarea prin înțelegere (Constantinescu, 15, a), învățarea cu sens, ceea ce presupune că lucrurile nou învățate sunt construite pe cele deja cunoscute. Înțelegerea unui concept înseamnă capacitatea de a-l explica prin referire la alte concepte. Dacă înțelegem ce învățăm, atunci informația nouă se conectează la cea existentă. În acelați timp, învățarea cu succes are loc printr-un proces personal de construire de ipoteze. Cel care învață își construiește cunoștințele. Numai elevul care a înțeles conceptul, va putea opera cu el.
Ce înseamnă a înțelege pe deplin un subiect? Ce înseamnă să poți utiliza ce ai învățat în situații noi?
Un răspuns a fost dat de către Benjamin Bloom care, în anul 1965 a descris procesul gândirii cognitive. Acesta a împărțit învățarea într-o paleta de sarcini sau abilități, numită taxonomie. Lista sa de procese cognitive este organizată pornind de la cele mai simple, amintirea cunoștințelor, până la cele mai complexe, cum ar fi emiterea unei judecăți cu privire la valoarea unei idei. Învățarea este completă dacă sunt atinse toate treptele.
Tot Bloom a definit noțiunea de obiectiv educațional ca fiind modalitatea de măsurare a procesului de învățare. În crearea obiectivelor operaționale, Bloom a dat o listă de verbe care pot fi utilizate pentru atingerea celor șase capacități (Bloom et al, 56):
Cunoștințe: amintirea informațiilor
Înțelegere: înțelegerea sensului, parafraza unui concept
Aplicare: utilizarea informațiilor sau a conceptului într-o situație nouă
Analiză: descompunerea informațiilor sau a conceptelor în părți pentru a le înțelege mai bine
Sinteză: folosirea ideilor pentru a produce ceva nou
Evaluare: emiterea de judecăți de valoare
III.1.3. Taxonomia lui Bloom revizuită
Lumea de astăzi este totuși diferită de cea pe care o reflecta taxonomia lui Bloom în 1956. Specialiștii în domeniul pedagogiei au învățat mult mai multe despre cum învață elevii și cum predau profesorii și recunosc acum că procesele de predare și învățare cuprind mult mai multe decât gândirea. Aceste procese implică și sentimentele și convingerile elevilor și ale profesorilor, precum și mediul social și cultural al clasei.
Ca orice model teoretic, taxonomia lui Bloom are punctele sale forte și slabe. Cel mai important punct forte al său este acela că a abordat subiectul foarte important al gândirii și a elaborat o structură în jurul său care poate fi utilizată de profesioniști. După crearea taxonomiei, unul din punctele slabe, subliniat de către însuși Bloom a fost diferența substanțială dintre categoria „cunoașterii” și celelalte cinci nivele ale procesului de gândire. Bloom a conștientizat diferența dintre cunoștință și procesele intelectuale și mentale realizate utilizând acea cunoștință.
În plus, atâtea activități care merită a fi desfășurate, cum ar fi problemele autentice sau proiectele, nu pot fi clasificate după taxonomie și numai încercarea de a le clasifica astfel le-ar diminua potențialul de oportunități de învățare.
Astfel, în 1999, Lorin Anderson și colegii săi au publicat o versiune actualizată a taxonomiei lui Bloom, care ia în considerare un număr mai mare de factori care au impact asupra predării și învățării. Această taxonomie revizuită încearcă să actualizeze unele concepte ale celei originale. Spre deosebire de versiunea din 1956, noua taxonomie face diferența între „ a ști ce”, conținutul gândirii și „a ști cum”, procedeele utilizate în rezolvarea problemelor.
Anderson, fost student a lui Bloom a împărțit cunoștințele în patru categorii: cunoștințe faptice, cunoștințe conceptuale, cunoștințe procedurale și cunoștințe metacognitive.
Potrivit acestei taxonomii, fiecărui nivel de cunoștințe îi poate corespunde un nivel al proceselor cognitive, astfel că elevul poate să-și amintească cunoștințe faptice sau procedurale, să înțeleagă cunoștințe conceptuale sau metacognitive sau să analizeze cunoștințe metacognitive sau faptice. După Anderson și colegii săi, „Învățarea care are sens le oferă elevilor cunoștințele și procesele cognitive de care au nevoie pentru a putea rezolva probleme.” (Anderson et al, 01).
Cunoștințele faptice sunt acele noțiuni de bază care sunt necesare elevilor pentru familiarizarea cu anumite domenii, discipline sau probleme.
Cunoștințele conceptuale sunt acele informații pe care elevii le utilizează pentru interdisciplinaritate și conexiuni cu viața reală.
Cunoștințele procedurale sunt reprezentate de metodele de descoperire, analizare, criticare și adaptare a algoritmilor și tehnicilor de rezolvare a problemelor la cele din viața reală.
Cunoștințele metacognitive sunt noțiunile necesare pentru cunoașterea în sine, precum și întelegerea procesului de învățare și gandire propriu.
Deși pare surprinzător, Bloom a definit primele trei tipuri de cunoștințe în taxonomia proprie. Aceste noțiuni au fost puțin înțelese de către profesori și mult mai puțin aplicate în decursul timpului. În general, au fost utilizate doar cele șase nivele ale procesului de gândire precum și lista verbelor.
Comparație între cele două taxonomii:
Taxonomia revizuită pune accentul pe modalitatea de atingere a capacităților descrise. Astfel, atingerea și depășirea unui nivel implică găsirea răspunsului adecvat pentru fiecare din întrebările de mai jos:
Reamintirea: pot elevii să își amintească informațiile?
Înțelegere: pot elevii să explice idei sau concepte?
Aplicarea: pot elevii să utilizeze înformațiile în situații noi?
Analizarea: pot elevii să facă distincția dintre diferite informații?
Evaluarea: pot elevii să justifice o decizie?
Crearea: pot elevii să utilizeze informațiile pentru a crea propriul punct de vedere?
III.1.4. Predarea prin proiecte
Autoînvățarea și învățarea informală în grup sunt modalități importante de dezvoltare a abilităților și competențelor în utilizarea noilor tehnologii informaționale și de comunicare. Aceste procedee sunt extrem de importante și în cadrul educației formale a elevilor. Integrarea tehnologiilor informaționale și de comunicație în procesul educativ oferă persoanelor posibilitatea de a-și dezvolta relațiile sociale precum și competențele de comunicare, acest lucru poate duce la o învățare activ-partcipativă din partea elevilor. Instrumentele și platformele e-learning și de comunicare socială devin din ce în ce mai populare. Acestea sunt blog-urile, wiki-urile, site-uri sociale virtuale, alături de alte instrumente precum telefoanele mobile, tabletele, e-reader-urile și altele. Acestea sunt ușor de utilizat, accesibile și larg răspândite.
Dezvoltarea abilităților de inovație necesită metodologii și strategii de predare/învățare/evaluare noi, bazate pe metode de învățare activă precum: rezolvarea în mod creativ a problemelor, învățarea prin descoperire, învățarea prin practică, învățarea prin experimentare, gândirea critică și creativitatea (Constantinescu, 15, b).
Proiectele ar trebui să dezvolte abordări inovatoare de consolidare a abilităților de a învăța și a capacităților de inovare. Se dorește realizarea de proiecte interdisciplinare sau de abordare a problemelor din viața de zi cu zi care utilizează instrumente și tehnologii moderne și care ating următoarele aspecte:
încurajarea creativității
genereze idei noi și soluții inovatoare
încurajarea învățării prin autointerogare și rezolvare de probleme
colaborarea în cadrul unui grup de lucru
autoevaluarea progresului făcut
Dintre metodele interactive utilizate pe scară largă în școli, metoda proiectelor interdisciplinare și-a dovedit în ultimii ani o deosebită eficiență.
Metoda proiectelor ca strategie de predare-învățare-evaluare se concentrează pe cercetarea realizată de elevi, pe depistarea detaliilor și înțelegerea subiectului în întreaga sa amploare, pe generarea ideilor proprii, pe crearea unui produs final și pe susținerea acestuia în fața colegilor ceea ce constituie garanția activității de învățare, deoarece permite folosirea unei multitudini de tehnici de structurare a materiei și poate fi folosită la toate nivelurile de școlarizare.
Metoda proiectelor asigură o învățare diferențiată, bazată pe experiență, individualizată, în cadrul căreia elevul experimentează lucruri noi. Elevii sunt permanent bombardați cu informații din mass-media, iar profesorii sunt puși în fața unor elevi care dețin deja informațiile sub diverse forme. Profesorii sunt puși în postura de a corecta informațiile primite și de a determina elevii să adopte o atitudine pozitivă în ceea ce privește procesul instructiv-educativ. Unul dintre dezavantajele fluxului continuu de informații a accestui secol este scăderea interesului elevilor pentru procesul de învățare. Este cazul să ne întrebăm din ce în ce mai mult dacă reproducerea informațiilor este necesară reușitei elevilor, în momentul în care informațiile sunt doar la un clic distanță.
Utilizând metoda proiectului se încearcă îmbinarea învățării spontane cu cea dirijată. Această metodă oferă posibilitatea de a respecta ritmul individual de învățare și înțelegere a fiecărui copil din clasă, cadrul didactic stabilind obiectivele de învățare, dar și metodele specifice prin care va urmări realizarea acestora. Copiii învață în ritmuri diferite, deci strategiile de predare-învățare-evaluare trebuie adaptate în consecință. Toți elevii au puncte forte dar și puncte slabe. Pentru a depăși punctele slabe, educatorul dorește să se bazeze pe interesele și pe capacitățile fiecărui copil. Este necesară deci o înțelegere prealabilă a dinamicii clasei de elevi, precum și a nivelului fiecărui elev și a intereselor acestora.
Cadrul didactic își asumă prin această metodă de predare rolul de mediator în cadrul clasei și nu numai. Transferul de informații nu va mai fi într-un sens unic, de la profesor la elev ci va deveni o descoperire, o îndrumare și o dezbatere pentru a ajunge la informațiile corecte. La fiecare unitate de învățare, este necesară stabilirea unei strategii de predare-învățare-evaluare astfel încât clasa de elevi să poată atinge un nivel de înțelegere acceptabil.
Elevul nu va mai fi doar receptor, ci va fi un factor important în structurarea și implementarea metodei proiectului pentru o unitate de învățare. El va fi implicat activ în înțelegerea materiei, răspunderea la întrebările întâlnite pe parcurs, găsirea unor noi modalități de abordare a informațiilor, crearea unui produs final care să arate nivelul de înțelegere atins ca și prezentarea acestui produs și discutarea ideilor de îmbunătățire primite din exterior.
Această metodă de predare-învățare-evaluare dorește să scoată elevii alături de profesori din zona de confort și să îi pună în situații cât mai apropiate de viața reală. Abordarea unei noi metode activ-participative nu înseamnă că profesorul nu mai este o parte importantă a procesului educativ ci înseamnă includerea elevului în propria învățare. În utilizarea acestei metode se pune accentul pe dezvoltarea abilităților necesare în acest secol.
Abilități necesare în secolul XXI (Rychen et al, 03), conform celor opt competențe cheie date de comisia europeană sunt:
Responsabilitate și capacitate de adaptare, obținute prin:
exersarea responsabilității personale și a flexibilității în contexte legate de propria persoană, loc de muncă și comunitate
stabilirea și atingerea unor standarde și țeluri ridicate pentru sine și pentru ceilalți
tolerarea ambiguității
Competențe de comunicare, realizate prin:
înțelegerea și realizarea unei comunicări eficiente verbale, scrise și multimedia, într-o varietate de forme și contexte
Creativitate și curiozitate intelectuală, realizată prin:
dezvoltarea, implementarea și comunicarea ideilor noi altor persoane
deschidere și receptivitate la nou, perspective variate
Gândire critică și gândire sistemică, obținută prin:
exersarea gândirii în ce privește înțelegerea și realizarea unor alegeri complexe
înțelegerea conexiunilor dintre sisteme
Informații și abilități media, realizate prin:
analizarea, accesarea, administrarea, integrarea, evaluarea și crearea de informații în diverse forme și medii
Capacități de colaborare și interpersonale, obținute prin:
demonstrarea capacităților de lucru în echipă și de conducere
adaptarea la diverse roluri și responsabilități
colaborarea productivă cu ceilalți
conduită empatică
respectarea altor puncte de vedere
Identificarea, formularea și soluționarea problemelor, realizată prin:
capacitatea de a depista, formula, analiza și rezolva probleme
Auto-formare, descrisă de:
monitorizarea propriilor nevoi de înțelegere și învățare
localizarea resurselor corespunzătoare
transferul cunoștințelor dintr-un domeniu în altul
Responsabilitate socială, realizată prin:
acționarea în mod responsabil, ținând cont de interesele comunității
demonstrarea unui comportament etic în contexte legate de propria persoană, loc de muncă și comunitate
Dar, nu toate unitățile de învățare pot să includă un proiect, însă în momentul în care învățarea pe bază de proiect este adecvată, integrarea unui proiect poate stimula semnificativ învățarea elevilor. De aceea, există nivele diferite ale modelării unei unități de învățare:
bazată pe proiect de la început până la sfârșit
include un proiect ca și experiență culminantă
include un proiect într-un anumit segment al unității.
III.1.4.1. Etapele implementării
Un proiect bun necesită o bună planificare și o bună organizare în avans, realizată de către profesor. Este foarte ușor să se greșească implementarea proiectului, începând de la unitatea la care se dorește să se integreze metoda proiectului, continuând cu cerințele proiectului care să nu fie în concordanță cu nivelul clasei de elevi și finalizând cu evaluarea proiectelor care să nu atingă toate tipurile de evaluare. O modalitate de a corecta o parte din aceste posibile erori este de a realiza proiectul de către profesor pentru a reuși să structureze un proiect care să atingă toate obiectivele și care să asigure o învățare adecvată pentru întreaga clasă de elevi.
După stabilirea unității și generarea primelor idei, profesorii ar putea parcurge o listă de întrebări despre proiectul ce urmează să fie implementat. Unele criterii pentru lista de verificare a caracteristicilor proiectului este:
Elevii se află în centrul procesului de instruire și își demonstrează cunoștințele și abilitățile prin intermediul produselor care sunt prezentate
Proiectul are conexiuni cu lumea reală și implică metode de evaluare multiple și continue
Proiectul implică sarcini de lucru și activități conectate, care se desfășoară într-o anumită perioadă de timp
Tehnologia sprijină și îmbunătățește procesul de învățare al elevilor, sprijinind diverse stiluri de învățare
Abilitățile de gândire de nivel superior sunt incluse în activitatea de proiect.
Un alt aspect pozitiv în metoda proiectului este utilizarea tuturor tipurilor de evaluare (inițială, sumativă și formativă). De asemenea, utilizarea autoevaluării și interevaluării permit elevilor dezvoltarea unui spirit critic pe lângă acceptarea opiniilor din exterior pentru îmbunătățirea propriei învățări. În acest sens, evaluarea integrată și continuă stă la baza învățării bazate pe proiect. În cadrul metodei proiectului, evaluarea este integrată astfel încât: utilizează o varietate de strategii de evaluare, include metode de evaluare pe tot parcursul procesului de instruire, evaluează obiectivele importante ale unității de învățare și nu în ultimul rând, implică elevii în propria evaluare. Implicarea elevilor în evaluarea proprie și în interevaluare este un proces amplu. În general, în procesul educativ, elevii se așteaptă la o notare din exterior, de cele mai multe ori criteriile nefiind clare acestora. În acest mod, se dezvoltă de către elevi percepția greșită asupra nivelului propriu de înțelegere precum și asupra evaluării. Prin această meodă, evaluarea nu mai este privită ca o simplă cotare a nivelului de informații deținute ci este privită ca un instrument de ghidare pentru atingerea tuturor obiectivelor proiectului. Elevii fiind evaluați continuu, sunt încurajați să utilizeze rezultatele evaluării continue pentru îmbunătățirea produsului final și atingerea unui nivel ridicat de înțelegere a unității de învățare.
Pentru a implica elevii în procesul de evaluare, cadrul didactic le va asigura: criterii clare, comunicate de la începutul unității, exemple și sugestii pentru o activitate de calitate ridicată, oportunități de monitorizare a propriului progres, metode pentru oferirea unui feedback constructiv colegilor și pentru încorporarea feedback-ului primit de la ceilalți pentru a îmbunătăți activitatea proprie, timp pentru reflecție și pentru îmbunătățirea produselor activității și sprijin în stabilirea unor obiective noi, pentru activitățile ulterioare de învățare.
Planificarea evaluării continue, centrate pe elev, necesită o planificare în prealabil. Evaluarea înițială dă informații despre nivelul cunoștințelor elevilor înainte de începerea capitolului și despre modalitatea de abordare a unității de învățare. Evaluarea abordată prin metoda proiectului pune accent pe gândirea de ordin superior și abilitățile necesare în secolul XXI în activitatea elevilor, implicarea elevii în înțelegerea așteptărilor cu privire la respectivul proiect, a obiectivelor și a criteriilor de evaluare înainte de a începe lucrul la proiect, utilizarea unei grile cu criterii pe tot parcursul proiectului pentru a înțelege așteptările și cel mai important, elevii creează grile și alte evaluări pentru a le folosi pe parcursul unui proiect. Evaluarea în cadrul unui proiect va monitoriza și comportamentul individual precum și cel de grup, va monitoriza de asemenea și învățarea independentă. Abordarea unei evaluări care să implice și elevii necesită o discutare a tuturor criteriilor și așteptărilor. Informațiile obținute ajută cadrul didactic în a oferi sugestii, a da instrucțiuni și a răspunde la întrebări. Evaluarea sumativă va da informații cu privire la instruirea viitoare precum și informații despre alte instrumente de evaluare și alte teme pentru proiecte.
Un alt aspect pozitiv în utilizarea metodei proiectului este utilizarea IT și a Internet-ului în căutarea informațiilor. Este necesară combaterea ideii că Internet-ul conține informații corecte în totalitate precum și utilizarea Internet-ului numai pentru aspectele relaxante. Internet-ul poate fi un instrument de documentare utilizat cu succes în găsirea informațiilor, generearea întrebărilor și găsirea unor răspunsuri care pot duce la abordări unice la probleme practice. Internet-ul poate fi un instrument puternic de cercetare, colaborare și comunicare cu alții. Instrucțiunile pentru o utilizare loială descriu modurile în care materialele protejate de drepturile de autor pot fi folosite în mod legal de către profesori și elevi în clasă. În acest scop, listele bibliografice pot fi create în diverse formate pentru elevii de toate vârstele. Elevii dezvoltă spiritul critic în legătură cu informațiile găsite pe diverse site-uri prin stabilirea factorilor ce trebuie luați în considerare în momentul în care se stabilește credibilitatea și valoarea unui site web. Instrumentele care permit elevilor să comunice cu persoane din toată lumea prin Internet: E-mail, Chat-uri online, mesaje instant și protocol pentru Internet, Voice Over IP, precum și blog-uri, wiki-urile și documentele online, permit elevilor să colaboreze la proiecte prin partajarea și oferirea de răspunsuri cu privire la activitatea celorlalte persoane.
Este important ca elevi să conștientizeze aspectele legale legate de utilizarea Internet-ului în realizarea unui proiect. Astfel, pe lângă stabilirea credibilității unui site, mai sunt și aspectele legate de drepturile de autor. Copyright-ul sau dreptul de autor este dreptul exclusiv de a produce și reproduce, de a reprezenta în public sau de a publica o operă originală artistică sau literală. Aproape orice creat privat și original este protejat, indiferent dacă are o înștiințare sau nu. De asemenea, este bine de știut factorii care determină utilizarea legală a unei informații: scopul și caracterul folosirii, natura lucrării protejate, mărimea părții utilizate și efectul folosirii asupra potențialei piețe.
III.1.4.2. Avantaje și dezavantaje
Metoda proiectului asigură elevilor următoarele avantaje:
urmărește studierea și rezolvarea unei probleme concrete, de viață
elevul exersează lucrul individual, pe grupe sau în echipă
folosește cunoștințe de la mai multe discipline, pe care le subordonează realizării unui scop
exersează elaborarea și generarea răspunsurilor la întrebări precum și la formularea de întrebări
își formează o expunere liberă
realizează o sarcină într-un timp determinat
lucrul în grup îi ajută pe elevi să asimileze cunoștințe în mod independent și să-și formeze atitudini ca: responsabilitate, inițiativă, perseverență, cooperare etc.
dezvoltarea abilităților secolului XXI
implicarea elevilor în procesul de predare-învățare-evaluare ceea ce duce la un interes crescut al elevilor către disciplina predată
dezvoltarea creativității elevilor
dezvoltarea modalității de utilizare a informațiilor teoretice în aplicații practice
finalitățile se concretizează în lucruri importante pentru ei care le creează satisfacții
Există și unele dezavantaje, cele mai evidente fiind:
nu poate fi aplicată la toate unitățile de învățare
cadrul didactic este cel care realizează schema de derulare a proiectului, activitățile practice, obiectivele, fișele de evaluare precum și monitorizarea realizării proiectului; acestea înseamnă o muncă susținută în implementarea și realizarea unui proiect
lipsa timpului necesar realizării unui proiect doar în timpul orelor de studiu
programele încărcate determină cadrele didactice să elimine metodele activ-participative
învățarea centrată pe elev este implementată doar la nivel teoretic în sistemul național de învățământ
modificarea abordării procesului educativ de către profesori – centrarea pe competențele secolului XII și nu pe reproducerea noțiunilor teoretice
lipsa implicării elevilor în această metodă datorată unui volum de muncă mai ridicat
tendința elevilor de a privi procesul educativ ca un proces static
neadaptarea cerințelor proiectului la nivelul clasei sau la viața reală
Integrarea noilor tehnologii în educație aduce toate avantajele dezvoltării abilităților secolului XXI, precum și dezavantajele utilizării fără un scop bine determinat. Ca și profesori, în acest secol, trebuie să dezvoltăm elevilor abilități necesare în viitor. Fiecare profesor dorește o atragere a interesului elevilor către disciplina predată. Este prin natura meseriei faptul că fiecare profesor adaugă câte un pic din propria personalitate și din propriile cunoștințe elevilor cu care interacționează.Învățarea pe tot parcursul vieții este abilitatea necesară integrării în societatea europeană care continuă să se dezvolte.
III.1.5. Implementarea la clasă
Am aplicat metoda proiectului în anii școlari 2013-2014 și 2014-2015, la finalul capitolului grafuri neorientate și orientate la clasa XI Matematică – Informatică intensiv informatică, ca o experiență culminantă. Proiectele au fost implementate la finalul unității, după parcurgerea materiei, ca răspuns la întrebările elevilor legate de legătura dintre grafurile neorientate și orientate cu viața reală. Elevii au avut la dispoziție 2 săptămâni (14 de ore) pentru realizarea produselor finale și 5 ore pentru prezentare și evaluare. Clasele au fost împărțite în grupe de 3 elevi, fiecare primind o problemă. Produsul final a constat dintr-o prezentare power point care să conțină:
enunțul problemei
cerințele problemei
descrierea metodei de rezolvare, amintind noțiunile teoretice utilizate în proiect
metoda de adaptare a noțiunilor teoretice la problema practică
programul C++ corespunzător
fișele de monitorizare a proiectului, fișele de evaluare și autoevaluare
Elevii au avut la dispoziție, ca surse de documentație manualul de informatică, portofoliul personal și Internet-ul. Fiecare grupă a stabilit rolurile în cadrul grupului, o singură persoană fiind responsabilă cu prezentarea produsului final. Fiecare grupă a fost implicată în evaluarea celorlalți elevi, implicând discuții cu privire la proiectul fiecărei grupe, formularea de întrebări pertinente cu privire la problema prezentată și la rezolvarea acesteia.
La diseminare, fiecare elev a notat colegii din clasă și s-a autoevaluat. Am utilizat aceste note pentru a realiza o medie, care a reprezentat nota finală pentru întreg proiectul. În cadrul diseminării am realizat și un vot cu privire la cea mai eficientă grupă, criteriile fiind axate pe modul în care au colaborat, modul în care au rezolvat eventualele conflicte, ca și modul în care au decizii de grup.
III.1.5.1. Teme de proiecte practice
„Theory without practice is useless; practice without theory is blind” Roger Bacon
Realizarea unei hărți rutiere a județului Bacău. Calcularea celor mai scurte rute din orasul Bacău către toate județele învecinate.
Realizarea unei hărți pentru transportul în comun a orașului Iași. Un călător dorește să viziteze tot orașul, utilizând transportul în comun, cu un cost minim.
Cablurile de înaltă tensiune care pornesc dintr-o centrală pot fi și ele reprezentate cu ușurință cu ajutorul unui graf orientat, indicând și direcția de deplasare a curentului. În acest caz, centrala este un nod sursă.
În imperiul maleficului Costel s-a instaurat anarhia. În imperiu sunt n orașe, numerotate de la 1 la n, unite prin m șosele unidirecționale, fiecare șosea fiind controlată de o bandă afiliată la unul dintre cele k sindicate banditești existente în imperiu, numerotate de la 1 la k. Pentru a călători prin pe șoselele din imperiu, orice călător trebuie să plătească taxe sindicatelor: plata taxei către un anumit sindicat îi permite călătorului să folosească nelimitat orice șosea controlată de o bandă afiliată acelui sindicat. Pentru toate sindicatele se plătește aceeași taxă. Călătorul Gigel trebuie să ajungă din orașul p în orașul q. Determinați numărul minim de sindicate banditești cărora Gigel trebuie să le plătească taxe, pentru a putea realiza călătoria dorită.
Pe o arena hipică ce urmează să organizeze un concurs de călărie, s-au montat n obstacole, numerotate 1,2, 3,….., n. Traseul pe care îl vor parcurge călăreții în timpul concursului trebuie să țină cont de următoarele condiții:
se poate începe cu orice obstacole și trebuie sărite toate obstacolele, fiecare o singura dată;
distanța între oricare doua obstacole poate fi parcursa numai într-un singur sens, pe care călăreții îl cunosc la intrarea în concurs Să se conceapă un program cu ajutorul căruia călăreții să-și stabilească traseul
Într-un complex de insule exotice, un turist dorește să realizeze cât mai multe excursii între insule, încadrându-se într-o suma inițială. Scrieți programul care determină toate traseele de la locul inițial până la insulele vizitate.
Criterii pentru proiecte
Pentru fiecare proiect, unele cerințe au fost comune cum ar fi: citirea datelor din fișier, utilizarea matricei de adiacență, determinarea celui mai scurt drum, determinarea unui lanț de la un nod dat la alt nod din graf, determinarea drumurilor de cost minim în graf. Restul cerințelor, cu privire la implementare au fost personalizate.
Criteriile comune de evaluare a proiectelor au fost:
III.1.5.2. Propuneri proiecte
Modul de implementare pentru o rețea feroviară. Se va pune accent pe introducerea datele pentru un orar al trenurilor, cum se modelează acest orar cu ajutorul unui graf orientat și determinarea drumurilor optime (trasee avînd timp minim de călătorie) între două stații.
Implementarea căilor aeriene cu ajutorul grafurilor. Nodurile sunt intersecțiile sau aeroporturile și muchiile sunt rutele. Implementarea va realiza un orar pentru o mulțime de avioane, astfel încât fiecare călător să știe costul unei călătorii de la oricare nod la toate celelalte, precum și timpul în care se realizează călătoria.
Cu ajutorul grafurilor se poate reprezenta și un sistem de canalizare dintr-un cartier al unui oraș.
Reprezentarea unui sistem de încălzire sau rețeaua de apa curentă. Determinarea costurilor de la toate nodurile la unul cu destinație specială.
Determinarea și reprezentarea numărului de izomeri ai compușilor organici, utilizând grafurile neorientate și orientate.
Să se implementeze o rețea electrică cu ajutorul grafurilor orientate, să se verifice funcționarea corectă a rețelei. Să se determine ciclurile grafului orientat.
Să se implementeze o rețea de electricitate dintr-o localitate, care să fie în totalitate ecologică și să nu fie conectată la nici o rețea de electricitate națională. Cum poate fi structurată informatic o astfel de rețea?
III.1.5.3. Exemple practice
Proiectele următoare au fost realizate în anul școlar 2013-2014 (primele patru) și în anul școlar 2014-2015 (ultimele patru). Am reluat unele din problemele propuse în al doilea an școlar, modificând doar unele din cerințe. După cum se poate observa și mai jos, diferiți elevi au abordări diferite cu privire la aceeași temă de proiect (exemplul 2 și exemplul 5).
Exemplul 1: Rețea informațională
N localități trebuie unite într-o rețea informațională astfel încât informația transmisă dintr-o localitate A să poată fi recepționată în orice altă localitate printr-un canal de legatură direct sau prin intermediul altor centre, cu condiția ca lungimea totală a acestei rețele să fie minimă. Se știe că între oricare două localități este posibilă trasarea unui canal de legatură informațională. Programul va determina timpul în care pot comunica calculatoarele din rețea.
Date de intrare:
Citirea datelor pentru cele n orașe,
Citirea coordonatelor pentru localități
Graful neorientat care mapează harta
Cerințe:
Descrierea topologiei de tip rețea, mod de funcționare, avantaje și dezavantaje
Posibilitatea adăugării și eliminării orașelor
Posibilitatea afișării tuturor orașelor din hartă
Calcularea prin mesaje de tip ping a timpului de transmitere a mesajelor între două localități
Realizarea unui meniu cu cerințele de mai sus
Codul sursă este:
#include <iostream>
#include <math.h>
#include <conio.h>
#include <fstream>
#include <string>
#include <limits>
#include<string.h>
using namespace std;
struct oras {
string orasul;
int x,y;
} ora;
void functiaPrincipala() {
int optiune;
cout << "1) Adauga localitate: " << endl;
cout << "2) Stergerea unei localitati existente: " << endl;
cout << "3) Stergerea tuturor localitatilor existente: " << endl;
cout << "4) Afisarea tuturor localitatilor existente: " << endl;
cout << "5) Calculul distantei a doua localitati si testarea legaturii dintre centru informational si localitate: " << endl;
cout << "Introduceti optiunea: " << endl;
cin >> optiune;
switch (optiune) {
case 1:
adaugaOras(); break;
case 2:
stergeLocatie(); break;
case 3: break;
case 4: break;
case 5: break;}
getch();}
void calculator(float coordonate_x1, float coordonate_y1, float coordonate_x2, float coordonate_y2) { float rezultat;
rezultat = sqrt((coordonate_x2 * coordonate_x1) – (coordonate_x2 * coordonate_x1) + (coordonate_y2 * coordonate_y1) – (coordonate_y2 * coordonate_y1));
cout << "Distanta de la orasul 1 la orasul 2 este de: " << rezultat<<" "<<"PING:";}
void adaugaOras() {
int n;
ofstream fisierOutt("ORASE.txt", ios::app);
cout << "Cate orase doresti sa introduci: ";
cin >> n;
if (fisierOutt.is_open()) {
for (int i = 0; i < n; i++) {
cout << "Introdu numele orasului: ";cin >> ora.orasul;
cout << "Introdu coordonatele x: ";cin >> ora.x;
cout << "Introdu coordonatele y: ";cin >> ora.y;
fisierOutt << ora.orasul << " " << ora.x << " " << ora.y << endl;cout << endl << endl;}}
else
{cout << "Nu am putut deschide fisierul";}
fisierOutt.close();
cout << endl;}
void stergeLocatie()
{}
void repetare()
{char optiune;
cout << "Doriti sa mai adaugati ceva sau sa iesiti?(d/n)";cin >> optiune;
if (optiune == 'd')
{functiaPrincipala();}
else
exit ;
}
main()
{functiaPrincipala();
adaugaOras();
repetare();
}
Exemplul 2: Rețele de calculatoare
Rețeaua Internet este o structură configurată la nivel hardware și software. Configurarea hardware este dată de modul în care sunt legate fizic calculatoarele între ele. Aceste legături poartă denumirea de topologie fizică.
Date de intrare:
Fișierul text care memorează un graf
Numărul de noduri din graf
Graful este neorientat
Cerințe:
Clasificarea topologiilor de rețea
Descrierea tipurilor de topologii pentru rețelele de calculatoare
Să se stabilească dacă graful citit din fișier poate mapa o topologie fizică de rețea
În caz afirmativ, să se specifice ce tip de topologie este
Codul sursă este:
#include <iostream>
#include<fstream>
using namespace std;
int a[50][50],n,i,j,gasit,t[50],c,d,suma,z,q=0, p,v,m=0,l;
void citire(char b[20],int a[50][50],int &n)
{ ifstream f("graf.txt");
f>>n;
while(f>>i>>j)
a[i][j]=a[j][i]=1;
f.close();}
void df(int nod)
{ int k,s[50];
s[nod]=1;
for(k=1;k<=n;k++)
if(a[nod][k]==1)
{ a[k][nod]=0;
if(s[k]==0)
df(k);
else
gasit=1; }}
void refac(int nod)
{ if(nod!=0)
{ refac(t[nod]);
cout<<nod<<" "; }}
void df_r(int nod)
{ int k,s[50];
s[nod]=1;
for(k=1;k<=n;k++)
if(a[nod][k]==1&&s[k]==0)
{ t[k]=nod;
df_r(k); }}
int main()
{ int x,s=0;
cout<<"1.Conexiune de tip stea."<<endl;
cout<<"2.Conexiune de tip inel."<<endl;
//cout<<"3.Conexiune de tip magistrala."<<endl;
cout<<"4.Verificare tip conexiune."<<endl;
// cout<<"5.Conexiune de tip arbore."<<endl;
cout<<"6.Conexiune de tip graf complet."<<endl;
cout<<"0.Iesire"<<endl;
cout<<"x=";cin>>x;
switch(x)
{ case 0:x=0;
return 0;
break;
case 1:x=1;
{cout<<"1.Conexiune de tip stea."<<endl;
citire("graf.txt",a,n);
for(i=1;i<=n;i++)
{v=0;
for(j=1;j<=n;j++)
if(a[i][j]==1)
v=v+a[i][j];
if((v==1)||(v==n-1))
m=m+v;}
if(m==2*(n-1))
cout<<"DA"<<endl;
else
cout<<"NU"<<endl; }
break;
cout<<"x=";cin>>x;
case 2:x=2;
{cout<<"2.Conexiune de tip inel."<<endl;
citire("graf.txt",a,n);
for(i=1;i<=n;i++)
{df(i);
if(gasit)
s++;}
citire("graf.txt",a,n);
for(i=1;i<=n;i++)
{v=0;
for(j=1;j<=n;j++)
if(a[i][j]==1)
v=v+a[i][j];
if(v==2)
m=m+v; }
if((m==2*n)&& (s==n))
cout<<"DA"<<endl;
else cout<<"NU"<<endl;}
break;
cout<<"x=";cin>>x;
case 3:x=3;
{cout<<"3.Conexiune de tip magistrala."<<endl;
citire("graf.txt",a,n);
cout<<"c=";cin>>c;
cout<<"d=";cin>>d;
df_r(c);
if(t[d]!=0)
refac(d);}
cout<<"x=";cin>>x;
break;
case 4:x=4;
{cout<<"4.Verificare tip conexiune."<<endl;
{
citire("graf.txt",a,n);
for(i=1;i<=n;i++)
{v=0;
for(j=1;j<=n;j++)
if(a[i][j]==1)
v=v+a[i][j];
if((v==1)||(v==n-1))
m=m+v;}
if(m==2*(n-1))
cout<<"Conexiune de tip stea"<<endl;}
{ citire("graf.txt",a,n);
for(i=1;i<=n;i++)
{df(i);
if(gasit)
s++;}
citire("graf.txt",a,n);
for(i=1;i<=n;i++)
{v=0;
for(j=1;j<=n;j++)
if(a[i][j]==1)
v=v+a[i][j];
if(v==2)
m=m+v; }
if((m==2*n)&& (s==n))
cout<<"Conexiune de tip inel"<<endl; }
{ citire("graf.txt",a,n);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(i==j&&a[i][j]==0)
l=1;
else l=0;
citire("graf.txt",a,n);
for(i=1;i<=n;i++)
{v=0;
for(j=1;j<=n;j++)
if(a[i][j]==1)
v=v+a[i][j];
if(v==n-1)
m=m+v;}
if((m==(n*n)-n)&&(l==1))
cout<<"Conexiune de tip graf completa"<<endl; }
cout<<"x=";cin>>x; }
break;
case 5:x=5;
{int s[50];
cout<<"5.Conexiune de tip arbore."<<endl;
citire("graf.txt",a,n);
df(1);
suma=0;
for(i=1;i<=n;i++)
suma+=s[i];
if(suma!=n)
cout<<"NU ESTE CONEX"<<endl;
else if(gasit)
cout<<"Are ciclu"<<endl;
else cout<<"DA"<<endl;}
cout<<"x=";cin>>x;
break;
case 6:x=6;
{ cout<<"Conexiune de tip graf complet"<<endl;
citire("graf6.txt",a,n);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(i==j&&a[i][j]==0)
l=1;
else l=0;
citire("graf6.txt",a,n);
for(i=1;i<=n;i++)
{v=0;
for(j=1;j<=n;j++)
if(a[i][j]==1)
v=v+a[i][j];
if(v==n-1)
m=m+v;}
if((m==(n*n)-n)&&(l==1))
cout<<"DA"<<endl;
else cout<<"NU"<<endl; }
cout<<"x=";cin>>x;
break; }
return 0;
}
Exemplul 3: O centrală de telefonie fixă
Să se implementeze o centrală de telefonie fixă cu ajutorul grafurilor orientate. Să se simuleze căderea unui nod de comunicație. Cum se va modifica modul de comportare a rețelei în cazul în care un nod nu este funcțional, eliminarea rețelei de comunicație nefiind o soluție posibilă.
Date de intrare:
Rețeaua de telefonie fixă
Graful orientat care mapează această rețea
Nodurile care vor fi evitate, în cazul defecțiunii acestora
Cerințe:
Să se calculeze drumul de cost minim de la un nod oarecare la alt nod din rețea
Să se afișeze drumul, în cazul în care se dorește evitarea unui anumit nod
Să se șteargă din matricea costurilor un nod și să se scrie un nou drum între două noduri din rețea
Să se afișeze un mesaj în cazul în care nu se poate ajunge la un nod din rețea
Codul sursă:
using namespace std;
#include<iostream>
#include<fstream>
float A[50][50];
int n;
const float PInfinit=1.e20;
void Citire_cost(char Nume_fis[20],float A[50][50],int &n)
{int i,j;
float c;
fstream f(Nume_fis,ios::in);
f>>n;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(i==j)
A[i][j]=0;
else
A[i][j]=PInfinit;
while(f>>i>>j>>c)
A[i][j]=c;
f.close();}
void Drum(int i,int j)
{int k=1,gasit=0;
while((k<=n)&&(!gasit))
{if((i!=k)&&(j!=k)&&(A[i][j]==A[i][k]+A[k][j]))
{Drum(i,k);
Drum(k,j);
gasit=1;}
k++;}
if(!gasit)
cout<<j<<" ";}
void Scriu_drum(int Nod_Initial,int Nod_Final)
{if(A[Nod_Initial][Nod_Final]<PInfinit)
{cout<<"Drumul de la "<<Nod_Initial <<" la "<<Nod_Final<<" are lungimea "<<A[Nod_Initial][Nod_Final]<<endl;
cout<<Nod_Initial<<" ";
Drum(Nod_Initial,Nod_Final);}
else
cout<<"Nu exista drum de la "<<Nod_Initial<<" la "<<Nod_Final;}
void Lungime_Drumuri()
{int i,j,k;
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(A[i][j]>A[i][k]+A[k][j])
A[i][j]=A[i][k]+A[k][j];}
void Stergere(int q)
{int i,j;
for(i=1;i<=n;i++)
A[i][q]=PInfinit;
for(j=1;j<=n;j++)
A[q][j]=PInfinit;}
int main()
{int g,h,q;
cout<<"Primul nod : ";cin>>g;
cout<<"Al doilea nod : ";cin>>h;
cout<<"Evitarea nodului : ";cin>>q;
Citire_cost("Graf.txt",A,n);
Stergere(q);
Lungime_Drumuri();
Scriu_drum(g,h);}
Exemplu 4: O centrală de televiziune
Să se implementeze o centrală de televiziune cu ajutorul grafurilor orientate. Să se simuleze căderea unui nod de comunicație. Ce va deveni rețeaua în cazul în care un nod nu este funcțional, eliminarea rețelei de televiziune nefiind o soluție posibilă.
Date de intrare:
Rețeaua de televiziune dintr-un cartier
Graful orientat care mapează această rețea
Nodurile care vor fi eliminate, în cazul defecțiunii acestora
Cerințe:
Să se citească graful
Să se elimine un nod din rețea
Să se afișeze care este cel mai apropiat nod care poate relua transmisia semnalului în cazul defecțiunii unui dintre nodurile de transmisie
Să se afișeze un mesaj în cazul în care nu se poate transmite la un nod din rețea
Codul sursă:
using namespace std;
#include<iostream>
#include<fstream>
const float Infinit=1.e20;
void Citire_const(char Nume_fis[20],float A[50][50],int& n)
{
int i,j;
float c;
ifstream f(Nume_fis);
f>>n;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(i==j)
A[i][j]=Infinit;
while(f>>i>>j>>c)
A[i][j]=A[j][i]=c;
f.close();}
int main()
{
int c,n,x,y,i,j,min;
float A[50][50];
Citire_const("Graf.txt",A,n);
cout<<"Alege nodul ce trebuie eliminat: ";cin>>y;
min=10;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(i==y)
if(min>A[i][j] && A[i][j]!=0)
{min=A[i][j];
x=j;}
cout<<"Nodul cel mai apropiat ce poate transmite semnal nodului eliminat este "<<x<<".";
return 0;}
Exemplu 5: Rețele de calculatoare
Rețeaua Internet este o structură configurată la nivel hardware și software. Configurarea hardware este dată de modul în care sunt legate fizic calculatoarele între ele. Aceste legături poartă denumirea de topologie fizică.
Date de intrare:
Fișierul text care memorează un graf
Numărul de noduri din graf
Graful este neorientat
Cerințe:
Clasificarea topologiilor de rețea
Descrierea tipurilor de topologii pentru rețelele de calculatoare
Să se stabilească dacă graful citit din fișier poate mapa o topologie fizică de rețea
În caz afirmativ, să se specifice ce tip de topologie este
Codul sursă:
#include <iostream>
#include "graf.h"
using namespace std;
int A[50][50],V[50],s,i,j,n;
int main()
{
citireN("graf.txt",A,n);
int k=0,l=0,o=0,p=0,m=0,q=0,r=0;
for(i=1;i<=n;i++)
{ s=0;
for(j=1;j<=n;j++)
{
s+=A[i][j];
V[i]=s;
}
}
cout<<"Gradele Nodurilor"<<endl;
for(i=1;i<=n;i++)
cout<<"Gradul nodului "<<i<<" este "<<V[i]<<endl;
for(i=1;i<=n;i++)
{
if(V[i]==n-1)
m++;
}
if(m==n)
cout<<"Graful reprezinta o retea de tip Plasa"<<endl;
for(i=1;i<=n;i++)
{if(V[i]==n-1)
k++;
else
if(V[i]==1)
l++;}
if(k==1 && l==n-1)
cout<<"Graful reprezinta o retea de tip Stea(Star)"<<endl;
for(i=1;i<=n;i++)
{
if(V[i]==n-1)
q++;
else
if(V[i]==2)
r++;
}
if(q==2&&r==n-2)
cout<<"Graful reprezinta o retea de tip Magistrala(BUS)";
for(i=1;i<=n;i++)
{if(V[i]==1)
o++;
else
if(V[i]==2)
p++;
}
if(o==2 && p==n-2)
cout<<"Graful reprezinta o retea de tip Linie"<<endl;
return 0;
}
graf.h
#include <iostream>
#include<fstream>
using namespace std;
void citireN(char nume_fis[20],int A[50] [50],int&n)
{
int i,j;
fstream f(nume_fis,ios::in);
f>>n;
while(f>>i>>j)
A[i] [j]=A[j] [i]=1;
f.close();
}
Exemplu 6: Traseul unui robot printr-o cameră
Un robot R de formă circulară trebuie să se deplaseze într-un mediu cu obstacole de formă poligonală. Zona în care se poate deplasa robotul poate fi determinată relativ simplu astfel. Mai întâi se setează fiecare obstacol cu o bordură descrisă de urma pe care ar lăsa-o robotul dacă acesta s-ar deplasa. Programul va calcula timpul în care robotul parcurge camera de la un punct inițial până la un punct final precum și traseul pe care îl va efectua, ocolind obstacolele.
Date de intrare:
Dimensiunea camerei în care se poate deplasa robotul
Timpul în care robotul se deplasează de la un nod la altul
Coordonatele obstacolelor, coordonatele de început și de sfârșit a robotului
Cerințe:
Să se afișeze harta de început a camerei și harta după trasarea obstacolelor
Să se calculeze timpul în care robotul poate traversa camera
Să se traseze drumul în interiorul camerei
Să se seteze obstacolele în matricea grafului
Codul sursă:
#include <iostream>
#include <fstream>
#include <math.h>
#include <string.h>
#include <stdlib.h>
using namespace std;
const float pinfinit = 1.e20;
float b[100][100];
int n,a[100][100];
int traseu[100],it=1;
int obstacole[100],ot=1;
void animatie(char mesaj[100])
{
cout<<endl;
cout<<" _______ "<<endl;
cout<<" _/ \\_ "<<endl;
cout<<" / | MOBOT | \\ "<<endl;
cout<<" / |__ __| \\ "<<endl;
cout<<" |__/(_)| |(_)\\__| "<<endl;
cout<<" | | | | "<<endl;
cout<<" |\\ |_| /| "<<endl;
cout<<" | \\ / | <- "<<mesaj<<endl;
cout<<" \\| / ___ \\ |/ "<<endl;
cout<<" \\ | / _ \\ | / "<<endl;
cout<<" \\_________/ "<<endl;
cout<<" _|_____|_ "<<endl;
cout<<" ____|_________|____ "<<endl;
cout<<" / \\ "<<endl;
cout<<endl;
cout<<"Raspuns: ";
}
void afisare_aranjat(int v)
{
int nr=0,aux=v;
while(aux!=0)
{
nr++;
aux/=10;
}
if(nr<=1)
{
cout<<" "<<v;
}
else
{
cout<<" "<<v;
}
}
void afisare_harta(int a[100][100],int n)
{
cout<<endl;
for(int i=1;i<=n*2-1;i++)
{
for(int j=1;j<=n*2-1;j++)
switch(a[i][j])
{
case 0:cout<<" ";break;
case -1:cout<<" -";break;
case -2:cout<<" |";break;
case -3:cout<<" \\";break;
case -4:cout<<" /";break;
case -5:cout<<" M";break;
default:
afisare_aranjat(a[i][j]);break;
}
cout<<endl;
}
}
void generare_harta(int a[100][100],int v[100],int c,int n,int o)
{
int el=1,coordonate[200];
el=1;
for(int i=1;i<=2*(c-1);i+=2)
{
int j=v[el]/n+1;
if(v[el]%n==0)
j–;
coordonate[i]=j;
j=v[el]%n;
if(j==0)
coordonate[i+1]=n;
else
if(j!=0)
coordonate[i+1]=j;
el++;
}
if(o==1)
{
for(int i=1;i<=2*(c-1)-3;i+=2)
if(coordonate[i]==coordonate[i+2])
a[((coordonate[i]*2-1)+(coordonate[i+2]*2-1))/2][((coordonate[i+1]*2-1)+(coordonate[i+3])*2-1)/2]=-1;
else
if(coordonate[i+1]==coordonate[i+3])
a[((coordonate[i]*2-1)+(coordonate[i+2]*2-1))/2][((coordonate[i+1]*2-1)+(coordonate[i+3])*2-1)/2]=-2;
else
if((coordonate[i]<coordonate[i+2] && coordonate[i+1]<coordonate[i+3]) || (coordonate[i]>coordonate[i+2] && coordonate[i+1]>coordonate[i+3]))
a[((coordonate[i]*2-1)+(coordonate[i+2]*2-1))/2][((coordonate[i+1]*2-1)+(coordonate[i+3])*2-1)/2]=-3;
else
a[((coordonate[i]*2-1)+(coordonate[i+2]*2-1))/2][((coordonate[i+1]*2-1)+(coordonate[i+3])*2-1)/2]=-4;
}
else
{
el=1;
for(int i=1;i<=n*2-1;i++)
for(int j=1;j<=n*2-1;j++)
if(i%2!=0 && j%2!=0)
{
a[i][j]=el;
el++;
}
else
a[i][j]=0;
for(int i=1;i<=2*(c-1)-3;i+=4)
a[((coordonate[i]*2-1)+(coordonate[i+2]*2-1))/2][((coordonate[i+1]*2-1)+(coordonate[i+3])*2-1)/2]=-5;
}
}
void construire_graf(char nume_fis[20], int a[100][100],float b[100][100], int &n)
{
int i,j,k,l,el;
//animatie("Salut, eu sunt Mobot! Setati perimetrul camerei.");
animatie("Salut, eu sunt Mobot! Setati perimetrul camerei.");
cin>>n;
system("cls");
generare_harta(a,obstacole,ot,n,0);
afisare_harta(a,n);
animatie("Setati timpul in care este parcurs un metru.");
cin>>k;
system("cls");
afisare_harta(a,n);
//MATRICEA DE NODURI
el=1;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
a[i][j]=el;
el++;
//afisare_aranjat(a[i][j]);
}
}
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
for(k=1;k<=n;k++)
for(l=1;l<=n;l++)
if(sqrt((k-i)*(k-i)+(l-j)*(l-j))<=sqrt(2))
{
b[a[i][j]][a[k][l]]=k;
}
else
{
b[a[i][j]][a[k][l]]=pinfinit;
}
//DIAGONALA PRINCIPALA = 0
for(i=1;i<=n*n;i++)
b[i][i]=0;
//OBSTACOLE
do
{
animatie("Setati obstacolele.");
cin>>i>>j;
system("cls");
b[i][j]=b[j][i]=pinfinit;
obstacole[ot]=i;
ot++;
obstacole[ot]=j;
ot++;
generare_harta(a,obstacole,ot,n,0);
afisare_harta(a,n);
}
while(i||j);
}
void drum(int i,int j)
{
int k=1,gasit=0;
while((k<=n*n) && !gasit)
{
if(i!=k && j!=k && b[i][j]==b[i][k]+b[k][j])
{
drum(i,k);
drum(k,j);
gasit=1;
}
k++;
}
if(!gasit)
{
traseu[it]=j;
it++;
}
}
void scriu_drum(int nod_initial, int nod_final)
{
if(b[nod_initial][nod_final]<pinfinit)
{
traseu[it]=nod_initial;
it++;
drum(nod_initial,nod_final);
}
else
{
cout<<"Nu exista drum de la "<<nod_initial<<" la "<<nod_final;
}
}
void lungime_drumuri()
{
int i,j,k;
for(k=1;k<=n*n;k++)
for(i=1;i<=n*n;i++)
for(j=1;j<=n*n;j++)
if(b[i][j]>b[i][k]+b[k][j])
b[i][j]=b[i][k]+b[k][j];
}
int main()
{
int i,j;
construire_graf("harta.txt",a,b,n);
lungime_drumuri();
animatie("Setati pozitia initiala si destinatia.");
cin>>i>>j;
system("cls");
scriu_drum(i,j);
generare_harta(a,obstacole,ot,n,0);
generare_harta(a,traseu,it,n,1);
afisare_harta(a,n);
char mesaj[100]="Am ajuns la destinatie in ";
char x[20];
char mesaj2[50]=" secunde.";
itoa(b[i][j],x,10);
strcat(mesaj,x);
strcat(mesaj,mesaj2);
animatie(mesaj);
cout<<endl;
return 0;
}
Exemplu 7: Implementarea prin grafuri a reacțiilor chimice
Să se realizeze reprezentarea ca grafuri neorientate a structurii și a secvențelor de reacții chimice. Se pornește de la un graf orientat și se dorește expandarea acestuia cu un număr specific de noduri, precum și transformarea în graf neorientat.
Date de intrare:
Reacția chimică a carbonului cu clorul și cu bromul
Graful orientat care mapează gaful chimic inițial
Costurile pentru fiecare legătură
Cerințe:
Maparea reacțiilor chimice cu ajutorul grafurilor
Adăugarea de noduri la graful inițial
Transformarea matricei costurilor în matrice de adiacență
Codul sursă:
#include<iostream>
#include <fstream>
using namespace std;
const float pinfinit =1.e20;
int n,i,j; float A[50][50];
void citire_cost(char nume_fis[20],float A[50][50],int &n)
{
int i,j;
float c;
fstream f(nume_fis,ios::in);
f>>n;
for( i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(i==j)
A[i][j]=0;
else
A[i][j]=pinfinit;
while(f>>i>>j>>c)
A[i][j]=c;
f.close();
}
void construire1(float A[50][50],int &n)
{
cout<<"Numarul de noduri introduse in cazul in care ati selectat cazul 1 este 2 "<<endl;
n=n+2;
for(i=1;i<=n;i++)
{for(j=1;j<=n;j++)
if(A[i][j]!=0 && A[i][j]!=1)
{A[i][j]=1;
A[i][j+1]=1;
A[i+1][n]=1;
}
}
for(i=1;i<=n;i++)
{for(j=1;j<=n;j++)
if(i==j)
A[i][j]=0;
}
}
void construire2(float A[50][50],int & n)
{
cout<<"Numarul de noduri introduse in cazul in care ati selectat cazul 2 este 4 "<<endl;
n=n+4;
for(i=1;i<=n;i++)
{for(j=1;j<=n;j++)
if(A[i][j]!=0 && A[i][j]!=1)
{A[i][j]=1;
A[i][j+1]=1;
A[i+1][n]=1;
}
}
for(i=1;i<=n;i++)
{for(j=1;j<=n;j++)
if(i==j)
A[i][j]=0;
}
}
main()
{
int x;
cout<<"Introduceti tasta 1 pentru a afisa legatura Carbonului cu Clorul"<<endl;
cout<<"Introduceti tasta 2 pentru a afisa legatura Carbonului cu Bromul"<<endl;
cout<<"Tasta = ";cin>>x;
citire_cost("graf2.txt",A,n);
switch(x)
{
case 1:{ cout<<"In urmatoarea secventa putem observa transformarea suferita de matricea costurilor a Carbonului cu Clorul"<<endl;
construire1(A,n);
break;
}
case 2: { cout<<"In urmatoarea secventa putem observa transformarea suferita de matricea costurilor a Carbonului cu Bromul"<<endl;
construire2(A,n);
break;}
}
for(int i=1;i<=n;i++)
{for(int j=1;j<=n;j++)
cout<<A[i][j]<<" ";
cout<<endl;
}
return 0;
}
Exemplu 8: Genetica populațiilor
Grafurile mai pot arăta legăturile dintre anuminte grupuri sau oameni. Un arbore genealogic este de asemena un graf. Fiind dat un număr de noduri, să se construiască un arbore genealogic.
Date de intrare:
Numărul de noduri din graf
Structura unui graf pentru arborele genealogic
Cerințe:
Să se afișeze arborele genealogic
Să se calculeze nivelul in graf pentru fiecare nod, precum și vectorul de tați
Să se afișeze referințele ascendente și descendente ale nodurilor
Codul sursă:
#include <iostream>
#include <fstream>
using namespace std;
int n,r, T[100], D[100],i,p[100] , niv[100];
int afis()
{ cout<<"gradele sunt>>"<<endl;
for(int i=1;i<=n;i++)
cout<<D[i];
cout<<endl;
cout<<"nivelele sunt>>"<<endl;
for(i=1;i<=n;i++)
cout<<niv[i];
cout<<endl;
}
int df(int r)
{
for(int i=1;i<=n;i++)
if(T[i]==r && !p[i])
{ p[i]=1;
niv[i]=niv[r]+1;
df(i);
}}
int main()
{
int N[100],i,x=1,y=1;
cout<<"numarul de noduri >>"<<endl;
cout<<"n=";cin>>n;
cout<<"––––––––––––"<<endl;
for(i=1;i<=n;i++)
N[i]=i;
cout<<"nodurile sunt>>"<<endl;
for(i=1;i<=n;i++)
cout<<N[i]<<" ";
cout<<endl;
cout<<"––––––––––––"<<endl;
cout<<"vectorul de tati pentru arborele ce "<<endl;
cout<<"reprezinta genetica populatiilor este >>"<<endl;
cout<<endl;
for(i=1;i<=n;i++)
{if(N[i]==1)
T[i]=0;
else
if(N[i]%2==0)
{T[i]=x;
x++;}
else
if(N[i]%2!=0)
{
T[i]=y;
y++;
} }
for(i=1;i<=n;i++)
cout<<T[i];
cout<<endl;
cout<<"––––––––––––"<<endl;
for(i=1;i<=n;i++)
{
if(T[i]!=0) { D[i]++;
D[T[i]]++;
} }
for(i=1;i<=n;i++)
if(T[i]==0) r=i;
niv[r]=0;
df(r);
afis();
cout<<"––––––––––––"<<endl;
cout<<" arborele ce reprezinta "<<endl;
cout<<"genetica populatiilor este >>"<<endl;
cout<<endl;
i=0;
while(n!=0)
{
i++;
if(i==1)
{cout<<" "<<i<<endl;
cout<<" / \\";cout<<endl;
cout<<" / \\";cout<<endl;
cout<<" / \\";cout<<endl;
}
else
if(i==2)
cout<<" "<<i;
else
if(i==3)
{cout<<" "<<i<<endl;
cout<<" / \\ / \\";cout<<endl;
cout<<" / \\ / \\ ";cout<<endl;
}
else
if(i==4)
cout<<" "<<i;
else
if(i==5)
cout<<" "<<i;
else
if(i==6)
cout<<" "<<i;
else
if(i==7)
{cout<<" "<<i<<endl;
cout<<" / \\ / \\ / \\ / \\";cout<<endl;
}
else
if(i==8)
cout<<" "<<i;
else
if(i==9)
cout<<" "<<i;
else
if(i==10)
cout<<" "<<i;
else
if(i==11)
cout<<" "<<i;
else
if(i==12)
cout<<" "<<i;
else
if(i==13)
cout<<" "<<i;
else
if(i==14)
cout<<" "<<i;
else
if(i==15)
cout<<" "<<i<<endl;
else
if(i==16)
{cout<<" / \\ / \\";cout<<endl;
cout<<" "<<i; }
else
if(i==17)
cout<<" "<<i;
else
if(i==18)
cout<<" "<<i;
else
if(i==19)
cout<<" "<<i;
n–; }
return 0;}
III.1.6. Monitorizarea activității proiectului
Pe lângă realizarea unui produs final, elevii au fost evaluați și afectiv, un scop important fiind determinarea unei mai eficiente colaborării și implicări în procesul de învățare. Din această cauză, monitorizarea proiectului a implicat și monitorizarea grupurilor de lucru. Unele discuții referitoare la proiectele implementate s-au derulat în afara orelor de curs, pe site-uri de socializarea și nu numai, acestea nefiind monitorizate și au creat unele disensiuni în interiorul grupelor de lucru. Ca o încercare de rezolvare, am propus ca la finalul proiectului să fie aleasă o echipă de lucru care a fost cea mai eficientă. Aceasta fiind recompensată în afara orelor. Această propunere, deși a fost inițiată în mijlocul derulării proiectului a fost primită cu interes de elevi, determinând o mai bună colaborare în interiorul echipelor de lucru.
III.1.6.1. Autoevaluarea elevilor
O parte extrem de importantă în procesul de evaluare o reprezintă autoevaluarea. Importanța autoevaluării este subliniată prin înțelegerea de către elevi a noțiunilor ce necesită aprofundare. Acest proces nu este important prin note ci prin aprecieri care să determine punctele slabe din procesul de învățare. Prin corectarea acestor puncte slabe, elevii vor obține rezultate care să îî ajute în realizarea optimă a produsului final din proiect. Din această cauză am realizat următoarea fișă de autoevaluare pentru elevi:
Cum am făcut ca participarea mea să fie eficientă?
Am ajutat la formularea întrebărilor esențiale proiectului?
Am învățat mai ușor prin realizarea unui proiect?
Am ajutat la găsirea răspunsurilor la întrebări?
Am descoperit un nou mod de învățare?
Ce dificultăți am întâmpinat în derularea proiectului?
Am acordat un real sprijin colegilor aflați într-un punct critic?
Cum știu că participarea mea a fost eficientă?
Colegii s-au putut baza pe ajutorul meu?
Ce am descoperit lucrând la acest proiect?
III.1.6.2. Interevaluarea elevilor
Am împărțit evaluarea produsului final în două părți, prima parte conținând criterii pentru proiectul în sine în timp ce partea a doua a fost axată pe prezentarea produsului final. În acest fel, am încercat să dezvolt elevilor și abilități de comunicare a informațiilor deținute. Am pus accentul și pe explicarea produsului final, dezvoltând în acest fel limbajul necesar elevilor la disciplina informatică. Produsul final a fost evaluat cu ajutorul unei fișe utilizând criteriile de mai jos:
Proiectul a cuprins toate etapele de realizare?
Proiectul a atins toate cerințele?
Proiectul a avut toate explicațiile cerute?
Prezentarea a fost realizată cu toate echipamentele necesare?
Proiectul a cuprins noțiuni teoretice?
Proiectul a conținut implementarea rezolvării?
Au fost realizate explicații cu privire la metoda de rezolvare?
Programul a rulat cu date diverse?
Elevii au explicat în detaliu rezolvarea abordată?
Elevii au lucrat în cadrul orelor de laborator?
III.1.6.3. Evaluarea prezentărilor proiectelor
La prezentarea finală, accentul a fost pus pe abilitățile de comunicare în limbaj adecvat disciplinei informatică și pe abilitățile de comunicare în limba română. Comunicarea nu s-a axat numai pe produsul final ci și pe formularea de întrebări și formularea de răspunsuri corecte. Grupele de lucru au fost încurajate să colaboreze în găsirea răspunsurilor corecte a explicațiilor complete. Astfel, am utilizat o fișă de evaluarea cuprinzând criteriile următoare:
Prezentarea a fost cursivă? DA NU 50%
Prezentarea a cuprins toate aspectele proiectului? DA NU 50%
Toți membrii grupului au participat la prezentare? 100% 50% 25%
Au utilizat metode inovative în prezentare? DA NU 50%
5. Au fost prezentate dificultățile întâmpinate în realizarea proiectului? 100% 50% NU
6. Elevii au înțeles întrebările adresate? DA NU 50%
7. Fiecare întrebare a avut un răspuns? DA NU 50%
8. Toți membrii au formulat un răspuns? DA NU 50%
9. Răspunsurile au fost obiective? 100% 50% NU
10. Au avut nevoie de materiale ajutătoare în formularea răspunsurilor? DA NU 50%
11. Întrebările au fost legate de tema proiectului? DA NU 50%
12. Întrebările au fost obiective? DA NU 50%
13. Gradul de dificultate a întrebărilor? DIFICIL MEDIU MIC
14. Toți membrii grupului au participat la formularea întrebărilor? DA NU 50%
15. Au avut nevoie de materiale ajutătoare în formularea întrebărilor? DA NU 50%
III.2. Impactul implementării metodei proiectului
III.2.1. Rezultatele evaluării
Am realizat o comparație între notele obținute de elevi la un test clasic și la proiecte. Am aplicat în cadrul parcurgerii materiei din unitatea de învățare un test care cuprindea itemi obiectivi (Nicu, 15) (cu alegere multiplă), semiobiectivi (cu răspuns de completare) și subiectivi (de tip rezolvare de probleme). Datorită faptului că acest capitol pune accentul pe reproducerea teoriei, aplicarea acesteia în itemi cu alegere multiplă, 37% din totalul elevilor au obținut note sub 5. Se poate observa că nota maximă a clasei a fost 8, obținută de un singur elev. Restul notelor s-au situat între 5 și 7. Deși, 63% din elevi au obținut note de trecere, media clasei a fost 5,12. Ceea ce a situat clasa foarte puțin peste valoarea 5.
După aplicarea metodei proiectului, se observă o creștere substanțială a valorilor notelor obținute. Astfel, datorită implicării active a elevilor, nu au existat note mai mici de 7, iar media clasei a fost 8,43. În cadrul proiectelor, la evaluare am pus accentul pe creativitatea elevilor în crearea produselor finale, în abordarea corectă a problemelor, alegerea algoritmilor corespunzători problemelor propuse precum și pe implicarea în realizarea produselor finale. Notele de la proiecte au fost stabilite prin diseminarea produselor finale de întreaga clasă. Notele au fost calculate ca fiind media notelor de la autoevaluare și notele de la interevaluare.
Majoritatea notelor au fost de 8, ceea ce reprezintă 50%, restul fiind de 9 și 10.
După susținerea proiectelor și diseminarea acestora, clasa a mai susținut o lucrarea scrisă care cuprindea toate tipurile de itemi. Cum se poate observa și din tabelul de mai jos, notele au fost cu mult mai bune decât la prima lucrare. Deși media clasei (7,18) nu a fost la fel de mare ca în cazul proiectelor (8,43), totuși a fost mult mai bună decât în primul caz. De asemenea, nu au existat note sub 5.
Elevii au reușit utilizând metoda proiectului să își consolideze cunoștințele, au reținut cu mai multă ușurință noțiunile teoretice și au aplicat aceste noțiuni în problemele practice și teoretice.
În anul școlar următor, am utilizat aceeași abordarea unității de învățare grafuri neorientate și orientate. La prima lucrare scrisă, cu toate tipurile de itemi, media clasei a fost 4,7 iar 45% din elevi au obținut note mai mici de 5. Nota maximă a fost 8, iar cea mai des obținută notă a fost 5. După realizarea proiectului și diseminarea acestuia, media clasei a fost 8,55, notele fiind calculate ca medie dintre autoevaluarea fiecărui elev și interevaluarea întregii clase. Cele mai multe note au fost de 8 dar, spre deosebire de anul precedent au fost mai multe de 10.
După diseminarea proiectului, clasa a susținut o lucrare scrisă, cu toate tipurile de itemi. Și în acest caz, media clasei a fost mai bună decât în primul caz (7,40), deși nu la fel de bună ca în cazul proiectelor (8,55). Totuși, numărul notelor de 9 și de 10 a fost mult mai mare, și nu au existat note sub 5, iar cele mai multe note au fost de 8.
Ca și în anul precedent, am observat o implicare activă a elevilor în realizarea produsului final în cadrul proiectului. Elevii au reușit să atingă un nivel de pregătire care să le permită aplicarea cu succes a noțiunilor teoretice în probleme practice și teoretice.
III.2.2. Finalitatea metodei proiectului
Cu privire la impactul utilizării metodei proiectului, am realizat un chestionar pe un eșantion de 53 elevi de clasa a XI-a, profil real, specializarea Matematică – Informatică intensiv informatică și filiera tehnologică, profilul tehnician ecolog și protecția calității mediului. Acest chestionar conține 10 întrebări, majoritatea cu subiectul metoda proiectului, pentru a afla în ce măsură această metodă de predare-învățare răspunde nevoilor elevilor secolului XII. În același timp, am dorit să aflu în ce măsură sunt utilizate instrumentele IT și Internet-ul în afara disciplinelor de profil.
Cu privire la organizarea unității de învățate și la alte discipline la care aplică această metodă, rezultatele au fost:
După cum se poate observa din primul grafic, majoritatea elevilor consideră că au fost implicați în structurarea produsului final, și nu numai. Se constată, un procent destul de ridicat de elevi care nu au mai utilizat această metodă activ-participativă la alte discipline.
Deoarece metoda proiectului pune accentul pe auto-instruire și pe dezvoltarea liberă integrală a individului uman, am inclus în chestionar întrebarea:
Se observă din diagrama de mai sus, că cea mai mare parte a elevilor consideră că școala nu îi formează suficient pentru secolul XXI.
Cei mai mulți elevi nu percep utilitatea evaluărilor și consideră că notele nu reflectă cu adevărat nivelul de înțelegere a materiei. Întrebați de finalitatea proiectului, elevii au răspuns:
Deși au existat elevi care au cerut discutarea notei finale, majoritatea s-au autoevaluat corect, nefiind diferențe foarte mari între notele lor și cele finale.
Cel mai controversat aspect al noilor tehnologii îl reprezintă Internetul care, deși este cea mai mare bibliotecă poate fi utilizat deficitar de către elevi.
Totuși, majoritate a elevilor utilizează ca sursă de documentare Internetul și la alte materii, exceptănd Informatica și TIC, cu toate că cele mai multe discipline nu utilizează frecvent calculatorul ca mijloc de predare/învățare.
Cu privire la organizarea unității de învățare prin această metodă activ-participativă, am întrebat elevii despre numărul de ore și despre eficiența metodei. După cum se observă mai jos, cei mai mulți elevi sunt de părere că această metodă i-a ajutat la o mai bună înțelegere a materiei.
Ca o opinie generală, am întrebat elevii cu privire la motivarea lor pe parcursul derulării proiectului. Deși se observă o mai bună motivare a lor cu această metodă, la întrebarea dacă ar mai trebui utilizată această metodă, mulți au fost de părere că nu este utilă:
Creșterea gradului de integrare a noilor tehnologii informaționale în curriculumul școlar pentru a-i pregăti pe elevi să se adapteze la cerințele unor ocupații ale secolului XXI este unul din factorii motivatori în utilizarea metodei proiectului la clasă. De asemenea, stimularea utilizării Internet-ului ca mijloc de comunicare prin pagini Web interactive (spreadsheet, googledocs, pagini blog, pagini wiki ) – comunicarea dintre elevi și cadrele didactice poate fi mereu îmbunătățită, prin utilizarea noilor tehnologii. Această comunicare poate câștiga prin aducerea în secolul XXI a orelor de curs.
Motivarea elevilor pentru o implicare mai activă în cadrul orelor de curs în vederea dezvoltării abilităților necesare secolului XXI este un punct de răscruce în abordarea materiei la clasa de elevi.
IV. Concluzii
Cu o nouă abordare a educației care să dezvolte elevilor abilitățile necesare unei învățări continue, unei abordări personale a procesului de învățare, am putea să aducem modificari benefice în dinamica orelor de studiu la școală.
Formarea profesorilor pentru integrarea noilor tehnologii este un pas important în alinierea educației cu secolul XXI. Predarea prin proiecte (prezentată cu succes de cursul IntelTeach) a adus o nouă abordare în sistemul educațional. Această abordare a fost implementată cu succes în 70 de țări din întreaga lume, inclusiv România.
Cloud computing, date mobile, securitate, case inteligente și orașe inteligente sunt doar unele dintre avantajele dezvoltării continue a tehnologiilor și a informaticii.
V. Bibliografie
[Anderson et al, 01] Lorin ANDERSON, David KRATHWOHL, Benjamin BLOOM, A taxonomy for learning, teaching, and assessing: a revision of Bloom’s taxonomy of educational objectives, Longman Publisher, 2001
[Bărbăcioru, 12] Iuliana Carmen BĂRBĂCIORU, Cercetari operaționale Curs universitar, Facultatea de Matematică, Universitatea Constantin Brâncuși Târgu-Jiu, an II, curs 2 – Elemente de teoria grafurilor (http://www.utgjiu.ro/math/cbarbacioru/book/co2009/c02.pdf)
[Bercu et al, 10] Nicoleta BERCU, Laura Elena CĂPIȚĂ, Despre a învăța elevul să învețe, Revista de pedagogie, Institutul de Științe ale Educației, nr. 58 (3)/2010
[Bloom et al, 56] Benjamin BLOOM, David KRATHWOHL, Taxonomy of Educational Objectives: The Classification of Educational Goals, D. McKay Publisher, 1956
[Captarencu, 14] Oana Otilia CAPTARENCU, Limbaje formale, automate și compilatoare Curs universitar, Facultatea de Informatică, Universitatea Alexandru Ioan Cuza, Iași an II, Curs 7 – Mașini Turing
[Cerchez et al, 06] Emanuela CERCHEZ, Marinel ȘERBAN, Programarea în limbajul C/C++ pentru liceu volumul III, Editura Polirom, Iași, 2006
[Constantinescu, 15a] Oana CONSTANTINESCU, Didactica matematicii Curs universitar, Facultatea de Matematică, Universitatea Alexandru Ioan Cuza Iași, an II, curs 2- Principiile învățării (http://www.math.uaic.ro/~oanacon/depozit/Curs_2_Prin_inv_gen.pdf)
[Constantinescu, 15b] Oana CONSTANTINESCU, Didactica matematicii Curs universitar, Facultatea de Matematică, Universitatea Alexandru Ioan Cuza Iași, an II, curs 2- Principiile MPM (http://www.math.uaic.ro/~oanacon/depozit/Curs_4_Prin_MPM_cont_lyx.pdf)
[Crețu, 15] Vladimir-Ioan CREȚU, Structuri de date și algoritmi Curs universitar, Facultatea de Automatică și Calculatoare, Universitatea Politehnică Timișoara, an II, curs 4 – Algoritmul lui Dijkstra (bigfoot.cs.upt.ro/~calin/resources/sdaa/dijkstra.ppt)
[Gontineac, 08] Mihai GONTINEAC, Limbaje formale și teoria automatelor Curs universitar, Facultatea de Matematică, Universitatea Alexandru Ioan Cuza Iași, an II, curs 12 – Mașini Turing
[Lucanu, 15] Dorel LUCANU, Proiectarea algoritmilor Curs universitar, Facultatea de Informatică, Universitatea Alexandru Ioan Cuza, Iași an II, curs 4 – Grafuri (http://thor.info.uaic.ro/~dlucanu/cursuri/ap/resurse/curs4.pdf)
[Miloșescu, 06] Mariana MILOȘESCU, Informatică: clasa a IX-a, intensiv informatică, Editura Didactică și Pedagogică, București, 2006
[Nicu, 15] Adriana NICU, Introducere în pedagogie. Teoria și metodologia curriculum-ului, DPPD Pedagogic, Universitatea Lucian Blaga Sibiu, curs 8-Testul docimologic (http://dppd.ulbsibiu.ro/ro/cadre_didactice/adriana_nicu/cursuri/Pedagogie%202_curs_8_Testul%20docimologic.pdf )
[Rebedea et al, 15a] Traian REBEDEA, Vlad POSEA, Ștefan TRĂUȘAN-MATU, Costin CHIRU, Proiectarea algoritmilor curs universitar, Facultatea de Automatică și Calculatoare, Universitatea Politehnică București, an II, Curs 16 – Algoritmul lui Dijkstra (http://andrei.clubcisco.ro/cursuri/f/f-sym/2pa/cursuri/elearning/PA%20-%2016.pdf)
[Rebedea et al, 15b] Traian REBEDEA, Vlad POSEA, Ștefan TRĂUȘAN-MATU, Costin CHIRU, Proiectarea algoritmilor curs universitar, Facultatea de Automatică și Calculatoare, Universitatea Politehnică București, an II, Curs 17 – Algoritmul Bellman-Ford (http://andrei.clubcisco.ro/cursuri/f/f-sym/2pa/cursuri/elearning/PA%20-%2017.pdf)
[Rebedea et al, 15c] Traian REBEDEA, Vlad POSEA, Ștefan TRĂUȘAN-MATU, Costin CHIRU, Proiectarea algoritmilor curs universitar, Facultatea de Automatică și Calculatoare, Universitatea Politehnică București, an II, Curs 18 – Algorimtul Floyd-Warshall (Roy-Floyd) (http://andrei.clubcisco.ro/cursuri/f/f-sym/2pa/cursuri/elearning/PA%20-%2018.pdf)
[Rychen et al, 03] Dominique Simone RYCHEN, Laura Hersh SALGANIK, Key Competencies for a Successful Life and a Well-Functioning Society, Hogrefe & Huber Publisher, 2003
[Sorin et al, 06] Tudor SORIN, Vlad HUȚANU, Informatică, manual clasa a XI-a, informatică intensiv, Editura L&S Soft, București, 2006
[Sorin, 08] Tudor SORIN, Informatică: curs pentru clasele a IX-a și a X-a, Editura L&S Soft, București, 2008
[Sedgewick et al, 08] Robert SEDGEWICK, Kevin WAYNE, Princeton University, Introduction to Programming in Java: an interdisciplinary approach, Chapters 17 and 18 Section 4.5, Pearson Education, Inc., 2008 (http://algs4.cs.princeton.edu/41undirected/)
[Tomescu, 81] Ioan TOMESCU, Probleme de combinatorică și teoria grafurilor, Editura Didactica și Pedagogică, București, 1981
[Zaharie, 14] Daniela ZAHARIE, Algoritmi Curs universitar, Facultatea de matematică și informatică Universitatea de Vest Timișoara, an I, curs 6 – Analiza algoritmilor de sortare
Algoritmul lui Dijkstra implementare practică: http://campion.edu.ro/arhiva/www/arhiva_2009/seds/7/html/moment_df_3.html
Predarea prin proiecte, structurarea unui proiect pentru o unitate de învățare: http://educate.intel.com/ro/ProjectDesign
Noile tendințe în educație, la nivel internațional, inițiativa Intel, Microsoft și Cisco de sprijinire a reformelor în educație pentru atingerea competențelor secolului XXI http://www.euractiv.ro/uniunea-europeana/articles|displayArticle/articleID_16039/Cisco-Intel-si-Microsoft-colaboreaza-pentru-a-imbunatati-evaluarea-in-educatie.html
Competențele cheie ale secolului XXI în educație http://www.eurotrainer.ro/competente-cheie/competente-cheie.html/lang/ro
Predarea prin proiecte, implementarea la clasă http://iteach.ro/
Dezvoltarea competențelor de învățare pe tot parcursul vieții http://www.ise.ro/a-invata-sa-inveti-in-scoala-dincolo-de-logica-implicita-a-simtului-comun
Competențele cheie ale secolului XXI în educație și implementarea în România https://eduproiect.wordpress.com/2009/08/18/competente-cheie-lisabona-2000/
Avantajele și dezavantajele învățării prin proiecte http://www.gsn.org/web/pbl/pblintro.htm
Dezvoltarea competențelor cheie în școlile din Europa http://eacea.ec.europa.eu/EDUCATION/EURYDICE/documents/thematic_reports/145RO.pdf
Declarație de autenticitate
Subsemnata, Arghire Diana declar pe propria răspundere că lucrarea de față a fost elaborată personal și îmi aparține în întregime.
Declar că lucrarea este rezultatul muncii mele, pe baza cercetărilor proprii și pe baza informațiilor obținute din surse care au fost citate și indicate în text, figuri, tabele și bibliografie conform normelor de citare a surselor și a respectării legislației privind drepturile de autor.
Declar că lucrarea nu a mai fost prezentată sub această formă vreunei instituții de învățământ superior în vederea obținerii unui grad sau titlu științific ori didactic.
Data,
…………………
Nume, prenume, semnătură
Arghire Diana……………………
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: Algoritmi Elementari (ID: 158624)
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.