ESTRUCTURA DE DATOS

Sirven para representar la información en un ordenador. Son las distintas estructuras que utilizamos para representar la información en un ordenador por ejemplo cuando estamos construyendo una aplicación que sirve para representar los datos de los libros, de una librería o de una biblioteca.

TIPOS DE DATOS

En la construcción de algoritmos eficientes, no solo basta la utilización de la lógica correcta para la resolución del problema sino también las estructuras de datos involucradas en dicho algoritmo. Las estructuras de datos están compuestas por un conjunto de variables que almacenarán los valores necesarios para un algoritmo. Estos valores toman información de acuerdo a un conjunto finito definido por un lenguaje de programación que los identifica. Asociado a estos valores se encuentra una serie de operaciones particulares. A este conjunto de valores y operaciones particulares se le conoce como tipo de dato de un lenguaje de programación.

A continuación estudiaremos en qué consisten los tipos de datos, una pequeña clasificación, que operaciones están asociadas a éstos y cómo están representadas en la computadora.

DEFINICIONES

Un tipo de dato es un conjunto de valores y un conjunto de operaciones aplicadas a dichos valores en un lenguaje de programación. Dependiendo del lenguaje de programación, un tipo de dato puede ser una estructura de datos, un tipo definido por el programador, un tipo abstracto, una clase, entre otros. Es posible clasificar los tipos de datos en tipos simples o elementales y en tipos compuestos o estructurados. En cuadro sinóptico se muestra la clasificación empleada de tipos de datos para la notación empleada.

El tipo simple está formado por aquellos que no pueden dividirse en componentes, es decir, forman en sí un tipo de dato indivisible o tipo base. Por el contrario, el tipo compuesto está formado por componentes tal que puede descomponerse o dividirse en tipos simples. Entre los tipos simples están el tipo Char, Pointer, Integer, Real, Boolean y Enum. En el tipo compuesto se encuentra el tipo String y Array, los cuales pertenecen a una sub-clasificación de acuerdo al tipo de elementos simples que lo conforman (tipo homogéneo); y los tipo Register y File que pueden contener elementos de diversos tipos (heterogéneo).

Es importante destacar que la clasificación se enfoca en los tipos de datos estáticos o creados de forma directa en la mayoría de los lenguajes de programación. Se excluyen tipos compuestos homogéneos dinámicos como listas, árboles, grafos, entre otros.

Básicamente en un lenguaje de programación, es posible expresar los valores de un tipo de dato de 3 formas:

1. Constantes: denotan un valor en particular dentro del conjunto posible para un tipo de dato.

2. Identificadores, nombres o variables: representan un valor cualquiera del conjunto posible para un tipo de dato asociado a una combinación de caracteres (dependiente del lenguaje).

3. Expresiones: denotan valores como resultado de operaciones entre constantes/identificadores/otras expresiones.

Cada tipo de dato determina una clase de valores que puede asumir un identificador o expresión las cuales pertenecen a un solo tipo. Por su parte, los operadores actúan sobre operando de algún tipo y arrojan como resultado otro tipo (que puede ser del mismo tipo o no). Al mismo tiempo, la utilización de los tipos de datos proporciona un ocultamiento de la representación interna en el computador de dichos tipos, ofreciendo una abstracción que es beneficiosa para la portabilidad y semántica de los programas. Del mismo modo, la verificación de los tipos durante el programa es una tarea importante a realizar. Esta verificación consiste en detectar que cada operación reciba el número adecuado de argumentos y que estos sean del tipo adecuado. Esto puede ser realizado de forma dinámica o de forma estática, es decir, en momento de ejecución o compilación/traducción respectivamente.

A continuación estudiaremos los tipos de datos indicando su organización lógica de definición, así como las operaciones y atributos que posee. También se estudiará la representación que manejan internamente en el computador, la cantidad de memoria que ocupan (CM (tipo)), y el conjunto de valores que puede tomar denominado como cardinalidad (CARD (tipo)).

En este estudio, no se tomará en cuenta el controlador o descriptor que algunos lenguajes de programación asocia a ciertos tipos de datos para realizar chequeos de desbordamiento que son ejecutados en tiempo de ejecución. Este descriptor puede incluir identificador únicos que asocian a un identificador así como límites o identificadores de subtipos.

TIPO DE DATO SIMPLE

Los valores de los tipos simples se codifican en la memoria del dispositivo como una secuencia de 0’s y 1’s. Estos están presente en la mayoría de lenguajes de programación y consideraremos los más esenciales. Por lo general, los tipos de dato simple ocupan lo que se denomina una palabra en memoria, debido a que en el peor de los casos los datos están alineados a frontera de palabra. Una palabra se define como una cantidad de bytes que es dependiente del hardware y está  directamente relacionada con el direccionamiento. Por ejemplo, en la tabla 2 se muestra el espacio en bytes  ocupado para una palabra de memoria en diversas arquitecturas.

 

Se considera que el tamaño de un tipo simple es 1 palabra, es decir, CM (tipo simple) = 1. Las instancias o variables creadas son las que ocupan el espacio en memoria mientras que la representación de los tipos no.

TIPO INTEGER

Conjunto de Valores: Se define como un subconjunto de Z (números enteros).

Conjunto de Operaciones: Suma, resta, multiplicación, división entera (div), residuo (mod), y operaciones relacionales (>, <, >=, <=, ==, ! =).

En algunos lenguajes existen operaciones bit a bit, es decir, operadores que manejan la representación binaria del tipo Integer tales como desplazamientos/corrimientos de bits o bitwise.

Representación: La representación de los enteros se pueden clasificar en enteros sin signo y con signo. Un entero sin signo (unsigned integer) que emplee n bits para su representación, puede representar un total de 2n valores. Por ejemplo, el número decimal 3, en una arquitectura donde el tipo Integer requiera n = 8 bits, dicho número sería 00000011.

Por otro lado, un entero con signo (signed integer) requiere que los números negativos sean representados en formato binario.

Así, existen diversas representaciones como signo-magnitud, complemento a la base menos uno (o complemento a uno), complemento a la base (o complemento a dos), en exceso a k, y base -2. Cada una de las representaciones tiene sus ventajas y desventajas (que no son tema de este documento).

Como ejemplo, se explicará la representación de complemento a dos para el número -6. La forma más sencilla es codificar el número en valor absoluto a su representación en binario, luego invertir todos los bits y finalmente sumarle el valor de 1. Así se tiene:

00000110 // representación del número |−6|

11111001 // invertir todos los bits

11111010 // sumarle el valor de 1, entonces 11111010 = −6

Cardinalidad: Dependiendo del número de bits empleados en la representación de un valor tipo Integer, existe una variación en el número de valores posibles que pueden tomar. En la tabla 2 se muestra el rango de valores y la cantidad de valores para diferentes tamaños de n empleando la representación de complemento a dos.

Así, la cardinalidad para el tipo Integer con una representación de n bits es 2n − 1 valores.

 ACTIVIDADES

              1-    Leer el texto.

              2-    Resumir el texto y copiar en la carpeta.

              3-    Graficar el cuadro sinóptico de la clasificación de los tipos de datos.

              4-    Realizar un glosario con las palabras que no conozca.

              5-    Mirar el video y representar la cardinalidad con signo y sin signo del tipo de datos integer expuestos en el video.

              6-    Comentar en el blog dejando su nombre, apellido, institución curso y división y consultar sus dudas.