terminology - tda - tipos de datos abstractos libros

¿Qué es ADT?(Tipo de datos abstractos) (14)

Antes de definir tipos de datos abstractos , consideremos la vista diferente de los tipos de datos definidos por el sistema. Todos sabemos que, de forma predeterminada, todos los tipos de datos primitivos (int, float, etc.) admiten operaciones básicas como la suma y la resta. El sistema proporciona las implementaciones para los tipos de datos primitivos. Para los tipos de datos definidos por el usuario, también necesitamos definir las operaciones. La implementación de estas operaciones se puede hacer cuando queremos usarlas realmente. Eso significa que, en general, los tipos de datos definidos por el usuario se definen junto con sus operaciones.
Para simplificar el proceso de resolución de problemas, combinamos las estructuras de datos con sus operaciones y llamamos a esto "Tipo de datos abstractos" . (ADT''s).
Los ADT de uso común incluyen: Lista enlazada, Pilas, Colas, Árbol binario, Diccionarios, Conjuntos disjuntos (Unión y búsqueda), Tablas hash y muchos otros.
Los ADT consisten en dos tipos:
1. Declaración de datos.
2. Declaración de funcionamiento.

Actualmente estoy estudiando sobre tipos de datos abstractos (ADT), pero no entiendo el concepto. ¿Puede alguien explicarme por favor qué es esto realmente? Además, ¿qué es la colección, el bolso y la lista ADT? ¿en lenguaje sencillo?

Notación del tipo de datos abstracto (ADT)

Un tipo de datos abstracto podría definirse como un modelo matemático con una colección de operaciones definidas en él. Un ejemplo simple es el conjunto de enteros junto con las operaciones de unión, intersección definida en el conjunto.
Los ADT son generalizaciones del tipo de datos primitivos (entero, carácter, etc.) y encapsulan un tipo de datos en el sentido de que la definición del tipo y todas las operaciones en ese tipo se localizan en una sección del programa. Se tratan como un tipo de datos primitivo fuera de la sección en la que se definen el ADT y sus operaciones.
Una implementación de un ADT es la traducción a las declaraciones de un lenguaje de programación de la declaración que define que una variable es de ese ADT , más un procedimiento en ese lenguaje para cada operación de ese ADT . La implementación del ADT elige una estructura de datos para representar el ADT .
Una herramienta útil para especificar las propiedades lógicas del tipo de datos es el tipo de datos abstracto. Fundamentalmente, un tipo de datos es una colección de valores y un conjunto de operaciones en esos valores. Esa colección y esas operaciones forman un constructo matemático que puede implementarse utilizando una estructura de datos de hardware y software particular. El término "tipo de datos abstractos" se refiere al concepto matemático básico que define el tipo de datos.
Al definir un tipo de datos abstracto como concepto matemático, no nos preocupa la eficiencia de espacio o tiempo. Esos son problemas de implementación. De hecho, la definición de ADT no tiene que ver con los detalles de implementación en absoluto. Es posible que ni siquiera sea posible implementar un ADT en particular en una pieza de hardware en particular o utilizando un sistema de software en particular. Por ejemplo, ya hemos visto que un entero ADT no es universalmente implementable.
Para ilustrar el concepto de un ADT y mi método de especificación, considere el ADT RATIONAL que corresponde al concepto matemático de un número racional. Un número racional es un número que se puede expresar como el cociente de dos enteros. Las operaciones en números racionales que definimos son la creación de un número racional a partir de dos enteros, la suma, la multiplicación y la prueba de igualdad. La siguiente es una especificación inicial de este ADT .

/* Value defination */ abstract typedef <integer, integer> RATIONAL; condition RATIONAL [1]!=0; /*Operator defination*/ abstract RATIONAL makerational (a,b) int a,b; preconditon b!=0; postcondition makerational [0] =a; makerational [1] =b; abstract RATIONAL add [a,b] RATIONAL a,b; postcondition add[1] = = a[1] * b[1] add[0] = a[0]*b[1]+b[0]*a[1] abstract RATIONAL mult [a, b] RATIONAL a,b; postcondition mult[0] = = a[0]*b[a] mult[1] = = a[1]*b[1] abstract equal (a,b) RATIONAL a,b; postcondition equal = = |a[0] * b[1] = = b[0] * a[1];

Un ADT consta de dos partes:
1) definición del valor
2) definición de la operación

1) Definición del valor: -

