De ce SDA?
Structuri de date : metode de organizare a unei mari cantitati de informatie
Analiza algoritmilor : estimarea timpului de executie si a resurselor necesare
Dezvoltarea tehnologiei=> calculatoare din ce in ce mai rapide
- nevoia de programe care sa poata procesa in timp util o mare catitate
de intrare
- eficienta programelor, obiectiv stringent in special la cantitati mari de
date de intrare
- analiza algoritmului permite o apreciere , o estimare a soluitie daca este
eficienta, inca inainte de a scrie codul
Ex. 1 Problema de selectie. Se da un grup de N numere. Sa se determine
elementul de pe pozitia k in ordinea descrescatoare a marimii.
SDA curs 1 I IS 2009/2010 3
Variante de solutii Ex.1
a) a citi cele N elemente intr-un tablou, sortarea lor in ordine
descrescatoare si returnarea elenetului de pe pozitia k
b) a citi primele k elemente intr-un tablou si sortarea lor in ordine
descrescatoare. Fiecare element este citit apoi unul cate unul. Daca
este mai mic dacat al k –lea element este ignorat, altfel este pus in
pozitia corecta, cel in plus fiind eliminat
Care varianta este mai buna ? Sunt destul de bune ambele ?
Set de intrare : 1 milion de elemente: k=500.000
Ex. 2 Se considera un tablou bidimensional de litere si o lista de cuvinte.
Obiectiv : gasirea de cuvinte in tablou
SDA curs 1 I IS 2009/2010 4
Variante de solutii Ex.2
a) Pentru fiecare cuvant din lista se verifica fiecare triplet ( rand,
coloana, orientare); vor rezulta prin implementare foarte multe bucle
imbricate
b) Pentru fiecare quadruplu ( rand, coloana, orientare, numar de
caractere) se verifica daca cuvantul exista in lista
Dimensiune tablou:16x16; lungime cuvant :1-16: lista – intregul dictionar.
Documentul este oferit gratuit,
trebuie doar să te autentifici in contul tău.
