Curs Metode de Analiza A Algoritmilor [PDF]

Zitiervorschau

qwertyuiopasdfghjklzxcvbnmq wertyuiopasdfghjklzxcvbnmq wertyuiopasdfghjklzxcvbnmq wertyuiopasdfghjklzxcvbnmq Metode de analiză a algoritmilor wertyuiopasdfghjklzxcvbnmq Note de curs wertyuiopasdfghjklzxcvbnmq wertyuiopasdfghjklzxcvbnmq wertyuiopasdfghjklzxcvbnmq wertyuiopasdfghjklzxcvbnmq wertyuiopasdfghjklzxcvbnmq wertyuiopasdfghjklzxcvbnmq wertyuiopasdfghjklzxcvbnmq wertyuiopasdfghjklzxcvbnmq wertyuiopasdfghjklzxcvbnmq wertyuiopasdfghjklzxcvbnmq Mașina Turing

Mihaela Colhon

Cuprins Algoritmi și funcții calculabile .............................................................................5 Instructiuni ........................................................................................................ 5 Caracteristicile algoritmilor ............................................................................... 9 Corectitudinea algoritmilor .......................................................................... 11 Calculabilitate .................................................................................................. 15 Mașina Turing ....................................................................................................17 Calcule realizate de Mașina Turing ................................................................. 21 Clase de complexitate ..................................................................................... 24 Familii de limbaje ............................................................................................ 25 Mașina Turing ca acceptor de limbaj .............................................................. 27 Exerciții ............................................................................................................ 29 Analiza complexității algoritmilor nerecursivi ...................................................30 Timpul de execuție .......................................................................................... 31 Cazuri de analiză.............................................................................................. 32 Analiza algoritmilor nerecursivi....................................................................... 33 Etapele analizei algoritmilor ..............................................................................37 Ordinul de creștere ......................................................................................... 37 Exerciții ............................................................................................................ 39 Notații asimptotice ............................................................................................43 Notația O ......................................................................................................... 44 Notația Ω ......................................................................................................... 47 Notația Θ ......................................................................................................... 48 Analiza asimptotică a principalelor structuri de prelucrare ............................ 52 Exerciții ............................................................................................................ 55 2

Analiza complexității algoritmilor recursivi .......................................................57 Metoda substituției ......................................................................................... 58 Metoda substituției înainte ............................................................................. 59 Metoda substituției înapoi .............................................................................. 60 Metoda Iterației .............................................................................................. 61 Arbori de recurență ......................................................................................... 63 Metoda Master ............................................................................................... 64 Tehnica reducerii ............................................................................................. 65 Aplicație a tehnicii de reducere....................................................................... 68 Exerciții ............................................................................................................ 70 Algoritmi recursivi. Studiu de caz ......................................................................72 Problema Turnurilor din Hanoi ....................................................................... 72 NP-completitudine ............................................................................................76 Limbaje formale .............................................................................................. 77 Verificări în timp polinomial ............................................................................ 79 Determinism .................................................................................................... 80 Clase de complexitate P și NP ......................................................................... 83 Reducere polinomială ..................................................................................... 87 Problema satisfiabilității (SAT) ........................................................................ 88 Varianta 2SAT ............................................................................................. 91 Bibliografie ........................................................................................................93

3

4

Algoritmi si funcții calculabile

Algoritmi și funcții calculabile Un algoritm este descris de o secvență finită de pași într-o ordine logică specifică astfel încât executarea lor produce o soluție corectă pentru problema precizată. Algoritmii pot fi descriși în orice limbaj pornind de la limbajul natural până la limbajele formale ca de exemplu limbajul de asamblare al unui calculator specific. Un limbaj al cărui scop unic este acela de a descrie algoritmi se numește limbaj algoritmic. Limbajele de programare sunt exemple de limbaje algoritmice. Limbajele algoritmice se considera limbaje tipizate, în sensul că datele sunt organizate în tipuri de date. Un algoritm cuprinde: •

•

Domeniul de date: o mulțime numărabilă de elemente asupra cărora operează algoritmul și care cuprinde și elementele de ieșire ale algoritmului (rezultatele) Descrierea algoritmului: un set finit de instrucțiuni care operează pe/cu elementele din domeniul de date.

Limbajul algoritmic are caracteristica de modularitate, modulele fiind reprezentate de subprograme. Există două tipuri de subprograme: proceduri și funcții.

Instructiuni Sintaxa instrucțiunii de atribuire este: ← unde este un nume de variabilă iar este o secvență de operații care în urma evaluării va produce un rezultat care se va memora în locația de memorie desemnată de . Atribuirea este singura instrucțiune cu ajutorul căreia se poate modifica memoria.

Algoritmi si funcții calculabile

Sintaxa instructiunii if if then

else

endif unde este o expresie care prin evaluare va produce un rezultat boolean. Componenta else a intrucțiunii if este facultativă.

Sintaxa instructiunii while while do

endwhile Această instrucțiune implică evaluarea componentei . Dacă rezultatul evaluării este true atunci se vor executa instrucțiunile din după care se continuă evaluarea condiției. Dacă rezultatul evaluării este false atunci execuția instructiunii while se termină.

6

Algoritmi si funcții calculabile

Dacă condiția nu este niciodată falsă, atunci ciclul WHILE intră într-o buclă infinită. Dacă condiția este de la bun inceput falsă, atunci ciclul WHILE nu se va executa niciodată.

Sintaxa instructiunii for for ← to do

endfor

sau for ← downto do

endfor

pentru care este o variabilă de tip întreg iar și sunt expresii care prin evaluare produc numere intregi.

7

Algoritmi si funcții calculabile

Blocul de instrucțiuni al unei instrucțiuni for se execută cel puțin o dată dacă rezultatul evaluării este mai mic sau egal decât evaluarea . Sintaxa intructiunii repeat repeat

until unde este o expresie care prin evaluare produce un rezultat boolean iar se execută atâta timp cât rezultatul produs prin evaluarea condiției este fals (dar execuția operațiilor din este asigurată cel putin o dată).

8

Algoritmi si funcții calculabile

Acest tip de instrucțiune asigură execuția cel putin o dată a instrucțiunilor din . Dacă condiția nu devine niciodată adevarată atunci ciclul REPEAT intră într-o buclă infinită.

Caracteristicile algoritmilor O problemă rezolvabilă algoritmic o definim ca pe o funcție p total definită pe mulțimea datelor de intrare (I) cu valori în mulțimea datelor de ieșire (O). p: I → O Se poate ca, pentru anumite date din mulțimea de intrare, problema p să nu aibă sens. Numim mai departe mulțimea datelor de intrare pentru care problema p are sens ca domeniul de date al algoritmului care implementeaza problema p. Rezumând, un algoritm trebuie să aibă următoarele proprietăți: • •

•

Generalitate: un algoritm nu rezolvă doar o anumită problemă, ci o clasă de probleme de același tip: ∀x ∈ I ⇒ ∃ p(x) Finititudine: un algoritm este compus dintr-un număr finit de instrucțiuni. Mai mult, setul de transformări care se aplică pe datele intrării x ∈ I pentru a obține un rezultat din mulțimea O este de asemenea finit Unicitate: numărul de transformări și ordinea în care sunt aplicate sunt bine determinate de regulile algoritmului. Altfel spus, pentru aceleași date de intrare x ∈ I, transformările aplicate și rezultatele obținute sunt mereu aceleași

Un algoritm trebuie să fie general. Algoritmul trebuie să funcționeze pentru toate instanțele intrărilor pentru care a fost definit și nu doar pentru anumite instanțe. De exemplu, să considerăm problema sortării crescătoare a unui șir de numere. (2,1,4,3,5)

(1,2,3,4,5) 9

Algoritmi si funcții calculabile

input

output

Vom considera mai departe o variantă de sortare prin metoda bulelor. a cărui descriere este următoarea: -

compară primele două numere și, dacă nu sunt în ordinea dorită, le interschimbă

-

la fel procedează pentru perechea formată din al doilea și al treilea număr

-

....

-

algoritmul continuă până ajunge să compare penultimul element cu ultimul element

Este această variantă de sortare un algoritm general? Realizează sortarea pentru orice vector de numere? Un algoritm trebuie să fie finit. Un algoritm trebuie să se termine, adică să se oprească după un număr finit de pași. Să considerăm următorul exemplu: Step1:

x ← 1

Step2:

x ← x + 2

Step3:

if x=10 then STOP 10

Algoritmi si funcții calculabile

else GO TO Step 2 endif Funcționează acest algoritm? Ce rezultat va genera? Un algoritm trebuie să fie neambiguu. Operațiile unui algoritm trebuie sa fie într-un mod riguros specificate. La fiecare pas al execuției trebuie să se știe precis care e pasul următor. Să considerăm următorul exemplu: Step 1: x ← 0 Step 2: Either

increment or decrement x with 1

Step 3: if x ∈ [-2,2] then GO TO Step 2 else Stop. endif Asupra unui algoritm se pun o serie de condiții: • • • •

Corectitudinea algoritmului Condiția de oprire Durata execuției Determinarea spațiului de memorie alocat

Corectitudinea algoritmilor Atunci când proiectăm un algoritm acesta trebuie să fie evaluat cel puțin din următoarele puncte de vedere: • Corectitudine: acest lucru înseamnă să se verifice dacă algoritmul produce soluția corectă (aceast rezultat trebuie de asemenea să fie obținut după un număr finit de prelucrări). • Eficiență: acest lucru înseamnă a stabili cantitatea de resurse (spațiu de memorie și timp de execuție) necesare pentru a executa algoritmul pe o mașină. 11

Algoritmi si funcții calculabile

Testarea corectitudinii unui algoritm implică de obicei următorii pași: 1) Analiza experimentală. Algoritmul se testează pe diferite instanțe ale problemei. Principalul avantaj al acestei abordări este simplitatea ei, în timp ce principalul dezavantaj este faptul ca testarea nu poate acoperi întotdeauna toate cazurile posibile ale datelor de intrare. Totuși analiza experimentală permite uneori identificarea situațiilor în care algoritmul nu funcționează. 2) Analiza formală. Scopul analizei formale este de a dovedi că algoritmul funcționează pentru orice instanță a datelor de intrare. Această abordare este numită formală ca urmare a utilizării regulilor formale de logică cu scopul de a demonstra faptul că algoritmul respectă specificațiile sale. Principalul avantaj al acestei abordări este că, dacă este aplicat riguros, această analiză garantează corectitudinea algoritmului. Principalul dezavantaj este dificultatea de a găsi o dovadă, în special pentru algoritmii dificili. În acest caz, algoritmul este descompus în subprograme și analiza se concentreză pe aceste subcomponente. Pe de altă parte, abordarea formala ar putea duce la o mai bună înțelegere a algoritmilor. Principalele etape în analiza formală a corectitudinii unui algoritm sunt: • Identificarea proprietăților de date de intrare (așa numita problemă a precondițiilor). • Identificarea proprietăților pe care trebuie să le îndeplinească datele de ieșire (așa numita problemă a post-condițiilor). • Demonstrarea faptului că, începând de la precondiții și prin executarea acțiunilor prevăzute în algoritm se obțin postconditiile. Când analizăm corectitudinea unui algoritm un concept util este cel al stării algoritmului. Starea algoritmului este definită prin setul de valori corespunzător pentru toate variabilele utilizate în algoritm. 12

Algoritmi si funcții calculabile

În timpul executiei, un algoritm trece prin mai multe stări (de obicei prin atribuiri de valori variabilelor) de la un pas la alt pas de prelucrare. Ideea de bază a verificării corectitudinii este aceea de a stabili care trebuie să fie starea corespunzătoare fiecărei etape de prelucrare astfel încât, la sfârșitul algoritmului postcondițiile să fie îndeplinite. Odată ce am stabilit aceste stări intermediare este suficient să verificăm dacă fiecare pas de prelucrare asigură transformarea corecta a starii actuale în starea următoare. În cazul în care structura de prelucrare este una secvențială atunci procesul de verificare este imediat (trebuie să analizăm doar efectul pe care atribuirile îl determină asupra stării algoritmului). Dificultățile pot apărea datorită instrucțiunilor repetitive, deoarece există multe surse de erori: inițializările poate fi greșite, etapele de prelucrare din interiorul buclei pot fi greșite sau condiția de oprire poate fi greșită. O metodă formală de a dovedi că o instrucțiune repetitivă funcționează corect este prin metoda inducției matematice. Exemplu. Algoritmul de sortare prin inserție: Input: un vector de n elemente v[1...n]. Output: un vector obținut prin sortarea elementelor din v. Descrierea formală a algoritmului: se pornește cu o listă vidă de elemente și succesiv, se inserează elementele din v în poziția corectă conform ordinii de sortare. Algoritmul de sortare prin insertie for j ← 2 to n do key ← v[j] i ← j-1 while (i > 0 and v[i] > key) v[i+1] ← v[i] i ← i-1 endwhile 13

Algoritmi si funcții calculabile

v[i+1] ← key endfor Să demonstrăm corectitudinea algoritmului de sortare prin insertie prin metoda inducției matematice. Scopul este de a demonstra că o instrucțiune I(n) este adevărată pentru toate numere naturale, începând cu n = 1. Folosind inducția matematică, doi pași sunt suficienti pentru acest scop: 1. Cazul de bază. Se arată că I(1) este adevărată. 2. Pasul inductiv. Să presupunem că I(k) este adevărată pentru k < n. Se demonstrează că I(k + 1) este de asemenea adevărată. Invarianți în structurile repetitive (în engleză Loop invariants) sunt instrucțiuni care sunt valide în orice moment al execuției buclei. Relativ la invarianți trebuie să considerăm trei aspecte: -

Inițializare – invariantul este adevărat înainte de prima iterație

-

Întreținere - dacă invariantul este adevărat înainte de o iterație, rămâne adevărat și înainte de următoarea iterație

-

Terminare - atunci când bucla se termină invariantul dă proprietatea utilă relativă la corectitudinea algoritmului

Pasul 0: se caută I - invariantul algoritmului de inserare. La începutul fiecărei iterație a buclei for subvectorul v[1..j-1] constă din elementele vectorului initial v[1..j-1], dar în ordine sortată. Pasul 1: Cazul de bază, pentru j = 2, subvectorul v[1..j-1], constă dintr-un singur element și evident v[1...j-1] este sortat. Pasul 2: Pasul inductiv

14

Algoritmi si funcții calculabile

Pasul 3: Pasul de terminare al ciclului for. Algoritmul se termină atunci când j depășește valoarea lui n, și anume j=n+1. Deci, în baza invariantului I, v[1..j-1] = v[1..n] ceea ce înseamnă că în acest moment vectorul este sortat.

