Qué es un algoritmo aleatorio

Elegir con dados

Algunos métodos deciden qué hacer a continuación tirando un dado. No lo piensan; simplemente lo dejan a la suerte.
Cada vez que pulsas el botón, el dado rueda una vez.
No hay forma de saber de antemano qué cara saldrá.

Pulsa para tirar el dado. La próxima cara no se puede saber de antemano.

¿Por qué dejar las cosas a la suerte a propósito? Si siempre eliges de la misma manera, alguien puede aprovechar esa costumbre y fabricar a propósito una entrada difícil.
Si eliges al azar, esquivas ese tipo de trampa.
Su verdadera utilidad se ve en el paso siguiente.

Usar un pivote al azar

Entre las formas rápidas de ordenar, hay una que elige un pivote y reparte el resto: los menores a la izquierda y los mayores a la derecha.
Pero si siempre se toma como pivote el último valor, con una entrada que ya está en orden todos los cortes salen desequilibrados y el orden se vuelve muy lento.

Compara cuántos pasos de corte hacen falta con el último valor como pivote vs con un pivote al azar. (desequilibrado = lento)

Si eliges el pivote al azar, venga la entrada que venga, casi nunca quedan cortes desequilibrados. Las trampas pensadas para entradas malas tampoco funcionan.
Así, en promedio, los cortes salen parejos y el orden se acelera.

Estimar a base de muchos tiros

El azar también sirve para estimar. Dibuja dentro de un cuadrado un cuarto de círculo, una de las cuatro porciones iguales de un círculo, y llénalo de puntos al azar.
Si miras qué parte de todos los puntos cae dentro del cuarto de círculo, puedes estimar cuánta área ocupa.
Ve marcando los puntos uno a uno.

Cuantos más puntos marcas, más se acerca la proporción al valor real. (puntos dentro del círculo / todos los puntos)

Con pocos puntos, la estimación da saltos. Pero cuantos más puntos marcas, más se pega la proporción al valor real.
Uno o dos golpes de suerte no son de fiar, pero el promedio de incontables tiros sí lo es.
Esta es la forma de estimar una respuesta a base de muchos tiros.

Cambiar certeza por velocidad

Los métodos al azar no salen gratis. A cambio de ser rápidos y sencillos, no pueden garantizar la misma respuesta cada vez, y con mala suerte a veces son lentos.
Toca los dos lados para comparar lo que ganas y lo que cedes.

Toca lo que ganas y lo que cedes para compararlos. (rapidez · sencillez vs sin garantía de la misma respuesta)

Por eso el azar no siempre es bueno: tiene su lugar adecuado.
Se usa cuando ser rápido y sencillo vale más que un poco de incertidumbre. Cedes algo de certeza para comprar velocidad y sencillez.

Resumen de un vistazo

Los métodos al azar, de un vistazo: elegir con dados, esquivar trampas con un pivote al azar, estimar una respuesta a base de muchos tiros y cambiar certeza por velocidad.
Toca los puntos clave en orden para resumirlos tú mismo.

Toca los cuatro puntos clave en orden para resumir. (dados · pivote al azar · estimar con muchos tiros · el intercambio)

Dejar las cosas a la suerte suena descuidado, pero bien usado, el azar es una herramienta rápida y fiable.
Cuanto más enormes son los datos, más útil resulta esta idea de estimar a base de muchos tiros.
En la próxima lección pasamos a un mundo de puntos unidos por líneas: los grafos.