[9] paradigme general

Proiectarea algoritmilor: Despre paradigmele deproiectare

Dorel Lucanu

Faculty of Computer ScienceAlexandru Ioan Cuza University, Iasi, Romania

[email protected]

PA 2014/2015

D. Lucanu (FII - UAIC) Despre paradigmele de proiectare PA 2014/2015 1 / 16

Outline

1 Aspecte generale

2 Un studiu de caz simplu


Aspecte generale

Plan

1 Aspecte generale



Aspecte generale

Necesitatea unui model

Descrierea unui algoritm care rezolva o problema presupune ca etapa intermediaraconstructia modelului matematic corespunzator problemei. Necesitateaconstructiei modelului matematic este impusa de urmatoarele motive:

eliminarea ambiguitatilor si inconsistentelor. De multe ori, problema estedescrisa informal (verbal). De aici, anumite aspecte ale problemei pot fiomise sau formulate ambiguu. Constructia modelului matematic evidentiazatoate aceste lipsuri si, ın acest fel, conduce la eliminarea lor;

utilizarea instrumentelor matematice de investigare. Parcurgerea drumuluide la formularea problemei la gasirea solutiei nu este ıntotdeauna simpla saupredictabila. Instrumentele matematice de investigare ofera un cadrusistematic si sigur pentru determinarea structurii analitice a solutiei si apoi amodului de obtinere a acesteia;

diminuarea efortului la scrierea programului. Descrierea solutiei ın termeniimodelului matematic usureaza foarte mult munca de definire si apoi dedescriere a algoritmului (programul).


Aspecte generale

O paradigma a paradigmelor de proiectare ale algoritmilor

model matematic

aspect conceptual

aspect analitic as

pect

co

mpu

tiona

l

problema program

PARADIGMA s. f. 1. (la Platon) lumea ideilor, prototip al lumii sensibile ın caretraim. ♦ principiu care distinge legaturile si opozitiile fundamentale ıntre catevano?iuni dominante cu functie de comanda si control al gandirii. ♦ caz exemplar,model, prototip, situatie ideala. 2. totalitatea formelor flexionare ale unui cuvant.♦ ansamblu de termeni, apartinnd aceleiasi clase morfosintactice sau semantice,care se pot substitui unul cu altul. (< fr. paradigme, lat. paradigma, gr.paradeigma) [sursa: MDN]


Aspecte generale

Modelul matematic

O paradigma de proiectare a algoritmilor se bazeaza pe un anumit tip de modelmatematic si pune la dispozitie procedee prin care se poate construi si implementa(descrie ca program) un model particular corespunzator unei probleme. Descriereaunui model matematic indexmodel matematic cuprinde urmatoarele trei aspecte:

1 conceptual : presupune identificarea si definirea conceptelor care descriucomponentele din domeniul problemei;

2 analitic: presupune gasirea tuturor relatiilor ıntre concepte care conduc lagasirea si descrierea solutiei;

3 computational : presupune evaluarea calitativa a algoritmului ce construiestesolutia.

Cele trei aspecte se reflecta ın etapele ce trebuie parcurse ın rezolvarea uneiprobleme si pe care le-am discutat ın capitolul de introducere.


Un studiu de caz simplu

Plan

1 Aspecte generale




Un exemplu simplu de model

Determinarea celui mai mare punct fix

Fie A o multime finita si f : A→ A o functie. Daca X ⊆ A, atuncif (X ) = {f (x) | x ∈ X}. Un punct fix este o submultime X ⊆ A cuproprietatea f (X ) = X .Date A si f , se pune problema determinarii celui mai mare punct fix, adicacea mai mare submultime X ⊆ A cu proprietatile f (X ) = X si pentru oriceY ⊆ A, daca f (Y ) = Y atunci Y ⊆ X .

O ”schema” de algoritm (algoritm abstract) care rezolva problema celuimare punct fix este:

X = A;

while (¬ X ⊆ f(X))

foreach (x ∈ X)

if (f(x) 6∈ X) X = X \ {x};



Corectitudinea algoritmului

Algoritmul se termina dupa prima iteratie while ın care foreach numodifica X . Deoarece toate iteratiile anterioare descresc |X | si X estefinita, rezulta ca se va termina totdeauna.

Dupa terminarea lui while, avem X ⊆ f (X ). Se observa ca f (X ) ⊆ Xeste invariant al lui while. (Exercitiu. De verificat.)Rezulta f (X ) = X , adica X este punct fix.

