complessita computazionale NP
complessità computazionale NP locuzione con cui si indica la complessità di calcolo di un problema di decisione (un problema cioè la cui soluzione può essere soltanto «sì» [...] (correlato alla dimensione del problema): non si decide, quindi, in tempo polinomiale se una particolare istanza del problema (cioè i valori assunti dai parametri che vi compaiono) è affermativa o meno, ma si verifica un’istanza affermativa ...
Leggi Tutto
regola
regola algoritmo o procedura di calcolo per risolvere un particolare problema. Per esempio: regola dei segni (→ Cartesio, regola di) per determinare i segni delle soluzioni reali di una equazione [...] polinomiale sulla base dei suoi coefficienti; regola di Cramer (→ Cramer, metodo di) per risolvere un sistema di equazioni lineari; regola di → Sarrus per il calcolo del determinante di una matrice quadrata di ordine 3; regola della mano destra per ...
Leggi Tutto
lineare
lineare termine che, se riferito alla rappresentazione analitica di un fenomeno, indica la possibilità di formalizzarlo con una espressione di primo grado. Una → ƒunzione lineare è, quindi, una [...] di un processo.
L’aggettivo si riferisce in modo naturale a diversi oggetti matematici in cui sono coinvolte espressioni polinomiali di primo grado e per la cui definizione si rimanda ai singoli lemmi.
□ In algebra elementare si parla, oltre ...
Leggi Tutto
complessita computazionale P
complessità computazionale P locuzione con cui si indica la complessità di calcolo di un problema di decisione (un problema cioè la cui soluzione può essere soltanto «sì» [...] alla dimensione del problema). In sostanza per un problema di complessità computazionale P esiste un algoritmo di soluzione il cui tempo di risoluzione è funzione polinomiale delle dimensioni dei valori in input (→ complessità computazionale). ...
Leggi Tutto
algoritmo quantistico
algoritmo quantìstico locuz. sost. m. – Algoritmo sviluppato secondo la logica della computazione quantistica (v.). Lo studio di a. q. è stato sostanzialmente improntato alla ricerca [...] di metodi di calcolo capaci di risolvere, in tempo polinomiale, problemi che non hanno soluzione polinomiale nel contesto classico. La struttura della meccanica quantistica mette infatti naturalmente a disposizione di chi costruisce l’algoritmo due ...
Leggi Tutto
termine noto
termine noto di un polinomio, è il termine di grado zero, in cui cioè non compaiono indeterminate. Un polinomio che coincide con il proprio termine noto è detto costante. Analogamente, il [...] termine noto di una equazione polinomiale è il termine noto del polinomio stesso e, se esso è uguale a 0 e quindi non compare, l’equazione ammette la soluzione banale nulla. ...
Leggi Tutto
crescita
crescita termine utilizzato in riferimento a una funzione crescente, per indicare qualitativamente la rapidità del suo accrescimento. In particolare, con riferimento al comportamento per x → [...] di crescita lineare quando ƒ(x) è una funzione di primo grado, o, più generalmente, quando ƒ(x) ~ mx per x → +∞; di crescita polinomiale quando ƒ(x) ~ axn (con n > 1, anche non intero) e di crescita esponenziale quando ƒ(x) ~ eλx (m, a, λ > ...
Leggi Tutto
funzione, zero di una
funzione, zero di una valore della variabile indipendente in corrispondenza del quale una data funzione è nulla. Graficamente uno zero di una funzione indica un punto in cui il [...] grafico della funzione interseca l’asse delle ascisse. Per esempio, gli zeri della funzione polinomiale y = x3 − x si ricavano dall’equazione x3 − x = 0 e sono, quindi, x1 = −1, x2 = 0 e x3 = +1. In corrispondenza di tali valori il grafico della ...
Leggi Tutto
Informazione e computazione quantistica: teoria
Mario Rasetti
Al crocevia tra scienza e tecnologia
La nuova disciplina che va sotto il nome di informazione e computazione quantistica si sviluppa al [...] ha un andamento della forma ϕ(ν)≳ν/lnν, ν≫1, e ne segue che con probabilità O(r2lnr), cioè facendo un numero al più polinomiale di tentativi, si può individuare un r′ coincidente con r.
Si prova infine r′ nel suo ruolo, vale a dire: se r′ è pari, si ...
Leggi Tutto
complessità Caratteristica di un sistema (perciò detto complesso), concepito come un aggregato organico e strutturato di parti tra loro interagenti, in base alla quale il comportamento globale del sistema [...] . Dati ora due problemi R e Q si dice che «R si riduce a Q» (e si indica con R ∝ Q), se esiste un algoritmo polinomiale che associa a ogni istanza di R un’istanza di Q in modo tale che la soluzione dell’istanza di Q fornisce la soluzione della ...
Leggi Tutto