Algoritmi și programare – noțiuni introductive

Introducerea conceptelor de algoritm, date și instrucțiuni ca bază a gândirii computaționale.

Ce este un algoritm și ce proprietăți are

Un algoritm este o succesiune finită și ordonată de pași care rezolvă o problemă: pornește de la niște date cunoscute și ajunge, după un număr limitat de operații, la un rezultat. Algoritmi există și în afara informaticii: o rețetă de clătite, instrucțiunile de asamblare a unei piese de mobilier, drumul explicat unui turist — toate sunt liste de pași care duc la un rezultat.

Proprietățile algoritmului — se cer cu denumirile exacte:

• finitudinea: algoritmul se termină după un număr finit de pași; o listă de instrucțiuni care nu se oprește niciodată nu este algoritm;
• claritatea (precizia): fiecare pas este descris exact, fără ambiguitate; „adaugă niște făină, cât crezi” nu este un pas clar;
• generalitatea: algoritmul rezolvă toate problemele dintr-o clasă, nu doar un caz; algoritmul de adunare funcționează pentru orice pereche de numere, nu doar pentru 2 + 3;
• eficiența (realizabilitatea): pașii pot fi efectuați concret și duc la rezultat într-un timp rezonabil.

Capcana teoretică preferată a subiectelor: o listă de pași care se repetă la nesfârșit („mergi înainte; reia de la primul pas”) încalcă finitudinea, iar un enunț vag încalcă claritatea. Când o întrebare descrie un defect al unui pseudo-algoritm, caută mai întâi care dintre aceste proprietăți este încălcată.

Date de intrare, date de ieșire și etapele rezolvării

Orice algoritm lucrează cu date:

• datele de intrare sunt valorile cunoscute la început, pe care algoritmul le primește (le citește); pentru calculul mediei a două note, intrarea este perechea de note;
• datele de ieșire sunt rezultatele pe care algoritmul le produce (le afișează); în exemplul nostru, media;
• datele intermediare (de manevră) apar pe parcurs, ca ajutor la calcul, dar nu se comunică utilizatorului — de exemplu suma notelor, calculată înainte de împărțirea la 2.

Rezolvarea unei probleme urmează mereu același drum: citim datele de intrare, le prelucrăm după pașii algoritmului, apoi afișăm datele de ieșire. Schema „citire → prelucrare → afișare” este scheletul oricărui algoritm de la această clasă.

La test se cere des identificarea lor dintr-un enunț: „Se citesc două numere naturale și se afișează suma lor” — intrarea: cele două numere; ieșirea: suma. Greșeala tipică este includerea rezultatului printre datele de intrare: suma NU se citește, ea se calculează. Verbul din enunț este indiciul: ce „se citește / se dă / se cunoaște” este intrare; ce „se afișează / se cere / se determină” este ieșire.

Variabile și tipuri de date

O variabilă este o zonă de memorie cu un nume, în care se păstrează o valoare ce se poate modifica pe parcursul algoritmului. Imagineaz-o ca pe o cutiuță etichetată: eticheta este numele variabilei (a, suma, nota), iar înăuntru stă valoarea curentă. Regula fundamentală a cutiuței: poate conține o singură valoare la un moment dat — când pui o valoare nouă, cea veche se pierde definitiv.

Prin contrast, o constantă este o valoare care nu se schimbă pe parcursul algoritmului (de exemplu numărul 2 din formula mediei).

Fiecare variabilă are un tip de date, care spune ce fel de valori poate păstra:

• întreg – numere fără parte zecimală: -3, 0, 17;
• real – numere cu zecimale: 3,14; -0,5;
• caracter/șir de caractere – litere, cuvinte, texte: A, „Maria”;
• logic – doar două valori: adevărat sau fals.

Tipul se alege după natura datelor: numărul de elevi dintr-o clasă este întreg (nu există 25,5 elevi), media notelor este reală (poate fi 8,75), iar răspunsul la „este numărul par?” este logic. Întrebarea-capcană tipică cere exact această potrivire: temperatura măsurată cu zecimale nu poate fi păstrată corect într-o variabilă de tip întreg — partea zecimală s-ar pierde.

Instrucțiunea de atribuire

Atribuirea este operația prin care o variabilă primește o valoare. În pseudocod se notează cu o săgeată: a ← 5 se citește „a primește valoarea 5”. În dreapta săgeții poate sta o valoare, altă variabilă sau o expresie de calcul:

• a ← 5 (a primește 5);
• b ← a + 2 (se calculează a + 2, adică 7, și rezultatul se pune în b);
• a ← a + 1 (se ia valoarea curentă a lui a, se adună 1, iar rezultatul revine în a; dacă a era 5, acum a este 6).

Ultima formă îi încurcă pe mulți: a ← a + 1 nu este o ecuație, ci o comandă — „mărește-l pe a cu 1”. În matematică, egalitatea a = a + 1 ar fi imposibilă; în informatică, atribuirea se execută întâi dreapta, apoi stânga: se calculează expresia din dreapta cu valorile actuale, apoi rezultatul se depozitează în variabila din stânga.

Două reguli care se punctează:

• atribuirea suprascrie: după a ← 3 urmat de a ← 8, variabila a conține 8; valoarea 3 a dispărut;
• în stânga săgeții stă obligatoriu o variabilă, niciodată un număr sau o expresie: 5 ← a sau a + 1 ← 7 sunt scrieri fără sens.

Exemplul clasic de test — interschimbarea valorilor a două variabile a și b — cere o a treia variabilă ajutătoare: aux ← a; a ← b; b ← aux. Varianta „directă” a ← b; b ← a NU funcționează: după primul pas, vechea valoare a lui a e deja pierdută, iar ambele variabile ajung să conțină aceeași valoare.

Pseudocod, schemă logică și urmărirea execuției

Un algoritm poate fi descris în mai multe feluri. La școală folosim două reprezentări standard:

• Pseudocodul – descriere în cuvinte, apropiată de limba română, cu instrucțiuni consacrate: citește a, b (preia datele de intrare), scrie s (afișează rezultatele), săgeata ← pentru atribuire;
• Schema logică – desen cu blocuri legate prin săgeți, în care forma blocului arată tipul operației: oval pentru Start și Stop, paralelogram pentru citire și scriere, dreptunghi pentru atribuiri și calcule, romb pentru decizii (întrebări cu răspuns da/nu). Asocierea formă–operație este întrebare sigură de test: calculul stă în dreptunghi, decizia în romb, citirea/scrierea în paralelogram.

Urmărirea execuției (testarea pe hârtie) înseamnă să joci rolul calculatorului: execuți pașii în ordine și ții evidența valorilor fiecărei variabile într-un tabel. Exemplu: citește x (se citește 4); y ← x * 2 (y devine 8); x ← x + y (x devine 4 + 8 = 12); scrie x (se afișează 12).

Două greșeli de urmărire care apar mereu: folosirea valorii vechi a unei variabile după ce ea a fost modificată (după x ← x + y, vechiul 4 nu mai există) și executarea pașilor în altă ordine decât cea scrisă. Calculatorul nu „vede” tot algoritmul deodată — execută strict pas cu pas, de sus în jos, iar la urmărire trebuie să faci exact la fel.

Test — 6 întrebări ca la examen