Verificarea unei proprietăți

O proprietate este o regulă care poate fi adevărată sau falsă pentru o valoare. „Este par” și „este mai mare decât 10” sunt două exemple. Pentru un șir, întrebarea poate fi „Există cel puțin o valoare pară?” sau „Sunt toate valorile pare?”. Cele două întrebări au răspunsuri diferite pentru șirul $[3,4,5]$: la prima răspundem „da”, la a doua „nu”.

Pentru a verifica dacă există o valoare potrivită, cercetăm valorile pe rând. În șirul $[3,4,5]$, 3 nu este par; 4 este par, deci avem deja răspunsul „da”. Nu mai trebuie să verificăm 5 pentru această întrebare. Dacă ajungem la sfârșit fără să găsim nicio valoare potrivită, răspunsul este „nu”.

Pentru a verifica dacă toate valorile sunt potrivite, procedăm invers: căutăm o valoare care încalcă regula. În același șir, 3 este impar, deci răspunsul „nu” este cunoscut imediat. Dacă nicio valoare nu încalcă regula până la sfârșit, răspundem „da”.

Formulează cu atenție regula înainte de parcurgere. Dacă întrebarea este „Toate notele sunt cel puțin 5?”, nota 5 este acceptată. Testul „mai mare decât 5” ar respinge-o greșit. Pentru șirul $[5,7,8]$, toate notele sunt cel puțin 5, dar nu toate sunt mai mari decât 5. Cuvintele „cel puțin”, „mai mare” și „egal” au sensuri precise.

Exemplu rezolvat — sunt toate notele cel puțin 5? Notele sunt $[5,7,8,6]$ și întrebarea este „Sunt toate notele cel puțin 5?”. Pentru o întrebare cu „toate” cauți o valoare care încalcă regula.

1. Nota 5: este cel puțin 5, deci nu încalcă regula; mergi mai departe.
2. Nota 7: nu încalcă regula.
3. Nota 8: nu încalcă regula.
4. Nota 6: nu încalcă regula.
5. Ai ajuns la sfârșit fără nicio încălcare, deci răspunsul este „da”.

Dacă șirul ar fi fost $[5,3,8,6]$, la al doilea pas ai fi găsit nota 3, mai mică decât 5, și ai fi putut răspunde imediat „nu”, fără să verifici restul. Pentru o întrebare cu „există” procedezi invers: te oprești la prima valoare care respectă regula.

O proprietate a unei valori este o condiție care poate fi adevărată sau falsă pentru ea. Pentru un șir se pun două feluri de întrebări: existențială („există cel puțin un element cu proprietatea?”) și universală („au toate elementele proprietatea?”). Ele se verifică prin două scheme opuse. La „există” se pornește cu răspunsul False și se oprește la prima valoare potrivită, care îl schimbă în True. La „toate” se pornește cu True și se oprește la primul contraexemplu, care îl schimbă în False. Cele două întrebări sunt legate prin negare: „nu toate elementele sunt pare” înseamnă „există un element impar”. Pentru lista goală, „există” este fals, iar „toate” este adevărat, pentru că nu există niciun contraexemplu. În cel mai defavorabil caz se parcurge tot șirul, deci timpul este proporțional cu $n$.

Exemplul 1 — pare în $[3,4,5]$.

v = [3, 4, 5]
exista = False
for x in v:
    if x % 2 == 0:
        exista = True
        break
toate = True
for x in v:
    if x % 2 != 0:
        toate = False
        break
print(exista, toate)

Valoarea 4 dovedește afirmația existențială, iar 3 infirmă afirmația universală. Programul afișează True False. La primul ciclu se parcurg doar 3 și 4, deoarece break oprește căutarea; la al doilea se parcurge numai 3.

Exemplul 2 — șir crescător. Un șir este crescător dacă fiecare termen este mai mic decât următorul. Proprietatea este universală pe perechi de vecini: se caută o pereche care o încalcă. Pentru $[3,5,7]$ perechile $(3;5)$ și $(5;7)$ respectă regula, deci șirul este crescător. Pentru $[3,5,4,7]$ perechea $(5;4)$ o încalcă, iar răspunsul este „nu”.

a = [3, 5, 7]
crescator = True
for i in range(len(a) - 1):
    if a[i] >= a[i + 1]:
        crescator = False
        break
print(crescator)

Programul afișează True. Ciclul merge până la penultimul indice, pentru că a[i + 1] trebuie să existe. Condiția >= respinge și valorile egale, deci șirul $[3,3,5]$ nu este strict crescător.

Căutarea se oprește de îndată ce răspunsul este cunoscut, de aceea numărul de comparații depinde de poziția primei încălcări. Pentru $[3,5,7,9,2]$ perechile verificate sunt $(3;5)$, $(5;7)$, $(7;9)$ și $(9;2)$: ultima încalcă regula, deci răspunsul este „nu” după 4 comparații. Pentru un șir deja crescător se fac $n-1$ comparații, iar pentru un șir a cărui primă pereche încalcă regula, una singură.

Exemplul 3 — elementele sunt distincte? Pentru $[3,1,3]$ se compară fiecare pereche de poziții $i<j$: sunt $3$ perechi, iar perechea $(a_1;a_3)=(3;3)$ conține valori egale. Răspunsul la întrebarea „există două elemente egale?” este „da”, deci șirul nu are elementele distincte.

Exemplul 4 — toate valorile sunt într-un interval? Se cere dacă toate elementele șirului $[3,4,9,5]$ aparțin intervalului $[2,8]$. Proprietatea este universală, deci se caută un contraexemplu:

v = [3, 4, 9, 5]
in_interval = True
for x in v:
    if x < 2 or x > 8:
        in_interval = False
        break
print(in_interval)

Valorile 3 și 4 respectă condiția, iar 9 o încalcă, pentru că $9>8$. Variabila devine False după trei elemente verificate, iar break oprește ciclul fără să mai examineze valoarea 5. Programul afișează False. Negarea condiției „$2\le x\le 8$” este „$x<2$ sau $x>8$”, nu „$x<2$ și $x>8$”, care nu poate fi adevărată pentru nicio valoare. Același rezultat, spus existențial: există un element în afara intervalului, anume 9.

Greșeli frecvente

• Greșit: pentru o proprietate universală ajunge un element care o respectă.
  Corect: trebuie verificat că nicio valoare nu o încalcă.
• Greșit: „cel puțin 5” și „mai mare decât 5” au același sens.
  Corect: prima include 5, a doua nu.
• Greșit: pentru lista goală, „toate elementele sunt pare” este fals.
  Corect: este adevărat, pentru că nu există niciun contraexemplu.

Înainte și după