Estructura de Datos con Orientación a Objetos

De manera muy general hay concenso de algunas cosas: que esta UEA fue diseñada cuando no habí­a Ingenierí­a en Computación, que algunos de los temas son demasiado repetitivos y que otros son demasiado poco profundos, que valdrí­a la pena considerar separar el temario en dos UEA (una de Estructura de Datos y otra de Orientación a Objetos) pero que al mismo tiempo habrí­a que considerar el impacto que esto tendrí­a en el Plan de Estudios de Ingenierí­a en Computación (seriación, número de créditos, etc.). Ana (separar en dos), Blanca (separar en dos), Francisco (separar en dos) y Lourdes (disminuir temas de orientación a objetos, redistribuir en otra parte) opinaron al respecto. Germán fué más claro: "Creo que el objetivo del curso debe ser la de presentar los conceptos abstractos, mostrar la forma en que estos conceptos se usan para resolver problemas y después la manera en que la abstracción puede volverse concreta mediante un lenguaje de programación; ie., la idea es enfatizar la versión abstracta y concreta de un concepto de tal forma que el estudiante aprenda sobre el concepto en sí­, su implantación y su aplicación; por lo que la metodologí­a orientada a objetos. ie.,  la metodologí­a OO debiera ser una uea optativa junto con otras uas que revisen otras metodologí­as tales como: la paralela, la concurrente, la funcional."

Objetivos

  1. Conocer algunas técnicas de ingenierí­a de software usadas en el diseño y la implantación de programas en lenguaje de programación Java o C++.
  2. Aplicar técnicas de programación usando estructuras y recursividad.
  3. Implantar estructuras de datos usando memoria estática y memoria dinámica.
  4. Utilizar las clases contenedoras de un lenguaje orientado a objetos.
  5. Aplicar las estructuras de datos más convenientes para la solución de problemas especí­ficos.

Contenido Sintético

  1. Introducción al diseño y a la programación orientada a objetos
  2. Listas lineales
  3. Recursividad
  4. Árboles
  5. Manejo de archivos
  6. Búsqueda y ordenamiento

Introducción al diseño y a la programación orientada a objetos

  1. Objetivo especí­fico actual: Contar con el marco teórico para el uso de la programación orientada a objetos.
  2. Contenido actual: Fundamentos del modelo de objetos. Concepto de objeto, estado y comportamiento. Concepto de clase. Relaciones entre clases. Clases y objetos en el lenguaje de programación. Referencias y/o apuntadores. Ejemplos y aplicaciones. 12 horas de clase = 8 clases.
  3. Josué: Bien en lo general.
  4. Óscar: Clases, polimorfismo y herencia. Apuntadores, referencias, funciones, sobrecarga, memoria dinámica, excepciones. STL: contenedores, iteradores.
  5. Francisco: Pasar "apuntadores" al siguiente tema y traer acá el tema de "concepto de tipo de dato abstracto". Reducir a 6 clases. No ver aquí­ ni memoria dinámica ni la STL.

Listas lineales

  1. Objetivo especí­fico actual: Utilizar las estructuras lineales en la solución de problemas.
  2. Contenido actual: Concepto de tipo de dato abstracto. Estructuras de datos implementados mediante arreglos: secuencias, pilas y colas. Estructuras de datos lineales utilizando memoria dinámica: secuencias, pilas, colas, dobles colas. Utilización de clases de biblioteca. Ejemplos y ejercicios. 12 horas de clase = 8 clases.
  3. Josué: Bien en lo general.
  4. Óscar: Listas simples, dobles, circulares, vectores dispersos, pilas, colas y colas de prioridad.
  5. Georgii: Pasar el punto "concepto de tipo de dato abstracto" al tema anterior.
  6. Francisco: Pasar "concepto de tipo de dato abstracto" al tema anterior y poner aquí­ los temas de apuntadores y memoria dinámica. Colas, pilas, listas simples, dobles y circulares. Como aplicaciones de pilas ver conversión de infija a postfija. Como aplicaciones de listas ver alguna selección de: secuencias, vectores, polinomios, números grandes, colas de prioridad.

