Análisis y Diseño de Algoritmos (300CIG004)

• Créditos: 3
• Horas de trabajo acompañado: 5 / semana (3 horas de clase, 2 de taller)
• Horas de trabajo independiente: 4 / semana
• Pre-requisitos: Árboles y Grafos, Computabilidad y Lenguajes Formales, Probabilidad Discreta
• Tipo de curso: Núcleo de Formación Fundamental

El curso estudia técnicas para diseñar algoritmos como, por ejemplo, dividir y conquistar, programación dinámica, programación voraz/avara y reintento. A los algoritmos desarrollados mediante estas técnicas se les aplican los dos tipos de análisis fundamentales en algoritmia: el de corrección y el de eficiencia. El curso también aborda técnicas de diseño de algoritmos aleatorizados y de algoritmos de aproximación, al igual que explora técnicas en la teoría de números computacional y en la computación geométrica. En la última parte del curso se introducen modelos de computación en paralelo.

Al finalizar el curso los participantes podrán:

1. Usar técnicas de diseño algorítmico para resolver problemas de decisión, optimización y búsqueda computacional.
   1. Diseñar algoritmos basándose en los principios de dividir y conquistar, programación avara/voraz y reintento.
   2. Describir las ventajas y desventajas de algoritmos aleatorizados y de aproximación.
   3. Aplicar técnicas para optimización de recursos en el diseño de una solución algorítmica.
2. Demostrar y argumentar la corrección y eficiencia de un algoritmo.
   1. Plantear contratos (i.e., precondición, poscondición, invariantes) para algoritmos iterativos y recurrentes.
   2. Demostrar que un algoritmo es correcto con respecto a su especificación; en particular, justificar por qué una fórmula es invariante de un ciclo.
   3. Calcular las complejidades temporal y espacial de una algoritmo en el peor de los casos.
3. Implementar correcta y eficientemente soluciones algorítmicas en un lenguaje de programación.
   1. Escribir programas en un lenguaje de programación con base en el diseño algorítmico de una solución.
   2. Conocer las ventajas y desventajas de los lenguajes de programación utilizados para implementar un diseño algorítmico.
4. Identificar técnicas de aproximación algorítmica para resolver problemas intratables (i.e., computacionalmente difíciles).
   1. Entender la programación lineal como un método general para resolver problemas de optimización.
   2. Usar la aproximación lineal para obtener algoritmos de aproximación para problemas algorítmicos combinatorios.
5. Comprender las diferencias entre los modelos de computación secuenciales y los modelos de computación en paralelo.
   1. Distinguir entre modelos de computación secuencial y modelos de computación en paralelo.
   2. Conocer las limitaciones prácticas de los modelos de computación en paralelo.

• El uso de un lenguaje de programación imperativo.
• La implementación de algoritmos correctos y eficientes en un lenguaje de programación.
• La estimación de complejidades algorítmicas para el peor de los casos.
• El diseño de casos de prueba para validar el comportamiento de los algoritmos diseñados.

Total de Horas: 5.

Total de Horas: 4.

Total de Horas: 10.

Total de Horas: 8.

Total de Horas: 30.

Total de Horas: 24.

Total de Horas: 15.

Total de Horas: 12.

Total de Horas: 12.5.

Total de Horas: 10.

Total de Horas: 7.5.

Total de Horas: 6.

(A) La habilidad para aplicar conocimientos de matemáticas, ciencias e ingeniería.

(B) La habilidad para analizar un problema e identificar los requerimientos necesarios para su definición y solución.

(C) La habilidad para diseñar, implementar y evaluar procesos y sistemas computacionales.

(D) La habilidad para funcionar en equipos de trabajo.

(E) El entendimiento de la responsabilidad profesional y ética.

(F) La habilidad para comunicarse efectivamente.

(G) La habilidad para analizar los impactos de la computación y la ingeniería en las personas, organizaciones y la sociedad.

(H) El reconocimiento de la necesidad de, y la habilidad para, continuar con el desarrollo profesional.

(I) La habilidad para usar las técnicas, destrezas y herramientas modernas para la práctica de la computación.

(J) La habilidad para aplicar los fundamentos y principios de las matemáticas y de la computación en el modelamiento y diseño de sistemas computacionales de manera que se demuestre comprensión de las ventajas y desventajas en las decisiones de diseño.

(K) La habilidad para aplicar los principios de diseño y desarrollo de software en la construcción de sistemas de diferente complejidad.

(1) baja relevancia - (5) alta relevancia

El curso es presencial y con participación y trabajo en clase. Se asigna trabajos, ejercicios y lecturas. Durante la sesión se expondrán los conceptos acompañados de ejemplos, se fomentará la participación de los estudiantes. Se realizan talleres semanal o bisemanales en los cuales se aplican los fundamentos teóricos.

La tabla muestra que aspectos de las competencias de Comunicación Escrita, Lectura Crítica y Razonamiento Cuantitativo son evaluados a través de los factores ABET correspondientes. Por otra parte, la competencias de Inglés se favorece gracias a la metodología del curso y también, gracias al factor ABET correspondientes.

E- Se evalúa. U - Se usa

La Carrera de Ingeniería de Sistemas y Computación plantea los siguientes objetivos educacionales, El estudiante graduado de la carrera será capaz de:

1. Ejercitar la práctica de la Ingeniería de Sistemas y Computación profesionalmente.
2. Diseñar y operar sistemas de computación que contribuyen a la solución de problemas relacionados a la disciplina, otra área de la ciencia y la ingeniería u otras disciplinas.
3. Contribuir al bienestar de las comunidades desde posiciones prominentes en la industria, academia, sector público o como un emprendedor.
4. Ser distinguido por su bases sólidas en computación, su sentido de ciudadanía responsable, su profesionalismo y liderazgo.
5. Continuar su desarrollo profesional o involucrarse en estudios de posgrado.

No está permitido el uso de material en los exámenes, ni el uso de computadores personales ni teléfonos celulares.

Es obligatoria.

1. T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to algorithms. Third Edition. MIT Press, Cambridge, MA, USA, 2009.
2. J. Kleinberg, É. Tardos. Algorithm Design. Pearson, 2005.
3. J. Erickson. Algorithms. Urbana, USA, 2015. Available online: http://web.engr.illinois.edu/~jeffe/teaching/algorithms/
4. S. Halim, F. Halim. Competitive Programming 3: The new lower bound of programming contests. Lulu, 2013.
5. R. Neapolitan, K. Naimipour. Foundations of Algorithms. 4th Edition. Jones and Barlett Publishers, 2011.

Salón de clase con computador y proyector. Laboratorio de Ingeniería de Sistemas y Computación.

Curso en Moodle

Material adicional del curso