Instituto Tecnológico y de Estudios Superiores de Monterrey

Campus Estado de México

División de Ingeniería y Arquitectura

Departamento de Ciencias Computacionales


Clave: Cs-95-039
Materia: Introducción al diseño y análisis de algoritmos
Requisitos: Teoría de la computación

 
OBJETIVO GENERAL DE LA MATERIA

El alumno conocerá los métodos usados para calcular la complejidad computacional de un algoritmo, y los aplicará a varios algoritmos con el fin de determinar cuál es más eficiente.

El alumno seleccionará las estructuras de datos y técnicas de programación apropiadas para diseñar un algoritmo eficiente desde el punto de vista de su complejidad computacional.

 
TEMAS Y SUBTEMAS

  1. Conceptos Básicos

    2. 1.1 Iteración y recursión
    1.2 Inducción matemática
    1.3 Estructuras de Datos

  2. Complejidad Computacional

    3. 2.1 Complejidad temporal
    2.2 Complejidad espacial

  3. Técnicas de programación

    4. 3.1 Recursión
    3.2 Divide y Conquista
    3.3 Balanceo
    3.4 Programación Dinámica
    3.5 Algoritmos avaros

  4. Análisis de la complejidad de algoritmos

    5. 4.1 Algoritmos para grafos
    4.2 Algoritmos para matrices
    4.3 Algoritmos para el reconocimiento de patrones

  5. Clasificación de los problemas con base a su complejidad

5.1 Problemas P y NP
5.2 Algoritmos paralelos y probabilistas
OBJETIVOS ESPECIFICOS DE APRENDIZAJE POR TEMA

1. El alumno recordará los conceptos básicos para el diseño de algoritmos eficientes.

    1. El alumno identificará los conceptos de iteración y recursión en un algoritmo terminando con la clasificación del mismo.

    2. El alumno definirá conceptos recursivos empleando la inducción y finalizará el ejercicio derivando un ejemplo del concepto.

    3. El alumno seleccionará las estructuras de datos apropiadas para diseñar un algoritmo iterativo o recursivo, para resolver un problema dado.


2. El alumno conocerá los métodos para medir la complejidad computacional de un algoritmo.
2.1 El alumno calculará la complejidad de un algoritmo: en el peor, en el promedio, y en el
mejor de los casos, y determinará sus límites asintóticos.
2.2 Dados dos algoritmos, el alumno determinará bajo que circunstancias uno es mejor que
otro, basándose en los tiempos de corrida y la complejidad asintótica de ambos. Al
final deberá reportar su análisis.
3.3 Formulará una ecuación de recurrencia que describa el comportamiento de un algoritmo
recursivo y la resolverá usando alguno de los siguientes métodos: iteración,
sustitución, y maestro; terminando la solución con la complejidad en notación O.

3. El alumno comparará algunas técnicas de programación útiles en el diseño de algoritmos.
3.1 El alumno distinguirá las técnicas de programación empleadas en un algoritmo
dado, concluyendo con el listado de las mismas.
3.2 El alumno diseñará un algoritmo eficiente para resolver un problema empleando
alguna o algunas de las técnicas de programación vistas en clase.

4. El alumno analizará distintos algoritmos para grafos, para matrices, y para el
reconocimiento de patrones.
4.1 Modelará un problema empleando los grafos y propondrá una solución al mismo.
4.2 Analizará la complejidad computacional de los algoritmos y distinguirá las
estrategias usadas para resolver problemas empleando grafos como: cobertura de
grafos, componentes biconectados, y distancias más cortas.
4.3 Conocerá varios problemas en los que se aplica la multiplicación de matrices.
4.4 Calculará la complejidad asintótica de la multiplicación de matrices.
4.5 Demostrará que la inversión de matrices y la solución de sistemas de
ecuaciones tienen la misma complejidad asintótica que la multiplicación.
4.6 Revisará los conceptos de autómata finito, lenguajes y expresiones regulares.
4.7 El alumno comparará diferentes algoritmos existentes para el reconocimiento de
patrones y cadenas.

5. El alumno clasificará a los problemas con base en su complejidad.
3.1 El alumno distinguirá los problemas P de los NP.
3.2 El alumno caracterizará los algoritmos paralelos y los probabilistas.

 
TIEMPO ESTIMADO POR TEMA

Horas de Clase

  1. Conceptos Básicos (4)

  2. Complejidad Computacional (10)

  3. Técnicas de programación (8)

  4. Análisis de la complejidad de algoritmos (14)

  5. Clasificación de los problemas con base a su complejidad (6)


 
METODOLOGÍA Y ACTIVIDADES DE APRENDIZAJE


 
BIBLIOGRAFÍA

Libro de texto:

Libros de consulta:


 
PERFIL DEL PROFESOR
Profesor con maestría en el área de ciencias computacionales.