TDA's

2.
T
D
A
'
S

## Introducción.

Muchas veces nos preguntamos que en el mundo de la programación existen diversos lenguajes, diversas acciones que se realizan día a día en la programación, pero no tomamos en cuenta la gran importancia que se tiene en el mundo de la programación aún más a fondo, por eso es que ahora les daremos a conocer el concepto de los TADs en términos más específicos el cual se refiere a los tipos de datos abstractos y es un tipo de dato definido por el programador.
Sabemos que hoy en día es de suma importancia tener muy claro algunos aspectos de la computación, pero hoy aprenderemos un poco más de eso, en cuanto a esto para empezar es útil comparar un tipo de dato abstracto con su noción más familiar en cuanto a su procedimiento, su utilización, sus aspectos y funciones en el cual se va a implementar el mismo. En este aspecto el programador es libre de definir sus propios operadores y aplicarlos, aquí van desglosadas una de las ventajas en cuestión a la definición de procedimientos localizando en distintas secciones de un programa las sentencias más relevantes a un cierto aspecto de un programa.
Podemos pensar que un tipo de dato abstracto es un modelo matemático con una colección de operaciones definidas en el modelo, debemos enfatizar que no existe un límite para el número de operaciones que se pueden aplicar a instancias en un modelo matemático, daremos a conocer ciertos niveles de abstracción para así llevar a cabo el manejo de un buen programa, el cómo se construye un programa con TADs, es decir, su proceso de diseño, así como también mencionar los tipos de datos requeridos para esta acción, con el fin de que nos quede bien claro que son los TADs. La primera aplicación de la abstracción a los datos esta en los propios tipos de datos básicos de los lenguajes de programación, la abstracción de datos se centra en la independencia de la representación, por el cual esto permite a los programadores modificar la representación del TDA sin que este afecte a su utilización.
Para definir un TDA comenzaremos por definir las operaciones que se pueden realizar con él, así como mencionar las partes del mismo, es decir, su especificación e implementación. Para representar a un modelo matemático que define a un TAD tenemos que utilizar en términos generales los tipos de datos y operadores, por el cual también se utilizan las estructuras de datos que va muy relacionado con los TADs. Aunque estas si dependen fundamentalmente del lenguajes de programación en el que vaya a ser desarrollado el modelo.
La popularidad de un programa utiliza la noción tipo abstracto de dato, siempre que sea posible si el lenguaje de programación soporta los tipos que desea el usuario y el conjunto de operaciones sobre cada tipo, se obtiene un nuevo tipo de dato denominado TDA, y eso es lo que daremos a conocer, para saber el uso y manejo de TADs en el mundo de la programación y así poder dominar el tema.

## Desarrollo.

Un tipo de dato abstracto (TDA). Es un modelo matemático compuesto por una colección de operaciones definidas sobre un conjunto de datos para el modelo. El concepto de tipo de dato abstracto (Abstract Data Type). Fue propuesto por primera vez hacia 1974 por John Guttag, el lenguaje turbo pascal fue determinante para la común aceptación de los TDA con la introducción de los Unís.
Se define como un conjunto de valores que pueden tomar los datos de ese tipo, junto a las operaciones que lo manipulan. Es decir, los TDA ponen a disposición del programador un conjunto de objetos junto con sus operaciones básicas.
Ahora bien mencionamos que un TDA está caracterizado por un conjunto de operaciones al cual se denomina usualmente como interfaz publica y representa el comportamiento del TDA.
- Los TDA que nos van a interesar de ahora en adelante, son aquellos que reflejen cierto comportamiento organizado, cierta variedad de datos estructuradamente.
- Un TDA tendrá una parte que será invisible al usuario la cual hay que proteger y que se puede decir que es irrelevante para el uso del usuario.
- Un TDA representa una abstracción.
  La abstracción. Es una de las herramientas que más nos ayuda a la hora de solucionar un problema.
  Definimos la abstracción como la simplificación de un objeto o proceso de la realidad, en el cual solo se consideran los aspectos más relevantes.
  En la abstracción hay que tomar en cuenta dos aspectos muy importantes entre ellos son:
