8/17/2019 1.Algoritmi Şi Scheme Logice

http://slidepdf.com/reader/full/1algoritmi-si-scheme-logice 1/20

ALGORITMIALGORITMI ŞŞI SCHEME LOGICEI SCHEME LOGICE

Caracteristicile algoritmilorCaracteristicile algoritmilor IterativitateIterativitate şşi recursivitatei recursivitate

Reprezentarea algoritmilorReprezentarea algoritmilor escrierea structurilorescrierea structurilor

!un"amentale!un"amentale Structurarea algoritmilorStructurarea algoritmilor ErorileErorile #  # n algoritmin algoritmi $roiectarea algoritmilor$roiectarea algoritmilor

8/17/2019 1.Algoritmi Şi Scheme Logice

http://slidepdf.com/reader/full/1algoritmi-si-scheme-logice 2/20

CARACTERISTICILECARACTERISTICILEALGORITMILORALGORITMILOR

• Generalitate

• Determinare (claritate)

 Exemplul 1: ecuaţia de grad 2

 Exemplul 2:• Suma elementelor impare dintr-un şir 

• Suma elementelor pare dintr-un şir 

• Finitudine

8/17/2019 1.Algoritmi Şi Scheme Logice

http://slidepdf.com/reader/full/1algoritmi-si-scheme-logice 3/20

Clase de algoritmi:

♠  Algoritmi cu număr finit de paşi, a priori cunoscut 

♠  Algoritmi cu număr finit de paşi, a posteriori cunoscut 

♠  Algoritmi cu număr infinit de paşi 

Produs scalar între două mulţimi 

• CMMDC între două numere• Numerele prime până la o limită dată 

• Reol!area unei ecuaţii transcendente• Numărarea unor elemente care îndeplinesc o condiţie dată

8/17/2019 1.Algoritmi Şi Scheme Logice

http://slidepdf.com/reader/full/1algoritmi-si-scheme-logice 4/20

ITERATI%ITATEITERATI%ITATE ŞŞIIREC&RSI%ITATEREC&RSI%ITATE

IterativitateIterativitate $ro"us vectorial

$'trateleelementelor unui (ir Creare vectori

