Recapitulare Bac Informatica

download Recapitulare Bac Informatica

of 66

  • date post

    28-Dec-2015
  • Category

    Documents

  • view

    464
  • download

    26

Embed Size (px)

description

recapitulare bac informatica

Transcript of Recapitulare Bac Informatica

1

Recapitulare pentru bacalaureat31. ALGORITMI

31.1. Noiunea de algoritm. Caracteristici:

31.2. Date, variabile, expresii, operaii:

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

81.4. Descrierea algoritmilor (programe pseudocod):

122. Elementele de baz ale unui limbaj de programare (Pascal)

122.1 Vocabularul limbajului

122.2 Constante. Identificatori

132.3 Noiunea de tip de dat. Operatori aritmetici, logici, relaionali

132.4 Definirea tipurilor de date

132.5 Variabile. Declararea variabilelor

142.6 Definirea constantelor

142.7 Structura programelor. Comentarii

142.8 Expresii. Instruciunea de atribuire

142.9 Citirea/scrierea datelor

152.10 Structuri de control (instruciunea compus, structuri alternative i repetitive)

153.Subprograme

153.1. Subprograme. Mecanisme de transfer prin intermediul parametrilor

173.2. Proceduri si functii predefinite

184. Tipuri structurate de date

184.1 Tipul tablou

234.2. Tipul sir de caractere

254.3. Tipul nregistrare (articol)

265. Fisiere text

265.1. Fisiere text. Tipuri de acces

265.2. Proceduri si functii predefinite pentru fisiere text

26Sintaxa de declarare:

27Efect

27Observatie importanta

27Probleme:

286. Algoritmi elementari

296.1. Probleme care opereaz asupra cifrelor unui numr

306.2. Divizibilitate. Numere prime. Algoritmul lui Euclid

336.3. Sirul lui Fibonacci. Calculul unor sume cu termenul general dat

356.4. Determinare minim/maxim

366.5. Metode de ordonare (metoda bulelor, inseriei, selectiei, numrrii)

39Metoda de sortare prin numrare

406.6. Interclasare

416.7. Metode de cutare (secvential, binar)

436.8 Analiza complexitii (considernd criteriile de eficien durata de executare i spaiu de memorie utilizat)

437. Subprograme definite de utilizator

437.1 Proceduri i funcii

467.2 Proiectarea modular a rezolvrii unei probleme

478. Recursivitate

488.1 Prezentare general

488.2 Funcii i proceduri recursive

499. Metoda backtracking

499.1. Prezentare general

529.2. Probleme de generare. Oportunitatea utilizrii metodei backtracking

5510. Generarea elementelor combinatoriale

5510.1 Permutari, aranjamente, combinari

5910.2 Produsul cartezian .Submultimi.

6011.Grafuri

6011.1Grafuri neorientate

6211.2Grafuri orientate

6511.3Arbori

1. ALGORITMI1.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

- Logice

2. 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 True

Observatie: 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 X

False True

True 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 q1.3. Structuri de baz (liniar, alternativ si repetitiv):

1.1. Structuri liniare

1.1.1. Citirea datelor

CitireSintaxa: Citeste(v1,v2,,vn);

Unde v1, vn= variabile

Efect: 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 3

1.1.2. Scrierea expresiilor

Sintaxa: Scrie(e1,e2,,en);

Unde e1,,en=expresii

Efect: 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 2

OBS 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. Atribuirea

Sintaxa:V:= expresie

Se citeste: v ia valoarea expresie

Efect: Se evalueaza expresia v si rezultatul ii este dat (in memorie) lui v.Exemple:A:=a+b

B:=b+2*a

=> Memorie:. 1.2. Structuri alternative:

1.2.1. Instructiunea IF

daca 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