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, la risposta attesa
- 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 … (questo punto è controverso!)
Un algoritmo è
- Un procedimento che permette di risolvere un certo problema tramite un numero finito di passi.
- Una sequenza ordinata e finita di passi (operazioni o istruzioni) elementari che conduce ad un ben determinato risultato in un tempo finito.
- …
Non esiste un modello unico per rappresentare un algoritmo.
La scelta dipende dal tipo di problema, dal paradigma di programmazione, dal risolutore, dall’esecutore, …
| Diagramma di stato | Stati e transizioni di stato | Cerchi e frecce |
| Sequenza di quintuple | Programma per la macchina di Turing | Stati, simboli, spostamenti |
| Tabella delle transizioni di stato | Programma per la macchina di Turing | Stati, simboli, triple |
| 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… |
| Programma scritto con un linguaggio di alto livello | Istruzioni interpretate/compilate | Linguaggio strutturato! |
| Programma scritto con uno pseudo-linguaggio | Istruzioni più vicine a formalismi già noti | Linguaggio naturale, formalismo logico-matematico … |
Alcune considerazioni…
- le istruzioni (gli stati) sono in numero finito
- le singole istruzioni sono non ambigue per l’esecutore
- le singole istruzioni sono eseguibili in tempo finito
- l’intero algoritmo è eseguibile in tempo finito
- la risposta per una certa istanza è sempre la stessa…