Ghid Practic pentru Teoria Informaticii la BAC

Algoritmi și Elementele de bază ale programării

Un algoritm este o succesiune clară și finită de operații realizabile care, pornind de la un set de date de intrare, conduc în timp finit la un set de date de ieșire. În programare, algoritmii sunt implementați prin intermediul limbajelor de programare precum Pascal sau C.

Conținuturile pentru Bacalaureat includ:

• Noțiunea și caracteristicile algoritmilor
• Date, variabile, expresii și operații
• Structuri de bază (liniară, alternativă și repetitivă)
• Descrierea algoritmilor prin pseudocod

Un limbaj de programare conține elemente esențiale precum:

• Vocabular, constante și identificatori
• Tipuri de date și operatori (aritmetici, logici, relaționali)
• Variabile și declararea acestora
• Structura programelor și instrucțiuni de control

Reține! Nu poți scrie un program eficient fără să înțelegi mai întâi structura și logica algoritmului care stă la baza lui.

Subprogramele predefinite, tipurile structurate de date (tablouri, șiruri de caractere, înregistrări) și fișierele text sunt componente esențiale ale unui limbaj de programare și vor fi testate la Bacalaureat.

Grafuri și metode avansate

Recursivitatea reprezintă o tehnică elegantă de programare unde o funcție sau procedură se apelează pe sine însăși. Această metodă este utilă pentru probleme care pot fi descompuse în subprobleme similare, dar mai simple.

Metoda backtracking este folosită pentru a genera toate soluțiile posibile ale unei probleme, fiind deosebit de utilă când trebuie să explorăm toate variantele. Poate fi implementată atât iterativ, cât și recursiv.

În matematică și informatică, elementele combinatoriale precum permutările, aranjamentele, combinările, produsul cartezian și submulțimile pot fi generate algoritmic.

Grafurile sunt structuri matematice formate din noduri și conexiuni:

Pentru grafurile neorientate trebuie să cunoști:

• Terminologie: nod/vârf, muchie, adiacență, grad
• Proprietăți: conexitate, graf complet, graf hamiltonian
• Reprezentare: matrice de adiacență, liste de adiacență

Pentru grafurile orientate sunt importante:

• Terminologie specifică: arc, grad intern și extern, drum, circuit
• Proprietăți particulare: tare conexitate
• Aceleași metode de reprezentare

Arborii sunt grafuri speciale fără cicluri, cu aplicații importante în informatică:

• Terminologie specifică: rădăcină, descendent, frunză
• Metode de reprezentare: matrici, liste de descendenți, vector de tați

Important! Structurile de date avansate precum grafurile sunt esențiale pentru rezolvarea eficientă a problemelor complexe și apar frecvent la Bacalaureat.

Noțiunea de algoritm și caracteristici

Termenul algoritm provine de la matematicianul persan Abu Jafar Mohammed ibn Musa al Khowarizmil (cca. 825 e.n.). Inițial, algoritmii erau considerați doar reguli pentru efectuarea calculelor aritmetice. Astăzi, gândirea algoritmică a devenit o modalitate fundamentală de abordare a problemelor în diverse domenii.

Un algoritm reprezintă o metodă de rezolvare a problemelor de un anumit tip. Rezolvarea unei probleme presupune obținerea unor date de ieșire plecând de la date de intrare:

Date de intrare → ALGORITM → Date de ieșire

Elaborarea unui algoritm are ca scop final implementarea sa într-un limbaj de programare. Pentru probleme complexe, înainte de programare, este recomandat să descriem pașii algoritmului în pseudocod.

Exemplu practic de algoritm: Presupunem că vrem să preparăm ochiuri, având ca ingrediente: 2 ouă, ulei, sare.

1. Se pune tigaia pe foc
2. Se toarnă ulei în tigaie
3. Așteptăm până se încinge uleiul
4. Spargem ouăle în tigaie
5. Așteptăm până se rumenesc
6. Dacă nu ținem regim, adăugăm sare

Reține! Un algoritm bun trebuie să fie clar, finit și realizabil, conducând în timp determinat la rezultatul dorit.

Date, variabile și expresii

Datele sunt entitățile cu care operează calculatorul. Orice algoritm lucrează cu:

• Date de intrare (primite din exterior)
• Date de ieșire (furnizate către exterior)
• Date de manevră (temporare, necesare calculelor)

În funcție de posibilitatea de a-și modifica valoarea, avem:

• Constante: date care nu își modifică valoarea (ex: 3.14, "text", 'A')
• Variabile: date care își pot schimba valoarea pe parcursul execuției

