Algoritmos centrales desplegados

Para demostrar la importancia de los algoritmos (por ejemplo, para estudiantes y profesores que no hacen teoría o incluso son de campos completamente diferentes), a veces es útil tener a mano una lista de ejemplos en los que se han implementado algoritmos centrales en empresas comerciales, gubernamentales, o software / hardware ampliamente utilizado.

Estoy buscando ejemplos que satisfagan los siguientes criterios:

1. El software / hardware que usa el algoritmo debería estar en uso ahora mismo.

2. El ejemplo debe ser específico. Proporcione una referencia a un sistema específico y un algoritmo específico.
   Por ejemplo, en "el algoritmo X es útil para el procesamiento de imágenes" el término "procesamiento de imágenes" no es lo suficientemente específico; en "La búsqueda de Google usa algoritmos gráficos", el término "algoritmos gráficos" no es lo suficientemente específico.

3. El algoritmo debe enseñarse en estudiantes universitarios o doctores típicos. clases en algoritmos o estructuras de datos. Idealmente, el algoritmo está cubierto en los libros de texto de algoritmos típicos. Por ejemplo, "el conocido sistema X usa un algoritmo poco conocido Y" no es bueno.

Actualizar:

Gracias de nuevo por las excelentes respuestas y enlaces! Algunas personas comentan que es difícil satisfacer los criterios porque los algoritmos centrales son tan generalizados que es difícil señalar un uso específico. Veo la dificultad Pero creo que vale la pena proponer ejemplos específicos porque, según mi experiencia, les digo a las personas: "¡Miren, los algoritmos son importantes porque están en todas partes !" No funciona.

Los algoritmos que son el principal impulsor de un sistema son, en mi opinión, más fáciles de encontrar en cursos sin algoritmos por la misma razón por la que los teoremas con aplicaciones inmediatas son más fáciles de encontrar en matemáticas aplicadas que en cursos de matemáticas puras. Es raro que un problema práctico tenga la estructura exacta del problema abstracto en una conferencia. Para ser discutidor, no veo ninguna razón por la cual el material del curso de algoritmos de moda, como la multiplicación de Strassen, la prueba de primitiva AKS o el algoritmo Moser-Tardos sea relevante para problemas prácticos de bajo nivel de implementación de una base de datos de video, un compilador optimizador, un sistema operativo , un sistema de control de congestión de red o cualquier otro sistema. El valor de estos cursos es aprender que existen formas complejas de explotar la estructura de un problema para encontrar soluciones eficientes. Los algoritmos avanzados también es donde uno encuentra algoritmos simples cuyo análisis no es trivial. Por esta razón, no descartaría algoritmos aleatorios simples o PageRank.

Creo que puede elegir cualquier software grande y encontrar algoritmos básicos y avanzados implementados en él. Como estudio de caso, hice esto para el kernel de Linux y mostré algunos ejemplos de Chromium.

Estructuras de datos básicos y algoritmos en el kernel de Linux

Los enlaces son al código fuente en github .

1. Lista enlazada , lista doblemente enlazada , lista enlazada sin bloqueo .

2. B + Árboles con comentarios que te dicen lo que no puedes encontrar en los libros de texto.

   Una implementación B + Tree relativamente simple. Lo he escrito como un ejercicio de aprendizaje para comprender cómo funcionan los árboles B +. Resultó ser útil también.

   ...

   Se utilizó un truco que no se encuentra comúnmente en los libros de texto. Los valores más bajos están a la derecha, no a la izquierda. Todos los espacios utilizados dentro de un nodo están a la izquierda, todos los espacios no utilizados contienen valores NUL. La mayoría de las operaciones simplemente se repiten en todas las ranuras y terminan en el primer NUL.

3. Listas ordenadas por prioridad utilizadas para mutexes , controladores , etc.

4. Los árboles rojo-negros se utilizan para programar, administrar la memoria virtual, rastrear descriptores de archivos y entradas de directorio, etc.
5. Árboles de intervalo

6. Los árboles Radix se utilizan para la gestión de memoria , búsquedas relacionadas con NFS y funciones relacionadas con la red.

   Un uso común del árbol de radix es almacenar punteros para estructurar páginas;

7. Montón de prioridad , que es literalmente, una implementación de libro de texto, utilizada en el sistema de grupo de control .

   Puntero simple que contiene punteros prioritarios de solo tamaño estático de inserción, basado en CLR, capítulo 7

8. Funciones hash , con referencia a Knuth y a un documento.

   Knuth recomienda números primos en proporción aproximadamente dorada al número entero máximo representable por una palabra de máquina para el hash multiplicativo. Chuck Lever verificó la efectividad de esta técnica:

   http://www.citi.umich.edu/techreports/reports/citi-tr-00-1.pdf

   Estos primos se eligen para que sean poco dispersos, es decir, las operaciones en ellos pueden usar cambios y adiciones en lugar de multiplicaciones para máquinas donde las multiplicaciones son lentas.

9. Algunas partes del código, como este controlador , implementan su propia función hash.

   función hash usando un algoritmo Rotating Hash

   Knuth, D. The Art of Computer Programming, Volumen 3: Clasificación y búsqueda, Capítulo 6.4. Addison Wesley, 1973

