Algoritmi Si Structuri DE Date

Algoritmi

Și structuri de date

CUPRINS

Sistem Informațional – Sistem Informatic

Structuri de date

Grafuri

Algoritmi definire

Descrierea algoritmilor

Structuri fundamentale ale algoritmilor

Evaluarea corectitudinii algoritmilor

Limbaje de programare

Algoritmi speciali

Tehnici de programare

Tehnici de programare structuratã

Probleme

Bibliografie

Introducere:

Semiotica se ocupã cu studiul semnelor în natura și în societate. Semnul nu este o calitate în sine a unui obiect, ci o funcție pe care acest obiect o poate dobandi. Studiind combinatorica rezultantã, rezultã ca din punct de vedere teoretic sunt posibile mii de clase de semne; dar imensa varietate de semne poate fi raportata la o anumita tipologie conform careia semnele se repartizeazã în 3 categorii: semne iconice, semne indiciale, semne simbolice. Aceasta clasificare se referã la tipul de legatura al semnului cu referentul.

Sunt de remarcat 3 specii de semne iconice: imagini, grafuri, metafore.

Știința este bogatã în semne indiciale, inevitabile, atât în procesele de generalizare cat și în cele de demonstrare, dar metoda modelarii promoveazã cu deosebita putere în cercetarea stiintifica, semnele iconice.

Se poate afirma totodata, ca semnele simbolice prezinta caracterul cel mai pronuntat social; ele sunt generate exclusiv prin puterea unei conventii pe care o comunitate de indivizi, istoriceste constituita o poate instaura.

Un loc special il ocupã aici codurile utilizate în telegrafie, sistemele de semne utilizate de diferite știinte ( formule algebriece, formule din chimia organica, etc. ) dar mai cu seama, limbajele de comunicare om – masina, de o deosebita importanta astãzi datorita dezvoltarii calculatoarelor electronice.

O alta triada care a jucat un rol important în dezvoltarea semioticii este constituita de distinctiile dintre:

Sintaxa – studiul relatiilor dintre semnele unui sistem semiotic;

Semantica – studiul relatiilor dintre semne și obiectele pe care ele le desemneaza;

Pragmatica – studiul relatiilor dintre semne și cei care le interpreteaza și le folosesc.

Statutul pragmaticii este inca foarte controversat, mai ales în legatura cu limbajele de programare a calculatoarelor electronice, și cu evolutia acestora.

Cele 6 functii ale procesului de comunicare codificata sunt:

Emotivã;

Conativã;

Referențialã;

Faticã ( de centrare asupra canalului );

Metalingvisticã ( de centrare asupra codului );

Poeticã.

Superioritatea calitativã a vorbelor fata de semnale provine din generalitatea semnificatiilor pe care le produce. „Magia” cuvintelor tine de valoarea cognitiva și pragmatica a notiunilor pe care le vehiculeaza. „Fiecare cuvant era și ramane o victorie contra absentei, contra lipsei, contra neputinei” a spus Gerard Mendel în cartea sa „La chasse structurale”.

CAPITOLUL 1

Sistem informațional – Sistem informatic

Sistem informațional

Un sistem poate fi privit ca un ansamblu de elemente interconectate și interconditionate prin relații fizice, sociale și de alta natura, intre ele și nu mediul extern sistemului, care functioneaza în vederea realizarii unui scop sau a finalizarii unui obiect.

Activitatea desfasurata intr-un sistem organizat, în vederea realizarii unui obiectiv poate fi definita ca fiind rezultatul actiunii conjugate, a 3 subsisteme ce actioneaza intr-o stransa interdependenta și care la randul lor pot fi considerate sisteme:

Sistemul de conducere sau decizional ( S.D. )

Sistemul condus, de executie sau operational ( S.O. )

Sistem informational.

Sistemul de conducere are rolul de a dispune, indruma și coordona activitatea în vederea realizarii abiectivelor fixate, cu eficienta maxima.

Sistemul condus are rolul de a executa practic deciziile luate și de a furniza date privind actiunile realizate, sau în curs de executie, folosind pt aceasta resursele materiale, financiare stiintifice și umane existente, repartizate pe obiective dinainte stabilite.

Pentru executarea activitatiilor de bazã ale procesului decizional: planificare, urmarire, control și decizie, sistemului de conducere ii sunt necesare permanent informatii despre starea și evolutia sistemului de executie, despre legaturile acestuia cu exteriorul. De la sistemul de conducere, spre sistemul condus vor circula decizii. Acest circuit de informatii și decizii reprezintã un proces permanent care se realizeaza prin existenta Sistemului Informational.

Sistemul Informational este un instrument indispensabil conducerii, având ca parti componente mijloacele și procedeele ce asigura legaturile intre elementele de executie și elementele decizionale pentru conducere și organizare.

În felul acesta, prin sistemul informational se pot cunoaste la timp și în cantitati necesare toate elementele de caracterizare a activitatilor desfasurate, el cuprinzand fondul de informatii, tehnicile de colectare și stocare, mijloacele și metodele necesare în vederea prelucrarii și transmiterii informatiilor.

Deci, sistemul informational este un ansamblu de fluxuri și circuite informationale organizate intr-o conceptie unitara, el utilizeaza modele, proceduri, resurse umane și materiale pentru colectarea, inregistrarea, prelucrarea, stocarea și/sau transmiterea datelor și a informatiilor, prin intermediul carora asigura interconexiunile informationale dintre sistemul de conducere și sistemul condus.

Sistemul informational primeste intrari, le prelucreaza și furnizeaza iesiri. Intrarile și iesirile unui sistem informational, sunt date, informatii și decizii.

Ansamblul operatiilor la care sunt supuse intrarile pentru a furniza iesirile se constituie în proceduri.

În cazul cand metodele, procedurile și mijloacele utilizate pentru colectarea, inregistrarea, prelucrarea, stocarea și/sau transmiterea datelor și a informatiilor sunt cu preponderenta automatizate, sistemul informational devine un sistem informatic.

Sistemul informatic – intrument al conducerii stiintifice a societatilor comerciale

Conceptul de sistem informatic

În masura în care activitatiile din cadrul sistemului informational sunt realizate cu ajutorul echipamentelor electronice de culegere, transmitere, stocare și prelucrare automata a datelor, se spune ca avem de a face cu informatizarea sistemului informational și implicit cu aparitia conceptului de sistem informatic.

Sistemul informatic, reprezintã un ansamblu de elemente intercorelate, functional în scopul automatizarii obtinerii informatiilor necesare conducerii în procesul de elaborare a deciziilor.

Un sistem informatic, este compus, în principal din urmatoarele elemente:

Bazã tehnica sau hardware-ul sistemului informatic, care este constituita din totalitatea mijloacelor tehnice de culegere, transmitere, stocare și prelucrare a datelor, în care locul central revine calculatorului electronic.

Sistemul de program sau software-ul sistemului, ce cuprinde totalitatea programelor pentru functionarea sistemului informatic, în concordanta cu functiunile și obiectivele ce au fost stabilite.

Bazã stiintifico-metodologica, care este constituita din modele matematice ale proceselor și fenomenelor economice, metodologii, metode și tehnici de realizare a sistemelor informatice.

Bazã informationala cuprinde datele suspuse prelucrarii, fluxurile informationale, sistemele și nomenclatoarele de coduri.

Resursele umane și cadrul organizatoric, care cuprinde personalul de specialitate și cadrul necesar functionarii sistemului informatic.

Obiectivele sistemului informatic

Obiectivele sistemului informatic pot fi clasificate dupa mai multe criterii astfel:

A. În functie de sfera de cuprindere pot fi: principale ( generale ) și secundare ( derivate ).

B. Din punct de vedere al domeniului de activitati asupra carora se rasfrang efectele utilizarii calculatoarelor electronice, obiectivele pot fi clasificate astfel:

Obiective ce afecteaza activitatiile de bazã din cadrul unitatilor economice ( comerciala, productia, etc. ) cum ar fi:

cresterea gradului de incarcare a capacitatilor de productie existente și reducerea duratei ciclului de fabricatie;

cresterea volumului productiei;

reducerea consumurilor specifice de materii prime și materiale

reducerea personalului administrativ – functionaresc;

cresterea gradului de utilizare a capacitatii de cazare;

sporirea volumului incasarilor din cativitati de prestari servicii;

cresterea profitului și a rentabilitatii etc.

b. obiectivele ce afecteaza functionarea sistemului informational cum ar fi:

cresterea vitezei de raspuns a sistemului la solicitarile beneficiarilor;

cresterea exactitatii și preciziei în procesul de prelucrare a datelor și informarea conducerii;

reducerea costului informatiei;

rationalizarea fluxurilor informationale;

rationalizarea circuitelor informationale;

sporirea completitudinii situatiilor de informare – raportare , etc.

C. Din punct de vedere al posibilitatiilor de cuantificare a efectelor acestora:

obiective cuantificabile, cum ar fi:

accelerarea vitezei de rotatie a mijloacelor circulante, prin inlaturarea imobilizarilor de mijloace circulante;

reducerea cheltuielilor de transport;

reducerea cheltuielilor indirecte;

cresterea volumului productiei;

rationalizarea formularisticii de evidenta, etc.

obiective necuantificabile, care influenteaza în mod direct indicatorii cuantificabili.

Clasificarea sistemelor informatice

Sistemele informatice se clasifica dupa mai multe criterii:

A. În functie de domeniul de utilizare, acestea se clasifica în 4 grupe, astfel:

a. sisteme informatice pentru conducerea activitatiilor unitatiilor economico sociale, care se caracterizeaza prin aceea ca datele de intrare, de regula sunt furnizate prin documente intocmite de om, iar la iesire sunt furnizate de catre sistem tot sub forma de documente, pentru perceperea acestora de catre om.

b. sisteme informatice pentru conducerea sistemelor tehnologice care se caracterizeaza prin aceea ca datele de intrare sunt asigurate prin intermediul unor dispozitive automate care transmit sub forma de semnale informatii despre diversi parametrii ai procesului tehnologic, iar datele de iesire se transmit de asemenea sub forma de semnale unor organe de executie, regulatoare, care modifica automat parametrii procesului tehnologic.

c. sistemele informatice pentru activitatea de cercetare stiintifica, și proiectare, care asigura atutomatizarea calculelor tehnico-ingineresti.

