Date post: | 11-Feb-2016 |
Category: |
Documents |
Upload: | diana-cojocaru |
View: | 293 times |
Download: | 3 times |
Curs 6 - 7
Algoritmi.Reprezentarea Algoritmilor
Pentru Programarea Calculatoarelor
2
Componenta SoftSoftware de bază
Software utilitar Software de aplicaţie
3
Comunicarea cu calculatorul• Şi prin programe de aplicaţie – programe care
sunt realizate pentru rezolvarea unei probleme pe calculator.
• Trebuie sa comunicăm cu calculatorul în măsură să îi spunem ce să facă, să creem programe specifice pe care calculatorul să le poată prelucra, execute şi la urmă să afişeze date sau să interacţioneze într-un anume mod cu utilizatorul.
4
Cum se face comunicarea?Se scriu programe care sunt
executate de către calculator.
Ce face calculatorul?• instrucţiunea se incarcă
de UCC(Unitatea de Comandă şi Control)
• decodificare instrucţiune si emitere ordin către UAL (Unitatea aritmetică logică )
• citire date• prelucrare• rezultate
5
Ce face omul?Etape de bază care trebuie urmate pentru rezolvarea unei
probleme pe calculator:
analiza problemei - se stabileşte exact CE subprobleme trebuie să rezolve programul;
programarea - reprezentarea problemelor într-un mod adecvat pentru rezolvarea cu calculator;
implementarea - scrierea programului care rezolvă problema, într-un anumit limbaj de programare;
6
Etape de bază care trebuie urmate pentru rezolvarea unei probleme pe calculator:
Ce face omul:
Problema care trebuie rezolvată
Reprezentarea problemei
Rezolvarea problemei folosind un limbaj de
programare
CE CUM
7
Informatica• O disciplină care încearcă să construiască o bază
ştiinţifică pentru un număr mare de domenii– Proiectarea şi programarea calculatoarelor– Prelucrarea informaţiilor– Rezolvarea algoritmică a problemelor
• Ştiinţa algoritmilor– Domenii: matematică, inginerie, psihologie,
management, lingvistică, etc.– Programare – principii de bază ale instrumentelor
de programare utilizate în prezent, evoluţie şi probleme
8
Algoritm
• Set de paşi prin care se defineşte modul în care poate fi dusă la îndeplinire o anumită sarcină
• Un set ordonat de paşi executabili, care definesc un proces finit
• Reprezentarea algoritmilor în calculator -> program -> software
9
Algoritmi
• Captează şi transmit informaţie• Rezolvă o problemă• Sunt în formă conceptuală - trebuie să fie
reprezentate într-o formă în care pot să fie comunicate unui calculator – prin setul de instrucţiuni (gramatică şi limbaj) – limbaj de programare
• Paradigme de programare
10
Limbaje de programare După modul de abordare a rezolvării problemelor cu
calculatorul limbajele pot fi: procedurale - atunci când rezolvarea problemei
urmează anumite etape şi utilizează nişte structuri fundamentale (cum sunt: Pascal, C, etc.)
neprocedurale - ele se bazează pe reguli şi sunt mai apropiate de limbajul şi modul de raţionare natural (cum sunt limbajele pentru inteligenţă artificială: Prolog, Lisp).
11
Algoritm
Pentru a înţelege noţiunea de algoritm vom porni de la un exemplu.
Exemplu:Să presupunem că mama ne roagă să
cumpărăm pâine. Ce trebuie să facem?
11
12
Când am decis să plecăm la magazin vom proceda astfel:
luăm banii necesari;ne îndreptăm către magazin;solicităm o pâine;o plătim;venim cu ea către casă;o dăm mamei.
12
13
Am obţinut astfel un algoritm:
– care conţine 6 etape (deci un număr finit de operaţii);
– care au fost scrise în ordinea în care trebuie executate (deci sunt ordonate);
– fiecare etapă este explicată în cuvinte (deci este complet definită);
– şi care pornind de la ceva (în cazul nostru bani) obţinem ceea ce dorim (pâinea).
13
14
Def.Se numeşte algoritm o secvenţă finită de
operaţii ordonată şi complet definită care pornind de la datele de intrare produce rezultatele.
14
Algoritmul:
15
Proprietatile algoritmului
• Generalitatea – constă în aceea că un algoritm nu rezolvă o singură problemă ci o clasă de probleme de acelaşi tip;
• Finititudinea – numărul transformărilor ce trebuie aplicat unei informaţii de intrare pentru a obţine imformaţia finală este finit;
• Unicitatea – toate transformările prin care trece informaţia finală sunt univoc determinate de regulile algoritmului.
16
Un alt exemplu:
Presupunem că vrem să citim un număr întreg (pe care noi îl introducem de la tastatură) şi îl tipărim (pe ecranul monitorului). Şirul acţiunilor ce trebuie executate este următorul:
- citeşte numărul- tipăreşte numărul
Şi în acest caz am obţinut un algoritm. Acţiunile trebuie executate în ordinea în care au fost puse. Astfel, nu putem tipări numărul înainte ca acesta să fie cunoscut (citit).
16
17
Temă:
Scrieţi un algoritm care calculează suma a două numere întregi a şi b.
17
18
Rezolvare:
Algoritmul problemei
1. Solicită valori pentru a şi b2. Calculează S=a+b3. Furnizează rezultatul pentru S
18
19
Mărimi cu care operează algoritmii
• CONSTANTE - o mărime ce are atribuită o valoare care nu se modifică în timpul execuţiei
Exemplu a=7 sau nume=Marian pe tot parcursul derularii algoritmului a va lua valoarea 7 sau pentru nume va fi afisat Marian
• VARIABILE - o mărime care poate lua o mulţime de valori posibile în cursul prelucrării.
Mărimile pot fi succesiuni de caractere alfabetice, numerice şi chiar speciale.
Este indicat ca aceste numere atribuite mărimilor să fie sugestive.
20
Operatii utilizate in algoritmi1.Operaţii de calcul – sunt operaţiile obişnuite de : adunare (+), scădere (-), înmulţire
(*), împărţire (/), ridicare la putere.Acestea intervin în cadrul expresiilor care sunt o succesiune de variabile şi constante
legate între ele prin operatori ( semne de operaţii ) şi eventual paranteze, după reguli bine definite.
În cadrul expresiilor operaţiile se execută în ordinea naturală, conform priorităţilor.Într-un algoritm o expresie apare întotdeauna în cadrul unei operaţii de atribuire.2.Operaţii de atribuire: printr-o asemenea operaţie se atribuie unei variabilie o valoare
a unei - constante, variabile, expresii.Operaţia de atribuire se notează cu: „ := „ sau „←”Ex: NUME : = ‘IOAN‘ (constantă) NUME ← ‘IOAN‘NUME : = NUMEP (variabilă) NUME ← NUMEP A:= 1, A←1, A:= X-1, A:= A+13.Operaţii de test (decizie): scopul acestei operaţii este de a verifica relaţiile existente
între datele asupra cărora operează algoritmul pentru a decide transmiterea controlului execuţiei către o anumită instrucţiune.
În urma executării unei operaţii de test rezultatul obţinut este una din aşa numitele valori logice de adevăr: „ adevărat” sau „fals”.
Operaţiile de test se reprezintă prin semnele: <; 4.Operaţii de intrare/ieşire : se referă la introducerea datelor de intrare respectiv
furnizarea rezultatelor.Operaţii de intrare – citire, atribuire – citeşteOperaţii de ieşire - scriere, afişare –scriere
21
Metode de reprezentarea algoritmilor
Limbajul natural nu permite o descriere suficient de exactă a algoritmilor.
Din acest motiv pentru reprezentarea algoritmilor se folosesc diferite forme de descriere caracteristice.
21
22
Două din cele mai folosite forme de descriere a algoritmilor sunt:
Limbajul pseudocod;
Schemele logice.
22
23
Reprezentarea algoritmilor în limbaj pseudocod
Limbajul pseudocod foloseşte cuvinte cheie, adică nişte cuvinte cu înţeles prestabilit ce indică operaţia care se execută.
23
24
Exemplu:
Să se calculeze suma a două numere naturale a şi b.
Rezolvare:
a) Algoritmul:1. Solicită valori pentru a şi b2. Calculează S=a+b3. Furnizează rezultatul pentru S
24
25
b) Pseudocodul:citeşte a,b
S=a+bscrie Sstop
25
26
Reprezentarea algoritmilor prin scheme logice
Schemele logice utilizează săgeţi de legătură între diferite forme geometrice care simbolizează acţiunile ce urmează a fi executate.
În continuare sunt prezentate blocurile care intră în componenţa unei scheme logice:
26
27
1. Bloc pentru introducerea datelor (bloc de citire)
unde “Listă variabile” cuprinde numele simbolice ale variabilelor cărora li se asociază valori numerice (citite).
27
Lista variabile
28
2. Bloc de extragere a rezultatelor (bloc de scriere)
unde variabilele menţionate în listă constituie rezultate ale problemei.
28
Lista variabile
29
3. Bloc de calcul (bloc de atribuire)
Un astfel de bloc indică următoarea succesiune de operaţii:- se calculează expresia din membrul drept;- se atribuie variabilei din membrul stâng valoarea calculată
anterior (V reprezintă numele variabilei).29
V = expresie
30
4. Bloc de decizie (bloc decizional)
Condiţia logică înscrisă poate să aibă valoarea “adevărat” sau “fals”; în funcţie de valoarea logică obţinută, blocul următor care va fi parcurs va fi legat de ramura “true”(adevărat) sau ramura “false”(fals).
30
condiţieTRUE FALSE
31
5. Bloc de început (bloc de start)
Indică începutul algoritmului.31
START
32
6. Bloc de sfârşit (bloc de stop)
Indică sfârşitul algoritmului. 32
STOP
33
Exemplu:
Să se calculeze suma a două numere naturale a şi b.
Rezolvare:a) Algoritmul:
1. Solicită valori pentru a şi b2. Calculează S=a+b3. Furnizează rezultatul pentru S
33
34
citeşte a,bS=a+bscrie Sstop
34
b) Pseudocodul:
35
c) Schema logică:
35
START
a, b
S=a+b
S
STOP
36
Structuri de control
O structură înseamnă o combinaţie de operaţii utilizată în scrierea algoritmilor.
Orice algoritm care are un punct de început şi un punct de sfârşit poate fi reprezentat ca o combinaţie a trei structuri de control:
Secvenţa; Decizia; Repetiţia.
36
37
Structura secvenţială
Secvenţa reprezintă o succesiune de două sau mai multe operaţii care conţine o transformare de date:
în care “Secvenţa A” reprezintă o transformare de date.
37
Secvenţa A
38
EXEMPLU:
• Să se calculeze suma, produsul şi diferenţa a trei nume întregi x, y şi z.
a) algoritmul: 1. Se dau valori pentru x, y şi z 2. Calculează S=x+y+z 3. Calculează P=x*y*z 4. Calculează diferenţa D=x-y-z 5. Afişează rezultatele pentru S, P şi D.
38
39
b) Pseudocodul:citeşte x, y, zS=x+y+zP=x*y*zD=x-y-zscrie S, P, Dstop
39
40
c) Schema logică:
40
START
x,y,z
P=x*y*z
D=x-y-z
STOP
S=x+y+z
S, P, D
41
Structura decizională
Decizia reprezintă alegerea unei operaţii sau a unei secvenţe de operaţii dintre două alternative posibile. Forma structurii decizionale este următoarea:
41
condiţie
Secvenţa A Secvenţa B
true false
42
42
În limbaj natural, execuţia poate fi descrisă astfel:
- se evalueză condiţia;- dacă condiţia este adevărat, se execută “Secvenţa A”;- în caz contrar (dacă condiţia este falsă) se execută “Secvenţa B”.
În pseudocod, execuţia se descrie astfel: dacă condiţie atunci
Secvenţa A altfel
Secvenţa B
43
EXEMPLU:
• Se dau două numere naturale a şi b. Să se determine care dintre ele are valoarea mai mare.Rezolvare:
a) Algoritmul:1. Se dau valori lui a şi b2. Se determină maximul dintre a şi b: dacă a este mai mare ca b atunci maximul este a altfel maximul este b3. Se afişează maximul 43
44
b) Pseudocodul: citeşte a dacă a>b atunci max=a altfel max=b scrie max stop
44
45
c) Schema logică:
45
start
stop
a, b
a>b
max=a max=b
true false
max
46
Decizia cu varianta unei căi nule
46
condiţie
Secvenţa A
true false
Mai există o formă a structurii decizionale şi anume cea cu varianta unei căi nume.
Forma acestei structuri este următoarea:
47
În limbaj natural, execuţia poate fi descrisă astfel:
47
- se evalueză condiţia;- dacă condiţia este adevărat, se execută “Secvenţa A” apoi execuţia structurii decizionale se încheie;- în caz contrar (dacă condiţia este falsă) execuţia structurii decizionale se încheie.
În pseudocod, execuţia se descrie astfel: dacă condiţie atunci
Secvenţa A
48
EXEMPLU:
• Se citeşte o valoare întreagă a. În cazul în care aceasta este egală cu 0 se va tipări mesajul “am citit zero”. Altfel, nu se va da mesaj.
Rezolvare: a) Algoritmul:1. Se dă valoare lui a2. Se determină dacă a este zero: dacă a este egal cu zero atunci se va tipări “am citit zero”
48
49
b) Pseudocodul: citeşte a dacă a=0 atunci
scrie ‘am citit zero’
stop
49
50
c) Schema logică:
50
start
stop
a
a=0true false
‘am citit zero’
51
Structura repetitivă
• Repetiţia (bucla sau iteraţia) asigură execuţia unei secvenţe în mod repetat în funcţie de o anumită condiţie.
• Există trei tipuri de structuri repetitive: - bucla cu test iniţial; - bucla cu test final; - bucla cu contor.
51
52
1. Structura repetitivă cu test iniţial
• Structura repetitivă cu test iniţial are forma:
52
condiţie
Secvenţa A
true
false
53
a
53
Execuţia structurii repetitive cu test iniţial presupune parcurgerea următoarelor etape:
1.Se evaluează condiţia; dacă rezultatul este adevărat se trece la pasul 2, altfel execuţia se încheie;2. Se execută secvenţa A, apoi se trece la pasul 1).
54
Exprimarea în pseudocod:
cât timp condiţie execută Secvenţa A
54
55
Exemplu:
• Să se calculeze suma primelor n numere naturale.Rezolvare:
a) Algoritmul:1. Se dă valoare lui n;2. Se dă lui S valoarea 0 şi lui I valoarea 13. Cât timp I este mai mic sau egal cu n se calculează suma după
formula S=S+I şi I ia valoarea următorului termen al sumei, după formula
I=I+14. Se afişează valoarea sumei S.
55
56
b) Peudocodul:citeşte nS=0I=1cât timp I<=n execută S=S+I I=I+1scrie Sstop
56
57
c) Schema logică:
57
start
stop
n
s=0
i=1
s=s+i
i=i+1
i<=ns
false
true
58
2. Structura repetitivă cu test final:
• Structura repetitivă cu test final are forma:
58
Secvenţa A
condiţiefalse
true
59
a
59
Execuţia buclei cu test final presupune parcurgerea următoarelor etape:
1. Se execută secvenţa A2. Se evaluează condiţia; dacă rezultatul
este fals, se continuă cu pasul 1), în caz contrar, se încheie execuţia buclei.
60
Pseudocodul:
repetă Secvenţa A până când condiţie
60
61
Exemplu:
• Să se calculeze suma primelor n numere naturale.Rezolvare:
a) Algoritmul:1. Se dă valoare lui n;2. Se dă lui S valoarea 0 şi lui I valoarea 13. Se calculează suma după formula S=S+I şi I ia valoarea I=I+1, până când I>n.4. Se afişează valoarea sumei.
61
62
b) Pseudocodul:
a
62
citeşte nS=0I=1repetă S=S+I I=I+1până când I>nscrie Sstop
63
c) Schema logică:
63stop
ns
s=0
i=1
s=s+ii=i+1
i>nfalse
true
start
64
3. Structura repetitivă cu contor:• Structura repetitivă cu contor are forma:
unde cu “vi” s-a notat valoarea iniţială, iar cu “vf” s-a notat valoarea finală. 64
contor=vi
contor<=vffalse true
secvenţa A
contor=contor +pas
65
• Această structură are un număr cunoscut de repetiţii a “Secvenţei A”, motiv pentru care se numeşte structură repetitivă cu contor.
• Execuţia structurii repetitive cu contor presupune parcurgerea următoarelor etape:
1).Variabila de ciclare “contor” ia valoarea iniţială “vi”.2). Dacă “contor” este mai mic sau egal cu valoarea finală
“vf”, se execută “Secvenţa A”, se adună 1 la “contor” şi se reia cu pasul 2) altfel, execuţia este încheiată.
65
66
pentru contor=vi, vf executăsecvenţa A
66
Pseudocod:
67
Exemplu:
• Să se calculeze suma primelor n numere naturale.
Rezolvare: a) Algoritmul:1. Se dă valoare lui n;2. Se dă lui S valoarea 0 şi lui I valoarea 13. Pentru I luând valori de la 1 până la n se calculează
suma după formula S=S+I4. Se afişează valoarea sumei. 67
68
b) Pseudocodul:
68
citeşte nS=0pentru I=1, n execută S=S+I
scrie Sstop
69
c) Schema logică:
69
start
stop
n
s
i=1
s=s+i
i=i+1i<=n
true
false
s=0
70
TEMĂ:
1) Să se calculeze aria si perimterul unui dreptunghi
2) Sa se calculeze minimul dintre trei numere naturale
Se cer: - algoritmul; - pseudocodul; - schema logică.
70
71
Curs 1- de citit istoricul cu accent pe• Date, Informatii• Format binar şi bibliografia de la finalCurs 2 – Structura Hardware cu accent pe• Memoria, Def., Caracteristici, Clasificari• Unitatea centrala – executarea unei instructiuniCurs 3 – Componenta software cu accent pe• Categorii de software• Sisteme de operare – def., functiile unui SO, Structura unui SOCurs 4 – Retele de calculatoare cu accent pe• Definitie• Clasificari• Modul de organizare• Topologii • Comunicarea pe Internet• Adresarea in Internet (URL - URI)Curs 5 – Sistem de numeratie• TotCurs 6 – 7• Tot
72
Intrati la adresa:
cadredidactice.ub.ro/simonavarlan căutaţi în stânga BTI şi aveţi acolo cursurile
în format electronic.