Aumentar letras   Inicio   Información   Contactar   Mapa
Català   English

Programación y Estructuras de Datos (PRED)

Créditos Dept. Tipo Requisitos
7.5 (6.0 ECTS) LSI
  • Obligatoria para la EI
  • Obligatoria para la ETIG
 P1 - Prerequisito para la EI , ETIG
PRAP - Prerequisito para la EI , ETIG

Profesores

Responsable:  Fernando Orejas Valdés (orejas@lsi.upc.edu)
Otros:Ana Cristina Zoltan Torres (zoltan@lsi.upc.edu)
Ana Edelmira Pasarella Sanchez (edelmira@lsi.upc.edu)
Nicolas Eduardo Mylonakis Pascual (nicos@lsi.upc.edu)

Objectivos Generales

Por una parte, se pretende que el estudiante conozca mejor cómo es un lenguaje de programación, en particular un lenguaje orientado a objetos. Con este objetivo se estudiarán aspectos como la estructura de tipos, el control de datos, la gestión de memoria y los mecanismos de abstracción de un lenguaje de estas características. Por otra parte, se pretende que el estudiante conozca nuevas técnicas de programación. En concreto, el uso de la memoria dinámica y las estructuras de datos enlazados, que están en la base de muchas aplicaciones.

Objectivos Específicos

Conocimientos

  1. Tipos de datos en lenguajes de programación.
  2. Control de datos en lenguajes de programación.
  3. Abstracción de datos. Especificación e implementación.
  4. Implementaciones con punteros, nodos encadenados y memoria dinámica.
  5. Gestión de memoria dinámica. Garbage collection.
  6. Implementaciones de TADs fundamentales: listas, colas, pilas, árboles, tablas hash.
  7. Herencia.

Habilidades

  1. Conocer mejor cómo es un lenguaje de programación.
  2. Tomar contacto con algunas técnicas avanzadas de programación.
  3. Adquirir una metodología para la especificación, el uso, el diseño y la implementación de TADs.
  4. Conocer y saber utilizar técnicas de implementación basadas en punteros y memoria dinámica.
  5. Conocer TADs genéricos, saber utilizarlos y saber adaptarlos para dar soluciones a necesidades específicas.

Competencias

  1. Capacidad para resolver problemas aplicando los métodos de la ciencia y la ingeniería.
  2. Capacidad para crear y utilizar modelos de la realidad.
  3. Capacidad para diseñar sistemas, componentes o procesos que se ajusten a unas necesidades, utilizando los métodos, técnicas y herramientas más adecuadas en cada caso.
  4. Capacidad de abstracción. Capacidad para enfrentarse a problemas nuevos recorriendo conscientemente a estrategias que han sido útiles en problemas resueltos anteriormente.
  5. Saber aplicar el ciclo de resolución de problemas típico de la ciencia y la ingeniería: especificación, generación de ideas y alternativas, diseño de una estrategia de solución, ejecución de la estrategia, validación, interpretación y evaluación de los resultados. Capacidad para analizar el proceso una vez acabado.
  6. Capacidad de análisis y de síntesis.
  7. Capacidad para aprender autónomamente.

Contenidos

Horas estimadas de:

T P L Alt L Ext. Est O. Ext.
Teoria Problemas Laboratorio Otras actividades Laboratorio externo Estudio Otras horas fuera del horario fijado

1. Abstracción de datos: Especificación e implementación
T      P      L      Alt    L Ext. Est    O. Ext. Total 
7,0 3,0 0 0 0 10,0 0 20,0
Concepto de tipo abstracto de datos:



Descripción informal del concepto de tipo abstracto de datos. Motivación y ventajas de la programación usando TADs. La programación por contrato. Descomposición por funciones y descomposición por datos en el diseño descendente.



Especificación de TADs:



Metodología de construcción de especificaciones. Tipos de operaciones (constructoras, consultoras, generadoras, modificadoras...).



TADs y programación basada en objetos:



Los TADs como concepto básico de la programación basada en objetos. Objetos. Clases. Métodos. Funcionalidad de gestión: construcción, destrucción y asignación. Mecanismos de ocultación de información y funcionalidad.



Genericidad:



TADs parametrizados. Instanciación. Contenedores. Iteradores.



Implementación de TADs:



Estructuras de datos concretos. Concepto de implementación de un TAD. Invariante de representación. Función de abstracción.

2. Estructuras lineales
T      P      L      Alt    L Ext. Est    O. Ext. Total 
4,0 2,0 2,0 0 12,0 6,0 0 26,0
Pilas:



Especificación. Aplicaciones. Implementación con tabla estática. Implementación con tabla dinámica. Implementación con nodos encadenados.





Colas:



Especificación. Aplicaciones. Implementación con tabla circular. Implementación con nodos encadenados.





Listas:



Especificación. Aplicaciones. Implementación con nodos encadenados. Variaciones.





  • Laboratorio:
    Planteamiento y discusión del trabajo práctico a realizar. Este trabajo se realizará sin la presencia del profesor.

  • Actividades de laboratorio adicionales:
    Realización de una pequeña práctica o ejercicio sobre estructuras lineales. Básicamente, la implementación de una variante de lista.

