Dettagli

Scritto da Super User

Categoria: Appunti di Matematica

Pubblicato: 24 Settembre 2014

Visite: 17423

Intuitivamente si dispone di un algoritmo per risolvere un problema se si ha un elenco finito di istruzioni tali che:

•  a partire dai dati iniziali le istruzioni sono applicabili in maniera rigorosamente deterministica, cioè in modo che ad ogni passo sia sempre possibile stabilire univocamente quale è l’istruzione che deve essere applicata al passo successivo;
• si disponga di un criterio univoco per stabilire quando si è raggiunto uno stato finale, quando cioè il processo deve considerarsi terminato e il risultato, se esiste, è stato ottenuto. Uno stato finale deve sempre essere raggiungibile in un numero finito di passi.

Il termine deriva dal nome del matematico persiano Al-Khwarizmi (780 – 850 ca) in quanto egli fu uno dei primi a far riferimento esplicito al concetto di algoritmo nel suo “Libro della matematica orientale”. Dalla definizione di algoritmo è possibile evincere le due proprietà fondamentali di un algoritmo

• finitezza, ovvero la sequenza delle istruzioni di un algoritmo deve essere finita;
• effettività, ovvero ogni algoritmo deve portare ad un risultato. 

  Attachments:

  Algoritmo euclideo

  [Algoritmo euclideo]

  1096 kB

  Leggi tutto: Il concetto di algoritmo e le proprietà che un algoritmo deve avere