• Istituto
    • Chi Siamo
    • La nostra storia
  • Magazine
    • Agenda
    • Atlante
    • Il Faro
    • Il Chiasmo
    • Diritto
    • Il Tascabile
    • Le Parole Valgono
    • Lingua italiana
    • WebTv
  • Catalogo
    • Le Opere
    • Bottega Treccani
    • Gli Ebook
    • Le Nostre Sedi
  • Scuola e Formazione
    • Portale Treccani Scuola
    • Formazione Digitale
    • Formazione Master
    • Scuola del Tascabile
  • Libri
    • Vai al portale
  • Arte
    • Vai al portale
  • Treccani Cultura
    • Chi Siamo
    • Come Aderire
    • Progetti
    • Iniziative Cultura
    • Eventi Sala Igea
  • ACQUISTA SU EMPORIUM
    • Arte
    • Cartoleria
    • Design & Alto Artigianato
    • Editoria
    • Idee
    • Marchi e Selezioni
  • Accedi
    • Modifica Profilo
    • Treccani X

algoritmo

Enciclopedia on line
  • Condividi

Matematica

Termine, derivato dall’appellativo al-Khuwārizmī («originario della Corasmia») del matematico Muḥammad ibn Mūsa del 9° sec., che designa qualunque schema o procedimento sistematico di calcolo (per es. l’a. euclideo, delle divisioni successive, l’a. algebrico, insieme delle regole del calcolo algebrico ecc.). Con un a. si tende a esprimere in termini matematicamente precisi il concetto di procedura generale, di metodo sistematico valido per la soluzione di una certa classe di problemi. Come esempio consideriamo un a. che codifica un comportamento assai comune, quello di una persona che confronta due parole. Esprimeremo questo a. in un linguaggio naturale un po’ rigido, tenendo presente che questa descrizione informale dell’a. è il punto di partenza anche per il disegno di nuovi algoritmi. A volte si usa, per lo stesso scopo, una rappresentazione grafica equivalente, il cosiddetto diagramma di flusso (➔ flowchart).

confronta (due stringhe di caratteri, S1 e S2, dando come risultato 0 se sono diverse, 1 se sono uguali)

1. Se S1 e S2 hanno lunghezza differente finisci ponendo risultato = 0, altrimenti

2. sia L la lunghezza di S1 e S2.

3. Per ciascuno dei valori di j da 1 a L esegui i seguenti passi:

4. confronta il carattere j-mo di S1 con il carattere j-mo di S2:

5. se sono diversi finisci ponendo risultato = 0, altrimenti

6. passa al successivo valore di j (se non sono esauriti).

7. Una volta esauriti i valori di j finisci dichiarando risultato = 1.

Si noti come l’a. riceva dei dati in ingresso (input) costituiti da due stringhe di caratteri di un alfabeto precisato e di lunghezza qualsiasi, producendo dei dati in uscita (output) che, in questo caso, sono le cifre 0 o 1.

Proprietà fondamentali di un algoritmo

Effettività. Un a. deve essere effettivamente eseguibile da un esecutore, che diciamo automa; l’automa deve poter riconoscere cioè le parti minime della descrizione dell’a. ossia deve accettare il linguaggio in cui l’a. è espresso; le frasi ben formate di questo linguaggio si dicono istruzioni.

Finitezza di espressione. Anche se si possono pensare procedure la cui definizione non finisce mai (per es. la rotta di una nave) per il semplice fatto che la lista delle istruzioni aumenta continuamente, nella nozione di a. si tende a non comprendere questo tipo di procedure; un a. è dunque una successione finita di istruzioni da eseguire; con un numero finito di istruzioni si può naturalmente descrivere anche un procedimento molto lungo (eventualmente anche infinito, come nelle divisioni che danno un numero periodico, o in certe radici quadrate).

Finitezza di calcolo. Nel concetto di a. è solitamente inclusa la condizione di terminazione della procedura per qualsiasi situazione dei dati iniziali all’interno di un certo dominio.

Determinismo. A ogni passo dell’esecuzione della procedura deve essere definita una e una sola operazione da eseguire successivamente. La condizione 1.1 è praticamente irrinunciabile; la 1.2, la 1.3 e la 1.4 possono essere rese meno stringenti o abbandonate del tutto, dando luogo a concetti più generali di quello di algoritmo. In particolare l’abbandono della condizione 1.4 porta al concetto di a. non deterministico.

Teorie degli algoritmi

