¿Cómo diseñas un algoritmo?

El primer paso es definir claramente el problema. Por lo general, se puede capturar con dos preguntas: ¿Cuáles son las entradas? ¿Cuáles son los resultados? En otras palabras, ¿qué información tiene disponible antes de que comience el algoritmo y qué información desea producir antes de que finalice el algoritmo?

Una vez que sabe cuáles son, la pregunta es: ¿Qué secuencia de pasos producirá la salida deseada, utilizando solo las entradas dadas? Ese es tu algoritmo.

Es aconsejable comparar el problema con otros problemas similares que haya resuelto o haya visto soluciones. Este suele ser el caso, con tanta frecuencia que realmente no pensamos en él como “diseño de un algoritmo” aunque, técnicamente hablando, sí cuenta como tal. Cuando tienes un problema que no se reduce a algo trivial, es cuando se vuelve divertido, ahí es donde entra en juego la creatividad.

Si la salida es un número único, entonces su algoritmo probablemente se parecerá mucho a una expresión matemática. ¿Cuáles son las variables de entrada y cómo afectan el resultado? ¿Es el resultado un múltiplo de esta variable? ¿O esta variable solo actúa como un desplazamiento del número resultante? ¿O esta variable actúa como un límite superior o inferior en el resultado? Y así.

Si el resultado es una decisión, como verdadero / falso, sí / no, o detener / ir, entonces su algoritmo probablemente se verá como una expresión lógica. Nuevamente, ¿cuáles son las variables de entrada y cómo afectan el resultado? ¿Es el resultado normalmente ‘verdadero’ y está más interesado en combinaciones de entradas que lo hacen falso, o es normalmente falso, y está buscando casos que lo hagan verdadero? ¿Cuáles son las relaciones entre cada posible par de entradas? ¿Importa si alguna es verdadera o si ambas deben ser verdaderas?

Ambos son ejemplos simples, pero puede crear algoritmos más complicados combinándolos. Por ejemplo, quizás necesite tomar una decisión cuyo resultado dependa de las relaciones entre algunos números. En ese caso, use el párrafo que escribí sobre cómo llegar a una salida numérica, para obtener un algoritmo que calcule cada uno de los números que necesita, y use el párrafo sobre expresiones lógicas para obtener el algoritmo que calcula la decisión.

A veces necesita operar en una gran colección de entradas, o producir una gran colección de salidas. Por lo general, puede desglosarlos pretendiendo por un momento que las colecciones de entrada y / o salida son pequeñas, solo un elemento, y buscando un algoritmo para resolver ese problema simplificado. Luego busque una manera de resolverlo con dos elementos, y luego con una colección arbitrariamente grande de entradas o salidas.

Acabo de describir el proceso de construir algoritmos grandes a partir de pequeños, pero en la práctica la parte desafiante generalmente es al revés: es descubrir cómo dividir un gran problema en algunos problemas más pequeños. A veces hay que mirar el problema de abajo hacia arriba, a veces es útil mirar el problema de arriba hacia abajo. A veces es útil pretender que algunas partes del problema se resuelven, cuando en realidad no lo están, porque eso te libera para escribir una solución sobre las partes restantes del problema … y luego regresas y rellenas los espacios en blanco.

Barra lateral:
Y a veces ese enfoque te muerde la cola, ya que descubres que la parte que asumiste que sería fácil, en realidad es imposible. Quizás depende de información que en realidad no tiene disponible. O depende de la información que se calcula más adelante, mediante una función que depende de la función que está intentando escribir, una dependencia circular. De vuelta al tablero de dibujo.

A veces es útil considerar no solo los pasos intermedios para resolver el problema, sino también las representaciones intermedias de los datos de entrada. Toma sus datos de entrada, los transforma de alguna manera y los usa como su nueva entrada. Este tipo de cosas generalmente se hace para obtener una mejora en el rendimiento, por ejemplo, si la estructura de datos transformada es más pequeña que la original, puede operar en menos tiempo.

Otra barra lateral:
Por ejemplo, una vez trabajé en algún software de correo electrónico, donde queríamos rechazar rápidamente mensajes cuyos destinatarios no existen. La velocidad es importante para eso, ya que a los spammers les gusta probar todas las combinaciones posibles de caracteres para generar un alias de correo electrónico, con la esperanza de que algunas de las combinaciones se realicen. La solución simple sería hacer una lista de todas las direcciones de correo electrónico de la empresa y comparar las direcciones de cada mensaje con las direcciones de la lista grande. Si la compañía tiene 10,000 empleados, eso podría funcionar. Si tiene 100,000, eso podría no serlo. Si la empresa es una universidad que proporciona buzones de correo a millones de alumnos, entonces podría haber un problema real con ese enfoque.