d. sistemele informatice speciale, care sunt destinate unor domenii specifice de activitate, ca de exemplu: informare și documentare tehnico-stiintifica, medicina, etc.

B. Un alt criteriu de clasificare al sistemelor informatice economice este nivelul ierarhic ocupat de sistemul economic în structura organizatorica a societatii, conform caruia avem urmatoarea clasificare:

a. sisteme informatice pentru conducerea activitatii la nivelul unitatilor economie. Acestea pot fi descompuse în subsisteme informatice asociate functiunilor economico-sociale sau chiar unor activitati;

b. sisteme informatice pentru conducerea activitatii la nivelul organizatiilor economico-sociale cu structura de grup.

c. sistemele informatice teritoriale. Sunt constituite la nivelul unitatilor administrativ-teritoriale și servesc la fundamentarea deciziilor adoptate de catre organele locale de conducere;

d. sistemele informatice pentru conducerea ramurilor, subramurilor și activitatilor la nivelul economiei nationale.

Se constituie la nivelul ramurilor, subramurilor și activitatilor individualizate în virtutea diviziunii sociale a muncii și specificate în clasificarea ramurilor economiei nationale. Principala lor functiune consta în fundamentarea și reglarea echilibrului dezvoltarii economico-sociale în profil de ramura.

e. sistemele informatice functionale generale au ca atribut principal faptul ca intersecteaza toate ramurile și activitatiile ce au loc în spatiul economiei nationale, furnizand informatiile necesare coordonarii de ansamblu și sincronizarilor în procesul reproductiei din cadrul ehilibrului dezvoltarii economico-sociale în profil de ramura.

e. sistemele informatice functionale generale au ca atribut principal faptul ca intersecteaza toate ramurile și activitatiile ce au loc în spatiul economiei nationale, furnizand informatiile necesare coordonarii de ansamblu și sincronizarilor în procesul reproductiei din cadrul economiei de piata.

C. În functie de modul de organizare a datelor în cadrul sistemelor informatice acestea pot fi:

sisteme informatice cu organizarea datelor în fisiere clasice. Acest mod de organizare a datelor are tendinta de rasfrangere sub aspectul aplicabilitatii, datorita neajunsurilor pe care le prezinta.

Sisteme informatice cu organizarea datelor în baze de date. Aceasta categorie de sisteme prezinta o tendinta de extindere și dezvoltare. De la baze de date cu structuri arborescente și retea, s-a trecut la baze de date rationale.

Sistemul informatic – instrument al conducerii moderne

Obtinerea de catre agentii economici și societatiile comerciale a unei eficiente economice sporite, este conditionata de existenta unei conduceri stiintifice bazate pe o buna cunoastere a legilor economice.

Plecand de la faptul, pe de o parte, ca modelele matematice reprezintã componenta stiintifica a unui sistem informatic, iar pe de alta parte, tinand seama de facilitatile oferite de utilizarea calculatorului electronic, se poate aprecia ca sistemul informatic constituie un adevarat instrument în conducerea stiintifica a activitatii economice.

Proiectarea la nivel micro și macroeconomic a unor sisteme informatice care sa utilizeze tehnica bazelor de date și care sa contina o serie de modele matematice, iar situatiile de informare – raportare sa aiba un caracter de semnalare preventiva a abaterilor fata de starea normala, reprezintã o forma superioara de organizare și prelucrare a datelor.

Stadiul actual și tendintele dezvoltarii sistemelor informatice

În ultimii ani asistam la una dintre cele mai importante transformari din istorie ale infrastructurii tehnologice a societatii. Aceasta schimbare consta defapt în adaugarea unui nou substrat în infrastructura tehnologica, substrat care este uzual denumit tehnologia informatiei. În acest nou substrat se evidentiaza în mod decisiv informatica. Aceasta extindere este pe cale de a produce o schimbare majora în societatea noastra și anume, trecerea de la orientarea industriala, în care accentul se pune pe masina și energie, la o noua orientare informationala în care accentul este pus pe robot și informatie. Masina și energia vor juca un rol important, fundamental în societatea informationala, dar pentru noile masini, pentru noile industrii, ca și pentru celelalte activitati ale omului devin esentiale tehnologiile informatice care au la bazã electronica, informatica, și comunicatiile moderne.

Informatizarea activitatilor economico-sociale a cunoscut profunde transformari precum:

Se manifesta în mod clar o tendinta spre divizarea costurilor software-ului sistemelor informatice. Reducerea costurilor sistemelor informatice se datoreaza, pe de o partea, reducerii costurilor hardware-ului, iar pe de alta parte, reducerii costului software-ului. În prezent se manifesta o tendinta clara în dezvoltarea sistemelor informatice bazate tot mai mult pe platformele software la nivel inalt. O platforma software corespunde unei platforme de aplicatii și contine functii software de bazã și functii specifice aplicatiei companiei.

Se manifesta o intensa tendinta spre tehnologia sistemelor informatice bazate pe retele de calculatoare. Cresterea complexitatii, varietatii aplicatiilor și aparitia de noi produse informatice cu un raport pret / performanta din ce în ce mai avantajos au facut necesara și rentabila conectarea intre ele a calculatoarelor în cadrul unor retele care constituie la ora actuala suportul cel mai adecvat pentru teleinformatica.

În domeniul organizarii datelor, se manifesta tendinta spre baze de date orientate obiect.

Structurile clasice de date bazate pe text și valori numerice fie se dovedesc insuficiente, fie complexitatea lor depaseste posibilitatiile de stocare și prelucrare oferite de tehnologiile clasice. Aplicatiile asociate cu disciplinele tehnologice cum ar fi : proiectarea asistata pe calculator, sistemele informatice geografice și sistemele bazate pe cunostinte, presupun stocarea unor cantitati mari de informatii cu o structura complexa.

Unele aplicatii informatice solicita monitorizarea unor desene formate din grupuri de elemente complexe ce trebuie sa fie combinate, separate, suprapuse și modificate astfel incat sa permita elaborarea unor variante de proiect. Bazele de date clasice sau relationale ofera prea putin suport teoretic și practic pentru tipurile neconventionale de date.

Se manifesta tendinta catre sisteme deschise.

Apreciem ca în prezent domeniul informaticii se caracterizeaza prin cel mai pronuntat dinamism. Se asista la o proliferare de produse hardware și software, apar de la o zi la alta noi versiuni și noi produse.

Faptul ca un sistem este deschis, nu implica și nu impune nici o implementare practica de sistem, tehnologie sau mijloc de interconectare, termenul de sistem deschis se referã doar la recunoasterea reciproca și aplicabilitatea acelorasi standarde.

Astfel de standarde au cel putin urmatoarele efecte mai importante:

Producatorii se simt incurajati sa le implementeze deoarece, având în vedere larga circulatie a acestor standarde, produsele lor informatice vor fi mult mai vandabile decat daca nu le utilizeaza;

Asigura o crestere a gradului de portabilitate de pe o platforma de sistem pe alta, atât a datelor cat și a produselor software;

Faciliteaza insusirea teoretica și practica a hardware-ului și software-ului de catre utilizatori

Standardizarea se regaseste intr-o multitudine de domenii de activitati

Standardizarea retelelor de calculatoare. Au luat o amploare deosebita preocuparile privind realizarea unor retele eterogene de calculatoare, precum și interconectarea retelelor a.i. sa se obtina sisteme teleinformatice de dimensiuni mari.

Aceste preocupari s-au materializat atât în plan practic, prin realizarea unor sisteme mari cat și în plan teoretic, prin elaborarea de catre ISO ( International Standard Organization ) a unui model arhitectural stratificat de referinta pentru interconectarea sistemelor deschise.

Modelul a fost adoptat în 1983 și reprezintã un cadru conceptual de lucru pentru definirea de standarde referitoare la interconectarea calculatoarelor eterogene. Scopul fundamental al acestui standard international este asigurarea unei baze comune pentru coordonarea de noi standarde privind interconectarea sistemelor, permitand în acelasi timp evaluarea standardelor existente.

Conceptul de sistem „deschis” în viziunea ISO denota capabilitatea oricaror 2 sisteme, omogene sau neomogene care „respecta” modelul de referinta și standardele corespunzatoare de a putea fi interconectate. De asemenea a fost adoptat teoretic și practic și un model arhitectural ierarhizat, elaborat de catre Departamentul Apararii din S.U.A. ( Departament of Defence – DoD )

Standardizarea arhitecturii Sistemelor de Gestiune a Bazelor de Date. În acest sens amintim arhitectura propusa de CODASYL și ANSI.

Standardizarea limbajelor de programare s-a materializat prin propunerile grupului de lucru CODASYL, care au elaborat limbajul de programare COBOL. Unele limbaje cum sunt: C, C++, Basic, SQL, au devenit standarde de facto, datorita faptului ca s-au impus prin performantele și facilitatiile ce le ofera.

CAPITOLUL 2

Structuri de date

Prelucrarea automata a datelor necesita, pe langa activitatiile legate de formularea problemei, de analiza acesteia în vederea gasirii algoritmului de rezolvare și o alta activitate deosebit de importanta, legata de organizarea datelor.

Organizarea datelor este un proces care cuprinde urmatoarele activitati:

identificarea datelor;

clasificarea și descrierea propietatiilor, a caracteristicilor datelor;

gruparea datelor în colectii de date destinate prelucrarii automate;

reprezentarea externa pe suporturi tehnice;

identificarea, definirea și descrierea procedurilor de prelucrare automata.

Eficienta prelucrarii automate a datelor, succesul acesteia depind în mare masura, de organizarea interna și externa a datelor, de stabilirea unor structuri de date care sa corespunda cerintelor de prelucrare.

Concepte de bazã

Odata cu aparitia bazelor de date, în terminologia curenta au fost introduse și utilizare 3 concepte de bazã în organizarea datelor, și anume: entitate, atribut și valoare.

Entitatea reprezintã un obiect concret sau abstract, reprezentat prin proprietatiile lui. Pe de alta parte orice proprietatea a unui obiect poate fi descrisa printr-o pereche ( Atribut, Valoare ); prin urmare o entitate poate fi reprezentata prin mai multe proprietati, deci mai multe perechi de forma ( Atribut, Valoare ).

De exemplu, un student X se poate reprezenta prin perechi ( Nume, Ion ), ( Facultate, Informatica ), ( Telefon, 435 34 76 ), ( Grupa 601 ) etc.