Si possono distinguere due linee di pensiero. Da un lato si cerca di precisare il concetto di operazione effettiva (realizzabile cioè mediante a.). Su questa linea si sviluppano il concetto di funzione ricorsiva, la definizione delle funzioni mediante l’operatore di astrazione lambda e i sistemi di combinatori di H.B. Curry. Dall’altro si cerca di caratterizzare in modo astratto il procedimento di calcolo. Si hanno in questo modo la teoria delle macchine di A. Turing, la teoria degli a. normali di A.A. Markov, e i sistemi di produzioni di E.L. Post. L’aspetto convergente e interessante delle varie teorie degli a. sta nel fatto che esse sono state dimostrate equivalenti. È possibile costruire delle macchine di Turing che calcolano una qualsiasi funzione ricorsiva, dei sistemi di Post che eseguono il calcolo di una qualsiasi macchina di Turing ecc. Questo è una conferma empirica della cosiddetta tesi di A. Church, secondo cui le funzioni computabili mediante a. sono tutte e sole le funzioni ricorsive generali. Non sono state sinora trovate smentite a questa tesi, in quanto in nessun altro modo rigoroso di costruzione formale di a. è stato possibile creare a. non calcolabili mediante una funzione ricorsiva generale.

Informatica

In informatica si definisce a. una sequenza finita di operazioni elementari, eseguibili facilmente da un elaboratore che, a partire da un insieme di dati I (input), produce un altro insieme di dati O (output) che soddisfano un preassegnato insieme di requisiti. Spesso i requisiti vengono distinti in due categorie: i vincoli, ossia requisiti che devono essere soddisfatti in ogni caso, e gli obiettivi, ossia requisiti che devono essere soddisfatti il meglio possibile secondo un qualche criterio specificato. Un a. è caratterizzato essenzialmente da due elementi: la complessità computazionale, relativa al numero di operazioni elementari necessarie per produrre l’output (direttamente legato al tempo di calcolo necessario per eseguire l’a.), e l’approssimazione, relativa a quanto vengono soddisfatti gli obiettivi secondo il criterio specificato. Dalla metà degli anni 1980 le tecniche algoritmiche hanno subito notevoli evoluzioni sotto diversi aspetti: una migliore utilizzazione delle crescenti possibilità offerte dai moderni mezzi di elaborazione (in particolare sfruttando in modo adeguato le possibilità di parallelismo, sia attraverso l’esecuzione simultanea di operazioni analoghe, come nell’elaborazione vettoriale, sia attraverso l’uso di opportune reti di elementi di elaborazione, quali, per es., le reti neurali, generalmente calibrate su specifiche applicazioni); l’uso di strutture dati più sofisticate adatte alle particolari classi di problemi trattati; l’uso di euristiche più potenti e flessibili di quelle usate precedentemente (sfruttando a fondo i concetti di ricerca locale con memoria, inserendo spesso alcuni elementi di tipo probabilistico). Gli a. basati su queste nuove tecniche raramente consentono di garantire a priori in modo esatto un assegnato livello di approssimazione, ma consentono in genere di raggiungere soluzioni molto buone, dando in molti casi garanzie a posteriori di tipo statistico.

