[1] limb-alg

Limbajul Algoritmic

Dorel Lucanu

Faculty of Computer ScienceAlexandru Ioan Cuza University, Iasi, Romania

[email protected]

PA 2014/2015

D. Lucanu (FII - UAIC) Limbajul Algoritmic PA 2014/2015 1 / 57

Outline

1 Introducere

2 Limbajul AlkModelul de memorieOperatiiExpresii si instructiuni

SintaxaSemantica

3 Testarea algoritmilor cu K Framework (Informativ)


Introducere

Plan

1 Introducere


SintaxaSemantica



Introducere

Ce este un algoritm

Nu exista o definitie standard pentru notiunea de algorithm.

Cambridge Dictionary:A set of mathematical instructions that must be followed in a fixed order, and that,

especially if given to a computer, will help to calculate an answer to a mathematical

problem.

Schneider and Gersting 1995 (Invitation for Computer Science):An algorithm is a well-ordered collection of unambiguous and effectively computable

operations that when executed produces a result and halts in a finite amount of time.

Gersting and Schneider 2012 (Invitation for Computer Science, 6ndedition):An algorithm is ordered sequence of instructions that is guaranteed to solve a specific

problem.


Introducere

Ce este un algoritm?

Wikipedia:

In mathematics and computer science, an algorithm is a step-by-step procedure forcalculations. Algorithms are used for calculation, data processing, and automatedreasoning.

An algorithm is an effective method expressed as a finite list of well-defined instructions

for calculating a function. Starting from an initial state and initial input (perhaps

empty), the instructions describe a computation that, when executed, proceeds through

a finite number of well-defined successive states, eventually producing output and

terminating at a final ending state. The transition from one state to the next is not

necessarily deterministic; some algorithms, known as randomized algorithms, incorporate

random input.


Introducere

Ingredientele de baza: model de calcul, problema rezolvata

Toate definitiile au ceva n comun:

datele/informatia si procesarea acestora/acesteia n pasi. Acesteasunt descrise n general de un model de calcul.Un model de calcul este format din:

memorie - modul de reprezentare a datelorinstructiunisintaxa - descrie sintactic pasii de procesaresemantica - descrie pasii de procesare realizati de executia uneiinstructiuni; n general este data de o relatie de tranzitie pesteconfiguratii (sistem tranzitional)

un algoritm trebuie sa produca un rezultat, adica un algoritm trebuiesa rezolve o problema.O problema este n general reprezentata de o pereche (input,output),unde input reprezinta descrierea datelor de intrare (instanta) iaroutput descrierea datelor de iesire (rezultatul).


Introducere

Cum descriem un algoritm?

informal: limbaj natural

formal

notatie matematica (masini Turing, lambda-calcul (Church), functiirecursive, . . . )limbaje de programare: imperative de nivel inalt, de nivel jos,declarative (e.g., programare functionala, programare logica). Acestapoate fi si un model informal daca nu exista o semantica formalapentru limbaj.

semiformal

pseudo-cod: combina notatia formala a limbajelor de prgramare culimbajul naturalnotatie grafica: scheme logice, automate (state machines), diagramede activitati


Introducere

De ce nevoie de formalizare?

nainte de secolul 20 matematicienii au utilizat notiunea de algoritmdoar la nivel intuitiv

n 1900, David Hilbert, la Congresul matematicienilor din Paris, aformulat 23 de probleme ca provocari ale secolului care ncepea

problema a 10-a cerea gasirea unui proces care sa determine daca unpolinom cu coeficienti ntregi are o radacina ntreaga

Hilbert nu a pronuntat termenul de algoritm


Introducere

De ce nevoie de formalizare?

problema a 10-a a lui Hilbert este nerezolvabila, i.e. nu exista unalgoritm care avand la intrare un polinom p, decide daca p areradacina ntreaga

acest fapt nu se poate demonstra avand doar notiunea intuitiva dealgoritm

