ALGORITMI DE CALCUL SI STRUCTURI DE DATE

UNIVERSITATEA ROMANO-AMERICANA

FACULTATEA DE INFORMATICA MANAGERIALA

ANUL I

DISCIPLINA : ALGORITMI DE CALCUL SI STRUCTURI DE DATE

TEORIE

Programarea este activitatea prin care se concepe un program pentru rezolvarea unei probleme cu ajutorul unui calculator.
Un program este o succesiune de instructiuni si comenzi apartinand unui limbaj de programare care conduce la solutionarea unei probleme formulate. Calculatorul va efectua aceste comenzi in ordinea stabilita de programator pentru a obtine rezultatele dorite.nala.

Prin elaborarea (proiectarea) unui algoritm intelegem intreaga activitate depusa de la enuntarea problemei pana la realizarea algoritmului corespunzator rezolvarii acestei probleme. In elaborarea unui algoritm deosebim urmatoarele activitati importante
- specificarea problemei;
- descrierea metodei alese pentru rezolvarea problemei;
- proiectarea propriu-zisa. Ea consta in descompunerea problemei in subprobleme, obtinerea algoritmului principal si a tuturor subalgoritmilor apelati, conform metodelor prezentate in sectiunile urmatoare. Ea se termina cu descrierea algoritmului principal si a subalgoritmilor mentionati, dar si cu precizarea denumirilor si semnificatiilor variabilelor folosite
- verificarea algoritmului obtinut.

Orice algoritm primeste date de intrare , le prelucreaza si obtine date de iesire. In fiecare caz , datele de intrare , datele intermediare -cele create in timpul prelucrarii - si datele de iesire sunt strucurate intr-un anumit fel care corespunde intrarii , necesitatilor de prelucrare sau a celor de utilizare ulterioara.

In informatica, o structura de date este o metoda de stocare a informatiilor intr-un calculator in asa fel incat sa poata fi folosit in mod eficient. Deseori o alegere bine facuta a structurii de date va permite implementarea celui mai eficient algoritm. Structura de date aleasa este derivata de multe ori dintr-un tip de data abstract. O structura de date bine conceputa permite efectuarea unei varietati de operatii de baza, utilizand pe cat posibil cat mai putine resurse, exprimate atat in timpi de executie cat si ca spatiu de memorie utilizat. Structurile de date sunt implementate utilizand tipuri de date, referinte si operatii asupra acestora facilitate de catre un limbaj de programare.

Diferite tipuri de structuri de date se potrivesc unor tipuri diferite de aplicatii, si unele sunt foarte specializate anumitor sarcini. De exemplu, in mod particular arborii B sunt foarte potriviti pentru implementarea bazelor de date, in timp ce tabelele de rutare depind de retele ce calculatoare pentru a functiona.

In design-ul multor tipuri de programe, alegerea structurii de date este principalul obiectiv luat in considerare la redactarea specificatiilor de implementare, dupa cum experienta in construirea unor mari sisteme informatice a aratat ca dificultatea de implementare si calitatea si performantele produsului final rezultat depind in mare masura de alegerea celei mai bune structuri de date. Dupa ce au fost alese tipurile de structui de date, algoritmii ce vor trebui utilizati devin de cele mai multe ori aproape evidenti. Cateodata lucrurile se complica - structurile de date sunt alese pentru ca anumite sarcini cheie au algoritmi care functioneaza cel mai bine numai cu structuri de date particulare. In orice caz, alegerea unei structuri de date adecvate este de o importanta cruciala.

Aceasta introspectie a dus la specificarea multor metode formale de design si limbaje de programare in care mai degraba structurile de date, decat algoritmii, sunt factorul organizatoric cheie. Majoritatea limbajelor expun un fel de modul sistem, permitand reutilizarea structurilor de date intr-un mod sigur si aproape transparent, in aplicatii diferite, prin ascunderea detaliilor de implementare, care au fost deja testate si verificate, in spatele unor interfete controlate. Limbajele de programare orientate pe obiecte cum ar fi C++ si Java, de exemplu, utilizeaza in acest scop clase.

Pentru ca structurile de date au o importanta atat de mare, multe dintre ele sunt incluse in librariile standard a multor limbaje de programare si medii de dezvoltare, cum ar fi Standard Template Library pentru C++, si Java Collections Framework.

Structurile de date fundamentale, care sunt elementele de baza in construirea majoritatii celorlalte structuri de date, sunt vectorii, inregistrarile, structurile de tip union, si referintele. De exemplu, referinta invalidabila, o referinta ce poate contine valoarea null (zero), este o combinatie de referinte si structuri de tip union, iar cel mai simplu model de structura de date inlantuita, lista simplu inlantuita, este construita din inregistrari si referinte invalidablie.

Structurile de date reprezinta implementari ale unor interfete: O structura de date poate fi vazuta ca o interfata intre doua functii sau ca o implementare a metodelor de accesare a depozitului care este organizat in concordanta cu tipul de data asociat.

Pentru a veni in sprijinul programatorilor , limbajele de programare evaluate pun la dispozitia acestora posibilitatea organizarii datelor in anumite 'sabloane' numite tipuri de date. Mai precis , prin tip de date se intelege :

o multime de valori;

o regula de codificare a acestora;

o multime de operatii definite pe multimea datelor.

Principalele tipuri de structuri de date
- liniara
- arborescenta
- retea
- relatio

Organizarea datelor este un process care cuprinde mai multe activitati
- identificarea datelor
- clasificare asi descrierea proprietatilor, a caracteristicilor datelor
- gruparea datelor in colectii de date destinate prelucrarii automate
- reprezentarea externa pe suporturi tehnice

O structura de date poate fi
- Secventiala - daca localizarea unui concept se face prin citirea tuturor componentelor care se afla inaintea sa, in ordinea exixtenta.
- Cu acces direct - daca o componenta poate fi selectata in mod direct fara a le parcurge pe celelalte.

PROBLEME

1.Se citeste un cuvant de la tastatura. Sa se stearga o litera la intamplare,

citita de la tastatura din cuvantul dat si sa se afiseze cuvantul final.

#include<iostream.h>

#include<conio.h>

#include<string.h>

int sterge(char v[201], char c)

k++;

}

return k;

}

void main()

2. Se citeste un nr intreg de la tastatura. Sa se verifice daca acesta este prim sau nu, si sa se afiseze da sau nu.

#include<iostream.h>

#include<math.h>

#include<conio.h>

int prim(int n,int d)

void main()

3. Se citeste un nr intreg de la tastatura. Sa se verifice daca acesta este superprim sau nu, si sa se afiseze da sau nu Nr superprim= un nr care este prim, si toate prefixele numarului respectiv sunt prime)

#include<iostream.h>

#include<math.h>

#include<conio.h>

int prim(int n,int d)

void main()

if(sem==1)

cout<<'da';

else cout<<'nu';

getch();}

4. Se citesc x numere reale cu zecimale dintrun fisier'nr.in'. Sa se afiseze intr-un alt fisier 'nr.out' numerele respective cu 2 zecimale.

#include<fstream.h>

void main()

f.close();

g.close();

}

5. Se citeste un sir de numere intregi date de la tastatura. Sa se afiseze secventa maxima de numere prime din sir.

#include<iostream.h>

#include<math.h>

#include<conio.h>

int prim(int n,int d)

main()

if (k>max)

}

for(int j=sf-max+1;j<=sf;j++)

cout<<v[j]<<' ';

getch();

}