10. Tablas hash utilizadas para implementar inodos , verificaciones de integridad del sistema de archivos, etc.

11. Las matrices de bits , que se utilizan para lidiar con banderas, interrupciones, etc. y se presentan en Knuth Vol. 4)

12. Semáforos y cerraduras giratorias

13. La búsqueda binaria se utiliza para el manejo de interrupciones , la búsqueda de registro de caché , etc.

14. Búsqueda binaria con árboles B

15. Profundidad primera búsqueda y variante utilizada en la configuración del directorio .

    Realiza un recorrido modificado de profundidad primero del árbol del espacio de nombres, comenzando (y terminando) en el nodo especificado por start_handle. La función de devolución de llamada se llama cada vez que se encuentra un nodo que coincide con el parámetro de tipo. Si la función de devolución de llamada devuelve un valor distinto de cero, la búsqueda finaliza inmediatamente y este valor se devuelve a la persona que llama.

16. La primera búsqueda de amplitud se utiliza para verificar la corrección del bloqueo en tiempo de ejecución.

17. La ordenación por fusión en listas vinculadas se utiliza para la recolección de basura , la administración del sistema de archivos , etc.

18. El ordenamiento de burbujas también se implementa asombrosamente en una biblioteca de controladores.

19. Knuth-Morris-Pratt coincidencia de cuerdas ,

    Implementa un algoritmo de coincidencia de cadenas de tiempo lineal debido a Knuth, Morris y Pratt [1]. Su algoritmo evita el cálculo explícito de la función de transición DELTA por completo. Su tiempo de coincidencia es O (n), para n es longitud (texto), utilizando solo una función auxiliar PI [1..m], para m es longitud (patrón), calculada previamente desde el patrón en el tiempo O (m). La matriz PI permite que la función de transición DELTA se calcule eficientemente "sobre la marcha" según sea necesario. En términos generales, para cualquier estado "q" = 0,1, ..., my cualquier carácter "a" en SIGMA, el valor PI ["q"] contiene la información que es independiente de "a" y es necesaria para calcular DELTA ("q", "a") 2. Como la matriz PI solo tiene m entradas, mientras que DELTA tiene entradas O (m | SIGMA |), guardamos un factor de | SIGMA | en el tiempo de preprocesamiento calculando PI en lugar de DELTA.

    [1] Cormen, Leiserson, Rivest, Stein Introdcution to Algorithms, 2nd Edition, MIT Press

    [2] Ver teoría de automatización finita

20. Coincidencia de patrones de Boyer-Moore con referencias y recomendaciones sobre cuándo preferir la alternativa.

    Implementa el algoritmo de coincidencia de cadenas de Boyer-Moore:

    [1] Algoritmo de búsqueda de cadena rápida, RS Boyer y Moore. Comunicaciones de la Association for Computing Machinery, 20 (10), 1977, pp. 762-772. http://www.cs.utexas.edu/users/moore/publications/fstrpos.pdf

    [2] Manual de algoritmos de coincidencia de cadenas exactas, Thierry Lecroq, 2004 http://www-igm.univ-mlv.fr/~lecroq/string/string.pdf

    Nota: Dado que Boyer-Moore (BM) realiza búsquedas de coincidencias de derecha a izquierda, aún es posible que una coincidencia se extienda a varios bloques, en ese caso este algoritmo no encontrará ninguna coincidencia.

    Si está dispuesto a asegurarse de que tal cosa nunca suceda, utilice la implementación de Knuth-Pratt-Morris (KMP) en su lugar. En conclusión, elija el algoritmo de búsqueda de cadenas adecuado según su configuración.

    Supongamos que está utilizando la infraestructura de búsqueda de texto para el filtrado, NIDS o
    cualquier propósito similar centrado en la seguridad, luego vaya a KMP. De lo contrario, si realmente le importa el rendimiento, digamos que está clasificando los paquetes para aplicar las políticas de Calidad de Servicio (QoS), y no le preocupan las posibles coincidencias distribuidas en múltiples fragmentos, luego vaya a BM.

Estructuras de datos y algoritmos en el navegador web Chromium

Los enlaces son al código fuente en el código de Google . Solo voy a enumerar algunos. Sugeriría usar la función de búsqueda para buscar su algoritmo favorito o estructura de datos.

1. Extiende árboles .

   El árbol también está parametrizado por una política de asignación (Asignador). La política se utiliza para asignar listas en la tienda gratuita C o la zona; ver zona.h.

2. Los diagramas de Voronoi se usan en una demostración.
3. Tabbing basado en el algoritmo de Bresenham .

