[SC] 2. One-time-pad Encryption

In cryptography, the one-time pad (OTP) is a type of encryption which has been proven to be impossible to crack if used correctly. Each bit or character from the plaintext is encrypted by a modular addition with a bit or character from a secret random key (or pad) of the same length as the plaintext, resulting in a ciphertext. If the key is truly random, as large as or greater than the plaintext, never reused in whole or part, and kept secret, the ciphertext will be impossible to decrypt or break without knowing the key.
The "pad" part of the name comes from early implementations where the key material was distributed as a pad of paper, so the top sheet could be easily torn off and destroyed after use. For easy concealment, the pad was sometimes reduced to such a small size that a powerful magnifying glass was required to use it. Photos show captured KGB pads that fit in the palm of one's hand,[7] or in a walnut shell.[8] To increase security, one-time pads were sometimes printed onto sheets of highly flammable nitrocellulose.

http://en.wikipedia.org/wiki/One-time_pad

For the first activity of this class, we have to write a python script implementing one time pad encryption.
For my script I used the technique of modular addition to cipher and decipher. The steps of my script are:

1. Generate the pads: Execute the file oneTimePad.py -G to generate the pads. The cipher pad name and the decipher pad name are requested before, also the number of keys to generate and the length of each key. Whole process happens silently and very fast.
   
   
   
   
   Basically, my pad generation function opens/creates the pad file, then, initialize a list of the same size that the lenght of a key, the list is filled with random integer numbers between 0 and 126 (the basic ascii code), that's means that my alphabet lenght is 127.
   When the list is full, I use the python join() function to convert it to a string and write it in the pad file. This is repeated until the specified amount of keys are created.
   Finally, I use the module shutil and import the function shutil.copy() to create a copy of the pad. One is the cipher pad and the other one is the decipher pad.
   
   
   
   
   Original message:
   
   
   
   
   



2. Encrypt a message: Execute the file oneTimePad.py -C to cipher a message file. The name of the original message file, the name of the output file (encrypted message) and the name of the cipher pad file are requested.
   
   
   
   
   This function opens the input file (original message file), reads all the lines and merges them into a single and long line, then, converts the line in a list, now, each character is a element of the list. Opens the cipher pad file and read the first line to get the cipher key, also, converts the line into a list. Then, checks if the length of the message is less than or equal to the length of the key, if is lesser, punctuation marks are appended to the message list, if is equal nothing is done, if is greater, an error is raised and the script finish the execution. After the verification, the message is encypted character by character according the formula:
   
   (int(key[a]) + ord(message[a])) % alphabetLength
   
   Where a corresponds to the index of an element in the lists.
   The characters are converted first in their corresponding ascii codes, then, the corresponding value of the key is added, then the module of the alphabet length is applied. The result is appended in a output list. When all the characters were converted, the output list are converted in a string using the function join() and is written in the specified output file. Finally, the cipher pad file is opened and the first line is removed.
   
   
   
   
   Encrypted message:
   
   
   
   
   



3. Decrypt a message: Execute the file oneTimePad.py -D to decrypt an encrypted message file. The name of the encrypted message file, the name of the output file (decrypted message) and the name of the decipher pad file are requested.
   
   
   
   
   This function opens the input file (encrypted message file), reads all the lines and merges them into a single and long line, then, converts the line in a list, now, each character is a element of the list. Opens the decipher pad file and read the first line, also, converts the line into a list. Then, checks if the length of the message is equal to the length of the key, if is lesser or greater an error is raised and the script finish the execution. After the verification, the message is decrypted character by character according the formula:
   
   (alphabetLength + int(message[a]) - int(key[a])) % alphabetLength
   
   Where a corresponds to the index of an element in the lists.
   The characters are converted first in their corresponding ascii codes, then, the alphabet length is added and the key value is substracted, then the module of the alphabet length is applied. The result is appended in a output list. When all the characters were converted, the output list are converted in a string using the function join() and is written in the specified output file. Finally, the decipher pad file is opened and the first line is removed.
   
   
   
   
   Decrypted message:
   
   
   

We can see how punctuation marks was added at the final of the file. This was because the key length was greater than the length of the message.

Code

References

• http://en.wikipedia.org/wiki/One-time_pad

[VVS] 2. Lógica proposicional; formas normales

Después de un pequeño recordatorio sobre matemáticas discretas y lógica proposicional, la tarea 2 consistío en armar una tautología.

Aterrizando el concepto:

"Una tautología es aquella fórmula lógica que es cierta para cualquier valoración de los símbolos proposicionales que contiene."

Sin embargo, la tautología a elaborar debía tener las siguientes caracteristicas:

• 3 variables
• 4 conectivos lógicos
• Por lo menos 1 disyunción, 1 conjunción y 1 negación