pentru a demonstra ca nu exista algoritm care rezolva o problema, enecesar de o notiune formala


Introducere

Formalizarea notiunii de algoritm

abia n 1936 Alonso Church si Alan Turing au definit formal, fiecareindependent, notiunea de de algoritm

Church a utilizat notattia cunoscuta acum sub numele delambda-calcul (-calcul)

Turing a definit modelul de calcul care acum este cunoscut subnumele de masini Turing

cele doua modele de calcul sunt echivalente

n 1970 Yuri Matijasevic a aratat ca nu exista algoritm care sa testezedaca un polinom dat are radacina ntreaga sau nu (rezultaul sebazraza pe munca anterioara depusa de Martin Davis, Hilary Putnam,si Julia Robinson)

de atunci au aparut multe alte modele echivalente cu masinile Turing


Introducere

Teza Church-Turing

Turing a afirmat (Teza lui Turing) ca orice functie a carei valoare poate fiobtinuta printr-o metoda efectiva (?), poate fi calculta de o masina Turing.

Forma cea mai accesibila formulata de Turing:LCMs [logical computing machines: Turings expression for Turing machines] cando anything that could be described as rule of thumb or purely mechanical.(Turing 1948)

Teza lui Church:A function of positive integers is effectively calculable only if recursive.

Modelul de calcul al functiilor recursive a fost definit de de Godel si Herbrand(1932-1934) si este echivalent cu lambda-calculul (Kleene, Church, 1936).

Kleene (1967) este cel care a introdus termenul de Teza Church-Turing:So Turings and Churchs theses are equivalent. We shall usually refer to themboth as Churchs thesis, or in connection with that one of its . . . versions whichdeals with Turing machines as the Church-Turing thesis.


Introducere

Nivelul de formalizare

Care este cel mai potrivit limbaj formal de prezentare a algoritmilor?

masinile Turing, lambda-calculul, functiile recursive au avantajul casunt usor de definit matematic, dar sunt greu de utilizat n practica

limbajele de programare sunt usor de utilizat n practica dar dificil demanevrat n demonstratii datorita detaliilor de implementare

cel mai simplu limbaj de programare echivalent cu masinile Turing:modelul de memorie: multime de variabile ce pot lua valori ntregiinstructiuni: goto conditionala si neconditionala, incrementarea sidecrementarea variabileloreste cunoscut sub numele de counting machines

o variant structurata (modelul programelor while):modelul de memorie: multime de variabile ce pot lua valori ntregiinstructiuni: atribuirea, if, while, si compunerea secventiala


Limbajul Alk

Plan

1 Introducere


SintaxaSemantica



Limbajul Alk

Motivatie

Scopul nostru este de a avea un limbaj care este

destul de simplu pentru a fi nteles

suficient de expresiv pentru a descrie toti algoritmii prezentati

abstract: descrierea algoritmului face abstractie de detaliile deimplementare (specifice unui limbaj de programare real), avantajandastfel focalizarea pe gandirea algoritmica

sa ofere un model de calcul riguros definit si potrivit pentru analizaalgoritmilor (corectitudine si eficienta)

executabil: algoritmii pot testati si executiile lor analizate cu diversemijloace (executie pas cu pas, executie simbolica, etc)

intrarile si iesirile sunt reprezentate abstract, ca obiecte matematice.astfel ncat detaliile de implementare sunt omise total

Un candidat care satisface aceste cerinte este Alk (limbaj specific acestuicurs).


Limbajul Alk Modelul de memorie

Plan

1 Introducere


SintaxaSemantica




Modelul de memorie

memoria este data de o multime de variabile

variabilele nu sunt altceva decat locatii de memorie care stocheazavalori si care sunt accesta prin nume simbolice n loc de adrese

astfel o varibila este o pereche:

notatie matematica nume-variabila 7 valoare

notatie graficavaloare

nume-variabila

o valoare va fi un obiect al unui tip de date abstract

