Algoritmo: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
m Annullata la modifica di 138.41.45.177 (discussione), riportata alla versione precedente di 31.191.90.124 Etichette: Rollback Modifica da mobile Modifica da web per mobile Modifica da mobile avanzata |
m sistemazione fonti e fix vari |
||
Riga 7:
* ''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 [[lingua latina|latina]] del nome del [[matematico]] persiano [[al-Khwarizmi]],<ref>[[Luca Serianni]], ''Grammatica italiana'', ed. UTET-De Agostini, Torino, 2010, ISBN 978-88-6008-057-8, p. 104.</ref> 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''.<ref>{{Cita web|url=https://www.corrieretneo.it/2018/11/25/algoritmo-la-teologia-della-complessita-capire-ed-emulare-dio/|titolo=Algoritmo, la teologia della complessità: capire ed emulare Dio - ?s=32, #038;d=mm, #038;r=g" width="32" height="32" alt="Avatar" class="avatar avatar-32wp-user-avatar wp-user-avatar-32 alignnone photo avatar-default" /> Giacomo Paternò ha detto|data=
Le prime nozioni di algoritmo si trovano in documenti risalenti al [[XVII secolo a.C.]], conosciuti come i papiri di [[Ahmes]], noti anche come [[Papiro di Rhind|papiri di Rhind]],<ref>{{Cita web|url=https://www.britishmuseum.org/collection/object/Y_EA10058|titolo=papyrus {{!}} British Museum|sito=The British Museum|lingua=en|accesso=
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]].
Riga 15:
== 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 "[[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|nome=Yiannis N.|cognome=Moschovakis|capitolo=What is an algorithm?|titolo=Mathematics Unlimited — 2001 and beyond|curatore-nome=B.|curatore-cognome=Engquist|curatore-nome2=W.|curatore-cognome2=Schmid|editore=Springer|anno=2001|pp=919–936 (Part II)|url=http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.32.8093}}</ref> 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".▼
▲}}</ref> 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".
=== Modelli formali ===
[[File:Quicksort example small.png|thumb
{{vedi anche|Teoria della calcolabilità#Che cos'è un algoritmo}}
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: {{
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 49 ⟶ 36:
* l'esecuzione deve portare a un risultato univoco (''effettività'').
[[File:Algoritmo para Procesar y Organizar en GTD.png|thumb
Così, ad esempio, "rompere le uova" può essere considerato legittimamente un passo elementare di un "algoritmo per la cucina" (ricetta), ma non potrebbe esserlo anche "aggiungere sale quanto basta" dato che l'espressione "quanto basta" è ambigua, e non indica con precisione quali passaggi servano per determinare la quantità necessaria.
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''.
Riga 274 ⟶ 261:
* {{FOLDOC|algorithm|algorithm}}
* {{Garzanti}}
*
* {{Cita testo|lingua=es
* {{cita web|url=http://www.nist.gov/dads/|titolo=Dizionario degli algoritmi e delle strutture dati|lingua=en}}
{{Controllo di autorità}}
| |||