7789 Simulacionnumeropiszc-soto (1)

SIMULACION DE SISTEMAS DE INFORMACION __________________________________________

_____________________________________________________________________________________1

INTRODUCCION HISTORIA Y CURIOSIDADES DEL NUMERO Pi

Cualquier esfuerzo prctico por dividir el dimetro de un crculo en su propia circunferencia solo puede resultar en fracaso. Tal procedimiento slo puede ser terico en su naturaleza, e intentar obtener su valor "racional" solo conllevar a frustracin. La frustracin que se retrata a lo largo de la historia en el esfuerzo de la humanidad por medir lo inconmensurable. Intentar inscribir una lnea recta (el dimetro de un crculo) en otra lnea curva (el permetro del mismo) es intentar una alteracin a la naturaleza, una alteracin imposible que siquiera los ordenadores modernos estn en condiciones de realizar.

Ya en la antigedad, los calculistas advirtieron que todos los crculos conservaban una estrecha relacin entre su permetro y su radio pero... Puede este vnculo ser considerado como un nmero "racional"? Es decir: Puede conocerse con exactitud esta relacin, o debemos limitarnos a dar aproximaciones? Slo desde el siglo XVII la relacin se convirti en un nmero y fu identificado con el nombre "Pi" (de periphereia, nombre que los griegos daban al permetro de un crculo), pero largo fu el camino hasta aceptar que era un irracional, como infinita es la posibilidad de encontrarle un nuevo decimal.

A lo largo de la historia, la expresin de ha asumido muchas variaciones. Uno de los mas antiguos textos matemticos, el papiro de Rhind, (1700 aos antes de nuestra era) nos muestra al escriba Ahms cotejando la evaluacin del area de un crculo inscrito en un cuadrado.

La biblia le asigna el valor 3, en Babilonia 3 1/8; los egipcios 4(8/9); Siddhantas 3,1416; Brahmagupta 3,162277; y en China 3,1724. Sin embargo, como era de esperarse, fue en Grecia donde la exacta relacin entre el dimetro y el permetro de una circunferencia comenz a consolidarse como uno de los mas llamativos enigmas a resolver. Un contemporneo de Scrates, Antiphon, inscribe en el crculo un cuadrado, luego un octgono e imagina doblar el nmero de lados hasta el momento en que el polgono obtenido coincida prcticamente con el crculo. Brisn, por la misma poca, hizo intervenir los polgonos circunscriptos.

Despus de los trabajos de Hipcrates y de Euxodo, Euclides precisa, en sus Elementos los pasos al lmite necesarios y desarrolla el mtodo de exhaucin, consistente en doblar, al igual que Antiphon, el nmero de lados de los polgonos regulares inscritos y circunscritos y en mostrar la convergencia del procedimiento.

Arqumedes rene y desarrolla estos resultados. Muestra que el rea de un crculo es el semiproducto de su radio por su circunferencia y que la relacin de la circunferencia al dimetro est comprendida entre 223/71 = 3,14084 y 22/7 = 3,14285.

Obtiene luego para las reas y los permetros de los polgonos regulares, inscritos y circunscritos, de n y 2n lados, relaciones de recurrencia de forma notable, que permiten


_____________________________________________________________________________________2

calcular pi con una aproximacin dada; este mtodo de clculo recibi el nombre de "algoritmo de Arqumedes".

Con el renacimiento, los trabajos de ciclometra se multiplican. Purbach construye una tabla de senos de 10' en 10' y adopta para Pi el valor 377/120 = 3,14666.... Los siglos XV y XVI se destacan por el desarrollo de la trigonometra, bajo el impulso de Coprnico y Kepler. Rhaeticus construye una tabla de senos en la que se incluye a Pi con 8 decimales exactos. Adrien Romain (1561-1615) obtiene 15 decimales y Ludolph de Colonia (1539-1610) llega hasta 32. Segn su deseo, estos 32 decimales fueron grabados en su tumba, pero en su pas la posteridad lo recompens mucho mejor pues se dio a pi el nombre de "nmero de Ludolph".

