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 [...] 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 può essere descritto, in termini di legami ingresso-uscita, dalle equazioni
dove A è una matrice, B è un vettore colonna e ...
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 [...] cui il principio di indeterminazione di Heisenberg e l'equazione di Schrödinger. Lo sviluppo di una macchina di di c. quantistico tale problema può essere risolto in tempo polinomiale, risultato che non viene ritenuto possibile in un modello di c ...
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 [...] corretta di istruzioni macchina per un algoritmo espresso in forma di un’equazione o di una formula. In effetti, è molto più facile scrivere lo si può fare in un tempo che è funzione polinomiale (e non esponenziale) di n. Dunque un ipotetico computer ...
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 [...] corretta di istruzioni macchina per un algoritmo espresso in forma di un'equazione o di una formula. In effetti, è molto più facile scrivere lo si può fare in un tempo che è funzione polinomiale (e non esponenziale) di n. Dunque un ipotetico computer ...
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, [...] faccia.f3; perciò, esso è dietro la faccia f1, e vale l'equazione a1x4+b1y4+z4+c1 > 0. Se in base all'etichettatura è possibile appartenente a C si può trasformare in X con complessità polinomiale. In altri termini, nessun problema in C è 'più ...
Leggi Tutto
Perceptron: passato e presente
Gérard Dreyfus Léon Personnaz
(Laboratoire d'Électronique, École Supérieure de Physique et de Chimie lndustrielles, Parigi, Francia)
Gérard Toulouse
(Laboratoire de Physique, [...] non lineari Φi sono monomi, cosicché il modello risulta polinomiale. Il vantaggio principale di tale modello è il fatto di tempo. Tali modelli (modelli input-output) sono quindi descritti da equazioni alle differenze finite del tipo
y(k) = ϕ[y(k-l), ...
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. [...] ogni problema in NP si può ridurre a questo in un tempo polinomiale. Ovviamente P⊂NP; è ragionevole supporre che P≠NP, ma una parola su A per ciascuna delle incognite x∈X. Per esempio, l'equazione ax=yb ha la soluzione x=b, y=a. Gennady S. Makanin ha ...
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 [...] ogni problema in NP si può ridurre a questo in un tempo polinomiale. Ovviamente P⊂NP; è ragionevole supporre che P≠NP, ma una parola su A per ciascuna delle incognite x∈X. Per esempio, l'equazione ax=yb ha la soluzione x=b, y=a. Gennady S. Makanin ha ...
Leggi Tutto
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, [...] P1 si riduce a P2, e si indica con P1⇒P2. Si noti che la riduzione polinomiale è transitiva, cioè P1⇒P2 e P2⇒P3 implicano P1⇒P3.
Se P1⇒P2, un una o più dimensioni e di risoluzione intera di equazioni. Se si passa a una più generale forma risolvente ...
Leggi Tutto