Calculabilitate Conceptele de funcție calculabilă și algoritm formează conceptele de bază din teoria calculabilității fiind preluate din informatică și matematică. Din punct de vedere tehnic, algoritmul este definit ca o secvență finită de pași neambigui și executabili a căror execuție asigură rezolvarea taskului pentru care algoritmul în cauză a fost definit. Teoria mulțimilor constituie un instrument de descriere simplă și precisă a conceptului de funcție. Construirea unui model matematic pentru acest concept este o sarcină relativ simplă deoarcere avem de a face cu un proces static spre deosebire de algoritmi care sunt procese dinamice. Calculabilitatea unei funcții înseamnă existența unei mașini de calcul și implicit a unui program, care prin execuție pe mașina aleasă să calculeze valorile funcției în orice punct din domeniul de valori al acesteia. Definiție. O funcție f: I → O este efectiv calculabilă dacă există o procedură efectivă de calculare a valorilor funcției pentru orice element x ∈ I. O procedură efectivă este o mulțime finită de instrucțiuni a căror execuție se termină într-un timp finit și care implică o cantitate finită de date pentru a obține un rezultat, mereu același pentru date identice. În general un program scris într-un limbaj de programare este asimilat conceptului de “algoritm” ceea ce înseamnă că programul respectiv va evalua o funcție. Dacă domeniul de valori al funcției reprezintă domeniul datelor de intrare ale programului atunci valorile funcției vor fi rezultatele programului. Un algoritm constituie o reprezentare finită a unei metode (procedeu) de calcul care permite rezolvarea unei probleme. El poate fi interpretat ca un text de lungime finită, scris într-un limbaj artificial în care fiecare rând 15

Algoritmi si funcții calculabile

are o anumită semnificație. Algoritmul descrie operațiile care se pot efectua conform procedeului de calcul. O problemă rezolvabilă algoritmic o gândim ca pe o funcție p total definită pe mulțimea datelor de intrare I (cel mult numărabilă) cu valori în mulțimea datelor de ieșire O (cel mult numărabilă). Fiecare element x ∈ I reprezintă o instanța a problemei (un caz particular) iar dacă există y astfel încât f(x) = y atunci y este soluția problemei p pentru instanța x. În caz contrar se spune că p nu are soluție pentru instanța x. Dacă există un algoritm care rezolvă o problemă p acest lucru nu atrage cu necesitate unicitatea acestuia. De asemenea un același algoritm se poate comporta diferit pe seturi de date de intrare diferite.

16

Mașina Turing

Mașina Turing O mașină Turing este un acceptor care poate să scrie pe banda de intrare. În acest mod, banda de intrare devine o memorie auxiliară. Când a inventat mașina care îi poartă numele, Turing nu era interesat de calculatoare ci de posibilitatea specificării și rezolvării problemelor de matematică folosind mijloace automate. Adică, poate fi rezolvată orice problemă de matematică utilizând niște reguli elementare de prelucrare a șirurilor?

Figure 1 Modele, paradigme și limbaje

1

Mașina Turing este un dispozitiv algoritmic de tip simplu dar cu o putere de calcul complexă, capabil sa execute cei mai complecși algoritmi. Orice alt model de calcul propus de-a lungul timpului, în final s-a dovedit a fi mai puţin expresiv, sau tot atît de expresiv cît maşina Turing. În abordarea din care face parte acest dispozitiv de calcul, orice cantitate de informație folosită de un algoritm la intrare, la ieșire sau ca valoare intermediară este socotită ca un șir de simboluri.

1

Mihnea Muraru, Paradigme de Programare – note de curs 2012

Mașina Turing

În construcția teoretică a mașinii, Turing a pornit de la modelul mașinii de scris: -

mașina de scris este considerată drept un dispozitiv cu memorie infinită (număr nelimitat de foi de scris) se poate mișca înainte și înapoi de la o poziție la alta poate să scrie un caracter în fiecare poziție

Turing a îmbunătățit acest model, înzestrând mașina Turing cu alte facilități cum ar fi: -

ștergerea unui simbol din memorie (prin rescrierea lui cu un caracter special – caracterul blank) citirea simbolurilor de pe banda posibilitatea de a avea un număr foarte mare (chiar dacă acesta este finit) de configurații interne

Mașina Turing este compusă din următoarele elemente: -

-

o bandă infinită de celule (de obicei finită la stânga și infinită la dreapta). În fiecare celulă se poate memora un caracter din alfabetul de citire/scriere al mașinii un cap de citire/scriere care se poate mișca de la dreapta la stânga deasupra benzii o unitate de control definită de un număr finit de reguli care indică mașinii ce să facă la fiecare mișcare a capului de citire/scriere în funcție de starea curentă și de simbolul citit

Figura 1 Arhitectura unei mașini Turing

18

Mașina Turing

Unitatea de control asigură execuția mișcărilor. O mișcare este formată din: -

stabilirea stării următoare pentru unitatea de control scrierea unui simbol pe banda de intrare și/sau mișcarea capului de citire/scriere la stânga sau la dreapta

Definiție. O mașină Turing deterministă este un tuplu de forma: (S, Σ, δ, s0) unde: -

S este o mulțime finită și reprezintă mulțimea stărilor interne ale mașinii. Σ este o mulțime finită, alfabetul de intrare care conține simbolul λ (caracterul blank) dar nu conține simbolurile L și R δ este funcția de tranziție definită astfel: δ: S × Σ → (S ∪ {STOP}) × Σ ∪ {L, R} s0 este starea inițială a mașinii Turing

Dacă s ∈ S, a ∈ Σ și δ(s, a) = (p, b) înseamnă că fiind în starea s și având simbolul a sub capul de citire/scriere mașina trece în starea p. Dacă b ∈ Σ atunci simbolul a va fi înlocuit cu simbolul b, altfel capul de citire/scriere se va deplasa la stânga sau la dreapta în funcție de valoarea simbolului b ∈ {L, R}. Caracteristica de calcul determinist a acestei mașini provine de la faptul că dintr-o stare internă oarecare și primind un simbol pe banda de intrare automatul va trece într-o stare unic determinată. Un calcul determinist pentru o mașină Turing și pentru o intrare ω ∈ Σ* este o secvență (posibil infinită) de stări pornind de la starea inițială a mașinii Turing astfel încât fiecare din aceste stări implică în mod unic următoarea stare din secvență. Spunem că un calcul este nedeterminist dacă dintr-o stare internă oarecare, primind un simbol al alfabetului de intrare, mașina poate trece în nici o stare, într-o singură stare sau în mai multe stări. Trecerea dintr-o stare internă în alta nu este asociată cu probabilităţi. 19

Mașina Turing

Încetarea funcționării mașinii Turing se face în momentul atingerii stării STOP sau atunci cînd se încearcă mutarea capului de citire/scriere la stânga dincolo de marginea din stânga a benzii de intrare. Generalizând conceptul de mașină Turing cu o singura bandă se obține următorul model. Definiție. O k-bandă mașină Turing deterministă (k ≥ 1) este un sistem: (S, Σ, δ, s0) unde: -

S este o mulțime finită numită mulțimea stărilor Σ este o mulțime finită numită alfabetul mașinii Turing δ: S × ΣK → (S ∪ {STOP}) × Σk × {L, R}k s0 este starea inițială a mașinii Turing

Se poate demostra că, din punct de vedere al puterii de calcul, o mașină Turing cu k-benzi, k >1, este echivalentă cu o mașină Turing cu o singură bandă. O mașina Turing poate fi asimilată unui calculator care rulează un singur program. Software-ul este reprezentat de funcția de tranziție iar hardware-ul de banda de citire/scriere și de capul de citire/scriere. O maşină Turing calculează o funcţie, fixată, pe cuvintele de intrare. În acest fel se comportă ca un calculator având un program fixat. Singura problemă este că mașina Turing în proiectarea clasică nu poate produce ieșiri, acestea trebuind să fie codificate tot prin stările interne ale mașinii. Observație. O mașina Turing este un acceptor determinist, ceea ce înseamnă că (∀) s ∈ S și (∀) a ∈ Σ, dacă există și este definită funcția δ pentru perechea (s, a) atunci δ(s, a) va trece într-o stare unic determinată. O mașină Turing nedeterministă are aceleași componente ca una determininstă, cu excepția funcției de tranziție care se definește astfel: δ : S × Σ → Pf (S × Σ × {L, R}) 20

Mașina Turing

Această definire a funcţiei de tranziţie permite ca pentru o stare dată şi un simbol citit pe bandă, să avem un număr finit de posibilităţi de a alege configuraţia în care trece maşina.

Calcule realizate de Mașina Turing Definim configurație a unei mașini Turing un tuplu de forma (s, ωL, a, ωR) în care s este starea curentă a mașinii, ωL este stringul de caractere aflat la stanga capului de citire/scriere, a este simbolul aflat sub capul de citire/scriere iar ωR este stringul aflat la dreapta capului de citire/scriere. Un calcul realizat de o mașina Turing este o secvență finită de configurații de forma c0 |- c1 |- ... |- cn pentru care relația “|-“ este definită astfel: -

(s, ωL, a, ωR) |- (p, ωL, b, ωR) dacă și numai dacă δ(s, a) = (p, b) iar b ∈ Σ. dacă δ(s, a) = (p, b) iar b ∉ Σ: o (s, ω1...ωk-1, ωk, ωk+1... ωn) |- (p, ω1... ωk, ωk+1, ωk+2... ωn) dacă și numai dacă δ(s, a) = (p, R). o (s, ω1...ωk-1, ωk, ωk+1... ωn) |- (s, ω1...ωk-2, ωk-1, ωk... ωn) dacă și numai dacă δ(s, a) = (p, L).

Se poate considera că o mașina Turing știe să evalueze funcții definite pe șiruri de simboluri cu valori în șiruri de simboluri. Dacă mulțimile Σ1 și Σ2 sunt două mulțimi alfabet care nu conțin simbolul λ, să considerăm funcția f: Σ1* → Σ2*. Spunem că mașina Turing (S, Σ, δ, s0) calculează funcția f dacă Σ1, Σ2 ⊆ Σ și pentru orice șir ω ∈ Σ1* dacă (∃) u ∈ Σ2*, f(ω) = u atunci avem (s0, λωλ) |-* (STOP, λuλ). Definiție. Pentru orice funcție f pentru care există o mașina Turing care o calculează spunem că funcția f este Turing calculabilă.

21

Mașina Turing

Să considerăm reprezentarea unară a numerelor naturale. Peste alfabetul Σ= {1} reprezentarea unui număr natural n este  1 … 1. Evident, numărul 0  

va fi reprezentat de stringul vid. În acest caz, o funcție f: N → N este calculabilă de o mașină Turing dacă aceasta calculeaza funcția f ′: Σ* → Σ*, f ′(ω) = u, unde pentru n ∈ N, ω =  1 … 1 și u =  1…1.  

  

Exemplu: Să considerăm funcția succesor f: N → N, f(n) = n+1. Să se stabilească dacă această funcție este Turing calculabilă. Pentru a demonstra acest lucru, vom considera mașina Turing ({s0}, {1}, δ, s0) cu următoarea funcție de tranziție: δ s0

1 (STOP, R)

λ (s0, 1)

Intr-adevăr, pentru intrarea 11 vom avea (s0, λ11λ) |- (s0, λ111) |- (STOP, λ111λ). Mai mult, pentru orice n ≥ 0, (s0, λ1  … 1 λ) |- (s0,  1 … 1 ) | 

(STOP,  1 … 1 λ).

 

 

Să ne mai amintim că elementele procesate de maşinile Turing sunt limbaje, adică mulţimi de cuvinte. O maşină Turing primeşte la intrare un cuvînt dintr-un anumit limbaj şi produce la ieşire un cuvînt dintr-un alt limbaj, care este răspunsul aşteptat. Dacă răspunsurile sunt doar „yes” sau „no” (adică un singur bit), atunci vom spune că maşina Turing decide limbajul format din toate cuvintele pentru care răspunsul este „yes”. O mașină Turing poate fi utilizată și ca acceptor de limbaj. Să considerăm un alfabet Σ și un limbaj L peste acest alfabet, L ⊆ Σ. Definim funcția: eval :Σ* → {yes, no} astfel: oricare ar fi ω∈ Σ* , ∈    =  , ∉  22

Mașina Turing

Spunem că limbajul L este decidabil în sens Turing dacă și numai dacă funcția eval este Turing calculabilă. Exemplu: Să considerăm limbajul L ca fiind limbajul cuvintelor de lungime pară peste alfabetul Σ = {a}, și anume: L = {ω∈ Σ*| ω= ω1... ωn, n mod 2 = 0 } Pentru a verifica dacă limbajul L este Turing acceptabil, vom considera mașina Turing ({s0, ..., s6}, {a, λ} ∪ {D, N}, δ, s0) unde: δ s0 s1 s2 s3 s4 s5 s6

a (s2, λ) (s0, λ)

λ (s1,L) (s4, R) (s3, L) (s6, R) (s5, D)

D

N

(STOP, R) răspunde yes

(STOP, R) răspunde no

(s5, N)

Verificarea decidabilității limbajului L în raport cu mașina considerată o lasăm ca exercițiu. Observație. La mașinile Turing, noțiunea de acceptare este mai largă decât noțiunea de decidabilitate. Într-adevar, pentru un limbaj L peste alfabetul Σ spunem ca este Turing acceptabil dacă există o mașina Turing care se oprește dacă și numai dacă ω∈ L, pentru orice ω ∈ Σ*. Ca o consecință directă, obținem că limbajele Turing decidabile sunt și limbaje Turing acceptabile. Reciproca însă nu este valabilă. Exista probleme care nu pot fi rezolvate deloc de masina Turing numite probleme nedecidabile.

23

Mașina Turing

Clase de complexitate Teoria complexităţii calculului se referă la problemele de decidabilitate prin prisma dificultăţii soluţiei. Dificultatea unei probleme este descrisă în termeni de resurse computaţionale necesare celui mai eficient algoritm care rezolvă problema respectivă. Vom descrie, pe scurt, clasele de complexitate cele mai importante. Pentru fiecare din aceste clase se cunosc probleme complete (o problemă de decizie p se numeşte completă pentru o mulţime S de probleme de decizie dacă p este element al mulţimii S şi orice problemă din S poate fi redusă la p). Vom prezenta clasele de complexitate în ordinea crescătoare a complexităţii lor. Spaţiu constant Prima clasă de complexitate este cea a maşinilor care folosesc o cantitate fixă de spaţiu pentru a-şi face calculele. Această cantitate este independentă de mărimea datelor de intrare. Chiar și atunci când datele de intrare tind la infinit, maşina foloseşte la fel de puţin spaţiu. Maşinile Turing care nu folosesc nici un fel de spaţiu pe bandă în afara cuvântului citit pe banda de intrare se numesc automate finite. Toate limbajele care se pot decide în spaţiu constant se numesc limbaje regulate. Aceste limbaje sunt extrem de importante în practică; există multe programare care manipulează limbaje regulate, de exemplu interpretorul Perl. Limbajele regulate sunt utile prin faptul că permit să se demonstreaze faptul că ele pot fi acceptate în timp liniar: pentru orice limbaj regulat există o maşină Turing care decide un cuvînt de lungime n în timp O(n) – adică în timp ce îl citește. Spaţiu logaritmic O altă clasă de complexitate este cea a limbajelor care pot fi acceptate folosind spaţiu logaritmic în lungimea cuvîntului de intrare. Pentru orice cuvînt de lungime n maşina nu foloseşte mai mult de O(log n) celule de memorie pentru a procesa cuvântul. Timp polinomial Cea mai folosită clasă de complexitate este cea a timpului polinomial, notată cu P. Putem defini matematic foarte precis 24

Mașina Turing

