fundamentacion de la asignatura objetivo de …€¦ · en estructura de datos (arreglos, listas,...

INSTITUTO POLITECNICO NACIONAL

SECRETARIA ACADEMICA DIRECCION DE ESTUDIOS PROFESIONALES EN INGENIERIA Y CIENCIAS FISICO MATEMATICAS

ESCUELA: UNIDAD PROFESIONAL INTERDISCIPLINARIA DE INGENIERÍA Y CIENCIAS SOCIALES Y ADMINISTRATIVAS CARRERA: LICENCIATURA EN CIENCIAS DE LA INFORMÁTICA LÍNEA CURRICULAR: COORDINACION: ACADEMIAS DE COMPUTACIÓN DEPARTAMENTO: CIENCIAS DE LA INGENIERÍA

ASIGNATURA: ESTRUCTURA Y REPRESENTACIÓN DE DATOS CLAVE: CCER SEMESTRE: SEGUNDO CREDITOS: 8 VIGENTE :ENERO 1999 TIPO DE ASIGNATURA: TEÓRICA 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

H/SEMANA: 4

H/TEORIA/SEMESTRE: 72

H/PRACTICA/SEMESTRE:

PROGRAMA ELABORADO O ACTUALIZADO POR: ACADEMIAS DE COMPUTACIÓN REVISADO POR: JEFATURA DE CARRERA DE CIENCIAS DE LA INFORMÁTICA APROBADO POR: EL CONSEJO TÉCNICO CONSULTIVO ESCOLAR ING. FRANCISCO BOJORQUEZ HERNÁNDEZ. PRESIDENTE FECHA DE APROBACIÓN: NOVIEMBRE 10 DE 1998

AUTORIZADO POR: COMISIÓN DE PLANES Y PROGRAMAS DE ESTUDIO DEL CONSEJO GENERAL CONSULTIVO DEL INSTITUTO POLITÉCNICO NACIONAL.



ASIGNATURA: ESTRUCTURA Y REPRESENTACIÓN DE DATOS CLAVE: CCER . HOJA: 2 DE 15 .

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. Es por esto que se hace indispensable que en la formación de los Licenciados en Ciencias de la 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? ¿como son implementadas?. Los conocimientos derivados de este curso tienen una aplicación directa en una gran cantidad de materias de la currícula 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 el 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 PROGRAMACIÓN I Y FUNDAMENTOS DE LA COMPUTACIÓN. COLATERALES: LENGUAJES DE PROGRAMACIÓN II E INGENIERÍA DE SOFTWARE. CONSECUENTES: LENGUAJES DE PROGRAMACIÓN III, SISTEMAS DE INFORMACIÓN, ALGORITMOS COMPUTACIONALES.



ASIGNATURA:ESTRUCTURA Y REPRESENTACIÓN DE DATOS CLAVE: CCER . HOJA: 3 DE 15 . No. UNIDAD NOMBRE: I INTRODUCCIÓN

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.0

2.0

10B,12B



ASIGNATURA: ESTRUCTURA Y REPRESENTACIÓN DE DATOS CLAVE: CCER . HOJA: 4 DE 15 . No. UNIDAD: NOMBRE: II 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


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.0

4.0

4.0

4.0

12B

1B, 10B




HORAS

No. TEMA

T E M A S


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)

• 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.


4.0

6.0

10B,12B




HORAS

No. TEMA

T E M A S


T

P

EC

CLAVE BIBLIOGRAFIA

2.4

2.5

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 • 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 almacenamiento y recuperación de información en la memoria • Almacenamiento y recuperación

secuencial: Variables estáticas; definición en Pascal • Almacenamiento y recuperación

encadenada o ligada: variables dinámicas, 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 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.0

4.0

10B




HORAS

No. TEMA

T E M A S


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)


4.0

4.0

4.0

10B, 12B

10B



ASIGNATURA: ESTRUCTURA Y REPRESENTACIÓN DE DATOS CLAVE: CCER . HOJA: 8 DE 15 . No. UNIDAD: NOMBRE:. III ESTRUCTURA DE DATOS LINEALES

OBJETIVOS PARTICULARES DE LA UNIDAD Al termino 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


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.0 4.0 10B,12B




HORAS

No. TEMA

T E M A S


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ísticas de

las Pilas • Algoritmos para las operaciones

básicas; implementació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.0

5.0

4.0

4.0

1B,2B,10B

10B,12B




HORAS

No. TEMA

T E M A S


T

P

EC

CLAVE BIBLIOGRAFIA

3.4

3.5

Colas • Definición y 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.0

4.0

4.0

4.0

1B,10B,12B



ASIGNATURA: ESTRUCTURA Y REPRESENTACION DE DATOS CLAVE: CCER . HOJA: 11 DE 15 . No. UNIDAD: NOMBRE: IV 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


T

P

EC

CLAVE

BIBLIOGRAFIA 4.1

Árboles • Definición y conceptos básicos • Arboles binarios; representació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.0 12.0 10B




HORAS

No. TEMA

T E M A S


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.0

8.0

10B, 12B




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.




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.




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.

fundamentacion de la asignatura objetivo de …€¦ · en estructura de datos (arreglos, listas,...

Documents