Algoritmo: differenze tra le versioni

Versione delle 14:08, 22 giu 2023

Versione delle 15:58, 22 giu 2023

Riga 1:

{{Nota disambigua}}

{{Nota disambigua}}In matematica e informatica un algoritmo è la specificazione di una sequenza finita di operazioni (dette anche istruzioni) che consente di risolvere tutti i quesiti di una stessa classe o di calcolare il risultato di un'espressione matematica. Un algoritmo deve essere

finito: è costituito da un numero finito di istruzioni e deve sempre terminare;

deterministico: partendo dagli stessi dati in ingresso, si devono ottenere i medesimi risultati;

non ambiguo: le operazioni non devono poter essere interpretate in modi differenti;

generale: deve essere applicabile a tutti i problemi della classe a cui si riferisce, o ai casi dell'espressione matematica.

Il termine deriva dalla trascrizione latina del nome del matematico persiano al-Khwarizmi,[1] vissuto nel IX secolo d.C., che è considerato uno dei primi autori ad aver fatto riferimento a questo concetto scrivendo il libro Regole di ripristino e riduzione.[2]

Le prime nozioni di algoritmo si trovano in documenti risalenti al XVII secolo a.C., conosciuti come i papiri di Ahmes, noti anche come papiri di Rhind,[3] che contengono una collezione di problemi con relativa soluzione comprendendo un problema di moltiplicazione che lo scrittore dichiara di aver copiato da altri papiri anteriori di 12 secoli.

L'algoritmo è un concetto fondamentale dell'informatica, anzitutto perché è alla base della nozione teorica di calcolabilità: un problema è calcolabile quando è risolvibile mediante un algoritmo. Inoltre, l'algoritmo è un concetto cardine anche nella fase di programmazione dello sviluppo di un software: preso un problema da automatizzare, la programmazione costituisce essenzialmente la traduzione o codifica di un algoritmo per tale problema in programma, scritto in un certo linguaggio, che può essere quindi effettivamente eseguito da un calcolatore rappresentandone la logica di elaborazione.

In [[matematica]] e [[informatica]] un '''algoritmo''' è la specificazione di una sequenza finita di operazioni (dette anche ''istruzioni'') che consente di risolvere tutti i quesiti di una stessa classe o di calcolare il risultato di un'espressione matematica. Un algoritmo deve essere

Riga 23 ⟶ 13:

L'algoritmo è un concetto fondamentale dell'[[informatica]], anzitutto perché è alla base della nozione teorica di [[Teoria della calcolabilità|calcolabilità]]: un problema è calcolabile quando è risolvibile mediante un algoritmo. Inoltre, l'algoritmo è un concetto cardine anche nella fase di [[Programmazione (informatica)|programmazione]] dello [[ciclo di vita del software|sviluppo di un software]]: preso un problema da [[automatica|automatizzare]], la programmazione costituisce essenzialmente la traduzione o [[codifica]] di un algoritmo per tale problema in [[programma (informatica)|programma]], scritto in un certo [[linguaggio]], che può essere quindi effettivamente [[esecuzione (informatica)|eseguito]] da un [[calcolatore]] rappresentandone la logica di [[Elaborazione dati|elaborazione]].

== Definizione ==

== Definizione ==Nel XX secolo, il concetto di algoritmo venne formalizzato per risolvere il problema matematico della "decisione" (Entscheidungsproblem), posto da David Hilbert nel 1928, e altre successive formalizzazioni giunsero con lo sviluppo dei concetti di "calcolabilità effettiva"[4] e di "metodo effettivo"[5]. Le formalizzazioni matematiche più famose sono le funzioni ricorsive di Gödel–Herbrand–Kleene del 1930, 1934 e 1935; il lambda calcolo di Alonzo Church e la Formulation 1 di Emil Leon Post del 1936; e, infine, la macchina di Turing del 1936–37 e 1939. Nonostante ciò, una definizione del concetto di algoritmo che sia formale e non tecnica manca tuttora[6] e si è pertanto costretti ad accontentarsi dell'idea intuitiva di algoritmo come "una sequenza ordinata e finita di passi (operazioni o istruzioni) elementari che conduce a un ben determinato risultato in un tempo finito

Nel [[XX secolo]], il concetto di algoritmo venne formalizzato per risolvere il problema matematico della "decisione" (''[[Entscheidungsproblem]]''), posto da [[David Hilbert]] nel 1928, e altre successive formalizzazioni giunsero con lo sviluppo dei concetti di "[[effective calculability|calcolabilità effettiva]]"<ref>Kleene 1943 in Davis 1965:274</ref> e di "metodo effettivo"<ref>Rosser 1939 in Davis 1965:225</ref>. Le formalizzazioni matematiche più famose sono le [[funzioni ricorsive]] di [[Kurt Gödel|Gödel]]–[[Jacques Herbrand|Herbrand]]–[[Stephen Cole Kleene|Kleene]] del 1930, 1934 e 1935; il [[lambda calcolo]] di [[Alonzo Church]] e la [[Formulation 1]] di [[Emil Leon Post]] del 1936; e, infine, la [[macchina di Turing]] del 1936–37 e 1939. Nonostante ciò, una definizione del concetto di algoritmo che sia formale e non tecnica manca tuttora<ref>

