La tabella di esecuzione di un algoritmo (in inglese trace table) è uno strumento utile per verificare la correttezza di un algoritmo simulandone l'esecuzione. Consideriamo a titolo di esempio di nuovo l'algoritmo seguente, rappresentato con un flow chart:
Per scrivere la trace table, dobbiamo crearci una tabella contenente tante colonne quante sono le variabili usate nel programma. Il numero di righe della tabella è inizialmente indeterminato e dipende dal numero di calcoli (iterazioni) che l'esecuzione del programma comporterà. Cominciamo dunque con una tabella fatta in questo modo:
| A | B | C |
All'inizio la nostra tabella è vuota. Ora immaginiamo di eseguire l'algoritmo. Le prime istruzioni che incontriamo sono:
I valori di A e B vengono forniti dall'utente: dunque, per poter simulare una esecuzione del nostro algoritmo, dobbiamo assegnare ad A e B due valori qualunque, scelti più o meno a caso, che rappresenteranno i dati di ingresso: supponiamo per esempio di scegliere A=3 e B=4. Invece il valore di C è assegnato a 0 dal programma. Compiliamo dunque la prima riga della nostra trace table con questi tre valori:
| A | B | C |
| 3 | 4 | 0 |
A questo punto, continuando a seguire il nostro diagramma di flusso, simuliamo l'esecuzione del test all'inizio del ciclo:
La risposta è ovviamente SI, perché nel nostro caso A vale 3 e dunque A≠0. Seguiamo dunque il ramo del SI e troviamo:
Queste due istruzioni modificano il valore di C e di A: per tenerne conto aggiungiamo un'altra riga in tabella con i valori aggiornati:
| A | B | C |
| 3 | 4 | 0 |
| 2 | 4 | 4 |
Come si vede il valore di B non è cambiato, per cui ci siamo limitati a ricopiare il valore che aveva prima (4). A questo punto seguendo il ramo di ritorno del ciclo, dobbiamo ripetere il test:
Anche questa volta la risposta è SI perché A vale 2 (seconda riga della nostra trace table). Dobbiamo dunque eseguire il ciclo un'altra volta e ricalcolare i valori di C e A che adesso diventano:
| A | B | C |
| 3 | 4 | 0 |
| 2 | 4 | 4 |
| 1 | 4 | 8 |
Il ciclo si ripete ancora una volta (infatti A è sempre diverso da zero) e i valori ricalcolati sono:
| A | B | C |
| 3 | 4 | 0 |
| 2 | 4 | 4 |
| 1 | 4 | 8 |
| 0 | 4 | 12 |
A questo punto A è diventato zero e il ciclo termina e viene visualizzato il valore di C (12):
Non è difficile osservare come, dati i valori di ingresso A = 3 e B = 4, l'algoritmo abbia calcolato il prodotto di A * B (12). In effetti questo algoritmo serve proprio a calcolare un prodotto fra interi attraverso una serie di somme.
Naturalmente in generale non è sufficiente un'unica prova per dire che un algoritmo funziona correttamente, ma occorre invece provare ad eseguirlo con molti diversi valori di ingresso e, in ciascuno dei casi, simulare l'esecuzione compilando una trace table.
precedente
Sito realizzato in base al template offerto da
http://www.graphixmania.it