exemple de tipuri de valori:scalaretablouristructuriliste. . .



Tip de date

Tip de data = valori (obiecte) + operatii

Fiecare valoare (obiect) este reprezentata pe un spatiu de memorie.

Pentru fiecare tip trebuie precizata lungimea (dimensiunea) reprezentariiobiectelor.

Exista doua moduri de a defini lungimea reprezentarii:uniform: lungimea reprezentarii valorilor scalare = 1, pentru obiecteleconpuse = numarul obiectelor scalare componente;logaritmic: pentru obiectele scalare se presupune reprezentarea binara,pentru obiectele compuse se ia suma reprezentarilor obiectelorcomponente.



Scalari

aici sunt incluse tipurile primitive: valorile boolene, algebra ntregilor,algebra numerelor rationale (virgula mobila), siruri

notatie matematica b 7 true i 7 5

notatie graficatrueb

5i

C++ bool b = true; int i = 5;

Notatia matematica este scrierea simplificata (fara numele intermediar alfunctiei) al unei functii : {b, i, . . .} Val data prin (b) = true,(i) = 5, . . . . Val este reuniunea valorilor booleene, ntregi,. . . .

Lungimea reprezentaarii: ntregi n - log2 n, booleeni b - 1, . . .



Scalari (cont.)

ntregi:Int = {. . . ,2,1, 0, 1, 2, . . .}booleeni:Bool = {false, true}rationale:Float = numerele rationale

O caracteristica importanta pentru valorile scalare: admit reprezentarifinite

Intrebare: ce se poate spune despre numerele irationale, de exemplu

2?



Tablouri (unidimensionale)

Un tablou (unidimensional) poate fi abstractizat ca o functie de lamultimea (finita) de indici la multimea de valori. O astfel de functie poatefi reprezentata de o multime de perechi indice 7 valoare. Vom consideraca multimea indicilor este {0, 1, . . . , n 1} (la fel ca n C++):

notatie matematica a 7 {0 7 a0 1 7 a1 2 7 a2}

notatie grafica

0 1 2

a0 a1 a2a

C++

int a[3];

