Manual Grafuri

1. Preliminarii

1.1. Algoritmi

Toti algoritmii descrisi în cadrul acestei lucrari folosesc structuri de date de tip graf. Unele descrieri sînt însotite de o analiza a complexitatii algoritmului respectiv. Pentru ca analiza sa poata fi urmarita mai usor de cititor, în cadrul acestei sectiuni sînt prezentate notiuni de baza.

Definitia 1.1. Un algoritm este un set de instructiuni care trebuie executate pentru a se obtine un raspuns la o problema data.

Un algoritm are urmatoarele proprietati (Knuth) (Burdescu, p 10):

 finitudine: trebuie sa se termine întotdeauna dupa un numar finit de pasi (instructiuni);

 determinism: fiecare pas trebuie sa fie exact precizat, în mod riguros si neambiguu;

 generalitate: trebuie sa rezolve problema pentru orice date de intrare din domeniul precizat;

 efectivitate: fiecare instructiune trebuie sa fie exacta si de durata finita.

Ultima proprietate trebuie nuantata, avînd în vedere faptul ca memoria oricarui calculator este limitata. Nu întotdeauna operatiile aritmetice se efectueaza exact, în unele cazuri obtinîndu-se o aproximare a rezultatelor, cum sînt de exemplu implementarile bazate pe aritmetica în virgula mobila (Goldberg).

În cadrul acestei lucrari algoritmii sînt descrisi într-un limbaj de tip Algol, un precursor al limbajului Pascal (cf Aho et al).

Avînd un algoritm care rezolva o problema data, urmeaza sa determinam resursele acestuia. Concret, de cîta memorie si timp avem nevoie ca sa obtinem solutia problemei? În acest scop facem urmatoarele simplificari: fiecare operatie elementara a algoritmului se executa într-o unitate de timp, informatiile despre un obiect elementar se memoreaza într-o locatie de memorie (Livovschi, Georgescu).

Fie f : N ® N o functie care indica relatia dintre numarul de valori (date de intrare) prelucrate de un algoritm, si numarul de operatii elementare efectuate de acesta pentru obtinerea rezultatelor. Functia f poate avea o expresie analitica destul de complicata, de aceea consideram înca o functie g : N ® N cu o expresie analitica simplificata.

Definitia 1.2. Functia f are ordinul de marime cel mult g(n), notatie: f Î O(g(n)), daca si numai daca exista doua valori, c > 0 si n0 Î N astfel încît pentru orice n > n0 sa avem f(n) £ c g(n).

O(g) = { h : N ® N | c > 0, n0 Î N a. î. n > n0, h(n) £ c g(n) }.

Definitia 1.3. Functia f are ordinul de marime cel putin g(n), notatie: f Î W(g(n)), daca si numai daca exista doua valori, c > 0 si n0 Î N astfel încît pentru orice n > n0 sa avem f(n) ³ c g(n).

W(g) = { h : N ® N | c > 0, n0 Î N a. î. n > n0, h(n) ³ c g(n) }.

Definitia 1.4. Functia f are ordinul de marime g(n), notatie: f Î q(g(n)), daca si numai daca exista trei valori, c1, c2 > 0 si n0 Î N astfel încît pentru orice n > n0 sa avem c1 g(n) £ f(n) £ c2 g(n).

q(g) = { h : N ® N | c1, c2 > 0, n0 Î N a. î. n > n0,

c1 g(n) £ h(n) £ c2 g(n) }.

Prezentam doua rezultate remarcabile care vor fi folosite pe parcursul lucrarii (Knuth):

(1) Se da un sir de n valori dintr-un domeniu pe care este definita o relatie de ordine totala. Cel mai eficient algoritm de ordonare a sirului dat, care se bazeaza pe comparatii, are complexitate de ordin W(n log n).

(2) Se da un sir de n valori ordonate. Cautarea unei valori (localizarea pozitiei acesteia sau obtinerea unui raspuns negativ) în sirul dat necesita un timp de ordin O(log n).