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

Información Básica

  • 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

Descripción del Curso

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.

Objetivos

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.

Se desarrollan competencias en

  • 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.

Contenido

Capítulo 1: Introducción

Sesión Horas teóricas Prácticas acompañadas Temas Profundidad Bibliografía
1-2 3 2 Introducción y repaso. Inducción matemática. Diseño algorítmico. Notación asintótica. Algoritmos cuadráticos de ordenamiento. Uso [1 caps 1,2] [2 cap 2][3 cap 0, app 1][5 cap 1]

Total de Horas: 5.

Sesión Horas de trabajo independiente Temas Bibliografía
1-2 4 Tareas semanales, resolución de problemas en temas vistos [1,cap 1,2][2 cap 2][3 cap 0, app 1][5 cap 1]

Total de Horas: 4.

Capítulo 2: Dividir y conquistar

Sesión Horas teóricas Prácticas acompañadas Temas Profundidad Bibliografía
3-6 6 4 Dividir, conquistar y combinar. Relación con inducción matemática. MergeSort. HeapSort. Bisección y búsqueda binaria. Teorema Maestro. Evaluación [1 cap 4][2 cap 5][3 cap 1][5 cap 2]

Total de Horas: 10.

Sesión Horas de trabajo independiente Temas Bibliografía
3-6 8 Tareas semanales, resolución de problemas en temas vistos [1 cap 4][2 cap 5][3 cap 1][5 cap 2]

Total de Horas: 8.

Capítulo 3: Técnicas de diseño algorítmico

Sesión Horas teóricas Prácticas acompañadas Temas Profundidad Bibliografía
7-11 7 5.5 Programación dinámica. Memorización (top-down). Tabulación (bottom-up). Técnicas de ahorro de memoria. Evaluación [1 cap 15][2 cap 6][3 caps 5,6][5 cap 3]
12-15 6 4 Algoritmos avaros/voraces. Óptimos locales. Técnicas de demostración de optimalidad. Evaluación [1 cap 16][2 cap 4][3 cap 7][5 cap 4]
16-18 5 2.5 Reintento (backtracking). Búsqueda exhaustiva. Heurísticas. Evaluación [3 cap 3][5 caps 5,6]

Total de Horas: 30.

Sesión Horas de trabajo independiente Temas Bibliografía
7-18 24 Tareas semanales, resolución de problemas en temas vistos [1 caps 15,16][2 caps 4,6][3 caps 3,5-7][5 caps 3-6]

Total de Horas: 24.

Capítulo 4: Temas seleccionados

Sesión Horas teóricas Prácticas acompañadas Temas Profundidad Bibliografía
19-21 4 3.5 Teoría de números computacional. El algoritmo de Euclides. Criba de Eratóstenes. Test de primalidad. Factorización de números. Funciones multiplicativas. Aritmética de precisión arbitraria. Ciframiento. Evaluación [1 cap 31][4 cap 5][5 cap 10]
22-24 4 3.5 Geometría computacional. Representación de puntos, líneas, segmentos, polígonos. Intersección de segmentos, polígonos. Envolvimiento convexo. Evaluación [1 cap 33][4 cap 7]

Total de Horas: 15.

Sesión Horas de trabajo independiente Temas Bibliografía
19-24 12 Tareas semanales, resolución de problemas en temas vistos [1 caps 31,33][4 caps 5,7][5 cap 10]

Total de Horas: 12.

Capítulo 5: Otras técnicas algorítmicas

Sesión Horas teóricas Prácticas acompañadas Temas Profundidad Bibliografía
25-26 3 2 Algoritmos aleatorizados. Quicksort. El algoritmo de Rabin y Karp. Uso [1 cap 7][3 cap 13]
27-29 5 2.5 Algoritmos de aproximación. Programación lineal entera. El algoritmo Simplex. Eliminación Gaussiana. Rounding. Cubrimiento de vértices. Uso [1 cap 29,35][3 caps 26]

Total de Horas: 12.5.

Sesión Horas de trabajo independiente Temas Bibliografía
25-29 10 Tareas semanales, resolución de problemas en temas vistos [1 caps 7,29,35][3 caps 13,26]

Total de Horas: 10.

Capítulo 7: Modelos de computación en paralelo

Sesión Horas teóricas Prácticas acompañadas Temas Profundidad Bibliografía
30-32 5 2.5 Modelos formales de programación en paralelo. Computación secuencial vs. en paralelo. Parallel programming vs. concurrent programming. La ley de Amdahl Uso [5 cap 11]

Total de Horas: 7.5.

Sesión Horas de trabajo independiente Temas Bibliografía
30-32 6 Tareas semanales, resolución de problemas en temas vistos [5 cap 11]

