Limbaje de programare

inginereti

Curs 3

Algoritmi

Scurt istoric

Algoritm: -pronuntia fonetica: Abu Ja`far Mohammed ibn Musa al-Khowarizmi (780-850); al-Khowarizmi (din orasul Khowarizm)

Algoritmul lui Euclid Definitii:

Prin algoritm se nelege o metod de soluionare a unei clase de probleme, reprezentat de o succesiune finit de operaii bine definite, numite instruciuni

Prin algoritm vom nelege o secven finit de comenzi explicite i

neambigue care executate pentru o mulime de date (ce satisfac anumite condiii iniiale) conduce n timp finit la rezultatul corespunztor.

Caracteristicile algoritmilor

1. Generalitate

Un algoritm destinat rezolvrii unei probleme trebuie s

permit obinerea rezultatului pentru orice date de intrare i

nu numai pentru date particulare de intrare.

Exemplu:

3x2-5x+7=0 ax2+bx+c=0, a,b,cR, a0 a,b,cR

Caracteristicile algoritmilor

2. Rigurozitate (Unicitate)

Prelucrrile algoritmului trebuie specificate riguros, fr

ambiguiti. n orice etap a execuiei algoritmului trebuie s

se tie exact care este urmtoarea etap ce va executat.

Toate transformrile prin care trece informaia iniial pentru

a obine rezultatul r sunt bine determinate de regulile

algoritmului. Fiecare pas din execuia algoritmului d

rezultate bine determinate i precizeaz n mod unic pasul

urmtor. Altfel spus, ori de cte ori am executa algoritmul,

pornind de la aceeai informaie admisibil x, transformrile

prin care se trece i rezultatele obinute sunt aceleai.

3. Finitudine

Prin finitudine se nelege c textul algoritmului este finit,

compus dintr-un numr finit de propoziii.

Mai mult, numrul transformrilor ce trebuie aplicate unei

informaii admisibile x pentru a obine rezultatul final

corespunztor este finit.

Finitudine

Clase de algoritmi:

Algoritmi cu numr finit de pai, a priori cunoscut

Algoritmi cu numr finit de pai, a posteriori cunoscut

Algoritmi cu numr infinit de pai

Produs scalar ntre dou mulimi

CMMDC ntre dou numere

Numerele prime pn la o limit dat

Rezolvarea unei ecuaii transcendente

Numrarea unor elemente care ndeplinesc o condiie dat

4. Eficien

Eficien. Algoritmii pot fi efectiv utilizai doar dac

folosesc resurse de calcul n volum acceptabil.

Prin resurse de calcul se nelege volumul de memorie i

timpul necesar pentru execuie.

Reprezentarea algoritmilor

Limbaj natural

Pseudocod

Scheme logice

Diagrame arborescente

Tabele de decizie

Reprezentarea algoritmilor

prin scheme logice

Blocul START Blocul STOP

START STOP

Blocurile delimitatoare Start i Stop vor marca nceputul

respectiv sfritul unui algoritm dat printr-o schem logic.

Descrierea unui algoritm prin schem logic va ncepe cu un

singur bloc Start i se va termina cu cel puin un bloc Stop.

Reprezentarea algoritmilor

prin scheme logice

Blocul de citire Blocul de scriere

Citete date_de_intrare

Scrie date_de_iesire

Blocurile de intrare/ieire Citete i Tiprete indic

introducerea unor date de intrare respectiv extragerea unor

rezultate finale. Ele permit precizarea datelor iniiale

cunoscute n problem i tiprirea rezultatelor cerute de

problem.

Reprezentarea algoritmilor

prin scheme logice

Blocul de atribuire

v = e v e

Blocurile de atribuire (calcul) se utilizeaz n descrierea

operaiilor de atribuire. Printr-o astfel de operaie, unei

variabile var i se atribuie valoarea calculat a unei expresii

expr

Reprezentarea algoritmilor

prin scheme logice

Blocul de decizie

Conditie Da Nu

Expresie 0

=0

Blocurile de decizie marcheaz punctele de ramificaie ale algoritmului n

etapa de decizie. Ramificarea poate fi dubl (blocul logic) sau tripl (blocul

aritmetic). Blocul de decizie logic indic ramura pe care se va continua

execuia algoritmului n funcie de ndeplinirea sau nendeplinirea unei

condiii. Blocul de decizie aritmetic va hotr ramura de continuare a

algoritmului n funcie de semnul valorii expresiei aritmetice nscrise n

acest bloc.

Reprezentarea algoritmilor

prin pseudocod

Limbajul Pseudocod este un limbaj inventat n scopul proiectrii

algoritmilor i este format din propoziii asemntoare

propoziiilor limbii romne, care corespund structurilor de calcul

folosite n construirea algoritmilor. Pseudocodul conine un set

de cuvinte cheie.

Un algoritm scris n pseudocod este de fapt o succesiune de

instruciuni scrise n pseudocod.

Reprezentarea algoritmilor

prin pseudocod Instruciunile pseudocodului sunt:

1) Instruciunea de citire: citeste (a,b,c,) ;

2) Instruciunea de scriere (afiare): scrie (a,b,c,) ;

3) Instruciunea de atribuire: x : = y + 2 ;

4) Instruciunea alternativ: dac-atunci

dac condiie atunci

instruciune

altfel

instruciune ;

Reprezentarea algoritmilor

prin pseudocod Instruciunile pseudocodului sunt:

5) Instruciunea repetitiv: repet-pn cnd

repet

bloc de instruciuni

pn cnd condiie ;

6) Instruciunea repetitiv: ct timp-execut

ct timp condiie execut

bloc de instruciuni ;

7) Instruciunea repetitiv: pentru

pentru v=vin, vfin, p execut

bloc de instruciuni ;

Reprezentarea algoritmilor

prin pseudocod Observaii:

1. La terminarea unei instruciuni se pune " ; "

2. nainte de " altfel " nu se pune punct i virgul

3. La sfritul unei instruciuni alternative sau repetitive se

pune o linie sf

4. La nceputul i sfritul algoritmului se pun linii de

nceput i sfrit

Structuri de control

Structura secventiala (liniara)

s1

s2

sn

Structuri de control

Structura alternativa

Structura repetitiva cu conditionare anterioara

Structuri de control

c

s

Da

Nu

Structura repetitiva cu conditionare posterioara

Structuri de control

c

s

Da Nu

Structura repetitiva cu un numar cunoscut de pasi

Structuri de control

vvf

v=vi

Da

Nu

v=v+vr

s

Paii realizrii unui algoritm 1. Citirea cu atenie a enunului problemei.

2. Identificarea datelor de intrare i a celor de ieire.

3. Rezolvarea propriu-zis a problemei pe cazuri particulare i reprezentative. n acest moment nu se ncearc scrierea programului ci doar determinarea metodei de rezolvare, generalizarea i nelegerea acesteia.

4. Descrierea n limbaj natural a soluiei problemei. Dac nu suntei capabili s descriei metoda folosit n limbaj natural e puin probabil s o putei face ntr-un limbaj de programare care e mai restrictiv dect limbajul natural.

5. Scrierea algoritmului.

6. Testarea algoritmului.

Testarea se face pe mai multe seturi de date care s acopere cazurile posibile ce pot aprea.

1.Nu orice problem poate rezolvat algoritmic.

a. Fiind dat un numr n s se determine toi divizorii si.

Pentru aceast problem se poate scrie un algoritm foarte uor.

b. Fiind dat un numr n s se determine toi multiplii si.

Pentru aceast problem nu se poate scrie un algoritm deoarece nu cunoatem un criteriu de oprire a operaiilor.

2.Un algoritm trebuie s funcioneze pentru orice date de intrare.

Fiind date numerele a, b, c s se afieze maximul dintre ele.

O posibil soluie ar fi:

se compar a cu b i c i dac e mai mare se afieaz a, iar apoi

se compar b cu a i c i dac e mai mare se afieaz b, iar apoi

se compar c cu b i a i dac e mai mare se afieaz c

Algoritmul nu funcioneaz dac 2 valori sunt identice i de valoare maxim.

Probleme i condiii

3. Un algoritm trebuie sa se opreasc.

Se consider urmtoarea secven de prelucrri: Pas 1. Atribuie variabilei x valoarea 1;

Pas 2. Mreste valoarea lui x cu 2; Pas 3. Daca x este egal cu 100 atunci se oprete prelucrarea altfel se reia de la Pas 2.

Este usor de observat ca x nu va lua niciodat valoarea 100, deci succesiunea de prelucrri nu se termin niciodat. Din acest motiv nu poate considerat un algoritm corect.

4. Prelucrrile dintr-un algoritm trebuie s fie neambigue.

Consideram urmtoarea secven de prelucrri: Pas 1. Atribuie variabilei x valoarea 0;

Pas 2. Fie se mrete x cu 1 fie se micoreaz x cu 1; Pas 3. Daca x aparine [-10; 10] se reia de la Pas 2, altfel se oprete algoritmul.

Probleme i condiii

5. Un algoritm trebuie s se opreasc dup un interval rezonabil de timp.

Fiind dat un numr n se cere s se determine de cte ori a aprut o cifr c n reprezentarea tuturor numerelor naturale mai mici ca n.

O rezolvare simpl ar fi s lum toate numere mai mici ca n i s vedem de cte ori apare cifra c n fiecare dinte ele. Soluia e simpl i pentru valori mici ale lui n algoritmul se termin ntr-un interval de timp rezonabil, dar pentru valori mari timpul de terminare al algoritmului

crete nepermis de mult.

Probleme i condiii

Tipuri de algoritmi

n funcie de modul de implementare, un algoritm poate fi:

recursiv - face uz de sine nsui, n mod repetat

iterativ (repetitiv)

serial sau paralel

deterministic sau aleatoriu (probabilistic)

exact sau aproximativ

Tipuri de algoritmi

n funcie de paradigma utilizat, ei pot fi:

algoritmi backtracking

algoritmi de gen divide et impera

algoritmi de programare dinamic

algoritmi de tip greedy

Algoritmi de tipul for brut

algoritmi probabilistici, genetici, euristici .a

Fiind date trei valori reale A,B,C s se determine i s se

afieze cea mai mare i cea mai mic dintre ele.

Aplicaie