Algoritmo: differenze tra le versioni

Versione delle 13:41, 13 dic 2024

Versione attuale delle 08:08, 26 set 2025

(6 versioni intermedie di 6 utenti non mostrate)

Riga 25:

La definizione di algoritmo appena riportata è piuttosto informale, mentre era necessario disporre di una definizione più rigorosa per trattare il concetto di algoritmo con strumenti matematici. Al tal fine sono stati definiti alcuni [[Modello matematico|modelli matematici]] di algoritmo, fra i quali uno dei più celebri è la [[macchina di Turing]]. Essa rappresenta una sorta di ''computer'' ideale corredato di un [[Programma (informatica)|programma]] da eseguire, ma, rispetto a un computer reale, la macchina di Turing ha un funzionamento estremamente più semplice che possa essere facilmente descritto con termini matematici, facendo uso di concetti come [[insieme]], [[relazione (matematica)|relazione]] e [[funzione (matematica)|funzione]].

La [[architettura di von Neumann|macchina di Von Neumann]], che è il modello di architettura primigenio di tutti i computer attuali, è equivalente, in termini di potere di calcolo, alla macchina di Turing. In altre parole, è stato dimostrato che un certo problema può essere risolto da un computer (opportunamente programmato) [[se e solo se]] esso può essere risolto anche da una macchina di Turing. Oltre alla macchina di Turing, proposta da [[Alan Turing]] nel [[1936]], nello stesso periodo altri matematici hanno elaborato diverse rappresentazioni formali del concetto di algoritmo, fra i quali ricordiamo, per esempio, il [[lambda calcolo]]. Dopo alcuni anni, emerse che tutti questi modelli erano equivalenti: {{Senza fonte|i problemi che una macchina di Turing poteva risolvere erano gli stessi che poteva risolvere una macchina di von Neumann e anche gli stessi che poteva risolvere una funzione costruita col lambda calcolo}}.

Da questi risultati, tra l'altro, scaturì la [[tesi di Church-Turing]], che afferma che qualsiasi algoritmo sia modellabile con una macchina di Turing. In altri termini, questa tesi sostiene che è sostanzialmente impossibile cercare di immaginare un modello di algoritmo più potente e, di conseguenza, che nessuna macchina potrà mai risolvere problemi che una macchina di Turing non possa risolvere in linea di principio. Non si tratta di un [[teorema]] dimostrato matematicamente, poiché la tesi stabilisce l'eguaglianza di due concetti, l'algoritmo e la macchina di Turing, ma il primo non possiede una definizione formale. La tesi è oggi generalmente condivisa, sebbene i progressi nelle ricerche nel settore dell'[[ipercomputazione]] sembrino talvolta metterla in discussione.

Riga 45:

All'istruzione non elementare di preparazione della crema potrebbe, però, essere associato un opportuno rimando a un'altra sezione del ricettario, che fornisca un sotto-algoritmo apposito per questa specifica operazione. Questo suggerisce che, per comodità d'implementazione, gli algoritmi possano essere ''modulari'', ovvero orientati a risolvere specifici sotto-problemi, e ''gerarchicamente organizzati''. Inoltre, una ricetta che preveda la cottura a [[microonde]] non può essere preparata da un esecutore sprovvisto dell'apposito elettrodomestico; questo rimanda al problema della ''realizzabilità'' degli algoritmi, ovvero della loro compatibilità con le risorse materiali e temporali a disposizione. Infine, possono darsi più algoritmi validi per risolvere uno stesso problema, ma ognuno con un diverso grado di ''efficienza''.

L'algoritmo viene generalmente descritto come "procedimento di risoluzione di un problema". In questo contesto, i "problemi" che si considerano sono quasi sempre caratterizzati da ''dati di ingresso'' ([[input]]) variabili, su cui l'algoritmo stesso opererà per giungere fino alla soluzione. Per esempio, il calcolo del [[Massimo comun divisore|massimo comune divisore]] fra due numeri è un esempio di "problema", e i suoi ''dati di ingresso'', variabili di volta in volta, sono i due numeri in questione. A un non matematico questa potrebbe apparire come una "famiglia di problemi" (il problema di calcolare il massimo comune divisore fra 10 e 15, il problema di calcolarlo fra 40 e 60, fra 35 e 95, e così via). Il matematico e l'informatico identificano con la parola "problema" l'intera famiglia e con "istanza" o "x" ciascuno dei quesiti specifici ottenuti fissando due particolari valori. Data questa premessa, un algoritmo risolve un problema se per qualunque istanza del problema esso produce in un tempo finito la soluzione desiderata, ovvero un certo risultato o dato in uscita ([[Input/output|output]]) a partire da dei dati in ingresso ([[input]]).

Se questa idea aveva già una certa importanza per il calcolo matematico, l'avvento dell'informatica l'ha arricchita di una nuova importanza, ed è infatti con l'informatica che il termine "algoritmo" ha iniziato a diffondersi. Difatti, se per ottenere un certo risultato (risolvere un certo problema) esiste un procedimento infallibile, che può essere descritto in modo non ambiguo fino ai dettagli, e conduce sempre all'obiettivo desiderato in un tempo finito, allora esistono le condizioni per affidare questo compito a un [[computer]], semplicemente introducendo l'algoritmo in questione in un [[Programma (informatica)|programma]] scritto in un opportuno [[linguaggio di programmazione|linguaggio]] comprensibile alla macchina.

Riga 89:

che esprime la dimensione dei dati in ingresso, ossia il numero di bit che servono per codificare i dati in input all'algoritmo.

Ad esempio su un vettore la lunghezza dello stesso determinerà il numero di bit necessari a codificarlo e sulle matrici il numero dell'ordine, ossia presa ad esempio una [[matrice quadrata]] l'ordine della stessa è determinata da una delle due dimensioni (orizzontale oppure verticale).

La complessità di un algoritmo si definisce come: