Noțiunea de algoritm. Caracteristici

Termenul provine din forma latinizată a numelui matematicianului persan al-Khwārizmī, autorul unui tratat de calcul cu cifre arabe scris în secolul al IX-lea.

Orice prelucrare executată de calculator pornește de la un algoritm. Înainte de a fi scris ca program, algoritmul se stabilește și se verifică pe hârtie.

Datele prelucrate

Un algoritm prelucrează date. După rolul lor, datele se împart în trei categorii.

Datele de manevră se mai numesc date intermediare sau de lucru. Contoarele, sumele parțiale și variabilele folosite la interschimbarea a două valori sunt date de manevră.

Un algoritm poate să nu aibă date de intrare. Algoritmul care afișează primele o sută de numere naturale prime nu primește nicio valoare din exterior. Datele de ieșire există însă întotdeauna: un algoritm care nu produce niciun rezultat nu rezolvă nicio problemă.

Proprietățile algoritmului

Proprietățile algoritmului sunt:

• claritatea;
• generalitatea;
• finitudinea;
• succesiunea determinată a pașilor;
• unicitatea;
• corectitudinea;
• eficiența.

O succesiune de operații este algoritm numai dacă îndeplinește primele șase proprietăți. Eficiența deosebește algoritmii corecți între ei: dintre doi algoritmi pentru aceeași problemă se alege cel mai eficient.

Generalitatea se mai numește universalitate, iar unicitatea se mai numește determinism.

Claritatea

Executantul nu are de ales și nu are de completat nimic.

Exemplu. Se citește un număr natural n. Se cere ultima lui cifră.

citește n
c ← n % 10
scrie c

Pasul c ← n % 10 este clar: împărțirea cu rest este o operație definită, iar restul împărțirii la 10 este chiar ultima cifră. Pentru n = 5372 se obține 2. Oricine ar executa algoritmul, cu aceeași valoare de intrare, obține tot 2.

Formulare care încalcă proprietatea. Se citește un număr natural n. Se cere suma S = 1 + 2 + … + n. Scrisă astfel, cu puncte de suspensie, cerința nu este un pas executabil: punctele nu corespund niciunei operații. Formularea clară cere o structură repetitivă în care se adună pe rând valorile de la 1 la n.

Tot neclară este și cerința „se ordonează elementele într-un mod convenabil”: nu se precizează nici criteriul de ordonare, nici procedeul prin care se face.

Generalitatea

Valorile concrete se primesc la intrare; algoritmul nu le conține.

Exemplu. Se citesc două numere naturale a și b. Se cere suma lor.

citește a, b
s ← a + b
scrie s

Algoritmul se aplică oricărei perechi de numere naturale: pentru 5 și 3 se obține 8, pentru 120 și 45 se obține 165. Datele de intrare se schimbă, algoritmul rămâne același.

Formulare care încalcă proprietatea. „Se adună 5 cu 3 și se afișează rezultatul 8.” Descrierea rezolvă un singur caz. Ea nu spune nimic despre cum se adună alte două numere, deci este un calcul, nu un algoritm.

Finitudinea

Exemplu. Se citește un număr natural n. Se cere numărul cifrelor sale.

citește n
nr ← 0
cât timp n ≠ 0 execută
    nr ← nr + 1
    n ← [n / 10]
sfcât timp
scrie nr

La fiecare pas, împărțirea întreagă la 10 elimină ultima cifră, deci n are de fiecare dată cu o cifră mai puțin. Pentru n = 5372, valorile lui n sunt pe rând 5372, 537, 53, 5, 0, iar structura repetitivă se execută de patru ori. Oricât de mare ar fi numărul citit, el are un număr finit de cifre, deci algoritmul se încheie.

Formulare care încalcă proprietatea. „Se afișează toate numerele naturale impare.” Șirul numerelor impare nu are ultim termen, deci prelucrarea nu se încheie niciodată. Formularea corectă mărginește șirul: „se afișează numerele naturale impare mai mici decât 100”.

Aceeași lipsă apare și acolo unde condiția de oprire nu se atinge. În prelucrarea „cât timp n ≠ 1 execută n ← n − 2”, pentru n = 10 se obțin pe rând 8, 6, 4, 2, 0, apoi −2, −4 și așa mai departe: valoarea 1 nu se atinge niciodată, fiindcă din numere pare se obțin tot numere pare.

Succesiunea determinată a pașilor

Când ordinea trebuie schimbată, pasul care urmează se precizează explicit.

Exemplu. Variabila a conține valoarea 7, iar variabila b valoarea 4. Se cere schimbarea valorilor între ele.

aux ← a
a ← b
b ← aux

Valoarea lui a se păstrează în variabila de manevră aux înainte de a fi înlocuită. Ordinea celor trei atribuiri face parte din algoritm.

Formulare care încalcă proprietatea. „Se efectuează atribuirile a ← b, aux ← a și b ← aux, în orice ordine.” Executate în ordinea scrisă, ele dau alt rezultat: după a ← b, variabila a devine 4, iar valoarea 7 se pierde. La sfârșit, amândouă variabilele conțin 4.

Unicitatea

Exemplu. Se citește un număr natural n. Se cere suma cifrelor sale.

citește n
s ← 0
cât timp n ≠ 0 execută
    s ← s + n % 10
    n ← [n / 10]
sfcât timp
scrie s

Pentru n = 5372 se adună pe rând 2, 7, 3 și 5, iar rezultatul este 17. Niciun pas nu lasă loc de alegere, deci rezultatul este 17 la orice execuție și pentru oricine.

Formulare care încalcă proprietatea. „Se alege un divizor al numărului n și se afișează câtul.” Pentru n = 12, un executant poate alege divizorul 3 și afișa 4, iar altul poate alege divizorul 6 și afișa 2. Din aceleași date de intrare se obțin rezultate diferite.

Corectitudinea

Exemplu. Se citesc două numere naturale. Se cere media lor aritmetică.

citește a, b
m ← (a + b) / 2
scrie m

Împărțirea este cea reală, iar variabila m este de tip real. Pentru 3 și 4 se obține 3,5, adică exact media aritmetică a celor două numere.

Formulare care încalcă proprietatea. Aceeași descriere, dar cu împărțire întreagă: m ← [(a + b) / 2]. Pentru 3 și 4 se obține 3. Algoritmul se termină, este clar și este general, dar rezultatul nu este cel cerut de problemă.

Eficiența

Dintre doi algoritmi corecți pentru aceeași problemă se alege cel care efectuează mai puține operații.

Exemplu. Se citește un număr natural n mai mare decât 1. Se cere să se stabilească dacă este prim.

citește n
d ← 2
prim ← adevărat
cât timp d * d ≤ n și prim = adevărat execută
    dacă n % d = 0 atunci
        prim ← fals
    altfel
        d ← d + 1
    sfdacă
sfcât timp
scrie prim

Divizorii se caută numai până la partea întreagă a rădăcinii pătrate din n. Pentru n = 1 000 003, rădăcina pătrată este aproximativ 1000, deci se efectuează în jur de o mie de împărțiri.

Formulare care încalcă proprietatea. Aceeași verificare, dar cu divizori căutați de la 2 până la n − 1. Pentru n = 1 000 003 se efectuează un milion de împărțiri în loc de o mie, adică de o mie de ori mai multe, pentru același rezultat.

Algoritm, program, limbaj de programare

Același algoritm poate fi scris ca program în C++, în Pascal sau în Python. Programele diferă între ele, metoda rămâne aceeași. Două programe scrise în același limbaj pot implementa algoritmi diferiți pentru aceeași problemă.

Din această deosebire decurge o regulă de lucru la clasă: algoritmul se stabilește înainte de deschiderea mediului de programare.

Exemplu

Problema. Se citește un număr natural n. Se cere suma cifrelor sale.

