ED 2023-11-05 Padilla G Rogelio U2

Descargar como docx, pdf o txt
Descargar como docx, pdf o txt
Está en la página 1de 6

UNIVERSIDAD DE GUAYAQUIL

FACULTAD DE CIENCIAS MATEMÁTICAS Y FÍSICAS


INGENIERÍA EN TECNOLOGÍAS DE LA INFORMACIÓN
TRABAJO DE CLASE
DOCENTE: Ing. Rogelio Padilla G, MSc SEMESTRE
ESTUDIANTE
FECHA:
:

TEMA: Tipos de datos abstractos lineales (tdas)

2.1 Concepto de TDA y ventajas

Tipos de Datos: Es una colección de valores.

Según su valor:
 Constante
 Variables
Según composición:
 Simples
 Estructurados
Simple:
 Entero
 Decimal
 Carácter
 Booleano
Estructurado:
 Arreglo
 Estructuras
 Unión
 Puntero

Definición de los tipos de datos predefinidos como TDA:


 El TDA entero tiene como posibles valores de los datos el conjunto {-1, -2, ..., ∞} ∪ {0, 1,
2, ..., ∞}, y como operaciones la suma, la resta, la multiplicación y la división entera.
 El TDA real tiene como tipo el conjunto de los puntos de la recta real (Z+Q+I) y como
operaciones la suma, la resta, la multiplicación y la división.
UNIVERSIDAD DE GUAYAQUIL
FACULTAD DE CIENCIAS MATEMÁTICAS Y FÍSICAS
INGENIERÍA EN TECNOLOGÍAS DE LA INFORMACIÓN
 El TDA Booleano tiene como conjunto de valores {True, False} y como operaciones las
definidas por el álgebra de Boole (AND, OR, NOT).
 El TDA carácter tiene como tipo el conjunto de caracteres definido por un alfabeto dado y
como operaciones todos los operadores relacionales (<, >, =, <>, ≥, ≤).

Definición de algunos tipos de datos estructurados como TDA:


 El TDA matriz es una colección homogénea de longitud fija tal que cada una de sus
componentes pueden ser accedidas individualmente mediante uno o varios índices, que
serán de tipo ordinal y que indican la posición de la componente dentro de la colección.
Las operaciones asociadas: Asignar_Elemento, Sumar, Restar, Negar, ProductoEscalar,
ProductoMatricial, Determinante, Inversa y Transponer.

 El TDA registro es un tipo de datos heterogéneo compuesto por un número fijo de


componentes denominadas campos a las que se accede mediante un selector de campo.

2.2 Representación BNF


La BNF (Backus-Naur Form por sus siglas en inglés: "BNF") es una notación formal utilizada
para describir la sintaxis de un lenguaje de programación. Consiste en un conjunto de reglas que
definen cómo se pueden combinar los elementos del lenguaje para crear declaraciones o
expresiones válidas.

En 1959, cuando estaba especificando la estructura del lenguaje de programación ALGOL, John
Backus desarrolló el Formulario Backus-Naur o notación normalizada BNF (siglas de Backus
Normal Form), con modificaciones de Peter Naur, que describe las reglas gramaticales para la
sintaxis de los lenguajes de alto nivel, con las que se podía describir cualquier lenguaje de
programación sin contexto. Posteriormente adaptado en varios lenguajes de programación y
para la utilización en varios idiomas.

SINTAXIS: forma de expresiones, sentencias y unidades de programa


SEMÁNTICA: significado de estas expresiones, sentencias y unidades de programa
Elementos Sintácticos
 Conjunto de caracteres
 Identificadores
 Símbolos de operadores
UNIVERSIDAD DE GUAYAQUIL
FACULTAD DE CIENCIAS MATEMÁTICAS Y FÍSICAS
INGENIERÍA EN TECNOLOGÍAS DE LA INFORMACIÓN
 Palabras claves y reservadas •Comentarios
 Blancos, delimitadores y paréntesis
 Expresiones
 Sentencias

Descripción de Sintaxis
Definición de Lenguajes:
 Reconocimiento (reconoce si string de entrada pertenece al lenguaje)
 Generación (genera strings que pertenecen al lenguaje)

2.3 TDA genérico


 Definición
Los TDAs se usan para definir un nuevo tipo a partir del cual se pueden crear instancias.
Como se mostrar en el ejemplo de la lista, algunas veces estas instancias deberán operar
del mismo modo sobre otros tipos de datos. Por ejemplo, uno puede pensar en listas de
manzanas, carros o aún listas. La definición semántica de una lista siempre es la misma.
Solamente el tipo de los elementos de datos cambia de acuerdo con el tipo sobre el cual
deba operar la lista.

Esta información adicional podrá ser especificada por un parámetro genérico que es
especificado al momento de la creación de la instancia. Así, una instancia de un TDA
genérico es en la práctica una instancia de una variante particular del TDA.

Ventajas, desventajas y aplicaciones


