Click here to load reader
Upload
ignacio-alan-moreno-alvarez
View
4.627
Download
0
Embed Size (px)
Citation preview
Instituto Tecnológico de Morelia
“José María Morelos y Pavón”
Ingeniería en Sistemas Computacionales
Simulación
Unidad 1
Tarea #1
Ing. José Contreras Navarrete
Equipo:
Ignacio Alan Moreno Alvarez
12 de Febrero del 2013
Números pseudoaleatorios
Introducción: Casi todas las aplicaciones comerciales tienen varios generadores de números pseudoaleatorios que pueden generar un conjunto muy grande de números sin mostrar correlación entre ellos, para ello se utilizan métodos preestablecidos que garantizan esta demanda. Para poder realizar una simulación que incluya variabilidad dentro de sus eventos, es preciso generar una serie de números que sean aleatorios por sí mismos, y que su aleatoriedad se extrapole al modelo de simulación que se está construyendo. En la construcción del modelo los números aleatorios juegan un papel relevante. Unas de las primeras tareas que es necesario llevar a cabo consiste en analizar si los números que se utilizaran para “correr” o ejecutar la simulación son realmente aleatorios o no; por desgracia, precisar lo anterior con absoluta certidumbre resulta muy complicado, ya que para ello se tendría que generar un número infinito de valores que permitan comprobar la existencia de correlaciones entre ellos. Esta actividad sería muy costosa y tardada, volviendo impráctico el uso de la simulación aun con las computadoras más avanzadas.
Tomando en cuenta lo anterior, se puede asegurar, con altos niveles de confiabilidad que el conjunto de números que se utilizarán en la simulación se comportan de manera muy similar a un conjunto de números totalmente aleatorios; por ello es que se les denomina números pseudoaleatorios. Un número pseudoaleatorio es un número U(0,1) producido por un algoritmo matemático.
Propiedades de los números pseudoaleatorios
Es deseable que los números pseudoaleatorios uniformes posean las siguientes características:
1. Uniformemente distribuidos.
2. Estadísticamente independientes.
3. Reproducibles.
4. Periodo largo.
5. Generados mediante un método rápido.
6. Generados mediante un método que no requiera mucha capacidad de almacenamiento de la computadora.
Generar un conjunto de números pseudoaleatorios es una tarea relativamente sencilla, para ello, el lector sólo tiene que diseñar su propio algoritmo de generación. Lo que resulta difícil es diseñar un algoritmo que genere un conjunto de números pseudoaleatorios con periodo de vida suficientemente grande (N) y además pase sin problema las pruebas de uniformidad e independencia, lo cual implica evitar problemas como éstos:
· Que los números del conjunto no estén uniformemente distribuidos, es decir, que haya demasiados números en un subintervalo y otro muy pocos o ninguno.
· Que los números pseudoaleatorios sean discretos en lugar de continuos.
· Que la media del conjunto sea muy alta o muy baja, es decir, que esté por arriba o por debajo de ½.
· Que la varianza del conjunto sea muy alta o muy baja, es decir, que se localice por arriba o por debajo de 1/12.
En ocasiones se presentan también anomalías como números pseudoaleatorios seguidos por arriba o por debajo de la media; secuencia de números por arriba de la media, seguida por una secuencia por debajo de la media, y viceversa, o varios números seguidos en forma ascendente o descendente. Existen varios métodos para generar números pseudoaleatorios. A continuación se presentan los más importantes.
El Método de Centros al Cuadrado (Método de los cuadrados medios) Este método es debido a von Neumann y tiene fundamentalmente sólo interés histórico. El método de centros al cuadrado se apega a la siguiente metodología:
1. Inicie con un número entero positivo de 4 (2n) dígitos y llámele Z0 (X0), llamado semilla.
2. Eleve Z0 (X0) al cuadrado para obtener un número de 8 (4n) dígitos. Si es necesario, agregue ceros a la izquierda para hacerlo exactamente de 8 dígitos.
3. Tome los 4 (2n) dígitos centrales como el próximo número de 4 (2n) dígitos y llámele Z1(X1).
4. Coloque el punto decimal a la izquierda de Z1(X1) para obtener el primer número pseudoaleatorioU(0,1).
5. Continué generando de esta forma números pseudoaleatorios U(0,1)
Desventaja del método de centros al cuadrado: Tiene una fuerte tendencia a
degenerar rápidamente hacia cero, donde permanecerá por siempre.
La gran mayoría de los generadores de números pseudoaleatorios que se usan en la actualidad son generadores congruenciales lineales, introducidos por Lehmer en 1951. Los generadores congruenciales lineales generan una secuencia de números pseudoaleatorios en la cual el próximo número pseudoaleatorio es determinado a partir del último número generado. A continuación se presentan los dos más importantes: el método congruencial mixto lineal y el método congruencial multiplicativo lineal.
Método de Lehmer
El método consiste en los siguientes pasos: 1. Se toma como semilla un número entero, X0, de n cifras.
2. Se elige otro entero, c, de k cifras. Suele tomarse k<n.
3. Se calcula X0 *c, número de a lo sumo, n + k cifras.
4. Se separan las k cifras de la izquierda de X0*c y al número formado por las n cifras restantes se le resta el que se forma de esas k cifras de la izquierda, dando lugar a X1.
5. Se repite este proceso tantas veces como sea necesario.
6. Se devuelven los valores
Método Congruencial Mixto Lineal Los valores posibles de Xn+1 son 0, 1, 2,3,…, m-1, m representa el número posible de valores que pueden ser generados.
Fórmula:
Donde: Xn= la semilla (X0>0) a= el multiplicador (a>0) c= constante aditiva (c>0) m= Módulo (m>Xn; m>a; m>c)
Periodo del generador = 4
Reglas para la selección de parámetros en el método congruencial mixto lineal En los ejemplos anteriores se colocaron de manera arbitraria cada uno de los parámetros requeridos: X0, a, c, m. Sin embargo, para que el algoritmo sea capaz de lograr el máximo periodo de vida n, es preciso que dichos parámetros cumplan ciertas condiciones. Banks, Carson, Nelson y Nicol sugieren lo siguiente: m= 2g a= 1 + 4k k debe ser entero c relativamente primo a m g debe ser entero Bajo estas condiciones se obtiene un periodo de vida máximo: N= m= 2g.
El Método Congruencial multiplicativo
Al igual que el generador congruencial mixto lineal, el generador congruencial
multiplicativo determina el próximo número pseudoaleatorio a partir del último
número generado, de acuerdo a la siguiente fórmula:
Fórmula:
http://simulacion-itstb.blogspot.mx/p/unidad-dos-numeros-aleatorios-y.html
Un número pseudo-aleatorioes un número generado en un proceso que
parece producir números al azar, pero no lo hace realmente. Las secuencias de
números pseudo-aleatorios no muestran ningún patrón o regularidad aparente
desde un punto de vista estadístico, a pesar de haber sido generadas por un
algoritmo completamente determinista, en el que las mismas condiciones
iniciales producen siempre el mismo resultado.
Los mecanismos de generación de números aleatorios que se utilizan en la
mayoría de los sistemas informáticos son en realidad procesos pseudo-
aleatorios.
Una de las utilidades principales de los números pseudoaleatorios se lleva a
cabo en el llamado método de Monte Carlo, con múltiples utilidades, por
ejemplo para hallar áreas / volúmenes encerradas en una gráfica y cuyas
integrales son muy difíciles de hallar o irresolubles; mediante la generación de
puntos basados en estos números, podemos hacer una buena aproximación de
la superficie /volumen total, encerrándolo en un cuadrado / cubo , aunque no lo
suficientemente buena. Asimismo, también destacan en el campo de la
Criptografía. Por ello se sigue investigando en la generación de dichos
números, empleando por ejemplo medidores de ruido blanco o analizadores
atmosféricos, ya que experimentalmente se ha comprobado que tienen una
aleatoreidad bastante alta.
- Utilizando tablas de números aleatorios.
- Utilizando calculadoras (algunas incluyen una función para generarlos).
- Los lenguajes de programación y las hojas electrónicas incluyen una función
para generarlos.
-Utilizando Generadores Congruencia les.
El método a utilizar, en sí mismo, no tiene importancia: la importancia radica en
los números que genera, ya que estos números deben cumplir ciertas
características para que sean validos. Dichas características son:
1. Uniformemente distribuidos.
2. Estadísticamente independientes.
3. Su media debe ser estadísticamente igual a 1/2.
4. Su varianza debe ser estadísticamente igual a 1/12.
5. Su periodo o ciclo de vida debe ser largo.
6. Deben ser generados a través de un método rápido.
7. Generados a través de un método que no requiera mucha capacidad de
almacenamiento de la computadora.
METODOS PARA GENERAR NUMEROS ALEATORIOS NO UNIFORMES
En los modelos estocásticos existirán una o más variable aleatorias
interactuando. Estas variables siguen distribuciones de probabilidad teóricas o
empíricas, diferentes a la distribución uniforme (0–1). Para generar números
que sigan el comportamiento de éstas variables, se pueden utilizar algunos
métodos como los siguientes:
1. Método de la transformada inversa
2. Método de rechazo
3. Método de composición
4. Procedimientos especiales
MÉTODO DE LA TRANSFORMADA INVERSA.
El método de la transformada inversa utiliza la distribución acumulada F(x) de
la distribución que se va a simular. Puesto que F(x) esta definida en el intervalo
(0–1), se puede generar un número aleatorio uniforme R y tratar de determinar
el valor de la variable aleatoria para cual su distribución acumulada es igual a
R, es decir, el valor simulado de la variable aleatoria que sigue un distribución
de probabilidad f(x), se determina al resolver la siguiente ecuación.
F(x) = R ó x = F^−1 ®
La dificultad principal de este método descansa en el hecho de que en algunas
ocasiones es difícil encontrar la transformada inversa. Sin embargo si esta
función inversa ya ha sido establecida, generando números aleatorios
uniformes se podrán obtener valores de la variable aleatoria que sigan la
distribución de probabilidad deseada.
UN METODO SENCILLO PARA GENERAR NUMEROS
PSEUDOALEATORIOS ES EL DE NEUMANN
1. ELEGIR UN NUMERO INICIAL DE 10 CIFRAS.
2. ELEVARLO AL CUADRADO
3. ELEGIR LOS CINCO CENTRALES.
X0=(1234567890)^2
X0=1524157875019052100
X0=87501
X1=(87501)^2……….
http://mx.answers.yahoo.com/question/index?qid=20090403130637AAbEz8a