Diseño y complejidad de algoritmos: ¿cómo pensar de esa manera?

15

Mi pregunta es general: ¿cómo empiezo a pensar en términos de diseño y complejidad de algoritmos? Voy a tomar un curso de posgrado en diseño de algoritmos. Me había inscrito en él antes, pero lo abandoné más tarde porque no podía seguir el ritmo. Tengo que tomar este curso como requisito.

¿Hay un 'truco' para pensar de esta manera? Sé que esto lo expresa de manera bastante cruda, pero a veces una nueva perspectiva ayuda a pensar sobre un tema de manera diferente.

El principal problema que tengo con este curso (y cursos teóricos similares) es: ¿Cómo sé que las soluciones que se me ocurren son correctas? ¿Encuentro que la parte teórica es arbitraria, especialmente cuando 'probar' que cierto algoritmo actúa o se comporta de cierta manera?

Nuestro curso utilizará el texto estándar: Introducción a los algoritmos de CLRS.

¿Hay libros de texto / sitios / libros / etc. que podría ofrecer una manera de tener confianza en este campo?

Gracias a todos,

Jason Dane

Jason Dane
fuente
2
Sugiero echar un vistazo a esta publicación . Sugiero especialmente el libro de Udi Manber.
MS Dousti
1
Esta discusión sobre StackOverflow ofrece varias sugerencias: stackoverflow.com/questions/2256721/…
Jeffε
2
Secundo la recomendación de Manber. Consulte también Cómo pensar en algoritmos por Jeff Edmonds: amazon.com/Think-About-Algorithms-Jeff-Edmonds/dp/0521614104
Jeffε
"¿Cómo sé que las soluciones que se me ocurren son correctas?" ¿Quiere decir que (1) se le ocurrió un algoritmo pero no sabe cómo demostrar que es correcto o (2) tiene una prueba pero no está seguro de si es correcta?
Jukka Suomela 01 de
Paso uno: deja de dar respuestas directas y consulta las soluciones de otros. ;)
Raphael

Respuestas:

18

Creo que los cursos sobre diseño de algoritmos y complejidad computacional son siempre desafiantes para los estudiantes que no están familiarizados con estas materias porque requieren cierto grado de madurez matemática y habilidad para resolver problemas. En mi primer curso de posgrado sobre "complejidad computacional", un amigo mío que tenía su título en matemáticas puras me dijo lo sorprendido que estaba por el hecho de que, aunque ese curso no requería muchos antecedentes en matemáticas (al menos eso es lo que se contó en el esquema del curso), ¡en realidad requería casi todas las habilidades que obtuvo a través de todos sus estudios universitarios de matemática pura!

Descubrí que tenía que saber sobre "la forma" más (cuando comienzo mi estudio de posgrado) leyendo y haciendo ejercicios del libro de Sipser . Asegúrese de hacer los ejercicios porque la habilidad para resolver problemas y la madurez matemática es lo que desea aprender y no solo un montón de hechos o definiciones.

Sin embargo, el libro de Sipser solo es bueno para la complejidad y la completitud de NP, no será suficiente para sustituir el libro de CLRS. El único problema con el libro CLRS es que su ventaja de una cobertura integral podría convertirse en su debilidad, ya que el libro puede parecer bastante aterrador o abrumador para los estudiantes. Entonces, mi consejo es que realmente debe ir a la biblioteca y buscar libros sobre algoritmos, escanear uno por uno y elegir los que mejor se adapten a su patrón de pensamiento. Y de nuevo, ¡no te olvides de hacer ejercicios!

Para los algoritmos, personalmente sugiero los siguientes libros (además de los sugeridos por Sadeq y JeffE):

  • El muy legible y hermoso libro Algorithms by de S. Dasgupta, CH Papadimitriou y UV Vazirani.
  • El asesino notas (o borrador del libro) de Jeff Erickson. (Como JeffE es demasiado modesto para sugerir sus propias notas, tengo que hacerlo yo mismo).

En general, cada vez que estudias un cierto algoritmo o estructura de datos, si de alguna manera la exposición en tu libro de texto no es lo suficientemente clara para ti, entonces la mejor manera es buscar en Google notas de conferencias sobre ese tema en particular. En muchos casos, diferentes explicaciones de la misma cosa eventualmente le dan la imagen completa. Al menos, así es como funciona para mí.

Dai Le
fuente
8
+1 para las notas asesinas de Jeff. Siempre disfruto leerlos. La caligrafía árabe de la palabra Algoritmo es muy hermosa.
Mohammad Al-Turkistany