timpul polinomial ca aparținând problemelor care se pot decide în timp f(n), unde f este un polinom. Se arată imediat că orice se poate calcula în spaţiu logaritmic, nu are niciodată nevoie de mai mult decît timp polinomial. Timp exponențial Problemele care au un astfel de timp de calcul formează așa zisa clasa „problemelor monstruase”.

Familii de limbaje Se numește alfabet sau vocabular V orice mulțime finită și nevidă de simboluri (sau litere, caractere, variabile). Un cuvânt peste un alfabet V este o secvență p = a1a2 . . . an, ai ∈ V, i = 1, ... , n. Numărul n se numește lungimea cuvântului și va fi notat cu |p|. Vom considera și cuvântul vid λ care nu conține nici un simbol; evident |λ| = 0. Noțiunea de cuvânt este fundamentală în teoria limbajelor formale sau în alte domenii ale informaticii; termeni sinonimi utilizați în literatură sunt propoziție, frază sau șir. Să observăm că nu există o similitudine foarte bună între noțiunile de “alfabet”, „cuvânt” etc. din teoria limbajelor formale și noțiunile corespunzătoare din lingvistică. Mulțimea tuturor cuvintelor peste un alfabet V o notăm cu V+. Această mulțime împreună cu cuvântul vid va fi notată cu V*. Un limbaj L peste alfabetul V este o parte a mulțimii tuturor cuvintelor peste V , deci L ⊆ V*. Un limbaj peste un alfabet poate să fie o mulțime finită sau infinită de cuvinte. În cazul unei mulțimi finite, el poate fi descris prin enumerarea efectivă a cuvintelor limbajului. În cazul în care este o mulțime infinită, el poate fi definit punând în evidentă structura cuvintelor lui. Există două mecanisme de bază pentru definirea limbajelor: 1. Mecanisme generative, care permit generarea tuturor cuvintelor limbajului. Există mai multe tipuri de mecanisme de generare a 25

Mașina Turing

limbajelor, între care gramaticile Chomsky, sistemele Lindenmayer,etc. 2. Mecanisme analitice, care determină dacă un cuvânt dat aparține sau nu limbajului. Sunt așa-numitele automate, automate finite, automate push-down. Un rol deosebit în teoria limbajelor formale îl au gramaticile Chomsky. Fie VN și VT două alfabete disjuncte, numite respectiv alfabetul simbolurilor neterminale (VN) și alfabetul simbolurilor terminale (VT). Notăm alfabetul gramaticii cu V, evident V = VN ∪ VT și fie P ⊆ V*VNV* × V*. Mulțimea P va fi deci formată din perechi de forma (u, v), cu proprietatea că u = u1Au2, cu u1, u2 ∈ V*, A ∈ VN și v ∈ V*, deci u și v sunt cuvinte peste V cu observația că u trebuie să conțină cel puțin un simbol neterminal. Vom spune că o astfel de pereche este o regulă de producție (regulă de generare, regulă de rescriere) și o vom nota u → v (vom spune că u se transformă în v). Apartenența unei reguli la P o vom nota în mod următor: (u → v) ∈ P.

O gramatică (Chomsky) G este un sistem G = (VN , VT , S, P), unde VN este alfabetul simbolurilor neterminale, VT este alfabetul simbolurilor terminale, S ∈ VN este simbolul inițial al gramaticii, iar P este mulțimea de reguli. Limbajul generat de gramatica G se definește ca mulțimea cuvintelor w peste alfabetul V:  ! = "# ∈ $%∗ |(⇒∗ #}

Tipuri de gramatici. După forma regulilor de generare, gramaticile Chomsky se împart în mai multe tipuri: • •

Gramatici de tipul 0 sunt gramatici fără restricții asupra regulilor; Gramatici de tipul 1 (dependente de context); sunt gramatici care au reguli de forma uAv → upv, u,p,v ∈ V* și A ∈ VN sau A → λ 26

Mașina Turing

•

•

Gramaticile de tipul 2 (independente de context); sunt gramatici care au reguli de forma: A → u, A ∈ VN și u ∈ V* Gramaticile de tipul 3 (regulate); sunt gramatici care au reguli de forma * → ,- * → -,    .→/ .→/

cu A, B, C ∈ VN și p, q ∈ VT*.

În raport cu această clasificare, în funcție de tipul de gramatică folosit la generarea limbajului avem limbaje de ordin 0 (L0), 1 (L1), 2 (L2) sau 3 (L3).

Mașina Turing ca acceptor de limbaj În această secțiune mașinile Turing sunt descutate din punctul de vedere al calității lor de acceptoare de limbaje formale. Mașina Turing este un mecanism de recunoaștere a limbajelor de tipul zero. În felul acesta, familiilor de limbaje din clasificarea Chomsky le corespund automate specifice de recunoaștere: -

Familia L3 - automate finite, Familia L2 - automate push–down, Familia L1 - automate liniar mărginite, Familia L0 - mașina Turing

Limbajul recunoscut de o mașină Turing MT = (S, Σ, δ, s0) se definește ca mulțimea: L(MT) = { ω ∈ Σ* | (s0, ω) |-+ (STOP, λ) } Este posibil ca mașina să ajungă într-o stare finală înainte de citirea integrală a cuvântului ω însă pentru a putea fi considerat acceptat,

27

Mașina Turing

atingerea stării finale trebuie făcută numai după parcurgerea cuvântului ω. Limbajul acceptat de o mașina Turing este mulțimea cuvintelor ω ∈ Σ* care, prin plasarea pe banda de intrare în partea stângă a benzii determină ca mașina Turing, prin tranzițiile efectuate și pornind din starea inițială cu unitatea de comandă/control poziționată pe prima locație să ajungă în starea finală având capul de citire/scriere pe ultima locație a cuvântului dat.

Deoarece clasa tuturor limbajelor peste un alfabet Σ este 2Σ - mulțime nenumărabilă, cum mulțimea mașinilor Turing este numărabilă se pune problema identificării atît a limbajelor acceptate dar și a limbajelor neacceptate. ∗

Un limbaj L este rezolvabil (decidabil) dacă există o mașină Turing MT acceptor astfel încât pentru orice ω ∈ Σ* calculul determinist al mașinii se oprește și acceptă intrarea ω dacă și numai dacă ω ∈ L (invers, pentru ω ∉ L calculul determinist se oprește într-o stare de rejectare).

28

Mașina Turing

Exerciții 1) Să considerăm următorul exemplu de mașină Turing: ({s0, s1}, {a, λ}, δ, s0) pentru care funcția de tranziție este definită astfel: δ a λ s0 (s1, λ) (STOP, λ) s1 (s0, a) (s0, R) Să se stabilească tranzițiile pentru intrarea aaa pentru cazul în care poziția capului este pe primul caracter din șir. Răspuns: (s0, aaaλ) |- (s1, λaaλ ) |- (s0, λaaλ) |- (s1, λλaλ) |- (s0, λλaλ) |- (s1, λλλλ) |- (s0, λλλλλ) |- (STOP, λλλλλ) 2) Să considerăm următorul exemplu de mașină Turing: ({s0}, {a, λ}, δ, s0) pentru care funcția de tranziție este definită astfel: δ a λ s0 (s0, L) (STOP, λ) Să se stabilească tranzițiile pentru intrarea aaa pentru cazul în care poziția capului este pe ultimul caracter din șir. 3) Să considerăm următorul exemplu de mașină Turing: ({s0, s1, s2}, {a, b, λ}, δ, s0) pentru care funcția de tranziție este definită astfel: δ a b λ s0 (s1, L) (s1, L) (s1, L) s1 (s0, b) (s0, a) (s2, R) s2 (s2, R) (s2, R) (STOP, λ) Să se stabilească tranzițiile pentru intrarea aaaλ pentru cazul în care poziția capului este pe ultimul caracter din șir. De asemenea, să se determine comportamentul mașinii pentru intrarea λλ. Hint. Funcția calculată de această mașină este funcția care interschimbă caracterele a și b.

29

Analiza complexității algoritmilor nerecursivi

Analiza complexității algoritmilor nerecursivi Analiza complexității unui algoritm are ca scop estimarea volumului resurselor de calcul necesare pentru execuția algoritmului: • •

Complexitate statică: spațiul de memorie necesar pentru stocarea datelor care se prelucrează Complexitate dinamică: timpul necesar pentru execuția tuturor prelucrărilor specificate de instrucțiunile algoritmului

Dacă în anii 1990 spațiul de memorie utilizat de un program era o resursă critică datorită capacității reduse a memoriilor calculatoarelor din acea vreme, astăzi aceast factor este mai puțin important. Calculatoarele actuale au suficientă memorie pentru procesările obișnuite. Bineînțeles ca volumul resurselor necesare depinde de volumul datelor de intrare. Mai precis, dimensiunea datelor de intrare este calculată după numărul de biți necesari pentru stocarea datelor. Mărimea unei instanțe, notată cu |x| este dată de numărul de biți necesari pentru stocarea lui x. Astfel, când vorbim de stocare, |x| este numărul de elemente care se sortează. La algoritmii numerici, |x| este valoarea numerică a instanței x. Dintre cele două resurse de calcul, cea critică este timpul de execuție. Acesta depinde de numărul de operații care trebuie efectuate și de dimensiunea datelor de intrare. Deci, timpul de execuție diferă de la execuție la alta. Având in vedere că pentru seturi de date de intrare diferite, un același algoritm operează în timpi de execuție diferiți, analiza complexității algoritmilor tratează cu precădere două cazuri: • •

Cazul cel mai defavorabil are durata maximă de execuție Cazul mediu – se consideră drept raportul între suma timpilor necesari execuției tuturor seturilor de date posibile și numărul

Etapele analizei algoritmilor

acestora. Însă, marea majoritate a algoritmilor au un număr infinit de seturi de date, deci acest caz nu poate fi analizat. Un algoritm este considerat eficient dacă necesită un volum rezonabil de resurse de calcul.

Timpul de execuție În continuare, vom nota cu T(|x|) timpul de execuție al unui algoritm relativ la instanța x ∈ I. Pentru a estima timpul de execuție este necesar a se stabili un model de calcul și o unitate de măsură. Vom considera în cele ce urmează modelul de calcul cu acces aleatoriu: • • •

Toate instrucțiunile sunt executate secvențial Fiecărei operații elementare i se alocă o unitate de timp, indiferent de tipul operanzilor Timpul de acces la informație nu este contorizat

Unitatea de măsură pe baza căreia vom calcula eficiența teoretică a unui algoritm derivă din principiul invariației potrivit căruia două implementări diferite ale aceluiași algoritm nu diferă în eficiență cu mai mult decât o constantă multiplicativă. Adică, presupunând ca avem două implementări de T1(|x|) respectiv T2(|x|) secunde pentru un caz de mărime |x|, există o constantă pozitivă c astfel încât T1(|x|) < cT2(|x|), pentru orice |x| suficient de mare. Dacă un algoritm necesită un timp de ordin |x| vom spune că necesită un timp liniar sau că este un algoritm liniar. Similar, un algoritm este pătratic, cubic, polinomial sau exponențial dacă necesită timp de ordinul |x|2, |x|3, |x|k respectiv k|x|, unde k este o constantă.

31

Etapele analizei algoritmilor

Cazuri de analiză Asa cum s-a mai precizat, timpul de execuție depinde de dimensiunea datelor de intrare dar și proprietățile datelor de intrare. Cazul cel mai favorabil (CCMF) furnizează o margine inferioară a timpului de execuție. Acest caz e mai puțin util în analiza eficienței algoritmilor însă permite identificarea algoritmilor ineficienți – acei algoritmi care au un timp de execuție mare și în cel mai favorabil caz. Cazul cel mai defavorabil (CCMD) reprezintă cel mai mare timp de execuție furnizînd limita superioară pentru acesta. În analiza algoritmilor, marginea superioară este mai importantă decât marginea inferioară. În practică cazurile extreme (CCMF și CCMD) se întălnesc rar, astfel că analiza acestor cazuri nu furnizează suficientă informație despre algoritm. Cazul mediu (CM) se bazează pe cunoașterea distribuției de probabilitate a datelor de intrare, adică pe estimarea probabilității de apariție a fiecăreia din instanțele posibile ale datelor de intrare. Timpul mediu de execuție este valoarea medie (în sens statistic) a timpilor de execuție corespunzători diferitelor intanțe ale datelor de intrare. Timpul mediu de execuție reprezintă o valoare medie a timpilor de execuție calculată în raport cu distribuția de probabilitate a datelor de intrare. Stabilirea acestei distribuții de probabilitate presupune împărțirea mulțimii instanțelor posibile în clase astfel încât pentru instanțe din aceeași clasă numărul de operații efectuate să fie același. Datorită dificultăților ce pot interveni în stabilirea timpului mediu și datorită faptului că, de regulă, acesta diferă de timpul în cazul cel mai defavorabil doar prin valori ale constantelor implicate, de regulă analiza algoritmilor se rezumă la estimarea timpului de execuție pentru cazul cel mai defavorabil. Ipoteze de estimare pentru cazul mediu: -

Datele de intrare pot fi grupate în clase după timpii lor de execuție Există un număr finit de astfel de clase (m) 32

Etapele analizei algoritmilor

-

Probabilitatea de aparitie a unor date din clasa k este Pk Timpul de execuție al algoritmului pentru date de intrare aparținând clasei k este Tk(|x|)

În aceste ipoteze de calcul, timpul mediu de execuție este: Tmediu(|x|) = P1T1(|x|) + ... + PmTm(|x|) Dacă probabilitatea de apariție este aceeași pentru toate clasele (cazuri echiprobabile) atunci: Tmediu(|x|) =



1

∑1

5 31 |4|

Analiza algoritmilor nerecursivi Un algoritm poate fi recursiv sau nerecursiv. Nu este întotdeauna necesar să se contorizeze toate costurile instrucțiunilor unui algoritm pentru a se determina timpul de execuție. De regulă, este suficient să se estimeze doar operația dominantă – operația cu cel mai mare cost sau cea mai repetitivă. Analiza algoritmilor nerecursivi implică următorii pași: -

-

Se stabilește dimensiunea datelor de intrare Se identifică operația dominantă a algoritmului și numărul de execuții ale acesteia Se determină (în funcție de dimensiunea și de valorile datelor de intrare) cele 3 cazuri de analiză: CCMF, CCMD și CM. Dacă execuția operației dominante e diferită în aceste cazuri, atunci această operație este analizată separat Se determină expresia matematică a funcției ce însumează numărul de execuții ale operației dominante. Această expresie dă ordinul de complexitate al algoritmului

Exemplificare. Sortarea prin inserție Intrare: un vector de elemente x = v[1] ... v[n]

33

Etapele analizei algoritmilor

Ieșire: o permutare v[σ(1)], ..., v[σ(n)] astfel încât: v[σ(1)] < ... < v[σ(n)] Dimensiunea problemei: |x| = n Algoritm 1. for i ← 2,n do 2. key ← v[i] 3. j ← i-1 4. while((j>0)and(v[j]> key))do 5. v[j+1] ← v[j] 6. j ← j-1 7. endwhile 8. v[j+1] ← key 9. endfor

Timp execuție

Repetări

c1 + c2n+c3(n-1)

c4 c5 c6 c7 c8

1 n-1 n -1  ∑ 58 6 7 +1 ∑ 58 6 7 ∑ 58 6 7

c9

n-1

