Limbajul Algoritmic

S
t. Ciobaca, Dorel Lucanu

Faculty of Computer Science

Alexandru Ioan Cuza University, Iasi, Romania
stefan.ciobaca@info.uaic.ro, dlucanu@info.uaic.ro

PA 2016/2017

S
t. Ciob
ac
a, D. Lucanu (FII - UAIC) Limbajul Algoritmic PA 2016/2017 1 / 55
 Outline

1 Introducere

2 Limbajul Alk
Modelul de memorie
Valori
Operatii
Expresii si instructiuni
Sintaxa
Semantica

3 Testarea algoritmilor cu K Framework

S
t. Ciob
ac
a, D. Lucanu (FII - UAIC) Limbajul Algoritmic PA 2016/2017 2 / 55
 Introducere

Plan

1 Introducere

2 Limbajul Alk
Modelul de memorie
Valori
Operatii
Expresii si instructiuni
Sintaxa
Semantica

3 Testarea algoritmilor cu K Framework

S
t. Ciob
ac
a, D. Lucanu (FII - UAIC) Limbajul Algoritmic PA 2016/2017 3 / 55
 Introducere

Ce este un algoritm?

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, 6nd

edition):
An algorithm is ordered sequence of instructions that is guaranteed to solve a specific
problem.

S
t. Ciob
ac
a, D. Lucanu (FII - UAIC) Limbajul Algoritmic PA 2016/2017 4 / 55
 Introducere

Ce este un algoritm?

Wikipedia:

In mathematics and computer science, an algorithm is a step-by-step procedure for

calculations. Algorithms are used for calculation, data processing, and automated
reasoning.
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.

S
t. Ciob
ac
a, D. Lucanu (FII - UAIC) Limbajul Algoritmic PA 2016/2017 5 / 55
 Introducere

Ingredientele de baza: model de calcul, problema rezolvata

Toate aceste definitii au ceva n comun:

un model de calcul format din:
memorie
instructiuni
sintax
a
semantic
a

trebuie sa rezolve o problema

Formalizarea notiunii de problema: o pereche (input,output)

S
t. Ciob
ac
a, D. Lucanu (FII - UAIC) Limbajul Algoritmic PA 2016/2017 6 / 55
 Introducere

Cum descriem un algoritm?

Exista o varietate larga de moduri n care poate fi descris un algoritm:

informal: limbaj natural
formal
notatie matematica
limbaje de programare
semiformal
pseudo-cod
notatie grafica

S
t. Ciob
ac
a, D. Lucanu (FII - UAIC) Limbajul Algoritmic PA 2016/2017 7 / 55
 Introducere

De ce este nevoie de formalizare?

nainte de secolul 20 matematicienii au utilizat notiunea de algoritm

doar la nivel intuitiv
n 1900, David Hilbert, la Congresul matematicienilor din Paris, a
formulat 23 de probleme ca provocari ale secolului
problema a 10-a cerea gasirea unui proces care sa determine daca un
polinom cu coeficienti ntregi are o radacina ntreaga
Hilbert nu a pronuntat termenul de algoritm

S
t. Ciob
ac
a, D. Lucanu (FII - UAIC) Limbajul Algoritmic PA 2016/2017 8 / 55
 Introducere

De ce nevoie de formalizare?

problema a 10-a a lui Hilbert este nerezolvabila

acest fapt nu se poate demonstra avand doar notiunea intuitiva de
algoritm
pentru a demonstra ca nu exista algoritm care rezolva o problema,
este necesara o notiune formala

S
t. Ciob
ac
a, D. Lucanu (FII - UAIC) Limbajul Algoritmic PA 2016/2017 9 / 55
 Introducere

Formalizarea notiunii de algoritm

Alonso Church, 1936: -calcul

Alan Turing, 1936: masini Turing
cele doua modele de calcul sunt echivalente
n 1970 Yuri Matijasevic a aratat ca problema a 10-a a lui Hibert este
nerezolvabila
de atunci au aparut multe alte modele echivalente cu masinile Turing

S
t. Ciob
ac
a, D. Lucanu (FII - UAIC) Limbajul Algoritmic PA 2016/2017 10 / 55
 Introducere

