muse - algorithms book
Sin dolor ''análisis de entrenamiento de algoritmos'' (12)
Asimismo, UC Berkeley tiene innumerables podcasts que pueden ser útiles.
Tuve una experiencia dolorosa con las clases de "Análisis de Algoritmos" en la universidad, pero recientemente he encontrado una necesidad en el mundo real . - De todos modos, estoy buscando un curso acelerado simple pero efectivo. ¿Algunas ideas?
Sidenote relacionado: Seguramente estaría bien si hubiera una "Guía de dibujos animados para el análisis de algoritmos", impartida por Dilbert.
ACTUALIZACIÓN: una pregunta muy similar se puede encontrar en: ¿Cómo comenzar a ALGORITMOS?
Me gusta la Introducción a los Algoritmos de Cormen, Leiserson, Rivest y Stein. Es un poco pesado, pero encontré que es un texto de referencia decente.
Google Code University ofrece una página sobre Algoritmos que apunta a algunas diapositivas ofrecidas por Stanford y Princeton .
Hay muchos buenos libros sobre el tema. Me gusta Una introducción al análisis de algoritmos . También consulte el curso de algoritmos en MIT OpenCourseWare (utilizando CLRS como el texto del curso). Es un poco profundo, pero tenerlo en línea te permite ir a tu propio ritmo.
Un par de otros libros que comencé a leer recientemente son Algorithms in a Nutshell y Algorithm Design Manual . Ambos toman un enfoque más ligero que la mayoría de los libros de algoritmos. En lugar de matemáticas pesadas y pruebas formales, estos libros le dan declaraciones de problemas realistas y le muestran los pasos necesarios para refinar un algoritmo. También le muestran cómo estimar y medir la complejidad de una solución. Yo recomendaría cualquier libro.
La mayoría de los cursos de análisis de algoritmo en las Universidades solo están abiertos para estudiantes universitarios y de posgrado de nivel superior. ¿Por qué espera que este tema sea fácil de aprender? Hay algoritmos que son simples de analizar y el artículo de Wikipedia sobre notación Big O es probablemente adecuado para comprender cómo y realizar un análisis sobre ellos, pero hacer un análisis de cualquier algoritmo razonablemente complejo no es trivial. El libro de Cormen es probablemente el libro más utilizado sobre algoritmos, pero no consideraría aprender a analizar algoritmos a partir de él ni de ningún otro libro de forma indolora.
No dices mucho sobre el resto de tus antecedentes. Para el análisis directo de algoritmos, los métodos mediante los cuales evalúa un algoritmo para encontrar las estadísticas y el comportamiento de su orden. Si se siente cómodo con las matemáticas en general, digamos que ha tenido dos años de cálculo o un buen curso de álgebra abstracta. - entonces realmente no puedes hacer mucho mejor que leer Knuth Volume One .
El curso habitual de "Análisis de Algoritmos" también es un curso de estructuras de datos, por lo que un texto de estructuras de datos podría ser mejor si también necesitas aprender sobre listas, árboles, etc. Mi favorito en la escuela de postgrado fue Aho, Hopcroft y Ullman .
Me gusta Cormen como referencia; también sirve como un admirable tope de puerta, para la ejecución de grandes errores icky, para sujetar pequeñas juntas de pegamento (la cubierta lisa libera la mayoría de los pegamentos de madera), y como un libro final porque tiene un sujetalibros en su lugar. No lo recomendaría como texto de introducción.
La herramienta más útil que he tenido para los algoritmos es Introducción a los algoritmos .
Es el mejor recurso que conozco para los algoritmos. Cubre tantos temas en buena profundidad y tiene ejemplos en todas partes. Todavía me refiero a él con bastante frecuencia.
Sin ese libro, mi clase de análisis de algoritmos hubiera sido un dolor.
Hay un atajo simple para entender el rendimiento de los algoritmos de búsqueda y clasificación, si eso es lo que está buscando.
Primero, la clasificación es básicamente búsqueda repetida. Para cada uno de N elementos, está buscando dónde insertarlo en la lista y luego insertarlo, por lo que lleva N veces la gran O del procedimiento de búsqueda.
Para entender la gran O de la búsqueda, una manera simple es pensar en ella como una serie de decisiones (generalmente binarias) con una cierta probabilidad de tomar cada rama.
Supongamos que su tabla tiene N = 1024 entradas. Eso significa que se necesitan 10 bits para indexar la tabla, porque log (1024) = 10 (base 2). La búsqueda es un proceso de aprendizaje de esos 10 bits.
Si un punto de decisión tiene aproximadamente la misma probabilidad de ir en cualquier dirección, entonces tiene una entropía de -0.5 log (0.5) - 0.5 log (0.5) (base 2) que es de 1 bit, por lo que aprende 1 bit de información en cada decisión . Voila! Toma aproximadamente 10 decisiones, o log (N). Entonces la clasificación es O (N log (N)). Todos los algoritmos de clasificación NlogN se basan en decisiones binarias que tienen resultados aproximadamente igualmente probables.
Supongamos que está haciendo una búsqueda lineal (como en el tipo de burbuja). En la primera decisión, la posibilidad de tener razón es 1/1024 vs 1023/1024. La entropía es 1/1024 * log (1024/1) + 1023/1024 * log (1024/1023) o aproximadamente 10/1024 + 0 (es decir, aproximadamente .01). Entonces, en la primera decisión solo aprendes sobre .01 bit porque los resultados son muy sesgados. Es por eso que la búsqueda lineal es ineficiente. Toma el orden de N operaciones, por lo que la ordenación toma O (N * N).
(Aparte: la búsqueda lineal es en realidad exponencial. Si define el contenido de información de un problema como n = log (N), la búsqueda lineal toma O (2 ^ n) pasos. Por eso, las cosas como la búsqueda no guiada del árbol de juego son exponenciales en cantidad de movimientos)
Por otro lado, suponga que en lugar de tomar decisiones binarias, está indexando. Toma algunos o todos los bits de la palabra que está buscando y los utiliza como un índice en una matriz, donde ha almacenado previamente las respuestas. Si esa operación de indexación tiene 1024 resultados igualmente probables, aprende 10 bits, por lo que solo se necesita aproximadamente 1 operación para obtener la respuesta. Esa es la idea básica detrás de la codificación hash. Si su función hash persiste en el orden, se puede usar para hacer un algoritmo de clasificación O (N).
Existen formas sofisticadas de analizar algoritmos, y tal vez eso es lo que necesita, pero mirarlos como bits de información de aprendizaje cubre el 99% de mis necesidades.
Asistí a un entrenamiento de 1 día (9 horas) sobre algoritmos hace aproximadamente un año. El prerrequisito era una licenciatura en Comp Sci, o al menos 2 años de experiencia en programación. Encontré que la capacitación era MUY útil, y especialmente los marcadores físicos que obtenía valían mi tiempo (y dinero, pagara la compañía). Asistiría a otra sesión si tuviera la oportunidad, incluso si era básicamente la misma. Obviamente, mucho depende del instructor. El nuestro fue genial: programador divertido, práctico y activo, a pesar de que tenía una experiencia docente significativa.
Si prefiere mirar y escuchar en lugar de leer, puedo recomendar el curso MIT "Introducción a los algoritmos". Puedes verlo gratis aquí: http://academicearth.org/courses/introduction-to-algorithms
Me pareció muy bueno y pedagógico, aunque no tengo suficiente conocimiento de las matemáticas involucradas.
Recomiendo Data Structures and Algorithms de Adam Drozdek, disponible en ediciones Java y C ++.
Erik Öjebo publicó una gran respuesta a una pregunta casi idéntica , hecha poco después de la tuya.
Citando su respuesta:
MIT tiene un curso sobre algoritmos en su Open Courseware Programme con video, audio y conferencias en PDF.
También hay un curso en línea, también con video conferencias, en la Universidad ArsDigita .
En la Universidad de Florida existe el curso Estructuras de datos y algoritmos en Java, y al igual que el anterior, tiene videoconferencias disponibles en línea.
En freescienceonline.blogspot.com puede encontrar una gran cantidad de video conferencias sobre algoritmos, así como muchos otros videos interesantes.