La definición del valor define la colección de valores para el ADT y consta de dos partes:
1) Cláusula de definición
2) Cláusula de condición
Por ejemplo, la definición de valor para ADT RATIONAL indica que un valor RATIONAL se compone de dos enteros, el segundo de los cuales no es igual a 0.
La palabra clave abstract typedef introduce definiciones de valor y la condición de palabra clave se utiliza para especificar cualquier condición en el tipo de datos recién definido. En esta definición, la condición especifica que el denominador puede no ser 0. Se requiere la cláusula de definición, pero la condición puede no ser necesaria para cada ADT .

2) Definición del operador: -

Cada operador se define como una unión abstracta con tres partes.
1) Encabezado
2) Condiciones previas opcionales
3) Postcondiciones opcionales
Por ejemplo, la definición de operador de ADT RATIONAL incluye las operaciones de creación (creación), suma (suma) y multiplicación (mult), así como una prueba de igualdad (igual). Consideremos primero la especificación para la multiplicación, ya que es la más simple. Contiene un encabezado y condiciones posteriores, pero sin condiciones previas.

abstract RATIONAL mult [a,b] RATIONAL a,b; postcondition mult[0] = a[0]*b[0] mult[1] = a[1]*b[1]

El encabezado de esta definición es las dos primeras líneas, que son como un encabezado de función C. El resumen de palabras clave indica que no es una función C, sino una definición de operador ADT.
La condición posterior especifica, lo que hace la operación. En una condición posterior, el nombre de la función (en este caso, mult) se usa para denotar el resultado de una operación. Por lo tanto, mult [0] representa el numerador del resultado y mult 1 representa el denominador del resultado. Es decir, especifica qué condiciones se cumplen después de que se ejecuta la operación. En este ejemplo, la condición posterior especifica que el numerador del resultado de una multiplicación racional es igual al producto entero de los numeradores de las dos entradas y el denominador es igual al producto einteger de dos denominadores.

Lista

En informática, una lista o secuencia es un tipo de datos abstracto que representa un número contable de valores ordenados, donde el mismo valor puede aparecer más de una vez. Una instancia de una lista es una representación de computadora del concepto matemático de una secuencia finita; El (potencialmente) análogo infinito de una lista es un flujo. Las listas son un ejemplo básico de contenedores, ya que contienen otros valores. Si se produce el mismo valor varias veces, cada aparición se considera un elemento distinto
La lista de nombres también se usa para varias estructuras de datos concretas que se pueden usar para implementar listas abstractas, especialmente listas enlazadas.

Imagen de una lista

Bolso

Una bolsa es una colección de objetos, donde puede seguir agregando objetos a la bolsa, pero no puede quitarlos una vez que se haya agregado a la bolsa. Así que con una estructura de datos de bolsa, puede recopilar todos los objetos y luego iterarlos. Lo harás normalmente en bolsas cuando programes en Java.

Imagen de una bolsa

Colección

Una colección en el sentido de Java se refiere a cualquier clase que implementa la interfaz de Colección. Una colección en un sentido genérico es solo un grupo de objetos.

Imagen de colecciones.

ADT es un conjunto de objetos y operaciones, en ninguna de las definiciones de un ADT se menciona cómo se implementa el conjunto de operaciones. Los programadores que usan colecciones solo necesitan saber cómo instanciar y acceder a los datos de una manera predeterminada, sin preocuparse por los detalles de las implementaciones de las colecciones. En otras palabras, desde la perspectiva de un usuario, una colección es una abstracción, y por esta razón, en ciencias de la computación, algunas colecciones se denominan tipos de datos abstractos (ADT). El usuario solo se preocupa por conocer su interfaz o el conjunto de operaciones que realiza ... more

ADT es un conjunto de valores de datos y operaciones asociadas que son precisamente independientes de cualquier implementación específica. La fuerza de un ADT es que la implementación está oculta para el usuario. Solo se declara la interfaz. Esto significa que el ADT es de varias maneras.

El artículo de Wikipedia sobre el tipo de datos Abstact tiene mucho que decir.

En ciencias de la computación, un tipo de datos abstracto (ADT) es un modelo matemático para una cierta clase de estructuras de datos que tienen un comportamiento similar; o para ciertos tipos de datos de uno o más lenguajes de programación que tienen una semántica similar. Un tipo de datos abstracto se define indirectamente, solo por las operaciones que se pueden realizar en él y por restricciones matemáticas sobre los efectos (y posiblemente el costo) de esas operaciones.

En términos un poco más concretos, puede tomar la interfaz de la List de Java como ejemplo. La interfaz no define explícitamente ningún comportamiento en absoluto porque no hay una clase de List concreta. La interfaz solo define un conjunto de métodos que otras clases (por ejemplo, ArrayList y LinkedList ) deben implementar para que se considere una List .

