¿Cuál es el algoritmo aleatorio más fácil para motivar al laico?

Question

Cuando se trata de explicar la teoría de la complejidad a los laicos, a menudo hago mención de algoritmos aleatorizados, pero aparentemente la falta de buenos ejemplos para motivar su uso. A menudo me quiero mencionar primalidad de prueba, pero el estándar aleatorizado algoritmos de no admitir una simple descripción (o prueba de corrección) en un lay-atmósfera. Yo a menudo recurren a la frase de que aleatorizado algoritmos de permitir la "búsqueda de heno en un pajar", pero que tiene poco de matemática de la sustancia.

La pregunta: ¿hay un buen ejemplo de un problema que:

• es fácil de explicar (y lo suficientemente interesante)

• dispone de un sencillo algoritmo aleatorio

• parece que no trivial para obtener un eficiente algoritmo determinista

y, idealmente, también satisface:

• el algoritmo aleatorio tiene un algo comprensible prueba de corrección, por lo que no Markov/Chernoff/random-walk-mezcla-los tiempos

Answer 1

Michael, ¿cómo aproximar el volumen de alguna forma en $\Re^n$ por muestreo aleatorio de puntos?

Este ejemplo tiene las siguientes ventajas:

• Parece bastante fácil de explicar en un cóctel (dependiendo, por supuesto, en el que los huéspedes).

• Se utiliza constantemente en la "vida real" (de hecho, casi cualquier simulación de Monte Carlo en la física, etc. podría ser interpretado como la solución de este problema).

• No sabemos cómo derandomize ella. De hecho, el problema es fácil de ver para PromiseBPP completo (asumiendo, por supuesto, que sea un punto de $x \in \Re^n$ pertenece a la forma es decidable en el polinomio de tiempo).

Answer 2

Aunque esto requiere el uso de la aproximación, así como la aleatorización, yo siempre encuentro la idea de que se puede obtener una buena estimación de una población mediante el muestreo de una constante de tamaño ajustado a ser no muy intuitiva y potente. La manera en que yo normalmente frase en clase es: desea encuestar a la población para que cualquier razonablemente popular grupo está representado. Si "razonablemente" popular" se define como una fracción constante, sólo es necesario tomar una muestra de un número constante de personas para golpear todos los grupos. A juzgar por cómo la población en general se confunde por las encuestas, este parece un buen ejemplo.

Otro ejemplo de que es más útil para un "CS-consciente" lego es uno que requiere el conocimiento de la noción de una mediana. Usted puede obtener una rápida y sucia de aproximación para la mediana de la constante de tiempo de muestreo (de hecho, la mediana de TRES elementos aleatorios es suficiente), y la más que de muestreo, mejor será la aproximación.

Probablemente el más espectacular demostración de la potencia de la aleatoriedad, pero ay uno que no es fácil demostrar que para un profano en la materia, es el poder de las dos opciones. Parece casi imposible que es cierto, pero lo es.

Answer 3

[EDIT: descargo de responsabilidad! Yo probablemente no debería haber publicado esta respuesta, porque no está en ninguna parte cerca de mi área de especialización, así que ten cuidado, puede contener una tontería!]

[EDIT: lo siento, vi a este problema en un libro, pero me parece un buen algoritmo determinista en $O(n (\log n)^4)$ tiempo fue encontrado más tarde, por lo que esta respuesta es inaplicable; referencia:

La coincidencia de las tuercas y los tornillos por Noga Alon, Manuel Blum, Amos Fiat, Sampath Kannan, Moni Naor, Rafail Ostrovsky;

citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.103 ]

Las "tuercas y tornillos" problema, y yo la vi hace apenas unos días en el Algoritmo Manual de Diseño [referencia precisa a seguir cuando tengo tiempo para editar]:

Se le da $n$ pares de tuercas y tornillos, todo muy ligeramente diferentes tamaños (por lo tanto, cada tuerca de ajuste exactamente a un tornillo), pero por desgracia todos ellos han sido desmontado, y usted tiene que adaptarse a ellos juntos.

Usted no puede ver la diferencia en el tamaño de los ojos, así que la única manera de ver si una tuerca se ajusta un tornillo es intentarlo. Si la tuerca es demasiado grande o pequeño para un perno, usted descubrirá este; pero tenga en cuenta que no se puede comparar dos tuercas, o dos tornillos, uno con el otro directamente.

De manera abstracta: tenemos 2 real secuencias desconocidas $(x_1, x_2, \ldots, x_n)$ e $(y_1, y_2, \ldots, y_n)$.

El $x_i$ son todos distintos, y $(y_j)$ es un desconocido reordenamiento de $(x_i)$. Queremos coincidir con ellos, pero la ÚNICA medida que podemos hacer es recoger $i,j$ y compare $x_i$ con $y_j$.

La obvia algoritmo de tratar de todos ellos, uno por uno, se lleva a $O(n^2)$ del tiempo.

Sin embargo, una variante de aleatorizado quicksort tarda $O(n \log n)$ en promedio. La aleatoriedad sólo viene de recoger cada tuerca/tornillo al azar.

Detalles: escoge una tuerca, usar eso como el elemento pivote para los pernos; a continuación, utilice la coincidencia de tornillo como el elemento pivote para los frutos secos, etc. - como quicksort, pero ir hacia adelante y hacia atrás entre el $x$ e $y$ elementos.

Answer 4

Si usted está dispuesto a flexionar un poco en "no trivial para obtener un eficiente algoritmo determinista" (o al menos en la definición de "no trivial"), max-cut es un muy fácil. Dado un grafo $G=(V,E)$, el objetivo es crear particiones $V$ a $(V_1,V_2)$ a maximizar el número de aristas entre $V_1$ e $V_2$. Escoger una al azar de la partición en grupos de igual tamaño, hasta la paridad -- le da algo que en promedio tiene al menos la mitad de los bordes de la gráfica, por lo que es, en promedio, al menos a medio camino óptimo.

Este ejemplo es también muy agradable, en mi opinión, porque la Goemans--Williamson algoritmo, el algoritmo de lograr el mejor conocido de la aproximación de la relación (y la mejor posible asumir una cierta complejidad resultado) para el problema, sobre 0.878, también es aleatorio. (Puede ser derandomized utilizando el método de la condicional expectativas, pero a un costo razonable en términos de facilidad de explicación.)

Answer 5

Cómo sobre el uso de Monte Carlo para descifrar los mensajes cifrados? Este papel por Diaconis descifra una prisión mensaje que consiste en la prisión de lingo, múltiples idiomas, mala ortografía y se centra alrededor de una prisión de la roza. El más joven de TV-detective-mostrar obsesionado con la multitud va a encantar. El algoritmo es muy simple. Mostrando precisa de la tasa de convergencia de las estimaciones es un poco si un tiempo de mezcla problema, pero tal vez se puede tomar en la fe?

Recuerdo haberlo leído hace un tiempo y sentirse inspirado por azar algoritmos. Voy a ser honesto, yo sé muy poco de criptografía, pero a mí me parece que el problema dado en la referencia SÓLO puede ser resuelto por un algoritmo aleatorio. El hecho de que converge de manera rápida y tiene incluso un moderado ventana de "corrupción de datos" (tales como la mala ortografía y de los diferentes idiomas) que realmente te hace apreciar el poder de este material.