Como saber entiendo totalmente un algoritmo

Bueno, la mejor manera de entender un algoritmo según mí es transformarse como un depurador , pasar por el algoritmo (ya sea pseudocódigo o algoritmo codificado), línea por línea, llamada por llamada y anotar la evolución de las variables para comprender completamente qué hace para que pueda entender cómo resuelve el problema.

Esta técnica es la mejor para mí, ya que a veces solo leer el código realmente no te da una visión clara de lo que está sucediendo. Siempre debe intentar primero con casos de prueba simples, para comprender los conceptos básicos y luego puede usar los más grandes para comprender completamente todo el dominio de entrada.

Como ejemplo, piense en el problema de la mochila. La programación dinámica no es realmente fácil de entender completamente. Aquí hay una versión de Python:

Al leer el código, probablemente no entenderás mucho, incluso si fue comentado. Sin embargo, si usted mismo revisa el código y escribe los valores de las diferentes variables después de cada llamada, ¡obtendrá la idea y la comprenderá por completo! Así es personalmente como entendí muchos algoritmos (incluida la mochila).

Para asegurarse de que lo ha entendido totalmente, puede probarse a sí mismo e intentar volver a escribirlo (sin aprenderlo de memoria, por supuesto), y por qué no codificar su propia versión, ¡lo cual es muy gratificante!

Buena suerte con eso, espero que haya ayudado. 🙂

Creo que los puntos principales que muestran que has entendido y el algoritmo son:

• Sabes lo que hace, cómo lo hace y por qué es correcto. A menos que trabaje en teoría, no creo que necesite poder escribir las pruebas formales de corrección, pero debe tener una idea de alto nivel de ellas.
• Conoce la complejidad del tiempo y puede analizar cómo cambiaría si cambia el algoritmo. Por ejemplo
  – Utilice una estructura de datos diferente: matriz en lugar de montón en el algoritmo Prims.
  – Cambiar el método de representación de datos de entrada: lista de adyacencia frente a matriz de adyacencia en gráficos.
  – ¿Los datos necesitan tener una propiedad especial? (es decir, está ordenado, tenemos una comparación entre elementos en [math] O (1) [/ math]). Un buen ejemplo de esto es un montón donde la inserción suele ser [matemática] \ log n [/ matemática] suponiendo que el tiempo para comparar dos elementos es [matemática] O (1) [/ matemática]. Si son cadenas de longitud [math] m [/ math], esto se convierte en [math] m \ log n. [/ Math]
• Puede escribir el algoritmo en pseudocódigo. Además, si usted es un programador, debería poder identificar cómo implementar el algoritmo en su idioma de preferencia
• Deberías poder explicárselo a alguien que no conozca el algoritmo. He descubierto que para enseñar algo, debes saberlo muy bien y estar preparado para cualquier pregunta que pueda tener la otra persona.

Para estar en un estado de comprensión total de cualquier algoritmo, ¡debes estar en modo compilador! Cualquier algoritmo implementado correctamente tendrá un comportamiento universal en todos los jueces de programación (compiladores), incluido usted, ya que ahora es un compilador 🙂 Pruebe algunas cosas para verificar cuán efectivo es un compilador:

• Analice la complejidad (tiempo y espacio) del algoritmo en los mejores, peores y promedio casos.

• Tome algunos casos de prueba predefinidos así como diseñar sus propios casos de prueba (lo más importante) y ejecutar en seco el algoritmo sobre ellos.

• Intente enseñar ese algoritmo a cualquiera de sus compañeros y verifique su respuesta. Aprenderá mucho mientras enseña a otros.

También puede buscar la otra implementación de la vida real del algoritmo que lo ayudará a comprender y relacionarse fácilmente.
Espero que seas un buen compilador 🙂

Antes de continuar, creo que es importante examinar su pregunta. ¿Qué está tratando de hacer aquí?

1 – ¿Estás tratando de entenderlo por interés? ¿Y quizás aplicarlo en un problema mayor?

2 – Eres un estudiante de CS y lo necesitas para aprobar tus exámenes.

3 – Usted se encuentra en un entorno restringido en particular y debe implementar sus efectos en dicho entorno a dichas restricciones.

4 – ¿Estás tratando de reinventar la rueda por el bien de ella? En otras palabras, no hay motivación que conduzca a dicha reinvención.

5 – Recuerda y regurgita más tarde para impresionar a los demás.

Si la motivación radica en el alcance descrito a través de 4 o 5, probablemente debería olvidarlo y proceder a reenfocar su atención en otra parte. Debido a que ha fallado el caso base y es lógicamente irrelevante continuar la discusión inductivamente.

Si es 2, entonces aquí están mis condolencias. Todos tenemos que pasar por eso.

Si es 1 y 3, entonces estás en el camino correcto.

Para mí, la comprensión de un algoritmo es saber qué tipo de problema está tratando de resolver y por qué se ha elegido resolverlo de esa manera. Es decir, su motivación es la clave para comprender el algoritmo en sí. Luego se reduce a conocer su complejidad de tiempo y espacio, el promedio y el peor caso del algoritmo. El costo que paga y sus compensaciones, ningún algoritmo es perfecto AFAIK. Después de eso, se trata de dónde aplicarlo. La implementación es solo detalles y varía de un autor a otro y del entorno. Pesudo códigos para algoritmos comúnmente conocidos están en su mayoría fácilmente disponibles.