for (i=0; i> a[i];

or

int a = {a0, a1, a2};

Tablourile multidimensionale pot fi modele cu tablouri unidimensionale detablouri . . .



Tablouri (unidimensionale) (cont.)

Arrn = {{0 7 v0, . . . , n1 7 vn1 | vi Val , i = 0, . . . , n1}

Val = multimea tuturor valorilor (scalare si nescalare (compuse))

Val = Int Bool Float n1 Arrn . . .ArrnV = {{0 7 v0, . . . , n1 7 vn1 | vi V , i = 0, . . . , n1}Exemple: ArrnInt, ArrnBool, ArrnArrm, ArrnList

Notatie: Uneori notam 0 7 v0, . . . , n1 7 vn1 prin (v0, . . . , vn1).



Structuri

Structurile sunt reprezentate ntr-un mod similar celui de la tablouri,numai ca acum domeniul functiilor este multimea numelor de campuri nloc de cea a indicilor.De exemplu, o structura p reprezentand puncte n plan are doua campuri:x si y:

notatie matematica p 7 {x 7 2 y 7 7}

notatie grafica

x y

2 7

p

C++

struct Point {

int x;

int y;

} p;

p.x = 2; p.y = 7;



Structuri (cont.)

F = {f1, . . . , fn} - o multime de campuri (de exemplux y next val...)

StrF = {{f1 7 v1, . . . , fn 7 vn} | vi Val , i = 1, . . . , n}

Strf1 : V1, . . . fn : Vn = {{f1 7 v1, . . . , fn 7 vn} | v1 V1, . . . , fn Vn}Exemplu:FSLL = {len, arr}Strlen : Int, arr : Arr 100Int ={{len 7 n arr 7 a | n Int, a Arr 100Int}



Liste liniare

O lista liniara este o secventa de valori:

notatie matematica ll 7 [2, 7, 4, 2, 8]

notatie grafica

2, 7, 4, 2, 8

ll

C++list ll;

(pot exista diferite implementari)



Liste liniare (cont.)

LLin = {[v0, . . . , vn1] | vi Val , i = 0, . . . , n}

LLinV = {[v0, . . . , vn1] | vi V , i = 0, . . . , n}

Exemple: LLinInt, LLinArrn, LLinArrnFloat

A nu se confunda notatia [v0, . . . , vn1] (lista liniara) cu (v0, . . . , vn1)(tablou unidimensional).



Valori complexe: grafuri

Graful G = ({0, 1, 2}, {(0, 1), (0, 2), (1, 2)}) este reprezentat prin liste deadiacenta dupa cum urmeaza:

notatie matematica{n 7 3 a 7 {0 7 [1, 2] 1 7 [0, 2] 2 7 [0, 1]}}notatie grafican a

0 1 2

3 [1, 2] [0, 2] [0, 1]

G

C++

struct Graph { G.n = 3;

int n; G.a[0].push_front(1);

vector a; ...

} G;


Limbajul Alk Operatii

Plan

1 Introducere


SintaxaSemantica




Tip de date (cont.)

Tip de data = obiecte + operatii

Fiecare operatie are un cost timp.

Pentru fiecare tip trebuie precizat timpul pentru fiecare operatie.

Exista doua moduri de a defini timpul (mostenite de la lungimeareprezentarii):uniform: nu depinde de marimea reprezentarii obiectelorlogaritmic: depinde de marimea reprezentarii



Operatii cu scalari

Intregi:Operatie time(Operatie)

Cost uniform Cost logaritmic

a +Int b O(1) O(max(log a, log b))

a Int b O(1)O(log a log b)O(max(log a, log b)1.545)

. . .



Tablouri

Operatie time(Operatie)Cost uniform Cost logaritmic

A.lookup(i) O(1) O(i + log ai )

A.update(i , v) O(1) O(i + log v)

unde am presupus A 7 {0 7 a0, . . . , n 1 7 an1}


TeaHighlight


Structuri

Operatie time(Operatie)Cost uniform Cost logarithmic

S .lookup(x) O(1) O(log sx)

S .update(x , v) O(1) O(log v)

unde am presupus S 7 {. . . x 7 sx , . . .}


TeaHighlight


Liste liniare: definitie operatii

empty() ntoarce lista vida []L.topFront() ntoarce v0L.topBack() ntoarce vn1L.lookup(i) ntoarce viL.insert(i,x) ntoarce [. . . vi1, x , vi , . . .]L.remove(i,x) ntoarce [. . . vi1, vi+1, . . .]L.size() ntoarce nL.popFront() ntoarce [v1, . . . , vn1]L.popBack() ntoarce [v0, . . . , vn2]L.pushFront(x) ntoarce [x , v0, . . . , vn1]L.pushBack(x) ntoarce [v0, . . . , vn1, x ]L.update(i,x) ntoarce [. . . vi1, x , vi+1, . . .]

unde am presupus L 7 [v0, . . . , vn1]Notatii: L[i] este aceeasi cu L.lookup(i)L[i] = x este aceeasi cu L.insert(i , x)



Liste liniare: operatii (versiunea 1)

- corespunde implementarii cu tablouriOperatie time(Operatie)

Cost uniform Cost logaritmicL.lookup(i) O(1) ?L.insert(i , x) O(L.size() i) ?L.remove(i , x) O(L.size() i) ?L.update(i , x) O(1) ?L.topFront() O(1) ?L.popFront() O(L.size()) ?L.pushFront() O(L.size())) ?L.topBack() O(1) ?L.popBack() O(1) ?L.pushBack() O(1) ?



Liste liniare: operatii (versiunea 2)

- corespunde implementarii cu liste dublu nlantuiteOperatie time(Operatie)

Cost uniform Cost logaritmicL.lookup(i) O(i) ?L.insert(i , x) O(i) ?L.remove(i , x) O(i) ?L.update(i , x) O(i) ?L.topFront() O(1) ?L.popFront() O(1) ?L.pushFront() O(1) ?L.topBack() O(1) ?L.popBack() O(1) ?L.pushBack() O(1) ?



Liste liniare: operatii (versiunea 3?)

- Exista o lista liniara cu urmatoarele proprietati?Operatie time(Operatie)

Cost uniform Cost logaritmicL.lookup(i) O(1) ?L.insert(i , x) O(i) ?L.remove(i , x) O(i) ?L.update(i , x) O(1) ?L.topFront() O(1) ?L.popFront() O(1) ?L.pushFront() O(1) ?L.topBack() O(1) ?L.popBack() O(1) ?L.pushBack() O(1) ?


Limbajul Alk Expresii si instructiuni

Plan

1 Introducere


SintaxaSemantica




Expresii: sintaxa

Sintaxa este foarte apropiata de cea limbajului C++:

Notatia Backus-Naur

syntax Exp ::= Id

| Int

| Exp "+" Exp

| Exp "*" Exp

...

| Exp "&&" Exp

| Exp "||" Exp

...

| Id "(" Exps ")"

...

syntax Exps ::= List{Exp,","}

Varianta recursiva

un identificator (nume de variabila)este espresie

un numar ntreg este expresie

daca E1 si E2 sunt expresii atunciE1 + E2 este expresie

daca E1 si E2 sunt expresii atunciE1 * E2 este expresie

. . .

daca E1, . . . ,En este o lista deexpresii sI F un identificator (numede functie)

. . .



Instructiuni: sintaxa

syntax Stmt ::= Exp "=" Exp ";"

| Exp ";"

| "{" "}"

| "{" Stmts "}"

| "while" "(" Exp ")" Stmt

| "return" Exps ";"

| Exp "(" Ids ")" "{" Stmts "}"

| "if" "(" Exp ")" Stmt "else" Stmt

| "if" "(" Exp ")" Stmt

...

syntax Stmts ::= List{Stmt,""}

Alk este extensibil: pot fi adaugate noi expresii si instructiuni, cu precizaaripentru costul timp



Tipuri de date

Sunt predefinite n Alk.

Presupunem existenta unei metainformatii care mentioneaza tipul fiecareivariabile (nu exista declaratii de variabile).



Exemplu de program

/*This example includes the recursive version of the DFS algorithm.@input: a digraf D and a vertex i0@output: the list S of the verices reachable from i0

*/

// the recursive functiondfsRec(i) {if (S[i] == 0) {// visit iS[i] = 1;p = D.a[i];while (p.size() > 0) {j = p.topFront();p.popFront();dfsRec(j);

}}

}

