Agencia de Gobierno Electrónico y Sociedad de la Información y del Conocimiento

D. Programa de Estructuras de Datos y Algoritmos

1. Datos de la Actividad Curricular

• Nombre: Estructuras de Datos y Algoritmos
• Área de formación: Programación
• Créditos: 12

2. Objetivos

El objetivo de esta actividad curricular es introducir estructuras de datos básicas y sus algoritmos de manipulación, realizar un análisis de su eficiencia, e introducir el concepto de abstracción de datos para el diseño y la evaluación de algoritmos de porte mediano.

A nivel de los objetivos de aprendizaje, el estudiante será capaz de:

• Implementar y analizar algoritmos recursivos.
• Definir y manipular estructuras de datos lineales y arborescentes, tantto estáticas como dinámicas.
• Reconocer los conceptos de modularización, abstracción de datos, en- capsulamiento y Tipo Abstracto de Datos (TAD).
• Explicar la diferencia entre especificación, implementación y uso de TADs.
• Especificar diferentes TADs y ejemplificar su uso. Por ejemplo: Lista, Pila, Cola de Prioridad, Conjunto, Mapping y Grafo.
• Implementar TADs usando estructuras de datos, por ejemplo arreglos, estructuras de datos lineales y arborescentes de memoria dinámica, tablas de dispersión y árboles parcialmente ordenados.
• Elegir estructuras de datos adecuadas para implementar los TADs teniendo en cuenta requerimientos de eficiencia en tiempo de ejecución y espacio de almacenamiento.
• Definir nociones de eficiencia para aplicarlas al análisis de los algoritmos de las estructuras vistas.
• Identificar qué TADs se vinculan con la resolución de ciertos problemas.

3. Metodología de enseñanza

• Horas clase (teórico): 45
• Horas clase (práctico y laboratorio): 75
• Horas evaluación: 6
• Horas estudio: 54

Total de horas de dedicación del estudiante: 180

4. Temario

1. Iteración y recursión
   1. Implementación de invocaciones a procedimientos y funciones
   2. Implementación y uso de esquemas recursivos
   3. Análisis comparativo entre algoritmos recursivos e iterativos
2. Introducción al análisis de algoritmos
   1. Eficiencia en espacio de almacenamiento y tiempo de ejecución
   2. Tiempo de ejecución y orden del peor caso de algoritmos iterativos y recursivos
   3. Introducción al análisis del caso promedio
3. Estructuras de datos estáticas y dinámicas
   1. Estructuras de datos lineales. Distintos tipos de listas
   2. Estructuras de datos arborescentes. En particular, árboles binarios, binarios de búsqueda, árboles balanceados y árboles generales
   3. Tablas de dispersión (hashing)
   4. ) Montículos binarios (binary heap)
   5. Implementación de estructuras múltiples para resolver problemas con restricciones de eficiencia
4. Tipos abstractos de datos (TADs)
   1. El rol de la abstracción en el diseño de sistemas
   2. Especificación e implementación de TADs Distintos tipos de listas, pilas y colas

Conjuntos, multiconjuntos, funciones parciales (mappings, tablas) y colas de prioridad.

Grafos

3. Uso de TADs en la resolución de problemas de porte mediano

5. Bibliografía

Básica

1. Mark A. Weiss. Data Structures and Algorithm Analysis in C (2nd Edition), (1996).

Complementaria

1. B. W. Kernighan, D. M. Ritchie. El lenguaje de programación C (Spanish Edition), (2021).
2. H. M. Deitel, P. J. Deitel. Cómo programar en C/C++. Prentice-Hall Hispanoamericana, (1998).
3. G. Brassard, P. Bratley. Fundamentos de Algoritmia. Prentice Hall, (1998).

6. Conocimientos Recomendados

Conocimientos Previos Exigidos Matemática Discreta y Lógica 1. Introducción a la Programación.

Conocimientos Previos Recomendados Solo se requieren conocimientos de los cursos Matemática Discreta y Lógica 1, e Introducción a la Programación. Se ubicaría en el segundo semestre del primer año de la carrera.