Una cosa de la que me he dado cuenta es que, a menos que esté buscando un doctorado o tratando de resolver un problema no resuelto de manera más efectiva, como decir una recuperación diferida efectiva con una penalización de bajo rendimiento en C ++ (es decir, punteros de peligro), o algún tipo de variante de clasificación GPGPU por aprovechando las propiedades conocidas de algún algoritmo y paralelizándolo, no hay otras razones para “entender” un algoritmo más que sus aspectos y sus pequeños problemas que ya se han dicho. Como ya están probados, la corrección no es un problema. El diablo radica en cuán cuidadoso es al seguir el código pesudo, lo que debería ser fácil si conoce bien el idioma que está utilizando. Después de lo cual, la única forma de averiguarlo es escribir pruebas de controladores para probar la corrección de su implementación y perfilarla para ver si resuelve su problema más rápido.

Aparte de eso, debes concentrarte en resolver el problema que estás enfrentando.

La vida es simplemente demasiado corta como para desperdiciarla en volver a derivar lo que se ha derivado rigurosamente. Además, hay muchos por ahí y con diferentes variaciones, algunos bastante oscuros por naturaleza, no es posible que los entiendas y los recuerdes. A menos que sea un profesor de CS y deba enseñarles.

Los de Einstein dijeron que entiendes totalmente algo solo si logras que un niño de 5 años lo entienda.

¡Parece recursivo sin embargo! ¿Cómo sabes que el niño de 5 años lo entendió? ¿Al pedirle que se lo enseñe a otro niño de 5 años?

Pero, en una nota seria, así es como va. Si puede explicar con éxito todo sobre el algoritmo a alguien muy joven para comprenderlo, lo ha entendido.

Confía en mí, he explicado con éxito conceptos de ingeniería como la recursión y la lista vinculada a mi hermana. Puedes probarlo también.

PD: Esta no es la única forma de ponerte a prueba. Es uno de los caminos. Por supuesto, la mejor manera es implementar, hacer cambios y quizás encontrar mejores alternativas.

La manera más simple y probablemente la mejor es implementar el algoritmo y verificarlo, especialmente para los algoritmos estándar, no debería haber ningún problema para encontrar una tarea en algunos de los jueces en línea como SPOJ que dice “implementar este algoritmo” para que pueda enviar su solución y ver si pasa todas las pruebas. Por supuesto, no recomiendo que uno deba implementar todos los algoritmos a lo largo del aprendizaje porque en algún momento simplemente deja de ser el uso óptimo del tiempo, pero si para un algoritmo desea estar seguro de que comprende totalmente cómo funciona, siempre Puede suceder que creas que sabes cómo lo hubieras escrito todo, pero cuando realmente empiezas a escribir, ves que hay algunos detalles que pasaste por alto que a veces pueden convertirse en cambios bastante grandes en el código. Si lo ha escrito y obtiene un OK, sabe que entendió cómo debería funcionar, porque ha hecho que su código funcione de esta manera. Además, por supuesto, leer la prueba para comprender también por qué el algoritmo que funciona de esta manera es el correcto.

Tome todos los casos de entrada mejores, peores e inválidos. Si puede describir en qué etapa sucede lo que sucede dentro, voila, ha dominado el algoritmo.

Por cierto. Debe conocer todos los casos mejores, peores e inválidos, para poder saber si el algoritmo es una elección correcta para la tarea.

También tenga cuidado: saber cómo funciona el algoritmo y cómo se implementa podría ser dos cosas absolutamente diferentes.

En realidad, la mejor manera que uso para comprender un algoritmo es primero, tratar de alcanzar una visión completa y clara del problema que el algoritmo está escrito para resolver, incluidas las respuestas y las consultas. En segundo lugar, trato de verificar qué desventajas del enfoque de la fuerza bruta, ya que a veces puede crear algunas chispas mágicas sobre cuál es la idea básica detrás de un algoritmo. El tercer paso es leer el algoritmo de una referencia especial como libros de referencia de diseño de algoritmos (“CLRS” por ejemplo). Yo mismo tuve la experiencia con CLRS y un libro llamado “Programación competitiva”. En este paso, no trato de depurar el código; en cambio, trato de leer la idea de la referencia. Luego, en el último paso, trato de implementarlo yo mismo o depurar un código escrito. Además, dos pasos adicionales pueden brindarle una comprensión profunda del algoritmo, buscar casos especiales del problema y verificar las aplicaciones del algoritmo.

1. Escriba un conjunto completo de pruebas en algún idioma (no el que se utilizó para el código de ejemplo que leyó).
2. Implemente el algoritmo para pasar las pruebas.
3. Espere tres meses, desenterre las pruebas y vuelva a escribir el algoritmo desde cero sin mirar la fuente.

Aquí está mi método para aprender algoritmos y estructuras de datos.

• En primer lugar, trate de comprender completamente el problema.
• Resuélvelo en el papel
• Cuando esté seguro de que podría resolver eso en el papel, pase a la parte de codificación.
• Al principio intente con su propio código, si no puede resolverlo, busque un ejemplo del código de otro para practicarlo.
• Ahora vuelva a su propia versión de código u optimización, intente optimizar el código si puede.
• Toma una taza de café y celebra tu éxito

Puede implementarlo , puede usarlo y también modificarlo , y puede explicárselo a otra persona.

Intente explicar el algoritmo en su totalidad a alguien que aún no lo conoce, incluidos los detalles, como los casos límite, los tiempos de ejecución / requisitos de almacenamiento, las estructuras de datos utilizadas y las relaciones con los algoritmos relacionados. ¿Puedes responder todas las preguntas que tienen sobre el algoritmo? ¿Pueden ahora implementarlo ellos mismos? ¿Enseñarlo a alguien más incluyendo todos los detalles? Entonces supongo que lo sabes y lo entiendes totalmente.