- Destacar los aspectos más relevantes del objeto.
- Ignorar los aspectos irrelevantes del objeto.
  Hay que tomar en cuenta que la irrelevancia también depende del nivel de abstracción, ya que si pasa a niveles más concretos, algunos aspectos pueden volverse relevantes.
  Para definir un TDA el programador comienza por definir las operaciones que se pueden realizar con él, es decir, que operaciones son relevantes y útiles para operar con las variables pertenecientes al mismo. Esto se conoce como establecer la interfaz del tipo. La interfaz permite al programador utilizar el tipo (que se puede hacer frente a como está hecho).
  A continuación mostramos el siguiente ejemplo:
  Siguiendo con el ejemplo de las fechas, podemos indicar que las operaciones validas sobre una fecha son, entre otras.
  Creas (día, mes, año: natural): fecha
  Incrementar (fechaInicio: fecha; numDías: entero): fecha
  Distancia (fechaInicio, fin: fecha): entero
  ObtenerMes (f: fecha): natural
  La representación del tipo fecha en el TAD es independiente y de hecho, puede variar sin que afecte a los programas que utilicen el tipo, ya que la especificación se mantiene.
  En los TDA también tenemos la modularidad el cual es un aspecto muy importante ya que es el reflejo de la independencia de la especificación y la implementación.
  Se define modularidad a la demostración de que un TDA puede funcionar con diferentes implementaciones. Cuando un programa necesita un recurso, importa un módulo, dependiendo del lenguaje se importa toda la biblioteca o recursos sueltos. Los módulos se compilan por separado y se caracterizan por su interfaz y su implementación.
  Ahora bien hablaremos de la especificación y la implementación dos partes muy importantes de los TDA.
  La especificación. (Refleja que hace el tipo de dato). Es necesaria para que el programador sepa cómo debe implementar el TAD, suele coincidir con la interfaz, pero no es necesario que esto ocurra, ya que la interfaz es un concepto de programación por lo que puede añadir operaciones a la especificación.
  He aquí algunas de las características de la especificación de un TAD.
- Debe ser precisa
- Debe ser lo más general posible
- Debe ser legible
- Debe evitar ambigüedades
  Implementación: A su vez se compone de una interfaz pública, que permite al programador usar el TAD, y una implementación que puede variar siempre y cuando la interfaz se mantenga.
  Para la implementación del TAD, es fundamental disponer de mecanismos que permitan encapsular, el tipo de dato y sus operaciones, y ocultar la información al programador usuario. Estas dos características son fundamentales para poder llevar a cabo esta abstracción.