Să se considere pentru studiu de caz vectorul (8, 1, 4, 9, 2, 6) (8, 1, 4, 9, 2, 6) → (1, 8, 4, 9, 2, 6) → (1, 4, 8, 9, 2, 6) → (1, 4, 8, 9, 2, 6) → (1, 2, 4, 8, 9, 6) → (1, 2, 4, 6, 8, 9)

T(n) = c1 + c2n + c3(n-1) + c4(n-1) + c5(n-1) + c6∑ 58 6 7 + 1 + c7 ∑ 58 6 7 + c8 ∑ 58 6 7 + c9(n-1) CCMF: tabloul este sortat ⇒ δ(i)=0, i=2,  ⇒ T(n) = k1n + k2.

CCMD: tabloul este sortat în ordine inversă (descrescătoare) ⇒ δ(i)=i,

i=2,  ⇒ T(n) = c1 + c2n + (c3 + c4 + c5 + c6 + c9)(n-1) + (c6 + c7 +

c8)∑ 58 6 7 = c1 + c2n + k1(n-1) + k3:

  8

− 1>>>> 1, ) + probabilitatea ca elementul x să nu fie în tablou: Tmediu(|x|) = :1  + 2  … +  < + 1 − -  =  :1 − 8< + 8. Pentru p = ?

?

?

?

?

0.5 obținem Tmediu(|x|) = 3/4n + ¼.

Deci timpul mediu de execuție pentru algoritmul de căutare secvențială depinde liniar de dimensiunea datelor de intrare. Din formula timpului mediu putem să determinăm formulele pentru timpul de execuție în cazul în care elementul se află în tablou: p=1: 3@∈A[…] |4| =

+1 2

ceea ce se poate interpreta astfel: în cazul aparteneței elementului la vector, algoritmul parcurge în medie jumătate din vector. În cazul non-aparteneței elementului la vector (cazul cel mai defavorabil) avem p=0, ceea ce implică: 3@∉A[…] |4| = 3DDEF |4| = n

36

Etapele analizei algoritmilor

Etapele analizei algoritmilor Scopul principal al analizei eficienței algoritmilor este acela de a identifica modul în care timpul de execuție crește odata cu creșterea dimensiunii problemei. Pentru aceasta trebuie să se identifice: -

Ordinul de creștere al timpului de execuție Clasa de eficiență (complexitatea) algoritmului

În analiza ordinului de creștere trebuie să se identifice expresia termenului dominant. Definiție. Numim termen dominant, termenul din expresia ordinului de creștere care devine semnificativ mai mare când dimensiunea problemei crește. Astfel, el disctează comportamentul algoritmului, pe date de intrare de dimensiune mare. Exemple de expresii pentru timp de execuție (în bold este scris termenul dominant) -

T1(n) = an+b T2(n) = alogn+b T3(n) = an2 + bn + c T4(n) = an + bn + c

Ordinul de creștere Caracterizează creșterea termenului dominant din expresia timpului de execuție în raport cu dimensiunea problemei. Mai precis, ordinul de creștere cuantifică creșterea termenului dominant când dimensiunea problemei crește de k ori. Exemple: T1(n) = an ⇒ T1’(kn)= kan = kT1(n) – creștere liniară

Etapele analizei algoritmilor

T2(n) = alogn ⇒ T2’(kn) = alog(kn) = a(logk + logn) = alogk + T2(n) – creștere logaritmică T3(n) = an2 ⇒ T3’(kn) = a(kn)2 = ak2⋅ an2 = ak2T3(n) – creștere pătratică T4(n) = an ⇒ T4’(kn) = akn = (an)k = T4(n)k – creștere exponențială Prin intermediul ordinului de creștere putem compara doi algoritmi -

Compararea se realizează pe seturi de date de dimensiuni mari valori mari (analiza asimptotică) Algoritmul cu ordinul de creștere mai mic este mai eficient Pentru a compara ordinele de creștere a doi timpi de execuție

T1(n) și T2(n) se calculează lim→J

%K 

%L 

:

o Dacă lim = 0, T1(n) are ordinul de creștere mai mic decât T2(n) o Dacă lim = c, c>0 – contantă, T1(n) și T2(n) au același ordin de creștere o Dacă lim = ∞, T2(n) are ordinul de creștere mai mic decât T1(n)

Formule utile pentru determinarea ordinului de creștere ∑ 5 1 =  - complexitate liniară ∑ 5 7 =

  8

∑ 5 7 M =

∑ 5 = =

NOK M

- complexitate pătratică

- complexitate polinomială

M POK Q MQ

- complexitate exponențială

∑ 5  ± S = ∑ 5  ± ∑ 5 S

∑ 5 T = T ∑ 5 

∑ 5M 1 =  − = + 1

ln ∏M5 M = ∑M5 ln M

38

Etapele analizei algoritmilor

Exerciții Exercițiu 1. Considerăm problema calculării sumei primelor n numere naturale ∑ 5 7 . Dimensiunea acestei probleme poate fi considerată n. Algoritm

1. 2. 3. 4. 5. 6. 7.

Timp execuție c1 c2 c3 c4 c5

suma ← 0 i ← 0 while (i < n) do i ← i+1 suma ← suma + i endwhile return suma

Repetări 1 1 n +1 n n

Obținem că T(|x|) = c1 + c2 + (n-1)c3 + nc4 + nc5 = nk1 + k2 deci timpul de execuție depinde liniar de dimensiunea datelor de intrare, adică |x| = n. Exercițiu 2. Considerăm problema înmulțirii a două matrici A(m,n) și B(n, p). În acest caz |x| = (m, n, p).

1. 2. 3. 4. 5. 6. 7. 8.

Algoritm for i ← 1, m do for j ← 1, p do c[i,j] ← 0 for k ← 1, n do c[i,j]←c[i,j]+ a[i,k]*b[k,j] endfor endfor endfor

Timp execuție c1 + (m+1)c2 + mc3 c4 + (p+1)c5 + pc6 c7 c8 + (p+1)c9 + pc10 c5

Repetări 1 m mp mp mpn

Se poate lesne verifica că T(|x|) = mnpk1 + mpk2 + mk3 + k4. Exercițiu 3. Considerăm problema determinării valorii minime dintr-un vector de n elemente. Dimensiunea problemei este dată de numărul de elemente din vector, |x| = n. 39

Etapele analizei algoritmilor

1. 2. 3. 4. 5. 6. 7.

Algoritm min ← vect[0] for i ← 1, n-1 do if (min > vect[i]) then min ← vect[i] endif endfor return min

Timp execuție c1 c2 + nc3 + (n-1)c4 c5 c6

Repetări 1 1 n-1 δ(n)

Spre deosebire de cazurile anterioare, timpul de execuție al acestui algoritm nu poate fi stabilit cu certitudine, el depinzînd de valorile tabloului de intrare. Cazul cel mai favorabil este atunci când minumul se află pe prima poziție in vector. În acest caz intrucțiunea 4. nu se va mai executa și avem δ(n) = 0. Cazul cel mai defavorabil este când minimul se află pe ultima poziție în tablou. În acest caz δ(n) = n-1. În ambele cazuri, atât limita inferioară cît și limita superioară depind liniar de dimensiunea problemei, deci T(|x|) = k1n + k2. Exercițiu 4. Să se definească un algoritm care stabileste dacă un vector are numai elemente distincte. Algoritm 1. i ← 1 2. j ← 2 3. gasit ← false 4. while (iv[j]) then 4. v[i] ↔ v[j] 5. endif 6. endfor 7. endfor

Timp execuție k1 k2 c3 k4

Repetări ∑Q

5  ∑Q

5 

n-1 − 7 + 1 − 7 + 1 δ(n)

Operația dominantă este compararea de la linia 3). Deci, ordinul de Q creștere este ∑Q

5  − 7 + 1 TX = c3 ∑ 5  − 7 − 1 = c3 [(n-2) + (n-3) + ... + (n-n+1)] = c3[ (n-2)(n-1)/2] - creștere pătratică

42

Notații asimptotice

Notații asimptotice În general, se utilizează analiza asimptotică atunci când se caută să se evalueze comparativ mai mulți algoritmi, urmărindu-se astfel gruparea algoritmilor în clase în funcție de ordinul de creștere al timpului de execuție. Acest tip de analiză a fost definită pentru: -

-

analiza algoritmilor pentru seturi de intrare de dimensiuni mari, fără a se lua în calcul eventualele constante ce intervin în expresiile detaliate ale timpilor de execuție. estimarea timpului de execuție atunci când dimensiunea datelor de intrare crește nelimitat

Figura 2 Analiza asimptotică a algoritmilor

Astfel, un algoritm care este considerat asimptotic mai eficient este o alegere bună și în cazul seturilor de date de dimensiune mică cât și pentru date de dimensiuni mari. Pentru formalizarea acestei analize s-au definit un set de clase de funcții și notații asociate.

Notații asimptotice

Notația O Considerăm un algoritm și o funcție t: N → R+2 astfel încât o implementare a algoritmului să necesite t(n) unități de timp pentru a executa algoritmul pentru o instanță de dimensiune n. Așa cum spune Principiul invariației, orice implementare a algoritmului va necesita un timp în ordinul lui t. Definiție. Fie f: N → R+ o funcție oarecare. Definim O(f) astfel:

O(f(n)) = "Y: [ → \ ; ∃T ∈ \ , W ∈ [ . î. ∀ ≥ W : Y  ≤ Td  }

Citim O(f) ca ordinul lui f aceasta fiind mulțimea tuturor funcțiilor g mărginite superior de un multiplu real pozitiv (c) pentru valori ale argumentului suficient de mari (n ≥ n0). Prin această notație spunem că funcțiile g cresc la fel de repede sau strict mai lent decât funcția f. Scriem că g este în ordinul lui f sau g este în O(f) astfel: g ∈ O(f) sau g(n) ∈ O(f(n)), pentru n≥ n0. Intuitiv, faptul că g(n) ∈ O(f(n)) înseamnă că g(n) crește asimptotic cel mult la fel de repede ca f(n). Această clasă de funcții permite descrierea algoritmilor în cazul cel mai defavorabil. Observație. O condiție suficientă ca o funcție f să dea o comportare asimptotică pentru o funcție g constă în existența unei constante n0 a.î. ∀n ≥ n0 și f(n) >0 să obținem că există lim→J   și că aceasta este finită e 

(pozitivă, nu neapărat nenulă).

Aceasta condiție nu este însă și necesară. De exemplu, să considerăm g(n) = sin(n). Avem |g(n)| = |sin(n)| ≤ 1. Pentru n0 = 0 și c=1, f(n)=1 obținem g(n) ≤ cf(n), deci g ∈ O(1) dar lim→J

fgh  

nu există.

Convenim să vorbim despre ordinul lui f chiar și atunci cînd valoarea lui f(n) este negativă sau nedefinită pentru anumite valori n < n0. De 2

*

Prin N notăm mulțimea numerelor naturale, N= {0, 1, 2, ...} și N mulțimea numerelor * naturale strict pozitive, N = {1, 2, ...}, R+ notăm mulțimea numerelor reale pozitive și * R + mulțimea numerelor reale strict pozitive

44

Notații asimptotice

exemplu, vom vorbi despre ordinul lui n=1 funcția nu este definită.



ie

chiar dacă în punctele n=0 și

Pentru un algoritm care necesită t(n) unități de timp, spunem că timpul de timpul de execuție este în ordinul lui f dacă t(n) ∈ O(f(n)). În general se caută să se gasească cea mai simplă funcție f(n) a. î. t(n) ∈O(f(n)). Pentru a demonstra că g ∉ O(f) trebuie găsit pentru ∀c ∈ R+ , n0 ∈ N a. î. ∀n ≥ n0: g(n) > cf(n) Notația asimptotică definește o relație de ordine partială între funcții și deci, între eficiența relativă a diferiților algoritmi care rezolvă o aceeași problemă.

Figura 3 Reprezentarea grafică pentru g(n) ∈ O(f(n))

Interpretarea algebrică a notației asimptotice Pentru oricare f, g: N → R+ se definește relația binară f ≤ g dacă O(f) ⊆ O(g). Relația “≤” este o relație de ordine parțială pe mulțimea funcțiilor definite pe N cu valori in R+. Similar se definește relația de echivalență f = g dacă O(f) = O(g).

45

Notații asimptotice

De exemplu, avem log n = lg n = ln n deoarece O(log n) = O(lg n) = O(ln n)3. Dacă notam cu O(k) – ordinul funcțiilor mărginite superior de o constantă avem următoarea ierarhie: O(k) ⊂ O(logn) ⊂ O(n) ⊂ O(n logn) ⊂ O(n2) ⊂ O(n3) ⊂ ... ⊂ O(nk) ⊂ ... ⊂ O(kn) ⊂ O(n!) ⊂ O(nn) ordin constant ⊂ ordin logaritmic ⊂ ordin liniar ⊂ ordin patratic ⊂ ordin cubic ⊂ ordin polinomial ⊂ ordin exponential ⊂ ordin factorial Această ierahizare corespunde unei clasificări a algoritmilor după performanța acestora. Astfel, un algoritm polinomial este întotdeauna preferat unuia exponențial. Se poate întămpla ca timpul de execuție al unui algoritm sa depindă simultan de mai mulți parametri. De exemplu, algoritmii care operează cu grafuri și care depind atât de numărul de vărfuri cât si de numărul de muchii ale structurii. În acest caz, pentru o funcție arbitrară f: N × N → R+ avem: O(f) = "Y: [ × [ → \ |∃T ∈ \ , ∃W , kW ∈ [ . î. ∀ ≥ W , ∀k ≥ kW : Y , k ≤ Td , k }

Notația O are următoarele proprietăți: 1) Dacă t(n) = aknk + ak-1nk-1 + ... + a1n + a0, ak >0 atunci t(n) ∈ O(np) pentru p ≥ k. 2) f(n) ∈ O(f(n)) – reflexivitate

3

Remember. Funcția logaritmică X Fie a >0 – un număr real pozitiv. Considerăm ecuația exponențială a = N. Această ecuație are o soluție unic determinată x = logaN. Deci logaritmul unui număr real pozitiv este exponentul la care trebuie ridicată baza pentru a obține numărul dat. log 10 N = lg N – logaritm zecimal loge N = ln N – logaritm natural (folosit în rezolvarea unor probleme de fizică, e = 2,71 – numărul lui Euler)

46

Notații asimptotice

3) dacă f(n) ∈ O(h(n)) și h(n) ∈ O(g(n)) atunci f(n) ∈ O(g(n)) – tranzitivitate 4) O(f(n) + g(n)) = O(max(f(n), g(n))) Dem. Fie c1 ∈ R+ a.î. f(n) ≤ c1 t1(n), ∀n ≥ n1 și c2 ∈ R+ a.î. g(n) ≤ c2 t2(n), ∀n ≥ n2. Dacă luăm c = max(c1, c2) și n0 = max(n1, n2) ⇒ ∀n ≥ n0, f(n) + g(n) ≤ c1 t1(n) + c2 t2(n) ≤ c( t1(n) + t2(n)) ≤ c×2×max(t1(n), t2(n)) ∈ O(max(f(n), g(n))). 5) Θ(f(n)) ⊂ O(f(n)) –nu e obligatoriu ca orice limită superioară să fie și limită inferioară