Teza Church-Turing

Teza lui Turing:

hhLCMs [logical computing machines: Turings expression for Turing machines]
can do anything that could be described as rule of thumb or purely
mechanical.ii (Turing 1948)
Teza lui Church:
hhA function of positive integers is effectively calculable only if recursive.ii

Kleene (1967) este cel care a introdus termenul de Teza Church-Turing:

So Turings and Churchs theses are equivalent. We shall usually refer to them
both as Churchs thesis, or in connection with that one of its . . . versions which
deals with Turing machines as the Church-Turing thesis.

S
t. Ciob
ac
a, D. Lucanu (FII - UAIC) Limbajul Algoritmic PA 2016/2017 11 / 55
 Introducere

Nivelul de formalizare

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

masinile Turing, lambda-calculul, functiile recursive usor de definit
matematic, dar greu de utilizat
limbajele de programare usor de utilizat n practica dar dificil de
manevrat n demonstratii
cel mai simplu limbaj de programare echivalent cu masinile Turing:
counting machines
o varianta structurata : programele while

S
t. Ciob
ac
a, D. Lucanu (FII - UAIC) Limbajul Algoritmic PA 2016/2017 12 / 55
 Limbajul Alk

Plan

1 Introducere

2 Limbajul Alk
Modelul de memorie
Valori
Operatii
Expresii si instructiuni
Sintaxa
Semantica

3 Testarea algoritmilor cu K Framework

S
t. Ciob
ac
a, D. Lucanu (FII - UAIC) Limbajul Algoritmic PA 2016/2017 13 / 55
 Limbajul Alk

Motivatie

Scopul nostru este de a avea un limbaj care este

destul de simplu pentru a fi nteles;
suficient de expresiv;
abstract;
sa ofere un model de calcul riguros definit si potrivit pentru analiza
algoritmilor;
executabil;
intrarile si iesirile sunt reprezentate abstract, ca obiecte matematice.
Un candidat care satisface aceste cerinte este Alk (limbaj specific acestui
curs).

S
t. Ciob
ac
a, D. Lucanu (FII - UAIC) Limbajul Algoritmic PA 2016/2017 14 / 55
 Limbajul Alk Modelul de memorie

Plan

1 Introducere

2 Limbajul Alk
Modelul de memorie
Valori
Operatii
Expresii si instructiuni
Sintaxa
Semantica

3 Testarea algoritmilor cu K Framework

S
t. Ciob
ac
a, D. Lucanu (FII - UAIC) Limbajul Algoritmic PA 2016/2017 15 / 55
 Limbajul Alk Modelul de memorie

Modelul de memorie
memoria este data de o multime de variabile
o variabila este o pereche:
notatie matematica nume-variabila 7 valoare

valoare
notatie grafica nume-variabila
o valoare va fi o constanta a unui tip de date
exemple de tipuri de valori:
scalare
tablouri
structuri
liste
...
Val desemneaza multimea tuturor valorilor

S
t. Ciob
ac
a, D. Lucanu (FII - UAIC) Limbajul Algoritmic PA 2016/2017 16 / 55
 Limbajul Alk Modelul de memorie

Exemple de variabile

notatie matematica b 7 true i 7 5 a 7 [3, 0, 8]

true 5 0 1 2
notatie grafica b i 3 0 8
a

Fiecare notatie este scrierea simplificata (fara numele intermediar al

functiei) al unei functii : {b, i, . . .} Val data prin (b) = true,
(i) = 5, . . .

S
t. Ciob
ac
a, D. Lucanu (FII - UAIC) Limbajul Algoritmic PA 2016/2017 17 / 55
 Limbajul Alk Valori

Plan

1 Introducere

2 Limbajul Alk
Modelul de memorie
Valori
Operatii
Expresii si instructiuni
Sintaxa
Semantica

3 Testarea algoritmilor cu K Framework

S
t. Ciob
ac
a, D. Lucanu (FII - UAIC) Limbajul Algoritmic PA 2016/2017 18 / 55
 Limbajul Alk Valori

Dimensiunea valorilor

Tip de data = valori (constante) + operatii

