Comprendi input, terminazione e correttezza di un algoritmo elementare.
Un algoritmo descrive un procedimento con istruzioni precise, che portano a un risultato per i dati ammessi dal problema. Qui consideriamo compiti che devono concludersi: il procedimento deve terminare dopo un numero finito di passi per ogni input valido. Non basta scrivere poche righe: anche una sola istruzione che ripete senza fine impedisce di arrivare alla soluzione. Prima di progettare i passi, bisogna perciò chiarire quali dati si accettano e quale risultato si vuole ottenere.
Per trovare il maggiore fra due numeri a e b, un possibile procedimento è questo: confronta a con b; se a è maggiore o uguale a b, restituisci a; altrimenti restituisci b. Se a e b sono uguali, il primo ramo restituisce quel valore, che è comunque il massimo. L’esempio distingue ingresso, condizione e uscita. Lo stesso procedimento può essere descritto con pseudocodice o con un diagramma di flusso: l’algoritmo non coincide con un particolare linguaggio di programmazione.
Provare numeri positivi, negativi e uguali aiuta a scoprire errori, ma alcuni test riusciti non dimostrano, da soli, la correttezza per tutti gli input possibili. Nell’esempio possiamo ragionare sui due casi: se a è almeno b, il massimo è a; nel caso contrario è b. Entrambi i rami restituiscono un risultato e non contengono ripetizioni. Questo ragionamento spiega perché il procedimento funziona, invece di limitarsi a mostrare esempi favorevoli.
Correttezza ed efficienza sono domande diverse. La prima riguarda il risultato corretto e la terminazione per ogni input valido; la seconda considera risorse come tempo e memoria. Un algoritmo può essere corretto ma poco efficiente. Inoltre, uno stesso algoritmo può avere più implementazioni: quando lo trasformi in un programma, devi controllare anche che le istruzioni scritte realizzino davvero il procedimento progettato.
- Gli input validi e il risultato atteso vanno precisati prima dei passi.
- Per un compito finito, istruzioni non ambigue e terminazione sono essenziali.
- I test trovano errori, ma pochi esempi riusciti non provano la correttezza generale.
Metti alla prova quello che hai letto
Quale affermazione descrive correttamente il controllo di un algoritmo?
- Basta un solo esempio riuscito per dimostrarne la correttezza generale
- Occorre ragionare sul risultato e sulla terminazione per gli input validi
- Un algoritmo corretto deve usare sempre Internet
- Un algoritmo esiste solo nel linguaggio Python
Soluzione e spiegazione
Occorre ragionare sul risultato e sulla terminazione per gli input validi. La correttezza riguarda tutti gli input ammessi. Provare alcuni casi è utile, ma non sostituisce un ragionamento generale; Internet e un particolare linguaggio non sono requisiti.
Fonti
- Algorithms, diapositive 2–6 e 12–14 — Virginia Tech, W. McQuain, CS 2104
- CSE417 — Algorithm Correctness — University of Washington, CSE417
- Algorithm — Dictionary of Algorithms and Data Structures — NIST, Paul E. Black
Nota editoriale
Confronto assistito documentato; revisione docente necessaria
Il registro editoriale conserva riserve aperte sull’indipendenza dei riscontri: l’elenco delle fonti non certifica da solo due verifiche indipendenti di ogni affermazione.