3. Estructuras arborescentes
T      P      L      Alt    L Ext. Est    O. Ext. Total 
4,0 2,0 2,0 0 8,0 6,0 0 22,0
Árboles generales, binarios y m-arios:



Especificación de árboles generales. Especificación de árboles m-arios.

Especificación de árboles binarios. Ejemplos: árboles de expresión. Implementación enlazada de árboles binarios. Implementación enlazada de árboles m-arios.

Isomorfismo entre árboles generales y árboles binarios. Implementación de árboles generales utilizando punteros al primer hijo y al siguiente hermano.





Esquemas de recorrido de árboles:



Recorridos en preorden, postorden, inordren y por niveles.

Aplicación: Evaluación de expresiones, derivación formal de expresiones.





  • Laboratorio:
    Planteamiento y discusión del trabajo práctico a realizar. Este trabajo se realizará sin la presencia del profesor.
  • Actividades de laboratorio adicionales:
    Realización de una pequeña práctica o ejercicio sobre estructuras arborescentes. Básicamente, la implementación de una variante de árbol.

4. Lenguajes de programación
T      P      L      Alt    L Ext. Est    O. Ext. Total 
2,0 0 0 0 0 2,0 0 4,0
Criterios de diseño de un lenguaje de programación.



Implementación de un lenguaje de programación. Máquinas abstractas.

5. Tipo de datos
T      P      L      Alt    L Ext. Est    O. Ext. Total 
6,0 2,0 0 0 0 0 0 8,0
Concepto de tipo.



Tipos de datos y características de un lenguaje de programación.



Polimorfismo y sobrecarga.



Definición de un sistema de tipo mediante reglas de inferencia.



Comprobación de tipo.

6. Memoria dinámica
T      P      L      Alt    L Ext. Est    O. Ext. Total 
5,0 2,0 0 0 7,0 0 0 14,0
Punteros. new y delete.
Destructor, constructor por copia y operador de asignación.
Asignación dinámica de memoria.
Algoritmos de "garbage collection"

7. Control de Datos
T      P      L      Alt    L Ext. Est    O. Ext. Total 
3,0 2,0 0 0 0 5,0 0 10,0
Nombres y entidades.



Visibilidad y vida de una entidad.



Ámbitos estáticos y dinámicos. Acceso a entidades: cadena estática y dinámica.



Paso de parámetros.

8. Hashing
T      P      L      Alt    L Ext. Est    O. Ext. Total 
6,0 2,0 2,0 0 6,0 8,0 0 24,0
Especificación de tablas y diccionarios.



Implementación con tablas hash: hash abierto, cerrado y otras variaciones.



Funciones de hash.



  • Laboratorio:
    Planteamiento y discusión del trabajo práctico a realizar. Este trabajo se realizará sin la presencia del profesor.
  • Actividades de laboratorio adicionales:
    Realización de una pequeña práctica o ejercicio sobre tablas hash. Básicamente, la implementación de una variante de tabla.

9. Herencia
T      P      L      Alt    L Ext. Est    O. Ext. Total 
3,0 1,0 0 0 0 4,0 0 8,0
Herencia y subtipos.

Herencia como herramienta de diseño.



Herencia y modificabilidad de los programas.


Total por tipo T      P      L      Alt    L Ext. Est    O. Ext. Total 
40,0 16,0 6,0 0 33,0 41,0 0 136,0
Horas adicionales dedicadas a la evaluación 6,0
Total horas de trabajo para el estudiante 142,0

Metodología docente

Se pretende exponer el temario de forma muy práctica, a través de la presentación de muchos ejemplos.

Las clases se dividen en tres tipos: sesiones de teoría, sesiones de problemas y sesiones de laboratorio. En particular, a lo largo del curso se harán 4 horas semanales de teoría y problemas. Con respecto al laboratorio, sólo se harán 2 o 3 sesiones a lo largo del curso. El resto del tiempo de laboratorio se dedica al trabajo individual de los estudiantes.

Método de evaluación

Se realizarán dos exámenes: uno de los aspectos más teóricos de la asignatura, con cuestiones cortas (nota NT) y otro de problemas de diseño de estructuras de datos (nota NP).

La nota de laboratorio (nota NL) viene dada por dos ejercicios de programación individuales que cuentan igual. El primer ejercicio, sobre estructuras lineales, se presentará hacia la sexta semana de clases. El segundo ejercicio, sobre tablas de hash, se presentará la última semana de clases.



La nota final (nota N) es N = 0.4*NT + 0.4*NP + 0.2*NL

Bibliografía básica

  • B. Meyer Object oriented software construction (2nd edition), Prentice Hall, 2000.
  • J. Mitchell Concepts in programming languages, Cambridge University Press, 2001.
  • B. Pierce Types and programming languages, MIT Press, 2002.
  • M. Weiss Estructuras de datos en Java, Prentice Hall, 2000.
  • R. Peña Diseño de programas, formalismo y abstracción, Prentice Hall, 2004.

Bibliografía complementaria

  • N. Martí, Y. Ortega, J.A. Verdejo Estructuras de datos y métodos algorítmicos - Ejercicios resueltos, Prentice Práctica, 2003.

Enlaces web

(Información no introducida)

Capacidades previas

PREREQUISITOS: Prácticas de Programación



 
logo FIB © Facultad de Informática de Barcelona - webmaster@fib.upc.edu - RSS RSS