Algorítmica

Semestre:

4°

Fecha de elaboración:

Agosto de 2013

Fecha de revisión:

Mayo de 2014

Elaborado por:

Nodari Vakhania Maizuradse, Antonio Daniel Rivera López

Ciclo de formación:

Profesional

Área curricular:

Ciencias de la Disciplina

Tipo de unidad:

Teórica

Carácter de unidad:

Obligatoria

Clave:

AG01FP050010

Créditos:

10

Semestre:

4°

Horas Teoría:

5

Horas Práctica:

0

Programas académicos en los que se imparte:

Licenciatura en Ciencias Áreas terminales en Matemáticas, Física, Bioquímica y Biología Molecular, y Ciencias Computacionales y Computación Científica

Prerrequisitos:

Domina los fundamentos matemáticos a través del desarrollo de la habilidad del estudiante para entender y crear argumentos matemáticos.

Antecedentes Recomendadas:

Ninguna

Consecuentes Recomendadas:

  • Teoría de la Computación

Presentación de la unidad de aprendizaje:

Los algoritmos son fundamentales en ciencias computacionales y en ingeniería de software. En esta unidad de aprendizaje, se continúa el estudio de las bases para construir y desarrollar algoritmos eficientes y demostrar su validez.

Propósito de la unidad de aprendizaje:

Comprender y utilizar las herramientas básicas de análisis de algoritmos.

Competencias profesionales:

Utiliza o elabora programas o sistemas de computación para el procesamiento de información, cálculo numérico, simulación de procesos o control de experimentos.Construye modelos computacionales simplificados que describan una situación compleja, identifica sus elementos esenciales y efectúa las aproximaciones necesarias.

Contribución al perfil de egreso:

Para el cumplimiento del perfil, se desarrollan las competencias académicas y profesionales en el área terminal de su elección, que posibiliten el adecuado desempeño para seleccionar, movilizar y gestionar las disposiciones y los recursos disponibles para resolver problemas en un campo determinado de situaciones de acción.

Secuencia temática:

  1. I Introducción informal a los algoritmos y su complejidad.
    1. La definición intuitiva de un algoritmo.
    2. Los medios de expresión de un algoritmo: descripción de alto nivel (el pseudocódigo).
    3. Modelos informales de computación.
    4. El tamaño de un problema y su instancia, y los esquemas de codificación de los problemas.
    5. Complejidad de tiempo y espacio.
    6. Introducción a los problemas (algoritmos) polinomiales e intratables.
    7. Las clases P, NP y problemas NP-completos.
  2. II Demostración de validez y análisis de complejidad de algoritmos.
    1. Divide y vencerás. Aplicaciones: búsqueda binaria, árboles binarios, n-arios y balanceados.
    2. Algoritmo de Euclides.
    3. Algoritmo de Strassen para multiplicar matrices.
    4. Cobertura de árboles: preorder, inorder y postorder.
    5. Búsqueda en profundidad y en altura.
    6. Algoritmos de búsqueda: Bubble sort, Merge sort, Quick sort.
  3. III Algoritmos voraces.
    1. La definición de los algoritmos voraces.
    2. Cobertura mínima de árboles (“minimal spanning trees”): los algoritmos de Prim y Kruskal.
    3. El problema de los tiempos de espera.
    4. El problema de la mochila no-entera.
    5. Calendarización de trabajos a plazos.
  4. IV Introducción a programación dinámica.
    1. Rutas más cortas en grafos con pesos no-negativos: el algoritmo de Dijkstra.

Criterios de Evaluación:

  • Exámenes parciales: 40%
  • Examen final: 30%
  • Participación en clase: 10%
  • Búsqueda de información: 10%
  • Otra (especifique): Tareas: 10%

Bibliografía básica:

  • Aho, J. Hopcropt y Ulman, J. 1974. The design and analysis of computer algorithms. Ed. Addisson-Wesley.
  • Horowitz, E. y Sahni, S. 1978. Fundamentals of computer algorithms. Ed. Computer Science Press.
  • Garey, M. y Johnson, D. 1979. Computers and intractabililty: a guide to theory of NP-completenes. Ed. Freeman and Company.
  • Aho, J. Hopcroft y Ullman, J. 1988. Estructuras de datos y algoritmos. Ed. Addison-Wesley.
  • Dasgupta, Sanjoy, Papadimitriou, Christos y Vazirani, Umesh. 2006. Algorithms. McGraw-Hill.

Bibliografía complementaria:

  • Levitin, Anany. 2006. Introduction to the design & analysis of algorithms. 2a edición. Ed. Addison Wesley.
  • Mehta, D. P. 2004. Handbook of data structures and applications.
  • Kocay, W. Graphs. 2004. Algorithms and optimization. Ed. Chapman and Hall.
  • Dobrushkin, V. A. 2009. Methods in algorithmic analysis. Ed. Chapman and Hall.