1. Arboles binarios
2. Árboles rojo-negro

   Conclusión de Julian Walker

   Los árboles rojos y negros son bestias interesantes. Se cree que son más simples que los árboles AVL (su competidor directo), y a primera vista parece ser el caso porque la inserción es muy sencilla. Sin embargo, cuando uno comienza a jugar con el algoritmo de eliminación, los árboles negros y rojos se vuelven muy complicados. Sin embargo, el contrapeso a esta complejidad adicional es que tanto la inserción como la eliminación se pueden implementar utilizando un algoritmo de arriba hacia abajo de un solo paso. Tal no es el caso con los árboles AVL, donde solo el algoritmo de inserción puede escribirse de arriba hacia abajo. La eliminación de un árbol AVL requiere un algoritmo ascendente.

   ...

   Los árboles negros y rojos son populares, ya que la mayoría de las estructuras de datos tienen un nombre caprichoso. Por ejemplo, en Java y C ++, las estructuras del mapa de la biblioteca generalmente se implementan con un árbol negro rojo. Los árboles negros rojos también son comparables en velocidad a los árboles AVL. Si bien el equilibrio no es tan bueno, el trabajo que se necesita para mantener el equilibrio suele ser mejor en un árbol rojo negro. Hay algunas ideas falsas que flotan por ahí, pero en su mayor parte la exageración sobre los árboles rojos y negros es precisa.

3. Árboles AVL
4. La coincidencia de cadenas Rabin-Karp se utiliza para la compresión.
5. Calcule los sufijos de un autómata .
6. Filtro Bloom implementado por Apple Inc.
7. Algoritmo de Bresenham .

Bibliotecas de lenguaje de programación

Creo que vale la pena considerarlos. Los diseñadores de lenguajes de programación pensaron que valía la pena el tiempo y el esfuerzo de algunos ingenieros para implementar estas estructuras de datos y algoritmos para que otros no tuvieran que hacerlo. La existencia de bibliotecas es parte de la razón por la que podemos encontrar estructuras de datos básicas reimplementadas en software que está escrito en C pero no tanto para aplicaciones Java.

1. El STL C ++ incluye listas, pilas, colas, mapas, vectores, y algoritmos para la clasificación, búsqueda y la manipulación del montón .
2. La API de Java es muy extensa y cubre mucho más.
3. La biblioteca Boost C ++ incluye algoritmos como los algoritmos de coincidencia de cadenas de Boyer-Moore y Knuth-Morris-Pratt.

Algoritmos de asignación y programación

Me parecen interesantes porque, a pesar de que se denominan heurísticas, la política que utiliza dicta el tipo de algoritmo y la estructura de datos que se requieren, por lo que es necesario saber sobre pilas y colas.

1. Menos utilizado recientemente se puede implementar de varias maneras. Una implementación basada en listas en el kernel de Linux.
2. Otras posibilidades son Primero en entrar, primero en salir, Menos utilizadas con frecuencia y Round Robin.
3. Una variante de FIFO fue utilizada por el sistema VAX / VMS.
4. El algoritmo Clock de Richard Carr se usa para reemplazar el marco de página en Linux.
5. El procesador Intel i860 utilizó una política de reemplazo aleatorio.
6. Adaptive Replacement Cache se usa en algunos controladores de almacenamiento de IBM, y se usó en PostgreSQL aunque solo brevemente debido a preocupaciones de patentes .
7. El algoritmo de asignación de memoria Buddy , que es discutido por Knuth en TAOCP vol. 1 se usa en el kernel de Linux, y el asignador concurrente jemalloc usado por FreeBSD y en Facebook .

Utilidades principales en sistemas * nix

1. grep y awk implementan la construcción de NFA de Thompson-McNaughton-Yamada a partir de expresiones regulares, que aparentemente incluso supera la implementación de Perl .
2. tsort implementa el tipo topológico.
3. fgrep implementa el algoritmo de coincidencia de cadenas Aho-Corasick.
4. GNU grep , implementa el algoritmo Boyer-Moore según el autor Mike Haertel.
5. crypt (1) en Unix implementó una variante del algoritmo de cifrado en la máquina Enigma.
6. Unix diff implementado por Doug McIllroy, basado en un prototipo coescrito con James Hunt, funciona mejor que el algoritmo de programación dinámica estándar utilizado para calcular las distancias de Levenshtein. La versión de Linux calcula la distancia de edición más corta.

Algoritmos Criptográficos

Esta podría ser una lista muy larga. Los algoritmos criptográficos se implementan en todo el software que puede realizar comunicaciones o transacciones seguras.

1. Los árboles Merkle , específicamente la variante Tiger Tree Hash, se usaron en aplicaciones de igual a igual como GTK Gnutella y LimeWire .
2. MD5 se usa para proporcionar una suma de verificación para paquetes de software y se usa para verificaciones de integridad en sistemas * nix ( implementación de Linux ) y también es compatible con Windows y OS X.
3. OpenSSL implementa muchos algoritmos criptográficos que incluyen AES, Blowfish, DES, SHA-1, SHA-2, RSA, DES, etc.

Compiladores

1. El análisis LALR es implementado por yacc y bison.
2. Los algoritmos de Dominator se utilizan en la mayoría de los compiladores de optimización basados ​​en el formulario SSA.
3. lex y flex compilan expresiones regulares en NFA.

Compresión y procesamiento de imágenes