RecursivitateRecursivitate Suma elementelor unui (ir $ro"usul elementelor unui

(ir $ro"us scalar Ma)im *minim+ "intr,un şir Cmm"c "intre "ou'

numere

•  "ormula iterati!ă•  "ormula de start•  "ormula recursi!ă

8/17/2019 1.Algoritmi Şi Scheme Logice

http://slidepdf.com/reader/full/1algoritmi-si-scheme-logice 5/20

RE$RE-E.TAREAALGORITMILOR $RI.ALGORITMILOR $RI.

SCHEME LOGICESCHEME LOGICE

#locul $%&R% #locul $%'P

#locul de citire #locul de scriere

Cite teș

date_de_intrare

Scrie

date_de_ie ireș

#locul de atriuire

! e ! e

$%&R% $%'P

e → !

8/17/2019 1.Algoritmi Şi Scheme Logice

http://slidepdf.com/reader/full/1algoritmi-si-scheme-logice 6/20

#locul de rami"icare

c* c+  , cn

c*∨ c+∨ , ∨ cn  *

ci ∧ c -  ./ i ≠ -0 i/- */n

Pentru caul n =2

ccc

 NU DA

8/17/2019 1.Algoritmi Şi Scheme Logice

http://slidepdf.com/reader/full/1algoritmi-si-scheme-logice 7/20

Structurile !un"amentale "inStructurile !un"amentale "inprogramarea structuratprogramarea structurat''

$tructura sec!enţială (liniară)

s1l1s1

analitic:

pseudocodarore

s*0

s+0

,

sn0

#2'C3(s*/s+/,/sn)

$tructură PR45426G4&%7 8

#2'C3 

s* sn,s+

8/17/2019 1.Algoritmi Şi Scheme Logice

http://slidepdf.com/reader/full/1algoritmi-si-scheme-logice 8/20

$tructurile alternati!e 9 selecţia simplă

s1l1s1

analiticpseudocod

arore

4F c %6N s*62$6 s+

6ND4F

4F9%6N962$6(c/s*/s+)

$tructură PR45426G4&%7 8

8/17/2019 1.Algoritmi Şi Scheme Logice

http://slidepdf.com/reader/full/1algoritmi-si-scheme-logice 9/20

analiticpseudocod

arore

4F9%6N (c/s*)

$tructurile alternati!e 9 pseudoalternati!a

8/17/2019 1.Algoritmi Şi Scheme Logice

http://slidepdf.com/reader/full/1algoritmi-si-scheme-logice 10/20

%rans"ormarea în structură pri!ilegiată

s1l1s1

analitic

4F9%6N (c/s*)

4F9%6N962$6(c/s*/ ∅)

$tructura pseudoalternati!ă pe ramura "als

8/17/2019 1.Algoritmi Şi Scheme Logice

http://slidepdf.com/reader/full/1algoritmi-si-scheme-logice 11/20

$tructura alternati!ă multiplăs1l1s1

arore

analitic

C&$69'F (i/s*/s+/,/sn/s)

pseudocod

C&$69'Fi!*: s*

i!+: s

+1 1 1i!n:sn

62$6 s6NDC&$6

8/17/2019 1.Algoritmi Şi Scheme Logice

http://slidepdf.com/reader/full/1algoritmi-si-scheme-logice 12/20

$tructurile repetiti!e

$tructura repetiti!ă condiţionată anterior

s1l1s1 arore

analitic

pseudocod

;426 c D's

6ND;426

;4269D'(c/s)

$tructură PR45426G4&%7 8

8/17/2019 1.Algoritmi Şi Scheme Logice

http://slidepdf.com/reader/full/1algoritmi-si-scheme-logice 13/20

$tructura repetiti!ă condiţionată posterior

arore

analiticpseudocod

D's

<N%42 c

D'9<N%42(s/c)

s1l1s1

8/17/2019 1.Algoritmi Şi Scheme Logice

http://slidepdf.com/reader/full/1algoritmi-si-scheme-logice 14/20

$tructura repetiti!ă cu numărător

D'9F'R(!i/!"/!r)

s

s1l1s1 arore

analitic

pseudocod

D'9F'R !!i/!"/!r

s6NDD'

D'9F'R(!/!i/!"/!r/s)

N =(!" 9 !i) > !r? @ *

8/17/2019 1.Algoritmi Şi Scheme Logice

http://slidepdf.com/reader/full/1algoritmi-si-scheme-logice 15/20

STR&CT&RAREA ALGORITMILORSTR&CT&RAREA ALGORITMILOR

$A (#2'C3/ 4F9%6N962$6/ 4F9%6N/ C&$69'F/ ;4269D'/D'9<N%42/ D'9F'R)

• <n algoritm este $ structurat (sau $A structurat) dacă este "ormatnumai din elemente din mulţimea $ (respecti! $A)1

$ (#2'C3/ 4F9%6N962$6/ 4F9%6N)

 Mul imea structurilor priilegiateț  Mul imea structurilor priilegiateț 

 Mul imea structurilor fundamentaleț  Mul imea structurilor fundamentaleț 

8/17/2019 1.Algoritmi Şi Scheme Logice

http://slidepdf.com/reader/full/1algoritmi-si-scheme-logice 16/20

%eorema "undamentală de structură (#oem9Bacoppini)

• Fie P un algoritm nestructurat/ "ormat dintr9o mulţime & de acţiuni

(opera ii)ț  i o mulţime C de condiții1 Dacă se adaugă un număr "init deacţiuni i>sau de condi iiț / se oţine un algoritm structurat/ eci!alentcu P1

Corolarul top9doEn

• <n algoritm P structurat este eci!alent cu un algoritm pus su unadin următoarele "orme:

• P #2'C3(s*/s+/,/sn)•  P 4F9%6N962$6(c/s*/s+)•  P ;4269D'(c/s)

8/17/2019 1.Algoritmi Şi Scheme Logice

http://slidepdf.com/reader/full/1algoritmi-si-scheme-logice 17/20

METOE E STR&CT&RARE AMETOE E STR&CT&RARE AALGORITMILORALGORITMILOR

  Metoda du!lării codurilor 

•

 structurarea sec!en elor alternati!eț

• structurarea sec!en elor repetiti!eț

  Metoda folosirii de aria!ile !ooleene

• structurarea sec!en elor repetiti!eț

8/17/2019 1.Algoritmi Şi Scheme Logice

http://slidepdf.com/reader/full/1algoritmi-si-scheme-logice 18/20

ERORILEERORILE //. ALGORITMI. ALGORITMI

6rori6rori î  î n datele inin datele iniţţiale:iale:

9 erori de oser!are9 erori de oser!are

9 erori datorate numerelor ira9 erori datorate numerelor iraţţionaleionale 6rori de rotun-ire6rori de rotun-ire 6rori de metod6rori de metodăă

6rori reiduale6rori reiduale

8/17/2019 1.Algoritmi Şi Scheme Logice

http://slidepdf.com/reader/full/1algoritmi-si-scheme-logice 19/20

5aloarea este solu ia eactăț5aloarea este solu ia eactăț // iariar  este solu ia aproimati!ă :ț este solu ia aproimati!ă :ț

H H I este o aproimare a lui prin adaos0I este o aproimare a lui prin adaos0

J J I realieaă o aproimare prin lipsă1I realieaă o aproimare prin lipsă1

*

x x-x=ε *

*

x  xxε

  *  −=

*

*

xx

xxr   *

−

=

 Eroare Eroare::

 Eroare a!solută Eroare a!solută::

 Eroare relatiă Eroare relatiă::

6rorile pot "i acceptate sau respinse6rorile pot "i acceptate sau respinse::  în "uncţie de mărimea lor în "uncţie de mărimea lor ii  în "uncţie de mărimea !alorilor cărora li se asociaă1 în "uncţie de mărimea !alorilor cărora li se asociaă1

8/17/2019 1.Algoritmi Şi Scheme Logice

http://slidepdf.com/reader/full/1algoritmi-si-scheme-logice 20/20

$ROIECTAREA ALGORITMILOR$ROIECTAREA ALGORITMILOR

Proiectarea/ codi"icarea i testarea top9doEn

Proiectarea modulariată

Proiectarea structurată