Cb-00-831 ESTRUCTURAS DE DATOS

(3 - 0 - 8. Requisito: Haber aprobado Cb00823. 3ISC, 3 ISI, 3 ISE, 3 LSCA)

Este programa ha sido actualizado para entrar en vigor a partir de enero de 2002

Características del curso: Es un curso clásico de Estructuras de datos, pero se parte de la base de que los alumnos ya dominan la programación orientada a objetos en 2 lenguajes, y que ya tienen experiencia con la herramienta de los apuntadores, memoria dinámica y listas encadenadas. Se sigue enfatizando como filosofía de trabajo a la metodología de abstracción de datos. Se incorpora el uso de bibliotecas estándar como el STL. Se esperaría que los alumnos desarrollen una aplicación de mediana complejidad en donde utilicen estructuras de datos.

La incorporación del CTE enfatiza en el uso del lenguaje C/C++.

OBJETIVO GENERAL DE LA MATERIA:

Al finalizar este curso se espera que el alumno:

1. Reafirme los conceptos de abstracción de datos y programación orientada a objetos, a través del conocimiento y aplicación de las estructuras de datos fundamentales en el desarrollo de software.

2. Sea capaz de seleccionar la estructura de datos más adecuada en la solución de un problema que la requiera.

3.Sea capaz de diseñar una nueva estructura de datos, de acuerdo a las necesidades de solución de un problema.

     TEMAS Y SUBTEMAS

1.Introducción. Conceptos preliminares. (10 horas)

1.1.   Abstracción de datos.

1.2.  Clasificación de las estructuras de datos.

1.3. Relación con la programación orientada a objetos.

1.4.  Diseño de un ADT.

1.5. Repaso de los conceptos importantes del lenguaje C++: apuntadores, templates y sobrecarga de operadores.

1.6.Objetos función en C++.

2. Repaso de conceptos de Listas encadenadas y memoria dinámica. (5 horas)

     2.1. Ventajas y desventajas.

     2.2. Variaciones a una lista encadenada:

     2.2.1 Listas circulares.

     2.2.2. Listas doblemente encadenadas.

     2.4. Multiencadenamientos (listas de listas).

3. Estructuras lineales con aplicaciones específicas. (5 horas)

     3.1. Pilas.

     3.1.1. Definición del ADT Pila.

     3.1.2. Representaciones para el ADT Pila.

     3.1.3. Aplicaciones para el ADT Pila.

     3.2. Filas (Colas).

     3.2.1. Definición del ADT Fila.

     3.2.2. Representaciones para el ADT Fila.

     3.2.3. Aplicaciones para el ADT Fila.

4.Concepto de búsqueda. Importancia y propuestas. (2 horas)

4.1.Búsqueda secuencial.

4.2.Búsqueda binaria.

4.3.Tablas estáticas vs. lista dinámica ordenada.

5. Estructuras sin relaciones: Conjuntos o colecciones. (5 horas)

5.1. Definición del ADT Conjunto.

5.2. Búsqueda en un conjunto a través de Hashing.

5.2.1. Diseño de una función de hashing.

5.2.2. Estrategias para el control de colisiones.

5.3. Aplicaciones del ADT Conjunto y Hashing.

6. Estructuras jerárquicas para el almacenamiento y búsqueda eficiente de información. (8 horas)

6.1. Terminología y conceptos generales de las estructuras jerárquicas.

6.2. Arboles Binarios de Búsqueda (ABB).

6.2.1. Definición del ADT ABB. Ventajas y limitaciones.

6.2.2. Implementación de las operaciones básicas.

6.2.3. Aplicaciones del ADT ABB.

6.3. Arboles Binarios de búsqueda balanceados.

6.3.1. Definición del ADT Arbol AVL.

6.3.2. Operaciones básicas: altas y bajas.

6.4 Otras estructuras jerárquicas de búsqueda: Arboles B y variantes.

6.5 Recorridos en árboles binarios.

6.6 Arboles de expresiones.

7. Estructuras de red: Grafos. (4 horas)

7.1. Definición del ADT Grafo. Terminología y tipos de grafos.

7.2. Representaciones para el ADT Grafo.

7.3. Operaciones del ADT Grafo.

7.4. Aplicaciones para el ADT Grafo: Arbol de extensión mínima, Arbol del camino más corto, Cerradura transitiva, etc.

8. Uso del STL (Standard Template Library). (5 horas) [Este tema se incorpora en TODO el contexto de trabajo del curso dado el material del CTE].

8.1. Concepto de contenedor.

8.2. Concepto de iterador.

8.3. Aplicación de las estructuras de datos bajo el contexto de STL.

9. AUTOESTUDIO: Algoritmos de ordenamiento.

LIBRO DE TEXTO

Bibliografía Actualizada

Data Structures in C++ using STL . Timothy Budd .Addison Wesley 1998

LIBROS DE CONSULTA

Metodología sugerida y actividades de aprendizaje

Seguir la estrategia del curso SSD5 del CTE (ver temario del CTE), exponiendo en clase los conceptos relevantes, después de la lectura previa del material por parte de los alumnos. En el material de la unidad 1 se puede avanzar rápidamente, por el conocimiento previo del lenguaje C++.

Los temas no cubiertos por el material del CTE, deberán ser enseñados durante el curso con la estrategia que el profesor decida.

El profesor enfatiza en las sesiones de clase, a través de ejemplos y ejercicios, los conceptos más relevantes del curso.

Los ejercicios y quizes del CTE pueden realizarse fuera del salón del clase, como tarea, y cuando el profesor lo considere, puede permitir el trabajo en equipo para la solución de algunos ejercicios.

Las sesiones de clase, también pueden ser utilizadas por el profesor, para resolver dudas de los ejercicios, o bien, para aplicar alguno de los quizes cortos del CTE.

Los exámenes de unidad del CTE deberán ser aplicados fuera de la sesión de clase, en el Centro de evaluación del propio campus, bajo las políticas definidas, en las fechas establecidas por el profesor.

Políticas de evaluación sugeridas

                Exámenes de unidad de CTE                                  55%

                Actividades de aprendizaje del CTE                       30%

                Examen final ITESM                                                 15%

Puesto que los exámenes de unidad, no necesariamente coinciden con los períodos de exámenes parciales del calendario del ITESM, se sugiere reportar como calificación parcial, un promedio de las calificaciones obtenidas hasta el momento del reporte.

Software de apoyo

Compilador de  C++ (CTE sugiere el Cygwin) .

Perfil del profesor

Profesor certificado por el CTE en SSD5, con maestría y carrera en el área de computación, con experiencia en desarrollo de software, de preferencia en lenguaje C++.