Pronto la proeza de Ludolph se vi opacada por lo perfeccionamientos logrados por

Snell (1580-1626) y Huyghens (1629-1655). El primero halla que el arco x est comprendido entre: 3 sen x /( 2 + cos x) y 1/3.(2 sen x + tg x) mientras que el segundo, cuya obra ha sido calificada como modelo de razonamiento geomtrico, da la expresin (sen x tg x)1/3 Con su mtodo, Snell obtuvo 34 decimales exactos, partiendo del cuadrado y doblando 28 veces el nmero de los lados. Huyghens, en cambio, calcula Pi con 9 decimales exactos utilizando simplemente el polgono de seis lados.

El clculo infinitesimal di frmulas notables que, al aportar mtodos de clculo nuevos y mucho mas potentes, separ en cierto modo a Pi de sus origenes geomtricos y aclar el papel fundamental que que juega en todo el anlisis matemtico. El matemtico francs Viete obtuvo, a fines del siglo XVI, la primer frmula de por medio de un producto infinito convergente que no hace figurar mas que a los nmero 1 y 2. Gregory en 1670 desarrolla la frmula del Arco tangente que, para x = 1 da la frmula de Leibniz: /4 = 1 - (1/3) + (1/5) -...

Como caso particular, cabe mencional a Euler, a quien le debemos la costumbre de designar por Pi a la relacin circunferencia : dimetro y quien en 1775 calcul su valor, con 20 decimales, en una hora por medio de la frmula:

/ 4 = 5 arc tg 1/7 + 8 arc tg 3/79.

Sin embargo, su mayor descubrimiento es el de un cierto parentesco entre y otros nmeros no menos importantes en la matemtica, como lo son el nmero e, i, como as los lazos que existen entre las funciones circulares seno y coseno, y la funcin exponencial ex : sta es peridica y su perodo imaginario es 2 i .

Estas verdades son el resultado comn de varias corrientes de ideas. Los logaritmos inventados por el escocs Neper (1550-1617), no solamente tuvieron gran importancia para los clculos numricos; la funcin, nula para x = 1, que admite como derivada a 1/x ofrece un sistema de logaritmos particularmente interesantes desde el punto de vista terico: los conocidos logaritmos neperianos.

El mas constante entre todos aquellos que se abocaron al cmputo de fue el matemtico ingls William Shanks, quien luego de un arduo trabajo que le demand nada


_____________________________________________________________________________________3

menos que veinte aos, obtuvo 707 decimales en 1853. Desafortunadamente, Shanks cometi un error en el 528 decimal, y apartir de se todos los restantes estn mal. En 1949 John Von Neumann utiliz la computadora electrnica ENIAC, y luego de setenta horas de trabajo obtuvo 2037 cifras decimales. Tiempo despus, otra computadora consigui 3.000 decimales en slo 13 minutos. Hacia 1959, una computadora britnica y otra gala lograron las primeras 10.000 cifras. En 1986 David H. Bailey extrajo 29.360.000 cifras en un Cray-2 de la Nasa utilizando el algoritmo de Ramanujan de convergencia curtica. Finalmente, en 1987, Kanada consigui mas de 100 millones de cifras se podran conseguir facilmente 2.000 millones de cifras usando en exclusiva un superordenador durante una semana. En resumen, ya es prcticamente posible tantas cifras como se requiera, y el nico impedimento aparente es debido al tiempo que un ordenador pueda tardar en conseguirlos.

