Tema I tipos abtractos de datos (tad’s) tipo de datos



Descargar 86,77 Kb.
Fecha de conversión24.09.2017
Tamaño86,77 Kb.

Tema I – TIPOS ABTRACTOS DE DATOS (TAD’s)







TIPO DE DATOS: Es un conjunto de estados o valores permitidos, junto con las operaciones que trabajan sobre tales estados, cuando pertenecen a ese tipo concreto.

Esto es así porque un mismo estado puede pertenecer a tipos diferentes; p.ej., el nº 4, puede ser un entero, un real, un complejo, un racional o un natural.

El usuario puede construir sus propios tipos de datos en un lenguaje determinado, mediante las construcciones sintácticas que se le den para ello.

Así, las estructuras de datos se crean usando constructores predefinidos, (de especial utilidad son los registros y matrices), junto con los tipos que suministra el lenguaje: REAL, INTEGER, CARDINAL, BOOLEAN, etc. Los tipos de datos definidos por el usuario también se pueden usar para crear otras estructuras de datos más complejas. Ej.:


TYPE

Persona = RECORD

Nombre : ARRAY [0..23] OF CHAR;

Apellidos : ARRAY [0..29] OF CHAR;

DNI : ARRAY [0..9] OF CHAR;

END;

VAR

Censo : ARRAY [1..1000] OF Persona;

La variable Censo es una estructura más compleja formada sobre otra (Persona), definida por el usuario.

Un TIPO ABSTRACTO DE DATOS permite la construcción de casi cualquier tipo de datos, atendiendo sólo a criterios de comportamiento, y sin relacionarlo para nada con la representación subyacente que nos permita su puesta en ejecución según las funcionalidades particulares que un lenguaje de programación dado nos pueda suministrar. Su objetivo es hacer referencia a una clase de objetos (conjunto de estados) definidos por una especificación independiente de la representación. La implementación del tipo se oculta al usuario del programa.

La diferencia entre Tipo de Datos y T.A.D. es que el TAD se centra sólo en el comportamiento, no en la implementación. Es algo así como una caja negra. Dice el qué y no el cómo, aunque por supuesto, el qué tiene que ser viable. Así, se pueden utilizar diferentes cómos, dando al programador la potestad para seleccionar el que más le convenga, pero sin alterar en ningún momento el comportamiento del TAD, ni, por supuesto, su interfaz con el exterior, que será siempre la misma, (ya que formalmente se trata del mismo tipo de datos). Así pues, la separación de la especificación de la implementación de un TAD permitiría la existencia de varias implementaciones equivalentes, dándole al programador la posibilidad de cambiar la implementación sin que esto tenga ningún efecto en el resto del sistema.

Juegan un papel muy importante en el desarrollo de software seguro, eficiente y flexible, ya que cuando usamos un TAD definido por otro programador, podemos concentrarnos en las propiedades deseadas de los datos, y en las funcionalidades que nos suministran. Por cuestiones de correctitud y fiabilidad, es muy importante la corrección formal de un TAD; también hay que prestar especial atención a la definición formal en el caso de precondiciones anómalas por cuestiones de Robustez.

Nosotros vamos a utilizar una notación formal para especificar el comportamiento de los TADes.

La primera ventaja que se consigue usando TADes en el diseño de programas es que conllevan el conseguir programas estructurados y modulares. Este tipo de modularidad asegura que las tareas lógicas y los datos se agrupan para formar un módulo independiente cuya especificación funcional es visible a otros programas que lo usan. Estas aplicaciones no necesitan información detallada de cómo están implementadas las tareas y los datos. Esto hace que podamos implementar estas operaciones y tipos de datos de diferentes formas, siempre que se ajusten a las especificaciones. Esta separación de especificaciones e implementación asegura que muchas decisiones de diseño, como eficiencia, consenso entre velocidad y ocupación de memoria, etc., puedan tomarse en una etapa posterior, cuando se ha probado que las propiedades lógicas de los tipos de datos y sus operaciones satisfacen la aplicación. Para todo ello es muy útil la compilación separada, que nos permite verificar la corrección de los interfaces definidos, antes de proceder a la implementación propiamente dicha de los TADes.

En definitiva, con el concepto de TAD conseguimos crear una especificación formal mediante la cual el implementador no tenga duda alguna sobre las características del producto software que se le está pidiendo que desarrolle. La siguiente figura ilustra a grandes rasgos este proceso.





FORMALISMOS PARA LA ESPECIFICACION DE T.A.D.ES.

Las propiedades de los tipos INTEGER o BOOLEAN son bien conocidas. Sin embargo, en el momento en que intervienen otros tipos de datos, como pilas, listas, árboles o grafos, cuyo comportamiento y propiedades no son tan bien conocidos, es necesario disponer de definiciones adecuadas para las operaciones sobre dichos tipos, y, en general, sobre cualquier otro que se vaya a utilizar en un programa, de manera que se permita:

- Usar dichas operaciones en los diseños, o sea, poder usarlos aunque se carezca de la implementación.

- Establecer precondiciones y postcondiciones sobre las estructuras de ese tipo, con objeto de fijar el comportamiento de los programas que hacen uso de ellos, y verificar los diseños que se deben ajustar a dichos comportamientos.

Para ello, es necesario emplear una herramienta matemática cuya exactitud no dé lugar a ambigüedades a la hora de entender el funcionamiento de una determinada operación.

La especificación formal más ampliamente extendida es la especificación algebraica, que constituye un caso particular de las especificaciones axiomáticas, y que usaremos de forma intensiva a lo largo del curso.

El concepto básico es la presentación, que no es más que un compendio de símbolos (al que se llama signatura; estos símbolos representan operaciones y combinaciones entre ellas), que se pueden combinar de una forma determinada , y un conjunto de ecuaciones que permiten especificar la relación de equivalencia entre los símbolos obtenidos en base a la signatura, lo que da lugar a un conjunto cociente formado por una serie de clases de equivalencia, que agrupan a los términos lexicográficamente distintos, pero semánticamente iguales.

Así, para definir un tipo T se tendrán una serie de operaciones, de la forma:

f: Te1 ×...× Ten Ts1 ×...× Tsm, con n $ 0, m > 0, que representa la signatura (convención de signos a emplear); ej.:

Suma: N × N N

OR : B × B B

donde N y B son los Dominios, que pueden ser diferentes del TAD que estemos definiendo; ej.:

Re, Im: C R

C representaría a los números Complejos, y R a los racionales.

Las ecuaciones definen el comportamiento de las operaciones, en base a variables pertenecientes a un cierto dominio. Ej.:

OR(a, b) == NO(AND(NO(a), NO(b)))

El papel de las ecuaciones es establecer identificaciones entre términos lexicográficamente distintos, pero que denotan el mismo valor semántico, de manera que los términos equivalentes se puedan reducir o reescribir a una única forma canónica, representante de una clase de equivalencia. Para ello, resulta indispensable utilizar variables. Una variable no es más que una palabra que identifica cualquier posible término perteneciente a un dominio concreto (el dominio de la variable). Cuando se va a aplicar una ecuación a un término concreto, la variable toma los valores necesarios para que la parte izquierda de la ecuación coincida con el término. A continuación, el término original se sustituye por el término de la parte derecha de la ecuación, reemplazando cada variable por el valor que tomó en la parte izquierda.

Por tanto, más que ecuaciones, podríamos considerarlas reducciones, pues su utilidad principal es llegar a formas canónicas de representación de los diferentes estados del TAD; tales reducciones se efectúan siempre de izquierda a derecha. No obstante, estas ecuaciones también nos servirán para hacer demostraciones por inducción; en tales casos no distinguiremos entre parte izquierda y parte derecha de la ecuación.

Veamos un ejemplo para entender esto. Sea la siguiente especificación formal para describir el comportamiento de los números Naturales:



