algorithm - muse - Cómo cultivar la intuición de algoritmo?

algorithms book (6)

Cuando me enfrento a un problema en el software, generalmente veo una solución de inmediato. Por supuesto, lo que veo suele ser algo desalentador, y siempre tengo que sentarme y diseñar (reconozco que normalmente no diseño lo suficiente), pero obtengo una cierta intuición de inmediato.

Mi problema es que no tengo esa misma intuición cuando se trata de algoritmos avanzados. Me siento mucho más para la tarea de construir otro Facebook y luego construir otra búsqueda de Google o un proyecto de Music Genom . Probablemente sea porque he estado desarrollando software por bastante tiempo, pero tengo poca experiencia en la composición de algoritmos.

Me gustaría que los consejos de la comunidad sobre qué leer y qué proyectos emprender para mejorar la composición de algoritmos.

(Esta pregunta no tiene nada que ver con la composición algorítmica . Bueno, casi nada)

dominio del problema

Primero debes entender el dominio del problema. Una solución elegante al problema equivocado no sirve, ni es una solución ineficiente al problema correcto en la mayoría de los casos. La calidad de la solución, en otras palabras, es a menudo relativa. Un simple problema de programación que tiene una solución determinística que demora diez minutos puede ser correcto si los cronogramas se realizan una vez por semana, pero si los cronogramas cambian varias veces al día, puede ser necesaria una solución de algoritmo genético que converja en unos segundos.

descomposición y mapeo

Segundo, descomponga el problema en sub-problemas y elementos conocidos / desconocidos que corresponden a los elementos de la solución. A veces esto es obvio, por ejemplo, para contar widgets necesita una forma de identificar widgets, un contador incrementable y una forma de almacenar el conteo. A veces no es tan obvio. A veces hay que descomponer el problema, el dominio y las posibles soluciones al mismo tiempo y probar varias asignaciones diferentes entre ellos para encontrar uno que conduzca a los resultados correctos [este es el método general].

modelo

Modele la solución, al menos en su cabeza, y camine a través de ella para ver si funciona correctamente. Ajustar según sea necesario (ver descomposición y mapeo, arriba).

composición / interfaces

Muchas veces puede encontrar elementos del problema y elementos de la solución que se correlacionan entre sí y producen resultados parciales que son útiles. Esta composición y construcción de interfaz proporciona el núcleo de la solución y también sirve para reducir el alcance del problema restante. Entonces simplemente vuelves a la parte superior con un problema inicial más pequeño, y lo revisas nuevamente.

experiencia

La experiencia es la mejor maestra, por supuesto, pero leer sobre diferentes tipos de problemas y soluciones también será útil. También es muy útil estudiar algunos de los algoritmos conocidos y sus aplicaciones , por ejemplo, Dijkstra , Bresenham , Unificación y, por supuesto, la teoría de grafos .

Puede resultarle útil realizar algoritmos físicamente. Por ejemplo, cuando estés estudiando algoritmos de clasificación, practica haciendo cada uno con un mazo de cartas. Eso activará diferentes partes de tu cerebro que leer o programar solo.

Steve Yegge se refirió a "The Algorithm Design Manual" en uno de sus discursos. No lo he visto yo mismo, pero parece que es solo el boleto de su descripción.

Mi favorito absoluto para este tipo de preparación de entrevistas es The Algorithm Design Manual de Steven Skiena. Más que cualquier otro libro, me ayudó a comprender cuán asombrosamente comunes (e importantes) son los problemas de los gráficos: deberían formar parte del conjunto de herramientas de todos los programadores que trabajan. El libro también cubre estructuras básicas de datos y algoritmos de clasificación, lo cual es una buena ventaja. Pero la mina de oro es la segunda mitad del libro, que es una especie de enciclopedia de 1-pagers en tropecientos de problemas útiles y varias maneras de resolverlos, sin demasiados detalles. Casi cada 1-pager tiene una imagen simple, por lo que es fácil de recordar. Esta es una gran manera de aprender a identificar cientos de tipos de problemas.

Intento encontrar análogos físicos cuando estoy viendo un problema complejo.

No estoy seguro de que se pueda cultivar la intuición, pero creo que sé lo que estás preguntando. Cuantos más problemas resuelva, más información y experiencia tendrá a su disposición para problemas futuros. Entonces, digo simplemente practica. Practica la programación de aplicaciones del mundo real y te encontrarás con muchos problemas. A veces, resolver acertijos puede ser muy educativo también.

+1 a quien dijo experiencia es el mejor maestro.

Hay varios portales en línea que tienen muchos problemas de programación, a los que puede enviar sus propias soluciones y obtener una indicación automática de aprobación / falla.

El sitio de capacitación de USACO es el programa de capacitación que atraviesan todos los participantes en la olimpíada de computación de EE. UU. Va paso a paso, introduciendo algoritmos cada vez más complejos a medida que avanza.