Vedi anche
informatica Scienza che studia l’elaborazione delle informazioni e le sue applicazioni; più precisamente l’informatica si occupa della rappresentazione, dell’organizzazione e del trattamento automatico della informazione. Il termine informatica deriva dal fr. informatique (composto di INFORMATion e automatIQUE, ... combinatòria combinatòria Termine con cui è anche chiamata l'algebra combinatoria, disciplina che studia, piuttosto che le strutture algebriche classiche (gruppo, anello, corpo, ecc.), le strutture algebriche di tipo più semplice, particolarmente importanti per i calcolatori elettronici, tra le quali i loop, i monoidi, ... applicazione matematica Il concetto di applicazione è una generalizzazione del concetto classico di funzione (➔ corrispondenza). Si parla di applicazione di un insieme P in un insieme Q, quando tra i due si stabilisce una corrispondenza del tipo seguente: a ogni elemento di P corrisponde un ben determinato elemento ... Muḥammad ibn Mūsà al-Khuwārizmī al-Khuwārizmī ‹al kℎuu̯aarìʃmii›, Muḥammad ibn Mūsà. - Matematico, astronomo, geografo e cronografo musulmano (m. metà sec. 9º), vissuto a Baghdād. Sue opere principali sono un rifacimento dell'atlante e della geografia di Tolomeo in base al testo greco, un trattato di algebra che è il più antico esistente ...
Indice
  • 1 Matematica
    • 1.1 Proprietà fondamentali di un algoritmo
    • 1.2 Teorie degli algoritmi
  • 2 Informatica
Categorie
  • PROGRAMMAZIONE E PROGRAMMI in Informatica
  • ALGEBRA in Matematica
Tag
  • MACCHINA DI TURING
  • FUNZIONE RICORSIVA
  • DETERMINISMO
  • INFORMATICA
  • MATEMATICA
Altri risultati per algoritmo
  • linguaggio algoritmico
    Enciclopedia della Matematica (2013)
    linguaggio algoritmico qualunque linguaggio nel quale possa essere espresso un algoritmo. Per esprimere un algoritmo in modo interpretabile ed eseguibile da un automa esecutore occorre utilizzare un → linguaggio di programmazione, cioè un linguaggio che permetta di esprimere dati e istruzioni attraverso ...
  • algoritmo, stabilità di un
    Enciclopedia della Matematica (2013)
    algoritmo, stabilita di un algoritmo, stabilità di un capacità di un algoritmo di fornire in output risultati attendibili quando l’insieme dei dati in input cambia, sia come valori sia come quantità di dati iniziali. Si supponga di dover trovare la soluzione x del problema generale P(x) = d, dove ...
  • algoritmo
    Dizionario di Economia e Finanza (2012)
    Procedimento di calcolo esplicito e descrivibile attraverso un insieme di regole, costituite da sequenze logiche di istruzioni elementari e non ambigue, che conduce a un determinato risultato atteso, attraverso l’applicazione, per un numero finito di volte, di quelle stesse regole.
  • algoritmi
    Enciclopedia dei ragazzi (2005)
    Roberto Levi Istruzioni per far funzionare da sole le macchine Molte attività umane non si possono svolgere senza seguire precise indicazioni. Come le 'istruzioni per l'uso' spiegano il funzionamento di certi elettrodomestici, così un algoritmo fornisce una serie di istruzioni che possono essere eseguite ...
  • algoritmo
    Dizionario delle Scienze Fisiche (1996)
    algoritmo [Der. del lat. mediev. algorithmus o algorismus, dal nome d'origine al-Huwa-rizmī- del matematico arabo Muhammad ibn Mu-sa, del 9° sec.] [ALG] [INF] Qualunque schema o procedimento sistematico di calcolo, quale, per es., l'a. euclideo delle divisioni successive (v. oltre), l'a. algebrico (cioè ...
  • ALGORITMO
    Enciclopedia Italiana (1929)
    Termine matematico derivato da al-Khuwārizmī (v.), soprannome del matematico arabo Muḥammad ibn Mūsà (morto nell'820). Tale termine fu usato nel Medioevo specialmente per indicare i procedimenti di calcolo numerico basati sopra l'uso delle cifre arabe, e attualmente si usa per qualunque schema di calcolo. Quando ...
Mostra altri risultati
Vocabolario
algoritmo
algoritmo (ant. algorismo) s. m. [dal lat. mediev. algorithmus o algorismus, dal nome d’origine, al-Khuwārizmī, del matematico arabo Muḥammad ibn Mūsa del 9° sec. (così chiamato perché nativo di Khwarizm, regione dell’Asia Centrale)]. –...
Pregiudizio algoritmico
pregiudizio algoritmico loc. s.le m. (spec. al pl.) Contenuto etico o ideologico distorto o discriminatorio (per es. verso le fasce più fragili della popolazione) processato dall’algoritmo nella fase di raccolta massiva dei dati e poi generato...
  • Istituto
    • Chi Siamo
    • La nostra storia
  • Magazine
    • Agenda
    • Atlante
    • Il Faro
    • Il Chiasmo
    • Diritto
    • Il Tascabile
    • Le Parole Valgono
    • Lingua italiana
    • WebTv
  • Catalogo
    • Le Opere
    • Bottega Treccani
    • Gli Ebook
    • Le Nostre Sedi
  • Scuola e Formazione
    • Portale Treccani Scuola
    • Formazione Digitale
    • Formazione Master
    • Scuola del Tascabile
  • Libri
    • Vai al portale
  • Arte
    • Vai al portale
  • Treccani Cultura
    • Chi Siamo
    • Come Aderire
    • Progetti
    • Iniziative Cultura
    • Eventi Sala Igea
  • ACQUISTA SU EMPORIUM
    • Arte
    • Cartoleria
    • Design & Alto Artigianato
    • Editoria
    • Idee
    • Marchi e Selezioni
  • Accedi
    • Modifica Profilo
    • Treccani X
  • Ricerca
    • Enciclopedia
    • Vocabolario
    • Sinonimi
    • Biografico
    • Indice Alfabetico

Istituto della Enciclopedia Italiana fondata da Giovanni Treccani S.p.A. © Tutti i diritti riservati

Partita Iva 00892411000

  • facebook
  • twitter
  • youtube
  • instagram
  • Contatti
  • Redazione
  • Termini e Condizioni generali
  • Condizioni di utilizzo dei Servizi
  • Informazioni sui Cookie
  • Trattamento dei dati personali