tipo N (*Naturales*)

Operaciones

0: N


suc: N N

suma: N × N N



Ecuaciones a,b:N

suma(suc(a), b) == suc(suma(a, b)) <<1>>

suma(0,b) == b

Esta especificación por sí misma no es nada. Ahora bien, nos damos cuenta de que podemos establecer una biyección entre los términos canónicos de la misma, y los números naturales.

Así pues, las formas canónicas son: 0, suc(0), suc(suc(0)), suc(suc(suc(0))), etc., que podemos asociar a los números naturales 0, 1, 2, 3, etc. respectivamente. Nótese que la especificación de los números naturales pares sería exactamente igual: 0-0, suc(0)-2, suc(suc(0))-4, etc. O sea, por un lado tenemos que distinguir entre los garabatos que escribimos, y los conceptos que queremos representar. La potencia aparece cuando podemos establecer una relación entre ambos elementos, ya que los garabatos y las reglas formales por las que se rigen, nos permiten descubrir y demostrar propiedades de los conceptos.

De esta manera, suponemos que los términos (canónicos o no) son una forma de representar en el papel los conceptos de la vida real que se desean formalizar. Cada valor de la vida real tiene que tener una correspondiente representación mediante un término canónico y, posiblemente, varios términos no canónicos (incluso infinitos). En la siguiente tabla se ve como cada valor de la realidad (expresado en la cabecera de la columna), se corresponde con varios términos, uno de los cuales es el canónico (en negrita) porque se expresa mediante funciones generadoras: 0 y suc(0):



Las ecuaciones nos permiten introducir en una misma clase de equivalencia o columna, a todos aquellos términos que representar el mismo concepto. Las variables permiten expresar con una única ecuación infinitas posibilidades en los términos izquierdo y derecho, estableciendo unos patrones mínimos que deben coincidir para que la ecuación pueda aplicarse.



Pero no sólo los valores tienen una representación según nuestro formalismo, sino que las operaciones de la vida real también tienen una representación. En nuestro caso, estamos representando las siguientes:


Con esto conseguimos que todo concepto de la vida real, ya sea valor u operación, tenga una representación formal y, además, conseguimos que esta representación sea matemática y no informática, con lo que evitamos tener que referenciar al cómo implementarla, expresando tan sólo los conceptos que queremos manejar.
REQUISITOS DE LOS LENGUAJES PARA LA ESPECIFICACIÓN DE TAD.

La programación estructurada (eliminación de la sentencia go to), la encapsulación de datos (el uso de módulos para agrupar procedimientos relacionados), y la abstracción de datos (el uso de tipos de datos junto con los procedimientos de manipulación correspondientes bien definidos), juegan un papel de fundamental importancia en la producción de software correcto.


En Lenguajes orientados a objetos.

Un paso más en la abstracción de datos, nos lleva a los lenguajes de programación orientados a objetos, tales como Smalltalk, C++, Eiffel, Java, C#, etc.

En la metodología orientada a objetos, un objeto no es más que un conjunto de datos privados (cuyos valores dan lugar al estado del objeto), y unas operaciones para acceder y procesar los datos.

Algunos conceptos interesantes son:

- Mensaje: Se llama así a la llamada a la operación que permite procesar un objeto.

- Método: Es la implementación oculta de cada operación.

- Herencia. Una clase de objetos puede heredar características y operaciones de otra clase más general.

- Polimorfismo. Un objeto definido de tipo general puede, en realidad, estar referenciando a cualquiera de los que de él heredan.

- Vinculación dinámica. Cuando se envía un mensaje a un objeto polimórfico, se elige en tiempo de ejecución qué versión del método se va a ejecutar.

