Algoritmos centrales desplegados

307

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.

Manu
fuente
Los comentarios no son para discusión extendida; Esta conversación se ha movido al chat .
Bjørn Kjos-Hanssen

Respuestas:

473

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 .
También existen tales estructuras de datos y algoritmos en el código de terceros incluidos en el código de Chromium.

  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.

Vijay D
fuente
55
@HuckBennett, CDCL es un algoritmo parametrizado por la heurística, pero no es en sí mismo una heurística. Tiene un comportamiento exponencial en el peor de los casos, pero no es trivial mostrar eso. Además, no podemos hacerlo mejor y es lo mejor que podemos hacer en la práctica, ¡así que creo que todos los informáticos deberían saberlo! En cuanto a LRU, FIFO, etc., son heurísticas, pero, como con ARC, pueden requerir algoritmos inteligentes o estructuras de datos para implementar.
Vijay D el
99
¿No se aplicaría tal comentario a Simplex: inicialmente no se entiende bien y luego se demostró que es exponencial, pero funciona en la práctica y mucho más tarde se demostró que tenía una complejidad suavizada polinómica? CDCL es interesante para el análisis de algoritmos porque necesita pasar por la complejidad de la prueba para derivar familias de fórmulas que exhiben el peor de los casos, y también para mostrar que puede ser exponencialmente más sucinto que algunas variantes de resolución. Hay varias extensiones, como la ruptura de simetría y las técnicas de autarquía para las cuales dicho análisis aún está abierto.
Vijay D
28
Esto es un tesoro para un estudiante
neo1691
2
@EmanueleViola, he agregado algunos ejemplos más. La publicación es larga ahora, así que no quiero extenderla. Tal vez debería hacer una nueva pregunta específicamente sobre implementaciones de filtros Dijkstra, Simplex, Bloom como parte de un sistema real como Linux, Chrome, un servidor web, etc. Creo que es más probable que obtenga buenas respuestas si es específico.
Vijay D
44
Noticias de hackers y r / programación.
Vijay D
40

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

Mkπ0kπ0M

Huck Bennett
fuente
77
No creo que este sea un material de algoritmos típico.
Manu
14
Por cierto, primero aprendí sobre PageRank en una clase de algoritmos. De hecho, creo que el profesor lo eligió porque era un buen ejemplo de "algoritmos utilizados en la práctica". Si limita los ejemplos al material de tipo "primera mitad del CLRS", la lista de ejemplos será demasiado larga o demasiado trivial: la clasificación rápida, los árboles B y el algoritmo de Dijkstra son omnipresentes.
Huck Bennett
2
Enseñamos PageRank a estudiantes universitarios.
Aaron Roth el
66
También se lo enseño a estudiantes universitarios (tanto en la clase de algoritmos requeridos como en una clase de algoritmos de gráficos más especializados).
David Eppstein el
2
Aprendí PageRank como estudiante de una asignatura optativa.
Vijay D el
33

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 ).

vb le
fuente
La "investigación de economía y operaciones" no es lo suficientemente específica. CPLEX tampoco es el tipo de ejemplo que estaba buscando, ya que es solo una implementación del algoritmo; sería diferente si, por ejemplo, el compilador gcc usara el método simplex.
Manu
12
Creo que los "problemas de programación lineal" son lo suficientemente específicos cuando hablamos de economía y OR. Además, por CPLEX me refería al algoritmo detrás de la implementación.
vb le
16
"En la actualidad, la mayoría de las grandes empresas utilizan la programación lineal para fijar el precio de los productos y administrar las cadenas de suministro. Las empresas de transporte lo utilizan para elegir la forma más económica de consolidar, coordinar y enrutar los envíos de muchos productos de proveedores distribuidos globalmente a mercados distantes sujetos a limitaciones de capacidad. El petróleo la industria lo usa para exploración, mezcla, programación de producción y distribución. La industria del hierro y el acero lo usa para evaluar minerales de hierro, explorar la adición de hornos de coque y seleccionar productos ... " news.stanford.edu/news/2005/may25/ dantzigobit-052505.html
Sasho Nikolov
Gracias. Pero la cita me parece terriblemente vaga. Creo que si digo que frente a una clase de estudiantes, la mitad se quedaría dormida ;-) Sería diferente si dijéramos algo como: UPS usa LP para enviar paquetes de la siguiente manera ... No estoy diciendo tales ejemplos son triviales de encontrar, pero dado que "la mayoría de las grandes empresas usan LP", espero que al menos podamos señalar una .
Manu
10
Fuera de mi cabeza, desde 2007 LAX (el aeropuerto) ha utilizado software para resolver los juegos de Stackelberg para programar el personal de seguridad. Resolver grandes LPs es parte de todo el asunto, ver, por ejemplo, teamcore.usc.edu/ARMOR-LAX . Además de eso, le preguntaría a alguien de su departamento de Investigación de Operaciones: generalmente tendrían muchas historias de guerra sobre el uso de LP en la vida real
Sasho Nikolov
30

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.