{{Cita libro

Riga 72 ⟶ 62:

Inizialmente un algoritmo può essere descritto attraverso l'uso di un [[diagramma di flusso]] o ricorrendo a uno [[pseudocodice]]. Successivamente, nella fase di [[Programmazione (informatica)|programmazione]] l'algoritmo così scritto verrà tradotto in [[linguaggio di programmazione]] a opera di un [[programmatore]] sotto forma di [[codice sorgente]] dando vita al [[programma (informatica)|programma]] che sarà [[esecuzione (informatica)|eseguito]] dal calcolatore, eventualmente dopo un'ulteriore traduzione in [[linguaggio macchina]]. Particolare rilevanza teorica in tale ambito assume il [[teorema di Böhm-Jacopini]] che afferma che qualunque algoritmo può essere implementato utilizzando tre sole strutture, la [[sequenza (informatica)|sequenza]], la [[selezione (informatica)|selezione]] e il ciclo ([[iterazione]]), da applicare ricorsivamente alla composizione di [[istruzione (informatica)|istruzioni]] elementari. Nella pratica corrente il programmatore professionista nel suo lavoro svolge automaticamente questo processo di traduzione scrivendo direttamente il codice sorgente necessario nelle suddette modalità avendo già trovato la soluzione al problema dato.

== Approccio matematico ==

== Approccio matematico ==Dalla precedente definizione di algoritmo si evincono alcune proprietà necessarie, senza le quali un algoritmo non può essere definito tale:

i passi costituenti devono essere "elementari", ovvero non ulteriormente scomponibili (atomicità);

i passi costituenti devono essere interpretabili in modo diretto e univoco dall'esecutore, sia esso umano o artificiale (non ambiguità);

l'algoritmo deve essere composto da un numero finito di passi e richiedere una quantità finita di dati in ingresso (finitezza)

l'esecuzione deve avere termine dopo un tempo finito (terminazione);

l'esecuzione deve portare a un risultato univoco (effettività).

Esistono numerosi modelli matematici di algoritmo. In generale, un algoritmo riceve un insieme di valori (dati) in [[input]] e ne genera uno in output (chiamato soluzione). Dato dunque un algoritmo A si denota con f_A la funzione che associa a ogni ingresso x di A la corrispondente uscita.

Riga 92 ⟶ 76:

dove <math>D \pi</math> sono le istanze del problema e <math> S \pi </math> sono le soluzioni e <math>\forall x \in D \pi:f \pi (x) </math> sia una soluzione al problema per l'istanza x.

=== Studio della complessità computazionale di un algoritmo ===

=== Studio della complessità computazionale di un algoritmo ===Esistono numerosi modelli matematici di algoritmo. In generale, un algoritmo riceve un insieme di valori (dati) in input e ne genera uno in output (chiamato soluzione). Dato dunque un algoritmo A si denota con fA la funzione che associa a ogni ingresso x di A la corrispondente uscita.

Questa corrispondenza tra input e output non rappresenta il problema risolto dall'algoritmo. Formalmente, un problema è una funzione

�

(

�

�

)

→

�

�

f(D_{i})\to D_{s} definita su insieme Di di elementi che chiameremo restanze, a valori su un insieme Ds di risoluzioni.

Lo studio di un algoritmo viene suddiviso in due fasi:

sintesi (detta anche disegno o progetto): dato un problema A, costruire un algoritmo f per risolvere A, cioè tale che f=fa.

analisi: dato un algoritmo f e un problema A, dimostrare che f risolve A, cioè f=fa (correttezza) e valutare la quantità di risorse usate da f (complessità concreta).

{{vedi anche|Teoria della complessità computazionale}}

Riga 196 ⟶ 164:

* l'algoritmo di Gauss non richiede altro spazio oltre a quello necessario per memorizzare la matrice dei coefficienti e il vettore dei termini noti. Al termine dell'algoritmo il vettore dei termini noti conterrà la soluzione. Pertanto la sua complessità spaziale è anch'essa minima: <math>O(n^2)</math>.

== Strutture di dati ==

== Strutture di dati ==Un'ampia porzione della teoria degli algoritmi è lo studio della complessità, computazionale e spaziale. Vogliamo cioè sapere, al crescere della complessità del problema, in che modo cresce il tempo necessario a eseguire l'algoritmo e lo spazio di memoria occupato in un calcolatore.

La complessità di un algoritmo si misura asintoticamente. Vi sono quattro metodi per calcolare la complessità di un algoritmo:

metodo di sostituzione

metodo dell'iterazione

metodo dell'albero

metodo dell'esperto

Si definisce asintotica per due motivi

poiché ogni calcolatore può implementare algoritmi in modo differente, non si può stimare il tempo preciso

si vuole dare un'idea quantitativa di come l'algoritmo possa crescere in consumo di tempo all'aumentare dell'input, per valori sempre maggiori.

Presa una funzione associata a un algoritmo del tipo:

{{vedi anche|Struttura dati}}

Riga 261 ⟶ 217:

Molte categorie di algoritmi sono strettamente legate all'organizzazione dei dati in memoria ([[struttura dati|strutture dati]]).

=== Altri algoritmi ===

=== Altri algoritmi ===La maggior parte degli algoritmi si avvalgono di tecniche per rappresentare ed organizzare i dati utilizzati nel calcolo e tali rappresentazioni, chiamate strutture dati, non sono necessariamente altrettanto sofisticate rispetto all'algoritmo che le usa: algoritmi semplici possono richiedere strutture dati complesse e viceversa.

Per agevolare ed astrarre la gestione e l'interazione di strutture dati complesse, vengono sviluppati appositi algoritmi che implementano le operazioni più comuni da svolgere su di esse. Esempi di strutture dati comuni sono i vettori, le liste, le code, le pile, gli alberi e i grafi.

{{div col|cols=3}}

* [[informatica quantistica|Algoritmi quantistici]]