1. Los algoritmos Lempel-Ziv para el formato de imagen GIF se implementan en programas de manipulación de imágenes, comenzando desde la utilidad * nix convert a programas complejos.
2. La codificación de longitud de ejecución se utiliza para generar archivos PCX (utilizados por el programa Paintbrush original), archivos BMP comprimidos y archivos TIFF.
3. La compresión Wavelet es la base de JPEG 2000, por lo que todas las cámaras digitales que producen archivos JPEG 2000 implementarán este algoritmo.
4. La corrección de errores Reed-Solomon se implementa en el kernel de Linux , unidades de CD, lectores de códigos de barras y se combinó con convolución para la transmisión de imágenes desde Voyager.

Aprendizaje de cláusulas controladas por conflictos

Desde el año 2000, el tiempo de ejecución de los solucionadores SAT en puntos de referencia industriales (generalmente de la industria del hardware, aunque también se utilizan otras fuentes) ha disminuido casi exponencialmente cada año. Una parte muy importante de este desarrollo es el algoritmo de aprendizaje de cláusulas controladas por conflictos que combina el algoritmo de propagación de restricciones booleanas en el documento original de Davis Logemann y Loveland con la técnica de aprendizaje de cláusulas que se originó en la programación de restricciones y la investigación de inteligencia artificial. Para modelos industriales específicos, SAT se considera un problema fácil ( vea esta discusión) Para mí, esta es una de las mejores historias de éxito en los últimos tiempos porque combina avances algorítmicos repartidos en varios años, ideas ingeniosas de ingeniería, evaluación experimental y un esfuerzo comunitario concertado para resolver el problema. El artículo del CACM de Malik y Zhang es una buena lectura. Este algoritmo se enseña en muchas universidades (he asistido a cuatro donde era el caso) pero generalmente en una clase de lógica o métodos formales.

Las aplicaciones de los solucionadores SAT son numerosas. IBM, Intel y muchas otras compañías tienen sus propias implementaciones de solucionador SAT. El administrador de paquetes en OpenSUSE también usa un solucionador SAT.

PageRank es uno de los algoritmos más conocidos. Desarrollado por el cofundador de Google, Larry Page y sus coautores, formó la base del motor de búsqueda original de Google y se le reconoce ampliamente por ayudarlos a lograr mejores resultados de búsqueda que sus competidores en ese momento.

Imaginamos un "surfista aleatorio" que comienza en alguna página web y hace clic repetidamente en un enlace aleatorio para llevarlo a una nueva página. La pregunta es: "¿Qué fracción del tiempo pasará el surfista en cada página?" Cuanto más tiempo pasa el surfista en una página, más importante se considera la página.

$M$

$M^k \pi_0$$k$$\pi_0$$M$

Mencionaría la implementación de software CPLEX (o similar) ampliamente utilizada del método / algoritmo Simplex para resolver problemas de programación lineal. Es el (?) Algoritmo más utilizado en economía e investigación operativa.

"Si uno tomara estadísticas sobre qué problema matemático está utilizando la mayor parte del tiempo de la computadora en el mundo, entonces (sin contar los problemas de manejo de la base de datos como ordenar y buscar) la respuesta probablemente sería la programación lineal " (L. Lovász, Un nuevo Algoritmo de programación lineal: ¿mejor o peor que el método simplex? Math. Intelligencer 2 (3) (1979/80) 141-146.)

El algoritmo Simplex también tiene una gran influencia en teoría; ver, por ejemplo, la Conjetura de Hirsch (Polinómica) .

Supongo que una licenciatura típica o un doctorado. La clase en algoritmos se ocupa del algoritmo Simplex (incluidos los algoritmos básicos de álgebra lineal como el Método de eliminación de Gauss).

(Otros algoritmos exitosos, incluido Quicksort para ordenar, se enumeran en Algoritmos del Libro ).

Según tengo entendido, el Programa nacional de emparejamiento de residentes fue durante mucho tiempo solo una aplicación directa del algoritmo Gale-Shapley para el problema del matrimonio estable. Desde entonces, se ha actualizado ligeramente para manejar algunos detalles adicionales como asignaciones conyugales (también conocido como "problema de dos cuerpos"), etc.

Si también incluye material de nivel de doctorado, muchos (¿la mayoría?) Programas de posgrado de CS incluyen algún curso de teoría de codificación. Si tiene un curso de teoría de la codificación, definitivamente cubrirá el código Reed-Solomon, que es esencial para el funcionamiento de los discos compactos y la codificación Huffman, que se utiliza en formatos de archivo JPEG, MP3 y ZIP. Dependiendo de la orientación del curso, también puede cubrir Lempel-Ziv, que se utiliza en el formato GIF. Personalmente, obtuve Lempel-Ziv en un curso de algoritmos de pregrado, pero creo que eso podría ser atípico.

GNU grep es una herramienta de línea de comando para buscar en uno o más archivos de entrada líneas que contengan una coincidencia con un patrón especificado. ¡Es bien sabido que grep es muy rápido! Aquí hay una cita de su autor Mike Haertel (tomada de aquí ):

GNU grep uses the well-known Boyer-Moore algorithm, which looks first for the
final letter of the target string, and uses a lookup table to tell it how far
ahead it can skip in the input whenever it finds a non-matching character.