Recursividad

  1. Objetivo especí­fico actual: Utilizar la recursividad para simplificar el desarrollo de algoritmos.
  2. Contenido actual: Principios de la recursividad. Condiciones necesarias en un algoritmo recursivo. Dividir para vencer. Prueba de los algoritmos recursivos. Solución de problemas con recursividad. 4.5 horas de clase = 3 clases.
  3. Josué: Bien en lo general.
  4. Óscar: Recursividad. Definiciones, llamadas a funciones e implementación. Tail recursion "Recursion por cola". NonTail Recursión. Recursión indirecta. Recursión anidada. Retroceso. Efectos de la recursión en la máquina (pila y apuntador de pila).
  5. Francisco: Recursión lineal, binaria y múltiple. Recursión directa, anidada e indirecta. Casos simples de eliminación de la recursión. Efectos de la recursión. 4 clases.

Árboles

  1. Objetivo especí­fico actual: Conocer y utilizar las estructuras de árboles. Realizar recorridos y aplicar el TDA árbol en el modelado de problemas.
  2. Contenido actual: Concepto de árbol. Representación de árboles binarios. Recorridos. Árboles binarios de búsqueda: búsqueda, inserción y remosión. Árboles balanceados. Ejemplos y aplicaciones. 7.5 horas de clase = 5 clases.
  3. Josué: Renombrar a "árboles binarios" y sólo una introducción a los árboles AVL.
  4. Óscar: Árboles, árboles bianarios, de búsqueda. Inserción, remosión y búsqueda. Recorridos. Árboles de expresión. Árboles AVL. Árboles B.
  5. Francisco: Árboles binarios de búsqueda (operaciones) y árboles de expresión (evaluación). No ver árboles balanceados aquí­. 4 clases.

Manejo de archivos

  1. Objetivo especí­fico actual: Utilizar las clases de entrada y salida para modelar problemas que requieran el manejo de información persistente.
  2. Contenido actual: Concepto de archivo. Operaciones de apertura, lectura, escritura y cierre. Clases de biblioteca para el manejo de archivos. Archivos de texto. Control de formato. Archivos binarios. Excepciones. Ejemplos y aplicaciones. 4.5 horas de clase = 3 clases.
  3. Josué: Entrada y salida de objetos (no sólo de los tipos simples).
  4. Óscar: Flujos. Apertura, lectura y escritura, cierre. Una clase. Aplicaciones: Compresión. Codificación de Huffman. Códigos de Shannon-Fano. RLE.
  5. Francisco: Reducir a 1 clase. Las demás cosas mencionadas arriba son parte del temario de Almacenamiento y recuperación de la información.

Búsqueda y ordenamiento

  1. Objetivo especí­fico actual: Conocer los principales métodos de búsqueda y ordenamiento de información en memoria. Aplicar los criterios para seleccionar los métodos de ordenamiento más adecuados de acuerdo a la naturaleza del problema. 3 horas de clase = 2 clases.
  2. Contenido actual: Búsqueda secuencial. Búsqueda binaria. Ordenamientos elementales: inserción directa, intercambio directo. Métodos de ordenamiento avanzados: Shell, por montí­culos y rápido.
  3. Josué: Ordenamiento de objetos y no mencionar las clases de complejidad O(n log n), etc.
  4. Óscar: Elementales: inserción, selección, burbuja. Árboles de decisión. Eficientes: Shell, heap, Quick, Merge, Radix. Análisis de complejidad (solo introductorio con notación asintótica). Tablas Hash. Métodos. Funciones hash. Colisiones: direccionamiento abierto y encadenamiento.
  5. Francisco: Búsquedas secuencial, binaria y dispersión (2 clases). Ordenamientos elementales y árboles de decisión (2 clases). Ordenamientos eficientes: ordenamiento por mezcla, ordenamiento de Shell y Quicksort (3 clases). Posiblemente ordenamiento por montí­culo, por cuenta, por raí­z, etc.

Bibliografí­a

  1. Actual: Weis, M. A. Estructuras de datos en Java. Addison Wesley. 2000. Joyanes A., L. Programación en C++: Algoritmos, estructuras de datos y objetos. Mc Graw Hill. 2000.
  2. Baase (Algoritmos), Parberry (Problemas), Rohl (Recursión), Sedgewick (Algoritmos en C++), etc.