FIEC : Análisis de AlgoritmosFacultad de Ingeniería en Electricidad y ComputaciónEscuela Superior Politécnica del LitoralSegundo semestre, año lectivo 2008-2009

Instructor: Carlos Jordán

Horario de Clases: Paralelo 1: Martes y Jueves, 11.30 – 13.30 Paralelo 2: Lunes y Miercoles, 11.30 – 13.30

Horario de Consultas: Lunes – Viernes, de 9:30 – 11:30

Programa Resumido: En este curso se estudiará los fundamentos teóricos necesarios para realizar el análisis de algoritmos. Se estudiará también varios métodos para el diseño de algoritmos eficientes y sus estructuras de datos. Se demostrará que los algoritmos son correctos y se calcularán sus tiempos de ejecución. Los temas principales que se estudiarán son los siguientes:

• Introducción al análisis de algoritmos, • Ordenamiento y Búsqueda• Diseño de Algoritmos por División y Conquista• Algoritmos Voraces• Algoritmos por Programación Dinámica.• Complejidad Computacional.

Evaluación: El curso se evaluará de la siguiente manera:• Deberes, lecciones y proyectos: 40 - 60 %• Examenes parcial y final: 60 – 40 %

Textos:• Introduction to Algorithms, T.H. Cormen, C. L. Leiserson, R. L. Rivest, y C. Stein, MIT

Press, 2001.

Referencias:• Estructuras de Datos y Algoritmos, Aho, Ullman y Hopcroft, Addison Wesley. • Computer Algorithm: Introduction to Design and Analisis, Sara Baase.

• Algoritmica, Gilles Brassard, Prentice Hall.

1.Clases Tema Lecturas1 Introduction Capitulo 1, pags. 1-162-4 Notaciones Asintóticas Capitulo 2, pags. 23-365-6 Ecuaciones de Recurrencia Capitulo 4, pags. 53-647 Dividir y Conquistar8-9 Quicksort Capitulo 8, pags. 151-16810 Medianas y Selección Capitulo 10, pags. 185-19411-12 Ordenamiento Lineal Capitulo 9, pags. 172-18413 Heapsort14 Conjuntos Disjuntos Capitulo 22, pags. 440-450

Examen Parcial15-18 Programación Dinámica Capitulo 16, pags. 301-32019-22 Algoritmos Voraces Capitulo 17, pags. 329-34423-24 Análisis por Amortización Capitulo 18, pags. 356-36625-26 Árboles Rojo-Negro Capitulo 14, pags. 261-28027-28 Complejidad Computacional Capitulo 36, pags. 916-963

Examen Final

El material de lectura asignado corresponde al libro de Corman, primera edición.