Descripción

Presentar conceptos básicos del diseño y análisis de algoritmos. Al finalizar el curso, el estudiante debe ser capaz de aplicar técnicas de desarrollo de algoritmos como dividir y conquistar, programación dinámica, utilizar diversos algoritmos de búsqueda y analizar su complejidad en tiempo y en espacio.

– Semántica

• Operacional
• Axiomática

Semántica operacional de un lenguaje de comandos guardados (GCL) definida sobre una máquina abstracta simple. Semántica axiomática presentada como un modelo teórico del cual es instancia la semántica operacional.

– Complejidad

Se elige estimar el desempeño de algoritmos basado en estimaciones de peor caso.
Se suponen conocimientos de cálculo (uso de notación O).
Se suponen conocimientos de solución de ecuaciones de recurrencia (lineales o no -lineales reducibles a éstas mediante cambios de dominios).

– Derivación de algoritmos

• Algoritmos sin ciclos
• Algoritmos con ciclos
• Algoritmos recurrentes

Presentación y práctica de una metodología de desarrrollo de programas basada en especificaciones formales (pre- poscondiciones).

– Estrategias generales

• Divide y vencerás
• Programación dinámica

Presentación de estrategias generales aplicables en situaciones conocidas.

– Ruta óptima en grafos

• Algoritmos clásicos de optimización para ruteo óptimo en grafos

Ejemplo de problemas solucionables de manera óptima y conocida.

– Búsqueda en grafos

• Algoritmos A, A*

Solución genérica de problemas de búsqueda. Nivel introductorio.

– Intratabilidad

• P : NP

Conceptos fundamentales. Nivel introductorio.