// the calling programi = 0;while (i < D.n) {S[i] = 0;i = i + 1;

}dfsRec(1);



Evaluarea expresiilor

Consideram o functie [[ ]]( ) : Expresii (Stare Valori), unde [[E ]]() ntoarcevaloarea expresiei E calculata n starea .

Exemplu: [[a + b 2]](a 7 3 b 7 6) = 15.Reguli de calcul pentru [[ ]]( ):

[[x]](. . . x 7 v . . .) = v [[v ]]( ) = v[[E1]]() = v1 [[E2]]() = v2

[[E1+E2]]() = v1 +Int v2

unde +Int reprezinta algoritmul de adunare peste ntregi.

Regulile de mai sus ne dau si o metoda de calcul a timpului necesar evaluarii:time([[x]](. . . x 7 v . . .)) = log v (logaritmic)time([[x]](. . . x 7 v . . .)) = 1 (uniform)time([[E1+E2]]()) = time([[E1]]()) + time([[E2]]()) + time([[E1]]() +Int [[E2]]())



Configuratii

O configuratie este o pereche secventa-de-program, stareExemple:x = x + 1; y = y + 2 * x;, x 7 7 y 7 12s = 0; while (x > 0) {s = s+x; x = x-1;}, x 7 5 s 7 15


TeaHighlight


