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 [...] difficoltà dei problemi in NP, nel senso seguente. Un problema P1 si riduce in tempo polinomiale a un problema P2, in formule P1≤PP2, se esiste una funzione f calcolabile in tempo polinomiale tale che X è una soluzione di P1 se e solo se f(X) è una ...
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 [...] 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
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
Previsioni economiche
Giovanni De Cindio
di Giovanni De Cindio
Previsioni economiche
Presupposti storici
La pratica sistematica delle previsioni economiche, cioè dell'attività di previsione avente [...] serie storiche si possono dunque applicare a processi stazionari.
L'interpolazione di una serie storica, anziché con funzionepolinomiale, può essere effettuata ricorrendo a un diverso tipo di modelli: autoregressivi (AR), a media mobile (MA, da ...
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
Il concetto di calcolo costituisce uno dei più importanti fondamenti teorici delle discipline informatiche. Così come nelle discipline meccaniche non si possono comprendere le caratteristiche dei motori [...] c. quantistico tale problema può essere risolto in tempo polinomiale, risultato che non viene ritenuto possibile in un modello se molto semplicistica, dà un'idea intuitiva di come funzioni il c. molecolare. Dopo l'esperimento di Adleman, ulteriori ...
Leggi Tutto
Visione artificiale
Pietro Parodi
(Scuola Internazionale di Studi Superiori Avanzati, Trieste, Italia)
Vincent Torre
(Scuola Internazionale di Studi Superiori Avanzati, Trieste, Italia)
La visione artificiale, [...] , in altri termini, risolvibile in modo efficiente, se e solo se la sua complessità T(n) è una funzione al più polinomiale della dimensione n dei dati di ingresso. Per molti problemi si conoscono solo algoritmi di complessità esponenziale, o comunque ...
Leggi Tutto
La fisica oggi
Vittorio Silvestrini
Folco Scudieri
In base alla prevalente ricerca scientifica svolta nel primo decennio del 21° sec., e all’interesse che le fonti di informazione hanno riservato ai [...] valori, 0 e 1, l’analogo nella teoria quantistica è il qubit, ossia la funzione d’onda di un sistema che possa esistere in due stati, per es. lo computazione quantistica consente di scomporre in tempo polinomiale in fattori primi un numero intero che ...
Leggi Tutto
Matematica: problemi aperti
Claudio Procesi
Prima di parlare dei problemi aperti nella matematica è bene riflettere su quelli che ne hanno segnato la storia passata. Sono infatti proprio questi che [...] in termini di linguaggi. Si introduce quindi un preordine in cui L≤pL′, con L⊂∑ e L′⊂∑′, se esiste una funzione calcolabile in tempo polinomiale f:∑→∑′ con la proprietà
[8] w∈L f(w)∈L′.
Con questa definizione, un linguaggio L si dice NP-completo ...
Leggi Tutto