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, [...] è la riduzione: presi due problemi P1, P2 e i relativi linguaggi L1, L2 , una riduzione polinomiale da P1 a P2 è una funzione f da Σ* su Σ* tale che: 1) esiste un algoritmo polinomiale deterministico F che calcola f; 2) per ogni v∈Σ*, si ha v∈L1 se e ...
Leggi Tutto
La seconda rivoluzione scientifica: matematica e logica. Problemi di analisi complessa alla fine dell'Ottocento
Jeremy Gray
Problemi di analisi complessa alla fine dell'Ottocento
La teoria generale [...] delimitata da un semicerchio e da due rette verticali. Utilizzando questa funzione Dedekind fu in grado di sviluppare una teoria quasi completa per ogni teoria geometrica delle soluzioni delle equazioni polinomiali si colloca in modo naturale fra i ...
Leggi Tutto
La seconda rivoluzione scientifica: matematica e logica. Equazioni differenziali ordinarie
Jean Mawhin
Equazioni differenziali ordinarie
Accanto a sostanziali progressi nella teoria delle equazioni [...] b)=0,
viene così estesa alla [21] per la classe di funzioni f che soddisfano una condizione del tipo [25].
Lo studio del approccio piuttosto indiretto. Se (pk) è una successione di approssimazioni polinomiali di f su un dato compatto, e se xk(t;c) ...
Leggi Tutto
L'Ottocento: matematica. Teoria degli invarianti
Leo Corry
Teoria degli invarianti
L'algebra del XIX sec. ebbe uno sviluppo intenso che coprì numerosi domini. Nuove entità matematiche come gruppi, anelli [...] y1 e y2, T(f)=F(y1,y2) con coefficienti bi che sono funzioni razionali, lineari nelle ai e di grado n nelle aij. Un'espressione algebrica n un terzo invariante per questa forma è una combinazione polinomiale dei due precedenti: z=u3+27v2.
Cayley e ...
Leggi Tutto
Campi di numeri
Massimo Bertolini
Sia α un numero algebrico, cioè un numero complesso che soddisfa un’equazione algebrica p(x)=0, dove p(x) è un polinomio
di grado n≥1 avente coefficienti nel campo [...] ζm] è l’anello ℤ[ζm], contenente tutte le espressioni polinomiali in ζm a coefficienti in ℤ. In particolare, se K K, moltiplicati per mezzo dell’operazione di composizione (un automorfismo di K è una funzione σ:K→K tale che σ(a+b)=σ(a)+σ(b) e σ(ab ...
Leggi Tutto
In matematica applicata, e in particolare nella teoria delle decisioni, problemi di o., le questioni attinenti alla ricerca dei criteri di scelta tra diverse opzioni o di determinazione del valore di particolari [...] sono iterativi. Se il problema consiste nella ricerca di un minimo locale di una funzione F(x) di n variabili x1, x2, …, xn, tali metodi si fondano riguarda la complessità, i modelli lineari sono generalmente polinomiali (lo è per es. il metodo degli ...
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 [...] 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 versione quantistica del bit. Lo stato di un qubit è espresso dalla funzione ∣ψ>=α∣0>+β∣1> in cui le ampiezze ...
Leggi Tutto
Modelli, Teoria dei
Silvio Bozzi
Malgrado le modeste origini che ne hanno segnato la nascita, la teoria dei modelli ha sviluppato nel corso del tempo idee e metodi che l'hanno resa uno dei settori più [...] Nel caso di insiemi, basterà considerare n=1 e per funzioni prendere il grafo come relazione n+1-aria. Diremo poi che catene di campi finiti - Ax prova così che ogni mappa polinomiale da una varietà affine (definita su un campo algebricamente chiuso) ...
Leggi Tutto
La seconda rivoluzione scientifica: matematica e logica. L'analisi numerica
Paolo Zellini
L'analisi numerica
L'analisi numerica moderna comincia a delinearsi verso la metà del XX sec., con le prime [...] di risoluzione numerica. Successivamente sono state usate, invece di funzioni lineari a tratti, funzioni regolari, polinomiali a tratti, in particolare funzioni spline. Sia le funzioni spline sia i metodi di tipo variazionale devono la loro ...
Leggi Tutto
approssimato
approssimato [agg. Der. del part. pass. approximatus del lat. approximare "avvicinarsi a", comp. di ad- e proximus "prossimo"] [LSF] Che riguarda o che deriva da un'approssimazione. ◆ [ANM] [...] [ANM] Formule a.: locuz. con cui s'indicano semplici espressioni polinomiali che, ove si accetti un determinato grado di approssimazione, possono essere sostituite a determinate funzioni per renderne molto più agevole il calcolo dei valori. Nella tab ...
Leggi Tutto