Una colección es otro tipo de datos abstractos. En el caso de la interfaz de la Collection de Java, es incluso más abstracto que List , ya que

La interfaz de la List coloca estipulaciones adicionales, más allá de las especificadas en la interfaz de la Collection , en los contratos del iterator , métodos de add , remove , equals y hashCode .

Una bolsa también se conoce como un conjunto multiset .

En matemáticas, la noción de conjunto múltiple (o bolsa) es una generalización de la noción de conjunto en la que los miembros pueden aparecer más de una vez. Por ejemplo, hay un conjunto único que contiene los elementos a y b y ningún otro, pero hay muchos conjuntos múltiples con esta propiedad, como el conjunto múltiple que contiene dos copias de a y uno de b o el conjunto múltiple que contiene tres copias de tanto a como B.

En Java, una bolsa sería una colección que implementa una interfaz muy simple. Solo necesita poder agregar artículos a una bolsa, verificar su tamaño e iterar sobre los artículos que contiene. Vea Bag.java para una implementación de ejemplo (de la 4ª edición de Sedgewick & Wayne''s Algorithms ).

El tipo de datos abstractos (ADT) es un tipo de datos, donde solo se define el comportamiento pero no la implementación.

Al contrario de ADT está el Tipo de datos concreto (CDT), donde contiene una implementación de ADT.

Ejemplos:
Array, List, Map, Queue, Set, Stack, Table, Tree, and Vector son ADTs. Cada uno de estos ADT tiene muchas implementaciones, es decir, CDT. Container es un ADT de alto nivel por encima de todos los ADT.

Ejemplo de la vida real:
El libro es abstracto (la guía telefónica es una implementación)

El tipo de datos abstractos es la colección de valores y cualquier tipo de operación en estos valores hace que sea un tipo de datos abstractos, por ejemplo: String, ya que no es un tipo de datos primitivo, podemos incluirlo en los tipos de datos abstractos.

El tipo de datos abstractos es un módulo matemático que incluye datos con varias operaciones. Los detalles de la implementación están ocultos y por eso se llama resumen. La abstracción le permitió organizar la complejidad de la tarea centrándose en las propiedades lógicas de los datos y las acciones.

El tipo de datos simplemente abstracto no es más que un conjunto de operaciones y un conjunto de datos que se utiliza para almacenar otros datos de manera eficiente en la máquina. No hay necesidad de ninguna declaración de tipo perticular. Solo requiere una implementación de ADT.

En los lenguajes de programación, un tipo es algunos datos y las operaciones asociadas. Un ADT es un agregado de datos definido por el usuario y las operaciones sobre estos datos y se caracteriza por la encapsulación , los datos y las operaciones se representan, o se declaran en la lista, en una sola unidad sintáctica, y se oculta la información , solo las operaciones relevantes son visibles usuario de ADT, la interfaz ADT, de la misma manera que un tipo de datos normal en el lenguaje de programación. Es una abstracción porque la representación interna de los datos y la implementación de las operaciones no son importantes para el usuario de ADT.

Para resolver problemas combinamos la estructura de datos con sus operaciones. Un ADT consta de dos partes:

Declaración de datos.
Declaración de Funcionamiento.

Los ADT de uso común son listas enlazadas, pilas, colas, colas de prioridad, árboles, etc. Al definir los ADT, no debemos preocuparnos por los detals de implementación. Entran en la imagen solo cuando queremos usarlos.

Un tipo de datos verdaderamente abstracto describe las propiedades de sus instancias sin compromiso con su representación u operaciones particulares. Por ejemplo, el tipo abstracto (matemático) Integer es un conjunto de instancias discretas, ilimitadas y ordenadas linealmente. Un tipo concreto proporciona una representación específica para instancias e implementa un conjunto específico de operaciones.

Los tipos de datos abstractos son como los tipos de datos definidos por el usuario en los que podemos realizar funciones sin saber qué hay dentro del tipo de datos y cómo se realizan las operaciones en ellos. Como la información no se expone se abstrae. p.ej. Lista, Array, Pila, Cola. En Stack podemos realizar funciones como Push, Pop, pero no estamos seguros de cómo se está implementando detrás de las cortinas.

en una palabra simple: un tipo de datos abstracto es una recopilación de datos y operaciones que funcionan con esos datos. Las operaciones describen los datos al resto del programa y permiten que el resto del programa cambie los datos. La palabra "datos" en "tipo de datos abstractos" se usa a la ligera. Un ADT puede ser una ventana de gráficos con todas las operaciones que lo afectan, un archivo y operaciones de archivo, una tabla de tasas de seguro y las operaciones en él, o algo más.

de código completo 2 libro