Gli algoritmi

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 … (questo punto è controverso!)
Vedi le definizioni fornite da Wikipedia:Algoritmo

Un algoritmo è

  1. Un procedimento che permette di risolvere un certo problema tramite un numero finito di passi.
  2. 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 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…

  • 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…