Fiecare valoare (constanta) este reprezentata utilizand un spatiu de
memorie.
Pentru valorile (obiectele) fiecarui tip trebuie precizata lungimea
(dimensiunea) reprezentarii obiectelor.
Exista doua moduri de a defini lungimea reprezentarii:
uniform: |v |unif
logaritmic: |v |log

S
t. Ciob
ac
a, D. Lucanu (FII - UAIC) Limbajul Algoritmic PA 2016/2017 19 / 55
 Limbajul Alk Valori

Scalari

tipurile primitive: valorile boolene, numerele ntregi, numerele rationale

(virgula mobila), siruri,. . .
O caracteristica importanta pentru valorile scalare: admit reprezentari
finite.

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

S
t. Ciob
ac
a, D. Lucanu (FII - UAIC) Limbajul Algoritmic PA 2016/2017 20 / 55
 Limbajul Alk Valori

Scalari (cont)

ntregi:
Int = {. . . , 2, 1, 0, 1, 2, . . .}
dimensiunea uniforma: |n|unif = 1
dimensiunea logaritmica: |n|log = log2 n
booleeni:
Bool = {false, true}
dimensiunea uniforma: |b|unif = 1
dimensiunea logaritmica: |b|log = 1
numere rationale:
Float = numerele rationale
dimensiunea uniforma: |v |unif = 1
dimensiunea logaritmica: |v |log = log2 (mantis
a) + log2 (exponent)
...
Avem Int Bool Float . . . Val.
S
t. Ciob
ac
a, D. Lucanu (FII - UAIC) Limbajul Algoritmic PA 2016/2017 21 / 55
 Limbajul Alk Valori

Tablouri (unidimensionale)

