Función de aleatorización
 |
En informática , una función de aleatorización o función de aleatorización es un algoritmo o procedimiento que implementa una función elegida al azar entre dos conjuntos específicos , adecuada para su uso en un algoritmo aleatorizado .
Las funciones de aleatorización están relacionadas con los generadores de números aleatorios y las funciones hash , pero tienen requisitos y usos algo diferentes y, a menudo, necesitan algoritmos específicos.
Usos
Las funciones de aleatorización se utilizan para convertir algoritmos que tienen un buen rendimiento esperado para entradas aleatorias en algoritmos que tienen el mismo rendimiento para cualquier entrada.
Por ejemplo, considere un algoritmo de clasificación como quicksort , que tiene un tiempo de ejecución esperado pequeño cuando los elementos de entrada se presentan en orden aleatorio, pero es muy lento cuando se presentan en ciertos órdenes desfavorables. Una función de aleatorización de los números enteros 1 a n a los números enteros 1 a n se puede utilizar para reorganizar los n elementos de entrada en orden "aleatorio", antes de llamar a ese algoritmo. Este algoritmo modificado (aleatorio) tendrá un tiempo de ejecución esperado reducido, sea cual sea el orden de entrada.
Aleatoriedad
En teoría, se supone que las funciones de aleatorización son verdaderamente aleatorias y producen una función diferente impredeciblemente cada vez que se ejecuta el algoritmo. La técnica de aleatorización no funcionaría si, en cada ejecución del algoritmo, la función de aleatorización siempre realizara el mismo mapeo, o un mapeo completamente determinado por algún parámetro observable externamente (como el tiempo de inicio del programa). Con una función de "pseudoaleatorización" de este tipo, se podría, en principio, construir una secuencia de llamadas tal que la función siempre arrojara un caso "malo" para el algoritmo determinista subyacente. Para esa secuencia de llamadas, el costo promedio estaría más cerca del costo del peor de los casos, en lugar del costo promedio de entradas aleatorias.
En la práctica, sin embargo, la principal preocupación es que algunos casos "malos" para el algoritmo determinista pueden ocurrir en la práctica con mucha más frecuencia de lo que podría predecirse por casualidad. Por ejemplo, en una variante ingenua de ordenación rápida, el peor de los casos es cuando los elementos de entrada ya están ordenados, lo cual es algo muy común en muchas aplicaciones. Para tales algoritmos, incluso una permutación pseudoaleatoria fija puede ser suficientemente buena. Aunque el algoritmo "pseudoaleatorio" resultante todavía tendría tantos casos "malos" como el original, serán ciertos órdenes peculiares que es muy poco probable que surjan en aplicaciones reales. Entonces, en la práctica, a menudo se usan funciones de aleatorización que se derivan de generadores de números pseudoaleatorios , preferiblemente sembrados con datos externos "aleatorios", como la hora de inicio del programa.
Uniformidad
Los requisitos de uniformidad para una función de aleatorización suelen ser mucho más débiles que los de las funciones hash y los generadores pseudoaleatorios. El requisito mínimo es que mapee cualquier entrada del algoritmo determinista en una entrada "buena" con una probabilidad suficientemente alta. (Sin embargo, el análisis suele ser más simple si la función de aleatorización implementa cada mapeo posible con probabilidad uniforme).
Referencias
 | Este artículo de ciencias de la computación es un fragmento . Puedes ayudar a Wikipedia expandiéndolo . |