Lo cierto es que slo cuatro decimales de con suficiente precisin bastan para las necesidades prcticas. Con 16 decimales se obtiene, con el espesor aproximado de un cabello, la longitud de una circunferencia que tenga por radio la distancia media de la tierra al sol. Si reemplazamos el sol por la nebulosa mas lejana y el cabello por el corpsculo mas pequeo conocido por los fsicos, no haran falta mas que 40 decimales. Entonces Que necesidad existe para buscar tantas cifras? Quiz ninguna necesidad prctica, pero el hombre no se resigna an a aceptar cosas que no pueda llegar a comprender, como por ejemplo el infinito. ENUNCIADO DEL PROBLEMA Simular el nmero PI segn el mtodo de Montecarlo SUPUESTOS Y ALCANCES El mtodo de Montecarlo se puede aplicar a una multitud de problemas para encontrar una solucin aproximada a partir de la generacin de nmeros aleatorios. Un ejemplo de aplicacin de este mtodo es la obtencin aproximada del nmero PI. El modelo elegido es un circulo inscrito en un cuadrado (lado = 2 * radio). Al igual que se lanza un dardo sobre una diana, simularemos N puntos elegidos al azar dentro del cuadrado y contaremos cuntos de ellos (M) caen dentro del circulo. La relacin de estos de nmeros, M y N, ser una aproximacin entre las reas del circulo y la del cuadrado, respectivamente N rea_cuadrado (r*2)^2 4 --- = ------------- = -------- = --- M rea_circulo pi * r^2 pi (nota: el smbolo " ^ " significa elevado. Ejm: x^2 significa " x elevado a 2") Por tanto la aproximacin de PI se obtiene multiplicando por 4 la fraccin obtenida por el mtodo de Montecarlo.


_____________________________________________________________________________________4

4 * M Pi = ----- donde M : n aciertos en el crculo N N : n total de lanzamientos


_____________________________________________________________________________________5

DIAGRAMA DE FLUJO

Inicio

Ingreso de Tiradas

N CORRECTO

NO SI

SALIR

NO SI

FIN

EJECUTAR


_____________________________________________________________________________________6

FINFUENTE DEL PROGRAMA DE SIMULACION CODIGO DEL PROGRAMA Private Sub Command1_Click() Dim n As Double Dim x As Double Dim y As Double Dim a As Double Dim j As Double Dim i As Double Randomize n = Val(Text2.Text) If Text2.Text > 10000 Then m = 39 Else m = 21 End If For i = 1 To n x = Rnd y = Rnd If (x * x + y * y)


_____________________________________________________________________________________7

Private Sub Command3_Click() Unload Me End Sub Private Sub Form_Load() Command1.Enabled = False End Sub Private Sub Text2_Change() If Text2.Text "" Then Command1.Enabled = True End If End Sub


_____________________________________________________________________________________8

FUENTE DE GENERADORES DE NUMEROS ALEATORIOS

Los nmeros aleatorios son muy tiles en diferentes tipos de aplicaciones:

a) Simulacin: cuando utilizamos un ordenador para simular fenmenos naturales, los nmeros aleatorios son necesarios para hacer las cosas ms realistas. b) Anlisis numrico: existen una serie de tcnicas para resolver complicados problemas numricos. c) Programacin de ordenadores: los nmeros aleatorios van a servir para probar la efectividad de los diversos algoritmos. d) Toma de decisiones. e) Juegos.

Podemos obtener nmeros aleatorios sirvindonos de distintos mtodos:

a) Tablas de bibliotecas. Libros.

b) Mtodos de computacin analgicos. Se basan en procesos internos del ordenador (alternancia de corriente elctrica). Son

lentos, difciles de mantener y construir. La secuencia de nmeros no es reproducible para el chequeo de programas. c) Mtodos de computacin digital.

Se usar una serie de mtodos algebraicos para generar nmeros aleatorios. Son mtodos simples, rpidos y reproducibles. Estos nmeros parten de un nmero X0 llamado semilla y produce secuencias de la forma:

X1 = f (X0) X2 = f (X1) ... Xi = f (Xi-1)

Puesto que el nmero de dgitos en un ordenador es finito, se podr generar un

nmero finito de nmeros distintos. De esta manera, se obtendr una serie de nmeros que en principio parecen aleatorios y que satisfacen la mayora de los tests de aleatoriedad.