De manera más general, el premio Kanellakis es otorgado por la ACM por precisamente esos descubrimientos teóricos que han tenido un gran impacto en la práctica.

El premio de 2012 es para el hashing sensible a la localidad , que se ha convertido en un método de referencia para la reducción de la dimensionalidad en la minería de datos para problemas cercanos al vecino (y es relativamente fácil de enseñar, al menos el algoritmo mismo)

$\varepsilon$

Algunos ejemplos de usos industriales de estas estructuras de datos son:

• El sistema Sawzall de Google para el análisis de datos no estructurados utiliza Count Sketch para implementar una función de "elementos más populares"
• El sistema de "base de datos" de Gigascope de AT&T para el monitoreo del tráfico de red implementa el boceto CountMin.
• El sistema de Monitoreo continuo de Sprint (CMON) implementa CountMin.

Aquí también hay un sitio que recopila información sobre las aplicaciones de CountMin.

En cuanto a la enseñanza, sé que las técnicas básicas de dibujo se enseñan en Princeton en cursos de pregrado en matemáticas discretas. Me enseñaron el boceto CountMin en mi primer curso de algoritmos. En cualquier caso, el análisis de CountMin es más simple que el análisis de casi cualquier otro algoritmo aleatorio: es una aplicación directa de la independencia por pares y la desigualdad de Markov. Si este no es material estándar en la mayoría de los cursos de algoritmos, creo que es por razones históricas.

En la última década, los algoritmos se han utilizado para aumentar la cantidad (y la calidad, creo) de trasplantes de riñón a través de varios programas de igualación de donantes de riñón. He tenido problemas para encontrar las últimas noticias sobre esto, pero aquí hay al menos algunos consejos:

• Tan recientemente como 2007, la Alianza para la Donación por Pares estaba utilizando un algoritmo de Abraham, Blum y Sandholm . Puede que todavía lo estén usando, pero no pude averiguarlo buscando en línea. Aunque este algoritmo seguramente no está cubierto en los cursos "estándar", combina varias ideas fundamentales que seguramente se enseñan en dichos cursos para proporcionar un algoritmo suficientemente bueno para un problema que es, en general, NP-complete (una variante de Cycle Cover )

• El Registro Nacional del Riñón también utiliza algunos algoritmos estándar, incluido (en un punto) CPLEX. Esto condujo a una cadena de trasplantes realmente realizada que unía a 60 personas .

Este es uno de mis ejemplos favoritos no solo del éxito de los algoritmos, sino de la importancia de estudiar algoritmos para problemas de NP completo. Literalmente pueden salvar vidas , ¡y ya lo han hecho!

Algoritmo de Viterbi, que todavía se usa ampliamente en el reconocimiento de voz y en muchas otras aplicaciones: http://en.wikipedia.org/wiki/Viterbi_algorithm El algoritmo en sí es una programación dinámica básica.

De Wikipedia: "El algoritmo de Viterbi fue propuesto por Andrew Viterbi en 1967 como un algoritmo de decodificación para códigos convolucionales a través de enlaces de comunicación digital ruidosos. [1] El algoritmo ha encontrado una aplicación universal en la decodificación de los códigos convolucionales utilizados en celulares digitales CDMA y GSM, módems de acceso telefónico, comunicaciones satelitales, de espacio profundo y LAN inalámbricas 802.11. Ahora también se usa comúnmente en reconocimiento de voz, síntesis de voz, localización de palabras clave, lingüística computacional y bioinformática. Por ejemplo, en voz a texto (voz reconocimiento), la señal acústica se trata como la secuencia observada de eventos, y se considera que una cadena de texto es la "causa oculta" de la señal acústica. El algoritmo de Viterbi encuentra la cadena de texto más probable dada la señal acústica ".

1. A * se usa en muchos dispositivos de navegación personal (también conocidos como unidades GPS)
2. A * está muy bien definido y se ha implementado de manera bastante sencilla.
3. A * no es del todo trivial, pero no requiere un doctorado. para entenderlo

Echa un vistazo al proyecto BonnTools de Jens Vygen para Chip Design. http://www.or.uni-bonn.de/~vygen/projects.html He escuchado algunas conversaciones sobre esto y también he visto algunos de sus documentos. Utilizan el redondeo aleatorio de estilo Raghavan-Thompson, así como el método de actualización de peso multiplicativo para resolver LP de flujo multicommodity a gran escala. Sin embargo, como cualquier gran proyecto, también necesitan hacer algo de ingeniería, pero la metodología se basa mucho en algoritmos bien conocidos.

Es curioso que vi esta pregunta hoy y luego, casualmente, hice clic en este enlace sobre los muchos usos de la Transformada de Fourier .

Estoy bastante sorprendido de que con todos los sofisticados algoritmos anteriores, nadie mencione la venerable familia de algoritmos de compresión Lempel-Ziv (inventada en 1977/78).

