Curso:
Estimación numérica Monte Carlo.
Lista de ejercicios
Departamento de Investigación Operativa
Instituto de Computación, Facultad de Ingeniería
Universidad de la República, Montevideo, Uruguay
dictado semestre 2 - 2007
Sesión 2 - Ejercicio 2.1
Supongamos que para construir una casa debemos efectuar la siguiente
lista de tareas:
T1 - cimientos - tiempo aleatorio uniforme entre 32 y 48 hs.
T2 - paredes - tiempo aleatorio uniforme entre 40 y 60 hs.
T3 - techo - tiempo aleatorio uniforme entre 15 y 25 hs.
T4 - instalación sanitaria - tiempo aleatorio uniforme entre 10 y 15 hs.
T5 - instalación eléctrica - tiempo aleatorio uniforme entre 10 y 15 hs.
T6 - cerramientos - tiempo aleatorio uniforme entre 6 y 10 hs.
T7 - pintura - tiempo aleatorio uniforme entre 18 y 24 hs.
T8 - limpieza final - tiempo aleatorio uniforme entre 4 y 8 hs.
Hay ciertas dependencias que implican que una tarea no puede comenzar hasta haberse terminado otra previa:
T2, T3 dependen de 1.
T3 depende de 2
T4 depende de 2
T5 depende de 2 y 3
T6 depende de 2 y 3
T7 depende de 2, 4 y 5
T8 depende de 4, 5, 6 y 7
Ejercicio:
implementar un programa que reciba como parámetros de línea de comando (o pregunte en pantalla) la cantidad de replicaciones n a realizar, y emplee Monte Carlo para calcular (e imprimir) la estimación del tiempo total desde que se comienza la obra hasta que se finaliza la misma, y la desviación estándar de este estimador.
Incluir código para calcular el tiempo de cálculo empleado por el programa.
Utilizar el programa con n
=10,100,1000, 10000, y mostrar en una tabla las estimaciones de media y desviación estándar, así como los tiempos de cálculo. Discutir estos resultados.
Las pautas sobre el informe a entregar estan disponibles.
Fecha entrega: viernes 5 de octubre de 2007.
Sesión 3 - Ejercicio 3.1
Problema: se desea estimar el volumen de una region  de [0,1]4 definida por todos los puntos de la hiper-esfera de centro (0.3, 0.2, 0.7, 0.8) y radio 0.50, que además cumplan las restricciones siguientes: 5x1+10x2 £ 4; x3+x4 £ 1; 2x1-3x2 ³ 0.
Ejercicio 3.1:
Parte a:
implementar un programa que reciba como parámetro la cantidad de replicaciones n a realizar, y emplee Monte Carlo para calcular (e imprimir) la estimación del volumen de Â, y la desviación estándar de este estimador. Incluir código para calcular el tiempo de cálculo empleado por el programa.
(partes b y c se incluirán en una próxima entrega).
Fecha entrega: viernes 19 de octubre.
Sesión 4 - Ejercicio 3.2
Comparar y discutir la dependencia de los criterios de peor caso nC, nN, nH frente a los parámetros e y d.
Calcular nC, nN, nH para e = 0.01, d = .001, .01, .05.
Fecha entrega: viernes 19 de octubre.
Sesión 5 - continuación Ejercicio 3.1
Problema (enunciado en la sesión 3): se desea estimar el volumen de una region  de [0,1]4 definida por todos los puntos de la hiper-esfera de centro (0.3, 0.2, 0.7, 0.8) y radio 0.50, que además cumplan las restricciones siguientes: 5x1+10x2 £ 4; x3+x4 £ 1; 2x1-3x2 ³ 0.
Parte b: calcular la cantidad de replicaciones a realizar para garantizar un error menor a 2×10-4 con probabilidad 0.95, utilizando el criterio
de peor caso de Hoeffding.
Parte c: calcular el intervalo de confianza de nivel 0.95 utilizando
el criterio de Chebyshev, y el criterio de Agresti-Coull. Comparar el ancho de estos intervalos entre sí y con el criterio de error manejado en el punto previo.
Fecha entrega: viernes 26 de octubre.
Sesión 6 - Ejercicios 3.3 y 3.4
Ejercicio 3.3:
Problema: se desea estimar la integral de la función sen(xy)/(x2y2) sobre la región definida por el círculo con centro en (0.5,0.5) y radio 0.5.
Parte a: escribir un programa para realizar este cálculo por Monte Carlo. Realizar 106 replicaciones y estimar el valor de z y el error cometido (con nivel de confianza 0.95), utilizando como criterio
la aproximación normal.
Parte b: en base al valor estimado en la parte a, calcular el número de replicaciones necesario para obtener un error absoluto menor a 10-2 (con nivel de confianza 0.95).
Parte c: realizar esa cantidad de replicaciones y estimar z y su intervalo de confianza.
Ejercicio 3.4:
Problema: se desea estimar la integral de la función x1x22x33x44x55 sobre el hipercubo Jm de dimensión m
=5.
Parte a: escribir un programa para realizar este cálculo por Monte Carlo. realizar 106 replicaciones y estimar el valor de z. Calcular analíticamente el valor exacto de la integral.
Parte b: en base al valor estimado en la parte a, calcular el número de replicaciones necesario para obtener un error menor a 5×10-4 (con nivel de confianza 0.95).
Parte c: Decimos que un intervalo de confianza cubre el valor exacto cuando este último pertenece al intervalo.
Realizar L=500 experimentos con semillas diferentes, cada uno consistente en estimar por Monte Carlo con el nro. de replicaciones de la parte b el valor de la integral, así como intervalos de confianza de nivel 0.9, 0.95 y 0.99.
Para cada nivel de confianza, calcular el nivel de cobertura empírico (en que porcentaje de los 500 experimentos el intervalo de confianza calculado cubrió el valor exacto).
Discutir los resultados, comparando la cobertura empírica con la especificada.
Fecha entrega: viernes 26 de octubre.
Sesión 7 - Ejercicio 3.5
Problema: dado un grafo G=(V,E), definido por la lista de sus nodos y sus aristas, y dados dos nodos s y t del grafo, estimar mediante Monte Carlo los cardinales ci de los conjuntos
Si={x|fst(x)=1 y åe=1m xe = i}, para i=0,¼,m.
Se debe recibir en entrada el número de replicaciones a realizar, y el nivel de confianza; en salida, se debe dar las estimaciones para cada ci, así como la desviación estándar y un intervalo de confianza (del nivel especificado) calculado en base al criterio de Agresti-Coull.
Parte a: escribir un programa para hacer el cálculo previamente descrito. Entregar seudocódigo y código.
Parte b: sea un grafo con ocho nodos V={v1,¼,v8}, y con once aristas E={(v1,v2), (v1,v3),(v2,v3), (v2,v4),(v3,v5),(v4,v5),(v4,v6) ,(v5,v7), (v6,v7),(v6,v8), (v7,v8)}.
Sean s=v1 y t=v8 los nodos fuente y terminal. Usando el programa anterior, y empleando 1000 replicaciones de Monte Carlo, estimar los valores de ci para i=0,¼,11, con intervalos de confianza de nivel 95%.
Fecha entrega: viernes 9 de noviembre
Sesión 8 - Ejercicio 4.1
Elegir una fuente de números aleatorios disponible en Internet (sitio o tabla con valores). Modificar el ejercicio 3.1, parte a (visto en la sesión 3) para que emplee dichos números aleatorios (en lugar de los generados por bibliotecas como hasta el momento). Comparar si la salida obtenida es consistente o no con la obtenida en los experimentos de la parte a del ejercicio 3.1.
Fecha entrega: viernes 9 de noviembre
Sesión 10 - Ejercicio 4.2
En base a dos generadores de números seudo-aleatorios ya implementados (disponibles en bibliotecas públicas, o en lenguajes), implementar el método de shuffling.
Utilizar la secuencia generada por este método para calcular
ó õ
1
0
ó õ
1
0
ó õ
1
0
¼
ó õ
1
0
æ è
Ö
x12+x22+x32+¼+x92
ö ø
dx1 dx2 dx3¼dx9.
en base a 100000 iteraciones. Calcular media, desviación estándar y un intervalo de confianza de nivel 99% (fórmula a elección entre las aplicables vistas en el curso).
Fecha entrega: viernes 16 de noviembre
Sesión 14 - Ejercicio 5.1
Utilizar el método antitético para calcular
ó õ
1
0
ó õ
1
0
ó õ
1
0
¼
ó õ
1
0
æ è
Ö
x12+x22+x32+¼+x92
ö ø
dx1 dx2 dx3¼dx9.
en base a 50000 iteraciones. Calcular media, desviación estándar y un intervalo de confianza de nivel 99%.
Comparar con los resultados del ejercicio 4.2
Fecha entrega: miércoles 5 de diciembre.
File translated from
TEX
by
TTH,
version 3.33. On 15 Nov 2007, 15:50.