Total de Horas: 6.

Integración Curricular

Resultados de Programa (ABET)

(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.

Relevancia del curso con los resultados de programa

Resultados de Programa
a b c d e f g h i j k
Relevancia 3 2 3 0 0 2 0 0 0 5 3

(1) baja relevancia - (5) alta relevancia

Integración de objetivos, contenido y metodología del curso

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.

Resultados del Programa Indicadores de Desempeño Objetivos/Contenido del Curso Actividades de aprendizaje Instrumentos de medición
(A) Aplicación de Conocimientos (A1) Identificar los fundamentos científicos y los principios de ingeniería que rigen un proceso o sistema. (Conocimiento) (A2) Resolver problemas relacionados con la disciplina y otras áreas por medio de la utilización de conocimientos, modelos y formalismos de las ciencias de la computación, las matemáticas y la ingeniería. (Aplicación) (A4) Interpretar modelos matemáticos para estimar su precisión y confiabilidad. (Comprensión) Todos Exposiciones del profesor, talleres, tareas y lecturas Exámenes, Talleres, proyecto
(B) Análisis de problemas y requerimientos (B1) Describir procesos de manera declarativa ignorando los detalles de su implementación. (Comprensión). (B2) Utilizar el lenguaje propio de las matemáticas, la lógica y la ingeniería para especificar requerimientos funcionales y no funcionales de un sistema o proceso. (Aplicación). (B3) Sintetizar la información, evidencias y hechos necesarios para analizar un problema. (Análisis - Síntesis). (B4) Formular hipótesis. Todos Exposiciones del profesor, talleres, tareas y lecturas Exámenes, Talleres, proyecto
(C) Diseño (C1) Utilizar estándares de codificación en la implementación de componentes de software. (Aplicación). (C2) Identificar componentes, interacciones, relaciones e interfaces entre componentes. (Análisis). (C3) Diseñar procesos y componentes de software haciendo uso de la notación, técnicas y herramientas adecuadas. (Síntesis). (C4) Evaluar un componente de software de acuerdo a su complejidad temporal y espacial. (Evaluación). Todos Exposiciones del profesor, talleres, tareas y lecturas Exámenes, Talleres, proyecto
(F) Comunicación efectiva (F2) Comunicarse de manera efectiva de acuerdo al público objetivo haciendo uso correcto del lenguaje, estilo, tiempo y expresión corporal. (Aplicación). (F4) Defender ideas con precisión y claridad. (Evaluación). Todos Ejercicios de demostración, presentación oral y escrita de talleres Exámenes y proyecto
(J) Modelamiento y diseño de sistemas computacionales (J1) Reconocer la importancia del modelamiento cuando se resuelve un problema. (Compresión). (J2) Relacionar conceptos y principios teóricos para la resolución efectiva de un problema. (Síntesis). (J4) Evaluar decisiones de diseño basándose en principios matemáticos y de computación. (Evaluación). Todos Exposiciones del profesor, talleres, tareas y proyectos Exámenes, Talleres, proyecto
(K) Desarrollo de software (K3) Establecer invariantes y propiedades de componentes de software. (Análisis). Todos Exposiciones del profesor, talleres, tareas y proyectos Exámenes, Talleres, proyecto

Contribución al Desarrollo de Competencias (CNA)

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.

Resultados de Programa
A B C D E F G H I J K
Comunicación escrita E E E E E E
Lectura crítica E E E
Inglés U U U U U U
Razonamiento cuantitativo E E E E E

E- Se evalúa. U - Se usa

Contribución a los objetivos educacionales

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.
Resultados de Programa
A B C D E F G H I J K
Objetivo 1 X X X X X
Objetivo 2 X X X X X X
Objetivo 3 X
Objetivo 4 X X X X X
Objetivo 5 X X X X X X

Recomendaciones del Director del Programa

Reglas del curso

Calificación y Balance de Evaluación del Curso

Instrumento Porcentaje A B C D E F G H I J K
Parcial 1 20 % 17 % 10 % 15 % 11 % 30 % 17 %
Parcial 2 20 % 17 % 10 % 15 % 11 % 30 % 17 %
Examen final 20 % 17 % 10 % 15 % 11 % 30 % 17 %
Proyecto 20 % 17 % 15 % 10 % 6 % 30 % 22 %
Talleres y quices 20 % 17 % 5 % 20 % 16 % 30 % 12 %

Uso de material en exámenes

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

Asistencia

Es obligatoria.

Bibliografía

  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.

Instalaciones

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

Material de este semestre

 
materias/analisisdisenoalgoritmos.txt · Última modificación: 2016/09/02 11:38 por camilo.rocha
Recent changes RSS feed Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki