Estructuras de datos abstractas
En informática, un tipo de datos abstracto (ADT) es un modelo matemático para tipos de datos donde un tipo de datos se define por su comportamiento (semántica) el punto de vista de un usuario de los datos, específicamente en términos de posibles valores, posibles operaciones sobre datos de este tipo y el comportamiento de estas operaciones. Esto contrasta con las estructuras de datos, que son representaciones concretas de datos, y son el punto de vista de un implementador, no de un usuario.
Formalmente, un ADT puede definirse como una «clase de objetos cuyo comportamiento lógico está definido por un conjunto de valores y un conjunto de operaciones»; esto es análogo a una estructura algebraica en matemáticas. Lo que se entiende por «comportamiento» varía según el autor, con los dos tipos principales de especificaciones formales para el comportamiento siendo la especificación axiomática (algebraica) y un modelo abstracto; estos corresponden a la semántica axiomática y a la semántica operativa de una máquina abstracta, respectivamente. Algunos autores también incluyen la complejidad computacional («costo»), tanto en términos de tiempo (para operaciones de computación) como de espacio (para representar valores).
La razón por la que utilizamos estructuras abstractas es porque utilizan de manera eficiente la memoria basada en el diseño de los datos almacenados en ellas. Con cantidades muy grandes de datos o datos que cambian con mucha frecuencia, la estructura de datos puede marcar una gran diferencia en la eficiencia (tiempo de ejecución) de su programa informático.
En un lenguaje más común, una estructura de datos abstracta es solo una disposición de datos que hemos incorporado en una disposición ordenada.
Una descripción perfectamente encantadora
Algunos tipos de estructuras de datos abstractas
Evaluadas por el IB
- estructura de datos estática y dinámica
- arrays
- arrays bidimensionales
- pila
- cola
- lista vinculada
- árbol
- árbol binario
- colecciones
- recursión
NO evaluadas por el IB, pero debes conocerlas
- listas
- diccionarios
- conjuntos
- tupla
Operaciones básicas de estructuras de datos
Encontré esta excelente diapositiva de Simon Allardice.
Comparación de diferentes estructuras de datos
| Estructura de datos | Fortalezas | Debilidades |
| matrices | Insertar y eliminar elementos, iterar a través de la colección | Ordenar y buscar, Insertar y eliminar, especialmente si está insertando y eliminando al principio o al final de la matriz |
| lista vinculada | indexación directa, Fácil de crear y usar | acceso directo, búsqueda y clasificación |
| pila y cola | diseñado para LIFO / FIFO | acceso directo, búsqueda y clasificación |
| árbol binario | velocidad de inserción y eliminación, velocidad de acceso, mantenimiento del orden ordenado | cierta sobrecarga |
- Las estructuras fijas son más rápidas / más pequeñas
- Cuando está considerando si debe usar una estructura de datos abstracta, debe preguntarse: ¿qué contiene más datos y qué contiene los datos que cambian con más frecuencia?
Comparación de estructuras de datos estáticas vs dinámicas
Esta comparación se utiliza de nuestro libro de texto de ciencias de la computación.
| Estructura de datos estática | Estructura de datos dinámica |
| Ineficiente ya que se asigna memoria que puede no ser necesaria. | Eficiente, ya que la cantidad de memoria varía según sea necesario. |
| Acceso rápido a cada elemento de datos, ya que la ubicación de la memoria se fija cuando se escribe el programa. | Acceso más lento a cada elemento, ya que la ubicación de la memoria se asigna en tiempo de ejecución. |
| Las direcciones de memoria asignadas serán contiguas, por lo que el acceso será más rápido. | El acceso a las direcciones de memoria asignadas puede ser muy lento. |
| Las estructuras son de tamaño fijo, lo que las hace más predecibles para trabajar. Por ejemplo, pueden contener un encabezado. | Las estructuras varían en tamaño, por lo que debe haber un mecanismo para conocer el tamaño de la estructura actual. |
| La relación entre los diferentes elementos de datos no cambia. | La relación entre los diferentes elementos de datos cambiará a medida que se ejecute el programa. |
Elegir qué estructura de datos usar
Este gráfico se utiliza con gran gratitud del Departamento de Informática de la Escuela Secundaria de Dartford.
- Identifican una situación que requiere el uso del pensamiento recursivo.
- Identificar el pensamiento recursivo en una solución de problema especificada.
- Traza un algoritmo recursivo para expresar una solución a un problema.
- Describir las características de un arreglo bidimensional.
- Construye algoritmos utilizando matrices bidimensionales.
- Describir las características y aplicaciones de una pila.
- Construya algoritmos utilizando los métodos de acceso de una pila.
- Describir las características y aplicaciones de una cola.
- Construye algoritmos utilizando los métodos de acceso de una cola.
- Explicar el uso de matrices como pilas estáticas y colas.
- Describir las características y características de una estructura de datos dinámica.
- Describir cómo funcionan lógicamente las listas enlazadas.
- Dibuje listas enlazadas (simples, dobles y circulares).
- Describir las características y aplicaciones de una colección.
- Construir algoritmos utilizando los métodos de acceso de una colección.
- Discutir la necesidad de subprogramas y colecciones dentro de soluciones programadas.
- Construir algoritmos utilizando subprogramas predefinidos, matrices unidimensionales y / o colecciones.
- Describir cómo los árboles funcionan lógicamente (tanto binarios como no binarios).
- Definir los términos: padre, hijo izquierdo, hijo derecho, subárbol, raíz y hoja.
- Indica el resultado del recorrido del árbol de pedidos, pedidos y pedidos anticipados.
- Bosqueja árboles binarios.
- Define el término estructura de datos dinámica.
- Compare el uso de estructuras de datos estáticas y dinámicas.
- Sugerir una estructura adecuada para una situación dada.
Leave a Reply