Algoritmo
Il concetto di algoritmo si è evoluto insieme ai sistemi di calcolo.
Un algoritmo è
- una macchina di Turing che per ogni istanza del problema in esame restituisce, in tempo finito, le risposte attese
- un programma per una macchina di Turing universale che ...
- un programma in forma comprensibile per una macchina programmabile che ...
- un programma in forma comprensibile per l'uomo che ...
Non esiste un modello unico per rappresentare un algoritmo.
La scelta dipende da
problema, paradigma di programmazione, risolutore, esecutore, ...
| Diagramma di stato | Stati e transizioni di stato: cerchi e frecce |
| Programma per la macchina di Turing | Quintuple di simboli |
| Diagramma di flusso | Flow-chart: rombi, rettangoli, cerchi, frecce Istruzioni, decisioni |
| Programma scritto con un linguaggio di basso livello | Istruzioni per la macchina a registri Linguaggio a salti... |
| ... un linguaggio di alto livello | Istruzioni interpretate/compilate Linguaggio strutturato! |
| ... uno pseudo-linguaggio | Istruzioni più vicine a formalismi già noti Linguaggio naturale, formalismo logico-matematico ... |
Alcune considerazioni
- numero finito di istruzioni/stati
- istruzioni non ambigue, eseguibili in tempo finito
- algoritmo eseguibile in tempo finito
