Descrierea algoritmilor, limbaj algoritmic

Descrierea algoritmilor, limbaj algoritmic

Limbajul algoritmic (pseudocod) permite folosirea unor instructiuni care contin structuri de aza, usurand astfel atat scrierea cat si intelegerea algoritmilor.
Prin program in limbaj algoritmic intelegem o succesiune de instructiuni. Instructiunile pot fi declaratii sau instructiuni efective.
O declaratie este formata din unul din cuvintele cheie intreg, real, logic, caracter urmat de un sir de variabile separate prin virgula, intelegand ca variabilele au tipul respectiv.
Instructiuni efective
1. Instructiuni de citire/scriere
citeste v1, v2, ..., vn // v1, v2, ..., vn sunt variabile
scrie e1, e2, ..., en // e1, e2, ...., en sunt expresii
2. Instructiunea stop
3. Instructiunea de atribuire
variabila <- expresie
Efectul instructiunii este evaluarea expresiei si atribuirea rezultatului obtinut variabilei.
Putem admite si forma mai generala:
(v1, v2, ...., vn) <- (e1, e2, ..., en)
care realizeaza simultan atribuirile vi<-ei, i fiind inclus in {1, 2, ..., n}
4. Instructiunea de ramificare (structura alternativa)
daca E atunci S1
altfel S2
sf - daca
Efectul instructiunii este evaluarea expresiei E si executarea secventei de instructiuni S1 sau S2 dupa cum E este adevarata sau falsa.
5. Instructiunea repetitiva cat timp (structura repetitiva cu test initial)
cat timp E executa
S
sf-cat timp
Efectul instructiunii este executia repetitiva a secventei de instructiuni S cat timp expresia logica E este adevarata.
Teorema de structura a lui Bohm si Jacopini asigura suficienta acestor structuri, insa in practica s-au impus si urmatoarele structuri derivate:
6. Instructiunea de ramificare cu o ramura vida
daca E atunci S1
sf-daca
7. Instructiunea de selectie multipla
alege E dintre
C1:S1
C2:S2
.........
Cn:Sn
rest: Sn+1
Efectul instructiunii este evaluarea expresiei E si executarea secventei de instructiuni Si daca E este egala cu constanta Ci sau Sn+1 daca E nu coincide cu valoarea niciunei constante.
8. Instructiunea repetitiva repeta - pana cand (structura repetitiva cu test final)
repeta
S
pana cand E
Efectul instructiunii este executia repetata a secventei de instructiuni S pana cans expresia E devine adevarata.

9. Instructiunea repetitiva pentru (structura repetitiva cu numar cunoscut de pasi).
a) pentru contor <- val_init, val_fin executa
S
sf-pentru
Efectul instructiunii este executia repetata a secventei de instructiuni S pentru fiecare valoare a contorului cuprinsa intre val_init si val_fin. Pentru ca secventa de instructiuni S sa se execute macar o data trebuie ca val_init sa fie mai mic sau egal cu val_fin, in acest caz numarul de repetari este val_fin-val_init+1.
b) pentru contor <- val_init, val_fin, -1 executa
S
sf-pentru
Efectul instructiunii este executia repetata a secventei de instructiuni S pentru fiecare valoare a contorului cuprinsa intre val_init si val_fin. Pentru ca secventa de instructiuni S sa se execute macar o data trebuie ca val_init sa fie mai mare sau egala cu val_fin, in acest caz numarul de repetari este val_init - val_fin + 1.

Analiza complexitatii unui algoritm

Eficienta unui algoritm se evalueaza din doua puncte de vedere:
1. Din punct de vedere al spatiului de memorie necesar pentru memorarea valorilor care intervin in algoritm (complexitatea spatiu).
2. Din punctul de vedere al timpului de executie (complexitatea timp). Timpul de executie al unui program depinde de numarul de operatii elementare efectuate de algoritm (consideram ca operatie elementara una din operatiile: citire, scriere, atribuire, comparatie, operatie aritmetica).

Echivalenta algoritmilor

Doi algoritmi sunt echivalenti daca pentru acelasi set de date de intrare returneaza acelasi rezultat. Putem simula o structura repetitiva cu ajutorul unor secvente de instructiuni care contin alte tipuri de structuri repetitive.

Structura repetitiva	Secventa echivalenta
repeta S1 pana cand E	S1 cat timp ! E executa S1 sf-cat timp
cat timp E executa S1 sf-cat timp	daca E atunci repeta S1 pana cand !E
Pentru contor <- val_init, val_fin executa S1 sf-pentru	contor <- val_init cat timp contor <= val_fin executa S1 contor <- contor+1 sf-cat timp