1. Esos se usan en todas partes: texto a imagen para transmitir el procesamiento. Es muy posible que LZ * sea la única familia de algoritmos más utilizada que existe.
2. La compresión del diccionario fue un avance considerable en la teoría de la compresión y una clara desviación del enfoque de estilo Shannon-Fano.
3. Los algoritmos en la familia son bastante sencillos y fáciles de comprender.

Actualizar

Aparentemente ya se mencionó brevemente.

La descomposición de valores singulares (SVD) tiene una fuerte conexión con el análisis estadístico de factores o el análisis de componentes principales y es comprensible dentro de una clase de estadística o álgebra lineal de pregrado, y tiene muchas propiedades teóricas importantes. También juega un papel en los algoritmos de compresión de imágenes. jugó un elemento clave en las entradas ganadoras en el concurso de premios de Netflix de $ 1M (una de las competencias de minería de datos más grandes del mundo en la historia) y ahora se implementa en su sitio para predecir las calificaciones de los usuarios. También se sabe que está muy relacionado con las redes neuronales autoorganizadas de Hebb que se originan en la teoría biológica.

También existe cierta conexión con el descenso de gradiente, que se usa ampliamente en aprendizaje automático y redes neuronales artificiales y como una técnica de optimización muy universalmente aplicada, en cuyo caso el método de Newton es una forma 2D básica. Hay un algoritmo de gradiente de descenso para obtener la SVD.

Encontrar un camino euleriano está en la base del ensamblaje del genoma, una tarea que se realiza comúnmente cuando se trabaja con genomas completos (en bioinformática, medicina, medicina forense, ecología).

ACTUALIZACIÓN Olvidé esta obvia: UPS, FedEx, USPS tienen que resolver grandes instancias de Problema de vendedor ambulante todas las noches. Ahorra mucho tiempo y dinero para que envíen a los conductores en una ruta óptima.

ACTUALIZACIÓN2 El problema del conjunto de vértices de retroalimentación mínima se utiliza para la resolución de puntos muertos en muchos sistemas operativos.

Me gusta este sistema para salvar el número máximo de vidas en el Reino Unido con trasplantes de riñón, basado en algoritmos de coincidencia máxima: donación de riñón emparejada y altruista . Emparejan a las personas que necesitan riñones que tienen un amigo / familiar no compatible dispuesto a donar, con otras personas en la misma situación, de manera máxima. Luego, el día de la donación, todos los donantes donan al mismo tiempo, seguido de un rápido transporte de riñones por todo el país a los receptores.

Vale la pena considerar este libro relativamente nuevo como una respuesta completa / detallada a la pregunta en forma conveniente, extendida / recopilada y que podría utilizarse como material complementario para una clase de algoritmos. [algunos de estos ya han sido mencionados; la fuerte superposición en sí misma es notable.]

• Nueve algoritmos que cambiaron el futuro: las ingeniosas ideas que impulsan las computadoras de hoy por MacCormick

  • indexación de motores de búsqueda
  • Rango de página
  • criptografía de clave pública
  • códigos de corrección de errores
  • reconocimiento de patrones
  • compresión de datos
  • bases de datos
  • firmas digitales
  • teoría de la computabilidad

• Otra referencia algo similar pero más teórica, The Best of the 20th Century: Editors Name Top 10 Algorithms Cipra / SIAM.

  • Método de Monte Carlo
  • algoritmo simplex
  • Iteración del subespacio de Krylov
  • computación matricial descompuesta
  • Compilador Fortran
  • Algoritmo de matriz QR
  • ordenación rápida
  • FFT
  • detección de relación de enteros
  • algoritmo multipolar rápido

La búsqueda de cadenas Knuth-Morris-Pratt es ampliamente utilizada, específica y enseñada en CS de pregrado / posgrado.

Pensando en algoritmos muy básicos

1. Los generadores de números aleatorios se encuentran en todas partes y específicamente en todos los juegos.
2. Las bases de datos se componen de muchos algoritmos, incluidos B +, Hashes, colas de prioridad, expresión regular, criptografía, clasificación, etc. Un amigo mío dice que los SGBD están en la parte superior de la cadena alimentaria informática.
3. Ordenar se usa en todas partes, por ejemplo en Excel. En realidad, se usa todo el tiempo en la vida real, pero generalmente los humanos usan algoritmos ad-hoc
4. Los bits de paridad se usan por todas partes
5. La codificación de Huffman está en software de compresión y transmisión
6. Las pilas (LIFO) se usan en todas partes. Lenguajes de programación internos, en CPU, etc.

Es bueno mostrar que aparecen en la vida real:

A. Muchos grupos usan un tipo de algoritmo de árbol de cobertura para comunicarse, al dividir las listas telefónicas de manera jerárquica entre las personas B. Los automóviles en una intersección generalmente usan un algoritmo round-robin (de manera voluntaria) C. La mayoría de los lugares, como bancos y hospital, organizan a sus clientes en un algoritmo FIFO

Un problema algorítmico fascinante surge en la aplicación médica de la tomografía computarizada. En la tomografía computarizada (TC), el cuerpo está expuesto a rayos X desde diferentes ángulos. En un extremo del escáner están los transmisores de rayos X y en el otro extremo los sensores. A partir de una serie de escaneos de este tipo, se reconstruye una imagen para que el médico la examine.