Notația Ω Notația O(f) este folosită pentru a nota superior timpul necesar unui algoritm, măsurând eficiența respectivului algoritm. Uneori este util să estimăm și limita inferioară a acestui timp: Ω(f) = "Y: [ → \ |∃T ∈ \ , ∃W ∈ [ . î. ∀ ≥ W : Y  ≥ Td  }

Intuitiv, faptul că g(n) ∈ Ω(f(n)) înseamnă că g(n) crește asimptotic cel e 

puțin la fel de repede ca f(n), adică lim→J   este strict pozitivă dar nu neapărat finită.

Observăm că pentru două funcții oarecare f, g: N → R+ avem f ∈ O(g) dacă și numai dacă g ∈ Ω(f).

47

Notații asimptotice

g(n) cf(n)

n0 Figura 4 Reprezentarea grafică pentru g(n) ∈ Ω(f(n))

Notația Ω are următoarele proprietăți: 1) Dacă t(n) = aknk + ak-1nk-1 + ... + a1n + a0, ak >0 atunci t(n) ∈ Θ(np), p ≤ k 2) f(n) ∈ Ω(f(n)) - reflexivitate 3) dacă f(n) ∈ Ω(h(n)) și h(n) ∈ Ω(g(n)) atunci f(n) ∈ Ω(g(n)) 4) Ω(f(n)+g(n)) = Ω(max(f(n), g(n))) 5) Θ(f(n)) ⊂ Ω(f(n)) 6) dacă f(n) ∈ O(g(n)) atunci g(n) ∈ Ω(f(n)) și reciproc O situație fericită este atunci când timpul de execuție este limitat atât superior cât și inferior de un multiplu real și pozitiv al aceleiași funcții, așa cum se va defini în secțiunea următoare ordinul exact al unei funcții Θ(f).

Notația Θ În general este dificil să se determine expresia ce definește timpul de execuție al unui algoritm în funcție de dimensiunea datelor de intrare. De aceea, o metodă de estimare a eficienței algoritmilor constă în determinarea limitelor între care timpul de execuție poate varia.

48

Notații asimptotice

Definiție. Pentru o funcție g: N → R+, Θ(f) reprezintă mulțimea de funcții:

Θ(f(n)) = "Y: [ → \ ; ∃T , T8 ∈ \ , W ∈ [ . î. 0 < T d  ≤ Y  ≤ T8 d  , ∀ ≥ W }

Figura 5 Reprezentarea grafică pentru g(n) ∈ Θ(f(n))

Observăm că avem:

Θ(f) = O(f) ∩ Ω (f) O altă remarcă relativă la notația O și Θ este următoarea: pentru f, g : N → R+ dacă O(f) = O(g) atunci Θ(f) = Θ(g). Despre timpul de execuție al unui algoritm t(n) se spune că este de ordin Θ(f(n)) dacă t(n) ∈ Θ(f(n)). Din punct de vedere intuitiv, faptul că t(n) ∈ Θ(f(n)) înseamnă că t(n) și f(n) sunt asimptotic echivalente, adică au același ordin de creștere. Altfel spus: n  == →J d  lim

unde k este o constantă pozitivă.

49

Notații asimptotice

Notația Θ are următoarele proprietăți: 1) Dacă t(n) = aknk + ak-1nk-1 + ... + a1n + a0, ak >0 atunci t(n) ∈ Θ(nk) Dem. Într-adevăr, din lim→J

n0(ε) a.î. p

o  N

o  N

= M rezultă că ∃ε ∈ R+ și

− M p < q, ∀n> n0(ε) => M − q ≤

o  N

≤ M + q,

∀n> n0(ε). Deci pentru c1 = ak - ε, c2 = ak + ε, n0 = n0(ε) => t(n) ∈ Θ(nk). 2) Θ(logan) = Θ(logbn) oricare ar fi a, b ∈ R+, a, b ≠1 Dem. Proprietatea rezultă din formula Yr  = s și din Θ(k ie r ie  s

3) 4)

5) 6)

f(n)) = Θ(f(n)). Această proprietate sugerează faptul că în analiza eficienței algoritmilor nu contează baza logaritmului, motiv pentru care, de obicei, logaritmul se specifică prin lg fără a mai face referire la baza logaritmului (de obicei se consideră a fi 2). f(n) ∈ Θ(f(n)) – reflexivitate dacă f(n) ∈ Θ(g(n)) atunci g(n) ∈ Θ(f(n)) – simetrie Proprietățile 3) și 4) sugerează că notația Θ permite definirea unor clase de echivalență: f(n) și g(n) sunt echivalente dacă f(n) ∈ Θ(g(n)). Clasele de echivalență corespunzătoare se numesc clase de complexitate. dacă f(n) ∈ Θ(h(n)), h(n) ∈ Θ(g(n)) atunci f(n) ∈ Θ(g(n)) – tranzitivitate Θ(f(n) + g(n)) = Θ(max(f(n), g(n))

Notația Θ se folosește atunci când se poate determina explicit expresia timpului de execuție pentru un set de algoritmi diferiți sau când algoritmii analizați au același ordin de creștere în cazuri extreme. Sumarizăm: -

Dacă g(n) ∈ O(f(n)) înseamnă că pentru valori mari ale setului de date de intrare cf(n) este o limită superioară pentru g(n) ceea ce implică faptul că algoritmul se va comporta mai bine decât această limită în marea majoritate a cazurilor. 50

Notații asimptotice

-

-

Dacă g(n) ∈ Ω(f(n)) înseamnă că pentru valori mari ale setului de date de intrare cf(n) este o limită inferioară pentru g(n) ceea ce implică faptul că algoritmul se va comporta mai rău decât această limită în marea majoritate a cazurilor. Dacă g(n) ∈ Θ(f(n)) înseamnă că pentru valori mari ale setului de date de intrare c1f(n) este limita inferioară pentru g(n) iar c2f(n) este limita superioară – algoritmul tinde să se comporte cam ca f(n)

Proprietăți ale notațiilor asimptotice de complexitate: 1) Tranzitivitate f(n) ∈ O(h(n)), h(n) ∈ O(g(n)) ⇒ f(n) ∈ O(g(n)) f(n) ∈ Ω(h(n)), h(n) ∈ Ω(g(n)) ⇒ f(n) ∈ Ω(g(n)) f(n) ∈ Θ(h(n)), h(n) ∈ Θ (g(n)) ⇒ f(n) ∈ Θ (g(n)) 2) Reflexivitate f(n) ∈ O(f(n)) f(n) ∈ Ω(f(n)) f(n) ∈ Θ(f(n)) 3) Simetria f(n) ∈ Θ(g(n)) atunci g(n) ∈ Θ(f(n)) 4) Antisimetria f(n) ∈ O(g(n)) atunci g(n) ∈ Ω(f(n)) 5) Altele f(n) ∈ Θ(g(n)) dacă și numai dacă f(n) ∈ O(g(n)) și f(n) ∈ Ω(g(n))

51

Notații asimptotice

