Limbaje de programare ingineretiTema 3Algoritmi

Scurt istoricAlgoritm: -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. GeneralitateUn 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. FinitudinePrin 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 paiProdus 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. EficienEficien. 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 logiceBlocul STARTBlocul STOPSTARTSTOPBlocurile 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 logiceBlocul de citireBlocul de scriereBlocurile 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 logiceBlocul de atribuirev = ev eBlocurile 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 logiceBlocul de decizieConditieDaNuExpresie0=0Blocurile 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 pseudocodLimbajul 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 pseudocodInstruciunile 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-atuncidac condiie atunci instruciune altfel instruciune ;

Reprezentarea algoritmilor prin pseudocodInstruciunile pseudocodului sunt:5) Instruciunea repetitiv: repet-pn cndrepet 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 pseudocodObservaii: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 sf4. La nceputul i sfritul algoritmului se pun linii de nceput i sfrit

Structuri de control

Structura secventiala (liniara)

Structuri de control

Structura alternativa

Structuri de control

Structura repetitiva cu conditionare anterioara

Structuri de control

Structura repetitiva cu conditionare posterioara

Structuri de controlStructura repetitiva cu un numar cunoscut de pasi

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.

Ar fi o idee bun s se exemplifice fiecare pas pe rezolvarea unei probleme.

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 cAlgoritmul nu funcioneaz dac 2 valori sunt identice i de valoare maxim.Probleme i condiii

1. Prima problem este rezolvabil. Elevii ar trebui s-i dea cu prerea dac e rezolvabil sau nu, i s propun un algoritm de rezolvare.A doua problem nu este rezolvabil deoarece nu putem scrie un algoritm. Elevii trebuie s spun de ce 2. Trebuie un exemplu de algoritm care s par corect, dar care in anumite condiii(pentru anumite valori) s nu mearg corect.

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

3. Un exemplu de algoritm care nu se oprete niciodat. Elevii vor fi ntrebai dac algoritmul este corect.4. Se discut de ce e ambiguu i se propune o variant corect.

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

Eficiena unui algoritm este foarte important mai ales dac se cere ca algoritmul s furnizeze rezultatul ntr-un interval de timp dat.

Tipuri de algoritmin funcie de modul de implementare, un algoritm poate fi:recursiv - face uz de sine nsui, n mod repetatiterativ (repetitiv)serial sau paraleldeterministic sau aleatoriu (probabilistic)exact sau aproximativ

Tipuri de algoritmin funcie de paradigma utilizat, ei pot fi:algoritmi backtrackingalgoritmi de gen divide et imperaalgoritmi de programare dinamicalgoritmi de tip greedyAlgoritmi de tipul for brutalgoritmi probabilistici, genetici, euristici .a

Fiind date trei valori reale A,B,C s se determine i s seafieze cea mai mare i cea mai mic dintre ele. Aplicaie

Ar fi o idee bun s se exemplifice fiecare pas pe rezolvarea unei probleme.1. Prima problem este rezolvabil. Elevii ar trebui s-i dea cu prerea dac e rezolvabil sau nu, i s propun un algoritm de rezolvare.A doua problem nu este rezolvabil deoarece nu putem scrie un algoritm. Elevii trebuie s spun de ce 2. Trebuie un exemplu de algoritm care s par corect, dar care in anumite condiii(pentru anumite valori) s nu mearg corect.3. Un exemplu de algoritm care nu se oprete niciodat. Elevii vor fi ntrebai dac algoritmul este corect.4. Se discut de ce e ambiguu i se propune o variant corect.Eficiena unui algoritm este foarte important mai ales dac se cere ca algoritmul s furnizeze rezultatul ntr-un interval de timp dat.