Contraexemplu minim: cum reduci o intrare care eșuează
Redu un test care produce un răspuns greșit până când cauza devine clară. Vezi cum păstrezi condițiile problemei și diferența față de referință.
În acest material
Un contraexemplu este o intrare permisă pentru care programul produce un rezultat greșit. Un contraexemplu mic este mai ușor de explicat decât un fișier cu mii de valori. Scopul reducerii nu este să obții cel mai scurt text cu orice preț, ci să păstrezi eroarea și contractul problemei.
Pornește de la o diferență verificată
Presupune că un algoritm trebuie să găsească maximul unui vector nevid, dar îl inițializează cu zero. Pe intrarea -9 -4 -7 -2, programul întoarce 0, deși răspunsul este -2. Calculează rezultatul corect separat. Dacă și programul de referință are aceeași eroare, comparația dintre ele nu te ajută.
Elimină jumătate dintre elemente și verifică din nou. Vectorul -9 -4 păstrează problema. Redu-l la -4: rezultatul corect rămâne negativ, iar programul continuă să întoarcă zero. Acum cauza este vizibilă fără un tabel lung de execuție.
Fiecare reducere trebuie să păstreze atât validitatea intrării, cât și răspunsul greșit.Mărește schema ↗
Nu distruge proprietatea garantată
După fiecare reducere, verifică mai întâi dacă intrarea rămâne validă. Dacă enunțul cere cel puțin două elemente, nu poți folosi un vector de lungime unu drept contraexemplu al acelei probleme. Dacă graful trebuie să fie conex, ștergerea unei muchii poate invalida testul înainte să spună ceva despre algoritm.
În problemele cu mai multe câmpuri, păstrează și coerența lor. Când elimini elemente, actualizează n. Când elimini vârfuri, remapează etichetele și capetele muchiilor. O eroare de citire introdusă de reducere poate înlocui bugul pe care îl urmăreai.
Redu și valorile, nu doar dimensiunea
După ce nu mai poți elimina elemente, încearcă valori mai simple: 0, 1, -1 sau valori apropiate între ele, dacă domeniul le permite. Pentru exemplul maximului, -1 este suficient. Pentru un overflow, însă, micșorarea prea mult a valorii face eroarea să dispară; păstrează o valoare care încă depășește pragul relevant.
Reducerea este un experiment repetat: propui o schimbare, verifici validitatea și verifici că diferența persistă. Dacă una dintre condiții eșuează, revii la ultima versiune utilă. Salvează la final intrarea, răspunsul corect și o propoziție despre cauza identificată. După reparare, acest caz devine un test de regresie.
Continuă cu maxime și minime, complexitatea algoritmilor, interpretarea verdictelor.
Întrebări frecvente
Trebuie să găsesc cel mai mic contraexemplu posibil?
Nu neapărat. Un caz suficient de mic pentru a explica eroarea este deja util. Minimul absolut poate cere multă căutare și nu este întotdeauna necesar pentru diagnostic.
Pot elimina o condiție din enunț când reduc testul?
Nu dacă vrei un contraexemplu valid pentru problema originală. Intrarea redusă trebuie să păstreze toate garanțiile cerute, precum sortarea, conexitatea sau dimensiunea minimă.
De ce păstrez testul după corectare?
El verifică exact greșeala pe care ai reparat-o. Rularea lui după modificări ulterioare ajută la detectarea reapariției aceleiași probleme.