a = [a0 , a1 , . . . , an1 ]
|a|d = |a0 |d + |a1 |d + + |an1 |d , d {unif, log}
Arr n hV i = {{0 7 v0 , . . . , n1 7 vn1 | vi V , i = 0, . . . , n1}
S
n1 Arr n hV i Val pentru fiecare tip V Val
tablourile bidimensionale sunt tablouri unidimensionale de tablouri
unidimensionale,
tablourile tridimensionale sunt tablouri unidimensionale de tablouri
bidimensionale,
etc.

S
t. Ciob
ac
a, D. Lucanu (FII - UAIC) Limbajul Algoritmic PA 2016/2017 22 / 55
 Limbajul Alk Valori

Structuri

Exemplu: punctul de coordonate (2, 7) este reprezentat de structura

{x 2 y 7}.
multimea de campuri: F = {f1 , . . . , fn }
s = {f1 v1 , . . . , fn vn }
|s|d = |v0 |d + |v1 |d + + |vn1 |d , d {unif, log}
Str hf1 :V1 , . . . fn :Vn i = {{f1 v1 , . . . , fn vn } | v1 V1 , . . . , fn Vn }
Exemplu (Fixed Size Linear Lists):
FSLL = {len, arr}
Str hlen : Int, arr : Arr 100 hIntii =
{{len n arr a} | n Int, a Arr 100 hInti}
Str hf1 :V1 , . . . fn :Vn i Val pentru fiecare structura F = {f1 :V1 , . . . fn :Vn }.

S
t. Ciob
ac
a, D. Lucanu (FII - UAIC) Limbajul Algoritmic PA 2016/2017 23 / 55
 Limbajul Alk Valori

Liste liniare

O valoare de tip lista liniara este o secventa de valori

l = hv0 , v1 , . . . , vn1 i.
|l|d = |v0 |d + |v1 |d + + |vn1 |d , d {unif, log}
LLinhV i = {hv0 , . . . , vn1 i | vi V , i = 0, . . . , n}
Exemple: LLinhInti, LLinhArr n i, LLinhArr n hFloatii
Avem LLinhV i Val pentru fiecare tip V .

S
t. Ciob
ac
a, D. Lucanu (FII - UAIC) Limbajul Algoritmic PA 2016/2017 24 / 55
 Limbajul Alk Valori

Valori complexe: grafuri

Graful G = ({0, 1, 2, 3}, {(0, 1), (0, 2), (0, 3), (1, 2)}) este reprezentat prin
liste de adiacenta de urmatoarea valoare:
{
n4
a [h1, 2, 3i, h0, 2i, h0, 1i, h0i]
}

S
t. Ciob
ac
a, D. Lucanu (FII - UAIC) Limbajul Algoritmic PA 2016/2017 25 / 55
 Limbajul Alk Operatii

Plan

1 Introducere

2 Limbajul Alk
Modelul de memorie
Valori
Operatii
Expresii si instructiuni
Sintaxa
Semantica

3 Testarea algoritmilor cu K Framework

S
t. Ciob
ac
a, D. Lucanu (FII - UAIC) Limbajul Algoritmic PA 2016/2017 26 / 55
 Limbajul Alk Operatii

Tip de date (cont.)

Tip de data = constante + operatii

Fiecare operatie op are un cost timp time(op).

Pentru fiecare operatie a unui tip trebuie precizat timpul.

Exista doua moduri de a defini timpul (mostenite de la lungimea

reprezentarii):
uniform: timeunif (op) utilizeaza dimensiunea uniforma
logaritmic: timelog (op) utilizeaza dimensiunea logaritmica

S
t. Ciob
ac
a, D. Lucanu (FII - UAIC) Limbajul Algoritmic PA 2016/2017 27 / 55
 Limbajul Alk Operatii

Operatii cu scalari

Intregi:
Operatie timeunif (op) timelog (op)
a +Int b O(1) O(max(log a, log b))
O(log a log b)
a Int b O(1)
O(max(log a, log b)1.545 )
... ... ...

S
t. Ciob
ac
a, D. Lucanu (FII - UAIC) Limbajul Algoritmic PA 2016/2017 28 / 55
 Limbajul Alk Operatii

Tablouri

Operatie timeunif (op) timelog (op)

A.lookup(i) O(1) O(i + log ai )
A.update(i, v ) O(1) O(i + log v )
unde am presupus A 7 [a0 , . . . , an1 ]

S
t. Ciob
ac
a, D. Lucanu (FII - UAIC) Limbajul Algoritmic PA 2016/2017 29 / 55
 Limbajul Alk Operatii

Structuri

Operatie timeunif (op) timelog (op)

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

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

S
t. Ciob
ac
a, D. Lucanu (FII - UAIC) Limbajul Algoritmic PA 2016/2017 30 / 55
 Limbajul Alk Operatii

Liste liniare: definitie operatii

empty() ntoarce lista vida []

L.topFront() ntoarce v0
L.topBack() ntoarce vn1
L.lookup(i) ntoarce vi
L.insert(i,x) ntoarce [. . . vi1 , x, vi , . . .]
L.remove(i,x) ntoarce [. . . vi1 , vi+1 , . . .]
L.size() ntoarce n
L.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 ]

S
t. Ciob
ac
a, D. Lucanu (FII - UAIC) Limbajul Algoritmic PA 2016/2017 31 / 55
 Limbajul Alk Operatii

Liste liniare: operatii (versiunea 1)

- corespunde implementarii cu tablouri

Operatie timeunif (op) timelog (op)
L.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) ?

S
t. Ciob
ac
a, D. Lucanu (FII - UAIC) Limbajul Algoritmic PA 2016/2017 32 / 55
 Limbajul Alk Operatii

Liste liniare: operatii (versiunea 2)

- corespunde implementarii cu liste dublu nlantuite

Operatie timeunif (op) timelog (op)
L.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) ?

S
t. Ciob
ac
a, D. Lucanu (FII - UAIC) Limbajul Algoritmic PA 2016/2017 33 / 55
 Limbajul Alk Operatii

Liste liniare: operatii (versiunea 3?)

- Exista o lista liniara cu urmatoarele proprietati?

Operatie timeunif (op) timelog (op)
L.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) ?

S
t. Ciob
ac
a, D. Lucanu (FII - UAIC) Limbajul Algoritmic PA 2016/2017 34 / 55
 Limbajul Alk Expresii si instructiuni

Plan

1 Introducere

2 Limbajul Alk
Modelul de memorie
Valori
Operatii
Expresii si instructiuni
Sintaxa
Semantica

3 Testarea algoritmilor cu K Framework