La tarea fue sencilla, no llevo mucho tiempo, los pasos que segui fueron:

1. Armar una tabla de verdad para las 3 variables
2. Agregar el primer conectivo, una conjunción y resolver
3. Agregar el segundo conectivo, una disyunción y resolver
4. Agregar el tercer conectivo, una implicación y resolver para la conjunción y la disyunción, elegí la implicación por el resultado de los anteriores conectivos, se ve que se puede obtener una tautología antes.
5. Aplicar un cuarto conectivo, la negación a la tercer variable.
6. Agregar el quinto conectivo, una disyunción, elegí este conectivo para obtener con seguridad una tautología al final ya que es el único que me da el resultado que busco.

Ésta es la tabla de verdad con todo el procedimiento:

p	q	r	(p ∧ q)	(p ∨ q)	((p ∧ q) -> (p ∨ q))	¬r	(((p ∧ q) -> (p ∨ q)) ∨ ¬r)
V	V	V	V	V	V	F	V
V	V	F	V	V	V	V	V
V	F	V	F	V	V	F	V
V	F	F	F	V	V	V	V
F	V	V	F	V	V	F	V
F	V	F	F	F	V	V	V
F	F	V	F	V	V	F	V
F	F	F	F	F	V	V	V

Éste es el árbol correspondiente a la tautología que arme:

Segundo Intento

Edito la entrada, pues no debí haber usado la implicación, entonces, partiendo del mismo procedimiento modifico del paso 4 en adelante:

1. Tabla con 3 variables
2. 1 conjunción
3. 1 disyunción
4. Negar la conjunción
5. Unir la conjunción negada y la disyunción con otra disyunción adicional

Ésta es la tabla de verdad con todo el procedimiento:

p	q	r	(p ∧ q)	(p ∨ q)	(¬(p ∧ q))	((¬(p ∧ q)) ∨ (p ∨ q))
V	V	V	V	V	F	V
V	V	F	V	V	F	V
V	F	V	F	V	V	V
V	F	F	F	V	V	V
F	V	V	F	V	V	V
F	V	F	F	F	V	V
F	F	V	F	V	V	V
F	F	F	F	F	V	V

Éste es el árbol correspondiente a la nueva tautología:

[RNA] 1. Pronostico de Patrones de Delincuencia

Tomada de http://blog.analyticstraining.in/archives/260

OBJETIVO

Utilizar una red neuronal para predecir actividad delictiva en una zona o en un lugar mediante reconocimiento de patrones.

PROCEDIMIENTO

La información de entrada sera una serie de tiempo, de le ensenara a la red neuronal el historial en un tiempo determinado, y se obtendrá una salida. Los resultados se convertirán en información pasada la cual pasara a ser ahora la entrada de la red neuronal y así obtendremos nuevos datos sucesivamente

• Lenguaje de programación Python

RESULTADO

Generar mapas de calor que permitan visualizar los resultados.

Tomada de http://supermodelcity3.blogspot.mx/2011/07/interesting-graphic-for-traffic-flow.html

REFERENCIAS

• How can Neural Networks be used for forecasting?
• Neural Forecasting Tutorials

[SC] 1. Texto Cifrado

Que tal a todos, este es mi texto cifrado, solo mencionaré que utilicé un método mixto. Saludos

[VVS] 1. La Verificación y Validación de Software

DEFINICIÓN

Conjunto de procesos de comprobación y análisis que aseguran que el software que se desarrolla está acorde a su especificación y cumple las necesidades de los clientes.

OBJETIVO

Los objetivos de las actividades de verificación y validación son valorar y mejorar la calidad de los productos del trabajo generados durante el desarrollo y modificación del software. Debemos corregir todo posible fallo y alcanzar cierto grado de perfección, asi mismo, debemos garantizar la consistencia, confiabilidad, utilidad, eficacia y el apego a los estándares del desarrollo de software.

Para ello es necesario encontrar defectos en el sistema que estamos desarrollando y asegurarnos que el sistema será útil para el entorno de trabajo requerido.

VERIFICACIÓN Y VALIDACIÓN

Ambos conceptos suelen tratarse como sinónimos, sin embargo, se refieren a cosas completamente distintas:

• La verificación se enfoca más al proceso de evaluación del sistema o de los componentes, permite determinar si los productos de una determinada fase del desarrollo satisfacen las condiciones impuestas en el inicio de la misma. Responde la pregunta ¿Estamos construyendo el producto correctamente?, entonces el software debería ajustarse a sus especificaciones iniciales.
• La validación también es una evaluación del sistema o componentes, pero solo se efectúa en el transcurso o al final del proceso del desarrollo para determinar si cumple con lo especificado. Responde la pregunta ¿Estamos construyendo el producto correcto?, entonces el software debería hacer lo que el cliente realmente quiere que haga.

