Algoritmi și Programare ID

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: