PDF de programación - Algoritmos y Estructuras de Datos: Introducción a los TAD y los Algoritmos

Algoritmos y Estructuras de Datos:

Introducción a los TAD y los Algoritmos

Guillermo Román Díez

groman@fi.upm.es

Universidad Politécnica de Madrid

Curso 2015-2016

Guillermo Román, UPM

AED: Introducción

1/11

Definiciones

Tipo Abstracto de Datos (TAD)

“a systematic way of organizing and accessing data”

Algoritmo

“a step-by-step procedure for performing some task in a finite amount of
time”

Los lenguajes de programación ofrecen herramientas y
mecanismos para implementar TADs (clases, interfaces,
objetos, herencia, genéricos. . . )

Ejemplo

Veamos un ejemplo de TAD: ComplejoCart

Guillermo Román, UPM

AED: Introducción

2/11

Observaciones ComplejoCart

Los métodos suma y resta no modifican el estado del objeto
sobre el que se invocan → Objetos Inmutables

Cada llamada devuelven un objeto nuevo con la suma de los
atributos

La clase ComplejoCart proporciona getters para acceder a los
valores de los atributos
La representación de los números complejos está restringida a
una la representación cartesiana.

¿y si queremos usar una representación polar (módulo y
ángulo)?
¿y si queremos combinar ambas representaciones?

Guillermo Román, UPM

AED: Introducción

3/11

TADs en Java

En Java un TAD consiste en una jerarquía de clases e
interfaces
Los interfaces especifican el qué
Las clases implementan el cómo
El interfaz no incluye constructores, ni métodos heredados de
Object como toString, equals, etc.
La descripción de lo que hace cada método del interfaz debe
documentarse

Ya sea en lenguaje natural usando Javadoc
Ya sea en lenguaje formal usando lógica formal

Ejercicio

Proponer un TAD para poder tener ComplejoCart y ComplejoPolar

Guillermo Román, UPM

AED: Introducción

4/11

Solución: Interfaz Complejo

public i n t e r f a c e C omp lej o {

D e v u e l v e la parte real */

/* *
public double getRe () ;
/* * D e v u e l v e la parte i m a g i n a r i a */
public double getIm () ;
/* * D e v u e l v e el modulo */
public double getMod () ;
/* * D e v u e l v e el angulo */
public double getAng () ;
/* * D e v u e l v e un C o m p l e j o h a c i e n d o sumando ’c ’ */
public C omp lej o suma ( C omp lej o c ) ;
/* * D e v u e l v e un C o m p l e j o h a c i e n d o r e s t a n d o ’c ’ */
public C omp lej o resta ( C omp lej o c ) ;
/* * D e v u e l v e un C o m p l e j o h a c i e n d o c o n j u g a n d o ’c ’ */
public C omp lej o conj ( C omp lej o c ) ;

}

Guillermo Román, UPM

AED: Introducción

5/11

Solución: Interfaz Complejo

Como hay dos formas de representar complejos ofrecemos
getters para cada posible representación
Los métodos suma, resta y conj reciben como parámetro
cualquier clase que implemente el interfaz Complejo

public C omp lej o suma ( C omp lej o c ) {

if ( c == null ) { throw new I l l e g a l A r g u m e n t E x c e p t i o n () ;}
return new C o m p l e j o C a r t ( this . re + c . getRe () ,

this . im + c . getIm () ) ;

}

El uso de getters permite comparar con cualquier objeto que
implemente el interfaz Complejo

Ejemplo

Ver las clases ComplejoCart2, ComplejoPolar y el interfaz Complejo

Guillermo Román, UPM

AED: Introducción

6/11

Algunas Propiedades del Software

Acoplamiento: Mide las dependencias (llamadas a métodos,
acceso a datos, . . . ) entre las partes que constituyen un
sistema de software
Cohesión: Mide la relación entre las responsabilidades de las
clases de un mismo módulo
Modularidad: División de un programa en unidades que
guardan una relación entre sí
Mantenibilidad: Capacidad del software para ser corregido o
incluir nuevas funcionalidades

Guillermo Román, UPM

AED: Introducción

7/11

Abstracción

Abstracción
“Separar por medio de una operación intelectual las cualidades de un
objeto para considerarlas aisladamente o para considerar el mismo objeto
en su pura esencia o noción”

Abstracción Funcional: Atender a la función ignorando la
estructura/representación interna
La funcionalidad se define mediante un interfaz y una
especificación (formal o informal) del comportamiento
La representación interna se describe en una
implementación

Guillermo Román, UPM

AED: Introducción

8/11

Propiedades de la Abstracción Funcional

Encapsulación (ocultación de información): sólo es necesario
conocer la función, la estructura puede quedar oculta

El cliente de un TAD sólo necesita conocer los interfaces
Independencia de la representación: la misma función
puede ser realizada por diferentes representaciones

El interfaz puede ser implementado por distintas clases

Modularidad: un módulo o cápsula realiza una funcionalidad

Debe tener alta cohesión (ser autocontenido) y bajo
acoplamiento (no depender de cambios en otros módulos)

Se hace en dos partes:

Abstracción de Datos: Tipos de datos, clases, paquetes. . .
Abstracción de Control: Métodos, funciones,
comunicaciones, . . .

Guillermo Román, UPM

AED: Introducción

9/11

Ventajas de la abstracción de datos

Pregunta

Enumerar algunas ventajas de la abstracción de datos

Guillermo Román, UPM

AED: Introducción

10/11

Ventajas de la abstracción de datos

Pregunta

Enumerar algunas ventajas de la abstracción de datos

Idealmente la independencia de la implementación implica
bajo acoplamiento ya que el interfaz es un “contrato”

Esto no es siempre del todo cierto: es necesario conocer los
constructores y requiere un buen diseño del interfaz

Los TADs tienen:
Alta cohesión
Bajo acoplamiento
Fuerzan un cierto diseño modular con refinamiento progresivo

La labor de diseño es clave a la hora de decidir qué datos y
métodos conforman un TAD

Guillermo Román, UPM

AED: Introducción

10/11

Resumen

Un TAD consiste en uno o más interfaces y clases. Los
interfaces especifican (”qué”) y las clases implementan
(”cómo”)

El ”cliente” del TAD sólo tiene que conocer los interfaces y
los constructores, para qué sirven, qué hacen los métodos y
con qué eficiencia

El ”cliente” NO tiene que conocer los atributos ni el código de
los métodos de las clases

En lo posible, los interfaces y clases deben estar diseñados
para poder combinar objetos de clases distintas pero que
implementan el mismo interfaz

Idealmente, el ”implementador” de las clases puede cambiar
los detalles sin que el código del ”cliente” se vea afectado

Guillermo Román, UPM

AED: Introducción

11/11