Mai trebuie aratat ca X este cel mai mare punct fix. Pentru asta estesuficient de verificat ca daca Y este un punct fix al lui f , atunci Y ⊆ Xeste un invariant al lui while. (Exercitiu. De verificat.)



Problema permutarii maximale

Se considera o colectivitate formata din n persoane. Fiecare persoana dincolectivitate are un singur preferat ın colectivitate. Este posibil ca opersoana sa se poate prefera pe sine ınsasi. Un grup de persoane dincolectivitate se numeste omogen daca fiecare membru al grupului estepreferatul exact al unui singur membru din acel grup. Se pune problemaalegerii unui grup omogen cu numar maxim de persoane.



Modelul matematic: aspectul conceptual

Notam cu Col multimea finita reprezentand colectivitatea de persoane.”Fiecare persoana din colectivitate are un singur preferat ın colectivitate”poate fi modelat printr-o functie pref : Col → Col .

pref (i) = j ınseamna ca i prefera pe j .

Proprietatea de omogenitate a unui grup X se defineste prinpref −1(X ) ⊆ X si prin faptul ca pref |X : pref −1(X )→ X este surjectiva,unde pref −1(X ) = {i | pref (i) ∈ X}.

Problema consta ın a determina cea mai mare submultime X a lui A cuproprietatile pref −1(X ) ⊆ X si pref |X este surjectiva.



Modelul matematic: aspectul analitic

pref |X : X → X surjectiva si X finita implica pref |X : X → X este bijectie(permutare).

Rezulta pref (X ) = X , i.e., X este un punct fix al lui pref .

Deci problema se reduce la deoerminarea celui mai mare punct fix al luipref .



Modelul matematic: aspectul computational

De la notatia matematica la structuri de date:

Col o modelam prin 1..n, unde n este |Col |;pref un tablou unidimensional 1..n 7→ pref[1], . . . , pref[n]X prin vectorul (tabloul) caracteristic:

x[j ] =

{1, daca j ∈ X

0, altfel

cu o mica modificare, tabloul x poate fi utilizat si pentrureprezentarea functiei pref |X :

x[j ] =

{pref [j ], daca j ∈ X

−1, altfel

multimea pref −1(X ) este reprezentata de un tablou

prefInvOfX[j ] = |{i | pref [i ] = j}|unde j ∈ pref −1(X ) ddaca prefInvOfX[j ] > 0;testul ¬(X ⊆ pref (X )) poate fi realizat ın O(1) utilzand o variabilabooleana existaj, care va fi true numai cand foreach modifica X .



Algoritmul

permMax(pref, n, x) {

for (j = 1; j <= n; ++j)

prefInvOfX[j] = 0;

for (j = 1; j <= n; ++j) {

x[j] = pref[j];

++ prefInvOfX[pref[j]];

}

existaj = true;

while (existaj) do {

existaj = false;

for (j = 1; j <= n; ++j)

if ((x[j]>0) && (prefInvOfX[j]==0)) {//j ∈ X ∧ pref −1(j) 6∈ Xx[j] = -1;

-- prefOfX[pref[j]];

existaj = true;

}

}

}D. Lucanu (FII - UAIC) Despre paradigmele de proiectare PA 2014/2015 14 / 16


Analiza algoritmului

corectitudinea rezulta din corectitudinea schemei de calcul al celuimai mare punct fix si din implementarea corecta a testuluiX ⊆ pref (X ) si a structurii foreach. (Exercitiu. De verificat.)

primele doua bucle for fac n iteratii, fiecare iteratnecesita timpulO(1);

bucla for din interiorul lui while face n iteratii, fiecare iteratnecesitatimpul O(1);

bucla while face cel mult n iteratii (la fiecare iteratie, exceptandultima, se elimina un element din X )

rezulta timpul O(n2) pentru cazul cel mai nefavorabil. (Exercitiu. Deprecizat cazul cel mai nefavorabil.)



Concluzii

modelarea matematica a permis formularea exacta a ceea ce sedoreste sa se calculeze

dupa conceptualizare si analiza, algoritmul a rezultat imediat pentruca s-a observat ca se poate aplica paradigma celui mai mare punct fix;

corectitudinea algorimului rezulta din corectitudinea paradigmei.


[9] paradigme general

Documents