Es importante resaltar que nunca se va a poder demostrar que el software está completamente libre de defectos, la verificación y validación mas crítica es realizada por los clientes finales.

TÉCNICAS DE VALIDACIÓN Y VERIFICACIÓN

Para aplicar estas técnicas siempre en necesario modelar cierto tipo de pruebas (tests) específicas, las pruebas son actividades en las cuales un sistema o uno de sus componentes se ejecuta en circunstancias previamente especificadas, los resultados se observan y registran y se realiza una evaluación de algún aspecto.

Varias pruebas juntas con un fin especifico constituyen un caso de pruebas donde un conjunto de entradas, condiciones de ejecución y resultados esperados son desarrollados para un objetivo particular.

Las pruebas deben centrarse en dos objetivos:

• Probar si el software no hace lo que debe hacer.
• Probar si el software hace lo que no debe hacer, es decir, si provoca efectos secundarios.

Se clasifican en 2 grandes grupos:

• Inspecciones de Software: analizan y comprueban las representaciones del sistema (los diagramas de diseño, el código fuente del programa). Se aplica a todas las etapas del proceso de desarrollo y se complementan con algún tipo de análisis automático del texto fuente y documentos asociados. Son técnicas de verificación y validación estáticas, no requieren que el sistema se ejecute.
• Pruebas de Software: consisten en comparar datos teóricos con los resultados del software utilizando series de datos de prueba, se examinan los resultados del software y su comportamiento operacional para comprobar que se desempeñe conforme a lo requerido. Es una técnica dinámica de la verificación y validación ya que requiere disponer de un prototipo ejecutable del sistema.

Lo que buscamos descubrir con ambos tipos de pruebas son:

• Defectos (bug): un defecto en el software como, por ejemplo, un proceso, una definición de datos o un paso de procesamiento incorrectos en un programa.
• Fallos (failure): La incapacidad de un sistema o de alguno de sus componentes para realizar las funciones requeridas dentro de los requisitos de rendimiento especificados.

Los errores mas comunes son:

• División por cero
• Ciclo infinito
• Problemas aritméticos como desbordamientos (overflow) o subdesbordamientos (underflow).
• Exceder el tamaño del array
• Utilizar una variable no inicializada
• Acceder a memoria no permitida (access violation)
• Pérdida de memoria (memory leak)
• Desbordamiento o subdesbordamiento de la pila (estructura de datos)
• Desbordamiento de búfer (buffer overflow)
• Bloqueo mutuo (deadlock)
• Indizado inadecuado de tablas en bases de datos.

Después de que hemos realizado ambas pruebas y que han sido localizados errores, es necesario especificar un proceso de depuración .

El proceso de depuración localiza y corrige los errores descubiertos durante la verificación y validación. Es un proceso complicado pues no siempre los errores se detectan cerca del punto en que se generaron. Para este paso„ se utilizan herramientas de depuración, que facilitan el proceso. Algunos ejemplos de herramientas de depuración para diferentes plataformas son:

• GDB (GNU Project Debugger) para C jdb - The Java Debugger
• JDB (Java Debugger) para JAVA
• JUnit (Java Unit Testing), suite de pruebas unitarias para JAVA , existen versiones para JavaScript.
• PDB (Python debugger), suite de pruebas unitarias para JAVA

Después de reparar el error, hay que volver a probar el sistema (pruebas de regresión)pues la solución del primer fallo puede dar lugar a nuevos fallos.

IMPORTANCIA

La importancia de los procesos de validación se puede entender mejor si analizamos las consecuencias de no realizarlos, hay varios ejemplos famosos: : El Cohete Mariner 1, en una investigación espacial destinada a Venus, se desvió de su trayectoria de vuelo poco después de su lanzamiento. El control de la misión destruyó el cohete pasados 293 segundos desde el despegue. Causa: Un programador codificó incorrectamente en el software una fórmula manuscrita, saltándose un simple guión sobre una expresión. Sin la función de suavizado indicada por este símbolo, el software interpretó como serias las variaciones normales de velocidad y causó correcciones erróneas en el rumbo que hicieron que el cohete saliera de su trayectoria.

• Desastre: Cohete Mariner 1 
  Descripción: investigación espacial destinada a Venus, se desvió de su trayectoria de vuelo poco después de su lanzamiento. El control de la misión destruyó el cohete pasados 293 segundos desde el despegue. 
  Causa: Un programador codificó incorrectamente en el software una fórmula manuscrita, saltándose un simple guión sobre una expresión. Sin la función de suavizado indicada por este símbolo, el software interpretó como serias las variaciones normales de velocidad y causó correcciones erróneas en el rumbo que hicieron que el cohete saliera de su trayectoria.


• Desastre: Mars Climate Orbiter 
  Descripción: El satélite se estrello en la superficie marciana. 
  Causa: error en la programación del sistema de navegación hizo que al entrar en su atmósfera este se desintegrara, esto pasó porque al introducir los cálculos no se hicieron en el Sistema Métrico Internacional lo que provocó un fallo en la medición de la altitud sobre el planeta.


• Desastre: Ariane 5 
  Descripción: El cohete se desvía se su curso debido a un error en los datos procesados. El intento posterior de enderezar la trayectoria fue demasiado brusco y el cohete finalmente se destruyó a los 37 sg. 
  Causa: el software de control realizó una conversión de un valor flotante de 64 bits en un entero de 16 bits sin comprobar que se produjeran desbordamientos.

Todos los desastres anteriores pudieron haber sido evitados si la causa de los mismos hubiera sido corregida mediante sencillas pruebas y evaluaciones.

Como podemos suponer, este tipo de experimentos tienen un alto costo para las instituciones que los realizan, un error en el sistema puede resultar en la perdida de millones de dolares, aunque en la actualidad son mas serios los errores que tienden a corromper o suprimir la información o datos guardados de los usuarios.

Siempre hay que darle importancia a estas pruebas y destinar los recursos necesarios a las mismas, no solo por las perdidas y el costo de repararlos en una etapa posterior, sino por nuestra propia ética profesional, un error de este tipo puede dejar a un Ingeniero en Software sin trabajo de por vida, entonces, es necesario ver las técnicas de validación y verificación de software como un proceso obligado en el desarrollo de software.

REFERENCIAS

• http://www.oscargallardo.com/wp-content/uploads/2011/04/CIISA_IS2_V_V2.ppt
• http://clases3gingsof.wetpaint.com/page/Verificación+y+Validación
• http://www.ctr.unican.es/asignaturas/Ingenieria_Software_4_F/Doc/M7_09_VerificacionValidacion-2011.pdf

[MSDS] Sistemas Caóticos: Geografía Fractal

Un Sistema Caótico es un tipo de Sistema Dinámico . Los Sistemas Dinámicos son sistemas cuyo estado evoluciona con el tiempo.

El comportamiento en dicho estado se puede caracterizar determinando los límites del sistema, los elementos y sus relaciones; de esta forma se puede elaborar modelos que buscan representar la estructura del mismo sistema. Constan de ciertas condiciones iniciales las cuales fijan los estados subsecuentes del sistema.

Asi pues, un Sistema Dinamico se considera caotico cuando es muy sensible a las variaciones en las condiciones iniciales. Pequeñas variaciones en dichas condiciones iniciales pueden implicar grandes diferencias en el comportamiento futuro; complicando la predicción a largo plazo.

Sistemas Dinámicos y Teoría del Caos es la rama de las Matemáticas que trata acerca del comportamiento cualitativo a largo plazo de un sistema dinámico. No se trata de encontrar soluciones exactas a las ecuaciones que definen dicho sistema dinámico (lo cual suele ser imposible), sino más bien el poder contestar preguntas como "¿A largo plazo, se estabilizará el sistema? ¿Y si lo hace, cuáles serán los estados posibles?" o "¿Variará el estado a largo plazo del sistema, si cambian las condiciones iniciales?"

Una de las mayores características de un sistema inestable es que tiene una gran dependencia de las condiciones iniciales. Esto sucede aunque estos sistemas son en rigor determinísticos, es decir; su comportamiento puede ser completamente determinado conociendo sus condiciones iniciales. De un sistema del que se conocen sus ecuaciones características, y con unas condiciones iniciales fijas, se puede conocer exactamente su evolución en el tiempo. Pero en el caso de los sistemas caóticos, una mínima diferencia en esas condiciones hace que el sistema evolucione de manera totalmente distinta.

Geografía Fractal

Cuando observamos algún paisaje nunca nos detenemos a pensar en éste llego a tener tal forma. A grandes razgos, nos ponemos a pensar siempre en las fuerzas moldeadoras del planeta tales como el agua y aire (erosion), erupciones volcánicas, movimientos tectónicos, etcetera. Sin embargo, esas curvas graciosas que cubren nuestro planeta son el resultado de un equilibrio de una gran cantidad de variables.

Los relieves que rodean el planeta parecen no tener relación para muchos, sin embargo, cuando nos vamos alejando de la superficie podemos comenzar a notar cierto patron en dichos relieves, los cuales finalmente terminan teniendo un tamaño de kilometros, una forma bien definida y que parece tener cierto orden.

Canales de drenaje pluvial en una cordillera

Y dichas formas caprichosas son el resultado de la gran cantidad de energía que esta debajo de nosotros y que permanece en equilibrio, la cual se manifiesta mediante los terremotos. Las placas se tensan unas a otras, cuando la tensión en cierto momento alcanza un punto critico, esta es liberada, alterando a su vez el paisaje que la rodea y moldeándolo. Ejemplo son las montañas, islas y cordilleras. Podemos ver en las siguientes imágenes como, a pesar de tener formas irregulares a simple vista, en escalas mayores los relieves tienden a conservar un orden Fractal, el cual es mas obvio en las costas marítimas.

