¿Por qué son importantes las pruebas para estudiar algoritmos y estructuras de datos? ¿Estudiar esas pruebas complejas es realmente necesario?

Aquí hay algunas razones por las que deberías considerar estudiar las pruebas (ten en cuenta que vengo de esto como un informático que trabaja en algoritmos, no como programador):

• A veces, los algoritmos (especialmente los simples) pueden parecer tan simples que parecería que implementarlos es una especie de “magia”. Especialmente puedo decir esto para algoritmos como los algoritmos sin bucle (utilizados para generar objetos combinatorios), que tienden a tener una estructura simple, pero están muy involucrados con la combinatoria. La prueba a menudo como lo han dicho otros, el “por qué” y el “cómo”. A veces esto requiere cierta madurez matemática, por lo que comenzar con algoritmos más básicos ayudará mucho a construir una perspectiva matemática sólida para explorar algoritmos.
• Del mismo modo, los algoritmos a veces pueden ser muy complicados. A veces (especialmente en la literatura) el algoritmo en sí está enterrado en una prueba. Por lo tanto, comenzar a enfocar los aspectos formales de la informática es importante si desea permanecer con el “estado del arte” con algoritmos. CLRS hace un buen trabajo al particionar el algoritmo de sus pruebas. También tenga en cuenta que hay un montón de algoritmos en ese libro, por lo que, por supuesto, habría toneladas de pruebas. Si no tiene una prueba de que el algoritmo funciona, la ira del escepticismo dependerá de si su algoritmo realmente funciona, ya que queremos algoritmos que funcionen. Cualquier análisis complementario también es útil para que pueda comparar algoritmos o ver dónde están los pros y los contras de cada algoritmo (si corresponde).
• Un algoritmo es una descripción formal (matemática); se supone que es inequívoco después de todo. Dicho esto, el diseño de algoritmos (en particular el área de Algoritmos) en sí mismo es inherentemente matemático. Sería una buena práctica estudiar las pruebas y ver por qué funcionan los algoritmos. Saber cómo y por qué funciona un algoritmo a menudo está en la prueba, lo que puede brindarle una mayor comprensión si elige implementarlo (y cómo debería hacerlo).
• Este punto se relaciona fuertemente con mi segundo punto. Muchas veces un algoritmo se basa en un teorema o idea. A veces es posible encontrar algoritmos que están en lugares no claramente etiquetados como algoritmo, sino como un teorema (entonces el algoritmo está enterrado en él). Obtener cualquier tipo de práctica lo ayudará a encontrarlos.

Podría continuar, pero creo que vale la pena mencionar estos puntos (y similares a otros puntos hechos por otras respuestas).

¡Que tengas un hermoso día!

Creo que la Lección Tres de las Diez lecciones de Gian-Carlo Rota hace un trabajo decente al responder esta pregunta.
Lección tres: En general, “saber cómo” es más importante que “saber qué”.

Cuando haces cosas que no se han hecho antes o intentas hacer que algo funcione de una manera ligeramente diferente, saber que el algoritmo x se ejecuta en O (y) no te ayuda mucho en comparación con entender por qué.

Supongo que la respuesta real depende de usted y de sus propósitos, pero personalmente siempre me ha resultado bastante difícil aceptar las cosas que se transmiten del cielo en pequeños paquetes.

Revelación completa: estudié matemáticas y el profesor Rota enseñó matemáticas, así que tal vez no somos la multitud adecuada para determinar el valor de las pruebas esotéricas.

Personalmente, diría que no se requeriría una comprensión detallada de las pruebas. La mayoría de las veces es fácil demostrar la complejidad / corrección de su algoritmo. Sin embargo, las ideas de estas pruebas podrían ser aplicables en el futuro, cuando deba probar la complejidad / corrección de su propio algoritmo “complejo”.

Voy a caminar por una línea muy fina aquí cuando digo:
Depende.

No saque esto de contexto. La regla general es que cuando estudias las cosas, es mejor que te asegures de entender cada cosa sobre un algoritmo. No hay margen de error, ya que la prueba de un algoritmo es el único indicador de que lo que usted (u otros) han desarrollado es correcto. Esto se aplica tanto si es un teórico como si está interesado en aplicar el algoritmo.

Pero en lo que respecta a la aplicación, probablemente tendrá más preocupaciones que tratar de comprender la mecánica de un algoritmo. Con toda probabilidad, esto es simplemente un pequeño engranaje en una vasta maquinaria que vas a desarrollar. Entonces, esto es lo que importa entonces: es mejor que se asegure de que este es un algoritmo bien conocido y bien estudiado, y que hace exactamente lo que desea usar como subrutina.

El último caso no es un requisito menor. Es posible que no tenga que pasar por la mecánica interna, pero aún necesita conocer el principio detrás del algoritmo. No tiene que derivar el resultado para estar convencido, pero debe ser una tarea estándar, o debe haber sido verificado por revisión por pares (aunque me condenaría si sé quién revisa las revisiones por pares) . Por lo tanto, asegúrese de usar Quicksort aleatorio todo lo que quiera sin tener que preocuparse por la mecánica, pero si alguien le pregunta cuál es el algoritmo básico, debe saber qué responder.

Y probablemente debería darle un mejor ejemplo que Quicksort aleatorizado, que espero que todos sepan. Pero considera esto. El algoritmo de coincidencia máxima de Micali y Vazirani es relativamente complejo. Es una variación del algoritmo original de Edmond, pero tiene todos estos pequeños detalles en los que es diferente. A menos que esté trabajando específicamente en coincidencias gráficas, cortes o flujos, probablemente nunca tendrá que pasar por la prueba. Pero este es uno de los algoritmos más utilizados en el mundo. Así que debes saber esto: el algoritmo es una variante del algoritmo de Edmond (que debes saber), se ejecuta a tiempo [matemáticas] O \ left (| E | \ sqrt {| V |} \ right) [/ math], y puede extenderlo a coincidencias ponderadas.

En forma aislada, las pruebas no son tan importantes como el algoritmo o la estructura de datos. Pero las pruebas son importantes cuando está utilizando un algoritmo específico (o estructura de datos) para resolver un problema, posiblemente con los ajustes necesarios para trabajar con el problema real. ¿Cómo demuestras que tu solución es correcta? La verificación a través de la implementación práctica no siempre es posible o es costosa. Por lo tanto, demostrar que la solución es correcta genera una serie de pensamientos (que se convierten en afirmaciones) que deben validarse.

Sí, se requiere estudiar esas pruebas. Si eres como yo, los encontrarás aburridos como en la mayoría de las teorías. Sin embargo, no comprendería en profundidad cómo algunas estructuras de datos y algoritmos ayudan a la optimización hasta el momento en que comprende el “cómo”.
Una cosa que hago es saltear las pruebas en la primera lectura y llegar a las partes prácticas. Eso me mantiene comprometido. Después de un tiempo, puedo probar algunos de los teoremas yo mismo o vuelvo a ellos cuando veo que pueden ser necesarios para avanzar en un concepto más avanzado.