· informatica · 1 min read
Cosa é un algoritmo?
La macchina di Turing rappresenta un esempio di modello astratto di una macchina in grado di eseguire programmi.La sua importanza è tale in quanto la Macchina di Turing risulta legata al concetto di complessità e di computazionalità. Vediamone le caratteristiche fondamentali
Un algoritmo è la “descrizione” dei passi necessari per risolvere un problema. Affinchè un qualsiasi procedimento risolutivo possa essere considerato e definito come algoritmo abbiamo bisogno di alcune proprietà fondamentali:
- finitezza: un algoritmo deve avere un numero finito di passi che portano alla soluzione.
- completezza: deve contemplare tutte le possibili casistiche del problema da risolvere.
- non ambiguo: non devono esserci elementi ambigui o imprecisi. Non deve esserci spazio all’interpretazione.
- generale: deve risolvere una intera classe di problemi.
- eseguibile: deve esistere un agente di calcolo in grado di eseguirlo in un tempo finito.
Esistono due categorie di algoritmi: quelli deterministici e quelli non deterministici. I secondi, a differenza dei primi, presentano almeno un elemento per cui sono possibili più elementi successivi da scegliere secondo un processo probabilistico. Questa categoria di algoritmi è molto importante, pensa che tutte le questioni relative all’intelligenza artificiale e agli algoritmi genetici si basano su questo tipo di algoritmi.
