IngineriaProgramarii_2014
27
INGINERIA PROGRAMĂRII Conf. Dr. Daniela Alexandra Crişan Colecţii de date Tehnici de programare
description
Ingineria programarii
Transcript of IngineriaProgramarii_2014
INGINERIA PROGRAMĂRII
Conf. Dr. Daniela Alexandra Crişan
Colecţii de date
Tehnici de programare
ATENTIE
Scopul acestui document este de structura materia
predata in cadrul orelor de curs si seminar. Invatarea
materiei, exclusiv pe baza acestui document, reprezinta o
abordare superficiala!
Bibliografie obligatorie:
1. Crisan D.A., Stanica L.J., „Ingineria programarii”, Bucuresti, Ed.
Universitara, 2010
2. Knuth D. E., „Arta programarii calculatoarelor”, Vol. I-III, Ed. Teora,
2002
3. Odagescu I., Copos C., Luca D. Furtuna F. Smeureanu I., „Metode si
tehnici de programare”, Ed. Intact, Bucuresti, 1994;
4. Odagescu I., Luca D., Furtuna F., „Concursurile nationale si
internationale de informatica”, Ed. L&S Informat, Bucuresti, 1996;
5. Livovski L. Georgescu H., „ Sinteza si analiza algoritmilor” Ed.
Stiintifica, Bucuresti,1997;
Bibliografie optionala:
Knuth D. E., Art of Computer Programming, Volume 1: Fundamental
Algorithms (3rd Edition);
Cuprins (manualul „Ingineria programarii”)
PARTEA I. COLECȚII DE DATE ..................................................................... 5
Capitolul I: Reprezentarea colecțiilor de date ............................................. 5
I.1 Masive de date ......................................................................................... 5
I.2 Structuri dinamice de date ....................................................................... 5
Capitolul II: Operații pe colecţii de date ........................................................ 6
II.1 Căutări ..................................................................................................... 6
II.2 Interclasarea ............................................................................................ 9
II.3 Strategii generale de sortare (ordonare totală)..................................... 10
II.4 Sortare prin distribuire (chei multiple)......................................................
II.5 Sortare topologică (ordonare parţială) ................................................. 11
II.6 Selecţia ................................................................................................... 14
PARTEA a II-a. TEHNICI DE PROGRAMARE ........................................... 14
Capitolul III: Metode clasice de programare ....................................................
III.1 Metoda Divide et Impera ....................................................................... 16
III.2 Metoda Backtracking ............................................................................. 18
III.3 Metoda Greedy....................................................................................... 19
III.4 Metode euristice ..................................................................................... 22
III.5 Metoda programării dinamice ............................................................... 23
III.6 Metoda Branch and Bound .................................................................... 25
III.7 Aplicaţii ale metodei Backtracking în combinatorică ...............................
Anexă. Complexitatea algoritmilor .................................................................... 27
Analiza algoritmilor ...............................................................................................
Ordinul timpului de execuţie .............................................................................. 27
Bibliografie
PARTEA I. COLECȚII DE DATE
Reprezentarea colecțiilor de date
I.1 Masive de date
O colecţie de date de acelaşi tip poate fi stocată sub forma unui masiv
de date, fiind necesară o zonă continuă de memorie de volum suficient
pentru a stoca întreaga colecţie. Masivele pot fi alocate static (la compilare)
sau dinamic (la execuţie). În primul caz, dimensiunea alocată este
independentă de numărul efectiv de date ale colecţiei (cu observaţia că
dimensiunea alocată trebuie să o depăşească pe cea necesară, efectivă). În
cazul alocării dinamice, modificarea, în timpul execuţiei, a dimensiunii
masivului comportă eliberarea memoriei utilizate şi realocarea unei noi
zone de memorie, cu dimensiunea cea nouă.
I.2 Structuri dinamice de date
Structurile dinamice de date sunt o alternativă de stocare a unei
colecţii de date de acelaşi tip, nefiind necesară o zonă continuă de memorie
şi nici cunoaşterea apriorică a numărului de elemente ale colecţiei.
Se disting mai multe categorii de structuri dinamice:
- liste înlănțuite (simplu înlănțuite, dublu înlănțuite, circulare);
- arbori;
- grafuri.
Operații pe colecţii de date
I.1 Căutări
Căutarea secvenţială - este utilizată atunci elementele masivului se
află într-o ordine arbitrară;
#include <iostream>
using namespace std;
int LSearch(int A[], int n, int e){
int pozitie=-1;
for(int i=0;i<n&&pozitie==-1;i++)
if(A[i]==e) // operaţie de bază
pozitie=i;
return pozitie;
}
int main()
{
int A[]={2, 9, 5, 4, 1, 7, 10, 8, 3, 6};
int n=sizeof(A)/sizeof(*A);
int e=7;
int poz= LSearch (A, n, e);
if(poz==-1) cout<<e<<" nu se afla in masiv";
else cout<<e<<" se afla pe pozitia "<<poz;
cin.get();
return 0;
}
Complexitate: algoritmul de căutare secvenţială este un algoritm liniar
(polinomial de ordin 1), care nu necesită memorie suplimentară.
Căutarea binară - este o căutare optimizată care se utilizează atunci
când masivul de date este sortat.
#include <iostream>
using namespace std;
int BSearch(int A[], int p, int u, int e){
if(p>u) return -1;
int mijloc=(p+u)/2;
if(A[mijloc]==e)
return mijloc; // elementul a fost gasit
if(A[mijloc]>e) // repetam cautarea pe prima jumatate
return BSearch(A, p, mijloc-1, e);
// repetam cautarea pe cea de-a doua jumatate
return BSearch(A, mijloc+1, u, e);
}
int main()
{
int A[]={1,3,5,7,9,11,13,15,17,19,21};
int n=sizeof(A)/sizeof(*A);
int e=5;
int poz=BSearch(A, 0, n-1, e);
if(poz==-1) cout<<e<<" nu se afla in masiv";
else cout<<e<<" se afla pe pozitia "<<poz;
cin.get();
return 0;
}
Complexitate: algoritmul de căutare binară are timpul de calcul de
ordin O(log2n).
Arbori de căutare – sunt construiţi pentru a atinge performanţe de
căutare comparabile cu cele ale căutării binare, dar care pot fi
utilizaţi pentru colecţii de date nu neapărat sortate.
Complexitate: Timpul de calcul necesar căutării unui element într-un
astfel de arbore este comparabil cu cel necesar căutării binare: O(log2n)
I.2. Interclasarea 9
I.2 Interclasarea
Interclasarea, întâlnită în literatura de specialitate şi sub denumirea de
„fuzionare” sau „colaţionare”, constă în combinarea (concatenarea) a două
masive sortate într-unul singur, sortat la rândul său.
I.3 Strategii generale de sortare (ordonare totală)
Metodele generale de sortare:
1. sortarea prin selecţie
2. sortarea prin inserţie
a. directă
b. binară
3. sortare prin interschimbare
a. metoda bulelor
b. sortare rapidă
4. sortare prin interclasare
5. sortarea prin numărare
Metoda bulelor (Bubble Sort)
#include <iostream>
using namespace std;
void BubbleSort(int A[], int n){
int temp;bool b=true;
for(int i=0;b&&i<n-1;i++) //parcurgeri repetate ale
vectorului
{
b=false;
for(int j=0;j<n-i-1;j++)
if(A[j]>A[j+1]) // operatie de baza
// interschimbam A[j] cu A[j+1]
{temp=A[j]; A[j]=A[j+1];A[j+1]=temp;b=true;}
}
}
int main()
{
int A[]={2, 9, 5, 4, 1, 7, 10, 8, 3, 6};
int n=sizeof(A)/sizeof(*A);
BubbleSort(A,n);
for(int i=0;i<n;i++) cout<<A[i];
cin.get();
return 0;
}
Complexitate: metoda bulelor are timpul maxim polinomial: O(n2).
I.4 Sortare topologică (ordonare parţială)
Sortarea topologică presupune ordonarea elementelor unei mulţimi
pe care este definită o relaţie parţială de ordine. De exemplu, să
presupunem că dorim să construim un mini-dicţionar tehnic în care (unele)
cuvinte să fie definite cu ajutorul altor cuvinte, astfel ca nici un cuvânt să nu
conţină în definiţia sa cuvinte care vor fi definite ulterior. Deci, orice cuvânt
va conţine în definiţia sa cuvinte care au fost deja definite sau care sunt de
la sine înţelese.
De exemplu, fie relaţiile de ordine: 2<1, 4<2, 3<2, 4<3, 5<3. Graful
de precedenţe va fi:
Fig. 0-1. Graf de precedenţe
O ordonare topologică pentru aceste date este: 4, 5, 3, 2, 1.
#include <iostream> #include <stack> #include <fstream> using namespace std; int main () { int N,n; // numarul de elemente, respectiv perechi int p,s;// predecesor/succesor int i; stack<int>* succ; int* pred; ifstream in("dictionary.csv"); in>>N; in>>n; // alocam memorie pentru pred si succ si initializam pred=new int[N]; succ=new stack<int>[N]; for(i=0;i<N;i++){ pred[i]=0;
} for(i=0;i<n;i++){ // se citeste o pereche p<s in>>p>>s; p--;s--;//ajustare // se incrementeaza numarul de predecesori ai lui s pred[s]++; // se adauga s in lista succesorilor lui p succ[p].push(s); } cout<<endl<<"Ordonare topologica: "; int servite=0; bool no_sol; do{ no_sol=true; for(i=0;i<N;i++) if(!pred[i]){ servite++; no_sol=false; cout<<i+1<<" "; //actualizare date dupa extragere element i pred[i]=-1; // element prelucrat stack<int> copy = succ[i];//copie stiva succesori // parcurgem lista succesorilor elementului i while(!copy.empty()){ pred[copy.top()]--; copy.pop(); } } if (no_sol){ cout<<"Problema nu are solutie!"; break; } }while(servite<N); delete[] succ; delete[] pred; cin.get(); return 0; }
I.5 Selecţia
Selecţia constă în determinarea celui al k-lea mai mic element al unui
masiv.
Selecţia directă
#include<iostream>
using namespace std;
int Selectie(int A[], int n, int k){
for(int i=0;i<k;i++){
// se determina pozitia minimului
// din secventa A[i], A[i+1]...A[n]
int min=i;
for(int j=i+1;j<n;j++)
if(A[j]<A[min]) min=j;
// se interschimba A[i] si A[min]
int temp=A[i]; A[i]=A[min];A[min]=temp;
}
return A[k-1];
}
int main()
{
int A[]={2, 9, 5, 4, 7, 1, 10, 8, 3, 6};
int n=sizeof(A)/sizeof(*A);
cout<<"Al 3-lea cel mai mic element este: "<<Selectie(A, n,
3);
cin.get();
return 0;
}
Complexitate: algoritmul este polinomial de ordin O(n2).
PARTEA a II-a. TEHNICI DE PROGRAMARE
Divide et Impera
Backtracking
Greedy
Euristice
Metoda programării dinamice
Branch and Bound
I.1 Metoda Divide et Impera
Metoda Divide et Impera (“Dezbină şi Stăpâneşte”) se aplică în
problemele care pot fi împărţite în mod repetat în două sau mai multe sub-
probleme de acelaşi tip dar de dimensiuni mai mici [Divide], rezolvarea lor
şi combinarea soluţiilor în scopul obţinerii soluţiei problemei iniţiale
[Impera].
Turnurile din Hanoi #include<iostream>
using namespace std;
void Hanoi(int n,char a,char b,char c){
// n=numarul de discuri; a,b,c=tijele
sursa/intermediara/destinatie
if(n){
Hanoi(n-1,a,c,b);
cout<<a<<"->"<<c<<endl;
Hanoi(n-1,b,a,c);
}
}
int main()
{
int n;
cout<<"n=";cin>>n;
Hanoi(n,'a','b','c');
cin.get();
return 0;
}
Complexitate: 2^n
I.2 Metoda Backtracking
- spaţiul soluţiilor posibile.
- condiţii interne.
- soluţii rezultat.
Timpul de calcul - exponential
procedure Backtracking(integer n, integer x[1..n])
k←1
while k>0:
i←0
while [mai există o valoare s din Sk netestată încă]
xk←s
if contk (x1,x2,…,xk-1) then i←1; exit
end if
repeat
if i=0 then k←k-1
else
if k=n then write x1,…,xn
else k←k+1
end if
end if
repeat
end
Exemplu: Generarea permutărilor elementelor unei mulţimi
ex.: pentru n=3 avem 3!=6 permutări:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1 #include <iostream>
using namespace std;
int cont(int *X, int n, int k){
//verifica daca x[k] este bine plasat
// (nu coincide cu nici una dintre valorile x[0], x[1], ...,
x[k-1])
for(int i=0;i<k;i++)
if(X[i]==X[k])
return 0;
return 1;
}
void ret_sol(int *X, int n){
cout<<endl<<"Solutie: ";
for(int i=0;i<n;i++)
cout<<X[i]<<" ";
}
void permR(int *X, int n, int k){
if(k==n) ret_sol(X, n);
else{
// se parcurge multimea Sk={1, 2, ..., n}
for(int i=1;i<=n;i++){
X[k]=i;
// daca X[k] este bine plasat
if(cont(X,n,k))
permR(X,n,k+1);// se continua generarea
}
}
}
void permI(int *X, int n){
int c,i,k=0;
X[k]=0;
while(k>=0){
c=0;
while(X[k]<n){// mai exista elemente in Sk
X[k]++;
if(c=cont(X,n,k)) break;
}
if(!c) k--;
else
if(k==n-1) ret_sol(X,n);
else {k++;X[k]=0;}
}
}
int main()
{
int n;
cout<<"Ordin = ";cin>>n;
int *X=new int[n];
permI(X,n);
delete X;
cin.get();
return 0;
}
I.3 Metoda Greedy
- soluţie posibilă.
-criteriu de optim soluţie optimă.
Timpul de calcul - polinomial O(n2).
Exemplu - Programarea activităţilor
Taxi Incepere Terminare Total întârziere (aşteptare+servire)
1 0 2 0+2=2
2 2 3 2+1=3
3 3 7 3+4=7
4 7 10 7+3=10
Total aşteptare: 22
P1. Se sortează activităţile crescător după duratele lor;
P2. pentru [toate activităţile] i
programează activitatea i
I.4 Metode euristice
- soluţii „suficient” de bune
- uşor de implementat şi obţine rezultate într-un timp rezonabil
Exemplu – Programarea aplicaţiilor pe procesoare
Procesor 1 : | 9 |
Procesor 2 : | 6 | 3 |
Procesor 3 : | 6 | 2 |
Algoritmul este descris astfel:
P1. Se sortează descrescător aplicaţiile după durata
execuţiei;
P2. [pentru fiecare aplicaţie i]
o se caută procesorul cel mai puţin ocupat, fie acesta
p_min
o se programează aplicaţia i pe procesorul p_min
I.5 Metoda programării dinamice
Metoda programării dinamice se aplică în cazul problemelor de
optim în care soluţia poate fi privită ca rezultatul unui şir de decizii d1, d2,
...,dn, unde alegerea fiecărei decizii dk depinde de deciziile luate anterior.
Timpul de calcul - de ordin polinomial.
Exemplu - Înmulţirea optimă a unui şir de matrice
Problema care se pune în scopul înmulţirii optime de matrice este
stabilirea ordinii de înmulţire, fără a încerca toate posibilităţile.
Să considerăm un exemplu extrem de simplu: presupunem că avem 4
matrice de dimensiuni (100,1), (1,100), (100,1), (1,100). Aşadar, n=4 şi
l=(100,1,100,1,100).
Fig. 0-1. Număr de înmulţiri
Tabel 0-1. Matricea de costuri
0 10.000 200 10.200
1 0 100 200
1 2 0 10.000
1 3 3 0
Un algoritm iterativ de populare a matricei cost este:
procedure COST(integer n, integer cost[1..n,1..n])
for i=1 to n
cost[i,i]← 0
next i
for d=1 to n-1 /*d reprezinta diferenta j-i*/
for i=1 to n-d
j←i+d
cost[i,j]
← 11],1[cos],[cosmin jkijki llljktkit
cost[j,i] ←[valoarea k pentru care se obtine
minimul]
next i
next d
end
I.6 Metoda Branch and Bound
- spaţiul soluţiilor posibile are formă arborescentă
- condiţiile de continuare au la bază un criteriu de optimalitate
Exemplu - Jocul Perspico
(a)
(b)
Fig. 0-2. Configuraţie iniţială (a), Configuraţie finală CF (b)
c(nod)=lungimea drumului de la rădăcină la nod + numărul de
căsuţe care nu se află la locul lor.
Un algoritm general de rezolvare este dat de:
procedure BB(arbore rad)
irad; L
do
for [toti j fiii lui i]
if [j este nod rezultat] then
write [drumul de la rad la j]
return
endif
jL
repeat
if L= then
write “Pb nu are sol”
return
else
iL
endif
repeat
end.
Complexitate: timp de calcul exponenţial, ca şi metoda
Backtracking.
Complexitatea algoritmilor
- estimarea volumului suplimentar de memorie utilizată
- estimarea timpului de calcul necesar execuţiei. Timpul maxim,
minim, mediu
Dimensiunea problemei - mărimea datelor ce trebuie prelucrate
Ordinul timpului de execuţie:
polinomial de ordin k . O(nk).
exponenţiali de ordin k . O(kn).