Analiza asimptotică a principalelor structuri de prelucrare Considerăm problema dterminării ordinului de complexitate în cazul cel mai defavorabil pentru următoarele structuri algoritmice: secvențială, alternativă, repetitivă. Presupunem că avem o structura secvențială construită din prelucrările P1, ..., Pk și fiecare are ordinul de complexitate O(fi(n)). Atunci ordinul de complexitate al algoritmului este O(f1(n) + ... + fk(n)) = O(max(f1(n), ..., fk(n)). Dacă evaluarea condiției unei structuri alternative are cost constant iar prelucrările celor două variante au ordinele de complexitate O(f1(n)) și O(f2(n)) atunci costul structurii alternative ar fi O(max(f1(n), f2(n)). În cazul unei structuri repetitive, pentru a determina costul de complexitate în cazul cel mai defavorabil se consideră numărul maxim de iterații. Dacă acesta este n iar dacă în corpul ciclului prelucrările sunt de ordin constant, atunci se obține ordinul O(n). În cazul ciclului dublu, dacă atât pentru ciclul interior cât și pentru ciclul exterior limitele variază între 1 și n atunci se obține de regulă o complexitate pătratică O(n2). Dacă însă, limitele ciclului interior se modifică atunci este posibil să se obțină alt ordin. m ← 1 for i ←1, n do m ← 2*m for j← 1, m do //prelucrare de ordin O(1) endfor endfor

În acest caz n  = ∑ 5 2 + 1 ∈ t 2

Marea majoritate a algoritmilor se încadrează în una din următoarele clase de complexitate:

52

Notații asimptotice

-

-

clasă de complexitate unitară O(1) – exemple: operații aritmetice, căutare folosind tabelele de dispersie clasă de complexitate algoritmică O(lgn) – exemplu: algoritmul de căutare binară clasă de complexitate liniară O(n) – exemple: algoritm de căutare secvențială, suma unui șir clasă de complexitate liniară O(n lgn) – exemple: algoritmi de sortare rapidă, interclasare clasă de complexitate pătratică O(n2) – exemple: algoritmi de sortare neperformanți: sortare prin inserție, sortare prin metoda bulelor, parcurgeri de tablouri pătratice de ordin n clasă de complexitate cubică O(n3) – exemplu: algoritmul de înmulțire a două matrici de dimensiune n clasă de complexitate exponențială O(2n) – exemplu: algoritmi de prelucrare a tuturor submulțimilor unei mulțimi de n elemente clasă de complexitate factorială O(n!) – exemplu: generarea tuturor permutărilor unei mulțimi de n elemente

În ierarhizarea claselor după ordinul de complexitate sunt utile următoarele limite: lim→J

ie s N

=0, lim→J

N

uP

=0, lim→J

uP

P

=0, lim→J

Metode generale de calcul pentru indicatorii de complexitate

uP !

=0

Pentru calculul funcţiei caracteristice şi încadrarea acesteia într-o clasă de complexitate se folosesc următoarele proprietăți de bază ale notațiilor asimptotice: - Compunerea -

-

dacă algoritmul este compus din două secvențe cu timpii de execuție caracterizați de funcțiile f(n) și g(n) atunci algoritmul va avea ordinul max(f +g); Θ(f + g) = Θ(max(f, g)) dacă un algoritm apelează o secvență de ordin f(n) de k ori, atunci algoritmul va avea tot ordinul f(n): Θ(k f(n)) = Θ(f(n))

53

Notații asimptotice

-

dacă un algoritm apelează o secvență de ordin f(n) într-un ciclu care se execută de g(n) ori, atunci algoritmul va avea ordinul Θ(f(n)g(n))

Exemple de limite pentru determinarea aparteneței la o clasă: -

dacă lim→J e  = 0 atunci f(n)=o(g(n)), adică f(n) = O(g(n)) și  

dacă lim→J

f(n) ≠ Θ(g(n)) -

dacă lim→J

 

e    e 

f(n) ≠ Θ(g(n))

∈ \ atunci f(n) = Θ(g(n))

= ∞ atunci f(n)=ω(g(n)), adică f(n)∈Ω(g(n)) și

Există o serie de proprietăți (se pot demonstra cu ajutorul limitelor): -

complexitatea funcțiilor polinomiale: dacă d  = ∑ 5W  4

atunci f(n) = Θ(xn) pentru orice constante a, b > 0, (n+ a)k = Θ(nk) pentru orice constantă reală a >1, dacă f(n) = Θ(g(n)) atunci af(n) = aΘ(g(n)) proprietatea de liniaritate a seriilor: ∑M5 Θxd = y = Θ ∑M5 d =

dacă Θ(f) = Θ(g) atunci Θ(ln f) = Θ(ln g)

54

Notații asimptotice

Exerciții 1. Să considerăm f(n) = 10n și g(n)=n2. Să se determine ordinele celor două funcții. n 1 2 3 ... 9 10 11 12

f(n) 10 20 30 ... 90 100 110 120

g(n) 1 4 9 ... 81 100 121 144

Se poate deci observa că ∀n ≤10 f(n) ≥ g(n) însă pentru n >10 f(n) < g(n). Obținem că pentru n0=10 și c=1 f(n) ≤ cg(n), deci f(n) ∈ O(g(n)) deci f= O(n2). Sau pentru c=10 și n0=1, ∀n ≥ n0 avem f(n) ≤ cg(n). 2. Verificați relația f(n)= n2 + 5nlgn + 10 ∈ O(n2). 3. Fie f, g: N → R+ cu f(n) = 6n3+14n2-8n+4 și g(n) = 2n3. Să se determine ordinele celor două funcții. Avem f(n) = 6n3+14n2-8n+4 ≤ 6n3+14n3+ 8n3 +4n3 = 32n3. Deci, pentru c=16 și n0=1 avem ∀n ≥ n0 avem f(n) ≤ cg(n), deci f = O(2n3). Avem g(n) = 2n3 ≤ 6n3 ≤ 6n3+14n2-8n+4 și obținem, pentru n0=1, că ∀n ≥ n0 avem g(n) ≤ f(n) deci O(g) = O(f) și anume g = O(2n3). 4. Verificați că f(n) = 3n2 + ∈ O(n2). 5. Demonstrați că următoarea afirmație nu este corectă f(n) = 3n ∈ O(2n). 6. Pentru n – număr natural nenul, fie: f(n) = 1+ 2+ ... + n, deci f(n) = ∈ O(n2) și f(n) ∉ O(n).

  8

55

. Verificați prin inducție că f(n)

Notații asimptotice

g(n) = 12 + 22 + ... + n2, deci g(n) = inducție că g ∈ O(n3)

  8

h(n) = 13 + 23 + ... + n3, deci h(n) = { că h ∈O(n4). i(n) = ∑ 5 4 =

@ POK Q @Q

z

. Verificați prin

  8 8

| . Verificați prin inducție

. Verificați prin inducție că i ∈Θ (xn), x>1

56

Analiza complexității algoritmi recursivi

Analiza complexității algoritmilor recursivi În cazul algoritmilor recursivi, principiile de analiză au în vedere următoarele aspecte: -

-

Stabilirea dimensiunii datelor de intrare Identificarea operației dominante și a numărului de execuții ale acestei operații. Dacă acest număr depinde de setul de date intrare (dimensiune sau valori) se tratatează separat cele 3 cazuri: CCMF, CCMD și CM Inițializarea relației de recursie pe anumite condiții inițiale și identificarea expresiei relației de recursie pentru operația dominantă. În general, determinarea formulei relației de recurență se obține folosind metoda de substituție forward si backward.

Algoritmii recursivi sunt ușor de implementat însă execuția lor conduce la costuri suplimentare. La fiecare apel recursiv se plasează o serie de informații într-o zonă de memorie special destinată, numită stiva programului. Exemplificare. Calculul factorialului unui număr. function fact(n) if (n 1 n  = ~ 2 1,  = 1

și se poate demonstra folosind metoda substituției că t(n)= O(log n) Într-adevăr, pentru n=2 t(2) = t(1)=1 ≤ clog 2= O(log 2), c ≥1.

Presupunem că avem n ⁄2 = t log ⁄2 și demonstrăm proprietatea pentru t(n).

n  = n ⁄2 ≤ T log 8 ⁄2 = T log  + log 2Q = T log  − T T log  pentru n0 = 2 și c ≥ 1.

≤

Metoda Iterației Această metodă transformă recursia într-o sumă și se bazează pe folosirea tehnicilor de mărginire a sumelor. Conversia recurenței în sumă se face prin expandarea recursiei și exprimarea ei ca o sumă de termeni dependenți numai de n și de condițiile inițiale. Pentru exemplificare vom considera algoritmul mergesort, care este un algoritm de sortare prin interclasare ce folosește strategia Divide et impera, după cum urmează: -

împarte vectorul în două jumătăți (divide) sortează fiecare jumătate folosind metoda sortării prin interclasare (impera) combina cei doi vectori într-un vector de dimensiune dublă 61

Analiza complexității algoritmi recursivi function mergesort(start, finish) if (start < finish) then mij ← (start+finish)/2 mergesort(start, mij) mergesort(mij+1, finish) merge(start, mij, finish) endif endfunction function merge(start, mij, finish) for i← start, finish temp[i] ← vect[i] i ← start; k ← start; j ← mij+1 while (i ≤ mij) and (j ≤ finish) do if (temp[i] ≤ temp[j]) then vect[k++] ← temp[i] else vect[k++] ← temp[j] endif endwhile while (i ≤ mij) vect[k++] ← temp[i++] endwhile while (j ≤ finish) vect[k++] ← temp[j++] endwhile endfunction

Costul nerecursiv al algoritmului este dat de funcția merge care are ordinul Θ(n) ⇒ f(n) = Θ(n). Costul recursiv este dat de funcția mergesort care include 2 apeluri recursive de dimensiune n/2. Relația de recurență devine: t(n) = 2t(n/2) + f(n) = 2t(n/2) + Θ(n) Să determinăm ordinul de complexitate folosind metoda iterativă: t(1) = Θ(1) – vectorul este deja sortat

62

Analiza complexității algoritmi recursivi

2W n :

    W < = 2 n : < + 2 Θ

2W 2 2W

28 n :

   < = 2X n : X < + 28 Θ 8 8 2 2 2

   2 n :  < = 28 n : 8 < + 2 Θ  2 2 2 ....

2M n :

   M M < = 2 n : < + 2 Θ

2M 2M 2M

Recurența se termină în momentul în care ajungem la Θ(1) deci când  =1, deci k= logn. 8N t(n) = ∑M5WL 2M Θ N = ∑M5WL Θ  = Θ  1 + log 8  8 ƒ„… 



ƒ„… 

Arbori de recurență Aceste reprezentări au următoarele semnificații: -

un nivel în arbore reprezintă un nivel de recursivitate un nod reprezintă un apel recursiv pentru fiecare nivel de recursiviate este indicat și costul nerecursiv al acelui nivel pentru fiecare nod este indicat costul nerecursiv al apelului

Pentru recursia algoritmului mergesort are un arbore cu log2n nivele, nodul rădăcină având un cost Θ(n). t(n) = Θ(n)(1 + logn) = Θ(n + nlogn) = Θ(nlogn)

63

Analiza complexității algoritmi recursivi

t(n)

(n/2)

t(n/2)

(n)

t(n/2)

(n/2) log2n + 1 nivele

(n/4)

t(1)

t(n/4)

t(n/4)

t(n/4)

(n/4)

t(1)

t(1)

(1)

(1)

t(n/4)

(1)

(n/4)

t(1) (1)

Figure 2 Arborele de recurență pentru algoritmul mergesort

Metoda Master Metoda Master oferă o soluție directă pentru relații de recurență de tipul: t(n) = at(n/b) + f(n), n ≥ k, k - o constantă pozitivă unde f(n) este o funcție asimptotic pozitivă iar t(n) o funcție nenegativă. Teorema Master stabilește dacă f(n) = Θ(nk) atunci t(n) poate fi mărginită asimptotic astfel: -

t(n) = Θ(nk) dacă a < bk t(n) = Θ(nk) dacă a = b

t(n) = Θ(ƒ„…s r 4) dacă a > bk

4

Remember! m log2m 1 0 2 1 4 2 8 3 16 4 32 5 64 6 128 7 256 8

64

Analiza complexității algoritmi recursivi

Aceste recurențe caracterizează timpul de execuție al unui algoritm Divide et impera care împarte problema în a subprobleme de dimensiune n/b pe care le rezolvă recursiv, constul necesar divizării problemei și recombinării soluției fiind f(n). Exemplu: să considerăm t(n) = 4t(n/2) + n. Conform notațiilor din teorema Master avem a = 4 și b =2 și pentru k=1 obținem f(n) = n = Θ(nk) deci t(n) = Θ(ƒ„…L ‡ ) = Θ(n2).

Tehnica reducerii Această tehnică folosește legătura între soluția unei probleme și soluția aceleiași probleme dar pentru o instanță de dimensiune mai mică. Pentru unele probleme această abordare conduce la obținerea unor algoritmi mai eficienți deoarece, uneori, este mai simplu să se specifice relația dintre soluția problemei de rezolvat și soluția unei probleme de dimensiune mai mică decât să se specifice explicit modul de calcul al soluției. Exemplu. Să considerăm problema calculării valorii expresiei xn, pentru n=2m, m ≥ 1. 48 =  ˆ

4

4 ∙ 4, k = 1  ˆŠK ∙ 48 , k > 1

8ˆŠK

Obținem că 4 8 poate fi calculat după următoarea schemă: ˆ

pentru m=1, x2 = 4 8 ∙ 4 8 ‹

‹

pentru m=2, 4 8 = 4 8 ∙ 4 8 L

K

K

pentru m=3, 4 8 = 4 8 ∙ 4 8 Œ

L

L

Funcția care implementează formula de mai sus, power2 folosește un mecanism de calcul ascendent, în sensul că pornește de la problema de dimensiune mai mică către problema de dimensiune mai mare. function power2(x, m) p ← x ⋅ x 65

Analiza complexității algoritmi recursivi

for i ← 1, m-1 do p ← p ⋅ p endfor return p endfunction Eficiența acestei tehnici: dacă dimensiunea problemei este n = 2m atunci t(m)=m adică t(n)=lg n. O altă variantă pentru aceeași tehnică dar cu o abordarea de sus în jos în care dimensiunea scade cu o unitate este următoarea: function power3(x, m) if (m=1) then return x ⋅ x else p ← power3(x, m-1) return p ⋅ p endif endfunction Să considerăm acum următoarea formulă pentru calcularea puterii lui xn, n număr par. 4 ∙ 4,  = 2  4 =    48 ∙ 48,  > 2 Se observă că în acest caz dimensiunea problemei descrește prin împărțire la 2: function power4(x, m) if (n=2) then return x ⋅ x else p ← power4(x, n div 2) return p ⋅ p endif endfunction 66

Analiza complexității algoritmi recursivi

Algoritmii de mai sus power3 și power4 au o abordare descendentă pornind de la problema de dimensiune inițială și reducând succesiv dimensiunea până când se ajunge la o problemă suficient de simplă. Așa cum se poate observa ambii algoritmi sunt recursivi. Tehnica reducerii poate fi extinsă și în cazul unui exponent n cu valoare naturală arbitrară: 4 ∙ 4,  = 2

4  = Ž 4 8 ∙ 4 8 ,  > 2,  − k -  

4

p



Q p 8

∙4

p

Q p 8

∙ 4,  > 2,  − k 7k-

Funcția corespunzătoare acestei formule este: function power5(x, n) if (n=1) then return x else if (n=2) then return x ⋅ x else p ← power5(x, n div 2) if (n mod 2=0) then return p ⋅ p else return p ⋅ p ⋅ x endif endif endif endfunction În cazul algoritmilor recursivi, pentru estimarea timpului de execuție se caută relația de recurență care exprimă legătura dintre timpul de execuție corespunzător problemei inițiale și timpul de execuție corespunzător problemei reduse. Estimarea timpului de execuție se obține prin rezolvarea relației de recurență: Pentru calculul lui n! după formula: 1,  = 1  ! =   ∙  − 1 !,  > 1 67

Analiza complexității algoritmi recursivi

0,  = 1  n  − 1 + 1,  > 1 Formula de recurență pentru algoritmul power3(x, m) este: t(2m) = t(2m-1) + 1 Aplicând metoda substituției înapoi avem: t(2m) = t(2m-1) + 1 t(2m-1) = t(2m-2) + 1 ... t(2) = 1 ________________ t(2m) = m = lg n avem următoarea recurență:

n  = 

Formula de recurență pentru algoritmul power4(x, n) este: 1,  = 2  n  =  2n /2 + 1,  > 2 Aplicând metoda substituției înapoi avem: t(n) = 2t(n/2) + 20 2t(n/2) = 22t(n/22) + 21 22t(n/22) = 23t(n/23) + 22 ... 2kt(n/2k-1) = 2kt(n/2k) + 2k-1 Pentru k = lg n avem t(n) = 2lg n + 1 + 2 + ... + 2lg n-1 deci t(n) = O(2ieL  ) = O(n).

Aplicație a tehnicii de reducere Generarea celor n! permutări ale mulțimii {1, 2, ..., n} Cele k! permutări ale mulțimii {1, 2, ... , k} pot fi obținute din cele (k-1)! permutări ale mulțimii {1, 2, ... , k-1} prin plasarea celui de-al k-lea element succesiv pe prima, pe a doua, ..., pe a k-a poziție în submulțimea de k-1 elemente. Plasarea elementului de pe poziția k pe poziția i se face prin interschimbarea elementului de pe poziția k cu elementul de pe poziția i.

68

Analiza complexității algoritmi recursivi

123 321

231

132

321 312

123

132 213

function permut(k) if (k=1) then write v[1...n] else for i ← 1,k do v[i] ↔ v[k] perumt(k-1) v[k] ↔ v[i] endfor endif endfunction Formula de recurență pentru acest algoritm este: 0, = = 1  n = =  = n = − 1 + 2 , = > 1

Aplicând metoda substituției înapoi obținem: t(k) = k(t(k-1) + 2) k⋅t(k-1) = k(k-1)(t(k-2) + 2) k⋅(k-1)t(k-2) = k(k-1)(k-2)(t(k-3)+2) .... k(k-1)⋅...⋅3t(2) = k(k-1)⋅...⋅2(t(1)+2) Și avem: t(k) = k! deci t(n)= O(n!)

69

123

Analiza complexității algoritmi recursivi

1) Demonstrați că t(n) = O(n) pentru: t(n) = 2n ⁄2 + 1. Presupunem t(n/2) = O(n/2) ⇒ ∃c >0 și n0 ∈ N a.î. t(n/2) ≤ c(n/2) Demonstrând pentru n obținem: t(n) ≤ 2c (n/2) + 1 = cn +1 care nu este în mod necesar mai mic decât cn Dacă însă luăm c, b >0 a.î. t(n/1) ≤ c(n/2) – b obținem t(n) ≤ 2c(n/2) – b = cn –b ≤ cn 2) Demonstrați că t(n) = O(logn log(logn)) pentru t(n) = 2n √ +logn. Luăm m = logn și avem: t(m) = 2t(m/2) + logm. Trebuie să demonstrăm că t(m) = O(m logm). t(m) ≤ 2cm/2 (log(m/2)) + logm = cm(logm + log2-1) + logm = cm logm – 2cm +logm = cm logm – 2c + logm ≤ cm logm + m, pentru c>1 3) Să se determine ordinul de creștere pentru problema Turnurilor din Hanoi care are un timp de execuție de forma:

Exerciții

n  = 

n  − 1 + 1 + n  − 1 ,  > 1 1,  = 1

Prin expandarea expresiei se obține:

t(n) = 2t(n-1) + 1 = 2(2t(n-2)+1) + 1 = 4t(n-1) + 2 + 1 = 4(2t(nn

1)+1) + 2 + 1 = 8t(n-1) + 4 + 2 + 1 = ... = ∑Q

5W 2 = 2 – 1

Obținem că t(n) = O(2n).

4) Considerăm algoritmul mergesort pentru care timpul de execuție este de forma: t(n) = 2t(n/2) + Θ(n) Să se demonstreze prin metoda substituției că ordinul de complexitate t(n) = Θ(n) (1 + logn) = Θ(n + n logn) Dem. Pentru n=1 avem t(1) = 1 = Θ(1). Presupunem adevărat pentru n/2 și vom avea ∃ c>0 și n >0 a.î. t(n/2) ≤ c(n/2 + n/2 log(n/2)) ⇒ 70

Analiza complexității algoritmi recursivi

t(n) ≤ cn + cn(log(n/2)) + Θ(n) = cn + cnlogn – cn + Θ(n) = cnlogn + Θ(n) = Θ(nlogn) + Θ(n) = Θ(n + nlogn) 5) Să se determine ordinul de complexitate prin metoda substituției pentru t(n) = t(n-1) + 1 cu t(0) = 0 – condiție inițială. Dem. Folosind substituția înapoi obținem: t(n-1) = t(n – 2) + 1 ⇒ t(n) = t(n-2) + 1 + 1 = t(n- 2) + 2 = t(n – 3) + 3 = ... = t(n – k) + k Pentru k = n ⇒ t(n) = t(0) + n = n ⇒ t(n) = Θ(n) 6) Să se determine ordinul de complexitate pentru relația de recurență: t(n) = 2t(n/2) + n, cu t(1) = 1.    t(n) = 2t(n/2) + n = 2[2t(n/4) + n/2] + n = 22t(8L ) + 218K + 8‹ 

8

t(n) = 2[2[2t( Π)+ Pentru



8N



8L





8

8



8

 8

] + ]+n = 23t( Π) + 22 L + 21 + n 

8

= 1 adică k = log2n obținem t( N) = t(1) = 1

Deci t(n) =

L M  ∑ƒ„… M5W 2 8N =

n(1 + log2n) = n + nlog2n

nlog2n) = Θ(nlog2n)

71

=