Practic, multimea atributelor, Nume, Facultate, Telefon, Grupa, poate fi asociata mai multor studenti; aceasta inseamna ca un atribut nu caracterizeaza doar o entitate, ci o clasa de entitati, numita entitate grup.

În exemplul nostru, entitatea grup se poate numi STUDENTI.

Notiunea de atribut este cunoscuta și sub numele de camp sau caracteristica.

Notiunea de data

În informatica prin data, se intelege un model de reprezentare a informatiilor despre obiectele supuse prelucrarii automate, accesibil atât utilizatorului cat și componentelor calculatorului.

În functie de obiectele pe care le reprezintã datele se pot clasifica în:

date elementare sau scalare care se prezinta sub forma de entitati indivizibile

colectii de date, care se prezinta sub forma unor multimi de date elementare intre care se definesc și se descriu anumite relații.

Componentele unei structuri se pot identifica și selecta prin numele de identificare sau prin pozitia pe care o ocupã în cadrul structurii, potrivit relatiei de ordine stabilita.

Dupa tipul componentelor, structurile de date se pot grupa în:

structuri de date omogene, care contin elemente de acelasi tip;

structuri de date eterogene, care contin componente de tipuri diferite.

OBSERVATIE:Daca o structura se poate descompune în structuri de acelasi tip, atunci structura respectiva este recursiva.

În mod corespunzator, structurile de date vor putea fi:

structuri de date interne , având caracter temporar, deoarece sunt realizate în memoria interna de tip RAM ( volatila );

structuri de date externe, care au un caracter relativ permanent, deoarece sunt memorate pe suport extern. Aceste structuri pot curpinde:

fisiere de date

baze de date

banci de date

Din punct de vedere al modului de alocare a zonelor de memorie, structurile de date pot fi grupate astfel:

structuri de date statice, la care alocarea zonelor de memorie necesare pastrarii temporare a datelor este facuta în momentul compilarii programului și ramane aceasi pe toata durata de executie a programului respectiv;

structuri de date dinamice, la care alocarea zonelor de memorie se face numai în momenutl executiei programului, la momentul necesar, ele putand fi modificate, eliberate, sau realocate pe toata durata de executie a programului respectiv.

Dupa nivelul de structurare a datelor se poate face gruparea:

structura logica, care se referã la modul de ordonare a datelor, la operatorii de prelucrare a datelor;

structura fizica, reprezentand modul de implementare, de reprezentare a datelor, pe suport magnetic de date.

Tipuri de structuri de date

Am vazut ca o structura de date reprezintã practic o colectie de date intre care s-au definit o serie de relații care duc la un anumit mecanism de selectie și identificare a datelor.

Aceste relații pot fi de tipul:

de echivalenta

de ordine

de ordine totala

de preordine

Se numeste tip de structura de date o multime ordonata de date, intre care s-au stabilit anumite relații și care folosesc, pentru realizarea operatiilor un grup de operatori de bazã cu o anumita semantica.

Principalele tipuri de structuri de date ( logice ) sunt:

structura punctuala

structura liniara

a1 a2 a3 a4

Structurã liniarã simplã

Principalele caracteristici ale acestui tip de structura sunt:

cardinalul multimii elementelor initiale este egal cu 1

cardinalul multimii elementelor terminale este egal cu maxim 1

orice element neterminal are un succesor imediat unic

primul element nu are predecesori

ultimul element nu are succesori

relatiile stabilite intre date sunt de tip 1 la 1

daca exista un cuplu în relatie de forma ( u, v ), unde v este ultimul element al structurii, iar u este primul element, atunci structura se numeste structura liniara inelara sau circulara.

intre date se stabilesc relații de tipul 1 la 1

structura liniara se numeste structura liniara cu elemente structurate arborescent, daca componentele ei sunt structuri arborescente

structura liniara se numeste structura liniara cu elemente structurate retea, daca componentele ei sunt structuri de tip retea

structura arborescenta, sau descendenta, sau ierarhica este definita atunci cand intre elementele colectiei de date exista o relatie de ordine.

Arbori binari

Datorita specificului lor, arborii binari admit o reprezentare grafica simetrica, axa de simetrie trecand prin radacina arborelui. De aceea, subarborii unui element oarecare sunt denumiti subarbore stang, și respectiv subarbore drept, functie de pozitia relativa a acestora fata de elementul respectiv.

Astfel pentru arborii binari s-au identificat și s-au descris 3 modalitati de parcurgere a elementelor arborelui denumite:

parcurgere în preordine

parcurgere în inordine

parcurgere în finordine ( postordine )

structura retea, definita atunci cand intre elementele colectiei de date exista o relatie de preordine. Ea are urmatoarele caracteristici:

este practic un graf care are, intre doua noduri, legaturi budirectionale;

exista unul sau mai multe noduri initiale (cardinalul miltimii este egal sau mai mare cu 1);

exista unul sau mai multe noduri finale (cardinalul mltimii nodurilor finale este egal sau mai mare cu 1);

orice nod poate avea mai multi predecesori, el putand fi predecesorul propriului predecesor. Atunci apar în retea cicluri. Un ciclu se defineste atunci cand nodul initial este acelasi cu nodul final;

intre elementele structurii de tip retea se regasesc relații de tip m la n.

Structura relationara este formata din mai multe tabele de date elementare, numite tablori sau relații, obtinute prin metoda normalizarii, pentru a asigura conditiile de integritate și unicitate a datelor și a elimina astfel nomaliile la actualizari.

Despre acest tip de structura vom invata mai mult la S.G.B.D.-uri, adica la sisteme de gestiune a bazelor de date, special realizate pentru operatii cu colectii de date memorate pe suporti externi.

Informatii despre cantitatile de produse finite care trebuie realizate

Informatii despre structura produselor finite respective.

Fisierul se defineste ca o multime de date omogene din punct de vedere al semnificatiei lor și al cerintelor de prelucrare. Aceasta multime este organizata ca o lista liniara, cu elemente structurale arborescente.

Bazã de date se defineste ca o colectie de date aflate în interdependenta, memorata pe suport impreuna cu descrierea datelor și a relatiilor dintre ele.

Banca de date reprezintã un sistem de organizare și prelucrare respectiv tele-prelucrare a datelor constituit din:

bazã de date

un sistem de programe pentru gestiunea datelor.

Structuri de date interne

Cele mai frecvent utilizate structuri statice de date sunt:

masive (tablouri )

articole ( inregistrari logice )

Limbajele de programare permit implementarea acestor structuri statice de date.

Masivul reprezintã o structura de date omogena cu una, doua sau n dimensiuni. Masivul cu o dimensiune se numeste în mod uzual vector, iar cu doua matrice.

Exemplu:

Fie vectorul X cu elementele x1, x2, x3, … ,xn un tablou unidimensional cu n elemente componente de acelasi tip.

În memoria interna el va fi memorat astfel:

X

1 2 …. n

Adresa Adresa Adresa Adresa

de de de de

bazã bazã+1 bazã+2*1 bazã+(n-1)*1

Reprezentarea elementelor unui vector în memoria interna

Articole.Fisiere de date

Articolul sau inregistrarea logica reprezintã o structura de date interna, eterogena de tipul „ structura arborescenta „.

Un articol este format din campuri de date care se identifica în mod unic printr-un identificator sau nume asociat.

Fisierul de date este format din articole sau inregistrari logice care descriu aceleasi entitati și formeaza o colectie de date omogene din punct de vedere al semnificatiei și al cerintelor de prelucrare.

Metodele de organizare a fisierelor definesc regulile care stau la bazã constituirii articolelor în fisiere și se stabilesc la operatia de creare a fisierelor. Astfel fisierele pot avea:

Organizare secventiala care memoreaza articolele de date secvential în ordinea introducerilor iar accesul la articole poate fi doar secvential.

Organizare secvential-indexata care presupune crearea fisierului de date cu articolele ordonate crescator dupa valoarea unui camp de date numit cheie de indexare.

Organizare directa care presupune memorarea și apoi identificarea articolelor printr-o cheie care poate fi un camp de date, sau nu, dar a carei valoare se asociaza fiecarui articol în parte.

Metodele de acces la articolele unui fisier stabilesc modalitatile prin care se localizeaza un articol în fisierul de date.

Tipuri de acces:

Acces secvential

Acces direct

Programare orientata spre obiecte

Programare orientata spre obiecte reprezintã un stil de programare nou, care utilizeaza concepte și constructii noi, modalitati noi de structurare a datelor, de tratare a colectiilor de date și programare.

La programarea orientata spre obiecte procedurile de prelucrare și datele sunt incapsulate în obiecte, asupra carora se aplica mesaje care modeleaza comportamentul sistemului.

Date și expresii

Asupra datelor elementare sau memorate în structuri de date statice sau dinamice, interne sau externe, în cadrul prelucrarii atutomate, se pot aplica diferiti operatori, rezultand astfel constructii sintactice denumite expresii.

Expresiile sunt deci grupuri alcatuite din operanzi și operatori. Din evaluarea unei expresii rezultã o valoare, care reprezintã rezultatul ei.

Operatorii pot fi grupati în:

operatori aritmetici

operatori logici

operatori de comparare

operatori pe siruri de caractere

Toate limbajele de programare permit implementarea acestor tipuri de operatori și constructia unor tipuri de expresii corespunzatoare.

În toate limbajele de programare, operatorii aritmetici au reprezentarea:

+ pentru adunare

– pentru scadere

* pentru inmultire

/ pentru impartire

^n pentru ridicarea la putere n

( ) pentru gruparea operatiilor și schimbarea ordinii normale de executie a acestora.

Este permisa includerea unor paranteze în altele, ordinea de desfacere a acestora fiind dinspre interior spre exterior.

CAPITOLUL 3

Grafuri

Definitii, tipuri

Notiunile de algoritm și schema logica pot fi definite, explicate și mai ales foarte des utilizate în legatura cu elemente de teoria grafurilor.

Se umeste graf neorientat o pereche ordonata G = ( X, U ), unde X este o multime finita și nevida de elemente numite noduri ( varfuri ), iar U este o multime de perechi neordonate de elemente distincte ale lui X, numite muchii.

Se numeste lant intr-un graf G = ( X, U ) o succesiune de muchii de forma [i1,i2], [i2,i3],…,[în-1,în], notata prescurtat prin [i1,i2,…în]