Un fractal es un objeto semigeométrico cuya estructura básica, fragmentada o irregular, se repite a diferentes escalas.

Asi por ejemplo: en un mapa mundial podemos ver islas de diferentes tamaños. Su distribución se rige por leyes potenciales rigen si tamaño y forma, por lo que nos encontramos de nuevo ante estructuras fractales. Mientras la distribución de los continentes e islas de gran tamaño son pocas, es muy alta la cantidad de islas y archipielagos.

Modelado de Relieves

El modelado computacional de relieves es un tema tanto sencillo, en su forma mas básica, la propiedad mas importante que necesita ser modelada es la elevación.

La forma más simple es generar una gradiente de grises aleatoriamente distribuida o de colores que después puede ser traducida cono un mapa de relieve o elevaciones para finalmente modelarse en 3D.

El método más utilizado es el llamado Perlin Noise. Este método genera una gradiente de ruido en grises la cual puede utilizarse para crear nubes, fuego o relieves.

Cuando se usa para crear relieves, las partes blancas son relieves altos, las partes negras son relieves bajos o por debajo del nivel del mar

Con este método primeramente se establece un estado inicial, que generalmente es un cuadrado cuyas esquinas tienen asignados valores aleatorios de elevación. Después el cuadrado comienza a subdividirse en cuatro, y a cada nuevo cuadrado se le han de calcular sus nuevas alturas siguiendo un patrón, por ejemplo:

Las elevaciones iniciales son valores generados al azar, los valores intermedios son calculados iterativamente y su computo depende total mente de las condiciones inciales.

Ejemplo del proceso (Wikipedia | Fractal Landscape)

Uno de los problemas del método consiste en que utilizaba solo cuadrados, lo que en la generación de graficas por computadora no es muy atractivo actualmente. El método se complemento con un paso intermedio que agrega en lugar de cuadrados, rombos o diamantes también. A este método se le llamo Diamond-square algorithm.

El beneficio que se obtiene es la generación de gradientes un poco mas naturales, pero no discontinuas, que proporcionan relieves mas realisticos.

Gradiente generada con Diamond Square Algorithm

Si vemos los gradientes asi como asi, se nos hacen aburridos, poco atractivos... lo bueno viene cuando son interpretados por un programa tal como Octave o Matlab, el resultado es algo como esto:

Este tipo de diseño de terrenos es llamado Fractal Landscape, su objetivo es la generación de paisajes naturales mediante fractales. Aunque los paisajes fractales parezcan naturales a primera vista, la exposición repetida puede defraudar a quienes esperen ver el efecto de la erosión en las montañas. La crítica principal es que los procesos fractales simples no reproducen (y quizás no puedan hacerlo) las funciones geológicas y climáticas reales.

Con algo de texturizado y sombreado nos queda un paisaje geográfico bastante real.

Generando Paisajes Fractales

Tuve poco tiempo, base mi código en un tutorial sobre este tema.

Recibe 2 parámetros, la cantidad de iteraciones y el segundo es el nivel de "evolución del terreno".

Básicamente el código lo que hace es crear una matriz de 2x2, y que solo tiene ceros, es decir, comenzamos con una zona flat (un cuadrado de cero altura en todos sus lados).

Después vamos a utilizar la función interp2 que lo que hace es agregarme los subelementos a la matriz, es decir, de 2x2 ahora hace una matriz 3x3, en la siguiente iteración me genera una matriz 5x5 y así sucesivamente según el numero de iteraciones. Entre mayor sea el número de iteraciones, mayor sera el detalle del paisaje, pero tardara mas en diseñarlo y plotearlo.

Despues marcamos solo los subelementos internos, es decir, una vez creado el cuadrado principal, lo subdividimos y descartamos los nodos viejos y solo seleccionamos los nuevos para trabajar con ellos.

Después calculamos un valor random, que sera la nueva altura que le sumaremos o restaremos a los nodos marcados, este se multiplica por el factor de cambio del terreno, valores pequeños ofrecen poco cambio, pero, debido a la dinámica del código esto no se cumple necesariamente.

Por último, dividimos el factor de cambio entre 2 para disminuir en cada iteración el factor de cambio y hacer todo un poco mas natural.

Código

Para la demostración, correré el código a 6 iteraciones (las cuales son suficientes) y una razón de cambio pequeña, de 0.1

Primera Iteración

Segunda Iteración

Tercera Iteración

Cuarta Iteración

Quinta Iteración

Sexta Iteración

Podemos ver como se genero un terreno fractal a partir de una zona completamente flat. Por medio de estos algoritmos podemos producir ambientes naturales bastante realistas y en poco tiempo. En mi caso no pude, creo que el poder de calculo de mi computadora se quedo corto, entonces, con mas de 8 iteraciones se congelaba Octave y había que matar el proceso.

Y este es el mapa de Perlin Noise utilizando Diamond-Square

Podemos también definir el nivel del mar del terreno, por ejemplo, con esta instrucción le digo que todo valor menor a cero lo iguale a cero, para que cero sea mi limite inferior y por consiguiente, mi nivel del mar:

octave> w = m;

octave> w(w < -0.01) = -0.01;

Después de correr el código otra vez y poner las líneas anteriores, este es el resultado (podemos ver la zona plana):

Bueno, quedo hasta aquí en el tema de geografía fractal, espero les sea de interés y utilidad.

Referencias

• Wikipedia | Teoria del Caos
• Wikipedia | Sistemas Dinamicos y Teoria del Caos
• Wikipedia | Fractal Landscape
• Sistema Caotico
• Leyes Fractales y Estructuras Superficiales
• Fractal Landscapes
• Perlin Noise Tutorial
• Fractal Landscape & Perlin Noise

[MSDS] Tarea 3 Pruebas estadísticas para los números pseudoaleatorios

El objetivo de esta tarea es determinar si los generadores de números pseudoaleatorios incluidos en las librerias de los diferentes lenguajes de programación se apegan a alguna distribución y si los mismos presentan las características deseables de los números pseudoaleatorios.

Herramientas

• Lenguaje de Programación: Python
• Libreria generadora de números pseudoaleatorios: random.normalvariate(0,1) (Normal Estándar)
• Distribución a evaluar: Normal
• Libreria de Pruebas Estadisticas: Scipy
• Graficador: GNUPlot

1. ¿Los números generados de acoplan a la distribución indicada?

Para realizar esta prueba primero realice un código en Python que, con la ayuda de la libreria random, nos permite generar números pseudoaleatorios.

En mi caso voy a generar números pseudoaleatorios que se acoplen a la distribución normal utilizando la función random.randomvariate(0,1), como vemos, los parámetros serán 0 y 1, esto es, significancia = 0 y una desviación = 1, para seguir una normal estándar.

Por default se generan 10000 números, ya que hay que tener una muestra bastante grande; pero es posible enviar la cantidad como parámetro también.

Además se implementa una prueba de Anderson (scipy.stats.anderson), al generar los números, éstos se van almacenando en una lista, la lista se envía a la prueba Anderson para que los valores sean evaluados y se deteminará si la muestra proviene de una distribución específica (en éste caso, la distribución normal).

Código Python

Una vez que corremos el código, se generará un archivo llamado data.dat, éste contiene los números generados, lo que haré después es graficarlos. Pensé en hacer un código que implementara canastas, sin embargo, decidí dejar el trabajo a GNUPlot, con el siguiente código se generaran canastas de 0.1 unidades de ancho, leeremos el archivo data.dat e iremos creando un histograma de frecuencias.

Adicional a eso, implemente en el archivo de GNUPlot la función de densidad de probabilidad de la distribución normal para ver el acople de la distribución de los números generados y la forma original de la distribución normal. La formula es la siguiente:

Código GNUPlot

Gráfica

Fueron generados 1 000 000 de números, se acomodaron por canastas y formaron un histograma, si lo comparamos con la gráfica normal estandar (en rojo, con líneas) podemos ver que se acoplan casi perfectamente, tentativamente podemos deducir que efectivamente los números generados por random.randomvariate() si se acoplan a la distribución normal.

Prueba Anderson

Los resultados de la prueba Anderson para la muestra de 1 000 000 fueron:

Las hipótesis relacionadas no fueron rechazadas para todos los niveles de significancia, entonces podemos terminar de deducir que los números si se acoplan a la distribución normal.

2. ¿Los números generados presentan características deseables de "números aleatorios"?

Para las pruebas de aleatoriedad decidi basarme en la pagina random.org y leer un poco sobre los test, entonces me puse implementar 2 de ellos:

1. Frecuency Monobit

El propósito de esta prueba es calcular la proporción de ceros y unos en una muestra dada de números pseudoaleatorios.

Se espera que la proporción sea aproximadamente el mismo, es decir, que la proporción de unos dea 1/2 y la proporción de ceros también.

2. Frecuency Block

El enfoque de la prueba es calcular la proporción de unos en una muestra dada e números aleatorios, pero esta ves, la secuencia es dividida en bloques más pequeños y del mismo tamaño.

El propósito de este ensayo es determinar si la frecuencia de unos en un bloque de M-bits es de aproximadamente M / 2, como sería espera que en el supuesto de aleatoriedad.

Código

