CURSO : DISE?O Y ANALISIS DE ALGORITMOS TRADUCCION : DESIGN AND ANALYSIS OF ALGORITHMS SIGLA : IIC2283 CREDITOS : 06 SCT-Chile / 10 UC MODULOS : 03 TIPO DE ASIGNATURA : CATEDRA CALIFICACION : ESTANDAR DISCIPLINA : INGENIERIA I. DESCRIPCION El curso ense?a los algoritmos principales y sus propiedades (correccion, completitud, complejidad); ademas, las tecnicas de analisis y dise?o, estructuras de datos avanzadas, grafos, y las clases de problemas NP-Dificil y NP-Completo. II. OBJETIVOS 1. Analizar algoritmos empleando las tecnicas de ecuaciones de recurrencia, notacion asintotica, e induccion, y demostrar cotas inferiores para la complejidad de algunos problemas. 2. Dise?ar algoritmos basados en las tecnicas de dividir y conquistar, programacion dinamica, algoritmos codiciosos, backtracking y branch-and-bound. 3. Usar algoritmos eficientes para resolver problemas de ordenacion, busqueda, secuenciamiento de tareas, y problemas en grafos. 4. Aplicar estructuras de datos avanzadas, y los algoritmos utiles para manipularlas. 5. Explicar la nocion de complejidad, y las nociones de NP-completitud y reduccion, y demostrar que un problema es dificil. 6. Aplicar las tecnicas de algoritmos aleatorizados, algoritmos de aproximacion y algoritmos para modelos paralelos para el dise?o de algoritmos. III. CONTENIDOS 1. Fundamentos: Crecimiento de funciones; recurrencias. 2. Tecnicas de analisis y dise?o: Dividir y conquistar; programacion dinamica; algoritmos codiciosos; backtracking y branch-and-bound; analisis amortizado; ejemplos de ordenacion y busqueda, secuenciamiento de tareas, el problema de la mochila, y problemas polinomiales en grafos. 3. Estructuras de datos avanzadas: Heaps binomiales; heaps de Fibonacci; conjuntos disjuntos. 4. Grafos: Arboles de cobertura minimos; rutas mas cortas; flujo maximo en redes. 5. Problemas NP-dificiles y NP-completos: Algoritmos no deterministas; las clases NP-dificil y NP- completo; el teorema de Cook; problemas NP-dificiles en grafos; problemas NP-dificiles de programacion de tareas. 6. Otros temas: Representacion, evaluacion e interpolacion de polinomios y la transformada rapida de Fourier (FFT); algoritmos aleatorizados; algoritmos de aproximacion; algoritmos para modelos paralelos. IV. METODOLOGIA - Clases expositivas. - Ayudantias. V. EVALUACION - Pruebas. - Proyectos. - Tareas. VI. BIBLIOGRAFIA Cormen, T. et al. Introduction to algorithms. MIT Press, 2003. Horowitz, E., S. Sahni y S. Rajasekaran. Computer Algorithms. Computer Science Press, 2007. PONTIFICIA UNIVERSIDAD CATOLICA DE CHILE FACULTAD DE INGENIERIA / Julio 2015