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 [...] una prima classificazione degli algoritmi. Una prima possibilità è che τ(L) sia una funzionepolinomiale di L o sia limitata superiormente da una funzionepolinomiale in L. Una seconda possibilità è che non esista nessun polinomio in L di grado ...
Leggi Tutto
INFORMAZIONE, SCIENZA DELLA
Roman Tirler
Pierluigi Ridolfi
Stefano Ceri e Alfonso Fuggetta
Tecnologie della comunicazione di Roman Tirler
Sommario: 1. Introduzione. 2. Tecniche di comunicazione dati: [...] insieme dei valori su cui l'algoritmo deve operare; la complessità viene espressa come una funzione f (n). Se f è una funzionepolinomiale, il problema viene classificato come trattabile, cioè risolubile in un tempo comunemente accettabile; viceversa ...
Leggi Tutto
Computer science
Scott Kirkpatrick
La computer science si colloca con caratteristiche peculiari tra le scienze cosiddette esatte e l’ingegneria, costituendo dal punto di vista accademico un settore [...] problema decisionale ci si propone di verificare una soluzione proposta, lo si può fare in un tempo che è funzionepolinomiale (e non esponenziale) di n. Dunque un ipotetico computer ad architettura altamente parallela, in cui ogni unità parallela ...
Leggi Tutto
La grande scienza. Computer science
Scott Kirkpatrick
Computer science
La computer science si colloca con caratteristiche peculiari tra le scienze cosiddette esatte e dell'ingegneria, costituendo dal [...] problema decisionale ci si propone di verificare una soluzione proposta, lo si può fare in un tempo che è funzionepolinomiale (e non esponenziale) di n. Dunque un ipotetico computer ad architettura altamente parallela, in cui ogni unità parallela ...
Leggi Tutto
La grande scienza. Automi e linguaggi formali
Dominique Perrin
Automi e linguaggi formali
La teoria degli automi e dei linguaggi formali ha lo scopo di descrivere le proprietà delle successioni di simboli. [...] : il tempo impiegato per una computazione da una macchina di Turing deterministica è maggiorato da una funzionepolinomiale. Un'altra classe importante è la classe NP: è definita come la P, ma ammette però anche macchine di Turing non deterministiche ...
Leggi Tutto
Automi e linguaggi formali
Dominique Perrin
La teoria degli automi e dei linguaggi formali ha lo scopo di descrivere le proprietà delle successioni di simboli. Tali successioni si presentano in situazioni [...] : il tempo impiegato per una computazione da una macchina di Turing deterministica è maggiorato da una funzionepolinomiale. Un'altra classe rilevante è la NP, definita come la P, ma che ammette anche macchine di Turing non deterministiche. Si ...
Leggi Tutto
Insieme di linee, reali o ideali, che si intrecciano formando incroci e nodi e dando luogo a una struttura complessa. Più in particolare, infrastruttura tecnica per la distribuzione di un segnale (tipicamente [...] tensione o la corrente sono vincolate a seguire rispettivamente le due funzioni prefissate vg(t) e ig(t), che vengono indicate con si è passati da complessità esponenziale in n a complessità polinomiale inferiore al terzo grado in n, con n numero di ...
Leggi Tutto
Dispositivo che permette di modificare determinate componenti o caratteristiche di un segnale sonoro, luminoso o elettrico.
Apparecchiatura attraverso la quale si fa passare un fluido allo scopo di trattenere [...] . La risposta impulsiva risulta di durata infinita. F. trasversali F. numerici non ricorsivi in cui la funzione di trasferimento è di tipo polinomiale. Sono comunemente indicati con la sigla FIR (finite impulse response). In tali f. il campione di ...
Leggi Tutto
Informatica
Giorgio Ausiello
Carlo Batini
Vittorio Frosini
(App. IV, ii, p. 189; V, ii, p. 704)
Mentre negli anni 1937-38 venivano pubblicati l'ultimo volume della Enciclopedia Italiana e l'App. I, [...] quale non è, ancora oggi, noto alcun algoritmo polinomiale.
Definiamo certificato di non primalità di un intero (ni, nj), in G₂ esiste un arco (nπ(i), nπ(j)). Il protocollo funziona nel seguente modo:
V sceglie a caso i in {1,2} e una permutazione π ...
Leggi Tutto