S
t. Ciob
ac
a, D. Lucanu (FII - UAIC) Limbajul Algoritmic PA 2016/2017 35 / 55
 Limbajul Alk Expresii si instructiuni

Expresii: sintaxa

Sintaxa este foarte apropiata de cea limbajului C++:

expresii aritmetice: a * b + 2
expresii relationale: a < 5
expresii booleene: (a < 5) && (a > -1)
expresii peste multimi: s1 U s2 s1 ^ s2 s1 \ s2
apel de functie: f(a*2, b+5)
apel operatii peste liste, multimi, tablouri:
l.update(2,55) l.size()

S
t. Ciob
ac
a, D. Lucanu (FII - UAIC) Limbajul Algoritmic PA 2016/2017 36 / 55
 Limbajul Alk Expresii si instructiuni

Instructiuni: sintaxa

atribuire a = E ; a[i] = E ; p.x = E ;

apeluri de functii: quicksort(a); l.insert(2,77);
bloc: { Sts }
instructiuni conditionale:
if ( E ) St
if ( E ) St 1 else St 2
instructiuni repetitive:
while ( E ) St
forall X in S St
for ( X = E ; E ; ++X ) S
return: return E ;
compunerea secventiala: St 1 St 2
Alk este extensibil: pot fi adaugate noi expresii si instructiuni, cu precizari
pentru costul timp
S
t. Ciob
ac
a, D. Lucanu (FII - UAIC) Limbajul Algoritmic PA 2016/2017 37 / 55
 Limbajul Alk Expresii si instructiuni

Tipuri de date

Sunt predefinite n Alk.

Presupunem existenta unei metainformatii care mentioneaza tipul fiecarei

variabile (nu exista declaratii de variabile).

S
t. Ciob
ac
a, D. Lucanu (FII - UAIC) Limbajul Algoritmic PA 2016/2017 38 / 55
 Limbajul Alk Expresii si instructiuni

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 vertices reachable from i0
*/

// the recursive function

dfsRec(i) {
if (S[i] == 0) {
// visit i // the calling program
S[i] = 1; i = 0;
p = D.a[i]; while (i < D.n) {
while (p.size() > 0) { S[i] = 0;
j = p.topFront(); i = i + 1;
p.popFront(); }
dfsRec(j); dfsRec(1);
}
}
}

S
t. Ciob
ac
a, D. Lucanu (FII - UAIC) Limbajul Algoritmic PA 2016/2017 39 / 55
 Limbajul Alk Expresii si instructiuni

Evaluarea expresiilor

Consideram o functie [[ ]]( ) : Expresii (Stare Valori), unde [[E ]]() ntoarce
valoarea expresiei E calculata n starea .
Exemplu: Fie o stare ce include a 7 3 b 7 6. Avem:
[[a + b 2]]() =
[[a]]() +Int [[b 2]]()=
3 +Int [[b]]() Int [[2]]()=
3 +Int 6 Int 2 =
3 +Int 12 = 15 unde +Int reprezinta algoritmul de adunare peste ntregi si Int
reprezinta algoritmul de nmultire peste ntregi.

S
t. Ciob
ac
a, D. Lucanu (FII - UAIC) Limbajul Algoritmic PA 2016/2017 40 / 55
 Limbajul Alk Expresii si instructiuni

Calculul timpului pentru evaluare

time d ([[a + b 2]]()) =

time d ([[a]]()) + time d ([[b]]()) + time d (6 Int 2) + time d (3 +Int 12),
d {unif, log}.

include a 7 3 b 7 6
time log ([[a]]()) = log 3, time log ([[b]]()) = log 6
time unif ([[a]]()) = 1, time unif ([[b]]()) = 1

S
t. Ciob
ac
a, D. Lucanu (FII - UAIC) Limbajul Algoritmic PA 2016/2017 41 / 55
 Limbajul Alk Expresii si instructiuni

Configuratii

O configuratie este o pereche hsecventa-de-program, starei

Exemple:
hx = x + 1; y = y + 2 * x;, x 7 7 y 7 12i
hs = 0; while (x > 0) {s = s+x; x = x-1;}, x 7 5 s 7 15i

