Saltar al contingut Menu
Mapa
  • Inicio
  • Información
  • Contacto
  • Mapa

Programación y Estructuras de Datos (PRED)

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

Profesores

Responsable:  (-)
Otros:(-)

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, se estudia el uso de la memoria dinámica y las estructuras de datos enlazadas, 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 expone 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 autónomo de los estudiantes.

Método de evaluación

A mitad de cuatrimestre se hará un examen parcial, de tipo práctico, sobre los temas de estructuras lineales y gestión de memoria (nota NP).

El examen final (nota NF) cubrirá toda la asignatura. Este examen tiene un carácter más conceptual, pero vuelve a evaluar los temas ya evaluados en el parcial.

La nota de laboratorio (nota NL) viene dada por dos ejercicios de programación con el mismo peso. Los ejercicios se resuelven en grupos de dos estudiantes. El primer ejercicio, sobre estructuras lineales, se propone hacia la tercera o cuarta semana de clase. El segundo ejercicio, sobre tablas hash, se propone unas tres semanas antes del fin de las clases. En ambos casos hay unas cuatro semanas para resolverlos.

La nota total de la asignatura se calcula con la fórmula:

NT = max(0,2*NP + 0,6*NF, 0,8*NF) + 0,2*NL

Bibliografía básica

  • Bertrand Meyer Object-oriented software construction, Prentice Hall, 1997.
  • John C. Mitchell. Concepts in programming languages, Cambridge University Press, 2003.
  • B. Pierce Types and programming languages, MIT Press, 2002.
  • Mark Allen Weiss Estructuras de datos en Java : compatible con Java 2, Addison Wesley, 2000.
  • Ricardo Peña Marí Diseño de programas : formalismo y abstracción, Prentice Hall, 2005.

Bibliografía complementaria

  • Narciso Martí Oliet, Yolanda Ortega Mallén, José Alberto Verdejo López. Estructuras de datos y métodos algorítmicos : ejercicios resueltos, Pearson Educación, 2001.

Enlaces web

(Información no introducida)

Capacidades previas

PREREQUISITOS: Prácticas de Programación


Compartir
Share

 
logo FIB © Facultad de Informática de Barcelona - Contacto - RSS
Esta web utiliza cookies propias para ofrecerle una mejor experiencia y servicio. Si continúa la navegación, entendemos que acepta nuestra política de cookies. Versión clássica Versión móvil