algoritmoalgoritmo [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 [...] continue. ◆ [PRB] A. normale: lo stesso che a. di Markov: → Markov, Andrej AndreevicŠ Senior. ◆ [ALG] [FAF] A. ricorsivo: → ricorsivo. ◆ [INF] Teoria degli a.: è una delle basi teoriche dell'informatica, che ha trovato una sistemazione nell'ambito ...
Leggi Tutto
ricorsivoricorsivo [agg. Der. di ricorrere: (→ ricorrente)] [LSF] Sinon. di ricorrente. ◆ [ALG] [INF] Algoritmo, o procedimento o procedura, r.: algoritmo che è formulato con esplicito riferimento a [...] intero positivo n, è r. la procedura: n!=n✄(n-1)!; ...; 5!=5✄4!; ...; 2!=2✄1!; 1!=1; si contrapp. ad algoritmo iterativo (v. fig.). ◆ [ELT] Filtro non r.: v. immagini, elaborazione di: III 167 e. ◆ [ALG] [INF] Funzioni r. primitive: nella teoria ...
Leggi Tutto
ricorsività La proprietà di essere ricorsivo, cioè ricorrente. Teoria della r., o della ricorsione, o computabilità, la disciplina che si occupa di fornire una caratterizzazione matematica del concetto [...] ), cioè delle funzioni n-arie f tali che esiste un algoritmo per computare il valore f(x1, …, xn) per ogni n-pla di numeri naturali (xs, …, xn), dette funzioni ricorsive (o, meno spesso, recorsive). Queste si definiscono a partire da 3 funzioni ...
Leggi Tutto
Scienza indiana: periodo classico. Matematica
Takao Hayashi
Matematica
'Gaṇita' ('matematica')
Prima dell'introduzione e diffusione dell'astrologia oroscopica e dell'astronomia matematica nella società [...] e b=d rispettivamente; nella risoluzione di ax2+bx=c, secondo l'algoritmo fornito da Brahmagupta e altri, si rende necessaria una regola per la del metodo ciclico.
Il cakravāla è un metodo ricorsivo che, con l'ausilio del polverizzatore, fornisce una ...
Leggi Tutto
L'Eta dei Lumi: matematica. I metodi numerici
Peter Schreiber
I metodi numerici
Il XVII sec. è stato in generale un 'secolo geometrico'. A parte alcune considerazioni di carattere puramente numerico, [...] ' che allora si stabilì spinse in secondo piano lo stile numerico-algoritmico del tipo (b), uno stile che aveva caratterizzato la matematica europea e che in molti casi fortunati porta a una formula ricorsiva per le an. In questo modo si ottenevano in ...
Leggi Tutto
Computazione, teoria della
Fabrizio Luccio
La necessità del calcolo, pur riconosciuta dall'uomo in tutte le epoche storiche, ha condotto solo in tempi relativamente recenti a una sistemazione teorica [...] caso il problema P è decidibile, e una MT che lo risolve è detta algoritmo per P. Se L non è ricorsivo il problema è indecidibile e non ammette algoritmo di risoluzione: tra questi problemi dobbiamo però distinguere quelli corrispondenti a linguaggi ...
Leggi Tutto
Simulazione, modelli di
Italo Scardovi
Modelli e simulazioni nella scienza
Secondo l'etimo latino, 'simulare' sta per 'render simile', come vuole la sua derivazione da similis; e tuttavia il verbo ha [...] - in cui non sia riconoscibile alcun algoritmo generatore: è la 'incomprimibilità algoritmica' secondo Kolmogorov e Chaitin; nota una sistema viene scomposto, variabile per variabile, in modo ricorsivo. Di metodi di simulazione nel senso premesso si ...
Leggi Tutto
teoremi di indecidibilità
Silvio Bozzi
In logica matematica, risultati che affermano che una data teoria formalizzata T non è decidibile, vale a dire non ammette un algoritmo in grado di stabilire in [...] se, l’insieme delle relazioni del gruppo è ricorsivamente enumerabile, rendendo così esplicita l’analogia con i Yuri Matijasevic (1968), il quale prova che non esiste un algoritmo in grado di stabilire quando un polinomio a coefficienti interi ha ...
Leggi Tutto
Informatica teorica
Giorgio Ausiello
Con l'espressione informatica teorica ci si riferisce a un complesso di discipline scientifiche aventi per oggetto lo studio formale degli strumenti, dei metodi [...] la semplice relazione di ricorrenza C(n)=2C(n/2)+n, direttamente ricavabile dalla struttura ricorsiva dell'algoritmo. Ricordiamo, per maggiore chiarezza, che il costo di un algoritmo è O(f(n)) se esistono due costanti c ed n′ tali che per ogni ...
Leggi Tutto
La seconda rivoluzione scientifica: matematica e logica. I problemi di Hilbert e la matematica del nuovo secolo
David E. Rowe
I problemi di Hilbert e la matematica del nuovo secolo
Problemi matematici [...] scrisse insieme ad Adolf Hurwitz, nel quale è delineato un procedimento ricorsivo per risolvere le equazioni diofantee omogenee di grado arbitrario e genere zero.
La teoria degli algoritmi, sviluppata da Alonzo Church (1903-1995) e Alan M. Turing ...
Leggi Tutto
ricorsivo
agg. [der. di ricorrere]. – In matematica e in logica matematica, sinon. di ricorrente (nel sign. 3 c); in partic., nella teoria della ricorsività, funzioni r. primitive, quelle che si possono ottenere dalle funzioni iniziali mediante...