nmeros pseudo-aleatorios o cuasi-aleatorios

Propiedades de un buen generador de nmeros aleatorios 1. Los nmeros han de estar uniformemente distribuidos entre 0 y 1. 2. Los nmeros han de ser estadsticamente independientes. 3. Los nmeros han de ser reproducibles. 4. Las secuencias de nmeros aleatorios han de tener un periodo de repetibilidad largo. 5. Los nmeros han de ser generados de forma rpida y noha de necesitarse una cantidad de memoria demasiado grande.


_____________________________________________________________________________________9

Mtodos para generar nmeros aleatorios 1.- Mtodo de los cuadrados medios

Consiste en que cada nmero de una sucesin es producido tomando los dgitos medios de un nmero obtenido mediante la elevacin al cuadrado.

P1 : Obtener semilla (valores iniciales 445) P2 : Aplicacin de Algoritmos recursivos (elevar al cuadrado) P3 : Validacin del conjunto de datos generados Ejemplo: Consideremos la semilla 445 X X2 N Aleatorio 445 1| 9802 | 5 0,9802 9802 96| 0792 | 04 0,0792 792 6 | 2726 | 4 0,2726 2726 ............... ............... 2.- Generadores congruenciales lineales

La secuencia de nmeros aleatorios se obtiene aplicando la frmula: Xn+1 = ( a Xn + c ) mod M, n 0

A la secuencia obtenida la denominaremos Secuencia Congruencial Lineal.

M, mdulo M > 0 a, multiplicador 0 a < M c, incremento 0 c < M X0, valor de inicio 0 X0 < M

La salida suele ser el nmero Xi/m, un nmero en coma flotante en el intervalo

[0,1). Algunas propiedades de estos generadores: 1. El mdulo m es una cota superior del nmero de valores diferentes que puede tomar la

semilla. 2. Si Xi vuelve a tomar el valor de la semilla inicial la secuencia se repetir cclicamente. 3. Todas las secuencias producidas por este tipo de generador si se prolongan lo suficiente

(periodo) acaban en un ciclo que se repite indefinidamente.

Un buen generador lineal tendr un periodo tan largo como sea posible (es decir m). Este mximo se alcanza si y slo si se cumplen las tres siguientes condiciones:


_____________________________________________________________________________________10

Parmetrosa b m xo6 0 13 17 0 13 105 0 13 57 0 11 56 0 11 3

Caso Salidas1 6 10 8 9 2 12 7 3 5 4 11 1 6 102 5 9 11 12 6 3 8 4 2 1 7 10 5 93 12 8 1 5 12 8 1 5 12 8 1 5 12 84 2 3 10 4 6 9 8 1 7 5 2 3 10 45 7 9 10 5 8 4 2 1 6 3 7 9 10 4

5

Caso1234

a) b es primo con m b) a-1 es mltiplo de p para todo primo p que divida a m c) a-1 es mltiplo de 4 siempre que m sea mltiplo de 4

Habitualmente se toma como m una potencia de 2 ms de 1 de modo que se puede coger por ejemplo b=1 y a un nmero impar. Obs: 1.- Cuando b=0 el generador se denomina Generador congruencial multiplicativo. 2.- Cuando b0 el generador se denomina Generador congruencial mixto. 3.- A pesar de la simplicidad una adecuada eleccin de los parmetros de a, b y m, permite obtener de manera eficiente una larga e impredecible sucesin de nmeros como para considerarse aleatoria. Ejemplo:

3. Generadores congruenciales multiplicativos

Xn+1 = ( a Xn) mod M El mximo periodo 2b-2 se obtiene cuando:

M = 2b, b 4 c = 8k + 5, k = 0, 1, 2, ... X0 es impar

Los generadores multiplicativos son rpidos, simples y fciles de implementar. Hutchinson demostr que el comportamiento del generador mejora cuando M es igual al mayor nmero primo menor que 2b, siendo de este modo P = M 1.


_____________________________________________________________________________________11