Θ( n +

Analiza algoritmilor. Studiu de caz

Algoritmi recursivi. Studiu de caz Problema Turnurilor din Hanoi Această problemă are o rezolvare suficient de simplă și de intuitivă pentru a permite analiza de complexitate și a demonstra corectitudinea algoritmului. O legendă Brahmană spune că, de la începutul lumii, există undeva 3 turnuri de fildeș. Pe unul dintre turnuri se afla inițial o stivă formată din 64 de discuri din aur cu diametre diferite, așezate în ordinea descrescătoare a diametrelor, de la baza turnului spre vârf. Preoții brahmani au sarcina de a deplasa stiva de discuri pe un alt turn astfe încât: -

doar un disc, și anume cel aflat în vârful unui turn poate fi deplasat la un moment dat pe alt turn orice disc trebuie să se sprijine pe baza unui turn sau pe un disc cu diametrul mai mare decât al lui

Lumea se va sfărși când preoții își vor termina treaba! Soluția este recursivă, fiind descrisă cu ajutorul unei funcții de 4 parametri: n – numărul de discuri, X, Y și Z – trei discuri generice. function hanoi(n, X, Y, Z) if (n ≥ 1) then hanoi(n-1, X, Z, Y) hanoi(1, X, Y, _) hanoi(n-1, Z, Y, X) endif endfunction

Analiza complexității algoritmi recursivi

Pentru hanoi(4, A, B, C) cele 15 deplasări efectuate de algoritm sunt listate mai jos: move disk from top of A on C move disk from top of A on B move disk from top of C on B move disk from top of A on C move disk from top of B on A move disk from top of B on C move disk from top of A on C move disk from top of A on B move disk from top of C on B move disk from top of C on A move disk from top of B on A move disk from top of C on B move disk from top of A on C move disk from top of A on B move disk from top of C on B Să calculăm complexitatea algoritmului, adică să determinăm numărul de discuri care se deplasează. Conform algoritmului, problema se poate descrie prin intermediul următoarei recurențe: move(n) = move(n-1) + 1 + move(n-1) = 2move(n-1) + 1 Să rezolvăm recursia folosind metoda substituției inainte: 73

Analiza complexității algoritmi recursivi

pentru n > 1: move(2) = 2move(1) + 1 = 3 move(3) = 2move(2) + 1 = 7 move(4) = 2move(3) + 1 = 15 ... Nu ajungem prea departe ... să încercam metoda substituției înapoi: move(n) = 2move(n-1) + 1 = 2[2move(n-2) + 1] + 1 = 22move(n-2) + 21 + 20 = 2[2[2move(n-3) + 1] + 1] + 1 = 23move(n-3) + 22 + 21 + 20 ......................................... = 2kmove(n-k) + 2k-1 + ... + 21 + 20 Pentru n – k = 1 obținem k = n – 1. Deci: move(n) = 2n-1move(1) + 2n-2 + ... + 21 + 20

n

= 2n-1 + 2n-2 + ... + 21 + 20 = ∑Q

5W 2 = 2 – 1

Prin inducție demonstrăm acum că move(n) = 2n – 1. Pentru n=1 avem move(1) = 1

Presupunem adevărată recurența pentru n-1 și o demostrăm pentru n. move(n) = 2move(n-1) + 1 = 2[2n-1 – 1] + 1 = 2n – 1 deci move(n) = Θ(2n – 1) = Θ(2n) Arborele de recursie corespunzător problemei Turnurilor din Hanoi este:

74

Analiza complexității algoritmi recursivi

Figure 3 Arborele de recursie pentru problema Turnurilor din Hanoi

75

NP-completitudine

NP-completitudine În analiza complexității, cel mai important aspect care interesează atât pe teoreticieni cât și pe cei care care implementează este acela de a stabili dacă, pentru o anumită problemă, există un algoritm polinomial care să o rezolve. Problemele rezolvabile în timp polinomial sunt probleme considerate „accesibile” și există macar trei argumente în favoarea acestei afirmații: •

•

•

În general gradul funcției polinomiale este un număr relativ mic, existând puține probleme al căror ordin de complexitate să fie Θ(nk) cu k ≥ 100. Pentru multe modele de calcul, o problemă care poate fi rezolvată în timp polinomial pe un anumit model de calcul, va putea fi rezolvata în timp polinomial pe orice alt model de calcul. Clasa problemelor polinomiale este închisă la operații de tipul adunare, înmulțire sau compunere. De exemplu, un algoritm care apelează de un număr constant de ori subprograme polinomiale este tot un algoritm cu ordin de complexitate polinomial.

În realitate, teoria NP-completitudinii este utilă chiar și atunci când produce rezultate negative: Atunci când imposibilul este eliminat, ceea ce rămâne, oricât de improbabil ar fi, este adevărul (Arthur Conan Doyle). Teoria NP-completitudinii permite concentrarea eforturilor într-o manieră productivă prin faptul că permite să se stabilească că există puține șanse pentru a găsi o soluție eficientă la o problemă dată. Cu alte cuvinte, atunci când nu reușește să demonstreze că o problemă e greu de rezolvat, atunci înseamnă că avem șanse de a găsi un algoritm eficient de rezolvare. Mai mult decât atât, teoria NP-completitudinii ne permite să identificăm care sunt caracteristicile care fac ca o problemă să fie dificilă. O problemă abstractă P se definește ca fiind o relație binară între mulțimea I a instanțelor problemei și mulțimea S a soluțiilor problemei. Teoria NP-completitudinii vizează numai problemele de decizie, și

NP-completitdine

anume problemele care au soluții de tipul da/nu. În această aserțiune, o problemă decizie este considerată ca fiind o funcție definită pe mulțimea I a instanțelor cu valori în mulțimea {da, nu}. Exemple de probleme de decizie: 1. Fiind dat un graf G = (V, N), există un drum în acest graf de lungime mai mică decât k? 2. Fiind dat un graf G = (V, N) se pot colora nodurile din V cu m culori astfel încât două noduri adiacente să nu aibe aceeași culoare? Din definiția problemelor de decizie observăm că ceea ce contează este doar existența soluției. Această restricție aplicată problemelor de decizie este justificată prin faptul că celelalte probleme care nu intră în categoria problemelor de decizie, ca de exemplu problemele de optimizare, pot fi ușor transformate în probleme de decizie. Rezolvarea problemelor de decizie constituie forma standard utilizată de teoria calculabilității. Deși marea majoritate a problemelor sunt probleme de optimizare, scopul teoriei complexității este de a clasifica problemele de decizie în funcție de dificultatea gradului lor de soluționare. Se poate arăta ca orice problemă de optimizare se poate transforma într-o problemă de decizie. În literatura de specialitate există mai multe categorii de complexitate. În cele ce urmează le vom aborda doar pe cele mai importante. Vom defini clasa de complexitate P ca fiind mulțimea problemelor de decizie care sunt rezolvabile în timp polinomial. Este așa-zisa clasă a problemelor ușoare.

Limbaje formale Rezolvarea problemelor de decizie poate profita de instrumentele oferite de teoria limbajelor formale. Vom recapitula în cele ce urmează câteva concepte ale limbajelor formale. Un alfabet Σ este o mulțime finită de simboluri. Un limbaj L peste Σ este orice mulțime de șiruri formate din 77

NP-completitdine

simbolurile mulțimii Σ. Simbolizăm șirul vid prin λ și limbajul vid prin ∅. Limbajul tututor șirurilor peste Σ se notează cu Σ*. Orice limbaj peste Σ este o submulțime a lui Σ*. Limbajele moștenesc operațiile din teoria mulțimilor, cum ar fi reuniuneai sau intersecția. Complementul unui limbaj, notat prin > se definește ca fiind Σ* \ L. Concatenarea a două limbaje L1 și L2 este limbajul: L = {ω1ω2: ω1 ∈ L1, ω2 ∈ L2} Închiderea sau steaua Kleene a unui limbal L este: L* = {λ} ∪ L ∪ L2 ∪ L3 ∪ ... unde Lk este limbajul L obținut prin concatenarea cu el însuși de k ori. Din punctul de vedere al teoriei limbajelor, o instanță a unei probleme P este un element din Σ*, cu Σ = {0, 1}. Datorită modului de definire al problemelor de decizie putem considera problema P ca fiind mulțimea instanțelor la care problema răspunde afirmativ, deci vom avea: L = {ω ∈ Σ*| P(ω) = da } Prin intermediul limbajelor formale putem exprima relații între problemele de decizie și algoritmii care îi rezolvă. Spunem că un algoritm A acceptă o intrare ω ∈ {0,1}* dacă ieșirea algoritmului corespunzătoarea intrării ω este da, A(ω) = da. Continuând, limbajul acceptat de un algoritm A este mulțimea instanțelor acceptate de algoritm: L = {ω ∈ {0,1}*| A(ω) = da} Analog, vom considera că un algoritm respinge un șir ω dacă A(ω) = nu. Un limbaj L este acceptat în timp polinomial de către un algoritm A dacă există o constantă k astfel încât pentru orice instanță ω de lungime n din L, algoritmul îl acceptă în O(nk). 78

NP-completitdine

Exemplu. Considerăm un graf G = (N, V). Se cere să se determine dacă există un drum între nodurile u, v ∈ N în graful G. Limbajul corespunzător acestei probleme se poate defini ca: L = {(G, u, v) | există un drum între nodurile u și v în graf} Limbajul L poate fi acceptat în timp polinomial de un algoritm care implementează o metodă de căutare a drumurilor într-un graf și returnează da dacă a fost găsit un astfel de drum și nu în caz contrar. Se poate defini drept clasă de complexitate mulțimea de limbaje pentru care apartenența unui element este determinată de o măsură a complexității algoritmului de testare a apartenenței. Astfel, folosind teoria limbajelor formale, putem da o definiție alternativă a clasei de complexitate P: P = {L ⊆ {0,1}*| există un algoritm care acceptă L în timp polinomial}

Verificări în timp polinomial Vom discuta în cele ce urmează despre algoritmi care “verifică” apartenența la diverse limbaje. Un algoritm de verificare se definește ca fiind un algoritm cu doi parametrii: • •

o intrare oarecare, ω o intrare probă, α

Un algoritm de verificare acceptă o intrare ω doar în baza unei probe α A(ω, α) = 1 și obținem că L este un limbaj verificat de un algoritm de verificare A dacă este mulțimea de intrări L = {ω ∈ {0.1}*| exista proba α ∈{0,1}* a.î. A(ω, α) = true} Obținem că un algoritm A verifică un limbaj L dacă pentru orice intrare ω ∈ {0,1}* există o probă α ∈ {0,1}* pe care A o poate folosi pentru a demonstra ω ∈ L.

79

NP-completitdine

Exemplu. Pentru un graf care conține un ciclu hamiltonian, lista vârfurilor din ciclu este proba necesară pentru a demonstra acestei proprietăți. Dacă un graf nu este hamiltonian, nu există nicio listă de vârfuri în baza căreia algoritmul să poată obține că acele vârfuri se află pe un ciclu hamiltonian.

Determinism Numim algoritm determinist o secvență finită de instrucțiuni în care fiecare operație are un rezultat unic determinat. Un algoritm determinist se bucură de asemenea de proprietatea de serialitate: la un moment dat, în timpul execuției se execută o singură acțiune. Algoritmii determiniști sunt algoritmii a căror evolutie este unic determinată în baza instrucțiunilor pe care le conțin. Mai precis, în fiecare moment al execuției, instrucțiunea care urmează să fie executată este unic determinată. Spre deosebire de aceștia, algoritmii nedeterminiști includ operații al căror rezultat nu este unic definit ca având valori într-o mulțime finită de posibilități. Un algoritm nedeterminist are o structura arborescentă de operații. Operațiile de pe o cale din arbore sunt efectuate secvențial iar cele de pe căi diferite sunt efectuate în paralel astfel că la un moment dat se pot executa mai multe acțiuni definite pe căi diferite. Algoritmii nedeterminiști nu sunt direct aplicabili însă studiul acestora aduce în discuție concepte foarte importante. Execuția unui algoritm nedeterminist implică alegeri nedeterministe. Un algoritm nedeterminist este considerat corect dacă există o posibilitate de execuție a sa care să determine soluția corectă. Exemplu de algoritm nedeterminist: algoritmul care caută ieșirea dintrun labirint. if not iesire(pozitie_curenta) if not perete(nord(pozitie_curenta)) then pozitie_curenta ← nord(pozitie_curenta)

80

NP-completitdine if not perete(est(pozitie_curenta)) then pozitie_curenta ← est(pozitie_curenta) if not perete(sud(pozitie_curenta)) then pozitie_curenta ← sud(pozitie_curenta) if not perete(vest(pozitie_curenta)) then pozitie_curenta ← vest(pozitie_curenta) endif endif

Comportamentul acestui algoritm nu se cunoaște a-priori (nu se știe dinainte drumul pe care îl va genera algoritmul în labirint). Însă acest algoritm reprezinta dovada că problema se poate rezolva algoritmic. Iar în virtutea faptului că orice algoritm nedeterminist se poate transforma în unul determinist, putem obține varianta deterministă a problemei în cauză. Pentru exemplul dat, transformarea ar înseamna generarea tuturor drumurilor posibile la fiecare pas al executiei. Operațiile caracteristice algoritmilor nedeterminiști sunt: -

choice(A) : ramifică copia curentă a algoritmului A în mai multe copii; copiile continuă în paralel și independent una de alta fail : copia curentă se termină cu eșec, restul copiilor (dacă mai există) continuă execuția succes : copia curentă se termină cu succes, celelalte copii sunt terminate

Valoarea de return al unui algoritm nedeterminist este succes când una din căi se termină cu succes sau fail când toate căile din arborele de operații eșuează. Complexitatea unui algoritm nedeterminist se definește ca suma tuturor operațiilor din secvența cea mai scurtă care determină algoritmul să se termine cu succes, iar în cazul în care toate căile se termină pe fail, 81

NP-completitdine

complexitatea algoritmului este suma complexității operațiilor de pe calea cea mai lungă. Observație: operația choice(A) se consideră a avea complexitatea O(1). Etapele construirii unui algoritm nedeterminist sunt următoarele: -

generare, care corespunde instrucțiunii choice ce are ca scop generarea de copii pentru fiecare candidat la soluție testare, care corespunde instrucțiunii ce testează dacă s-a obținut soluția corectă

Observație: caracteristica nedeterministă este dată de etapa de generare. Algoritmii de optim pot fi modelați ca apeluri succesive ale unor algoritmi de decizie. Exemplu: determinarea arborelui de acoperire minim pentru un arbore fără costuri pe muchii – există un astfel de arbore de o muchie? dacă nu, există un arbore de acoperire de 2 muchii? etc. Exemple de algoritmi nedeterminiști Cautarea unui element intr-un vector input: v[1...n], elem caut(v, elem) { i ← choice(1..n) // generare if (v[i]=elem) then return success // testare else return fail }

Testarea daca un numar natural este neprim input: n neprim(n) { i ← choice(2.. |sqrt(n)|) // generare

82

NP-completitdine if (n mod i=0) then return success // testare else return fail }

Sortarea unui vector de elemente strict pozitive input: v[1 ...n] sort(v, n) { for i ←1, n aux[i] ← 0 // in aux vom crea vectorul sortat for i ←1, n j ← choice(1..n) // generare if (aux[j]>0) then return fail // testare else aux[j] ← V[i] for i ←1, n-1 if (aux[i]>aux[i+1])then return fail // testare else return success // daca niciun test nu a // dat fail, success }

Clase de complexitate P și NP Termenul de NP-complexitate vine de la "timp polinomial nedeterminist". Această clasă cuprinde toate problemele de decizie cărora li se poate asocia un set de soluții posibile, fiecare soluție putând fi verificată dacă este sau nu o soluție potențială într-un timp polinomial. Mai precis, un limbaj L aparține clasei NP dacă și numai dacă există un algoritm A care verifică intrările lui L în timp polinomial:

83

NP-completitdine

L = {ω ∈ {0,1}* | exista proba α a.î. (A(ω, α) = da) ∈ O(|α|k)} pentru k o constantă. Teoria complexității se ocupă cu studiul clasificării problemelor și al granițelor existente între diferitele clase de probleme. Se analizează, de asemenea, resursele de calcul necesare pentru a rezolva o anumită problemă. Problematica centrală, cea mai cunoscută, a acestei teorii este întrebarea: P = ? NP Clasa de complexitate P este reprezentată de mulțimea tuturor problemelor de decizie care au complexitate polinomială. De exemplu, apartenența unui element la un vector are ordinul de complexitate O(n), unde n reprezinta numarul de elemente al vectorului, deci are complexitate polinomiala (mai precis, ordinul de complexitate este linear). O problemă este considerată problemă dificilă dacă complexitatea ei este exponenţială în raport cu dimensiunea instanțelor. O problemă este accesibilă dacă complexitatea ei se poate defini sub forma unui functii polinomiale, de un grad oricît de mare. Clasa tuturor problemelor care se pot rezolva cu algoritmi nedeterminişti într-un timp polinomial se notează cu NP (Nedeterminist Polinomial). Este evident că orice problemă care se află în P se află şi în NP: algoritmii determinişti sunt doar un caz extrem al celor nedeterminişti prin faptul ca în fiecare moment au o singură alegere posibilă. Însă transformarea într-un algoritm determinist se face de cele mai multe ori prin pierderea eficienței, generând algoritmi determiniști care au complexitate exponenţială. Avem deci o incluziune de mulţimi între problemele de decizie: P ⊆ NP ⊆ EXP. Știm cu certitudine că P ≠ EXP, însă nu avem nici o idee despre relaţia dintre clasele NP şi P sau dintre clasele NP şi EXP. Problema egalitatii P=NP este cea mai importantă problemă din teoria calculatoarelor, pentru că soluţionarea ei ar avea multe consecinţe importante. 84

NP-completitdine

În 1971 Cook a demonstrat că există o problemă specială în NP (clasa problemelor pentru care se poate da un algoritm eficient nedeterminist), numită problema satisfiabilităţii (notată cu SAT). Problema este foarte simplă: dacă se dă o formulă booleană care cuprinde mai multe variabile, poate fi formula făcută adevărată dând anumite valori variabilelor? De pildă formula (x1 ∧ x2) ∨ (x1 ∧ ¬x2) devine adevărată pentru x1=true şi x2 ∈ {true, false}. SAT este foarte importantă, pentru că Cook a demonstrat că dacă SAT poate fi rezolvată în P (adică folosind un algoritm determinist polinomial), atunci orice problemă din NP poate fi rezolvată în timp polinomial! Problema satisfiabilităţii booleene este considerata “cea mai grea problemă” din NP, pentru că rezolvarea oricărei alte probleme din NP se poate face ”mai repede'' decît a ei. Din această cauză SAT se mai numeşte problemă NP-completă. De la Cook încoace s-au mai descoperit câteva sute de probleme NPcomplete. Unele probleme care se ivesc foarte adesea în practică s-au dovedit NP-complete. Acesta este un alt motiv pentru care clasa abstractă a problemelor cu algoritmi nedeterminişti este atît de importantă: foarte multe probleme practice au algoritmi polinomiali nedeterminişti, dar cei mai buni algoritmi determinişti iau un timp exponenţial! Iată cîteva exemple de probleme NP-complete: 1) Problema comis-voiajorului (turneu Hamiltonian de cost minim): dîndu-se o reţea de oraşe, o reţea de drumuri între oraşe şi o lungime k, există un traseu de cost mai mic decît k trecînd prin fiecare oraş o singură dată şi revenind la punctul de plecare? 2) Dîndu-se o mulţime de numere naturale, se poate împărţi această mulțime în două submulţimi de numere de sume egale? Clasa de complexitate P reprezintă clasa problemelor care pot fi rezolvate rapid iar NP reprezintă clasa problemelor a căror soluție poate fi verificată rapid sau clasa de probleme pentru care există un algoritm nedeterminist polinomial. Cu alte cuvinte, a verifica o soluție este echivalent cu a găsi soluția problemei? Răspunsul la această întrebare 85

NP-completitdine

rezolvă mai multe probleme majore ale acestei discipline. Cei mai mulți cercetători cred că P și NP nu reprezintă aceeași clasă dar consideră că NP include clasa P. Este evident faptul că P ⊆ NP: dacă există un algoritm A care acceptă un limbaj L în timp polinomial atunci acesta poate fi ușor transformat într-un algoritm de verificare în timp polinomial (ignoră orice probă și acceptă doar elementele limbajului L). Există un alt argument pentru a demonstra că P ≠ NP și acesta este dat de limbajele NP-complete. Clasa problemelor NP-complete are următoarea proprietate: dacă pentru o singură problemă NP-completă se poate găsi un algoritm care să o poată rezolva în timp polinomial, atunci pentru toate problemele NP-complete se poate găsi un algoritm de rezolvare polinomial și astfel am putea obține P = NP. Invers, dacă o singură problemă se dovedește a fi dificilă, atunci întreaga clasa NP devine distinctă de clasa P.

Figure 4 Modelul acceptat de majoritatea informaticienilor pentru clasele P, NP, NP-complete.

Marea majoritate a informaticienilor consideră relația între clasele P, NP și NP-complete ca în Figura 4: ambele clase de probleme P și NPcomplete sunt incluse în clasa NP iar P ∩ NP-complete = ∅. Limbajele NP-complete sunt considerate cele mai dificile limbaje din NP. În continuare vom studia dificultatea relativă a acestora folosind o noțiune numită “reductabilitate în timp polinomial”.

86

NP-completitdine

Reducere polinomială Reducerea poate fi văzută ca o modalitate de a afirma că o problemă este la fel de ușoară sau la fel de grea ca o altă problemă. Vom folosi reducerea pentru a arăta dificultatea de rezolvare a unei probleme prin transformarea ei într-o problemă deja cunoscută ca fiind o problemă grea. Intuitiv, o problemă P poate fi redusă la o problemă P’ dacă orice instanță a problemei P poate fi reformulată ca o instanță a problemei P’ iar găsirea unei soluții pentru P’ va însemna găsirea unei soluții pentru P. Algoritm P

Input pentru P

Reducere R

Input R(x)

Algoritm P’

Output P’

Figure 5 Tehnica de reducere polinomială

Considerăm P și Q două probleme de decizie. Avem că P este reductibil în Q dacă și numai dacă există o funcție R astfel încât: -

R transformă o instanță x ∈ P într-o instanță R(x) ∈ Q R este calculată în timp polinomial P(x) și Q(R(x)) au aceeași valoare

În urma verificării acestor condiții obținem ca problema P este reductibilă (în f(n)) în problema Q dacă R(x) este calculabilă în O(f(n)). Teoremă. Presupunem că P este reductibilă în Q, și are complexitatea f(n). 1) Dacă P are complexitatea Ω(g(n)) atunci Q are complexitatea Ω(g(n)-f(n)). 2) Dacă Q are complexitatea O(g(n)) atunci P are complexitatea O(f(n)+g(n)).