Numele unei variabile trebuie să înceapă cu o literă sau liniuță de subliniere și poate conține litere, cifre și liniuțe de subliniere. Variabilele trebuie declarate înainte de utilizare pentru a cunoaște tipul de valori permise.

Clasificarea datelor după valoare:

1. Date numerice (naturale, întregi sau reale)
2. Date alfabetice (caractere sau șiruri)
3. Date logice (adevărat/fals)

Expresiile sunt constituite din operanzi (constante, variabile sau alte expresii) conectați prin operatori. Principalele categorii de operatori sunt:

1. Operatori aritmetici:
   • Multiplicativi: * (înmulțire), / (împărțire), % (rest)
   • Aditivi: + (adunare), - (scădere)

Atenție! Operatorul de împărțire (/) are comportament diferit în funcție de tipul operanzilor: pentru operanzi întregi returnează câtul (împărțire întreagă), iar pentru operanzi reali returnează rezultatul exact al împărțirii.

Expresii și operatori

În programare, expresiile sunt evaluate prin înlocuirea variabilelor cu valorile lor și efectuarea operațiilor conform regulilor de precedență. Rezultatul depinde de tipul operanzilor și operațiilor.

Operatorii relaționali compară valori și returnează rezultate logice (adevărat/fals):

• == (egal), != (diferit)
• < (mai mic), <= (mai mic sau egal)

• (mai mare), >= (mai mare sau egal)

Operatorii logici se aplică valorilor logice:

• && (AND logic) - adevărat doar când ambii operanzi sunt adevărați
• || (OR logic) - adevărat când cel puțin un operand este adevărat
• ! (NOT logic) - inversează valoarea logică

Pentru eficiență, evaluarea expresiilor logice se face de obicei în mod "scurtcircuitat":

• Pentru a && b: dacă a este fals, b nu mai este evaluat
• Pentru a || b: dacă a este adevărat, b nu mai este evaluat

Precedența operatorilor stabilește ordinea de evaluare:

1. Operatori unari $!, -, etc.$
2. Operatori aritmetici multiplicativi (*, /, %)
3. Operatori aritmetici aditivi (+, -)
4. Operatori relaționali $<, >, ==, etc.$
5. Operatori logici (&&, ||)

Important! Utilizează paranteze rotunde pentru a impune ordinea dorită de evaluare și a face expresiile mai clare, evitând ambiguitățile.

Proiectarea modulară și structurarea algoritmilor

Programarea modulară este o abordare fundamentală care constă în descompunerea unei probleme complexe în subprobleme mai simple. Fiecare subproblemă este rezolvată printr-un modul de program relativ independent, care comunică cu celelalte prin intermediul parametrilor.

Avantajele programării modulare sunt multiple:

• Permite lucrul în echipă (module diferite pot fi implementate de programatori diferiți)
• Modificarea unui modul nu afectează celelalte module
• Fiecare modul poate fi testat și depanat independent

Un alt principiu esențial este structurarea datelor și a prelucrărilor. Conform teoremei lui Bohm-Jacopini, orice algoritm poate fi descris prin trei structuri fundamentale:

1. Structura liniară (secvențială)
2. Structura alternativă
3. Structura repetitivă

Reprezentarea algoritmilor în pseudocod oferă o metodă universală de descriere, independentă de limbajul de programare. Față de schemele logice (care devin stufoase pentru probleme complexe), pseudocodul are avantajul clarității și conciziei.

Un limbaj pseudocod constă din:

• Cuvinte cheie care identifică anumite acțiuni
• Reguli de sintaxă pentru folosirea acestor cuvinte
• Instrucțiuni care reprezintă acțiunile algoritmului

Sfat practic: Deși există diverse variante de pseudocod, învață una singură și folosește-o consecvent pentru a-ți dezvolta gândirea algoritmică înainte de a scrie cod în limbajul de programare.

Structuri fundamentale în pseudocod

În pseudocod, înainte de a scrie algoritmul propriu-zis, trebuie să declarăm datele și tipul lor:

Declararea datelor:

variabila tip;

Exemple:

x real;
c caracter;
i întreg;

Operații de bază:

1. Citirea datelor:

citește variabila₁, variabila₂, ..., variabilan;

2. Scrierea rezultatelor:

scrie expresie₁, expresie₂, ..., expresien;

3. Atribuirea valorilor:

variabila ← expresie;

Structura alternativă (dacă-atunci-altfel) permite executarea condiționată a instrucțiunilor:

dacă expresie atunci
    instrucțiune_1