Para ser pragmáticos, un objeto no es más que un registro en el sentido normal de la palabra. La diferencia con los registros convencionales estriba en que, en el caso de los objetos, junto con la definición del tipo se declaran aquellas operaciones que se pueden hacer con dichos registros. De esta forma, el aspecto estructural y el operacional quedan perfectamente ensamblados. Si el diseño orientado a objetos está correctamente construido, entonces debe ser imposible acceder a las interioridades de un objeto (sus campos, también llamados datos miembro) directamente y sólo las operaciones declaradas junto al tipo tienen acceso a dichos campos.

De esta manera, con los paradigmas antiguos de programación, los programas eran secuencias de instrucciones que manejaban datos de manera indiscriminada, aunque agrupadas funcionalmente en procedimientos y funciones. Con la programación orientada a objetos, la ejecución de un programa se convierte en una secuencia de pasos de mensajes, esto es, llamadas de un objeto a otro.
COMPLEJIDAD DE LOS ALGORITMOS.

Normalmente hay muchos programas o algoritmos que pueden resolver una misma tarea o problema. Es necesario, por lo tanto, considerar los criterios que podemos usar para determinar cuál es la mejor de las posibilidades en cada situación. Estos criterios pueden incluir características de los programas tales como documentación, portabilidad, etc. Alguno de estos criterios puede ser analizado cuantitativamente, pero en general, la mayoría no pueden ser evaluados con precisión. Puede que el criterio más importante (después de la corrección, por supuesto) es el que es normalmente conocido como eficiencia. Informalmente, la eficiencia de un programa es una medida de los recursos de tiempo y espacio (memoria o almacenamiento secundario) que se requieren en la ejecución. Es deseable, por supuesto, minimizar estas cantidades tanto como sea posible. Antes de poder cuantificar esto es preciso desarrollar una notación rigurosa para poder analizar los programas.

El tiempo y el espacio requeridos por un programa medido en segundos de tiempo de computador y en número de bytes de memoria, son muy dependientes del ordenador usado. Por esto, debemos buscar medidas más simples y abstractas, que sean independientes del ordenador real.

Este modelo abstracto puede servir como base para comparar diferentes algoritmos. En la práctica nos interesa saber la forma en que se comporta el tiempo y el espacio empleado en función del tamaño de la entrada.

Objetivos a la hora de resolver un problema:

- Algoritmo fácil de entender, codificar y depurar.

- Uso eficiente de los recursos del computador y, en general, que se ejecute con la mayor rapidez posible.
Para programas que se ejecutan una o pocas veces el primer objetivo es el más importante. Si se va a ejecutar muchas veces, el coste de ejecución del programa puede superar con mucho al de escritura. Es más ventajoso, desde el punto de vista económico, realizar un algoritmo complejo siempre que el tiempo de ejecución del programa resultante sea significativamente menor que el de un programa más evidente. Y aún en situaciones como esa, quizás sea conveniente aplicar primero un algoritmo simple, con objeto de determinar el beneficio real que se obtendría escribiendo un programa más complicado. En la construcción de un sistema complejo, a menudo es deseable aplicar un prototipo sencillo en el cual se puedan efectuar simulaciones y mediciones antes de dedicarse al diseño definitivo.
Medición del tiempo de ejecución de un programa.

El tiempo de ejecución de un programa depende de factores como:

- Los datos de entrada del programa,

- La calidad del código generado por el compilador utilizado para crear el programa objeto,

- La naturaleza y rapidez de las instrucciones de máquina empleadas en la ejecución del programa, y

- La complejidad de tiempo del algoritmo base del programa.

El hecho de que el tiempo de ejecución dependa de la entrada indica que el tiempo de ejecución de un programa debe definirse como una función de la entrada. Por ejemplo, en algoritmos de ordenación, cuanto mayor sea el número de elementos a ordenar, mayor será el tiempo necesario.

Para muchos programas, el tiempo de ejecución es en realidad una función de la entrada específica, y no sólo del tamaño de ésta. En este caso se define T(n) como el tiempo de ejecución del peor caso, es decir, el máximo valor del tiempo de ejecución para entradas de tamaño n.





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

    Página principal