mhum
fuente
No estoy seguro de que el matrimonio estable sea un material típico de algoritmos.
Manu
16
Está en el libro de Diseño de Algoritmos de Tardos y Kleinberg, y también en los Algoritmos Aleatorizados de Motwani, y ambos libros son ampliamente utilizados. Es posible que el matrimonio estable no se enseñe universalmente en cursos de algoritmos, pero ciertamente se enseña en muchos de ellos.
Sasho Nikolov
10
Una búsqueda rápida revela que ha aparecido en CS70 de Berkeley , MIT de 6.042 , de UMD CMSC451 , etc ...
mhum
1
Curiosamente, cuando agrega tareas conyugales, el problema se completa con NP: arxiv.org/abs/1308.4534 . Sin embargo, en la práctica esto parece no causar demasiado problema: en.wikipedia.org/wiki/…
Joshua Grochow
2
@EmanueleViola, aunque podría no estar cubierto tradicionalmente, su inclusión en el libro Kleinberg / Tardos lo ha hecho más popular (¡y si no debería serlo!)
Suresh Venkat
24

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.

mhum
fuente
1
Y recibí una conferencia sobre la codificación de Huffman como estudiante universitario, que era necesaria para un proyecto.
Brian S
Huffman está en uno de los primeros capítulos de CLRS, por lo que definitivamente debería calificar
Sasho Nikolov el
21

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.
Dai Le
fuente
19

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)

Suresh Venkat
fuente
Creo que esto se puede enseñar pero no se enseña ampliamente.
Manu
3
Desafortunado, pero cierto. Sin embargo, las variantes de LSH (como el boceto Count-min y parientes) comienzan a aparecer en los cursos de "datos grandes" o "minería de datos". Enseño filtros de floración en mi clase de algoritmos, por ejemplo.
Suresh Venkat
Como experiencia personal, LSH no se ajustó para nosotros en una instancia de "big data" (elementos de 100 mln).
linxoide
1
@lynxoid que es una discusión / pregunta por separado :). Hay suficientes ejemplos en los que no funciona de esa creo que es relevante para esta pregunta en particular.
Suresh Venkat
18

ε

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.

Sasho Nikolov
fuente
1
Grandes ejemplos (aunque no es algo básico en este momento).
Manu
16

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!

Joshua Grochow
fuente
Además, se utiliza una versión más simple de estos algoritmos para intercambiar juegos de mesa: okasaki.blogspot.co.uk/2008/03/what-heck-is-math-trade.html
Radu GRIGore
15

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 ".

Grigory Yaroslavtsev
fuente
13
  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
MSalters
fuente
A * también se enseña con frecuencia en el diseño de juegos. No creo que los juegos 3D modernos usen generalmente A * para la navegación NPC, pero los juegos 2D / isométricos, así como los juegos más antiguos, hacen uso del algoritmo.
Brian S
@BrianS ¿Conoces ejemplos de algoritmos de búsqueda de caminos utilizados en juegos 3D, específicamente NPC enemigos en juegos (como un juego de disparos npc) Recuerdo haber leído algo como ... dividir un mapa en sectores hexagonales y usarlo como nodo, en lugar de cuadrados , y eso permitió un movimiento más suave.
Goodwine
@Goodwine, lo siento, no tengo ejemplos del mundo real de algoritmos de pathfinding en juegos 3D. Mi experiencia personal ha sido con entornos parecidos a "cubos" (mapa hecho de cubos en los que se paran los personajes, básicamente 2D, a pesar del renderizado 3D) y AI falsos utilizados para probar los personajes de los jugadores.
Brian S
12

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.

Chandra Chekuri
fuente
Voy a echar un vistazo, pero no suena como material típico de algoritmos.
Manu
8
Hmm, el redondeo aleatorio generalmente se enseña en cursos de algoritmos de nivel de doctorado, ¿no?
Chandra Chekuri
2
¿Por qué solo redondeo aleatorio? Sanjeev Arora, Elad Hazan y Satyen Kale piensan que incluso el método de actualización de pesos mulplicativos es lo suficientemente básico como para ser enseñado a nivel UG :) "Creemos que nuestro meta algoritmo y su análisis son lo suficientemente simples y útiles como para ser vistos como una herramienta básica enseñó a todos los estudiantes de algoritmos junto con divide y vencerás, programación dinámica, muestreo aleatorio y similares ". (cf. cs.princeton.edu/~arora/pubs/MWsurvey.pdf ).
Jagadish
10

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.

Oakad
fuente
10

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.

vzn
fuente
10

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.

linxoide
fuente
¿Está seguro de que TSP es el problema que las empresas de paquetería están tratando de resolver? Pensé que un desafío práctico más grande era la mochila y otros tipos de problemas de embalaje.
András Salamon el
Las asignaciones para los conductores cambian todos los días (es decir, UPS Guy no necesita visitar la misma casa todos los días), por lo que las rutas deben actualizarse diariamente. No es un TSP puro: hay restricciones adicionales, como calles de un solo sentido, sin vueltas en U, entregando paquetes en un lado de la calle, pero no en el otro.
linxoide
Sin embargo, estoy seguro de que empacar también es importante.
linxoide
9

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.

Alnitak
fuente
8

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.]

vzn
fuente
La segunda referencia es originalmente de enero / febrero de 2000 de Computing in Science & Engineering, una publicación conjunta del American Institute of Physics y la IEEE Computer Society. compilado por los editores invitados Jack Dongarra del Laboratorio Nacional de la Universidad de Tennessee y Oak Ridge y Francis Sullivan del Centro de Ciencias de la Computación del Instituto de Análisis de Defensa
vzn
7

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

Darth Egregious
fuente
2
Sería bueno si pudieras apuntar a un uso específico. Algo así como MS Word usa KMP.
Manu
6

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

usuario19461
fuente
44
Ordenar no es un algoritmo. Es una tarea, es decir, algo que desea realizar, para lo cual debe diseñar (o, en la práctica, elegir) un algoritmo.
David Richerby
Estos no parecen ser ejemplos específicos según lo solicitado en la pregunta.
Kaveh
SGBD == RDBMS FYI para aquellos que no lo sabían.
Autodidacta
6

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 .

Leeor
fuente
6

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.

ClérigoGunem
fuente
5

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.

TimRing
fuente
2

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.

Ravi Kiran
fuente
-2

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.

vzn
fuente
-3

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

Wes Turner
fuente
¿Cómo es este un ejemplo de "algoritmos centrales ... implementados en software / hardware comercial, gubernamental o ampliamente utilizado"?
David Richerby
Sería útil hacer una referencia cruzada de las implementaciones de cada uno de los excelentes algoritmos enumerados en otras respuestas aquí a Wikipedia / DBpedia URI. No hay URI de Wikipedia / DBpedia para todos estos algoritmos; pero hay páginas de Rosetta Code.
Wes Turner
bigocheatsheet.com también enumera la complejidad de Big-O y enlaces a artículos de Wikipedia para bastantes algoritmos.
Wes Turner
La pregunta pide ejemplos de algoritmos centrales utilizados en piezas importantes de software. "Aquí hay un sitio web con algoritmos implementados en un millón de idiomas" no responde a esa pregunta en absoluto. De hecho, es exactamente lo contrario de lo que busca la pregunta.
David Richerby
Una referencia útil, contextualmente relevante, no obstante.
Wes Turner
-5

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".

vzn
fuente
Se podrían agregar muchas citas a esto. Aquí hay uno para comenzar: DARPA y la revolución de Internet por Waldrop
vzn
otra referencia sobre la optimización de internet, biografía de Danny Lewin , cofundador de akamai, "el genio que transformó internet"
vzn
-8

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.

Luego
fuente
55
El reinicio de encendido no es un algoritmo. Es una tarea, es decir, algo que desea realizar, para lo cual debe diseñar un algoritmo.
David Richerby