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

Información Básica

  • Créditos: 3
  • Horas de Clase: 4 / semana
  • Horas de trabajo independiente: 5 / semana
  • Horas de Laboratorio al semestre:
  • Tipo de curso: Núcleo de Formación Fundamental.

Descripción del Curso

Este curso estudia técnicas bien conocidas en el diseño de algoritmos como dividir y conquistar, programación dinámica, la técnica voraz y backtracking. 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. Adicionalmente, el curso aborda el estudio de problemas intratables y las alternativas para su solución, como algoritmos aleatorizados, paralelos o probabilisticos. Finalmente se retoma la teoria de la NP-completitud en lo referente a realizar demostraciones por reducción.

Objetivos

Al finalizar el curso los participantes podrán:

  1. Utilizar las tecnicas de diseño para proponer soluciones eficaces y eficientes a problemas del mundo real.
    1. Modelar formalmente un problema real como un problema abstracto, algorítmico.
    2. Diseñar algoritmos que resuelvan problemas del mundo real, siguiendo técnicas de diseño como dividir y conquistar, backtracking, programación dinámica o algoritmos voraces.
    3. Aplicar algoritmos clásicos (como ordenamiento, búsqueda en grafos, hallar caminos mínimos en grafos, entre otros) al modelamiento de situaciones reales.
    4. Extender y adaptar algoritmos y estructuras de datos clásicas para dar solución a problemas planteados.
    5. Desarrollar soluciones para problemas algorítmicos intratables computacionalmente.
  2. Analizar rigurosamente el desempeno de algoritmos y de operaciones en estructuras de datos.
    1. Argumentar rigurosamente la corrección de los algoritmos clasicos estudiados y de los algoritmos propios.
    2. Analizar la complejidad temporal y espacial de algoritmos usando cotas superiores y cotas estrechas, para el mejor caso, el peor caso o el caso promedio.
    3. Escoger el algoritmo y estructura de datos más apropiados para usar en la solución de un problema determinado atendiendo a criterios de eficacia y eficiencia computacional.

Contenido

Capítulo 1: Introducción

Sesión Horas de Clase Tópicos Bibliografía
1 2 Presentación del curso, introducción al análisis y diseño de algoritmos, repaso de análisis de complejidad y demostraciones de corrección [1,cap 1]

Total de Horas: 2.

Capítulo 2: Técnicas de Diseno

Sesión Horas de Clase Tópicos Bibliografía
2 8 Dividir y conquistar: solución de ecuaciones de recurrencia. Teorema maestro. Ejemplos variados de aplicación de la técnica. [1,cap 4][1,cap 2][1,cap 7][3,cap ?][7,cap 3]
6 10 Programación dinámica. Ejemplos variados de aplicación de la técnica. [1,cap 15][6,cap 9][3,cap ?][7,cap 5]
11 10 Técnica voráz. Ejemplos variados de aplicación de la técnica. [3,cap ?][7,cap 4]

Total de Horas: 28.

Capítulo 3: Estructuras de Datos Eficientes

Sesión Horas de Clase Tópicos Bibliografía
16 2 Estructura Union-Find [1,cap 21]
17 2 Arboles de Busqueda [1,cap 12]
18 2 Arboles Rojo y Negro. Arboles B [1, cap 13][1,cap 18]
19 2 Heap Binomial [1,cap 19]

Total de Horas: 8.

Capítulo 4: Problemas Intratables

Sesión Horas de Clase Tópicos Bibliografía
20 10 Backtracking. Ejemplos variados de aplicación de la tecnica [7,cap 7][3,cap ?]
25 2 El metodo Simplex de programación lineal [1,cap 29]
26 4 Algoritmos de aproximación y aleatorizados [1,cap 35]

Total de Horas: 16.

Capítulo 4: Teoria de la NP-completitud

Sesión Horas de Clase Tópicos Bibliografía
28 6 Demostraciones de NP-completitud [1,cap 34][4,cap ?]

Total de Horas: 6.

Integración Curricular