S
t. Ciob
ac
a, D. Lucanu (FII - UAIC) Limbajul Algoritmic PA 2016/2017 42 / 55
 Limbajul Alk Expresii si instructiuni

Pasi de executie

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

hS, i hS 0 , 0 i
daca si numai daca
executand prima instructiune secventa din S n starea obtinem secventa
S 0 , ce urmeaza a fi executata n continuare, si o noua stare 0

Pasii de executie sunt descrisi prin reguli hS1 , 1 i hS2 , 2 i, unde

S1 , S2 , 1 , 2 sunt termeni cu variabile (patterns).
Pentru a putea calcula costul timp al unui pas de executie, vom preciza
costul dat de aplicarea unei reguli.

S
t. Ciob
ac
a, D. Lucanu (FII - UAIC) Limbajul Algoritmic PA 2016/2017 43 / 55
 Limbajul Alk Expresii si instructiuni

Instructiuni: semantica

atribuirea: x = E ;
informal: se evalueaza E si rezultatul este atribuit ca noua valoare a
variabilei x
formal:
hx = E ;S, }i hS, 0 i
unde este de forma . . . x 7 v . . . si 0 de forma . . . x 7 [[E]]() . . .
(n rest la fel ca ).

Costul timp:
time unif (hx = E ;S, i hS, 0 i) = time unif ([[E ]]()) + 1,
time log (hx = E ;S, i hS, 0 i) = time log ([[E ]]() + log[[E ]]()).

S
t. Ciob
ac
a, D. Lucanu (FII - UAIC) Limbajul Algoritmic PA 2016/2017 44 / 55
 Limbajul Alk Expresii si instructiuni

Instructiuni: semantica

if: if (E ) then S else S 0

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

formal:
hif (E ) then S else S 0 S 00 , i hS S 00 , i daca [[E ]]() = true
hif (E ) then S else S 0 S 00 , i hS 0 S 00 , i daca [[E ]]() = false

Costul timp:
time d (hif (E ) then S 0 else S 00 S, i h , i) = time d ([[E ]]())
d {unif, log}.

S
t. Ciob
ac
a, D. Lucanu (FII - UAIC) Limbajul Algoritmic PA 2016/2017 45 / 55
 Limbajul Alk Expresii si instructiuni

Instructiuni: semantica

while: while (E ) S
informal: se evalueaza e; daca rezultatul obtinut este true, atunci se
executa S, dupa care se evalueaza din nou e si . . . ; altfel executia
instructiunii se termina
formal: se exprima cu ajutorul lui if:
hwhile (e) S S 0 , i
hif (e) { S ; while (e) S } else { }S 0 , i

Costul timp:
time d (hwhile (E ) then S else S 0 S, i hif (e) ...S, i) = 0,
d {unif, log}.

S
t. Ciob
ac
a, D. Lucanu (FII - UAIC) Limbajul Algoritmic PA 2016/2017 46 / 55
 Limbajul Alk Expresii si instructiuni

Apelul de functie

Presupunem functia f(a,b) { Sf }. Evaluarea apelului f(e1 ,e2 )

presupune urmatorii pasi:
hf(e1 , e2 ) S, , Stacki
hSf , {a 7 [[e1 ]]() b 7 [[e2 ]]()}, (S, ) Stacki
hv , 0 , (S, ) Stacki
hv S, updateGlobals(, 0 ), Stacki
Presupunere: costul unui apel este suma dintre costul evaluarii
argumentelor actuale si costul executiei corpului functiei.

S
t. Ciob
ac
a, D. Lucanu (FII - UAIC) Limbajul Algoritmic PA 2016/2017 47 / 55
 Limbajul Alk Expresii si instructiuni

Calcul (executie)

Un calcul (o executie) este o secventa de pasi:

= hS1 , 1 i hS2 , 2 i hS3 , 3 i . . .

Costul unui Pcalcul:

time d ( ) = i time d (hSi , i i hSi+1 , i+1 i), d {unif , log }

S
t. Ciob
ac
a, D. Lucanu (FII - UAIC) Limbajul Algoritmic PA 2016/2017 48 / 55
 Limbajul Alk Expresii si instructiuni

Calcul: exemplu

hif (x > 3) x = x + y; else x = 0; y = 4; , x 7 7 y 7 12i

hx = x + y; y = 4; , x 7 7 y 7 12i
hy = 4; , x 7 19 y 7 12i
h, x 7 19 y 7 4i
Am utilizat:
[[x > 3]](x 7 7 y 7 12) = true
[[x + y]](x 7 7 y 7 12) = 19
[[4]](x 7 19 y 7 12) = 4
Costul:
cost uniform: 3 (= numarul de pasi)
cost logaritmic: log 7 + log 7 + log 12 + log 19 + log 4

S
t. Ciob
ac
a, D. Lucanu (FII - UAIC) Limbajul Algoritmic PA 2016/2017 49 / 55
 Limbajul Alk Expresii si instructiuni

Calcul: exemplu

hwhile (i > 5) i--; , i 7 6 x 7 12i

hif (i > 5) { i --; while (i > 5) i--; }, i 7 1 x 7 12i
h{i --; while (i > 5) i--; } , i 7 6 x 7 12i
hi --; while (i > 5) i--; , i 7 6 x 7 12i
hwhile (i > 5) i--; , i 7 5 x 7 12i
h, i 7 5 x 7 12i
Am utilizat:
[[i > 5]](i 7 6 x 7 12) = true
[[i ]](i 7 6 x 7 12) = 0
[[i > 5]](i 7 5 x 7 12) = false
Costul timp:
cost uniform: 4 (= numarul de pasi, exceptand primul)
cost logaritmic: log 6 + log 6 + log 5 + log 5

S
t. Ciob
ac
a, D. Lucanu (FII - UAIC) Limbajul Algoritmic PA 2016/2017 50 / 55
 Testarea algoritmilor cu K Framework

Plan

1 Introducere

2 Limbajul Alk
Modelul de memorie
Valori
Operatii
Expresii si instructiuni
Sintaxa
Semantica

3 Testarea algoritmilor cu K Framework

S
t. Ciob
ac
a, D. Lucanu (FII - UAIC) Limbajul Algoritmic PA 2016/2017 51 / 55
 Testarea algoritmilor cu K Framework

Testarea algoritmilor cu K Framework

K Framework (www.kframework.org) este un mediu de lucru pentru

definitii de limbaje de programare. Definitiile K sunt executabile.

Definitia K a lui Alk se gaseste la adresa

https://github.com/kframework/alk-semantics
si poate fi compilata cu K versiunea 3.6:
https://github.com/kframework/k/releases
O copie actualizata va fi accesibila de pe pagina cursului.
Compilarea definitiei limbajului Alk:
kompile alk
Proiecte (posibil pentru licenta):
1. implementare C++ a definitiei lui Alk;
2. dezvoltarea unei interfete specifice pentru definitia lui Alk.

S
t. Ciob
ac
a, D. Lucanu (FII - UAIC) Limbajul Algoritmic PA 2016/2017 52 / 55
 Testarea algoritmilor cu K Framework

Executia algoritmului DFS recursiv

Starea initiala este data ca valoare a optiunii init:

alki dfsrec.alk \
--init="D |-> { n -> 3
a -> [ < 1, 2 >, < 2, 0 >, < 0 > ] }
i0 |-> 1"

S
t. Ciob
ac
a, D. Lucanu (FII - UAIC) Limbajul Algoritmic PA 2016/2017 53 / 55
 Testarea algoritmilor cu K Framework

Obtinerea configuratiei finale

Configuratia finala obtinuta prin comanda precedenta este:

State:

D |-> { (n -> 3) (a -> ([ (< 1, 2 >), (< 2, 0 >), (< 0 >) ])) }
i0 |-> 1
reached |-> [ 1, 1, 1 ]

S
t. Ciob
ac
a, D. Lucanu (FII - UAIC) Limbajul Algoritmic PA 2016/2017 54 / 55
 Testarea algoritmilor cu K Framework

Demo

Executia algoritmilor de mai sus.

S
t. Ciob
ac
a, D. Lucanu (FII - UAIC) Limbajul Algoritmic PA 2016/2017 55 / 55