(¿Casi todo? Bucles, recursión y memorización. Los problemas de gráficos son probablemente el ejemplo más fácil. Los problemas de gráficos NP tienen soluciones ridículamente fáciles: fuerza bruta y compare todas las soluciones posibles. Pero vemos que “lo más genérico es más simple” incluso en su familia más estrecha.
Tome su primo más simple y conocido, usando el algoritmo de Dijkstra en un gráfico donde todos los bordes tienen pesos de borde positivos (> 0). Dijkstra puede requerir cien o más líneas de código y utiliza estructuras de datos más avanzadas que sus abuelos NP. El algoritmo Bellman-Ford, más versátil, maneja más tipos de gráficos que los de Dijkstra y utiliza estructuras de datos menos sofisticadas. Y en la mayoría de los idiomas debe ser al menos la mitad del código. Y de nuevo, el algoritmo Floyd-Warshall es más general e incluso más simple. En algunos idiomas, Floyd-Warshall tiene menos de diez líneas de código, mientras que su primo menos genérico Dijkstra puede requerir 100 o más (sin incluir el código que rodea la implementación, como la estructuración de gráficos, io, etc.).
Nuevamente, viene el ejemplo de CS de primer año. Son tortugas hasta el fondo en informática. Los algoritmos de ordenación de matriz / lista son otro ejemplo. Los más genéricos son fáciles y rápidamente codificables para la mayoría de las personas con un BS en CS. Puedo programar docenas de algoritmos de clasificación de matriz O (nlogn) y O (nlogn) y O (n!) En unos minutos. Los menos genéricos, aquellos que también tienen complejidad de tiempo de ejecución O (n) o sub O (n), pueden desafiar a aquellos con un doctorado en CS y pueden tomar un día para que se codifiquen.
- ¿Por qué debería aprender las matemáticas detrás del aprendizaje automático?
- ¿Cuáles son las formas de paralelizar los códigos Python y NumPy?
- ¿Qué NIT es mejor para CS?
- ¿Cuál es la importancia o los beneficios de un algoritmo informático para una persona normal que no es un programador informático?
- ¿Cómo se puede resolver la enfermedad de la realidad virtual?