Ésta es la implementación de las pruebas, para hacerlo un poco más equilibrado, decidí comparar 2 muestras diferentes de 10000 números pseudoaleatorios cada una. La primera es generada con random.normalvariate() redondeando algunos valores y aplicando algunas condiciones para obtener valores binarios 0 y 1. La segunda es generada con random.randint() poniendo como limites 0 y 1 obviamente.

Después ambas listas se envían a evaluar, primero por Frecuency Monobit y después por Frecuency Block:

Los resultados de las pruebas para ambas listas fueron:

Podemos ver como para la lista generada por random.normalvariate() la proporción es 1, podemos deducir que la probabilidad entre ceros y unos es idéntica, por lo que se trata de una librería que cumple con los estándares para la generación de números aleatorios. No sorprende que haya pasado ambas pruebas.

No podemos decir lo mismo de la librería random.randint() cuya proporción es bastante baja comparada con la anterior. Podemos ver que cumple con los estándares de la prueba monobit, pero la prueba de bloques fue un fracaso total, entonces es 50% menos confiable que la random.normalvariate() además del umbral que las separa a las dos por la prueba monobit.

Referencias

• Random.org Análisis 2005
• Random.org Análisis
• R: Tests of Normality

[MSDS] Mapa de Logística. Puntos Extra

Código

GNUPLOT

Comando

python logisticMap.py 0.000039 100 1000 100000

gnuplot logisticMap.plot

convert -flatten data.eps data.png

Resultado Pagina Web

Resultado Código

Referencias

• Logictic App

[MSDS] Procesos Estocásticos Discretos y Contínuos

"La distribución de probabilidad de una variable aleatoria es una función que asigna a cada suceso definido sobre la variable aleatoria la probabilidad de que dicho suceso ocurra.
La distribución de probabilidad está definida sobre el conjunto de todos los sucesos, cada uno de los sucesos es el rango de valores de la variable aleatoria.
Cuando la variable aleatoria toma valores en el conjunto de los números reales, la distribución de probabilidad está completamente especificada por la función de distribución, cuyo valor en cada real x es la probabilidad de que la variable aleatoria sea menor o igual que x."

Distribución Probabilidad Wikipedia

Distribución Discreta

Las distribuciones discretas son aquellas en las que la variable aleatoria puede pude tomar un número determinado de valores, por ejemplo:

• Si se lanza una moneda al aire puede salir cara o cruz
• Si se tira un dado puede salir un número de 1 al 6
• En una ruleta el número puede tomar un valor del 1 al 32

Para mi tarea elegí la distribución discreta binomial.

Distribución Discreta Binomial

Grafica de la Distribucion Discreta Binomial (fuente: Wikipedia.org)

Las distribución binomial parte de la distribución de Bernouilli.

La distribución de Bernouilli se aplica cuando se realiza una sola vez un experimento que tiene únicamente dos posibles resultados (éxito o fracaso), por lo que la variable sólo puede tomar dos valores: el 1 y el 0

La distribución binomial se aplica cuando se realizan un número"n" de veces el experimento de Bernouilli, siendo cada ensayo independiente del anterior. La variable puede tomar valores entre:

• 0: si todos los experimentos han sido fracaso
• n: si todos los experimentos han sido éxitos

Por ejemplo: se tira una moneda 10 veces: ¿cuantas caras salen?.

Si no ha salido ninguna la variable toma el valor 0; si han salido dos caras la variable toma el valor 2; si todas han sido cara la variable toma el valor 10

Partiendo de esta definición, tome el siguiente problema de distribución binomial, tratare de explicar un poco si comportamiento binomial y posteriormente lo relacionaremos con una distribución de probabilidad continua.

Planteamiento

"Tenemos un examen que consta de 20 preguntas, cada pregunta puede ser verdadera o falsa. ¿La probabilidad de obtener 13 preguntas acertadas?"

Comportamiento

En este caso, la respuesta es binaria, entonces podemos deducir que:

• La probabilidad de éxito es 0.5
• La probabilidad de fracaso es 0.5

Ahora, la distribución binomial recibe 2 parámetros, B(n,p)

• n: que es el número de veces que se repite el experimento.
• p: que es la probabilidad de que el experimento sea exitoso, en este caso, que la respuesta sea acertada

La variable aleatoria x en este caso puede valer x = 0, 1, 2, ..., 20 dependiendo de cuantas preguntas sean acertadas (éxitos); la probabilidad de éxito se calcula con la siguiente formula:

donde:

Ahora, analicemos el comportamiento del problema con el siguiente programita, escrito reutilizando algunos módulos de la clase anterior, recibe el numero de repeticiones "n" y la probabilidad "p" y lo único que hace es aumentar el valor de x desde 0 hasta n (en este caso, 20), con estos valores podremos realizar una pequeña gráfica, utilizo la función bincoeff de Octave para obtener la mayor precisión, el código es el que sigue:

