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, [...] quale non è, ancora oggi, noto alcun algoritmo polinomiale.
Definiamo certificato di non primalità di un intero (ni, nj), in G₂ esiste un arco (nπ(i), nπ(j)). Il protocollo funziona nel seguente modo:
V sceglie a caso i in {1,2} e una permutazione π ...
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 [...] : il tempo impiegato per una computazione da una macchina di Turing deterministica è maggiorato da una funzionepolinomiale. Un'altra classe rilevante è la NP, definita come la P, ma che ammette anche macchine di Turing non deterministiche. Si ...
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 [...] in termini di linguaggi. Si introduce quindi un preordine in cui L≤pL′, con L⊂∑ e L′⊂∑′, se esiste una funzione calcolabile in tempo polinomiale f:∑→∑′ con la proprietà
[8] w∈L f(w)∈L′.
Con questa definizione, un linguaggio L si dice NP-completo ...
Leggi Tutto
Chimica quantistica
Frank Jensen
La materia è costituita da nuclei atomici e da elettroni che interagendo formano gli atomi e le molecole, i quali a loro volta danno origine alla materia inorganica, [...] , ma è necessario utilizzare metodi numerici. In sostanza, non si può scrivere la funzione d'onda mediante le consuete funzioni matematiche polinomiali, esponenziali e trigonometriche con le quali si potrebbe direttamente calcolare il valore di ψ ...
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, [...] è 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
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