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, [...] .
La dimostrazione del teorema 1 è basata su una simulazione del funzionamento della MTND X sulla macchina di Turing Y, ove il tempo di esecuzione cresce esponenzialmente nel passaggio dalla macchina non deterministica a quella deterministica: è ...
Leggi Tutto
Frattali
Luciano Pietronero
La geometria frattale permette di caratterizzare le strutture che godono della proprietà di invarianza di scala. Il termine frattale (dal latino fractus, rotto o frammentato) [...] superiore. Il numero N(L) corrisponde a un volume generalizzato in funzione della scala L scelta.
Un modo spesso utilizzato in fisica per di potenza rispetto, per esempio, a un andamento esponenziale o gaussiano.
Da un punto di vista matematico, ...
Leggi Tutto
L'Eta dei Lumi: matematica. Il calcolo delle variazioni
Ivor Grattan-Guinness
Il calcolo delle variazioni
Il calcolo in una e più variabili
Una volta sviluppata la teoria della differenziazione e integrazione [...] Per esempio, le curve di decadimento esponenziale y=Kexp[−x/(2a)] sono d(fp)/dx è una condizione del primo ordine necessaria per l'ottimalità. Manipolando una funzione dZ con coefficienti differenziali di ordine superiore p, q (uguale a dp/dx), r, ...
Leggi Tutto
circuito
circùito [Der. del lat. circuitus, da circuire "andare intorno", comp. di circum "intorno" e ire "andare"] [ALG] Qualunque curva i cui punti siano in corrispondenza biunivoca con i punti di [...] f/R) exp[-t/(RC)], cioè si ha un impulso di corrente che decade esponenzialmente a zero, con costante di tempo RC, dal valore iniziale f/R; la f-L(di/dt)=Ri, che, integrata, fornisce la funzione i(t). Due soluzioni significative sono le seguenti: (a) ...
Leggi Tutto
tempo
tèmpo [Der. del lat. tempus -oris] [LSF] (a) Successione di istanti, intesa sempre come una estensione illimitata, ma tuttavia capace di essere suddivisa, misurata, e distinta, in ogni sua frazione [...] 5 e. ◆ [LSF] T. di rilassamento: in un generico fenomeno di rilassamento, la costante che compare nell'esponenziale decrescente della funzione descrittiva; ha le dimensioni di un t. ed effettivamente rappresenta l'intervallo di t. nel quale il valore ...
Leggi Tutto
vettore
vettóre [agg. m. e s.m. (per il f. → vettrice) Der. del lat. vector -oris "conducente, portatore", dal part. pass. vectus di vehere "condurre, portare"] [ALG] Ente che permette di descrivere [...] per es., per certi insiemi di matrici, insiemi di funzioni, ecc.) ha condotto a uno studio sempre più astratto delle: IV 751 d. ◆ [PRB] V. coerente o esponenziale: v. distribuzioni di probabilità infinitamente divisibili, teoria delle: II 226 ...
Leggi Tutto
approssimazione
approssimazióne [Der. di approssimare (→ approssimato)] [LSF] (a) Avvicinamento alla descrizione di un fenomeno la quale non sia ottenibile con esattezza per altra via. (b) Il sostituire [...] a. ◆ [ANM] A. delle fasi casuali: metodo per approssimare funzioni con una serie di Fourier i cui termini hanno fasi iniziali casuali fosse generato unicamente da un momento dipolare. ◆ [ANM] A. esponenziale: v. semigruppo: V 169 f. ◆ [FSD] A. ...
Leggi Tutto
ipotesi di Riemann
Matteo Longo
Congettura sulla distribuzione degli zeri nella funzione zeta di Riemann. La funzione zeta di Riemann ζ(s) è la serie L di Dirichlet associata al carattere di Dirichlet [...] banale definito dalla condizione χ(n)=1 per ogni intero n. Esplicitamente, tale funzione è definita dalla serie:
dove nσ indica exp(s log n) e
è l’esponenziale complessa (convergente su tutto il piano complesso); il simbolo n!=(n−1)∙∙∙2∙1 indica ...
Leggi Tutto
riduzione polinomiale
Fabrizio Luccio
Nello studio della complessità di algoritmi combinatori l’attenzione è focalizzata sulla classificazione dei problemi come polinomiali o esponenziali. L’esame si [...] l’esistenza dove non sia dato richiede tempo esponenziale. Si ha P⊆NP. Il meccanismo di è una soluzione di P2. Conoscendo un algoritmo A di soluzione per P2 e la funzione f relativa alla coppia P1, P2, si può risolvere P1 trasformando ogni dato X di ...
Leggi Tutto
serie L di Dirichlet
Matteo Longo
Sia m un numero intero. Un carattere di Dirichlet modulo m è una funzione χ:ℕ→ℂ tale che: (a) χ(1)=1; (b) χ(p+m)=χ(p) per ogni p∈ℕ (si esprime questo fatto dicendo [...] n)). Nella formula precedente si è indicato con exp l’esponenziale complessa, definita per ogni numero complesso z dalla serie valga 1). Sia χ un carattere di Dirichlet modulo m. La funzione L di Dirichlet associata al carattere χ è la serie L(χ ...
Leggi Tutto
esponenziale
agg. e s. m. [der. di esponente]. – 1. Relativo all’esponente, come esponente. a. In matematica, funzione e., quella del tipo y = ax, in cui cioè la variabile indipendente x compare come esponente (per a reale e maggiore di 1...
funzione
funzióne s. f. [dal lat. functio -onis, der. di fungi «adempiere»]. – 1. Attività svolta abitualmente o temporaneamente in vista di un determinato fine, per lo più considerata nel complesso di un sistema sociale, burocratico, ecc....