Un lant în care muchiile sunt diferite doua cate doua se numeste ciclu.

Un varf care este extre,otatea imeo somgire ,icjoo se mi,este varf terminal.

Doua varfuri unite printr-o muchie se numesc varfuri adiacente.

Un graf orientat este o pereche ordonata G = ( X, U ), deosebirea fata de graful neorientat constand în faptul ca elementele lui U sunt perechi ordonate de varfuri numite arce. În cazul grafurilor orientate, notiunile de lant și ciclu isi au corespondent în notiunile de drum și circuit.

Arbori

Se numeste arbore un graf neorientat, conex,

OBSERVATIE: Intr-un arbore cu nvarfuri, exista cel putin doua varfuri terminale.

Se poate demonstra, cu privire la grafuri, teorema:

Fie G un graf neorientat, cu n1 varfuri. Urmatoarele afirmatii sunt echivalente:

1. G este un arbore;

2. G are n-1 muchii și nu contine cicluri;

3. G are n-1 muchii și este conex;

4. Orice doua varfuri din G sunt unite printr-un unic lant.

Se numeste arbore binar un arbore orientat, în care fiecare varf are cel mult doi descendenti, facandu-se insa distinctia intre descendetul stang și cel drept al fiecarui varf.

Se numeste arbore de sortare un arbore binar cu proprietatile:

INF(i) INF(j) pentru orice varf j din subarborele stang al lui i;

INF(i) INF(j) pentru orice varf j din subarborele drept al lui i.

CAPITOLUL 4

Algoritmi definire

Notiunea de algoritm, preluata din matematica, este fundamentala în activitatea de programare a calculatoarelor electronice.

Programarea este practic activitatea prin care se concepe și se realizeaza programul pentru rezolvarea unei probleme, cu ajutorul calculatorului electronic.

Un program reprezintã o succesiune de instructiuni și comenzi apartinand unui/unor limbaje de programare ( Pascal, Basic, C, Java ) care conduc la solutionarea problemei formulate.

Daca ne referim la activitatea de programare, vom identifica în cadrul acestea etapele:

formularea problemei

elaborarea, identificarea și descrierea algoritmului de rezolvare

scrierea programului

programul trebuie sa fie bun, simplu și eficient.

testarea programului

realizarea, completarea și definitivarea documentatiei programului

exploatarea curenta

Notiunea de algoritmi

