Programación y Estructuras de Datos
Verano 2015
Dr. René Cumplido. Contacto: rcumplido(at)inaoep.mxHorario: Lunes 15 - Jueves 18 de Junio, de (por definir) a (por definir). Salón del edif. Chavira
Introducción
Se espera que el/la estudiante que ingrese a la maestría, domine detalladamente conceptos de programación y estructuras de datos con un enfoque orientado a objetos, a través de su implementación en C++. Esto incluye las siguientes habilidades:- Dominio de programación estructurada y orientada a objetos.
- Dominio de la aplicación eficiente de clases, encapsulación, herencia y polimorfismo.
- Dominio de conceptos básicos de estructuras de datos relacionados a pilas, colas, listas, árboles y grafos.
- Dominio de la aplicación de estructuras de datos a través del lenguaje C++
1. Fundamentos de programación
1.1. Principios de Ingeniería de software
1.2. C++ Sintaxis y semántica
1.3. Condiciones expresiones lógicas, estructuras de selección y ciclos
1.4. Funciones
1.5. Tipos de datos simples
1.6. Tipos de datos estructurados
1.7. Recursión
2. Desarrollo orientado a objetos
2.1. Objetos,
2.2. Herencia y polimorfismo
2.3. Composición
3. Apuntadores
3.1. Variables y expresiones apuntador
3.2. Tipos de referencia
3.3. Datos dinámicos y clases
4. Diseño de datos e implementación
4.1. Vistas diferentes de los datos
4.2. Tipos de datos abstractos
4.3. Abstracción de alto nivel y la clase Type
4.4. Comparación de algoritmos
5. La estructura abstracta lista
5.1. El concepto de lista desordenada
5.2. Implementación de una estructura lista desordenada
5.3. El concepto de lista ordenada
5.4. Implementación de una lista ordenada
6. Pilas y Colas
6.1. El concepto de pila
6.2. Implementación de pilas como una estructura ligada
6.3. El concepto de cola
6.4. Implementación de cola como una estructura ligada
6.5. Listas circulares
6.6. Listas doblemente ligadas
7. Árboles
7.1. El concepto de árbol
7.2. Implementación de árboles
7.3. Búsqueda binaria recursiva en árboles
7.4. Inserción y borrado en árboles
7.5. Árboles ordenados (heaps)
8. Grafos
8.1. Representaciones matriciales,
8.2. Recorridos
8.3. Algoritmos de búsqueda de rutas
9. Tablas Hash
Material de apoyo
El siguiente material se presenta únicamente como material de apoyo. Durante el curso no se cubrirá todo el material, únicamente se hará un repaso de los aspectos más relevantes.Por temas
- Introducción
- Simple Data Types: Built-In and User-Defined
- Object-Oriented Software Development, Part I
- Object-Oriented Software Development, Part II
- Pointers, Dynamic Data, and Reference Types, Part I
- Pointers, Dynamic Data, and Reference Types, Part II
- Abstract Data Structures
- ADT Unsorted List
- ADT Sorted List
- ADTs for Stacks and Queues
- Binary Search Trees, Part I
- Binary Search Trees, Part II
- Priority Queues, Heaps, and Graphs
Material Corto 2015
- Programación y Estructuras de Datos
- Pointers
- Object-Oriented Software Development
- Listas
- Pilas y Colas
- Árboles
- Grafos
- Astrachan, Owen L. Computer Science Tapestry. 2º. Edition. McGraw Hill, 2000.
- Bruce Eckel. Thinking in C++, Vol 1. 2000
- Budd, T. Classic Data Structures in C++, Addison-Wesley 1994.
- Cormen et al. /Introduction to Algorithms/, MIT Press & McGraw-Hill, 1990.
- * Dale, Nell and Weems, Chip. Programming and Problem Solving with C++. 4th. Edition. Jones and Bartlett Publishers. Boston, 2005. ISBN 10: 0-7637-0798-8
- * Dale, Nell. C++ Plus Data Structures. 4th. Edition. Jones and Bartlett Publishers. Boston 2007. ISBN-10: 0-7637-4158-2
- * Drozdek, Adam. Data Structures and Algorithms in C++. Thomson, 2005.
- Koffman, Elliot B. Paul A. T. Wolfgang. Objects, Abstraction, Data Structures and Design using C++. John Wiley, 2006.
- Shaffer, C. /A Practical Introduction to Data Structures and Algorithm Analysis./ Prentice Hall, 1998.