Pasi de executie

Un pas de executie este definit ca o tranzitie ntre configuratii:S , S ,

daca si numai dacaexecutand prima instructiune secventa S n starea obtinem secventa S ,ce urmeaza a fi executata n continuare, si o noua stare

Pasii de executie sunt descrisi prin reguli S1, 1 S2, 2, undeS1,S2, 1, 2 sunt termeni cu variabile (patterns).



Instructiuni: semantica

atribuirea: x = E;

informal : se evalueaza E si rezultatul este atribuit ca noua valoare avariabilei x

formal :x = E;S , (x 7 v)} S , (x 7 [[E ]]( (x 7 v))}

time(x = E;S , S , ) = time([[E ]]()) + 1, cost uniformtime(x = E;S , S , ) = time([[E ]]() + log[[E ]]()), costlogaritmic




if: if (E) then S else S

informal : se evalueaza e; daca rezultatul obtinut este true, atunci se executaS , altfel se executa S

formal :

if (E) then S else S y S , S S , daca [[E ]]() = trueif (E) then S else S y S , S S , daca [[E ]]() = false

time(if (E) then S else S S , , ) = time([[E ]]()), cost uniformtime(if (E) then S else S S , , ) = time([[E ]]()), costlogaritmic




while: while (E) S

informal : se evalueaza e; daca rezultatul obtinut este true, atunci seexecuta S , dupa care se evalueaza din nou e si . . . ; altfel executiainstructiunii se termina

formal : se exprima cu ajutorul lui if:while (e) S y S , if (e) { S ; while (e) S } else { }S ,

time(while (E) then S else S S , if (e) ...S , ) = 0,pentru ambele costuri



Apelul de functie

Operatie mai complexa ce include mai multe activitati:

se evalueaza argumentele actuale

legarea parametrilor formali la valorile date de argumentele actuale(parametrii functiei devin variabile cu valorile date de evaluareaargumentelor actuale)

salvarea starii curente n lista de actvitati

construirea starii de start pentru executia corpului functiei formatadin variabilele globale, parametrii si variabilele locale ale functiei

dupa executia corpului functiei, se restaureaza starea de dinainte deapel

Functiile sunt memorate ca variabile specialef 7 (parametri@{corpul functiei})

Presupunere: costul unui apel este suma dintre costul evaluariiargumentelor actuale si costul executiei corpului functiei.


TeaHighlight


Calcul (executie)

Un calcul (o executie) este o secventa de pasi:S1, 1 S2, 2 S3, 3 . . .

Exemplu:if (x > 3) x = x + y; else x = 0; y = 4; skip, x 7 7 y 7 12 x = x + y; y = 4; skip, x 7 7 y 7 12 y = 4; skip, x 7 19 y 7 12 skip, x 7 19 y 7 4 [[x > 0]](x 7 7 y 7 12) = true[[x + y]](x 7 7 y 7 12) = 19[[4]](x 7 19 y 7 12) = 4cost uniform: 4cost logaritmic: log 7 + log 7 + log 12 + log 19 + log 4


TeaNote7; y->12>0 y->12>0 y->4>

Testarea algoritmilor cu K Framework (Informativ)

Plan

1 Introducere


SintaxaSemantica




Testarea algoritmilor cu K Framework

K Framework (www.kframework.org) este un mediu de lucru pentrudefinitii de limbaje de programare. Definitiile K sunt executabile. Limbajul

Alk este definit n K, asa ca algoritmii descrisi n Alk pot fi testati sianalizati.

