Algoritmos aleatorios (introducción)

Tengo una noticia La NASA ha dicho que habra hardware generador de números aleatorios en el Rover al que tenemos acceso. Después de eso, hicieron otro comentario ellos me recordaron que solo necesitamos nuestro algoritmo para que funcione en práctica. Para que algo funcione en práctica, significa que hay siempre alguna posibilidad de error, pero tal vez la posibilidad es tan pequeña que la ignoramos en la practica, y si eso suena loco, solo date cuenta de que en el mundo físico nada es siempre incuestionable, siempre hay posibilidad de error. Por ejemplo, el empaquetado de chips contine pequeñas cantidades de contaminantes radioactivos, y cuando estos decaen, se liberan particulas alfa las cuales pueden en realidad cambiar bits en memoria, y quizás cambiar un número inesperadamente. Aún mas interesante, los rayos cósmicos pueden también causar pequeños errores, nunca podemos borrar la posibilidad de error completamente Le pregunte a la NASA exactamente qué posibilidad de error es aceptable. Ellos dijeron, "Solo tenemos que estar seguros que "la probabilidad de error, por una prueba dada, "es menos que las posibilidades de "ganar la loteria dos veces seguidas Las posibilidades de ganar la loteria, digamos 649 dos veces seguidas, es seis veces diez elevado a menos catorce, entones aseguremosnos y redondiemoslo y digamos que nuestra posibilidad es diez a la menos quince Suficientemente seguro; no esperaremos ver un error, y esto podria correr cientos o miles de veces. Ahora mi pregunta es, el acceso a la aleatoriedad nos ayudaría a acelerar un algoritmo de decisión tal como esta prueba preliminar? Esta es una pregunta profunda, asi que demos un paso atras y miremos la imagen completa. Dada alguna colección de enteros desde uno hasta algun limite N digamos, pensemos en esto como en nuestro universo de enteros. Podemos siempre dividir una colección en dos conjuntos. Un problema de decisión puede en realidad ser pensado como una particion en dos conjuntos. Por ejemplo, dados algun N es N menos que 100, eso dara como salida 'si' para todos los enteros menores que 100. Aqui esta una colección y 'no' para todos los otros, lo cual es otra colección. Ok, entonces ahora concentrémonos en reconocer primos con la decisión. Idealmente, lo que nos gustaria es algún criterio simplemente computado que satisface a todos los primos y no satisface a factoreables. Ahora si supieramos algún patrón simple el cual describe la localización de todos los primos, y solo los primos, entonces dado algún número N podríamos simplemente verificar si N sigue ese patrón. El problema es hasta ahora no exaustivo y se ha encontrado un patrón simplemente computado para todos los primos y no factoriables, o todos los factoriables y no primos. Bero nos sabemos pruebas rapidas para la mayoria de los números factoriables. Por ejemplo, un criterio simplemente computado sería una prueba por paridad, y todos los numeros pares son divisibles por dos. Es rápido porque podemos decir si algo es par solo mirando el último digito, y aún cuando N crece, el problema no se hace mas dificil, solo miramos a ese último dígito también conocido como bit de bajo orden. Ahora date cuenta que podemos usar esta prueba de paridad como un prueba de baja calidad para factoriables. En eso podríamos hacer que el algoritmo acepte nuestro entero N, y todo lo que nuestro algoritmo hace es verificar si es par. si es par, y mayor a dos, entonces sabemos con 100 % de certeza de que es factoriable porque tenemos prueba. Piensa en dos como nuestro factoriable testigo. Aunque si no, entonces no estamos totalmente seguros. Si es impar, podría ser primo ya que todos los primos son impares, o podría ser uno de muchos factoriables que son impares, solo nueve o quince. Esta región masiva de factoriables impares causa un test inaceptable. Ahora para que quede claro, dibujemos esto. Dado algun N, N puede ser o primo o factoriable. Si N es primo, nuestro algoritmo dira primo 100 porciento del tiempo ya que no hay primos pares Nunca dira factoriable cuando se dé un primo Aunque, si N es factoriable, nuestro algoritmo dira factoriable aproximadamente cincuenta porciento del tiempo, y primo cincuenta porciento del tiempo Esto significa que si nuestro algoritmo da como salida 'factoriable', significa que encontro prueba de testigo factoriable. Aunque, para que nuestro algoritmo de salida 'primo' sabemos que hay una inaceptablemente grande posibilidad de error. Hasta ahora, nuestra estrategia ha lidiado con este grande, inaceptablemente grande error, por iteración y dibujemos el flujo de nuestra maquina. Dado algun N, nuestra maquina hace unas series de pruebas de divisibilidad empezando con A es 2 pregunta si A divide N. si no divide N, entonces podemos eliminar todo de esta región. Entonces formula la siguiente pregunta, N divide tres? Si no, entonces eliminamos toda esa sección. N divide cinco, siete, y continuando asi. Notese que estos son conjuntos disjuntos los cuales gradualmente llenan todo posible factoriable. ahora si alguna vez dijimos si a lo largo del camino, entonces encontramos prueba de que N es factoriable. A, lo que sea is en ese punto, nuestro testigo. nos detenemos, N da salida 'factoriable' desde nuestro algoritmo De otra forma, continuamos intentando hasta que agotamos todo posible factoriable. Hasta que damos con la raiz cuadrada de N ya que sabemos, recuerda todo número factoriable N debe tener un factor menos que o igual que la raiz cuadrada de N Esto realmente nos lleva a la pregunta final en nuestro algoritmo si no se encuentra ningun testigo, y A es mayor a la raiz cuadrada de N, entonces de pronto tenemos prueba y nos detenemos y devolvemos 'primo' Date cuenta que tenemos dos caminos a la salida en el algoritmo. Ambos senderos representan prueba de certeza que N es o primo o factoriable. Cuando N es primo, probamos todos los posibles divisores y basicamente los descartamos a todos y esa es nuestra prueba que N es primo. El problema con esta estrategia es que nuestro valor de prueba A cuando menos necesita que se itere por todo numero primo empezando desde dos hasta la raiz cuadrada de N. Mientras N crece, el numero de primos crece con el. Esto resulta en demasiadas iteraciones en el peor escenario tal como cuando damos al algoritmo un primo. Mirando a la imagen completa ahora, date cuenta se esta dando prueba cuando N es primo Lo cual sabemos no necesitamos excactamente. Nadie dijo que necesitabamos probarlo. Solo necesitamos estar 99.9999 quince nueves por ciento seguros. Hmmm, entonces en realidad necesitamos pensar acerca de la prueba de factoriable que esta siendo usada en nuestro algoritmo Recuerda, nuestra prueva de division mas rapida las pruebas de numeros primos hasta ahora han intentado usar un patron primo tal como 6k, o todos los primos de la forma 6k mas o menos uno, para ayudar a caminar a lo largo de primos solamente y eliminar muchos de los factoriables para ahorrar tiempo. Recuerda, una prueba como esta puede tornarse una prueba de factoriable. Eso es, dado un entero N es de la forma 6K mas menos uno, entonces podemos decir 'es probablemente un primo' pero hay muchos factoriables aún los cuales siguen el patron. esto no incluye solo primos, solo todos los primos y algunos factoriables, y podemos pensar en estos factoriables extra como una fuga y esta fuga es nuestra causa de error. Ahora si lo invertimos y si N no es de la forma 6K mas menos 1, entonces podemos decir con 100 porciento seguros es un factoriable, entonces la fuga es nuestra causa de error del lado de los primos, pero en este caso es inaceptable no es un error no-insignificante. Hay una probabilidad mucho mas grande. Necesitamos definir un procedimiento de prueba para factoriables el cual pueda reducir este espacio y hacer la posibilidad de error insignificante. Lo que significa necesitaremos revisar cómo podemos en realidad reducir errores con iteraciones. Creo que debemos ahora postear nuestras ideas debajo respecto a que clase de pruebas podriamos realizar y tambien mas importante ¿cómo podría un generador de numeros aleatorios realmente ayudarnos?