Introducción al diseño y análisis de lagoritmos: un enfoque estratégico
Lee, R.C.T.
Introducción al diseño y análisis de lagoritmos: un enfoque estratégico R.C.T. Lee, S.S. Tseng, R.C. Chang, Y. T. Tsai - 1 - 736 páginas ; il. ; 25cm.
1. Introdicción. 2. Complejidad de los algoritmos y cotas inferiores de los problemas. 3. El método codicioso. 4. La estrategía divide-Y-vencéras. 5. La estrategía de árboles de búsqueda. 6. la estrategía prune-and search. 7. Programación dinámica. 8. Teoría de los problemas NP-completos. 9. Algoritmos de aprximación. 10. Análisis amortizado. 11. Algoritmos aleatorios. 12. Algoritmos en línea.
Existen múltiples razones para estudiar algoritmos. La principal es e?ciencia. Suele creerse que para obtener altas velocidades de cálculo basta contar con una computadora de muy alta velocidad. Sin embargo, no es completamente cierto. Un buen algoritmo implementado en una computadora lenta puede ejecutarse mucho más rápido que un mal algoritmo implementado en una computadora rápida. Imagine que un programador re-quiere encontrar un árbol de expansión mínima para un problema su?cientemente gran-de. Si su programa examina todos los posibles árboles de expansión, no existirá ni hoy, ni en el futuro, una computadora capaz de resolver el problema. En cambio, si conoce el método de Prim, con una PC le basta. Otro ejemplo: cuando alguien quiere resol-ver el problema del reconocimiento del habla, es muy difícil siquiera comenzar a resolver el problema. Pero, si conoce que el problema de subsecuencia común más larga puede ser resuelto por medio de programación dinámica, se sorprendería con la sencillez con la que resolvería el problema. El estudio de algoritmos no es exclusivo de las ciencias de la computación. Los ingenieros en comunicaciones también utilizan y estudian programación dinámica o algoritmos A´. Sin embargo, el grupo más grande de cientí?cos interesados en algo-ritmos, ajenos a las ciencias de la computación, es el del campo de la biología molecular. Por ejemplo, si se desea comparar dos secuencias de ADN, dos proteínas, o secuencias RNA, estructuras 3-dimensionales, entonces es necesario conocer algoritmos e?cientes .Además, estudiar algoritmos puede resultar divertido. Los autores continúan entusiasmados cada que encuentran un algoritmo nuevo y bien diseñado, o alguna idea novedosa sobre diseño y análisis de algoritmos. Se sienten con la responsabilidad moral de compartir su diversión y emoción. Muchos problemas, que aparentan ser difícil-les, pueden ser resueltos con algoritmos polinomiales, mientras que otros problemas, que a primera vista parecen sencillos, pueden ser NP-completo. Por ejemplo, el árbol de expansión mínima parece ser un problema difícil para nuevos lectores, aunque luego descubren que puede resolverse con algoritmos polinomiales. En contraste, si se representa como un problema euclidiano del agente viajero, repentinamente se con-vierte en un problema NP difícil. Otro caso es el 3-satisfactibilidad, que es un problema NP, pero si se decrece su dimensión, el problema de 2-satisfactibilidad se convierte en un problema P. Para quien estudia algoritmos, es fascinante descubrir esto.
970-10-6124-1
ALGORITMOS ALEATORIOS
DISEÑO ANÁLISIS DE ALGORITMOS
519.721 / L4771in
Introducción al diseño y análisis de lagoritmos: un enfoque estratégico R.C.T. Lee, S.S. Tseng, R.C. Chang, Y. T. Tsai - 1 - 736 páginas ; il. ; 25cm.
1. Introdicción. 2. Complejidad de los algoritmos y cotas inferiores de los problemas. 3. El método codicioso. 4. La estrategía divide-Y-vencéras. 5. La estrategía de árboles de búsqueda. 6. la estrategía prune-and search. 7. Programación dinámica. 8. Teoría de los problemas NP-completos. 9. Algoritmos de aprximación. 10. Análisis amortizado. 11. Algoritmos aleatorios. 12. Algoritmos en línea.
Existen múltiples razones para estudiar algoritmos. La principal es e?ciencia. Suele creerse que para obtener altas velocidades de cálculo basta contar con una computadora de muy alta velocidad. Sin embargo, no es completamente cierto. Un buen algoritmo implementado en una computadora lenta puede ejecutarse mucho más rápido que un mal algoritmo implementado en una computadora rápida. Imagine que un programador re-quiere encontrar un árbol de expansión mínima para un problema su?cientemente gran-de. Si su programa examina todos los posibles árboles de expansión, no existirá ni hoy, ni en el futuro, una computadora capaz de resolver el problema. En cambio, si conoce el método de Prim, con una PC le basta. Otro ejemplo: cuando alguien quiere resol-ver el problema del reconocimiento del habla, es muy difícil siquiera comenzar a resolver el problema. Pero, si conoce que el problema de subsecuencia común más larga puede ser resuelto por medio de programación dinámica, se sorprendería con la sencillez con la que resolvería el problema. El estudio de algoritmos no es exclusivo de las ciencias de la computación. Los ingenieros en comunicaciones también utilizan y estudian programación dinámica o algoritmos A´. Sin embargo, el grupo más grande de cientí?cos interesados en algo-ritmos, ajenos a las ciencias de la computación, es el del campo de la biología molecular. Por ejemplo, si se desea comparar dos secuencias de ADN, dos proteínas, o secuencias RNA, estructuras 3-dimensionales, entonces es necesario conocer algoritmos e?cientes .Además, estudiar algoritmos puede resultar divertido. Los autores continúan entusiasmados cada que encuentran un algoritmo nuevo y bien diseñado, o alguna idea novedosa sobre diseño y análisis de algoritmos. Se sienten con la responsabilidad moral de compartir su diversión y emoción. Muchos problemas, que aparentan ser difícil-les, pueden ser resueltos con algoritmos polinomiales, mientras que otros problemas, que a primera vista parecen sencillos, pueden ser NP-completo. Por ejemplo, el árbol de expansión mínima parece ser un problema difícil para nuevos lectores, aunque luego descubren que puede resolverse con algoritmos polinomiales. En contraste, si se representa como un problema euclidiano del agente viajero, repentinamente se con-vierte en un problema NP difícil. Otro caso es el 3-satisfactibilidad, que es un problema NP, pero si se decrece su dimensión, el problema de 2-satisfactibilidad se convierte en un problema P. Para quien estudia algoritmos, es fascinante descubrir esto.
970-10-6124-1
ALGORITMOS ALEATORIOS
DISEÑO ANÁLISIS DE ALGORITMOS
519.721 / L4771in