Afortunadamente, uno de mis compañeros de trabajo estaba familiarizado con algo llamado Bloom Filter (¿Cuáles son los tipos más comunes de Bloom Filter y cómo funcionan?). Esto le brinda una forma de ‘insertar’ una gran cantidad de cadenas en una matriz de bits relativamente pequeña. No puede extraer las cadenas originales de la matriz de bits, pero las operaciones rápidas en la matriz de bits le dirán con certeza si una cadena determinada no estaba en la colección original. Es posible que obtenga algunos falsos negativos, pero pueden hacerse lo suficientemente raros como para no importar. Fue adecuado para rechazar el spam.

Siempre ayuda tener un buen ‘vocabulario’ de algoritmos, estructuras de datos y patrones de diseño para dibujar. Cuanto mayor sea su vocabulario, más problemas podrá resolver rápidamente, ya que se reducen a problemas que ya sabe cómo resolver. O reconocerá las oportunidades para reducir los algoritmos que consumen mucho tiempo a algoritmos rápidos transformando la entrada en algo con lo que sea más fácil trabajar.

En teoría, una vez que ha definido sus entradas y salidas, tiene todo lo que necesita para encontrar el algoritmo que necesita. Pero en la práctica, es frecuente que las entradas o salidas no estén claramente especificadas. Falta algo que necesitas. O algo que le dan en realidad no significa lo que le dijeron que significaría. O, encontrará que en realidad no puede calcular la salida deseada, a partir de las entradas deseadas.

En cualquier caso, terminará necesitando negociar con las personas que proporcionan esos insumos y requieren esos productos. Aquí es donde intervienen las habilidades de las personas. En grandes proyectos de software, este tipo de cosas termina tomando la mitad o más de la semana laboral. A veces puede ser difícil lograr que todos estén en la misma página.

Crear algoritmos es probablemente la parte más creativa de la programación.

Para la gran mayoría de los problemas, las personas (en su mayoría informáticos) ya han ideado el algoritmo más óptimo.

Sin embargo, a menudo su software tiene restricciones únicas que necesitan pensar en un enfoque completamente nuevo.

Después de años de programación, comienzas a sentirte como un sabueso, en el sentido de que puedes comenzar a oler la solución a kilómetros de distancia, e intentas avanzar hacia ella. A veces es un camino falso, a veces puedes toparte con algunas cosas geniales.

John Carmack inventó este concepto de árboles espaciales binarios, una forma de particionar el espacio para gráficos 3D. Nadie había pensado en algo así antes.

Mi mayor triunfo intelectual hasta la fecha fue reinventar las “imágenes integrales” de forma independiente, en poco tiempo pensando en cómo contar píxeles iluminados en regiones rectangulares arbitrarias de un mapa de bits monocromo.
¡Es el mayor apuro de la historia!

Para volver a su consulta original, hay algunas cosas básicas en las que debe pensar al “inventar” algoritmos:

1) Divide y vencerás: ¿se puede resolver el problema para una parte de los datos y luego adaptarlo de alguna manera para todos los datos?
2) La ordenación o la indexación basada en árboles binarios de alguna manera ayuda: una gran cantidad de algoritmos son posibles si puede ordenar o mantener el orden a través de índices o árboles.
3) ¿Cómo lo harías como humano? ¿Puedes adaptar ese enfoque a los programas?
4) ¿Puedes ver el problema desde una perspectiva matemática diferente, digamos geometría o álgebra lineal?
5) ¿Cuál es el trabajo real que se realiza? Esto ayuda a comprender los límites computacionales y si su técnica potencial realmente está haciendo todo ese trabajo; por ejemplo, para mí fue muy obvio desde el primer día que la clasificación de números estaba limitada por N log N. Obviamente, debe observar cada número, y necesitas mirar cada dígito de cada número.
6) ¿Cuál es el paradigma de su lenguaje de programación? ¿Cómo influye en la forma en que se tratarán las cosas? ¿Qué herramientas existen en el idioma / biblioteca para facilitar su solución?

Es como escribir una receta, al más elegante estilo francés, para un cocinero sub-imbécil que nunca ha estado en una cocina antes, para que lo hagan exactamente bien cada vez.

Debe pensar en su problema y seguir dividiéndolo en fragmentos más pequeños que puede convertir en operaciones más simples. Siga haciendo esto hasta que pueda expresarlo en una sola declaración / función del lenguaje de programación deseado.

Tenga en cuenta que los lenguajes de programación han evolucionado para que los fragmentos encontrados con frecuencia se puedan expresar de la manera más simple posible. Por ejemplo, multiplicar 2 × 3 una vez requirió la aplicación de un algoritmo que aprendió en la escuela primaria; ahora el lenguaje de programación lo convirtió en un fragmento simple (comúnmente “2 * 3”) para usted.

Python es un gran ejemplo de un lenguaje que ha alcanzado un nivel muy alto de expresibilidad (o “elegancia”), lo que significa que los fragmentos históricamente comunes encontrados en una gran cantidad de problemas se expresan de manera muy simple. Es una de las razones por las que no encuentra el problema de los algoritmos tanto en Python en comparación con C. Python pone 50 años de experiencia de programación acumulada comprimida en una sintaxis claramente definida.

Pero como pones esta pregunta en “Matemáticas”, puedes probar el lenguaje Haskell.