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
Respuestas:
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):
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í.
fuente