Seqüència pseudoaleatòria
Una seqüència pseudoaleatòria, seqüència de pseudosoroll o codi de pseudosoroll és qualsevol grup de seqüències binàries que presenten propietats aleatòries semblades a les del soroll. Les seqüències de pseudosoroll es distingeixen de les seqüències aleatòries veritables que mostren una periodicitat. És a dir, estan formades per una sèrie periòdica de nombres positius i negatius, o bits, de longitud N. A un d'aquests bits d'una seqüència de pseudosoroll se li anomena xip. Per tant, a la velocitat de la seqüència se li diu taxa xip, i se mesura en xips per segon (cps). Una seqüència d'aquest tipus es pot representar de la següent manera:
... aN−1, aN, a1, a₂,..., aN, a1,...
Els codis de pseudosoroll han de satisfer, entre altres, les següents condicions:
- En cada període la quantitat de nombres positius ha de diferir de la quantitat de nombres negatius en exactament un. Així doncs, N és un nombre imparell:
- En cada període la meitat de les seqüències del mateix signe han de tenir longitud 1, una cambra ha de tenir longitud 2, un vuitè ha de tenir longitud 3, i així successivament. A més el nombre de seqüències de nombres positius ha de ser igual al nombre de seqüències de nombres negatius.
- L'autocorrelació d'una seqüència periòdica s'ha de poder descriure mitjançant: on.
Història modifica
La generació de nombres té múltiples usos (principalment en estadística, simuladors i criptografia). Al principi els investigadors que necessitaven seqüències de nombres aleatoris havien de generar-los ells mateixos mitjançant daus, monedes, cartes, etc. o utilitzar taules de nombres aleatoris existents.
El primer intent de dotar als investigadors amb un subministrament de dígits aleatoris va tenir lloc en 1927, quan el Cambridge University Press va publicar una taula de 41.600 dígits desenvolupada per Leonard H. C. Tippet. En 1947 la RAND Corporation va generar una seqüència de nombres a partir d'una simulació electrònica d'una roda de ruleta; els resultats van ser publicats en 1955 sota el títol A Million Random Digits with 100.000 Normal Deviates.
John von Neumann va ser un pioner en la investigació dels generadors de nombres aleatoris implementats en computadores. En 1951, Derrick Henry Lehmer inventà el generador congruencial lineal, utilitzat en un gran nombre de generadors pseudoaleatoris actuals. Amb la proliferació dels ordinadors, els algorismes de generació de nombres pseudoaleatoris van ser reemplaçant les taules de nombres aleatoris, i els generadors de nombres aleatoris "reals" (generadors de nombres aleatoris per maquinari) són utilitzats en molt rares ocasions.
Quasi aleatori modifica
Una variable pseudoaleatòria és una variable que ha estat creada a través d'un procediment determinístic (per norma general un programa d'ordinador o subrutina) el qual té com entrada dígits realment aleatoris. La cadena pseudoaleatòria resultant sol ser més llarga que la cadena aleatòria original, però menys aleatòria, és a dir, amb menys entropia.
Els generadors de nombres pseudoaleatoris són àmpliament utilitzats en camps tals com el modelatge per computadora, estadística, disseny experimental, etc. Algunes d'aquestes seqüències són molt aleatòries per a ser útils en aquestes aplicacions.
Pseudoaleatòria en la complexitat computacional modifica
A les ciències de la computació, una distribució és pseudoaleatòria contra una classe d'adversaris, si cap adversari de la classe pot distingir-la de la distribució uniforme, amb avantatge significatiu.[1]
Aquesta noció de pseudoaleatorietat s'estudia a teoria de la complexitat computacional i té aplicacions en criptografia.
Referències modifica
- ↑ Oded Goldreich. Computational Complexity: A Conceptual Perspective. Cambridge University Press. 2008.
Enllaços externs modifica
- HotBits: Nombres aleatoris genuïns, generats per la desintegració radioactiva (anglès)
- Història dels nombres aleatoris (anglès)
- Ús i creació de nombres aleatoris criptogràfics de qualitat Arxivat 2005-10-23 a Wayback Machine. (anglès)
- A RFC 1750, l'ús de seqüències de nombres pseudo-aleatoris a la criptografia s'analitza en profunditat.
- A The Art of Computer Programming, Volum 2: Seminumerical Algorithms (3a edició) de Donald E. Knuth, 1997. Addison-Wesley Professional, ISBN 0-201-89684-2
- Oded Goldreich, Capítol 8 en el Computational Complexity: A Conceptual Perspective (2008)