4. Otros generadores de nmeros aleatorios a) Generador cuadrtico

Xn+1 = ( d Xn2 + a Xn + c ) mod M

Son ms lentos ( se realizan ms operaciones) b) Generadores de tipo Xn+1 = f (Xn, Xn-1) - Recurrencia de Fibonacci (1950).

Xn+1 = (Xn + Xn-1) mod M En teora se pueden alcanzar periodos de longitud M2. Se ha demostrado que no son buenos.

- Generadores aditivos (1959, Green. Smith, Klem).

a) Xn+1 = (Xn + Xn-k) mod M k fijo y conocemos X0, X1,..., Xk-1

Para que se comporte correctamente, k ha de ser grande. Se demuestra que si k 15, el generador no produce resultados satisfactorios. Si k = 16, el generador ya produce buenos resultados.

b) Xn = (Xn-m + Xn-l) mod M Mitchell y Moore (1957) propusieron:

Xn = (Xn-24 + Xn-55) mod M

Hay que fijar X0, X1,..., X54, es decir 55 semillas Ms rpido que los congruenciales lineales


_____________________________________________________________________________________12

TABLAS Y GRAFICOS


_____________________________________________________________________________________13

MANUAL DE USO DEL PROGRAMA DE SIMULACION Al ejecutar el programa, esta imagen aparece en pantalla

Para comenzar a utilizar el programa, se debe realizar las siguientes operaciones:

Ingresar el n de iteraciones que se desea, si est correcto presionar Generar Tiradas, sino, presionar Borrar

En el cuadro n de tiradas genera las iteraciones En el cuadro valor de pi muestra el valor final al que se llego tras un

cierto n de iteraciones. En el cuadro adyacente se refleja el grfico de las tiradas. Si desea salir del programa slo tiene que presionar el botn salir .


_____________________________________________________________________________________14

ARCHIVO DE SALIDA CON LOS METODOS GENERADORES Valor aproximado del nmero Pi con 2500000 iteraciones 50 3,04 100 3,08 500 3,176 5000 3,1704 10000 3,1648 15000 3,14906666666667 20000 3,1502 25000 3,15056 30000 3,15013333333333 35000 3,14377142857143 40000 3,1454 45000 3,14275555555556 2000 3,144 4000 3,162 20000 3,1508 200000 3,1393 400000 3,13964 600000 3,13876 800000 3,140735 1000000 3,141376 1200000 3,14043666666667 1400000 3,13944 1600000 3,139585 1800000 3,13948666666667 2200 3,10545454545455 4400 3,11272727272727 22000 3,15490909090909 220000 3,14834545454545 440000 3,14379090909091 660000 3,1405696969697 880000 3,14003181818182 1100000 3,14069454545455 1320000 3,14128181818182 1540000 3,14124155844156 1760000 3,14210227272727 1980000 3,14162828282828 2500 3,1456 5000 3,1248 25000 3,13408 250000 3,14128 500000 3,145 750000 3,14327466666667 1000000 3,143492


_____________________________________________________________________________________15

1250000 3,142928 1500000 3,14369866666667 1750000 3,14326171428571 2000000 3,143336 2250000 3,14359466666667


_____________________________________________________________________________________16

CONCLUSION El nmero Pi como se demostr en este informe se puede simular con el mtodo de Montecarlo, como se explic, consiste en un circulo inscrito en un cuadrado y cada vez que se marcan los puntos dentro o fuera va generando el nmero Pi, entre ms iteraciones se hayan hecho ms cerca del valor estaremos.


_____________________________________________________________________________________17

UNIVERSIDAD TECNOLOGICA METROPOLITANA FACULTAD DE INGENIERIA ESCUELA DE INFORMATICA

TAREA N 1

ALUMNA : Ana Luisa Soto. ASIGNATURA : Simulacin de Sistemas de

Informacin. PROFESOR : Santiago Zapata. CARRERA : 2141

Documents

7789 Simulacionnumeropiszc-soto (1)