Se ejecuta entrando a Octave y llamando al script, escribiendo el nombre de la funcion y pasando los parametros correspondientes a nuestro problema planteado: binomial(20, 0.5)La salida generada consiste en 2 columnas donde la segunda corresponde a la probabilidad de obtener el numero de respuestas acertadas, dado por la primera columna, la salida es la siguiente:

Y la gráfica es la siguiente, generada con la herramienta GNUplot:

El resultado a nuestro problema es una probabilidad de 0.073929 (7.3929%) de obtener 13 aciertos de 20 preguntas de verdadero y falso.

Distribución Continua

Las distribuciones continuas son aquellas que presentan un número infinito de posibles soluciones, por ejemplo:

• El peso medio de los alumnos de una clase puede tomar infinitos valores dentro de cierto intervalo (42,37 kg, 42,3764 kg, 42, 36541kg, etc)
• La esperanza media de vida de una población (72,5 años, 7,513 años, 72, 50, 63 años)

Analizando la gráfica de la distribución discreta binomial de mi problema, pude relacionar que comportamiento de la misma con la distribución continua normal.

Distribución Continua Normal

Grafica de la Distribucion Continua Normal (fuente: Wikipedia.org)

Es el modelo de distribución más utilizado en la práctica, ya que multitud de fenómenos se comportan según una distribución normal.

Esta distribución de caracteriza porque los valores se distribuyen formando una campana de Gauss, en torno a un valor central que coincide con el valor medio de la distribución.

No quiere decir que mi problema sea continuo, sin embargo, estuve leyendo ciertas investigaciones acerca de la relación existente entre ambas distribuciones y es posible obtener una distribución binomial mediante una aproximación.

El método de aproximación a una distribución binomial por medio de la normal es muy común, vamos a analizar el comportamiento de mi problema mediante una distribución normal. Para ello ya no podemos plantear nuestro problema de la misma forma que en la binomial, ahora el planteamiento seria:

"Tenemos un examen que consta de 20 preguntas, cada pregunta puede ser verdadera o falsa. ¿La probabilidad de obtener por lo menos 13 preguntas acertadas?"

El primer paso es calcular los valores media y desviación estándar correspondientes a la distribucion normal. Para ello se utiliza el teorema de De Moivre, donde:

Entonces calculamos (recordemos que n = 20, p = 0.5, q = 0.5):

Media = np = (20)(0.5) = 10

Desviación Estándar = sqrt(npq) = sqrt[(20)(0.5)(0.5)] = sqrt(5) = 2.236068

Teniendo estos datos, es posible aproximarnos al resultado mediante la siguiente formula:

Donde x sigue valiendo 13 (13 aciertos en 20 preguntas). Entonces calculamos:

Z = [(13 - 10)/2.236068] = (3/2.23608) = 1.34

El valor de 1.34 no es en realidad el valor de la probabilidad, sino el limite central de la distribución normal. Si comparamos este valor de límite central con las tablas de distribución normal vemos que la probabilidad es de 0.91014 (91.014%) de obtener por lo menos 13 preguntas acertadas. Utilizando la funcion normcdf de Octave:

Hay que recordar que nos da un valor de 0.91014 (91.014%) porque nos esta dando la probabilidad de obtener POR LO MENOS 13, es decir, se suman las probabilidades de obtener desde 1 pregunta hasta 13.
Si sumamos los valores de la table que obtuvimos con la binomial el resultado sera 0.94234 que comparado con el 0.91014 lo cual es una buena aproximacion.

Entonces, ahora es posible generar la gráfica de la distribución normal y ver como es su aproximación a la distribución binomial, para ello modifique el programa que calcula la binomial para que calcule la también la normal y realice un proceso de "tipificación" que es lo que nos proverá los valores aproximados a la binomial, esto es, restar a 1 la probabilidad obtenida por la tabla de la distribución normal de acuerdo al limite central obtenido por cada experimento. El código del calculo y ploteo quedaron como sigue:


la parte importante del código es donde se comienza a convertir la gráfica, si vemos son 3 estados principales los cuales producen las siguientes gráficas, los estados los obtenemos comentando y descomentando las lineas (pero nunca debemos tener 2 o mas lineas descomentadas):

Estado 1. Que es la binomial en rojo sin ningún ajuste contra la normal estándar en verde.

Estado 2. Donde ajustamos el desplazamiento causado por la binomial cuando 'n' crece.

Estado 3. Donde convertimos la gráfica binomial basada en la altura de los puntos, a una distribución normal basada en el área debajo de la Campana de.

Asi es como aproxime mi problema binomial y a una normal. :)

Referencias

• Distribución Binomial
• Distribuciones Probabilidad
• Distribución Binomial