equazione algebrica
equazione algebrica equazione che, eventualmente dopo opportune trasformazioni che utilizzano le proprietà dei numeri reali, assume forma polinomiale, cioè del tipo p(x1, …, xn) = [...] una o più variabili, oppure assume la forma di uno o più sistemi misti in cui compaiono equazioni in forma polinomiale.
Una equazione algebrica è detta intera se nessuna delle incognite compare mai al denominatore delle espressioni algebriche che la ...
Leggi Tutto
polinomio osculatore
polinomio osculatore o polinomio interpolatore di Hermite, in analisi, polinomio che si ottiene effettuando una interpolazione per punti polinomiale che considera non soltanto la [...] di dati (x0, y0), …, (xn, yn), con xi ≠ xj, che costituiscono i poli, ma anche i valori della derivata yi′ nei punti, per i = 0, …, n, ottenendo in tal modo una funzione polinomiale che meglio approssima l’andamento dei dati (→ interpolazione). ...
Leggi Tutto
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 P e NP
problemi P e NP classi di problemi costituite sulla base della loro → complessità computazionale, cioè della intrinseca difficoltà della loro risoluzione. Un problema appartiene alla [...] se l’esponente α ha un valore sufficientemente piccolo. È evidente, per esempio, che un algoritmo di complessità O(n13) è polinomiale, ma prevede comunque un costo in termini di tempo di calcolo non trascurabile. Un problema appartiene alla classe 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, [...] un numero composto o è un numero primo (test di primalità), un problema per il quale non è, ancora oggi, noto alcun algoritmo polinomiale.
Definiamo certificato di non primalità di un intero n un altro intero m, con 1〈m〈n, dotato di proprietà tali da ...
Leggi Tutto
differenze finite
differenze finite particolare sequenza di operazioni utilizzate soprattutto nei metodi numerici di calcolo approssimato, come la derivazione e l’interpolazione polinomiale. Sia dato [...] è h, la relazione tra le differenze divise e le differenze finite è tale che per ogni n:
I metodi di interpolazione polinomiale, come il metodo di → Newton e il metodo di → Lagrange, nei quali si approssima l’andamento locale di una funzione ƒ(x ...
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, [...] ∈L1 se e solo se f(v)∈L2. Si dice allora che 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 algoritmo A2 per risolvere P2 può essere usato per risolvere P1 ...
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
identita, principio di
identità, principio di (per polinomi) stabilisce che due polinomi a coefficienti in un anello A sono identici quando definiscono la stessa funzione polinomiale. Due polinomi a [...] coefficienti reali in una indeterminata x sono identici se e solo se hanno rispettivamente uguali i coefficienti di xi, per ogni i. Tale principio rimane vero anche in Z[x], Q[x], C[x] e in ogni anello ...
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, [...] problema X si dice completo per una classe C se ogni problema appartenente a C si può trasformare in X con complessità polinomiale. In altri termini, nessun problema in C è 'più difficile' di X. Se esiste un algoritrno che risolve X con complessità O ...
Leggi Tutto