Resultados de Programa (ABET)

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

B. La habilidad para diseñar y conducir experimentos así como para analizar e interpretar datos.

C. La habilidad para diseñar un sistema, componente o proceso para satisfacer necesidades deseadas dentro de restricciones realistas.

D. La habilidad para funcionar en equipos multidisciplinarios.

E. La habilidad para identificar, formular y resolver problemas de ingeniería.

F. El entendimiento de la responsabilidad profesional y ética.

G. La habilidad para comunicarse efectivamente.

H. La educación amplia y necesaria para entender los impactos de las soluciones de ingeniería en contextos globales económicos, ambientales y sociales.

I. El reconocimiento de la necesidad de, y la habilidad para, continuar el aprendizaje a lo largo de la vida.

J. El conocimiento de asuntos contemporáneos.

K. La habilidad para usar las técnicas, destrezas y herramientas modernas de ingeniería necesarias para la práctica de la ingeniería.

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 2 5 1

Escala: (1) baja relevancia - (5) alta relevancia.

Relación de objetivos del curso con resultados de programa y estrategia de evaluación

Resultados del Programa Objetivos del Curso Actividades de aprendizaje Instrumentos de medición
A. Conocimiento técnico. Todos Solución ejercicios Exámenes, talleres, proyecto
B. Habilidades experimentales. 2.1, 2.2, 2.3 Solución ejercicios Exámenes, talleres
C. Diseño de ingeniería. Todos Solución ejercicios, Proyecto Exámenes, talleres, proyecto
D. Trabajo en equipo N/A N/A N/A
E. Solución problemas de ingeniería. Todos Solución ejercicios, Proyecto Exámenes, talleres, proyecto
F. Responsabilidad ética. Práctica de las reglas del curso Observancia de las reglas del curso
G. Comunicación efectiva. 2.1 Demostraciones, sustentación Talleres, proyecto
H. Amplitud de conocimiento. N/A N/A N/A
I. Aprendizaje de por vida. Todos Solución de ejercicios Talleres
J. Asuntos contemporáneos. N/A N/A N/A
K. Uso de herramientas de ingeniería. 1.4, 1.5, 2.3 Solución de ejercicios Exámenes, talleres, proyecto

Recomendaciones del Director del Programa

Reglas del curso

Calificación

Porcentaje
Primer parcial 20 %
Segundo parcial 20 %
Tercer parcial 20 %
Talleres y quices 20 %
Proyecto 20%

Uso de material en exámenes

Talleres, Quices y Proyecto

Se deben resolver en forma individual y todas las soluciones deben ser originales, es decir, no es aceptable reutilizar código ni descargar respuestas de internet.

Asistencia

Obligatoria

Matriculación

  1. 2011-2:
  2. 2011-1:
  3. 2010-2:

Recursos

Ejemplos:

Demo PAPI

Bibliografía

  1. T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to algorithms. MIT Press, Cambridge, MA, USA, 2001.
  2. G. Brassard and P. Bratley. Algorithmics: theory & practice. Prentice-Hall, Inc., Upper Saddle River, NJ, USA, 1988.
  3. S. Dasgupta, C. H. Papadimitriou, and U. Vazirani. Algorithms. McGraw-Hill Science/Engineering/Math, 2006.
  4. S. S. Skiena. The algorithm design manual. Springer-Verlag New York, Inc., New York, NY, USA, 1998.
  5. Garey, M. R. and Johnson D. S. Computers and intractability : a guide to the theory of NP-completeness. W.H. Freeman & Company, USA, 2003
  6. Maning C. D. and Schutze H. Foundations of Statistical Natural Language Proccessing. MIT Press, 2000.
  7. Horowitz E. Sahni S. Fundamentals of Computer Algorithms. Computer Science Press. 1978.

Instalaciones

Salón de clase con computador y proyector.

 
materias/analisis_y_diseno_de_algoritmos.txt · Última modificación: 2014/06/19 14:24 por lfrincon
Recent changes RSS feed Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki