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.