Objetivo general

Proporcionar  al alumno las técnicas algorítmicas básicas que le permitan construir programas para resolver problemas  de mediana escala, poniendo especial énfasis en criterios de “corrección” y eficiencia.

UNIDAD 1. Análisis de eficiencia de algoritmos

Contenidos

Definiciones básicas: algoritmos, eficiencia, complejidad temporal y complejidad espacial. El rol del análisis de eficiencia en el desarrollo de programas. Análisis asintótico de cotas de complejidad. Las notaciones “big-O”, “big-Ω” y “big-Θ” para cotas asintóticas superior, inferior y exacta de la complejidad temporal y espacial de algoritmos. Análisis de eficiencia de algoritmos iterativos. Análisis de eficiencia de algoritmos recursivos mediante el uso de relaciones de recurrencia. Trade-off entre espacio y tiempo. Análisis empírico de eficiencia de algoritmos versus análisis teórico.

Objetivos de aprendizaje

Al finalizar el dictado de la Unidad 1 se espera que el alumno sea capaz de:

• Comprender el uso de las notaciones “big-O”, “big-Ω” y “big-Θ” para evaluar algoritmos y usarlas para acotar en tiempo y espacio su complejidad.
• Determinar la complejidad temporal y espacial de algoritmos iterativos.
• Deducir relaciones de recurrencia que describan la complejidad temporal de algoritmos recursivos.
• Resolver relaciones de recurrencia.

 

UNIDAD 2. Tipos de Datos Abstractos (TDA)

Contenidos

2.1. Especificación algebraica de TDA. Tipos de datos como conjunto de valores con un conjunto de operaciones.  Clasificación de operaciones. Método general de construcción de especificaciones algebraicas de TDA. Especificación algebraica de tipos de datos básicos tales como pilas, filas, listas y árboles binarios. Estructuración de especificaciones. Parametrización e instanciación. Relaciones de herencia y cliente.

2.2. Implementación de tipos de datos abstractos. Relación entre especificaciones algebraicas y clases orientadas a objetos: parametrización, relaciones de herencia y cliente. Especificaciones incompletas y clases abstractas. Implementación de TDA básicos. Ejemplos adicionales de TDA: Heap y Union-Find.

 

Objetivos de aprendizaje

Al finalizar el dictado de la Unidad 2 se espera que el alumno sea capaz de:

• Comprender los  potenciales beneficios del uso de especificaciones formales para la construcción de programas “correctos”.
• Poder abstraer las propiedades esenciales de los tipos de datos involucrados en un problema algorítmico e identificar cómo se relacionan, en forma independiente de una implementación en un lenguaje de programación.
• Especificar algebraicamente tipos de datos abstractos básicos.
• Diseñar e implementar  clases  y jerarquías de clases estructuradas por mecanismos de herencia y cliente.
• Dilucidar la relación entre la estructura estática de una clase y la estructura dinámica de sus instancias.
• Justificar los conceptos de encapsulamiento, abstracción, herencia y polimorfismo
• Elegir estructuras  eficientes de datos para implementar tipos de datos.
• Evaluar la eficiencia de algoritmos que involucren el uso de varios TDA.

 

 UNIDAD 3. Técnicas de diseño de algoritmos

Contenidos

3.1. Divide y conquista. Caracterización del tipo de problemas resolubles por divide y conquista. Esquema algorítmico. Problemas representativos: ordenamiento (Mergesort, Quicksort), multiplicación de matrices por el algoritmo de Strassen y multiplicación de matrices ralas basada  en Quadtrees.

3.2. Greedy. Caracterización del tipo de problema. Esquema algorítmico. Principio de optimalidad y  función de selección. Problemas representativos: el problema de la mochila, minimización de tiempos de espera y planificación de tareas.

3.3. Programación dinámica. Caracterización del tipo de problemas resolubles por programación dinámica. Principio de optimalidad. Formulación recursiva y memorización. Problemas representativos: multiplicación de secuencias de matrices, construcción de árboles binarios de búsqueda óptimos y  el problema de la subsecuencia más larga entre cadenas.

 

Objetivos de aprendizaje

Al finalizar el dictado de la Unidad 3 se espera que el alumno sea capaz de:

• Captar la esencia de las técnicas de diseño de algoritmos y poder identificar para cada una  de ellas problemas que ejemplifiquen los conceptos subyacentes.
• Implementar algoritmos basados en la técnica de diseño “Divide y Conquista”.
• Implementar algoritmos basados en la técnica de diseño “Greedy”
• Implementar algoritmos basados en la técnica de diseño “Programación dinámica”.
• Adquirir una metodología para la especificación, diseño e implementación de soluciones algorítmicas basada en la elección de técnicas de diseño e implementaciones de TDA.
• Poder analizar críticamente cuál es la técnica de diseño adecuada para resolver un problema. y adaptar esquemas algorítmicos para resolver problemas específicos.
• Producir programas de tamaño medio, fiables y fáciles de entender, modificar, mantener y reutilizar a partir de una metodología de programación basada en TDA.