Limbaje+3+2011-2012
-
Upload
cristian-popa -
Category
Documents
-
view
5 -
download
1
description
Transcript of Limbaje+3+2011-2012
-
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