riduzione polinomiale
Fabrizio Luccio
Nello studio della complessità di algoritmi combinatori l’attenzione è focalizzata sulla classificazione dei problemi come polinomiali o esponenziali. L’esame si [...] f relativa alla coppia P1, P2, si può risolvere P1 trasformando ogni dato X di P1 in un dato f(X) di P2 e applicando l’algoritmo A a f(X). Ne segue che se P2 appartiene a P anche P1 appartiene a P. I problemi ‘più difficili’ in NP sono pertanto così ...
Leggi Tutto
Tecnica
Strumento utilizzato per aprire o chiudere una serratura. Esistono molti tipi di c., anche se la più comune è quella a corpo piatto con scanalature e intagli che si introduce in una fessura praticata [...] sistema hardware e/o software.
In crittografia, la c. è un parametro dell’algoritmo di crittografia ed è su questa che poggia la sicurezza dell’algoritmo stesso.
Musica
Segno convenzionale posto all’inizio del rigo musicale per determinare il nome ...
Leggi Tutto
Simulazione
Luigi Accardi
Mario Lucertini
Una delle maggiori innovazioni concettuali della scienza contemporanea, che coinvolge in ugual misura tutte le discipline scientifiche, è la transizione dalla [...] non trovo un tale y, allora non posso concludere niente e non ho risolto il problema. Questo è un algoritmo Las Vegas.
Un esempio di algoritmo Monte Carlo è invece il seguente: è data una regione A contenuta in un quadrato e si vuole calcolarne la ...
Leggi Tutto
Sistemi disordinati
David Sherrington
I sistemi disordinati possono trovarsi ovunque e apparire con svariate forme e componenti in discipline molto differenti, fra cui la fisica dello stato solido, [...] si introduce un'opportuna ridondanza nei codici trasmessi e ha calcolato la ridondanza minima necessaria. Sebbene il trovare un algoritmo che funzioni in tempi non eccessivamente lunghi, e che raggiunga il limite di Shannon per la ridondanza minima ...
Leggi Tutto
La grande scienza. Sistemi disordinati
David Sherrington
Sistemi disordinati
I sistemi disordinati sono estremamente comuni e appaiono con svariate forme e componenti in discipline molto differenti, [...] anche le porte all'utilizzazione di tecniche della fisica statistica per trovare soluzioni a problemi tipici e sviluppare algoritmi per casi specifici di questo e altri problemi di ottimizzazione. Una di queste tecniche, ormai usuale nella ricerca ...
Leggi Tutto
Pier Luigi Sacco
Il marchio Italia segna il passo
Un folto gruppo di ricercatori dell’Università di Harvard, in partnership con GoogleLabs, l’ufficio Ricerca e Sviluppo di Google, ha sviluppato un nuovo [...] di un insieme di documenti collegati tra loro. Il motore di ricerca messo a punto da Google si basa su questo algoritmo, che ha sfruttato una serie di studi, applicandoli alle ricerche su Internet e sul World Wide Web. Un ruolo importante è ...
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 [...] riuscì così a gettare le basi teoriche del c. quantistico.
Uno dei risultati più importanti del c. quantistico è l'algoritmo di P.W. Shor per la fattorizzazione (decomposizione in fattori primi) di numeri interi: nel 1994 Shor ha infatti dimostrato ...
Leggi Tutto
Fisica
(XV, p. 473; App. II, i, p. 950; III, i, p. 619; IV, i, p. 812; V, ii, p. 246)
Gli argomenti riguardanti la f. sono stati svolti ampiamente, sia nell'Enciclopedia Italiana sia nelle successive [...] di possibili utilizzazioni di alta efficienza molto più vasto di quanto spesso si pensi: uno sforzo nello studio di algoritmi efficaci (che sono spesso meno banali di quelli, forse più intuitivi, destinati a un calcolatore MIMD) è ricompensato da ...
Leggi Tutto
Virtuale, estetica del
Daniela Angelucci
Il termine
L'aggettivo virtuale, dal latino medievale della scolastica virtualis, derivato a sua volta da virtus, ovvero facoltà, potenza, si presenta generalmente [...] più avanzata della cibernetica, ovvero un ambiente costituito dal 'fenomenizzarsi' di una memoria digitale (un algoritmo in sistema binario), in cui sono simulate condizioni di esperienza reale, sperimentabili dal soggetto attraverso appositi ...
Leggi Tutto
L'Eta dei Lumi: matematica. La teoria della musica
Thomas Christensen
La teoria della musica
Nel XVIII sec. la musica non ebbe particolare spicco come oggetto d'indagine scientifica. In effetti la [...] =9). Euler scrisse pagine di tabelle nelle quali analizzava e graduava i vari intervalli e accordi impiegando questo algoritmo. In maniera analoga, egli poteva graduare la rispettiva dolcezza della successione di due accordi qualsiasi. Egli usò anche ...
Leggi Tutto
algoritmo
(ant. algorismo) s. m. [dal lat. mediev. algorithmus o algorismus, dal nome d’origine, al-Khuwārizmī, del matematico arabo Muḥammad ibn Mūsa del 9° sec. (così chiamato perché nativo di Khwarizm, regione dell’Asia Centrale)]. – 1....