Los algoritmos están escritos para ser ejecutados por una computadora, pero el análisis de algoritmos es teórico. ¿Es posible comprender completamente un algoritmo (sin implementarlo) solo leyendo estos famosos libros de Knuth, CLR, etc.

Answer 1

¡Absolutamente! Sin embargo, probablemente necesitará mucho lápiz y papel.

Tomemos un ejemplo simple, digamos merge sort. Puede tomar una lista, ejecutar el algoritmo para ver cómo funciona, convencerse de que el invariante se mantiene e incluso probarlo formalmente. Y de hecho es importante hacer todos estos ejercicios.

Sin embargo, en una situación de la vida real, puede encontrarse en una situación en la que está tratando de ordenar miles de millones de enteros. ¿Puedes simplemente ejecutar un algoritmo de clasificación en memoria de libros de texto? ¡No! Es posible que deba dividir su entrada en varios archivos, pensar en algo que implique varios montones, o tal vez incluso usar algo similar a Map-Reduce. Es posible que no todos sus aportes lleguen simultáneamente, por lo que es posible que también tenga que explicar eso. Quizás pueda explotar ciertas propiedades de sus datos para facilitar su tarea (por ejemplo, podría estar tratando con un dominio restringido de números). Otro ejemplo es un escenario en el que intenta resolver un tipo de problema de optimización o programación. Es posible que no sea factible, ni siquiera necesario, obtener la solución matemáticamente óptima, ya que podría estar lidiando con un problema de NP completo. Tal vez su cliente esté de acuerdo con algo razonablemente cercano (dentro de límites comprobables) a la solución óptima, siempre y cuando se ejecute increíblemente rápido. Y hay varias heurísticas que pueden ayudar con eso. Es probable que un libro de algoritmos estándar no tenga la respuesta exacta para su situación única, pero ciertamente lo equipará para pensar en su problema y encontrar una solución, o saber dónde buscarla (porque seamos sinceros, la mayor parte En ese momento, alguien ya lo resolvió y lo publicó en línea :))!

En cuanto a su segunda pregunta, “¿Es necesario ser un buen programador para ser bueno en algoritmos?”, No creo que necesite acercarse a una computadora para ser bueno en algoritmos. Muchos de los “grandes éxitos de algoritmos” que todos aprendemos en nuestro curso estándar de Algoritmos UG fueron concebidos por personas como Knuth, Dijkstra, Hoare, Tarjan, etc., quienes ni siquiera tenían una fracción de los recursos informáticos que tenemos hoy a su disposición. . ¡Sin embargo, no les impidió pensar con mucha anticipación! Un algoritmo es simplemente un conjunto de pasos matemáticos precisos para transformar una entrada arbitraria en una salida deseada, dadas ciertas condiciones. Realmente no es diferente de resolver un problema matemático. La mayoría de las veces, todo lo que realmente necesita es un lápiz y papel, y mucha paciencia. Si puede encontrar un buen algoritmo no trivial para resolver su problema favorito (elija el que más le guste), demuestre su corrección y analice cómo se comportaría en función del tamaño de entrada, felicidades, ¡es bueno con los algoritmos! No se requieren habilidades de programación (aparte de un conocimiento básico de las estructuras y primitivas comunes que generalmente ofrecen todos los lenguajes de programación modernos).

Answer 2

¿Si por qué no?

Hay una regla general que uso, que es: si quieres ser bueno en X, la mejor manera de aprender es practicar X. Suena obvio, pero la gente a menudo trata de decirte cosas como “es importante aprender latín en la escuela secundaria, porque realmente ayuda a entender la gramática inglesa “. Pero si ese fuera el objetivo, sería más eficiente enseñar gramática en inglés.

Lo mismo aquí: si lees Knuth, mejorarás en el análisis de algoritmos: dado un algoritmo, comprenderás bajo qué circunstancias y qué tan eficientemente puede resolver un problema particular, cuáles son sus debilidades, a menudo puedes encontrar alternativas … ¡Diría que eso ciertamente cuenta como algoritmos de “comprensión”!

Por otro lado, si quieres ser bueno en la construcción de sistemas de software concretos que hagan algo en el mundo real, entonces debes practicar eso (o cooperar con alguien que lo hizo).