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
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 [...] prima di tutto che la Nullstellensatz (in forma equivalente) afferma che un sistema f1(x1,…,xn)=0,…,fk(x1,…,xn)=0 di equazionipolinomiali a coefficienti complessi non ha una soluzione fi(ζ1,…,ζn)=0 se e solo se esistono polinomi gi con ∑ki=1gifi=1 ...
Leggi Tutto
Computazionali, metodi
Alfio Quarteroni
I metodi computazionali permettono di risolvere con i computer, nell'ambito delle scienze applicate, problemi complessi formulabili tramite il linguaggio della [...] −HkA). Nel caso in cui F(x)=0 sia un'equazione (o un sistema di equazioni) non lineare, il processo descritto è il paradigma di numerosi
[11] formula
dove vh è una funzione (della sola x) polinomiale su ogni T dello stesso grado di uh, fh(uh) un' ...
Leggi Tutto
Serie storiche, analisi delle
Franco Giusti
Finalità
Una serie storica è un insieme finito cronologicamente ordinato di osservazioni x₁, x₂, x₃,..., xT relative a un carattere X, generalmente equidistanti, [...] capace di annullare stagionalità di periodo 4 o 5 e di rimuovere trend polinomiali fino a quelli cubici - e più recentemente le medie mobili di Henderson. Il miglior modo è di introdurre nell'equazione di regressione uno o più valori ritardati ...
Leggi Tutto
L'Ottocento: matematica. Metodi del calcolo numerico
Dominique Tournès
Metodi del calcolo numerico
Prima del 1870 l'analisi numerica non si era ancora sviluppata come disciplina autonoma; esisteva [...] di errore. Egli studia anche la convergenza del metodo generale delle approssimazioni successive.
Riguardo alle equazionipolinomiali Paolo Ruffini (1804), François-Desiré Budan (1807), William Horner (1819) e Teofilo Holdred (1820) pubblicano ...
Leggi Tutto
Combinatoria
Peter J. Cameron
Secondo alcuni la combinatoria costituisce soltanto una parte della matematica, secondo altri non rappresenta una branca separata dalle altre ma le pervade tutte, poiché [...] è osservabile ed è per questo che le equazioni differenziali danno una buona descrizione dell'Universo. , se una soluzione proposta si può controllare in un numero polinomiale di passi). Il grande problema irrisolto della teoria della complessità ...
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
Nodi e fisica
Louis H. Kauffman
Nel secolo scorso lord Kelvin (William Thomson) ideò la cosiddetta teoria degli atomi vortice in cui gli atomi erano visti come mulinelli nell'etere, che si supponeva [...] natura alquanto diversa. Si tratta di un invariante polinomiale scoperto da Vaughan F.R. Jones: questo invariante come illustrato nella fig. 13. Definiamo ora una matrice R tramite l'equazione:
[10] Rcdab = AMabMcd + AIca Idb
dove Ica denota la ...
Leggi Tutto
La seconda rivoluzione scientifica: matematica e logica. Calcolo delle variazioni
Craig Fraser
Mario Miranda
Calcolo delle variazioni
Tra il 1870 e il 1920 si assiste al consolidamento degli argomenti [...] a)) e (x,y(x)). Dalle proprietà della variazione abbiamo
Tuttavia
e quindi
Dall'ultima equazione possiamo esprimere y′ in termini di x,y e ∂S/∂y. Posto H=−(f−y Se abbiamo un dato al bordo polinomiale, sappiamo infatti risolvere il problema dell ...
Leggi Tutto
Storia della civiltà europea a cura di Umberto Eco (2014)
Giorgio Strano
Il contributo è tratto da Storia della civiltà europea a cura di Umberto Eco, edizione in 75 ebook
Negli anni Trenta del Novecento i logici riescono a dare uno statuto matematico alla [...] impostare il problema della fermata in termini di equazioni diofantee e nel 1970 Jurij V. Matijasevic problema di classe NP è NP-completo se a esso è riducibile in tempo polinomiale ogni altro problema in NP. Se dunque un problema è NP-completo e di ...
Leggi Tutto