Ventajas
 Recogen mejor la semántica de los tipos. Al agrupar la representación junto a las
operaciones que definen su comportamiento, y forzar a utilizar el TDA a través de estas
operaciones se evitan errores en el manejo del tipo de datos (Por ejemplo, la división por
0 en el caso del TDA Racional).

 Abstracción: Separa la especificación (que hace) de la implementación (como lo hace).


Los usuarios de un TDA no necesitan conocer sus detalles de implementación. Como
consecuencia:
UNIVERSIDAD DE GUAYAQUIL
FACULTAD DE CIENCIAS MATEMÁTICAS Y FÍSICAS
INGENIERÍA EN TECNOLOGÍAS DE LA INFORMACIÓN
a) Se favorece la extensibilidad del Código: Es posible modificar y mejorarla
implementación del TDA sin afectar a los demás módulos que lo utilizan.
b) Aumenta la facilidad de uso.
c) Aumenta la legibilidad del Código que usa el TAD.

 Produce Código reutilizable.


 Favorece la ausencia de errores, reutilizar Código ya probado y forzar a utilizar la
estructura de datos correctamente.
Desventaja
 Grado de dificultad
 Se reserva antes de conocer los datos y causa siempre un manejo máximo de memoria
Aplicaciones
 Manipulación de datos en procesos necesarios para la resolución de problemas de la vida
real

Listas enlazadas simples:


Es una lista enlazada de nodos, donde cada nodo tiene un único campo de enlace. Una variable
de referencia contiene una referencia al primer nodo, cada nodo (excepto el último) enlaza con el
nodo siguiente, y el enlace del último nodo contiene NULL para indicar el final de la lista.

Estática
las estructuras de datos que obligan al programador a definir, antes de la ejecución del
programa, un tamaño y estructura que permanecerán fijas e invariables, siendo su objetivo
informar al compilador del espacio que debe reservar en memoria para ellas (estructuras
estáticas). Dinámica

Dinámica
Por ello, es interesante disponer de métodos que permitan acceder a las direcciones de memoria
que se necesiten durante la ejecución de dicho programa con la posibilidad de liberarlas,
ofreciéndonos también la posibilidad de modificar su tamaño y estructura en tiempo de ejecución.
Dichas estructuras se denotan con el nombre de dinámicas.

Variantes de Listas
Podemos distinguir, atendiendo a la organización de los nodos, entre:
UNIVERSIDAD DE GUAYAQUIL
FACULTAD DE CIENCIAS MATEMÁTICAS Y FÍSICAS
INGENIERÍA EN TECNOLOGÍAS DE LA INFORMACIÓN
 Listas simplemente enlazadas: cada nodo tiene un campo que apunta al siguiente nodo.
 Listas doblemente enlazadas: cada nodo dispone de un puntero que apunta al siguiente
nodo, y otro que apunta al nodo anterior.

Otra distinción puede ser:


 Listas lineales: son listas que tienen un comienzo y un final.
 Listas circulares: en estas listas el último elemento apunta al primero, por lo tanto
podríamos estar recorriéndolas siempre, ya que no tienen final.

Para que esta estructura sea un TDA lista enlazada, debe tener unos operadores asociados que
permitan la manipulación de los datos que contiene. Los operadores básicos de una lista
enlazada son:
 Insertar: inserta un nodo con dato x en la lista, pudiendo realizarse esta inserción al
principio o final de la lista o bien en orden.
 Eliminar: elimina un nodo de la lista, puede ser según la posición o por el dato.
 Buscar: busca un elemento en la lista.
 Localizar: obtiene la posición del nodo en la lista.
 Vaciar: borra todos los elementos de la lista

2.4 PILAS
 Definición
El método LIFO (Last In, First Out) es un método contable de valuación de inventarios que
asume que los últimos artículos comprados o producidos son los primeros en ser vendidos
o utilizados, es decir, da prioridad de salida a las últimas unidades de producto que han
llegado al almacén.

Una pila es la estructura de datos que se obtiene al limitar la adición o eliminación de


elementos a uno de los extremos de una lista enlazada. Esto es, en una pila sólo se
admite añadir y eliminar información por el principio (se puede hacer por el final, pero es
menos eficiente).

 Ventajas y desventajas
UNIVERSIDAD DE GUAYAQUIL
FACULTAD DE CIENCIAS MATEMÁTICAS Y FÍSICAS
INGENIERÍA EN TECNOLOGÍAS DE LA INFORMACIÓN
 Implementación dinámica

2.5 COLAS
 Definición
FIFO (First In - First Out): Primero en entrar - Primero en salir. Con el método FIFO el
primer lote de mercancía que entra en el almacén debe ser el primero en salir.

Una cola es la estructura de datos que se obtiene al limitar la adición y eliminación de


información en una lista de tal modo que sólo se admite la adición al principio de la lista, y
la eliminación al final de la lista.

 Ventajas y desventajas

 Implementación dinámica

También podría gustarte