87

NP-completitdine

Problema satisfiabilității (SAT) Enunț: Se dă o formulă F din calculul propozițional în forma normală conjunctivă și în care apar variabile din {x0, ..., xn-1}. Se cere să se determine o substituție pentru variabilele lui F pentru care F este satisfăcută. Înainte sa descriem algoritmul pentru rezolvarea acestei probleme, vom prezenta mai întâi formalismele logicii propoziționale. Logica propozițiilor este un caz particular al logicii cu predicate de ordinul I. La fel ca în cazul logicii propozițiilor, definirea logicii cu predicate de ordinul I începe prin a fixa alfabetul limbajului. Alfabetul conține simboluri pentru reprezentarea constantelor (notate a, b, ...), variabilelor (notate X, Y, ...), funcțiilor (notate cu f, g, ...), predicatelor (notate cu p, q, ...), a conectorilor și cuantificatorilor logici. Conectorii logici folosiți în logica cu predicate de ordinul I sunt: ~, ∧, ∨, → și ↔ iar cunatificatorii sunt: cuantificatorul existențial (∃) și cuantificatorul universal (∀). O formulă în logica propozițională sau o expresie Booleană cuprinde variabile, operatori logici sau conective logice: AND (conjuncție, notată cu ∧), OR (disjuncție, ∨), NOT (negație, ¬) și paranteze. Implicația este considerată falsă numai în cazul în care un antecedent adevarat implică un consecvent fals (A→B sau ~A∨B). Adevărul sau falsitatea unei formule rezultă din valorile de adevăr/fals ale componentelor și din modul în care operatorii combină componentele în cadrul frazei. Considerăm SF o mulțime finită de simboluri funcționale în care fiecare simbol are atașat un număr natural numit aritatea simbolului respectiv. Dacă f ∈ SF este un simbol de aritate n atunci avem f(x1, ..., xn). Considerăm SC o mulțime finită de simboluri de constante. Considerăm SP o mulțime finită de simboluri de predicate. Ca și în cazul simbolurilor funcționale, fiecare simbol de predicat are atașat un număr care reprezintă aritatea simbolului.

88

NP-completitdine

Considerăm SV o mulțime finită de elemente numite variabile. Un atom peste o bază B este definit ca un element de forma p(t1, ..., tn), unde p(n) ∈ SP și t1, ..., tn sunt termeni peste B. Se numește literal un atom sau negația unui atom. Literalul reprezentat de un atom se numește literal pozitiv iar literalul reprezentat de negația unui atom se numește literal negativ. O formulă corectă în logica cu predicate de ordinul I se definește astfel: -

1) un atom este o formulă corectă 2) daca p este o formulă corectă, atunci: ~p, (∃x)p(x), (∀x)p(x) sunt formule corecte 3) daca p și q sunt formule corecte atunci: p∧q, p∨q, p→q, p↔q sunt formule corecte 4) orice formulă corectă este generată prin aplicarea de un număr finit de ori a regulilor (1)÷(3)

Într-o formulă variabilele pot fi variabile libere sau legate. O variabilă este legată dacă există un cuantificator care o referă. În caz contrat, variabila este liberă. O formulă care conține variabile libere nu poate fi evaluată. O formulă f se spune că este în forma normal conjunctivă dacă se poate exprima ca o conjuncție de m componente astfel încât fiecare componentă să fie o disjuncție de literali. O formulă se numește satisfiabilă dacă există o anumită interpretare în care formula este adevărată. Problema satisfacerii formulei Booleene problema SAT are scopul de a determina, pentru o formulă dată, dacă aceasta este satisfiabilă. Această problemă de decizie are o mare importanță pentru mai multe domenii ale informaticii, ca de exemplu informatica teoretică, teoria complexității, algoritmi și inteligență artificială. În cele ce urmează considerăm o clauză drept o disjuncție de literali. Obținem că o formulă este în formă normală conjunctivă dacă este o 89

NP-completitdine

conjuncție de clauze. Problema SAT decide dacă o formulă în forma normal conjunctivă este satisfăcută de o interpretare astfel încât toate clauzele să fie adevărate. Definiție. Problema de satisfiabilitate se definește astfel: Instanță: m clauze Ci formate folosind n variabile logice (literali)

Output: Formula F = C1 ∧ C2 ... ∧ Cm este satisfacută?

De exemplu, formula (x ∨ ¬y ∨ z) ∧ (¬x ∨ ¬y) ∧ (x ∨ ¬z) este satisfăcută de substituția: σ = {(x, true), (y, false)} Teormă (Steven Cook, 1971) Problema SAT este NP-completă. Este ușor de verificat că problema SAT este în NP. Dacă se consideră cei n literali stocați pe n biți de memorie, verificarea satisfiabilității se reduce la a verifica dacă toate clauzele sunt satisfăcute, ceea ce implică o complexitate polinomială, O(nm). Algoritmul nedeterminist care rezolvă SAT este următorul: 1. ghicește o atribuire pentru variabile 2. calculează valoarea formulei 3. dacă formula este satisfacută întoarce succes; altfel întoarce fail. Varianta kSAT a problemei de satisfiabilitate este de a găsi o interpretare variabilelor unui formule date în formă normală conjunctivă ale cărei clauze sunt formate din k literali. Pentru k ≥ 3, versiunea kSAT a problemei de decizie este NP-completă, dar pentru k=2 problema este rezolvabilă în timp polinomial, așa cum se arată în cele ce urmează.

90

NP-completitdine Varianta 2SAT

Se dă o formulă booleană F în forma normal conjunctivă astfel încât fiecare clauză conține exact doi literali. Să se determine dacă există o substituție (atribuire de valori) care să satisfacă formula F. Teoremă. Problema 2SAT are complexitate polinomială, deci 2SAT ∈ P. Dându-se o formulă propozițională F în formă normală conjunctivă în care toate clauzele sunt formate din două literali, trebuie să găsim o interpretare I variabilelor sale, care satisface F. În acest scop, pornind de la o formulă F - instanță de 2SAT, vom defini un grafic G(F), după cum urmează: -

nodurile lui G sunt date de variabilele formulei F și negația acestora; G conține un arc orientat de la nodul u la nodul v, (u, v) dacă și numai dacă există o clauză (¬u ∨ v) sau (v ∨ ¬u).

A se remarca faptul că o clauză (¬u ∨ v) va genera două arce în graful G: -

(u, v) dat de (¬u ∨ v) (¬u, ¬v) dat de (¬(¬v) ∨ ¬u)

Obținem că graful G are o proprietate de simetrie: dacă există un arc (u, v) în G atunci va exista și arcul (¬u, ¬v) în G. Exemplu. Să considerăm următoarea formulă: (x1 ∨ x2) ∧ (x1 ∨ ¬x3) ∧ (¬x1 ∨ x2) ∧ (x2 ∨ x3) . Graficul corespunzător acestei formule este prezentat în Figura 6. Intuitiv, arcele reprezintă implicațiile logice ale formulei F (în fapt, o implicație u → v poate fi rescrise ca ¬u ∨ v). Prin urmare, drumurile în graful G(F) sunt implicații logice ale formulei F. Scopul problemei 2SAT este să găsească o interpretare în care formula F să fie adevărată, adică să gasească o substituție pentru variabilele formulei F astfel încât valoarea lui F să devine true. 91

NP-completitdine

Figure 6 Graful G(F)

Dacă adoptăm următoarea convenție: să colorăm cu roșu valorile false și cu verde valorile true din graf, observăm că pentru x1 = false, x2 = true și x3 = false toate arcele grafului sunt pe “verde”, adică toate implicațiile formulei F sunt adevărate. Ceea ce se traduce în faptul ca toate clauzele lui F sunt true, deci conjuncția de clauze este satisfacută.

Figure 7 O interpretare a formulei F (x1=false, x2=true și x3=false)

92

Bibliografie [1] Irina Athanasiu, Limbaje formale şi automate (Note de curs), 2012 [2] Dumitru Dan Burdescu, Analiza complexității algoritmilor, Editura Albastra, Cluj Napoca, 1998. [3] Mihai Budiu, Algoritmi, http://www.cs.cmu.edu/~mihaib/articole/algoritmi/algoritmihtml.html, 1997. [4] Thomas H. Cormen, Charles E. Leiserson, Ronald R. Rivest, Introducere în algoritmi, Editura Computer Libris Agora, 2000 [5] Cristian Giumale, Analiza algoritmilor (Note de curs), 2014 [6] Mihai Gontineac, Limbaje Formale și Teoria Automatelor, Note de curs (http://www.math.uaic.ro/~gonti/Didactics.htm) [7] Dorel Lucanu, Mitică Craus, Proiectarea algoritmilor, Editura Polirom, 2008 [8] Drăgan Mircea, Limbaje Formale și Tehnici de Compilare, 2006 [9] Drăgan Mircea, Ștefan Mărușter, Limbaje Formale, 2005 [10] Mihnea Muraru, Paradigme de programare, Note de curs 2012 [11] Daniela Zaharie, Algoritmi Note de curs, http://web.info.uvt.ro/~dzaharie/alg/alg2014.html, 2014