El algoritmo de retroproyección filtrada es la base para la reconstrucción de una imagen a partir de un conjunto de escaneos. Este algoritmo es en realidad una forma de un problema de aproximación en el que la "señal" se muestrea por debajo de la velocidad de Nyquist. Este algoritmo se usa "detrás de escena" en todos los hospitales y la proyección de filtro básica de nuevo utiliza matemática de pregrado como transformaciones de Fourier para lograr el Teorema de la rebanada de Fourier .

Un ejemplo de FFT

Una vez ayudé a portar un algoritmo FFT a un lenguaje de sistema diferente.

El algoritmo se estaba utilizando para determinar los saltos de línea en la entrega coaxial de televisión por cable / internet / teléfono. Básicamente, un técnico solicitaría que se enviara una señal a la casilla del cliente, al mismo tiempo que mostraría una visualización en tiempo real de las estadísticas para el cliente específico, como QoS, dB, ... El técnico podría usar los datos y un gráfico para determinar dentro de unos pocos pies entre la casa y el poste donde existió una ruptura parcial (o múltiples rupturas, como me dijeron).

Como se mencionó anteriormente, FFT se usa ampliamente, pero este fue uno de los más evidentes y obvios (en términos de por qué y cómo) que he visto en la práctica.

Lo siento, tuve que mantenerlo en un nivel alto.

El algoritmo de línea de Bresenham es el algoritmo más útil que he encontrado. Fácil de entender. Lo he usado para muchas aplicaciones, desde dibujos lineales hasta un complejo spliner para motor de fundición en 3D y un complejo renderizador de polígonos, así como también para complejos usos de animación y escalado.

Planificación de ruta personalizable (Daniel Delling, Andrew V. Goldberg, Thomas Pajor y Renato F. Werneck) http://research.microsoft.com/apps/pubs/default.aspx?id=145688

poderes Bing Maps: http://www.bing.com/blogs/site_blogs/b/maps/archive/2012/01/05/bing-maps-new-routing-engine.aspx

Wikipedia tiene una colección decente de algoritmos / aplicaciones clasificadas más o menos en una lista . Microsoft proporciona los principales documentos citados pero sin ninguna explicación explícita del área de la informática ni la aplicación. También hay una lista cronológica de diferentes conferencias de CS _http: //jeffhuang.com/best_paper_awards.html_ compilada por el profesor Huang.

El agrupamiento espectral es un algoritmo de agrupamiento elegante, conocido como algoritmo de cortes normalizados introducido por Jianbo Shi y Jitendra Malik para la segmentación de imágenes. También se ha desarrollado bien en aplicaciones de agrupación de datos, siendo una buena intersección entre las dos comunidades.

Otros dos ejemplos favoritos personales firmemente arraigados en la informática pero que pueden pasar fácilmente por alto los teóricos abstraccionistas, que han experimentado avances enormes / transformadores y han tenido un impacto práctico / aplicado de mayor a mayor en la vida cotidiana en las últimas décadas. Ya toda una generación ha crecido sin conocer el mundo sin ellos. básicamente la categoría de modelado y simulación .

• algoritmos de simulación física . principalmente usando las leyes de Newton pero usando otras leyes (como la dinámica de fluidos). Se utiliza en una amplia variedad de aplicaciones que van desde aplicaciones de ingeniería, videojuegos y, a veces, películas. esto también es responsable de mejorar significativamente la seguridad, la eficiencia o la confiabilidad de, por ejemplo, automóviles y aviones sometiendo diseños virtuales / de prueba a tensiones simuladas. un área importante de investigación en curso relacionada con bioinformática con implicaciones masivas en biología, por ejemplo, diseño de fármacos, prevención de enfermedades, etc.: predicción de estructura / plegamiento de proteínas . También tenga en cuenta que este año el Premio Nobel de Química fue otorgado por simulación química a Karplus, Levitt, Warshel. los algoritmos de simulación física están altamente involucrados en la seguridad / prueba de armas nucleares por ejemplo, en los laboratorios de Los Alamos.

• Raytracing / algoritmos CGI . esto comenzó como un tema de investigación hace solo unas décadas [un amigo obtuvo su maestría en algoritmos de trazado de rayos CS] pero se volvió muy aplicado, por ejemplo, en los juegos y el negocio de hacer películas, alcanzando niveles extraordinarios de verosimilitud que es responsable de grandes cantidades de efectos especiales en peliculas. Estas industrias literalmente han invertido miles de millones de dólares y utilizan estos algoritmos, y grandes corporaciones enteras se basan en su aprovechamiento, por ejemplo, Pixar . se utiliza principalmente en películas de ciencia ficción, por ejemplo, la técnica ahora está tan extendida que se usa de manera rutinaria incluso en películas "típicas". por ejemplo recientemente The Great Gatsby dependía en gran medida de los efectos CGI para dibujar ambientes convincentes o estilizados, retocar la película / personajes, etc.

Rosetta Code enumera los algoritmos aplicados por Tarea de programación (692) y por Lenguaje de programación (518) con Semantic MediaWiki.