Cuvantul algoritm este de origine araba, derivand din numele matematicianului Abu Ja`far Mohammed ibn Musa al-Kahowarizmi.

Cunoscuta cu aproape 2000 ani I.H., notiunea de algoritm a devenit una din notiunile centrale ale matematicii actuale.

Sunt mai multe tipuri de algoritmi, cum ar fi:

algoritmul impartirii a doua numere

algoritmul extragerii radacinii patrate a unui numar

algoritmul rezolvarii ecuatiei de gradul II

S-a demonstrat apoi ca nu orice problema poate fi rezolvata alcatuind un algoritm de rezolvare a acesteia.

Se spune ca o problema este decidabila daca exista un algoritm pentru rezolvarea ei.

De exemplu, problema gasirii solutiilor unei ecuatii diofantice de gradul I de forma:

ax+by=c a,b,c sunt numere intregi, este decidabila.

CAPITOLUL 5

Limbaje de prezentare a algoritmilor ( pseudocod )

Descrierea in practica a algoritmilor in limbaj natural sau cu ajutorul schemelor logice prezinta unele dezavataje. Astfel, prima este prea detaliata pentru gustul programatorilor si de aceea nu este acceptata decat in cazuri speciale, in care trebuie sa sustina in fata unor nespecialisti in informatica, solutia adoptata.

Practica acceptata si alte metode de descriere, dintre care in ultima vreme s-au impus limbajele de prezentare a algoritmilor, numite si pseudocod.

Unele notatii folosite la descrierea algoritmilor

Formulele folosite in matematica si in tehnica sunt date pentru cazul general, aparand in ele atat numele unor cantitati variabile, cat si a unor constante.

In pseudocod subprogramele au urmatoarea forma generala:

ANTET

Secventa de instructiuni

END

ANTET poate fi de forma:

PROGRAM nume_program

PROCEDURE nume_procedura

FUNCTIE nume_functie

Apelul subprogramelor se face prin referirea de forma:

Nume ( lista_parametrii ) sau prin intermediul unui cuvant cheie cum ar fi cuvantul CALL:

CALL nume_procedura ( lista_parametrii )

Exista posibilitatea reluarii repetate a unui pas sau grup de mai multi pasi in interiorul unui aloritm; aceste procee repetitive pot fi definite ca iterative sau recursive.

Iterativitatea este procesul prin care rezultatul este obtinut prin executia repetata a uui set de operatii, de fiecare data cu alte valori de intrare.

Recursivitatea reprezinta un proces repetitiv prin care rezultatul de la un anumit pas se determina pe baza unuia sau mai multor rezultate obtinute in pasii anteriori.

Scheme logice

Schema logica este o forma de prezentare a algoritmului si a modului de lucru al acestuia sub forma grafica, folosind diferite simboluri grafice.

Se stie ca in practica programarii se acorda o importanta deosebita realizarii schemelor logice in perioada de debut, astfel ca dupa o anumita experienta in domeniu, se incearca tot mai des renuntarea la aceasta importanta etapa a proiectarii.

Figurile geometrice folosite la realizarea schemelor logice se numesc simboluri sau blocuri.

Principiile ralizarii schemelor logice:

orice schema logica incepe cu blocul START

dupa START, daca e necesar si daca sunt date de intrare, se citesc datele de intrare.

Dupa terminarea activitatii unui bloc de prelucrare, incepe activitatea blocului imediat urmator.

Dupa terminarea activitatii unui bloc de decizie isi incepe activitatea blocul conectat la iesirea corespunzatoare conditiei adevarate, in cazul unui bloc simplu, cu doua iesiri, se executa blocul conectat la DA daca este adevarata conditia specificata si blocul conectat la NU in caz contrar.

Schema logica isi inceteaza activitatea la blocul STOP.

Schemele logice pot aparea, functie de gradul lor de dificultate, fiind:

scheme logice simple

scheme logice ramificate

scheme loice cu cicluri

scheme logice cu cicluri ierarhizate

CAPITOLUL 6

Structuri fundamentale ale algoritmilor

Structura secvențialã sau liniarã desemneazã una sau mai multe operații ce se executã una dupã cealaltã, în mod liniar (secvențial).

Structura alternativãdesemneazã execuția unei secvențe de operații S1 sau a alteia S2, în funcție de îndeplinirea sau nu a unei condiții.

Structurile alternative sunt de mai multe tipuri:

Structura IF – THEN – ELSE, selecteazã succesiunea operațiilor ce urmeazã a fi executate, funcție de valoarea logicã de ,,adevãr” sau ,,fals” pe care o are în momentul respectiv condiția specificatã. Dacã este adevãratã condiția se urmeazã calea specificatã de ramura DA, altfel se urmeazã calea NU.

Blocul are deci o intrare și douã ieșiri, corespunzãtoare celor douã valori logice posibile pentru o expresie logicã (Adevarat și fals, Da și Nu)

Structura IF – THEN numitã și selecția simplã, este practic o formã particularã a selecției IF – THEN – ELSE, în care blocul de pe ramura Nu este vid.

În mod asemãnãtor se poate construi și selecția IF – ELSE, cu precizarea cã în acest caz blocul vid va fi cel de pe ramura Da.

Practic, în ambele forme particulare, se testeazã condiția logicã și se specificã doar succesiunea de operații ce trebuie efectuate pe una dintre ramuri. Pe ramura cu bloc vid nu se executã nimic.

Structura CASE – OF selecteazãuna dintre mai multe ramuri, în funcție de valoarea unui selector. De aceea structura de acest tip se mai numește selecție multiplã.

Structura repetitivã sau iterația indicã repetarea unei operații sau secvențe de operații S, atâta timp cât este îndeplinitã o anumitã conditie.

În funcție de momentul în care se face testarea condiției specificate, structurile repetitive sunt de mai multe tipuri:

Condiția poate fi testatã anterior execuției secvenței de comenzi S și atunci avem o structurã de tip WHILE – DO

Condiția se testeazã posterior execuției secvenței de comenzi S și atunci avem o structurã de tip DO – UNTIL

Structura repetitivã mai poate fi analizatã și din punct de vedere al numãrului de reluãri. Din acest punct de vedere, o structurã poate fi:

fãrã numãrãtor, cãci nu se cunoaște de la început numãrul de reluãri. Așa este cazul structurii de tip WHILE, indiferent de tipul ei.

cu numãrãtor, atunci când se știe sau se poate calcula automat numãrul de reluãri. Așa e cazul structurii repetitive de tip DO – FOR

Pentru a evita ciclarea la infinit a structurilor repetitive, programatorul trebuie sã aigure negarea condiției pentru a permite ieșirea din structurile WHILE – DO și DO – UNTIL.

Se observã cã diferența esențialã între cele douã structuri constã în faptul cã DO – UNTIL executã S cel puțin o datã, în timp ce WHILE – DO poate sã nu-l execute pe S deloc, dacã la intrarea în structurã condiția este deja falsã.

Programarea structuratã beneficiazã și de un puternic suport teoretic constând într-o construcșie de principii, termeni și teoreme matematice specifice.

Teorema de structurã Bohm și Jacopini spune:

Orice schemã logicã este echivalentã cu o schemã logicã structuratã

Dacã o organigramã cuprinde o mulțime F de acțiuni și o mulțime P de predicate, astfel încât organigrama sã fie structuratã și sã fie echivalentã cu cea inițialã.

Corolarul ,,de sus în jos”: Un program structurat este echivalent cu un program scris sub una din urmãtoarele forme:

P=Secvențial(f,g)

P=Alternativ(p,f,g)

P=Repetitiv(p,f)

Unde p este un predicat al lui P, iar f și g sunt secvențe structuratesau funcții ale programului.

Teorema de corectitudine:

Corectitudinea unui program structurat poate fi verificatã prin examinarea fiecãrui nod din arborescența sa. Dacã fiecare nod se verificã local, se spune cã programul structurat este corect.

CAPITOLUL 7

Evaluarea corectitudinii algoritmilor

Un program realizat trebuie sã fie corect, clar, sigur în funcționare, ușor de modificat, portabil, eficient, însoțit de o documentație corespunzãtoare. Existã numeroase tehnici de verificare și validare a algoritmilor, adresate în general practicienilor, dar și ușor accesibile unui începãtor în programare.

Dintre acestea amintim:

testarea programelor și depanarea programelor

verificarea formalizatã a programelor

cea mai slabã precondiție

cea mai tare postcondiție

instrucțiuni generalizate

sintaxa expresiilor logice

Acțiunea de testare a programelor se deosebește de celelalte faze prin care trec acestea (proiectare, programare, documentație, etc.) prin caracterul ei în aparențã “demolator”. Astfel, în timp ce alte faze au o esențã constructivã, testarea are în aparențã un caracter distructiv, deoarece scopul ei este de a pune în evidențã proasta funcționare a programului, de a gãsi hibele aeestuia și nu pãrțile sale bune. Din punct de vedere psihologic, programatorul însuși trebuie sã adopte în aceastã etapã 0 atitudine “dușmãnoasã” fațã de propriul program, pentru a putea gãsi defectele acestuia,

Analizând problema mai atent, realizãm de fapt cã scopul testãrii este în realitate tot constructiv, acela de a pune în funcțiune un program care sã funcționeze la parametri prevãzuți.

Se știe cã, într-un algoritm de calcul și deci, într-un program, este oricând posibilã prezența unei/unor erori, oricât de precisä și laborioasã ar fi metodologia de elaborare. Proeesul de detectare și apoi de eliminare a erorilor unui algoritm/program are douã componente, numite:

• verificare

• validare

Aceste douà aetivitãți ar trebui sã earacterizeze practic toate etapele prin care trece un program, de la formularea cerinței de rezolvare a unei probleme, la analiza acesteia, la identificarea și apoi descrierea algoritmului de rezolvare a problemei, a codificãrii datelor și validarea rezultatelor obținute.

Aceasta deoarece tot mai mulți specia1iști din diferite domenii aratã cã aceastã activitate de testare și validare nu este specificã doar activitäții de programare, ci se întâ1nește pretutindeni, acolo unde se produce sau construiește ceva; existã în acest sens controale efectuate la nivelul fiecärei operații sau grup de operații, dupã cum existã și un control final, produsului finit, pentru realizarea recepției lui finale.

În acest sens, activitatea de verificare și validare a unui produs program urmãrește în principal, urmàtoarele:

• descoperirea defectelor programului
• certificarea faptului cã programul va funcționa corect în condiții de exploatare curentã.

Testarea programului rãmâne metoda de bazã pentru verificarea corectitudinii unui program, succesul ei fiind condiționat în primul rând de experiența programatorului, de complexitatea și completitudinea setului de date folosite în procesul testãrii, de analiza riguroasã, atentã a rezultatelor obținute în urma fiecãrui test.

Prin testarea programului se înțelege deci executarea programului respectiv cu scopul de a descoperi o anomalie sau eroare. Ea se bazeazã pe construirea unor eșantioane de date de intrare care sã conducã la depistarea unor erori în functionarea programului, într-un timp cât mai scurt și cu efort cât mai mic.

Practic, pornind de la niște date de test construite de el, programatorul așteaptã sã obținã la final sau pe parcurs, anumite rezultate. Dacä acestea sunt corecte, complete sau în formatul așteptat avem cel putin o eroare în execuția programuiui. Putem spune cã succesul testãrii depinde de “arta” programatorului de a-și construi setul de date de test.

Trebuie sä precizãm insã faptul cã relevanța testului depinde de numãrul eșantioane1or de date de test, dar mai ales de calitatea datelor alese. În acest sens, au apãrut, în ultimul timp, o serie de metode de elaborare a datelor de test, care ajutã programatorul, oferindu-i posibilitatea de a aborda sistematic activitatea de testare a programelor, cu o probabilitate crescutã de depistare a erorilor.

Aceste metode pot fi denumite:

• testarea funcționalã sau metoda cutiei negre, care presupune construirea datelor de test astfel încât sã permita testarea fiecãrei funcțiuni a programului;

• testarea structuralã sau rnetoda cutiei transparente, care presupune construirea datelor de test astfel încât toate pãrțile programului sã poatã fi testate.

Succesul activitãții de testare constã deci în conceperea unor date de intrare prin prelucrarea cãrora defectele algoritmului și deci și a programului sã fie puse în evidențã prin observarea și analiza rezultatelor obținute.

De aceea el este în mare mãsura dependent de experiența și îndemânarea programatorului, de abilitatea lui de a-și construi datele de test cât mai complete, complexe, cuprinzãtoare din punct de vedere al situațiilor sau valorilor de excepție ce pot apare în execuția curectã a programului.

Testarea unui program trebuie sã se finalizeze, pentru a fi utilã, cu semnalarea erorii și localizarea ei. De aceea, testarea programului este urmatã de depanarea lui.

Depanarea unui program constã în localizarea erorii, determinarea naturii sale și corectitudinea ei. Ea se poate face în mod:

sttic, dupã executarea programului

dinamic, în timpul execuției acestuia

Depanarea simbolicã, o altã metodã de depanare, este mai ușor de utilizat, deoarece oferã posibilitatea de a urmãri executarea programului la nivel de limbaj sursã. Limbajele de programare oferã, în ultimile lor versiuni, un depanator simbolic integrat, care permite depanarea ușoarã, plãcutã și eficientã a programelor prin urmãtoarele operații:

• executarea pas cu pas a programului (un pas inseamnã de fapt o instrucțiune executabilã);

• observarea, în timpul execuției, a valorilor unor variabile sau expresii specificate de programator (care apar într-o fereasträ specialã – Watch Window);

• specificarea unor puncte de suspendare a execuției programului;

• modificarea valorilor unor variabile.

În activitatea de testare și depanare a programelor, erorile datorate variabilelor neinitializate sunt greu de semnalat și de localizat, mai ales atunci când aparent totul funcționeazã corect. În acest sens amintim variabila cu rol de indice (numãrãtor) care asigurã parcurgerea elementelor unui vector. Aceasta trebuie inițializatã cu poziția primului element din șir care trebuie prelucrat și apoi testatä și comparatã valoarea ei cu cea finalã. Deasemenea, expresia care stabilește dacã un ciclu se executã sau nu trebuie astfel formulatã sau initializatã încât sã asigure sau nu prima execuție, așa cum necesitã algoritmul de prelucrare descris. În acest sens, trebuie sã facem precizarea cä adeseori, suntem nevoiți sã facem noi, prin program, inițializarea variabilei care controleazã execuția ciclului, pentru a asigura execuția lui pentru prima datã. Este vorba de ciclul cu testarea inițialã a condiției, la care reluarea ulterioarã va fi hotãrâtã de valoarea pe care respectiva variabilã o primește, în timpul execuției programului, în cadrul ciclului. Deci, ciclul cu testarea inițialã a condiției trebuie sã fie bine analizat, verificat și testat din punctul de vedere al expresiei care-i controleazã reluarea.

Practica a dovedit, în timp, cã oricât de numeroase ar fi testele efectuate asupra unor programe foarte complexe, ele nu pot garanta funcționarea corectã a acestora. Ele rãmân deosebit de utile pentru semnalarea multora dintre erori și deasemenea pentru familiarizarea programatorului cu algoritmul, cu modul sãu de lucru.

Proprietatea P se numește precondiție sau proprietate finalã, iar proprietatea Q postcondiție san proprietate finalã.

Practica a dovedit cä existã situații când pentru un algoritm A și o postcondiție datã, nu intereseazã o precondiție oarecare, ci se cautã “ cea mai bunã” precondiție care rezolvã algoritmul dat.

Fie secvența de comenzi, care calculeazã factorialul unui numãr >=2:

(n>=2)

f:=1;

i:=1;

while i <n do

begin

i:=i+1;

f:=f*i

end

(f=n!)

Se poate observa factorialul este calculat corect și dacã n pornește de la valoarea 1 (n>=1). Deci, precondiția n>=2 poate fi inlocuitã cu n>=1 care se considerä o precondiție mai bunã, care descrie o mulțime de date inițiale mai cuprinzãtoare, obtinutã prin adãugarea valorii 1.

O analizã mai atentã a algoritmului aratã cã precondiția n>=1 poate fi inlocuitã cu n>0 consideratä o precondiție mai bunã, care atestã capacitatea algoritmului de a calcula factorialul oricãrui numãr natural, mulțimea datelor initiale fiind din nou mãritã prin adãugarea valorii 0 (0!=1).

CAPITOLUL 8

Limbaje de programare

Un limbaj de programare este un ansamblu de simboluri, cuvinte, instrucțiuni și semnificații atribuite acestora, utilizat pentru descrierea algoritmilor. Limbajul de programare este astfel un mijloc prin care programatorul comunicã cu calculatorul.

Programul este o succesiune de intrucțiuni aparținând unui limbaj de programare, prin care se descriu operațiile la care sunt supuse datele și ordinea de execuție a acestora, pentru rezolvarea automatã a unei probleme date. Un program reprezintã o alta modalitate de descriere a unui algoritm de rezolvare a unei probleme date.

Pentru a înlãtura acest mare dezavantaj au apãrut limbajele simbolice și apoi limbajele de programare evoluate care prin intermediul ansambloarelor și compilatoarelor de care dispun, permit traducerea automatã a instrucțiunilor scrise într-un limbaj apropiat de limbajul curent de limbajul binar. Limbajele de programare reprezinta principalele mijloace de comunicare om-masina, evolutia lor fiind nemijlocit legatã de cea a calculatoarelor electronice, a caror era a inceput prin anii 1944.

Dintre limbajele de programare evoluate utilizate pe toata gama sistemelor de calcul menționãm:

Basic

Algol

Fortram

Cobol

Pascal

C

PL/1

În ultimul timp s-au impus tot mai multe limbaje de inteligențã artificialã și sisteme expert cum sunt:

C++

Lisp

Prolog

precum și programarea pe obiecte ( Basic, C, etc. ).

Orice limbaj de programare presupune definirea urmatoarelor elemente componente:

alfabetul

vocabularul

gramatica

punctuatia

semantica

Rezultatul activitãții de programare îl constituie programul scris ca text într-un limbaj de programare. Un astfel de program se numește program sursa. El este scris printr-un editor de texte acceptat de limbajul de programare respectiv.

Fiind scris ca format text, programul sursã nu este înțeles de cãtre șistemul electronic de calcul. Pentru aceasta este necesara traducerea lui intr-un cod intern, accesibil calculatorului. Aceastã operație se realizeazã cu un program translator numit compilator. Compilatorul este componenta software care realizeazã traducerea programului sursa în cod intern, rezultand așa numitul program cod obiect. Lucrul cu un anumit limbaj de programare presupune existenta compilatorului pentru acel limbaj. Ansamblul format din limbajul de programare și programul translator asociat, formeaza sistemul de programare.

Limbajul de programare pascal face parte din categoria limbajelor de programare evoluate de nivel inalt. Un program structurat este constituit din unitati functionale bine definite, ierarhizate conform naturii specifice a problemei de rezolvat. În interiorul unei astfel de unitati functionale, structurarea se manifesta atât la nivelul operațiilor de executat cât și la cel al datelor de prelucrat.

Programarea structurata este o metoda independenta de limbajul de programare utilizat. Limbajul Pascal include conceptele programarii structurate în ambele sensuri ale efortului de abstractizare presupus de realizarea unui program: ogranizarea datelor și conceperea succesiunii de operații.Limbajul Pascal a fost implementat pânã în prezent pe o mare varietate de calculatoare, având un inalt grad de portabilitate comparativ cu implementarea altor limbaje de programare.

Un program reprezintã o mulțime ordonatã de instrucțiuni, asociatã unui algoritm de rezolvare a unei probleme care comandã operațiile de prelucrare a datelor.

Instrucțiunea reprezintã exprimarea intr-o forma riguroasa a unei operatii și precizeaza functia și adresele operanzilor.Relația dintre cele 3 elemente: algoritm, limbaj și program poate fi exprimatã astfel:

Blocul executabil constituie lanțul de instructiuni prin care este codificat programul în limbajul pascal, deci prin care se descrie algoritmul de prelucrare. Acestea sunt cuprinse între Begin și End.

Este interzis sa dam nume diverselor obiecte care sa coincida cu acele cuvinte rezervate. În partea declarativa orice declaratie careia nu i se asociaza obiectele legate de programul în cauza se poate omite.

Toate obiectele manipulate în pascal poarta un nume. Acest nume se numeste identificator. Identificatorii sunt denumiri prin care se desemneaza datele, procedurile, functiile, programele.

Un tip de date reprezintã setul de valori pe care le poate lua elementul respectiv, împreunã cu mulțimea operațiilor care se aplica asupra acestora. Orice variabila utilizata în program trebuie sa apartina unui tip. Tipul de date poate fi: predefinit și construit pe baza celor predefinite.

Din punct de vedere al posibilitatii de modificare a valorii în faza de executie a programului, datele se pot clasifica în:

date variabile

date constante

Tipurile intregi de date sunt:

Byte

Word

Shortint

Integer

Longint

Tipul real reprezintã un numãr real cuprins între douã limite care diferã de la un compilator la altul și de la un tip la altul.

Astfel tipurile reale pot fi:

real

single

double

extended

comp

Funcțiile SUCC și PRED nu functioneazã, tipul REAL nefiind ordinal.

Tipul Caracter ( CHAR )

O variabilã de tip caracter poate avea drept valoare un caracter. O constanta de tip caracter poate fi:

`a` `:` literele mari au alte valori decat cele mici

x:char se reprezinta în memorie pe un octet, adica 255 coduri.

x:=`a` sau x:=a

Existã funcții care permit trecerea de la caracter la codul ASCII și invers.

CHR ( cod ) este o funcție care intoarce ca rezultat caracterul respectiv.

x:=chr(64)

ORD ( caracter ) este o funcție care intoarce codul ASCII al caracterului respectiv.

Tipul Boolean este un tip ordinal, enumerativ, care ocupã un octet memorie și poate lua 2 valori logice: adevarat și fals.

Declarația de tip se face :

Type boolean = ( True, False )

Tipul Declarat ( Enumerativ ) este definit de utilizator ca o lista ordonatã, prin enumerarea valorilor posibile astfel:

TYPE identif tip = ( lista elemente )

TYPE zi-sapt= ( luni, marti, … , duminica )

Tipul Subdomeniu se mai numeste tip interval și se defineste ca submultime a unui tip ordinal prin precizarea intervalului inchis de valori. Toate caracteristicile tipului parinte ( Integer , Char ) se regasesc în tipul subdomeniului, singura deosebire dintre ele constand în multimea valorilor pe care le poate lua.

Declararea constantelor:

CONST ident = valoare;

Pot fi numai de tip standard ( scalar ) și se declarã în sectiunea CONST

Valoarea constantei nu poate fi modificatã în timpul rulãrii programelor.

Orice încercare de a atribui constantelor o valoare, chiar dacã este egalã cu cea inițialã, va genera un mesaj de eroare.

Se asigurã astfel protecția valorilor.

Declarația de tip

TYPE Identif_tip=definiție tip;

Declarația de variabile

Var identif var: spațiu tip var

Dacã sunt mai multe variabile de acelasi tip, se inșirã separate cu `,`

Declarația de funcții și proceduri

function nume_funcție (declarație de var): tip rez;

function fact (n: integer):integer;

Mai multe variabile se separã prin `;`

Instrucțiuni pascal: Limbajul pascal este puternic orientat spre programarea structuratã, fiind conceput astfel încât sa implementeze corect conceptele proiectãrii și realizãrii structurate și modularizate a programelor. Progamul scris într-un limbaj de programare evoluat deci în pascal, se numeste progream sursã.

Instrucțiuni simple:

de atribuire

apeluri de procedura

instrucțiunea de salt necondiționat(goto)

instrucțiunea vidã

Instrucțiuni simple

Prin instructiuni simple se realizeazã o mare parte din operatiile de bazã a algoritmilor de prelucrare. Instructiunea vidã descrie acțiunea vidã, ea este definitã prin lipsa în contextul unor construcții pascal, fãrã a avea o mnemonica explicitã.

Se prezintã ca o linie goala urmatã de `;`

i:=1 ; 2 instrucțiuni vide

If x>0 then

x:=x+1

else;

Instrucțiunea de atribuire evalueazã o expresie și atribuie rezultatul obtinut unei variabile sau functii.

Are formatul general:

Identificator:=valoare;

Prioritatea operanzilor în Pascal:

Expresii logice sunt cele care în urma evaluarii produc un rezultat logic de TRUE sau FALSE ( Boolean ). Ele se prezintã fie sub forma unor condiții simple, fie sub forma unor conditii compuse, formate din mai multe conditii simple legate prin operatorii logici: AND, OR, NOT.

Dacã nu suntem siguri de prioritatea anumitor operatori este necesara utilizarea parantezelor.

Apelul de procedurã:

Orice rutinã scrisã de noi, pentru a efectua anumite operații, se numește procedurã.

Procedurile întâlnite în program ca simple instrucțiuni genereazã o serie de operații:

compilatorul cautã numele de procedurã în biblioteca sa; dacã nu este gãsit acolo procedura e cautatã în lista de declarații de proceduri a programului; dacã nu este nici acolo se afiseazã un mesaj de eroare.

dacã este gãsitã procedura e apelatâ.

Instructiunea de salt neconditionat GOTO

Format : GOTO eticheta;

La intalnirea ei se executa un salt la linia care este precedata de eticheta urmata de `:`

IF delta >= 0 THEN

GOTO 30

ELSE

WRITE (` ecuatia nu are solutii`);

30: x1:=(-b+sqrt(delta))/(2*a);

x2:=(-b-sqrt(delta))/(2*a);

write ( x1, x2 );

end.

Instructiuni structurate

Instructiunea compusa este o secventa de instructiuni delimitata de cuvintele rezervate BEGIN, END.

Format :

BEGIN lista-instr END;

Efectul executiei instructiunii IF:

Se evalueaza conditia specificata.

Instructiuni pentru realizarea structurilor repetitive

Instructiunea WHILE realizeaza structura repetitiva conditionata anterior.

Format:

WHILE conditie DO instructiune; este echivalenta cu o constructie formata din urmatoarele instructiuni:

IF conditie THEN

BEGIN

instructiune

GOTO 1

end.

Instructiunea WHILE se mai numeste instructiune cu test initial.

Instructiunea Repeat

Realizeaza „structura repetitiva conditionata posterior”.

Format:

REPEAT instructiune UNTIL conditie ;

REPEAT

instructiune

UNTIL

conditie;

Ca și ELSE, inainte de UNTIL mi se pune `;`.

Instructiunea FOR ( ciclu cu contor )

Realizeaza structura repetitiva cu numarator ( contor de numarare ).

Format:

1) FOR contor:=val initiala TO val finala

DO instructiunea;

2) FOR contor:=val initiala DOWNTO val finala

DO instructiunea

Instructiuni de citire și scriere a datelor

În pascal, citirea și scrierea nu se realizeaza prin instructiuni, ci prin proceduri specializate în acest sens, proceduri standard ale limbajului.

Aceste fișiere în Turbo Pascal sunt asociate tastaturii și respectiv ecranului.

Fisierele INPUT și OUTPUT conțin excusiv șiruri de caractere organizate pe linii. Liniile sunt încheiate de caracterul special standard EOL introdus automat la apasarea tastei ENTER.

Citirea datelor din fișierul INPUT

Existã doua proceduri standard predefinite în Pascal:

-Read

-Readln

Procedura READ

Format:

READ ( variabila{,variabila});

variabilele pot fi doar de tip CHAR, INTEGER, REAL sau STRING.

Procedura READLN

Format:

READLN ( variabila{,variabila});

Scrierea datelor:

-Write

-Writeln

Instrucțiuni de selectie multiplã ( CASE )

Format:

CASE expresie OF

lista etichete CASE:instructiune;

END;

Structura de tablou (Vector, Matrice): structura de tablou în Pascal este mai flexibilã decât în alte limbaje de programare, fiind rezultatul compunerii a douã tipuri:

tipul de baza al tabloului

tipul de indexare al tabloului

Setul de caractere : Acestea sunt entități formate din caractere :

Literele mari și mici ale alfabetului limbii române: A-Z, a-z;

Cifrele sistemului de numerotație zecimal: 0-9;

Caractere speciale: =-/^(){}[].,;:_!@#$%&etc;

Caractere speciale perechi: <=,>=,=,<>;

Separatorii : spațiu, tab, Enter.

Identificatorii : Pot fi o variabilă, o contantă, un tip definit de utilizator, o enumerare, o procedură, o funcție, un obiect, o metodă, o proprietate, un control, o formă, un modul sau chiar proiectul însuși. Un proiect Basic poate să conțină maxim 32000 identificatori.

Comentariile sunt șiruri de caractere care au în față caracterul apostrof (‘) și servesc pentru a face mai lizibil textul programului , pntru a documenta programul.

Fiecare tip de dată permite o serie de operații. Astfel pentru valorile unui tip întreg se pot face următoarele operații : +, -, *, împărțirea întreagă, împărtirea reală, restul împărțirii întregi, ridicarea la putere.

Constantele : reprezintă o valoare fixă care nu se schimbă în timpul execuției programului sau de la o execuție la alta. Pot fi de 2 tipuri : intrinseci și simbolice.

Variabilele : reprezintă o locație de memorie internă care servește pentru stocarea temporară a datelor și care se identifică printr-un nume. Tipul variabilelor din Basic sunt : variant, byte, boolean, integer, long, single, double, currency, date și object.

Variabilele din Basic sunt caracterizate prin :

nume

tip de data

domeniu.

Utilizatorul poate defini în cadrul modulului său și tipuri de date proprii, deci tipuri de date predefinite. Pentru aceasta, declarația de tip se face de către programatori în prima parte a modului de cod cu ajutorul instrucțiunii :

TYPE – definire variabilă

END TYPE

Operatorii : Reprezintă comenzi speciale pentru operațiile ce pot fi executate cu datele din program. Basic pune la dispoziție 4 tipuri de operatori : aritmetici, logici, de comparare și de concatenare.

O funcție este o procedură care efectuează o anumită sarcină într-un program.

Dialogul standard cu utilizatorul

Funcția INPUT- apelul funcției INPUT permite preluarea de date de la tastatură.

Funcții matematice și statistice : ABS, EXP, INT, LOG, RND, SQR, ATN, SIN, COS, TAN ;

Funcții pentru șiruri de caractere : LCASE$, UCASE$, LTRIM$, RTRIM, CHR, ASC, LEN, VAL, LEFT$, RIGHT$, MID$, INSTR,

Funcții pentru conversia întregilor : INT, CINT ;

Funcții pentru conversia tipului de dată : CDBL, CLNG.

Funcții pentru lucrul cu date calendaristice : TIME$, DATE$ ;

O procedură este o secvență de instrucțiuni executate ca un tot unitar sau partajabile. Există trei tipuri de proceduri : SUB, FUNCTION, Tip de proprietate. Sintaxa generală a unei proceduri este : Private/Public/Static/Sub

…………………………….

End Sub.

Instrucțiuni de atribuire – atribuirea se poate efectua prin instrucțiunile :

Let – pentru valori atribuite variabilelor și proprietăților ;

Set – pentru atribuirea de obiecte la o variabilă de tip obiect ;

Lset și Rset – pentru atribuiri speciale de șiruri sau tipuri definite de utilizator

Terminarea execuției unui program sau oprirea temporară a acestuia sepot realiza prin instrucțiunile : DoEvents, End, Exit, Stop.

Se știe că în cadrul algoritmilor de rezolvare a problemelor se întâlnesc, în afara unor secvențe de operații care se execută liniar, în mod necondiționat, o serie de operații care necesită testarea unor condiții, funcție de care se o succesiune de operații sau alta, sau o serie de operații care se execută în mod repetat. Avem de a face cu cele trei tipuri de structuri fundamentale :

secvențială /liniară ;

alternativă/de decizie ;

repetitivă.

Limbajul de programare Basic implementează aceste structuri de control ale programului prin comenzi corespunzătoare, deci :

comenzi pentru structuri alternative ;

comenzi pentru structuri repetitive.

Comenzile pentru structurile alternative : If…. Then, If…Then…Else, Select Case.

Comenzile pentru structurile repetitive : While…Wend, Do….Loop, For….Next, For Each… Next.

Fișierele conțin colecții de date omogene ca natură și criterii de prelucrare, memorate pe discul magnetic .

CAPITOLUL 9

Algoritmi speciali

1. Sortarea unui vector

Prin sortare se înțelege aranjarea elemntelor unei mulțimi , în ordine crescătoare/descrescătoare a valorilor acestora. Există mai multe variante de sortare : sortarea prin interschimbare, prin selecție, prin inserție,

2. Interclasarea a doi vectori de dimensiuni variabile.

Prin interclasare se înțelege procesul de obținere din două sau mai multe mulțimi ordonate, o nouă mulțime, ordonată după același criteriu. Există mai multe variante de interclasare :

Varianta 1 :

Presupune compararea a două elemente , câte unul din fiecare vector inițial, cu scrierea celui mai mic dintre ele în vectorul rezultant și trecerea la următorul element al vectorului inițial din care s-a preluat.

Varianta 2 :

Presupune obținerea vectorului rezultant într-un proces unic de comparare. Pentru a continua procesul în cazul în care se epuizează unul din vectorii inițiali, ultimul element al acestuia va primi o valoare mai mare decât oricare din valorile regăsite, de regulă, în vectorii inițiali.Această valoare poartă denumirea HIGH-VALUE (HV) . Procesul se încheie când ambii vectori inițiali au fost parcurși integral, deci elementele finale au valoarea HV.

CAPITOLUL 10

Tehnici de programare

1. Programarea modulară. Tabele de decizie

Programarea modulară are ca obiectiv reducerea empirismului artizanal folosit în elaborarea programelor și instaurarea principiilor ingineriei programării, vizând obținerea unor programe corecte și fiabile, reducerea costului elaborării, documentării, testării, întreținerii și dezvoltării produselor software.

Modularizarea programelor.

Algoritmii de rezolvare a problemelor complexe se întocmesc și/sau pot fi descompuși în manieră sistematică, după criteriul funcțional, în mod ierarhic, până la nivel de subalgoritm/funcție elementară, ca element terminal în structura unității funcționale(UF).

Un modul funcțional se caracterizează prin :

Nume extern și/sau intern;

Funcție logică perfect definită;

Punct de intrare și punct de ieșire unice;

Relația cu modulele din aval și amonte-interfată;

Posibilitatea elaborării și testării independente (în cadrul contextului său);

Tipuri de module funcționale :

Module directoare sau de comandă sau monitoare;

Module de prelucrare sau module-funcție;

Module mixte;

Module comune;

Module speciale;

Module nefuncționale;

Module monitor.

2 Monitorizarea modulelor.

Tipul de monitorizare poate varia în limite relativ largi, în funcție de filozofia de realizare a sistemului, de facilitățile de utilizare puse la dispoziția beneficiarului său și de deciziile de proiectare adoptate, astfel :

Monitoare pure

Monitoare complexe

Monitoare foarte complexe.

3. Interconectarea modulelor.

În mod ideal , modulele trebuie să fie cât mai independente pentru a reduce gradul de cuplare a acestora. Gradul de interconectare poate fi :

Minimal

Normal;

Coeziunea modulelor.

Se disting mai multe nivele de coeziune :

Întâmplătoare

Logică

Temporală

Procedurală

Comunicațională

Secvențială

Functională.

.4. Tehnici de modularizare

Construirea unor programe modularizate implică utilizarea unor tehnici și procedee foarte diversificate :

Utilizarea tabelelor de decizie și a diagramelor de optimizare

Utilizarea parametrilor simbolici

Asigurarea și definirea centralizată și standardizată a parametrilor statici, a datelor comune, a tabelelor de decizie, a listelor.

Separarea funcțiilor de intrare/ieșire

Evitarea reutilizării zonelor de memorare temporară intermodule

Nealterarea valorii constantelor.

5. Tabele de decizie (TD)

Tabele de decizie reprezintă un procedeu de reprezentare a algoritmilor cu număr mare de decizii bazate pe condiții complexe sau dinamice, fiind astfel un mijloc eficient de modularizare. TD conțin două tipuri d intrări :

Condiții elementare simple sau compuse aplicate unor variabile cu valori alternatil-exclusive de tip alfanumeric sau logic;

Condiții compuse aplicate asupra condițiilor elementare prin conjuncție.

CAPITOLUL 11

Tehnici de programare structuratã

Cele mai utilizate tehnici de programare structurată sunt :

Recursivitatea ;

Metoda Backtracking;

Metoda Divide et impera;

Metoda Greedy;

Metoda Branch and Bound;

Metode euristice;

Metoda programării liniare;

Metoda programării dinamice.

1. Recursivitatea

Este o tehnică de programare utilizată frecvent , în implementarea funcțiilor și procedurilor . La baza recursivității stă stiva, care este gestionată în mod implicit, în această zonă de memorie salvându-se automat, la fiecare la fiecare apel de funcțieurmătoarele informații :

Valorile parametrilor de tip valoare;

Adresele parametrilor de tip variabilă;

Variabilele locale ale subprogramului;

Adresa de întoarcere la instrucțiunea aflată după instrucțiunea de apel.

2. Tehnica “Backtracking”

Această tehnică se folosește în rezolvarea unor probleme cum ar fi :

Generarea permutărilor de n elemente;

Generarea aranjamentelor;

Generarea combinărilor;

Generarea partițiilor unei mulțimi;

Problema celor N dame;

Produsul cartezian a N mulțimi;

Problema Comis-voiajorului;

Problema plății unei sume S utilizând N tipuri de monede;

3. Metoda “ Divide et Impera”

Exemple de probleme rezolvate cu această metodă : căutare binără.

4. Metoda Greedy

Caracteristicile acestei metode sunt :

La intrare avem o mulțime A cu N elemente

Se cere selectarea unei submulțimi B a lui A sau o ordine de prelucrare a elementelor lui A care să optimizeze o funcție obiectiv dată . Se cere deci o singură soluție.

Elementele mulțimii A se parcurg pe rând, după o eventuală rearanjare a lor, în vederea testării lor pentru adăugarea acestora la B.

CAPITOLUL 12

Probleme

Problema nr. 1

Sa se prezinte sub forma de chema logicã și instrucțiunea unui limbaj de programare sau pseudocod un algoritm eficient care sã determine pentru o matrice de n linii și m coloane a cãrei elemente se citesc de la tastaturã urmãtoarele:

a) media aritmeticã a elementelor de pe fiecare linie

b) media aritmetica a elementelor de pe fiecare coloanã

c) valoarea elem. maxim și locul în care acesta se aflã de pe fiecare linie

d) valoarea elem. maxim și locul în care acesta se aflã de pe fiecare coloanã

e) valoarea elem. minim și locul în care acesta se aflã de pe fiecare linie

f) valoarea elem. minim și locul în care acesta se aflã de pe fiecare coloanã

g) elementul maxim la nivel de matrice

h) elementul minim la nivel de matrice

program matricea_de_la_curs;

type matrice=array[1..20,1..20] of integer;

var a:matrice;

max,max2,min,min2,w,z,i,p,maa,m,n,d,e,f,g,minn,maxx,j,s,ma,x,y:integer;

begin

writeln('dati nr de linii și nr de coloane');

write('n=');

readln(n);

write('m=');

readln(m);

for i:=1 to n do

for j:=1 to m do

begin

writeln('a[',i,',',j,']=');

read(a[i,j]);

end;

a) for i:=1 to n do

begin

s:=0;

for j:=1 to m do

s:=s+a[i,j];

ma:=(s div m);

writeln('media aritmetica pe linia ',i ,'=',ma);

readln;

end;

b) for j:=1 to m do

begin

p:=0;

for i:=1 to n do

p:=p+a[i,j];

maa:=(p div n);

writeln('media aritmetica pe coloana ',j,'= ',maa);

readln;

end;

c) for i:=1 to n do

begin

max:=-3200;

for j:=1 to m do

if a[i,j]>max then

begin

max:=a[i,j];

x:=j;

end;

writeln('maximul liniei ',i,' este elementul a[',i,',',x,'] și este egal cu ',max);

readln;

end;

d) for j:=1 to m do

begin

max2:=-3200;

for i:=1 to n do

if a[i,j]>max2 then

begin

max2:=a[i,j];

y:=i;

end;

writeln('maximul coloanei ',j,' este elementul a[',y,',',j,'] și este egal cu ',max2);

readln;

end;

e) for i:=1 to n do

begin

min:=3200;

for j:=1 to m do

if a[i,j]<min then

begin

min:=a[i,j];

w:=j;

end;

writeln('minimul liniei ',i,' este elementul a[',i,',',w,'] și este egal cu ',min);

readln;

end;

f) for j:=1 to m do

begin

min2:=3200;

for i:=1 to n do

if a[i,j]<min2 then

begin

min2:=a[i,j];

z:=i;

end;

writeln('minimul coloanei ',j,' este elementul a[',z,',',j,'] și este egal cu ',min2);

readln;

end;

g) maxx:=-3200;

minn:=3200;

for i:=1 to n do

for j:=1 to m do

if a[i,j]>maxx then

begin

maxx:=a[i,j];

d:=i;

e:=j;

end;

h) for i:=1 to n do

for j:=1 to m do

if a[i,j]<minn then

begin

minn:=a[i,j];

f:=i;

g:=j;

end;

writeln('elementul maxim al matricei este a[',d,',',e,']=',maxx);

writeln('elementul minim al matricei este a[',f,',',g,']=',minn);

readln;

end.

SCHEMA LOGICÃ:

Problema nr. 2

Se dã un vector cu n elemente numere întregi. Sã se mute la sfârșitul vectorului elementele sale nule pãstrând ordinea celorlalte elemente.

program ddd;

type vector=array[1..20] of integer;

var v:vector;

n,i,j,k:integer;

begin

write('dati numarul de elemente');

readln(n);

for i:=1 to n do

begin

write('v[',i,']=');

readln(v[i]);

end;

for i:=1 to n-1 do

for j:=i+1 to n do

if v[i]=0 then

begin

k:=v[i];

v[i]:=v[j];

v[j]:=k;

end;

for i:=1 to n do

writeln('v[',i,']=',v[i]);

readln;

end.

SCHEMA LOGICÃ:

Problema nr. 3

Să se realizeze un program pentru evaluarea expresiei:

A +B, dacă C≥0

E=

A-B, dacă C<0

Analizând problema dată, se observă că datele de intrare sunt A, B și C. Algoritmul va testa pe C, și, în funcție de valoarea sa, va calcula pe E fie ca A+B, fie ca A-B.

program prg2_pagina_187;

var a,b,c:integer;

e:real;

begin

write('Introduceti valoarea pentru a= ');read(a);

write('Introduceti valoarea pentru b= ');read(b);

write('Introduceti valoarea pentru c= ');read(c);

e:=0;

if (c<0) then e:=(a*a)-b

else

if (c=0) then e:=sqrt((a*a)-b)

else e:=(1/(a*a))-b;

write('E:= ',e:8:2);

readln;

end.

SCHEMA LOGICÃ:

Problema nr. 4

Sa se verifice dacã 2 numere sunt prietene

Doua numere sunt prieten dacã primul numar este = cu suma divizorilor celui de-al doilea mai putin el insusi și cel de-al doilea este egal cu suma divizorilor primului numar mai putin el insusi

n=220 1+2+4+5+10+11+20+22+44+55+110

m=284 1+2+4+71+142

s1 = suma divizorilor lui n mai putin el insusi

s2 = suma divizorilor lui m mai putin el insusi

n și m prietene dacã s1=m și s2=n

program lalala;

var m,n,s1,s2,i:integer;

begin

write('n=');

readln(n);

write('m=');

readln(m);

for i:=1 to n-1 do

if n mod i=0 then s1:=s1+i;

for i:=1 to m-1 do

if m mod i=0 then s2:=s2+i;

if (s1=m) and (s2=n) then writeln('aceste doua numere sunt prietene')

else writeln('din pacate nu sunt prietene');

readln;

end.

SCHEMA LOGICÃ:

Probleme de logicã:

Problema nr. 5:

În această vară, bătrânul Trică a murit, lăsând proprietățile sale ca moștenire nepotului său Andi, prietenul meu. El a moștenit și castelul Towertia, bântuit de fantome. Începând cu ora 12 noaptea până dimineața se aud în tot castelul două zgomote descifrabile: un cântat duios la vioară și un râs puternic. Andi a observat anumite obiceiuri:

când el cântă la pian și fantoma nu râde, fantoma care cântă la vioara își schimbă activitatea (dacă cânta-tace, dacã tăcea-cântă); altfel ea face în fiecare minut ce făcea în cel precedent;

când fereastra este închisă fantoma care râde face ce făcea cealaltă fantomă în minutul precedent (râde dacă cealaltă cântă, tace dacă cealaltă tăcea);

când fereastra este deschisă, fantoma care râde face opusul la ceea ce cealaltă făcea în minutul precedent.

Andi vrea să știe cum să scape de fantome (să le facă să tacă)!

Rezolvare:

3: când fereastra este deschisă, fantoma care râde face opusul la ceea ce cealaltă făcea în minutul precedent.

1: când el cântă la pian și fantoma nu râde, fantoma care cântă la vioara își schimbă activitatea (dacă cânta-tace, dacã tăcea-cântă); altfel ea face în fiecare minut ce făcea în cel precedent;

2: când fereastra este închisă fantoma care râde face ce făcea cealaltă fantomă în minutul precedent (râde dacă cealaltă cântă, tace dacă cealaltă tăcea)

Problema nr. 6

Duminică, Marius și Radu au fost să vadă la hipodrom cursa de cai. Mai întâi s-au dus să vadă caii. Au făcut pariuri pe primele cinci locuri.

Radu a crezut astfel:

Doodoo; 2) Azur; 3) Elfy; 4)Candy; 5) Emily.

Marius a pariat astfel:

Azur; 2) Emily; 3)Candy; 4)Doodoo; 5) Elfy

Rezultatele au arătat că nici unul nu a căștigat:

1)Marius nu a ghicit locul nici unui cal

2)Marius nu a ghicit nici măcar ordinea a câte doi cai unul după altul

Radu a fost mai aproape de realitate:

3)A ghicit locurile a doi cai;

4)A ghicit ordinea finala a două perechi de cai unul după altul.

Care a fost rezultatul ?

Urmărind tabelul de mai sus putem afirma că:

Pe locul I nu va fi Doodoo sau Azur

Pe locul II nu va fi Emily

Pe locul III nu va fi Candy

Pe locul IV nu va fi Doodoo

Pe locul V nu va fi Elfy

Deci Doodoo poate fi pe locurile II sau V.

Ordinea este:

Problema nr. 7

Un batranel se duce la piațã (mai bine statea acasa) sã vândã niște ouã. Un tânãr neatent l-a îmbrâncit și coșul a cãzut spãrgând ouãle. vinovatul vrând sã își rãscumpere greșeala l-a întrebat :

-Câte ouã au fost în coș?

-Nu-mi aduc aminte, dar știu cã dacã le scoteam câte 2,câte 3,câte 4,câte 5 sau câte 6, în coș rãmânea mereu un singur ou, iar dacã le scoteam câte 7 , nu rãmânea nici unul.

Dupã câteva minute de gândire, tânãrul a calculat câte ouã erau.

Tu poți gãsi numãrul de ouã din coș?

Rezolvare:

batrânelul spune cã dacã scotea ouãle câte 7 nu mai rãmânea nici un ou un coș de unde tragem concluzia cã numãrul ouãlor trebuie sã fie un multiplu de 7

mai spune cã dacã le scotea câte 2,câte 3,câte 4,câte 5 sau câte 6, în coș rãmânea mereu un singur ou de unde rezultã cã din numãrul care este multiplu de 7 dacã scadem 1 trebuie sã rãmânã un numãr care sã fie divizibil și cu 2 și cu 3 și cu 4 și cu 5 și cu 6

deci cãutãm un numãr care sã aibe ultima cifrã 1 sau 6

astfel 7, 14 sunt excluse

incercãm 21:7=3

21-1=20:2=10

20:3 nu este divizibil

– cãutãm în continuare…

– 28, 35, 42, 49 sunt excluse

– verificãm 56:7=8

56-1=55:2 nu este divizibil

– 63, 70, 77, 84 sunt excluse

– continuãm cu 91:7=13

91-1=90:2=45

:3=30

:4=25

:5=18

:6=15

Rezultã cã bãtrânelul avea în coș exact 91 de ouã.

Bibliografie

Manual „Algoritmi și structuri de date: fundamente ale programãrii structurate” / Cezar Botezatu – București : Editura Universitarã, 2004