¿Cuáles son algunos de los mejores algoritmos?

Un candidato es ciertamente el algoritmo euclidiano para encontrar el máximo divisor común. Data de aproximadamente 300 a. C., más de dos milenios antes de que existieran dispositivos mecánicos (mucho menos electrónicos) para ejecutar algoritmos. Para poner esto en perspectiva, considere que los números negativos no ganaron aceptación en las matemáticas europeas hasta la década de 1700.

Más recientemente, la programación dinámica es una clase general de algoritmos que continúa sorprendiéndonos con su poder. Muchos algoritmos muy comunes para problemas como encontrar la distancia mínima de edición entre dos cadenas y el algoritmo de Viterbi utilizado en los sistemas de reconocimiento de voz se basan en la programación dinámica. En esencia, el sistema de búsqueda QPX desarrollado por el software ITA de mi compañía anterior era un algoritmo de programación dinámico.

Finalmente, los sistemas a prueba de conocimiento cero son intuitivamente bastante difíciles de creer al principio. A ZKP le permite a la parte A demostrarle a la parte B que A conoce un secreto particular, sin que la parte B sepa el secreto o aprenda algo útil al respecto . Utilizamos un sistema de prueba de este tipo en Inky, nuestro cliente de correo, para autenticarlo cuando inicia sesión. Los servidores de Inky no conocen su contraseña, pero saben cuándo la sabe. ¿Extraño, eh?

Un algoritmo que es particularmente importante para la física (especialmente la astrofísica) es el código de árbol Barnes-Hut. Por lo general, con problemas de n cuerpos, debe calcular [matemáticas] O (n ^ 2) [/ matemáticas] número de fuerzas entre partículas, pero con el árbol Barnes Hut puede hacerlo en [matemáticas] O (n \ log {n }) [/ math] tiempo. Esto se debe a que divide la cuadrícula en pedazos para que no trates los cuerpos más alejados individualmente sino como una celda colectiva. Aquí hay una visualización:


Puede ver claramente que las celdas son más grandes cuanto más se aleje del origen (en este caso, estaría calculando las fuerzas sobre la partícula en el origen, es decir, donde el espacio entre celdas es más fino).

De todos modos, es bastante importante porque la aceleración es bastante grande (especialmente cuando se considera el número masivo de partículas en las simulaciones astrofísicas, por lo que la curva cuadrática se vuelve bastante empinada rápidamente), y estas fuerzas deben calcularse en cada paso de tiempo, lo que significa que La aceleración total también es una función de su horario. Es uno de esos algoritmos que literalmente permitió que floreciera un campo.

Consulte el artículo de Wiki para obtener una explicación completa: simulación Barnes – Hut

Muestreo de yacimientos

Supongamos que tiene una matriz de n elementos y desea elegir un elemento aleatorio de la matriz. Esto es fácil: elija cada elemento con probabilidad 1 / n.

Pero supongamos que recibe los elementos uno a la vez, y no sabe cuántos elementos habrá. ¿Cómo lo harías entonces? No sabes qué es n, por lo que no puedes elegir cada elemento con probabilidad 1 / n. En teoría, podrías esperar a que vengan todos los elementos y luego hacer lo que hiciste antes. Pero el flujo podría ser muy largo, lo que hace que esto no sea factible. Queremos una solución donde no almacenes elementos y no los mires dos veces.

Como sucede, puede hacer esto de la siguiente manera:

  • Elija el primer elemento con probabilidad 1
  • Reemplace el primer elemento con el segundo elemento, con probabilidad 1/2
  • Reemplace el elemento actual con el tercer elemento, con probabilidad 1/3
  • Continúe haciendo esto hasta que termine la secuencia.

Este algoritmo requiere espacio constante y tiempo lineal.

Por que funciona Digamos que tienes tres elementos.

  • La probabilidad de elegir el primer elemento (al final) es P (sin reemplazar con el segundo elemento) * P (sin reemplazar con el tercer elemento) = 1/2 * 2/3 = 1/3
  • La probabilidad de elegir el segundo elemento es P (reemplazando el primer elemento con el segundo elemento) * P (no reemplazando el segundo elemento con el tercer elemento) = 1/2 * 2/3 = 1/3
  • La probabilidad de elegir el tercer elemento es P (reemplazando un elemento con el tercer elemento) = 1/3

En general, puede probar la corrección por inducción. Suponga que después de ver los elementos n-1, cada uno de los primeros elementos n-1 se elige con la misma probabilidad. Cuando vea el enésimo elemento, se elige con probabilidad 1 / n, y cada uno de los otros elementos se elige con probabilidad [1 / (n-1)] * [(n-1) / n] = 1 / n. Por lo tanto, todos los elementos se eligen con la misma probabilidad.

Para obtener más información, consulte Muestreo de yacimientos [Wikipedia].