Capitolul 1
Introducere
Acest manual este dedicat ^n special studentilor de la formele de ^nvatam^ant ID (^Invatam^ant la Distanta)
si PU (Post universitare) de la Facultatea de Informatica a Universitatii "Alexandru Ioan Cuza" din Iasi.
Cartea se doreste a un suport pentru disciplinele Algoritmi si Programare (ID) si Structuri de Date si
Algoritmi (PU). Recomandam ca parcurgerea acestui suport sa se faca ^n paralel cu consultarea materialul
electronic a
at pe pagina web a cursului la adresa http://www.infoiasi.ro/fcs/CS2101.php. De fapt
continutul acestei carti este o versiune simpli cata a celui inclus pe pagina cursului. Din acest motiv
unele referinte apar ca nede nite (marcate cu ??"). Toate acestea pot gasite pe pagina cursului.
Structura manualului este urmatoarea: Capitolul doi include de nitia limbajului algoritmic utilizat
^mpreuna cu de nitiile pentru cele doua functii principale de masurare a e cientei algoritmilor: complex-
itatea timp si complexitatea spatiu. Tipurile de date cele mai utilizate ^n programare sunt prezentate
^n capitolul trei. ^In capitolul patru sunt prezentati principalii algoritmi de sortare interna bazati pe
comparatii. Capitolul al cincilea este dedicat algoritmilor de cautare si a principalelor structuri de date
utilizate de acesti algoritmi. Capitolul sase include doi algoritmi de enumerare: enumerarea permutarilor
si enumerarea elementelor produsului cartezian. Fiecare capitol este acopaniat de o lista de exercitii.
Capitolul 2
Despre algoritmi
2.1 Limbaj algoritmic
2.1.1 Introducere
Un algoritm este o secventa nita de pasi, aranjata ^ntr-o ordine logica speci ca care, atunci c^and este
executata, produce o solutie corecta pentru o problema precizata. Algoritmii pot descrisi ^n orice limbaj,
pornind de la limbajul natural p^na la limbajul de asamblare al unui calculator speci c. Un limbaj al
carui scop unic este cel de a descrie algoritmi se numeste limbaj algoritmic. Limbajele de programare
sunt exemple de limbaje algoritmice.
^In aceasta sectiune descriem limbajul algoritmic utilizat ^n aceasta carte. Limbajul nostru este tipizat,
^n sensul ca datele sunt organizate ^n tipuri de date. Un tip de date consta dintr-o multime de entitati de
tip data (valori), numita si domeniul tipului, si o multime de operatii peste aceste entitati. Convenim
sa grupam tipurile de date ^n trei categorii:
- tipuri de date elementare, ^n care valorile sunt entitati de informatie indivizibile;
- tipuri de date structurate de nivel jos, ^n care valorile sunt structuri relativ simple obtinute prin
asamblarea de valori elementare sau valori structurate iar operatiile sunt date la nivel de compo-
nenta;
- tipuri de date structurate de nivel ^nalt, ^n care valorile sunt structuri mai complexe iar operatiile
sunt implementate de algoritmi proiectati de catre utilizatori.
Primele doua categorii sunt dependente de limbaj si de aceea descrierile lor sunt incluse ^n aceata sectiune.
Tipurile de nivel ^nalt pot descrise ^ntr-o maniera independenta de limbaj si descrierile lor sunt incluse
^n capitolul 3. Un tip de date descris ^ntr-o maniera indepenedenta de reprezentarea valorilor si imple-
mentarea operatiilor se numeste tip de date abstract.
Pasii unui algoritm si ordinea logica a acestora sunt descrise cu ajutorul instructiunilor. O secventa
de instructiuni care actioneaza asupra unor structuri de date precizate se numeste program. ^In sectiunea
2.2 vom vedea care sunt conditiile pe care trebuie sa le ^ndeplineasca un program pentru a descrie un
algoritm.
2.1.2 Modelarea memoriei
Memoria este reprezentata ca o structura liniara de celule, ecare celula av^and asociata o adresa si
put^and memora (stoca) o data de un anumit tip ( g. 2.1). Accesul la memorie este realizat cu ajutorul
variabilelor. O variabila este caracterizata de:
Documentul este oferit gratuit,
trebuie doar să te autentifici in contul tău.
