Curs 6 - 7 Algoritmi

transcript

Curs 6 - 7

Algoritmi.Reprezentarea Algoritmilor

Pentru Programarea Calculatoarelor

Componenta SoftSoftware de bază

Software utilitar Software de aplicaţie

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.

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

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;

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

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

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

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

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).

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?

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.

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).

Def.Se numeşte algoritm o secvenţă finită de

operaţii ordonată şi complet definită care pornind de la datele de intrare produce rezultatele.

Algoritmul:

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.

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).

Temă:

Scrieţi un algoritm care calculează suma a două numere întregi a şi b.

Rezolvare:

Algoritmul problemei

1. Solicită valori pentru a şi b2. Calculează S=a+b3. Furnizează rezultatul pentru S

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.

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

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.

Două din cele mai folosite forme de descriere a algoritmilor sunt:

Limbajul pseudocod;

Schemele logice.

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ă.

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

b) Pseudocodul:citeşte a,b

S=a+bscrie Sstop

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:

1. Bloc pentru introducerea datelor (bloc de citire)

unde “Listă variabile” cuprinde numele simbolice ale variabilelor cărora li se asociază valori numerice (citite).

Lista variabile

2. Bloc de extragere a rezultatelor (bloc de scriere)

unde variabilele menţionate în listă constituie rezultate ale problemei.

Lista variabile

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

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).

condiţieTRUE FALSE

5. Bloc de început (bloc de start)

Indică începutul algoritmului.31

6. Bloc de sfârşit (bloc de stop)

Indică sfârşitul algoritmului. 32

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

citeşte a,bS=a+bscrie Sstop

b) Pseudocodul:

c) Schema logică:

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.

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.

Secvenţa A

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.

b) Pseudocodul:citeşte x, y, zS=x+y+zP=x*y*zD=x-y-zscrie S, P, Dstop

c) Schema logică:

P=x*y*z

D=x-y-z

S=x+y+z

S, P, D

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:

condiţie

Secvenţa A Secvenţa B

true false

Î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

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

b) Pseudocodul: citeşte a dacă a>b atunci max=a altfel max=b scrie max stop

c) Schema logică:

max=a max=b

true false

Decizia cu varianta unei căi nule

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:

În limbaj natural, execuţia poate fi descrisă astfel:

- 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

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”

b) Pseudocodul: citeşte a dacă a=0 atunci

scrie ‘am citit zero’

c) Schema logică:

a=0true false

‘am citit zero’

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.

1. Structura repetitivă cu test iniţial

• Structura repetitivă cu test iniţial are forma:

condiţie

Secvenţa A

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).

Exprimarea în pseudocod:

cât timp condiţie execută Secvenţa A

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.

b) Peudocodul:citeşte nS=0I=1cât timp I<=n execută S=S+I I=I+1scrie Sstop

c) Schema logică:

2. Structura repetitivă cu test final:

• Structura repetitivă cu test final are forma:

Secvenţa A

condiţiefalse

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.

Pseudocodul:

repetă Secvenţa A până când condiţie

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.

b) Pseudocodul:

citeşte nS=0I=1repetă S=S+I I=I+1până când I>nscrie Sstop

c) Schema logică:

63stop

s=s+ii=i+1

i>nfalse

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

• 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ă.

pentru contor=vi, vf executăsecvenţa A

Pseudocod:

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

b) Pseudocodul:

citeşte nS=0pentru I=1, n execută S=S+I

scrie Sstop

c) Schema logică:

i=i+1i<=n

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ă.

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

Intrati la adresa:

cadredidactice.ub.ro/simonavarlan căutaţi în stânga BTI şi aveţi acolo cursurile

în format electronic.

Curs 6 - 7 Algoritmi

Documents