Guia de estudio ED

UNIVERSIDAD CAECE
DEPARTAMENTO DE SISTEMAS


PROGRAMA DE:
ALGORITMOS Y ESTRUCTURAS DE DATOS II
CODIGO DE LA CARRERA

PLAN DE LA CARRERA

CODIGO ASIGNATURA

AÑO

CUATRIMESTRE

VIGENCIA

CARRERA:

LICENCIATURA EN SISTEMAS
Nº DE RESOLUCIÓN MINISTERIAL

Nº DE RESOLUCIÓN INTERNA

OBJETIVOS
Que los alumnos logren:

Profundizar en la separación de la especificación abstracta de tipos abstractos dedatos (TADs) respecto a la implementación de los mismos.

Conocer nuevas estructuras de datos y combinadores para la especificación e implementación de TADs de un alto nivel de abstracción y complejidad de implementación.

Conocer todas las características del paradigma de programación orientado a objetos, y sus características de mantenibilidad y extensibilidad respecto al estilo de programaciónconocido hasta el momento.

Poder implementar TADs complejos en un lenguaje de programación del paradigma de orientación a objetos, como el lenguaje de programación Java, extendidos con el concepto de orientación a objetos.

PROGRANA ANALITICO

Unidad 1. Introducción.
Lenguajes de programación de tercera generación. Programación no estructurada y estructurada. Programación modular (procedimientos yfunciones). Lenguajes tipados y no tipados. Tipificación fuerte/débil, estática/dinámica. Mapeo de la realidad a un programa estructurado. El tratamiento de los datos por parte de un programa estructurado. Tipos de variables. Tipos estructurados. Tipos definidos por el usuario. Variables estáticas y dinámicas. Uso de punteros. El problema de la liberación de memoria de variables dinámicas.Abstracción y encapsulamiento. Los TADs. Especificación axiomática (funcional) e implementación de TADs. Componentes de la especificación axiomática (constructores, proyectores, otras operaciones y axiomas). Tipos de datos de implementación básicos (enteros, booleanos, reales, caracteres, strings) y estructurados (arreglos, registros y punteros). Introducción a los tipos paramétricos. Manejo de tiposvariables en especificación e implementación (con o sin restricciones de existencia de ciertas operaciones sobrecargadas). Operaciones de implementación. Operaciones constructoras y destructoras.

Unidad 2. Recursión.
Definición y objetivo de la recursión. Relación entre recursión e inducción matemática. Recursión sobre procedimientos y funciones. Diferencias y casos. Casos base y recursivo.Definición funcional de la recursión (axiomas), y su relación con la recursión sobre algoritmos (procedimientos y funciones imperativas). Recursión aplicada sobre estructuras de datos básicas (números naturales “como simples números”).
El concepto de orden bien fundado sobre la estructura (muy básico e intuitivo) para explicar la terminación de un algoritmo recursivo (o definición completa de una funciónrecursiva).
Implementación de la recursión (explicación de la pila de registros de activación).
Recursión simple, doble (mutua). Recursión directa, indirecta. El concepto de backtracking.
Estructuras de datos recursivas: números naturales con la notación de constructores (constante cero y función sucesor), listas y otras similares.
Modularidad aplicada a la recursión. Definición de especificacionesaxiomáticas/algoritmos en función de otras especificaciones axiomáticas/algoritmos. Definiciones de especificaciones / implementaciones de TADs en función de otros TADs.
Recursión de pila (stack recursion), de cola (tail recursion). Comparaciones.
Cuándo y cómo evitar la recursión. La recursión de cola como iteración. Conversión de recursión de cola a iteración. Utilización de estructuras depila/cola explícitas para evitar la recursión.

Unidad 3. Arboles binarios.
Idea básica. Definición del TAD. Definición estructural recursiva funcional. Definición funcional (axiomática) de operaciones sobre árboles binarios (recursivas de pila, recursivas de cola-iterativas, iterativas con uso de estructuras de pila/cola explícita). Recorridos depth-first (pre-order, in-order, post-order)....