Testarea algoritmilor

Testarea înseamnă să alegi intrări, să stabilești rezultatul așteptat și să compari cu rezultatul algoritmului. Un exemplu reușit arată doar că algoritmul funcționează pentru acel exemplu. Pentru o regulă ce numără valorile pozitive, merită încercate un șir fără valori pozitive, unul cu toate pozitive și unul cu zerouri: zero nu este pozitiv. Înainte de rulare, calculează așteptarea prin raționament independent.

Pentru datele $[-2,0,3,5]$, valorile pozitive sunt 3 și 5, deci răspunsul așteptat este 2. Dacă programul afișează 3, tabelul cu valoarea contorului după fiecare element poate arăta că a fost numărat și zero. Depanarea caută pasul la care rezultatul începe să difere de așteptare.

Datele de test sunt valorile alese pentru rulare, iar rezultatul așteptat se stabilește înaintea execuției, prin raționament independent de program. Un test care reușește arată doar că algoritmul funcționează pentru acea intrare; testele nu dovedesc corectitudinea, dar pot dezvălui erori. Datele se aleg din clase care provoacă comportamente diferite: un caz obișnuit (numere pozitive și negative amestecate), cazuri de frontieră (un singur element, valoarea chiar pe prag, șirul de lungime maximă) și cazuri speciale (nicio valoare care respectă condiția, toate valorile egale, zerouri). Dacă enunțul permite un șir vid, el se testează separat.

Depanarea începe când rezultatul diferă de cel așteptat. Se urmărește execuția cu un tabel al valorilor variabilelor și se caută prima stare care diferă de cea gândită; instrucțiunea care a produs-o conține eroarea. Modificarea codului la întâmplare nu este depanare.

Corectitudinea unui ciclu se argumentează cu un invariant: o afirmație adevărată înainte de ciclu, păstrată de fiecare execuție a corpului, care la ieșire dă rezultatul. Un algoritm este corect dacă se termină și dă rezultatul cerut pentru toate intrările admise.

Exemplul 1 — maximul unui șir. Pentru lista [-5, -2] rezultatul așteptat este $-2$. Varianta greșită cu maxim = 0 afișează 0, valoare care nici nu apare în listă. Varianta corectă pornește de la primul element:

a = [-5, -2]
maxim = a[0]
for i in range(1, len(a)):
    if a[i] > maxim:
        maxim = a[i]
print(maxim)

Inițial maxim = -5; la pasul următor $-2>-5$, deci maxim = -2, iar ieșirea este -2. Pe [4, 1] condiția rămâne falsă și răspunsul este 4. Pe un singur element bucla nu rulează și chiar acel element este răspunsul. Invariantul este: după fiecare pas, maxim este cel mai mare dintre elementele parcurse. Este adevărat pentru primul element, comparația cu următorul îl păstrează, iar la final au fost parcurse toate. Algoritmul presupune o listă nevidă; cazul vid trebuie respins sau tratat separat. Timpul este proporțional cu $n$, iar memoria auxiliară este constantă.

Exemplul 2 — găsirea unei erori. Funcția de mai jos trebuie să returneze suma elementelor pare ale unei liste, dar are o greșeală.

def suma_pare(a):
    s = 0
    for i in range(1, len(a)):
        if a[i] % 2 == 0:
            s += a[i]
    return s

print(suma_pare([2, 4, 6]), suma_pare([3, 5]), suma_pare([8]))

Testele așteptate sunt 12, 0 și 8. Funcția afișează 10 0 0. Primul test dă 10 în loc de 12: urmărind execuția, indicele i pornește de la 1, deci elementul de pe poziția 0, adică 2, nu este niciodată verificat. Eroarea este în limita ciclului, nu în testul de paritate; testul cu un singur element, [8], arată același lucru, pentru că ciclul nu se execută. Corectura este range(len(a)) și, cu ea, rezultatele devin 12 0 8. Testul [3, 5] a trecut și înainte de corectură: un test care reușește nu dovedește absența erorii.

Ce probe merită scrise. Pentru fiecare algoritm alegi cel puțin patru intrări: una obișnuită, una de frontieră inferioară, una de frontieră superioară și una în care răspunsul este „nicio valoare nu respectă condiția”. Notezi răspunsul așteptat în dreptul fiecărei intrări înainte de rulare; dacă îl notezi după, riști să-l ajustezi după ce vezi ieșirea programului.

Greșeli frecvente

• Greșit: un singur exemplu corect dovedește algoritmul.
  Corect: testele pot găsi erori, iar corectitudinea generală cere și argumentarea metodei.
• Greșit: alegerea numai a datelor ușoare este suficientă.
  Corect: include valori de frontieră și cazuri cu rezultat zero.
• Greșit: depanarea înseamnă să modifici codul la întâmplare.
  Corect: găsește prima stare care diferă de rezultatul așteptat.

Înainte și după