- Encapsulación: permite ocultar los detalles de implementación del comportamiento de una clase.
- Ocultación: restringir el acceso a la información del estado de un objeto.
  He aquí un ejemplo de implementación es la suma de racionales que definimos como sigue:
  El procedimiento Normalizar calcularía la forma simplificada del racional dado como parámetro. Una posible forma de definirla es tomar los restos de dividir numerador y denominador entre los números 2 a mínimo del numerador y denominador. Cuando los restos dan ambos 0 se dividen entre el número. Notar que SumaRacional podría definirse sin acceder a la representación haciendo uso de la operación CrearRacional. Esto tiene la ventaja de que se puede definir sin conocer la representación del TAD.

  ### Separación de la interfaz e implementación.

  Cuando se usa en un programa de computación, un TDA es representado por su interfaz, la cual sirve como cubierta a la correspondiente implementación ya que esta puede ir cambiando con el tiempo. La idea es que los usuarios de un TDA tengan que preocuparse solo por la interfaz, pero no por la implementación, ya que esta puede ir cambiando con el tiempo y, si no existiera encapsulación, afectar a los programas que usan el dato. Esto se basa en el concepto de ocultación de información, una protección para el programa de decisiones de diseño que son objeto de cambio.
  Separar la interfaz de la implementación no siempre significa que el usuario ignora totalmente la implementación de la rutina, pero lo suficiente para no depender de ningún aspecto de la implementación.

  ### Tenemos también la metodología de un TDA.

  Debido al proceso de abstracción, la programación de un TAD debe realizarse siguiendo tres pasos fundamentales.
  1.- Análisis de datos y operaciones
  2.- Especificación del tipo de dato abstracto
  3.- Implementación

  ### Etapas de los TDA.

  • Reconocimiento de los objetos candidatos a elementos del nuevo tipo de datos
  • Identificación de las operaciones del tipo de datos.
  • Especificación de las operaciones de forma precisa, sin ambigüedad.
  • Selección de una buena implementación.

  ### Categorías de las aplicaciones aplicables a un TDA.

  • Operaciones de creación. (constructoras o primitivas): obtienen nuevos objetos del tipo creación.
  • Operaciones de consulta: realizan funciones tal que empleando un argumento del tipo devuelven un valor de otro tipo.
  • Operaciones de modificación: permiten modificar un objeto del TDA.
  • Operaciones propias del tipo: se emplean en las operaciones antes descritas.

  ### Desarrollo de programas con TAD's

  • El primer paso a seguir es definir un TAD (colección de objetos junto con el conjunto de operaciones definidas para dichos objetos).
  • Una vez definido el TAD y sin necesidad de conocer como ha sido implementado, ya se puede utilizar de una forma abstracta, siendo suficiente la información suministrada por su definición.

  ### Construcción de un TDA.

  Un TDA puede construirse como una clase de un lenguaje orientado a objetos con sus variables en “private” y sus métodos para acceder y manipular esas variables, y una vez ya definida la clase solo hay que implementarla en el programa.
  La construcción de un TAD consta de dos fases bien diferenciadas entre ellas: la especificación (formal e informal) y la implementación.
  Las características de un TAD no deben depender de su realización concreta, sino solamente de cómo queremos que sea su comportamiento, lo cual llamamos especificación. Para la especificación de un tipo abstracto de datos en lenguaje natural (especificación informal) hemos de seguir el siguiente esquema:
  1. TIPO DE DATOS Nombre del tipo (Lista de operaciones)
  2. VALORES: Descripción de los posibles valores
  3. OPERACIONES: Descripción de cada operación
  Primero indicaremos el nombre del TAD y citaremos todas las operaciones definidas. En el apartado valores describiremos los posibles valores de los datos de este tipo, pero lo haremos desde un punto de vista abstracto, sin pensar en la posible realización concreta. Finalmente en el apartado operaciones haremos una descripción de cada una de las operaciones definidas sobre el TAD. En la especificación informal, habitualmente hacemos referencia a conceptos con los cuales el lector está familiarizado (como por ejemplo conceptos matemáticos). El problema surge cuando estos datos auxiliares no están definidos tan precisamente.

  ### Ventajas de un TDA

  1.- Permite una mejor conceptualización y modelización del mundo real: Mejora la presentación y comprensibilidad así como clarificar los objetos basados en estructuras
  2.- Mejora la robustez del sistema: Los tipos abstractos de datos permiten la comprobación de tipos para evitar errores.
  3.- Mejora el rendimiento (prestaciones): Para sistemas tipeados, el conocimiento de los objetos permite la optimización de tiempo de compilación.
  4.-Separa la implementación de la especificación: Permite la modificación y mejora de la implementación sin afectar la interfaz del tipo abstracto de dato.
  5.- Permite la extensibilidad del sistema: los componentes de software reutilizables son más fáciles de crear y mantener.
  6.- Recoge mejor la semántica del tipo: agrupan o localizan las operaciones TADs más comunes.
  • Listas: se utilizan habitualmente para guardar elementos del mismo tipo.
  • Colas: es una lista en la que los elementos se insertan por un extremo.
  • Pilas: es una estructura de datos en la cual todas las inserciones y eliminaciones se realizan por el mismo extremo.

  ### TADs no lineales.

  • Arboles: Es un TAD que organiza sus elementos de forma jerárquica.
  • Binarios de búsqueda: Se trata de aquellos árboles binarios (cada nodo tiene dos hijos como máximo) en los cuales todos los datos del subárbol izquierdo son menores que los datos del nodo, y los datos del subárbol derecho son mayores que los datos del nodo.
  • Grafos: se utilizan para representar relaciones arbitrarias entre datos.

  ### Ejemplos de uso de TDA

  • Conjuntos: implementación de conjuntos con sus operaciones básicas (unión, intersección y diferencia), operaciones de intersección, borrado y búsqueda.
  • Arboles binarios de búsqueda: implementación de árboles de elementos, utilizados para la representación interna de datos complejos.
  • Pilas y colas: implementación de los algoritmos FIFO y LIFO.
  • Grafos: implementación de grafos; una serie de vértices unidos mediante una serie de arcos y aristas.

  ## CONCLUSIÓN

  Hay muchos tipos de datos: enteros, punto flotante, booleanos, cadenas de texto, etc., todas tiene su utilidad, igual los tipos de datos abstractos (TAD), siendo parte de la evolución a la programación orientada a objeto (POO) y al desarrollo del software en base a la importancia de sus aplicaciones y a la mejora de rendimiento a la hora de programar.
  La implementación de los TADs y sus diferentes usos han mejorado la forme en como programamos y de cómo estructuramos los datos de forma más abstracta enfocándonos solo en la partes relevantes del algoritmo mejorando su implementación en softwares más complejos o con un equipo de persona considerablemente grande.

  ## BIBLIOGRAFIA

  • Luis Joyanes, Ignacio Zahonero. (2007). Estructura de Datos en C++. Madrid: McGraw-Hill
  • Guardati Buemo. (2007)Estructura de datos orientada a objetos: algoritmos con C++. México: Prentice Hall.
  • Luis Joyanes Aguilar. (2005). Estructuras de datos en C. Madrid: McGraw-Hill.
  • Criado Clavero, María Asunción. (2006). Programación en lenguajes estructurados. México, D.F: Alfaomega.
  • López Román, Leobardo. (2011). Programación estructurada y orientada a objetos: un enfoque algorítmico. México, D. F: Alfaomega.
  • Luis. J.A., Matilde. F.A., Lucas. S.G., Ignacio. Z.M. (2005). Estructuras de datos en c. (1ra ed.).Madrid, Schaum. McGraw-Hill.

  ## BIBLIOGRAFIA ELECTRONICA

  • Donal Wales, J. (2017). Tipo de dato abstracto. 2017, de Wikipedia Sitio web: https://es.wikipedia.org/wiki/Tipo_de_dato_abstracto
  • Contreras, H. (2014). Tipo de Dato Abstracto (TDA). 2015, de Universidad de los Andes, de Sitio web: http://webdelprofesor.ula.ve/ingenieria/hyelitza/materias/programacion2/tda/PR2-tema1-TDA.pdf
  • Serrano, M. (2010). Estructura de Datos. 2012, de Universidad de Valladolid Sitio web: https://www.infor.uva.es/~mserrano/EDI/cap2.pdf
  • Paredes, D. (2009). Tipos Abstractos de Datos. 2013, de David Paredes.es Sitio web: http://www.davidparedes.es/2009/01/02/tipos-abstractos-de-datos-tad/

  ## COMPLEMENTOS

  Estructura de datos creación de TDA