Complessità algoritmica
Fabrizio Luccio
Gli studi di complessità di calcolo si sono sviluppati essenzialmente nella seconda metà del ventesimo secolo. Basati sulla formalizzazione del concetto di algoritmo, [...] da quei valori e la n-pla è quindi accettata. Si noti la forma ricorsiva della procedura - chiamata di SAT(k+1) all'interno di SAT(k) di S, Σ, Π, s′, b, F resta invariato, mentre la funzione di transizione è ora definita come ∂′ da S×Π su 2S×Π×{←,→}. ...
Leggi Tutto
Storia della civiltà europea a cura di Umberto Eco (2014)
La musica nel pensiero pitagorico
Carlo Serra
Il contributo è tratto da Storia della civiltà europea a cura di Umberto Eco, edizione in 75 ebook
L’individuazione matematica delle consonanze, sistematizzata [...] implica che i pesi, nel racconto, abbiano solo la funzione di dare un indice numerico, di indicare i giusti rapporti , ma che va avviandosi verso il piano formale dell’iterazione logica ricorsiva. Il suono si è fatto diagramma, la corda sonora si è ...
Leggi Tutto
definizione
definizione proposizione che descrive, chiaramente e sinteticamente, un ente matematico (algebrico o geometrico) servendosi di termini aventi un significato noto. In logica, si distinguono [...] interno della teoria in cui tale definizione è assunta. La funzione di una definizione quale generatrice di concetti risulta ancor più un particolare tipo di definizione, detto definizione ricorsiva (→ ricorsività), utilizzata in particolare in quel ...
Leggi Tutto
algoritmo
algoritmo procedimento sistematico di calcolo, oggi per lo più destinato a essere eseguito da un automa esecutore quale un computer. Il termine deriva dal nome latinizzato del matematico di [...] n;
• la sequenza delle operazioni da effettuare, descritte da una funzione ƒ(xi), definita su tutti i valori xi in ingresso;
• i primi n termini di tale successione con un algoritmo ricorsivo: l’n-esimo termine della successione è dato dall’ ...
Leggi Tutto
regola ricorsiva
regola ricorsiva regola che, nella propria formulazione, “richiama sé stessa”. Tale richiamo non è tuttavia una sorta di circolo vizioso perché una regola ricorsiva definisce un oggetto [...] delle pile degli argomenti della procedura. Il principio alla base delle regole ricorsive è applicato anche nella definizione di una importante classe di funzioni, le → funzioniricorsive, le quali hanno il ruolo di tradurre in termini formali il ...
Leggi Tutto
Girard
Girard Albert (Saint-Mihiel, Lorena, 1595 - L’Aia 1632) matematico francese. È noto per i suoi lavori in algebra, aritmetica e trigonometria, nell’ambito della quale gli si deve il teorema sui [...] primo le notazioni sin, cos, tan per le funzioni goniometriche e ne fornì delle tavole di valori nel campo complesso). A Girard si devono anche la prima formulazione della definizione ricorsiva della successione di Fibonacci, Fn+2 = Fn+1 + Fn, a ...
Leggi Tutto
polinomi ortogonali
Alfio Quarteroni
Si consideri lo spazio vettoriale ℙn dei polinomi algebrici di grado minore o uguale a n e sia w:(a,b)→ℝ una funzione peso, ovvero una funzione non negativa e assolutamente [...] ortogonali di Legendre così definita:
per k≥0. Essa soddisfa la seguente relazione ricorsiva a tre termini:
per k≥1. Se invece, sempre sull’intervallo [−1, 1] si considera la funzione peso w(x)= =(1−x2)−1/2, si ottiene la famiglia dei polinomi ...
Leggi Tutto
Laguerre, polinomi di
Laguerre, polinomi di espressi come
con α > −1, sono polinomi ortogonali sulla semiretta [0, +∞) rispetto alla funzione peso x αe−x (nel caso generalizzato, nel caso classico [...] peso w(x) = e−x) è:
Per esempio:
Nell’intervallo [−1, 1] e relativamente alla funzione peso w(x) = 1, essi possono essere definiti dalla formula ricorsiva:
con n ≥ 2. Tali polinomi, che sono soluzione dell’equazione differenziale xy″ + (1 − x)y ...
Leggi Tutto
METAMATEMATICA
Alberto Pasquinelli
Aldo Marruccelli
. Il problema della metamatematica. - Come disciplina specifica, la m. deve la propria genesi (e la propria denominazione) a D. Hilbert, il quale [...] , si dimostra che in esso non è neppure rappresentabile la funzione prodotto a • b. Invece il sistema formale P′, ottenuto il nuovo simbolo • e i due assiomi che definiscono ricorsivamente il prodotto, cioè
è sufficiente per la formalizzazione dell' ...
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 [...] , è possibile garantire l'applicabilità del teorema del punto fisso di Knaster-Tarski e individuare la funzione calcolata da un programma ricorsivo come il punto fisso del funzionale associato a tale programma.
L'approccio denotazionale ha il pregio ...
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...
piazza
s. f. [lat. platĕa «via larga, piazza» (dal gr. πλατεῖα, propriam. femm. di πλατύς «largo»); cfr. platea, che risale a una variante lat. platēa con e lunga]. – 1. a. Area libera, più o meno spaziosa, di forma quadrata, rettangolare,...