quizás todos los algoritmos principales / preferidos de interés para esta audiencia se hayan mencionado en este punto. sin embargo, algunos más merecen mención por su integridad. Y aquí es relevante algún análisis de lo que se considera un algoritmo significativo.

En los campos de CS e IT parece haber un fenómeno notado hace mucho tiempo en la IA llamado "mover los postes" . Este es un fenómeno psicológico en el que el campo avanza relativamente rápido, pero las personas se adaptan mentalmente rápidamente a "la nueva normalidad" y toman avances reales o incluso innovadores como mundanos o poco notables en retrospectiva, después de logrados, es decir, minimizados o minimizados. Esto se capta altamente en esta pregunta en la forma en que los algoritmos pasan de la I + D al "despliegue". citando al autor de la pregunta en comentarios posteriores:

De hecho, una fracción insignificante de todo el código que se escribe está implementando cualquier cosa que sea interesante desde un punto de vista algorítmico.

pero esto es problemático y básicamente es una redefinición centrada en TCS de la palabra "algoritmo". presumiblemente los algoritmos interesantes están avanzados. ¿eso significa que si un problema se reduce a un algoritmo avanzado, ya no es "interesante"? y "avanzado" es claramente un objetivo en movimiento. así que hay una manera de definir "algoritmos" de forma restringida o amplia . parece que la definición de TCS cambia en el contexto, pero tenga en cuenta que incluso en TCS, hay una tendencia hacia la definición amplia, por ejemplo, en la llamada "lente algorítmica" .

¡a veces los algoritmos más ubicuos también son los más pasados ​​por alto! Internet y WWW es un gran entorno / casi ecología para algoritmos. todavía relativamente joven, con solo alrededor de 2 décadas (inventado ~ 1991), ha crecido de manera masiva y exponencial en un corto período de tiempo. El crecimiento del sitio WWW probablemente incluso ha superado la famosa ley exponencial de Moores.

Internet / WWW son compatibles con muchos algoritmos sofisticados. Internet tiene algoritmos de enrutamiento complejos integrados en los enrutadores (de nuevo alimentando a corporaciones multimillonarias como Cisco). alguna teoría avanzada es aplicable allí, por ejemplo, en algoritmos de enrutamiento . Estos algoritmos fueron objeto de investigación emergente, avanzada / de vanguardia hace décadas, sin embargo, ahora tan bien afinado y bien entendido que es algo invisible.

No debemos olvidar tan pronto que hace décadas, los principales investigadores ni siquiera estaban seguros de si el mundo de Internet funcionaba o si era posible (visto en la investigación inicial de cambio de paquetes, un nuevo patrón de diseño radical en el momento que se alejaba del cambio de circuito anterior), y Incluso hace unos años, existía el temor de que no se escalara en algún momento y comenzara a fallar debido a picos abrumadores en el volumen.

También utiliza detección / corrección de errores sofisticados . Internet probablemente sea el sistema más grande y tolerante a fallas jamás construido por humanos, aún en crecimiento.

A continuación, hay un caso sólido para hacer que los algoritmos que alimentan la WWW sean avanzados. Los servidores HTTP y web están altamente optimizados y también utilizan protocolos avanzados de seguridad / cifrado (HTTPS). La lógica de representación de una página web se ha vuelto extremadamente avanzada en HTML5 y CSS3 , junto con el lenguaje de programación Javascript .

el CSS relativamente nuevo tiene varios principios similares a la programación OOP , como la reutilización y la herencia. Hablando de composición tipográfica, TeX es un importante sistema de composición científica internamente complejo (no muy diferente a un lenguaje de programación) inventado por Knuth que ahora se puede representar en páginas web (y se utiliza en posiblemente cientos de miles de artículos científicos o más).

Otra área relativamente nueva de algoritmos que se construye en Internet, aún emergente, los basados ​​en la inteligencia colectiva . El software stackexchange en sí mismo es un ejemplo de un sofisticado sistema de inteligencia colectiva. Las redes sociales también exhiben las características clave de la inteligencia colectiva y se agregan continuamente características para aumentar esa inteligencia (por ejemplo, los "Me gusta" de Facebook tienen solo unos pocos años). El campo de los sistemas de calificación se basa en algoritmos de filtrado colaborativos y sigue evolucionando en función de nuevas investigaciones y aplicaciones.

en resumen, todos los éxitos revolucionarios que transforman la experiencia humana diaria en realidad van mucho más allá de los "objetivos de campo". Como dice el título de la pregunta, todos los algoritmos centrales implementados . ahora tan ubicuo e invisible como para ser algo así como la expresión de TI, "parte de la fontanería".

Un algoritmo increíblemente exitoso (hardware) es el reinicio de encendido.

Sin un sistema por el cual una computadora está en un estado conocido cuando se aplica energía, nada más sucede correctamente .

El reinicio de encendido es la razón por la cual todo funciona que tenga una CPU, ya sea que se considere integrado o no.

La próxima vez que esté en el abrevadero para programadores y científicos de la computación, levante su vaso de refresco de cereza para reiniciar el encendido.