Metoda. Ultima cifră a unui număr este restul împărțirii lui la 10. Prin împărțirea întreagă la 10, ultima cifră se elimină. Cele două operații se repetă până când numărul devine 0.

Algoritmul în pseudocod.

citește n
s ← 0
cât timp n ≠ 0 execută
    s ← s + n % 10
    n ← [n / 10]
sfcât timp
scrie s

Programul.

#include <iostream>
using namespace std;

int main() {
    unsigned n, s = 0;
    cin >> n;

    while (n != 0) {
        s = s + n % 10;   // se adaugă ultima cifră
        n = n / 10;       // se elimină ultima cifră
    }

    cout << s;
    return 0;
}

Verificarea proprietăților.

Flashcarduri

Citește întrebarea și formulează răspunsul. Apoi întoarce flashcardul și verifică.

Flashcardul 1 din 12

Știu: 0 De repetat: 0

Întrebare

Ce este algoritmul?

Apasă pe flashcard pentru a vedea răspunsul

Răspuns

Ce este algoritmul?

O succesiune finită de operații, executate într-o ordine bine precizată, prin care se rezolvă o problemă.

← Precedentul Întoarce flashcardul Următorul →

Amestecă flashcardurile Începe din nou

Din tastatură: Spațiu întoarce flashcardul, ← și → trec la flashcardul precedent sau următor.

Hartă mentală

Pentru recapitulare, ascunde ideile, spune ce cuprinde fiecare ramură, apoi apasă pe titlul ei și verifică.

Ascunde ideile Arată ideile

▾ Algoritm, program, limbaj

• algoritmul: metoda de rezolvare
• programul: algoritmul scris într-un limbaj de programare
• limbajul: mulțimea regulilor de scriere

Citește în lecție →

▾ Proprietățile algoritmului

• claritatea
• generalitatea
• finitudinea
• succesiunea determinată a pașilor
• unicitatea
• corectitudinea
• eficiența

Citește în lecție →

Algoritmul

▾ Definiția

• succesiune finită de operații
• ordine bine precizată
• rezolvă o problemă

▾ Datele prelucrate

• date de intrare
• date de ieșire
• date de manevră

Citește în lecție →

Test grilă

Bifează un răspuns la fiecare întrebare, apoi apasă „Vezi nota”. Răspunsurile corecte se arată după corectare.

1. 1 Algoritmul este

   a un program scris în limbajul C++ b o succesiune finită de operații, executate într-o ordine bine precizată, prin care se rezolvă o problemă c mulțimea regulilor după care se scriu programele d o succesiune de operații care se pot executa în orice ordine

2. 2 Într-un algoritm care interschimbă valorile variabilelor a și b, variabila aux este

   a dată de intrare b dată de ieșire c dată de manevră d constantă

3. 3 Formularea „Se afișează toate numerele naturale impare” încalcă proprietatea de

   a claritate b finitudine c generalitate d eficiență

4. 4 Formularea „Se adună 5 cu 3 și se afișează rezultatul 8” încalcă proprietatea de

   a generalitate b unicitate c finitudine d corectitudine

5. 5 Formularea „Se alege un divizor al numărului n și se afișează câtul” încalcă proprietatea de

   a finitudine b eficiență c unicitate d generalitate

6. 6 Media aritmetică a două numere calculată cu împărțire întreagă, m ← [(a + b) / 2], încalcă proprietatea de

   a claritate b finitudine c corectitudine d succesiune determinată a pașilor

7. 7 Verificarea primalității lui n cu divizori de la 2 până la n − 1

   a nu este algoritm, pentru că durează prea mult b este algoritm corect, dar mai puțin eficient decât verificarea până la rădăcina pătrată a lui n c nu este algoritm, pentru că nu este finită d dă un rezultat greșit pentru numerele mari

8. 8 Pentru n = 5372, algoritmul care numără cifrele lui n execută structura repetitivă de

   a 3 ori b 4 ori c 5 ori d 5372 de ori

Vezi nota