Exista o interfata online pentru K (http://fmse.info.uaic.ro/tools/K/), darse recomanda instalarea Kului pentru calculatorul personal.

Definitia K a lui Alk se gaseste la adresahttps://github.com/kframework/alk-semantics

Compilarea definitiei limbajului Alk:kompile alk

Proiect (posibil pentru licenta): dezvoltarea unei interfete specifice pentruAlk.



Precizarea configuratiei initiale

Pentru executia unui algoritm, trebuie precizata configuratia initiala, care constadin program si starea memoriei.

Urmatorul exemplu este un generator de numere pseudo-aleatorii din cartea TheC Programming Language de Kernighan and Ritchie.

rand() {

random_seed = random_seed * 1103515245 +12345;

return (random_seed / 65536) % 32768;

}

x = rand();

y = rand();

Deoarece random seed este variabila globala, valoarea ei initiala trebuieprecizata n starea initialaa (ST):

krun programs/random.alk -c ST="random_seed |-> 1212"



Obtinerea configuratiei finale

Configuratia finala se obtine prin urmatoarea comanda:

$ krun programs/random.alk -cST=".Map" -cGST="random_seed |-> 1212"

.K

rand |-> lambda ( @ random_seed = ((random_seed * 1103515245) + 12345) ;

return ((random_seed / 65536) % 32768) ; )

random_seed |-> 1475908039511156662170

x |-> 26331

y |-> 19887

Componentele unei confiratii n K sunt celule, descrise cu o sintaxa inspirata din

XML. Celula S include lista de activitati S de executat (n cpnfiguratia

initiala ea include programul), iar celula include starea

memoriei . Functiile program sunt memorate ca lambda-expresii.D. Lucanu (FII - UAIC) Limbajul Algoritmic PA 2014/2015 52 / 57


Exemplu de algoritm n Alk: DFS nerecursiv

/*This example includes the nonrecursive version of the DFS algorithm.@input: a digraf D and a vertex i0@output: the list S of the verices reachable from i0

*/

i = 0;while (i < D.n) {p[i] = D.a[i];S[i] = 0;i = i + 1;

}SB = empty();SB.pushFront(i0);S[i0] = 1;

// visit i0while (SB.size() > 0) {i = SB.topFront();if (p[i].size() == 0) {SB.popFront();

}else {j = p[i].topFront();p[i].popFront();if (S[j] == 0) {// visit j;S[j] = 1;SB.pushFront(j);

}}

}



Executia algoritmului DFS nerecursiv

Presupunand ca digraful D este

D.n = 3

D.a[0] = (1,2)

D.a[1] = (2, 0)

D.a[2] = (0)

si ca varful de start i0 este 1, linia de comanda pentru executie va precizavaloarea lui D n starea locala (ST):

krun programs/dfsnerec.alk

-cST "D |-> { n |-> 3

a |-> { 0 |-> [1, 2]

1 |-> [2, 0]

2 |-> [0] } }

i0 |-> 1

p |-> { .Map }

S |-> { .Map }"



Exemplu de algoritm n Alk: DFS recursiv

/*This example includes the recursive version of the DFS algorithm.@input: a digraf D and a vertex i0@output: the list S of the verices reachable from i0

*/

// the recursive functiondfsRec(i) {if (S[i] == 0) {// visit iS[i] = 1;p = D.a[i];while (p.size() > 0) {j = p.topFront();p.popFront();dfsRec(j);

}}

}

// the calling programi = 0;while (i < D.n) {S[i] = 0;i = i + 1;

}dfsRec(1);



Executia algoritmului DFS recursiv

Este similara cu a variantei nerecursive:

krun programs/dfsrec.alk

-cST "D |-> { n |-> 3

a |-> { 0 |-> [1, 2]

1 |-> [2, 0]

2 |-> [0] } }

i0 |-> 1

p |-> { .Map }

S |-> { .Map }"



Demo

Executia algoritmilor de mai sus cu interfata online.


IntroducereLimbajul AlkModelul de memorieOperatiiExpresii si instructiuni


[1] limb-alg

Documents

Transcript of [1] limb-alg