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 [...] Karp-riducibile in tempo polinomale a un problema di decisione B se dato un caso x del problema A è possibile creare (in tempo polinomiale) un caso f(x) del problema B tale che x ha soluzione positiva se e solo se f(x) ha soluzione positiva. In base ...
Leggi Tutto
problemi NP-completi
Mauro Cappelli
I problemi di decisione possono essere classificati prescindendo dall’algoritmo usato per risolverli. Sono state individuate le classi di problemi P, NP e NP-completi. [...] contiene. 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
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 [...] decisionale ci si propone di verificare una soluzione proposta, lo si può fare in un tempo che è funzione polinomiale (e non esponenziale) di n. Dunque un ipotetico computer ad architettura altamente parallela, in cui ogni unità parallela verifichi ...
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 [...] decisionale ci si propone di verificare una soluzione proposta, lo si può fare in un tempo che è funzione polinomiale (e non esponenziale) di n. Dunque un ipotetico computer ad architettura altamente parallela, in cui ogni unità parallela verifichi ...
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: [...] cui l'algoritmo deve operare; la complessità viene espressa come una funzione f (n). Se f è una funzione polinomiale, il problema viene classificato come trattabile, cioè risolubile in un tempo comunemente accettabile; viceversa, se f è una funzione ...
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 [...] 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 uscita in un ...
Leggi Tutto