[altfel
    instrucțiune_2]
sf. dacă

Funcționare:

• Se evaluează expresia
• Dacă rezultatul este adevărat, se execută instrucțiune_1
• Dacă rezultatul este fals și există ramura altfel, se execută instrucțiune_2

Observație importantă: Pentru a executa mai multe instrucțiuni pe oricare dintre ramuri, acestea trebuie grupate într-o instrucțiune compusă. Structura alternativă este esențială pentru luarea deciziilor în algoritmi.

Structuri repetitive în pseudocod

Structurile repetitive permit executarea repetată a unor instrucțiuni și se clasifică în:

1. Structuri repetitive cu număr necunoscut de pași:

a) Instrucțiunea repetitivă condiționată anterior:

cât timp expresie execută
    instrucțiune
sf. cât timp

Funcționare:

• Mai întâi se evaluează expresia
• Dacă este adevărată, se execută instrucțiunea și se revine la evaluarea expresiei
• Dacă este falsă, se iese din structură

Important: Dacă expresia este falsă de la început, instrucțiunea nu se execută niciodată.

b) Instrucțiunea repetitivă condiționată posterior:

Varianta 1:

execută
    instrucțiune
cât timp expresie;

Varianta 2:

repetă
    instrucțiune
până când expresie;

Funcționare:

• Se execută instrucțiunea
• Se evaluează expresia
• În funcție de rezultat (și de tipul structurii), se continuă sau se iese

Important: În aceste structuri, instrucțiunea se execută cel puțin o dată, deoarece condiția este verificată după execuție.

Atenție! În structurile repetitive, trebuie să ne asigurăm că instrucțiunea modifică variabilele din condiție astfel încât să evităm buclele infinite. Diferența între "cât timp" și "până când" este că prima continuă cât timp condiția este adevărată, iar a doua până când condiția devine adevărată.

Structuri repetitive și echivalența lor

Instrucțiunile repetitive condiţionate posterior:

execută
    instrucțiune
cât timp expresie;

și

repetă
    instrucțiune
până când expresie;

Diferențele principale:

• În execută...cât timp, instrucțiunea se repetă cât timp expresia este adevărată
• În repetă...până când, instrucțiunea se repetă cât timp expresia este falsă (și se oprește când devine adevărată)

Pentru a face echivalente cele două tipuri de instrucțiuni:

• execută...cât timp expresie este echivalent cu repetă...până când !(expresie)
• Adică, negăm condiția pentru a transforma una în cealaltă

Structură repetitivă cu număr cunoscut de pași:

Pentru contor←expresie₁, expresie₂, [pas] execută
    Instrucțiune
Sf. pentru

Funcționare:

1. Contorul primește valoarea inițială (expresie₁)
2. Se verifică dacă valoarea contorului depășește limita (expresie₂)
3. Dacă nu, se execută instrucțiunea și se modifică contorul cu valoarea pas
4. Se repetă pașii 2-3 până când condiția nu mai este îndeplinită

Sfat practic: Structurile repetitive pot fi simulate unele prin altele. De exemplu, pentru poate fi implementat folosind cât timp, dar este mai elegant și mai clar să folosești structura potrivită pentru fiecare situație.

Structura repetitivă cu număr cunoscut de pași

Cea mai intuitivă structură repetitivă este cea cu număr cunoscut de pași, utilizată când știm exact de câte ori trebuie să repetăm o acțiune:

Pentru contor←expresie₁, expresie₂, [pas] execută
    Instrucțiune
Sf. pentru

Pașii de execuție:

1. Se evaluează expresie₁ și se atribuie valoarea variabilei contor
2. Se evaluează expresie₂
3. Se verifică dacă valoarea contorului a depășit limita (expresie₂)
   • Dacă a depășit-o, se iese din structura repetitivă
   • Dacă nu, se execută instrucțiunea, se modifică contorul și se revine la pasul 2

Observații importante:

• Dacă parametrul pas lipsește, se consideră implicit valoarea 1
• Dacă pasul este pozitiv, bucla se execută cât timp contor ≤ expresie₂
• Dacă pasul este negativ, bucla se execută cât timp contor ≥ expresie₂

Această structură repetitivă poate fi simulată folosind celelalte două tipuri de structuri repetitive, dar utilizarea ei directă face algoritmii mai clari și mai ușor de înțeles.

Concluzie: Cele trei structuri de bază (liniară, alternativă și repetitivă) sunt suficiente pentru a exprima orice algoritm. Alegerea structurii potrivite face algoritmul mai elegant, mai eficient și mai ușor de înțeles.