1

Recapitulare pentru bacalaureat

1. ALGORITMI31.1. Noiunea de algoritm. Caracteristici:31.2. Date, variabile, expresii, operaii:31.3. Structuri de baz (liniar, alternativ si repetitiv):51.4. Descrierea algoritmilor (programe pseudocod):82. Elementele de baz ale unui limbaj de programare (Pascal)122.1 Vocabularul limbajului122.2 Constante. Identificatori122.3 Noiunea de tip de dat. Operatori aritmetici, logici, relaionali132.4 Definirea tipurilor de date132.5 Variabile. Declararea variabilelor132.6 Definirea constantelor142.7 Structura programelor. Comentarii142.8 Expresii. Instruciunea de atribuire142.9 Citirea/scrierea datelor142.10 Structuri de control (instruciunea compus, structuri alternative i repetitive)153.Subprograme153.1. Subprograme. Mecanisme de transfer prin intermediul parametrilor153.2. Proceduri si functii predefinite174. Tipuri structurate de date184.1 Tipul tablou184.2. Tipul sir de caractere234.3. Tipul nregistrare (articol)255. Fisiere text265.1. Fisiere text. Tipuri de acces265.2. Proceduri si functii predefinite pentru fisiere text26Sintaxa de declarare:26Efect27Observatie importanta27Probleme:276. Algoritmi elementari286.1. Probleme care opereaz asupra cifrelor unui numr296.2. Divizibilitate. Numere prime. Algoritmul lui Euclid306.3. Sirul lui Fibonacci. Calculul unor sume cu termenul general dat336.4. Determinare minim/maxim356.5. Metode de ordonare (metoda bulelor, inseriei, selectiei, numrrii)36Metoda de sortare prin numrare396.6. Interclasare406.7. Metode de cutare (secvential, binar)416.8 Analiza complexitii (considernd criteriile de eficien durata de executare i spaiu de memorie utilizat)437. Subprograme definite de utilizator437.1 Proceduri i funcii437.2 Proiectarea modular a rezolvrii unei probleme468. Recursivitate478.1 Prezentare general488.2 Funcii i proceduri recursive489. Metoda backtracking499.1. Prezentare general499.2. Probleme de generare. Oportunitatea utilizrii metodei backtracking5210. Generarea elementelor combinatoriale5510.1 Permutari, aranjamente, combinari5510.2 Produsul cartezian .Submultimi.5911.Grafuri6011.1Grafuri neorientate6011.2Grafuri orientate6211.3Arbori65

1. ALGORITMI

1.1. Noiunea de algoritm. Caracteristici Prin algoritm se nelege o mulime ordonat i finit de reguli ce descriu o succesiune finit de operaii necesare rezolvrii unei probleme.Paii algoritmului trebuie s-i fie indicai calculatorului sub forma unor comenzi numite instruciuni. Mulimea tuturor instruciunilor ce descriu algoritmul de rezolvare a unei probleme formeaz programul. Pentru a dialoga cu un calculator, este necesar cunoaterea unui limbaj comun omului i calculatorului. Atenie! Care sunt deosebirile dintre un calculator de buzunar i unul programabil?Exemple de algoritmi:-calcularea ariei unui triunghi(se cunosc a,b,c);-calcularea nlimilor unui triunghi (se cunosc a,b,c);-calcularea mediei unui elev;-rezolvarea ecuaiei de gradul I etc.Caracteristici ale algoritmilor:-generalitatea = proprietatea de a fi valabil pentru o clas ( un gen) de probleme; (ex nu aduna 3+4 ci a+b)-finitudinea = proprietatea de a permite obinerea soluiei problemei dup parcurgerea unui numr finit de operaii (contraexemplu: ciclu infinit ex repeat write(*);until 3=4;).-unicitatea= proprietatea conform creia ori de cte ori se pornete de la acelai set de valori ale variabilelor de intrare se obin aceleai soluii.Atenie!Fiecare proprietate trebuie exemplificat prin cte un exemplu i un contraexemplu.Atenie! Dac un algoritm are aceste 3 proprieti nu nseamn c el este i corect. 1.2. Date, variabile, expresii, operaii:1. Date :- Numerice- Alfanumerice- Logice2. Operatii: - aritmetice- relationale (,,=)- logice (booleene true, false)3. Expresii - Aritmetice- relationale- logice (si, sau, not) Tabela de adevr a operatorului si: X Y X si Y False False False False True False True False False True True TrueObservatie: si are valoarea true doar daca ambii operanzi sunt true si falsa daca unul dintre ei este false. Tabela de adevar a operatorului sau: X Y X sau Y False False False False True True True False True True True True Observatie: sau are valoarea false doar daca ambii operanzi sunt falsi si true daca unul dintre ei este true.

Tabela de adevar a operatorului not X not XFalse TrueTrue False

Operatorul XOR (sau exclusiv):X Y X xor Y False False False False True True True False True True True FalseAplicatii:Legile lui De MorganNot(p sau q)= not p si not q Not (p si q)= not p sau not q

1.3. Structuri de baz (liniar, alternativ si repetitiv):

1.1. Structuri liniare1.1.1. Citirea datelorCitireSintaxa: Citeste(v1,v2,,vn);Unde v1, vn= variabileEfect: calculatorul asteapta introducerea de la tastatura a valorii variabilelor v1,, vn si da aceasta valoare (in memorie) variabilelor precizate

Exemplu: Citeste(a,b) => Memorie | Ecran a 2 2 b 3 31.1.2. Scrierea expresiilor

Sintaxa: Scrie(e1,e2,,en); Unde e1,,en=expresiiEfect: Se evalueaza(calculeaza) valoarea expresiilor din lista si rezultatul se afiseaza pe ecran.Exemplu: Scrie(a,b); => Ecran: 23 scrie( este , a); =>Ecran: A este 2OBS importanta: in sintaxa lui citestein lista nu pot sa apara expresii. De ce? Atenie la formatul de afiare(a:2, a:n1:n2)!1.1.3. AtribuireaSintaxa:V:= expresieSe citeste: v ia valoarea expresieEfect: Se evalueaza expresia v si rezultatul ii este dat (in memorie) lui v.Exemple:A:=a+bB:=b+2*a=> Memorie:. 1.2. Structuri alternative:1.2.1. Instructiunea IFdaca c atunci X altfel Yunde c=conditie (expresie logica) , X,Y= cate o singura instructiune;Efect - se evalueaza c si daca este true se executa X; daca este false se executa Y;

- Probleme:* Intr-o sala de clasa sunt mese si scaune. Se cunoaste numarul lor. Care dintre acestea sunt mai multe? Cunoscand si numarul elevilor clasei si faptul ca la o masa pot sta 3 persoane afisati daca:a) sunt destule mese;b) sunt destule scaune.* Se cunosc 5 numere