Programa de asignatura curso académico 2001/02



Descargar 75,42 Kb.
Fecha de conversión14.05.2017
Tamaño75,42 Kb.


PROGRAMA DE ASIGNATURA

CURSO ACADÉMICO 2001/02


Fecha de Edición: 7/11/2001



Área de Titulación: Ingeniería Técnica en Informática de Sistemas

Asignatura: ESTRUCTURAS DE DATOS Y DE LA INFORMACIÓN

Curso: Segundo

Duración (Anual/Cuatrimestral): Anual

Carácter: Troncal

Créditos: 12






INDICE



1. Objetivos del programa
El objetivo general de la enseñanza de la programación es capacitar a los alumnos para construir metódicamente programas legibles, bien documentados, correctos, eficientes y fáciles de mantener y reutilizar. En el curso de "Introducción a la programación", los alumnos deben haber adquirido ya la capacidad de diseñar pequeños programas en un lenguaje imperativo estructurado, así como razonar en cierta medida acerca de la corrección y eficiencia de los mismos. el presente curso hace énfasis en el estudio de la eficiencia y en el diseño e implementación de tipos abstractos de datos (TADs). la eficiencia se analiza introduciendo las medidas asintóticas de complejidad de los algoritmos y el cálculo de la complejidad asociada a los programas iterativos y recursivos. se estudian la especificación informal e implementación de distintos TADs, analizando la eficiencia de las diferentes alternativas.
El objetivo perseguido consiste en que los alumnos adquieran la capacidad de especificar TADs; implementarlos en un lenguaje imperativo, eligiendo para ello estructuras de datos adecuadas; razonar sobre la corrección y eficiencia de tales implementaciones; y desarrollar pequeños programas que utilicen modularmente tipos abstractos de datos, sin acceso a la representación usada internamente por la implementación de éstos.
2. Temario
Tema 1 Introducción

La librería estándar de plantillas (STL). Fundamentos del lenguaje C++. Problemas.


Tema 2 Clases y programación orientada a objetos.

Clases y objetos. Encapsulación. Sobrecarga de funciones. Sobrecarga de operadores. Ejemplo práctico. Problemas.


Tema 3 Análisis de algoritmos.

Complejidad de los algoritmos. Medidas asintóticas de complejidad. Órdenes de complejidad. Métodos de análisis de la complejidad temporal de los algoritmos iterativos. Problemas.


Tema 4 Diseño de algoritmos recursivos.

Introducción a la recursión. Diseño de algoritmos recursivos. Análisis de algoritmos recursivos. Transformación de la recursión final a forma iterativa. Técnicas de generalización. Problemas.


Tema 5 Las clases contenedoras de la librería estándar.

Las clases contenedoras. Elección de un contenedor. Iteradores. Problemas.



Tema 6 Cadena de caracteres (string).


El tipo abstracto de datos. Resolución de problemas con cadenas. Operaciones de cadenas. La implementación del tipo de datos. Problemas.
Tema 7 Vectores.

El tipo abstracto de datos. Plantillas. Resolución de problemas con vectores. Operaciones vectores. La implementación del tipo de datos. Problemas.



Tema 8 Listas dinámicas.

El tipo abstracto de datos. Operaciones de listas. Ejemplos. La implementación del tipo de datos. Variaciones mediante herencia. Problemas.



Tema 9 Pilas y colas.

El tipo abstracto de datos. Pilas. Colas. Colas con final explícito. Problemas.


Tema 10 Conjuntos y multiconjuntos.

El tipo abstracto de datos. Operaciones de conjuntos. La implementación del tipo de datos. Problemas.


Tema 11 Árboles.

Propiedades de un árbol. Árboles binarios. Iteradores. Representación binaria de árboles n-arios. Problemas.


Tema 12 Búsqueda.

Dividir y vencer. Vectores ordenados. Árboles AVL. Aplicaciones. Problemas.


Tema 13 Colas de prioridad.

El tipo abstracto de datos. Montículos. Aplicación: Simulación de eventos discretos. Problemas.


Tema 14 Mapas y multimapas.

El tipo abstracto de datos. Operaciones de mapas. La implementación del tipo de datos. Problemas.


Tema 15 Tablas de dispersión.

El tipo abstracto de datos. Operaciones de tablas de dispersión. Resolución de colisiones. Algoritmos de ordenación. La implementación del tipo de datos. Problemas.


Tema 16 Grafos.

El tipo abstracto de datos. Representaciones. Autómatas finitos. Máquinas de Turing. Problemas.



3. Desarrollo de la asignatura
Al inicio de cada tema se entregará el contenido del mismo, que desarrolla y amplía los apartados ofrecidos en el programa general de la asignatura, así como la bibliografía específica.
Además, la asignatura comprende diferentes clases de resolución de problemas, tanto de forma individual por los alumnos como por parte del profesor.


4. Forma de evaluación
La evaluación de los alumnos se basará en dos aspectos:


  • La realización de los exámenes parciales o finales.

  • La participación de los alumnos en clase tanto en la resolución de problemas como en las preguntas que se formularán en las clases teóricas.

Aprobar el examen resulta imprescindible para aprobar la asignatura; la participación del alumno en clase sirve para modificar positivamente la nota global obtenida.



5. Bibliografía

Básica



G. L. Heileman. "Estructuras de datos, algoritmos y programación orientada a objetos". McGraw-Hill, 1996.

Carrano, Helman y Veroff. "Data Abstraction and Problem Solving with C++, Second Edition". Addison-Wesley, 1998

Complementaria



M. Allen Weiss. "Estructuras de datos y algoritmos". Addison-Wesley Iberoamericana, 1995.

A.V.Aho, J.E.Hopcroft, J.D.Ullman. "Data Structures and Algorithms". Addison Wesley, 1983.

G. Brassard, P. Bratley. "Fundamentos de Algoritmia". Prentice Hall, 1997.

J. P. Cohoon, J. W. Davidson. "Programación y diseño en C++". MacGraw-Hill, 2000

X. Franch Gutiérrez. "Estructuras de datos. Especificación, diseño e implementación". Ediciones UPC, 1994.

E. Horowitz, S. Sahni, D. Mehta. "Fundamentals of Data Structures in C++". W H Freeman & Co., 1995.

6. Enlaces de interés en Internet

CES Felipe II, www.cesfelipesegundo.com

Universidad Complutense de Madrid, www.ucm.es

Biblioteca UCM, www.ucm.es/BUCM/

Facultad de Informática, UCM, www.fdi.ucm.es

Facultad de Matemáticas, UCM, www.mat.ucm.es


La información actualizada sobre esta asignatura se encuentra disponible en www.cesfelipesegundo.com

Página de




La base de datos está protegida por derechos de autor ©absta.info 2016
enviar mensaje

    Página principal