INSTITUTO POLITECNICO NACIONAL
SECRETARIA ACADEMICA DIRECCION DE ESTUDIOS PROFESIONALES EN INGENIERIA Y CIENCIAS FISICO MATEMATICAS
ESCUELA: UNIDAD PROFESIONAL INTERDISCIPLINARIA DE INGENIERIA Y CIENCIAS SOCIALES Y ADMINISTRATIVAS CARRERA: INGENIERIA EN INFORMATICA ESPECIALIDAD: COORDINACION: ACADEMIAS DE COMPUTACION DEPARTAMENTO: CIENCIAS DE LA INGENIERIA
ASIGNATURA: ESTRUCTURA Y REPRESENTACION DE DATOS CLAVE: FCER SEMESTRE: SEGUNDO CREDITOS: 8 VIGENTE: JULIO/1999. TIPO DE ASIGNATURA: TEORICA MODALIDAD: Escolarizada XXXXX Abierta .
FUNDAMENTACION DE LA ASIGNATURA Los programas para computadora comúnmente se escriben para resolver problemas reales. La información a ser procesada es almacenada en estructura de datos (arreglos, listas, pilas, colas, árboles, etc.) haciendo uso de algún lenguaje, siendo las estructuras de datos, estructuras cuyos componentes son elementos de datos y cuya organización está determinada tanto por la interrelación entre dichos elementos, así como por las funciones de acceso que se utilizan para almacenarlos y recuperarlos.
OBJETIVO DE LA ASIGNATURA
Al término del curso el alumno aplicará los métodos para representar información compleja en la memoria de una computadora; aplicará los diferentes tipos de estructuras de datos, las operaciones que se pueden realizar en ellas, algunas de sus propiedades matemáticas y las técnicas para su implementación, considerando diversos métodos de almacenamiento, en la solución de problemas de sistemas de información. TIEMPOS TOTALES ASIGNADOS: H/SEMESTRE: 72:00 H/SEMANA: 4:00 H/TEORIA/SEMESTRE: 72:00 H/PRACTICA/SEMESTRE:
PROGRAMA ELABORADO O ACTUALIZADO POR:ACADEMIAS DE COMPUTACION REVISADO: JEFATURA DE LA CARRERA DE INGENIERIA EN INFORMATICA APROBADO POR: EL C.T.C.E.
PRESIDENTE ING. FRANCISCO BOJORQUEZ HERNANDEZ
AUTORIZADO POR: COMISION DE PLANES Y PROGRAMAS DE ESTUDIO DEL CONSEJO GENERAL CONSULTIVO DEL INSTITUTO POLITECNICO NACIONAL.
INSTITUTO POLITECNICO NACIONAL
SECRETARIA ACADEMICA DIRECCION DE ESTUDIOS PROFESIONALES EN INGENIERIA Y CIENCIAS FISICO MATEMATICAS
ASIGNATURA: ESTRUCTURA Y REPRESENTACION DE DATOS CLAVE: FCER . HOJA: 2 DE 16 .
FUNDAMENTACION
Estas estructuras son creadas y manipuladas por programas que se ejecutan en computadoras y que son almacenados en el sistema de memoria de éstas. La correcta solución de una estructura de datos para la realización de una operación puede hacer que ésta sea simple y eficiente, o de lo contrario, resulte que la operación sea complicada e ineficiente. Las estructuras de datos son utilizadas ampliamente aplicadas a todas las áreas de las ciencias de la computación: desde la programación de aplicaciones hasta diseño de compiladores y la teoría computacional, desde los microprocesadores hasta los sistemas de computación en gran escala, desde el diseño de HARDWARE hasta los sistemas operativos, etc. Todo lo anterior, hace indispensable que en la formación de los Ingenieros en Informática se disponga de un curso que proporcione los conocimientos sobre las estructuras de datos, y que fundamentalmente responda a las interrogantes: ¿qué son las estructuras de datos? ¿cómo se utilizan? ¿cómo son implementadas?. Los conocimientos derivados de este curso tienen una aplicación directa en una gran cantidad de materias de la curricula de la Licenciatura en Ciencias de la Informática, en áreas como desarrollo de SOFTWARE, los Compiladores, los Sistemas Operativos, etc. La metodología general del PEA para alcanzar los objetivos conductuales en el alumno, consiste en la exposición detallada, por parte del profesor, de las estructuras y representación de datos que se utilizan por los sistemas operativos y que, por lo general, están relacionadas íntimamente con la arquitectura de las computadoras que se esté utilizando. Sin embargo, a través de exposición teórica, el profesor inducirá al alumno a utilizar dichas estructuras en la solución de problemas de manejo de información, haciendo uso de las herramientas de software que se tengan al alcance. El alumno deberá investigar a que estructura de datos se orientan algunas computadoras, y desarrollará programas que simulen el funcionamiento de diversas estructuras de datos. ANTECEDENTES: LENGUAJES DE PROGRAMACION I Y FUNDAMENTOS DE LA COMPUTACION. COLATERALES: LENGUAJES DE PROGRAMACION II E INGENIERIA DE SOFTWARE. CONSECUENTES: LENGUAJES DE PROGRAMACION III, SISTEMAS DE INFORMACION, ALGORITMOS COMPUTACIONALES.
INSTITUTO POLITECNICO NACIONAL
SECRETARIA ACADEMICA DIRECCION DE ESTUDIOS PROFESIONALES EN INGENIERIA Y CIENCIAS FISICO MATEMATICAS
ASIGNATURA:ESTRUCTURA Y REPRESENTACION DE DATOS CLAVE: FCER . HOJA: 3 DE 16 . No. UNIDAD I NOMBRE INTRODUCCION
OBJETIVOS PARTICULARES DE LA UNIDAD Al término de esta unidad, el alumno:
Interpretará los objetivos del curso, su contenido y la forma en que se desarrollará y evaluará, así como la bibliografía mínima necesaria.
HORAS
No. TEMA
T E M A S
INSTRUMENTACION DIDACTICA
T
P
EC
CLAVE
BIBLIOGRAFIA
1.1 1.2
1.3
1.4
Presentación del profesor. Descripción de objetivos del curso. Descripción del temario y la bibliografía. Descripción del desarrollo del curso y forma de evaluación.
- Exposición por parte del profesor Lecturas recomendadas de la bibliografía por parte del alumno.
- Se empleará los métodos deductivos e inductivo.
- Se emplearán apoyos didácticos preparando rotafolios y aprovechando los recursos audiovisuales del departamento.
- Participación de los alumnos en la solución de problemas típicos.
2:00
2:00 10B,12B
INSTITUTO POLITECNICO NACIONAL
SECRETARIA ACADEMICA DIRECCION DE ESTUDIOS PROFESIONALES EN INGENIERIA Y CIENCIAS FISICO MATEMATICAS
ASIGNATURA: ESTRUCTURA Y REPRESENTACION DE DATOS CLAVE: FCER . HOJA: 4 DE 16 . No. UNIDAD II NOMBRE REPRESENTACION DE DATOS
OBJETIVOS PARTICULARES DE LA UNIDAD Al término de esta unidad, el alumno:
- Distinguirá los medios de almacenamiento de una computadora - Describirá como está organizada la memoria de una computadora y cómo representan los datos en ésta. - Definirá conceptos generales de las estructuras de datos. - Aplicará las estrategias de almacenamiento de información en la memoria y las operaciones básicas que pueden realizarse
sobre las estructuras de datos.
HORAS
No. TEMA
T E M A S
INSTRUMENTACION DIDACTICA
T
P
EC
CLAVE
BIBLIOGRAFIA
2.1
2.2
Medios de almacenamiento en una computadora digital: • Memoria primaria o
principal. • Memoria secundaria. Organización de la memoria de una computadora digital. Conceptos básicos: bit, patrón binario, byte, palabra.
- Exposición por parte del profesor. - Investigación por el alumno. - Estudio de casos. - Utilizando los apoyos didácticos
siguientes: Pizarrón, acetatos, proyector.
- Presentación por parte del profesor de ejemplos ilustrativos.
- Tarea complementaria extra clase
4:00
4:00
4:00
4:00
12B
1B, 10B
INSTITUTO POLITECNICO NACIONAL
SECRETARIA ACADEMICA DIRECCION DE ESTUDIOS PROFESIONALES EN INGENIERIA Y CIENCIAS FISICO MATEMATICAS
ASIGNATURA: ESTRUCTURA Y REPRESENTACION DE DATOS CLAVE: FCER . HOJA: 5 DE 16 .
HORAS
No. TEMA
T E M A S
INSTRUMENTACION DIDACTICA
T
P
EC
CLAVE BIBLIOGRAFIA
2.3
• Conceptos básicos: bit, patrón binario, byte, palabra.
• Localidad de memoria y sus características: capacidad, dirección, operaciones básicas (lectura y escritura.
• La memoria como un conjunto de localidades: tamaño de memoria; memoria RAM; utilización de una memoria por el lenguaje Pascal, el HEAP de la memoria.
Organización de los datos en la memoria. Organización física: Tipos de datos y su representación en memoria: Datos numéricos, precisión sencilla y doble precisión: enteros y reales (punto flotante).
- Exposición por parte del profesor. Investigación por el alumno.
- Estudio de casos. - Utilizando los apoyos didácticos
siguientes: Pizarrón, acetatos, proyector.
- Presentación por parte del profesor de ejemplos ilustrativos.
- Tarea complementaria extra clase.
4:00
6:00
10B,12B
INSTITUTO POLITECNICO NACIONAL
SECRETARIA ACADEMICA DIRECCION DE ESTUDIOS PROFESIONALES EN INGENIERIA Y CIENCIAS FISICO MATEMATICAS
ASIGNATURA: ESTRUCTURA Y REPRESENTACION DE DATOS CLAVE: FCER . HOJA: 6 DE 16 .
HORAS
No. TEMA
T E M A S
INSTRUMENTACION DIDACTICA
T
P
EC
CLAVE BIBLIOGRAFIA
2.4
• Datos no numéricos: Cadenas de caracteres, datos lógicos (booleanos)
• Dirección de memoria. • Definición de tipos de
datos y características usando el lenguaje Pascal.
Organización lógica: • Elementos de datos de
una localidad. • Elementos de datos de
múltiples localidades. Generalidades de las estructuras de datos: • Conceptos de estructuras
de datos. • Clasificación de las
estructuras de datos. • El elemento básico de una
estructura.
- Exposición por parte del profesor. - Investigación por el alumno. - Estudio de casos. - Utilizando los apoyos didácticos
siguientes: Pizarrón, acetatos, proyector.
- Presentación por parte del profesor de ejemplos ilustrativos.
- Tarea complementaria extra clase.
5:00
4:00
10B
INSTITUTO POLITECNICO NACIONAL
SECRETARIA ACADEMICA DIRECCION DE ESTUDIOS PROFESIONALES EN INGENIERIA Y CIENCIAS FISICO MATEMATICAS
ASIGNATURA: ESTRUCTURA Y REPRESENTACION DE DATOS CLAVE: FCER . HOJA: 7 DE 16 .
HORAS
No. TEMA
T E M A S
INSTRUMENTACION DIDACTICA
T
P
EC
CLAVE BIBLIOGRAFIA
2.5
• El nodo visto como un conjunto de datos básicos (DATA ITEM).
• Analogía nodo-registro de archivo.
• Definición de nodos en Pascal.
Ejemplo, aplicaciones reales. Estrategias para el almace- namiento y recuperación de información en la memoria: • Almacenamiento y recu-
peración secuencial: Variables estáticas; definición en Pascal: • Almacenamiento y recu-
peración encadenada o ligada: variables dinámi- cas, definición en Pascal, utilización del HEAP.
- Exposición por parte del profesor. - Investigación por el alumno. - Estudio de casos. - Utilizando los apoyos didácticos
siguientes: Pizarrón, acetatos, proyector.
- Presentación por parte del profesor de ejemplos ilustrativos.
- Tarea complementaria extra clase.
4:00
6:00
1B,2B,10B
INSTITUTO POLITECNICO NACIONAL
SECRETARIA ACADEMICA DIRECCION DE ESTUDIOS PROFESIONALES EN INGENIERIA Y CIENCIAS FISICO MATEMATICAS
ASIGNATURA: ESTRUCTURA Y REPRESENTACION DE DATOS CLAVE: FCER . HOJA: 8 DE 16 .
HORAS
No. TEMA
T E M A S
INSTRUMENTACION DIDACTICA
T
P
EC
CLAVE BIBLIOGRAFIA
2.6
2.7
Operaciones básicas sobre las estructuras de datos: • Definición de la estructura. • Inserción de nodos a la
estructura. • Localización, consulta,
proceso y/o modificación del contenido de los nodos de la estructura.
• Borrado de la estructura: Algoritmos que utilicen las diferentes estructuras de almacenamiento en memoria (ejemplos).
- Exposición por parte del profesor. - Investigación por el alumno. - Estudio de casos. - Utilizando los apoyos didácticos
siguientes: Pizarrón, acetatos, proyector.
- Presentación por parte del profesor de ejemplos ilustrativos.
- Tarea complementaria extra clase.
4:00
4:00
4:00
10B, 12B
10B
INSTITUTO POLITECNICO NACIONAL
SECRETARIA ACADEMICA DIRECCION DE ESTUDIOS PROFESIONALES EN INGENIERIA Y CIENCIAS FISICO MATEMATICAS
ASIGNATURA: ESTRUCTURA Y REPRESENTACION DE DATOS CLAVE: FCER . HOJA: 9 DE 16 . No. UNIDAD III NOMBRE ESTRUCTURA DE DATOS LINEALES
OBJETIVOS PARTICULARES DE LA UNIDAD Al término de esta unidad el alumno:
- Identificará los diferentes tipos de estructuras de datos lineales. - Distinguirá las estrategias de almacenamiento y las funciones de acceso que se utilizan para almacenamiento y recuperación
de las estructuras. - Elaborará los programas para implementar los algoritmos. - Aplicará las estructuras en la solución de problemas.
HORAS
No. TEMA
T E M A S
INSTRUMENTACION DIDACTICA
T
P
EC
CLAVE
BIBLIOGRAFIA
3.1
Arreglos: • Axiomatización. • Vectores y matrices
secuenciales. • Matrices esparcidas. • Representación de
arreglos; definición en Pascal.
Ejemplos y aplicaciones.
- Exposición del profesor. - Investigación por los alumnos. - Estudios de casos. - Utilizando los apoyos didácticos
siguientes: Pizarrón, Proyector de acetatos.
- Para el desarrollo del curso, se utilizarán las técnicas de inducción y deducción.
6:00 4:00 10B,12B
INSTITUTO POLITECNICO NACIONAL
SECRETARIA ACADEMICA DIRECCION DE ESTUDIOS PROFESIONALES EN INGENIERIA Y CIENCIAS FISICO MATEMATICAS
ASIGNATURA: ESTRUCTURA Y REPRESENTACION DE DATOS CLAVE: FCER . HOJA: 10 DE 16 .
HORAS
No. TEMA
T E M A S
INSTRUMENTACION DIDACTICA
T
P
EC
CLAVE BIBLIOGRAFIA
3.2
3.3
Listas: • Definición de una lista;
principios de ordinalidad • Listas secuenciales. • Listas ligadas: con ligas
sencillas y doblemente ligadas.
• Listas circulares: con liga sencilla y doblemente ligadas.
• Algoritmos para las operaciones básicas. Implementación en Pascal ejemplos y aplicaciones.
Pilas: • Definición y característi-
cas de las Pilas. • Algoritmos para las
operaciones básicas. Im- plementación en Pascal.
• Ejemplos y aplicaciones.
- Exposición del profesor. - Investigación por los alumnos. - Estudios de casos. - Utilizando los apoyos didácticos
siguientes: pizarrón, proyector de acetatos.
- Exposición del profesor. - Investigación por los alumnos. - Estudios de casos. - Utilizando los apoyos didácticos
siguientes: pizarrón, proyector de acetatos.
6:00
5:00
4:00
4:00
1B,2B,10B
10B,12B
INSTITUTO POLITECNICO NACIONAL
SECRETARIA ACADEMICA DIRECCION DE ESTUDIOS PROFESIONALES EN INGENIERIA Y CIENCIAS FISICO MATEMATICAS
ASIGNATURA: ESTRUCTURA Y REPRESENTACION DE DATOS CLAVE: FCER . HOJA: 11 DE 16 .
HORAS
No. TEMA
T E M A S
INSTRUMENTACION DIDACTICA
T
P
EC
CLAVE BIBLIOGRAFIA
3.4
3.5
Colas: • Definicióny características
de las Colas. • Algoritmos para las
operaciones básicas; implementación en Pascal.
• Ejemplos y aplicaciones. Colas con doble terminación: • Definición y
características. • Algoritmos para las
operaciones básicos; implementación en Pascal.
• Ejemplos y aplicaciones. Ejemplos aplicando búsqueda binaria y métodos de ordenamiento.
- Exposición del profesor - Investigación por los alumnos - Estudios de casos - Utilizando los apoyos didácticos
siguientes: pizarrón, proyector de acetatos
- Exposición del profesor - Investigación por los alumnos - Estudios de casos - Utilizando los apoyos didácticos
siguientes: pizarrón, proyector de acetatos
5:00
4:00
4:00
4:00
1B,10B,12B
INSTITUTO POLITECNICO NACIONAL
SECRETARIA ACADEMICA DIRECCION DE ESTUDIOS PROFESIONALES EN INGENIERIA Y CIENCIAS FISICO MATEMATICAS
ASIGNATURA: ESTRUCTURA Y REPRESENTACION DE DATOS CLAVE: FCER . HOJA: 12 DE 16 . No. UNIDAD IV NOMBRE ESTRUCTURAS DE DATOS NO LINEALES
OBJETIVOS PARTICULARES DE LA UNIDAD Al término de esta unidad, el alumno: Identificará los distintos tipos de Estructuras de Datos no lineales Distinguirá las estrategias de almacenamiento y las funciones de acceso Elaborará los programas para implementar los algoritmos Aplicará las estructuras en la solución de problemas
HORAS
No. TEMA
T E M A S
INSTRUMENTACION DIDACTICA
T
P
EC
CLAVE
BIBLIOGRAFIA
4.1
Arboles: • Definición y conceptos
básicos. • Arboles binarios; repre-
sentación. Recorrido de arboles binarios: In-order, Pre-order, Pos-order. Algoritmos e implementación.
- Exposición por parte del profesor. - Investigación por los alumnos,
Estudios de casos. - Uso de metodología deductiva para
dar definiciones. - Uso de metodología inductiva para dar
ejemplos y deducir teoremas. - Por partes de los alumnos se
presentaran aplicaciones practicas. - Tareas complementarias extra clase.
7:00 12:00 10B
INSTITUTO POLITECNICO NACIONAL
SECRETARIA ACADEMICA DIRECCION DE ESTUDIOS PROFESIONALES EN INGENIERIA Y CIENCIAS FISICO MATEMATICAS
ASIGNATURA: ESTRUCTURA Y REPRESENTACION DE DATOS CLAVE: FCER . HOJA: 13 DE 16 .
HORAS
No. TEMA
T E M A S
INSTRUMENTACION DIDACTICA
T
P
EC
CLAVE BIBLIOGRAFIA
4.2
• Arboles con nodos ordenados.
• Búsqueda en arboles ordenados; algoritmo e implementación.
• Arboles de decisión • Arboles balanceados • Arboles A-VL. Grafos y Digrafos: • Definiciones y conceptos
básicos. • Representación de
gráficas. • Recorridos y
componentes. • Arboles expandidos. • Redes. Ejemplos y aplicaciones.
Apoyos didácticos: Pizarrón, acetatos, equipos de cómputo.
8:00
8:00
10B, 12B
INSTITUTO POLITECNICO NACIONAL
SECRETARIA ACADEMICA DIRECCION DE ESTUDIOS PROFESIONALES EN INGENIERIA Y CIENCIAS FISICO MATEMATICAS
ASIGNATURA: ESTRUCTURA Y REPRESENTACION DE DATOS CLAVE: FCER . HOJA: 14 DE 16 .
PERIODO
UNIDADES TEMATICAS
PROCEDIMIENTOS DE EVALUACION
I II III
I, II III
IV
Los tres exámenes departamentales se evaluarán de acuerdo al siguiente procedimiento: 70% Examen escrito. 30% Participación y trabajos extraclase. El promedio de las tres calificaciones obtenidas será la calificación final.
CLAVE
B
C
BIBLIOGRAFIA
1
2
X
X
Aho A.V., Hoperoft , Ullman J.d. Estructura de Datos y Algoritmos Sistemas Técnicos de Edición 1988. 1a. De, 438 p.p. Albizuri R., Miren B. Estructuras de Datos e Introducción a Bases de Datos. Ed. Limusa, Méx. 1989. 1a. De., 198 p.p.
INSTITUTO POLITECNICO NACIONAL
SECRETARIA ACADEMICA DIRECCION DE ESTUDIOS PROFESIONALES EN INGENIERIA Y CIENCIAS FISICO MATEMATICAS
ASIGNATURA: ESTRUCTURA Y REPRESENTACION DE DATOS CLAVE: FCER . HOJA: 15 DE 16 .
CLAVE
B
C
BIBLIOGRAFIA
3
4
5
6
7
8
X
X
X
X
X
X
Barnet, Michael P. Animated Algoritmhms A. Selfteaching Course in Data Structures Mc. Graw Hill New York USA 1986, 1a. Ed, 279 p.p. Evan A., Jorge I Estructuras de Datos Noriega México 1991, 1a. Ed. 219 p.p.. Horowitz E., Shani S. Fundamentals of Data Structures in Pascal. Computer Science Press, N.Y. U.S.A. 1990, 3a. Ed., 564 p.p. Kolman B., Busby R. Estructuras de Matemáticas Discretas para al Computación Prentice-Hall Hispanoamericana, S.A., Méx. 1986, 3a. Ed., 383 p.p. Dal, Nell Pascal y Estructuras de Datos Mc Graw Hill, México 1992, 2da. Ed. 785 p.p. Kruse Robert L. Estructuras de Datos y Diseño de Programas Prentice Hall Hispanoamericana, S.A., Méx. 1988, 4a. De. 453 p.p.
INSTITUTO POLITECNICO NACIONAL
SECRETARIA ACADEMICA DIRECCION DE ESTUDIOS PROFESIONALES EN INGENIERIA Y CIENCIAS FISICO MATEMATICAS
ASIGNATURA: ESTRUCTURA Y REPRESENTACION DE DATOS CLAVE: FCER . HOJA: 16 DE 16 .
CLAVE
B
C
BIBLIOGRAFIA
9
10
11
12
13
X
X
X
X
X
Schildt Herbert Advanced Turbo Pascal Borland - Osborne/Mc Graw Hioo, U.S.A. 1986, 5a. Ed., 740 p.p Tenembaum A.M., Augenstein M.J. Estructuras de Datos en Pascal Prentice Hall Hispanoamericana, S.A. Méx. 1983, 4a. Ed., 560 p.p. Tremblay J.P., Sorenson P.G. An Introduction To Data Structures With Applications Second Edition Mc Graw Hill, Inc. U.S.A. 1984, 2da. Ed., 365 p.p. Wirth Niklaus Algorithms + Data Structures = Programs. Prentice Hall, Inc. U.S.A. 1976, 2da. Ed., 350 p.p. Wirth Niklaus Algoritmos y Estructuras de Datos. Prentice Hall Hispanoamericana, S.A. Méx. 1987, 3a. Ed., 305 p.p.