¿Cuáles son los algoritmos más importantes que todo informático debe dominar?

Las variaciones de esta pregunta parecen surgir todo el tiempo en Quora. Por favor refiérase a la siguiente:

¿Cuáles son los mejores algoritmos en informática para dominar inicialmente?
¿Cuáles son algunos de los algoritmos más ingeniosos en informática? Bonificación si el algoritmo se ejecuta en tiempo constante.
¿Cuáles son los diez mejores algoritmos informáticos para realizar proyectos?

La pregunta se refiere a “informático”. Con suerte, eso es lo que se pretendía. De lo contrario, solo señalaría que las necesidades de un informático serían diferentes de las de un ingeniero de software o de un desarrollador de aplicaciones. No necesita “dominar” los algoritmos para aplicarlos. La mayoría de los desarrolladores no tienen que inventar algoritmos realmente inteligentes con estrategias que resuelvan rápidamente problemas especializados. La mayor parte de ese trabajo está disponible en bibliotecas de software reutilizables.

¿Qué constituye el “dominio”? En general, significaría adquirir un conocimiento o habilidad integral en un tema u oficio. Uno esperaría que un científico de la computación participara en la investigación o la enseñanza en el campo de los programas informáticos y, por lo tanto, necesitara comprender completamente todos los algoritmos principales comúnmente estudiados en el campo de la informática. Eso no necesariamente significa que tendrían que ser capaces de lanzar una versión del algoritmo en cualquier lenguaje de computadora en particular desde la memoria. Pero sí significa que deben saber para qué sirve, la estrategia que emplea, las características de rendimiento y escalabilidad de la misma, y ​​cómo se relaciona con otros algoritmos que se ocupan del mismo espacio problemático. También deben saber cómo abstraer un algoritmo de su forma concreta (en código) en una formulación matemática más abstracta.

Un ingeniero de software, por otro lado, realmente solo necesita saber cómo encontrar algoritmos que aborden el problema en cuestión, y cómo evaluar el rendimiento y las características de escalabilidad de diferentes algoritmos que se consideran como una solución. Si el algoritmo no está disponible en una biblioteca, entonces deberán poder traducirlo de una descripción abstracta a un lenguaje de programación específico. Por supuesto, un conocimiento profundo del diseño de algoritmos podría ser beneficioso para un ingeniero de software, especialmente si se enfrenta con la necesidad de adaptar un algoritmo o inventar uno nuevo.

Para resumir, un informático necesita “dominar” todos los algoritmos que encontraría en un libro de texto. Un ingeniero de software generalmente no tiene que “dominar” ninguno de ellos.

Reduzcamos esto a algunas técnicas esenciales de bajo nivel que necesita para aprender a escribir programación de tipo secuencial.

(1) Bucles de control
Cómo empezar. Cómo salir Donde poner el mostrador.

(2) Intercambio
Necesitas intercambiar dos valores. Necesita una tercera variable “temp” para hacer eso.

(3) Clasificación
A veces las cosas necesitan estar para funcionar.

(4) Pruebas de coincidencia (más difícil si las cosas que coinciden no son exactas)

(5) Creación de estructura
Construye una lista. Construye un árbol. Llena una mesa. (y otros tipos de estructura)

Las técnicas más comunes que he utilizado implican la manipulación de datos de la base de datos, la mayoría de ellos históricos. Gran parte de esto es coincidencia de patrones, análisis de campos, fusiones por campo clave, extracción y asignación de códigos y conversiones de formato (fechas, etc.).