Tema 12. Tipos abstractos y Estructuras de datos. Organizaciones de ficheros. Algoritmos. Formatos de información y ficheros.

1. Tipos abstractos y Estructuras de datos

1. Tipos abstractos y Estructuras de datos

🎯 Idea clave

• Los Tipos Abstractos de Datos (TAD) constituyen especificaciones matemáticas que definen qué valores y operaciones son válidos, independientemente de su representación física en memoria.
• Las estructuras de datos son las implementaciones concretas que materializan los TAD, determinando cómo se almacena y accede a la información.
• La separación entre especificación (TAD) e implementación (estructura) permite dominar la complejidad y facilita el mantenimiento del software.
• Los tipos primitivos (enteros, reales, booleanos, caracteres) sirven de base para construir tipos compuestos estáticos y dinámicos.
• La elección entre diferentes estructuras de datos determina la eficiencia en operaciones de almacenamiento, búsqueda, inserción y eliminación.

📚 Desarrollo

Definición de tipo de dato. Un tipo de dato establece un conjunto de valores posibles y un conjunto de operaciones válidas sobre dichos valores. Los enteros permiten operaciones aritméticas, los booleanos operaciones lógicas, y las cadenas permiten comparaciones, búsquedas y concatenaciones. Esta definición constituye el fundamento sobre el que se construyen representaciones más complejas de la información.

Concepto de TAD. El Tipo Abstracto de Datos describe un modelo lógico mediante sus valores y operaciones sin fijar una representación concreta. Lo esencial es su interfaz: qué operaciones existen, qué parámetros reciben, qué resultados devuelven y qué condiciones deben respetarse. Por ejemplo, una pila se define por operaciones como apilar, desapilar y consultar la cima, independientemente de que se implemente con un array o una lista enlazada.

Separación abstracción-implementación. La abstracción surge cuando se separa lo que el dato permite hacer de cómo se almacena internamente. Esta separación facilita diseñar programas mantenibles, cambiar implementaciones sin afectar el comportamiento observable, y razonar sobre el sistema sin depender de detalles físicos. El TAD responde al qué, mientras la estructura de datos responde al cómo.

Tipos primitivos y compuestos. Los tipos primitivos (enteros byte/short/int/long, reales float/double, char, booleano, string) actúan como elementos base. Sobre ellos se construyen tipos compuestos para representar entidades más ricas: registros, objetos, listas, mapas, árboles o grafos. Estos se dividen en estáticos, cuya memoria se asigna en tiempo de compilación, y dinámicos, que gestionan su espacio en tiempo de ejecución.

Estructuras lineales. El array ofrece acceso directo en tiempo constante pero inserciones costosas. La lista enlazada permite inserciones eficientes con referencia previa pero requiere recorrido secuencial. Las pilas funcionan bajo esquema LIFO con operaciones push y pop, mientras las colas operan FIFO mediante enqueue y dequeue. El deque y las colas de prioridad implementadas con heaps binarios amplían estas funcionalidades básicas.

Jerarquías y grafos. Los árboles binarios de búsqueda ofrecen operaciones logarítmicas en promedio que degradan a lineal si pierden equilibrio. Los árboles balanceados (AVL, rojo-negro, B-tree, B+-tree) garantizan altura logarítmica mediante rotaciones, siendo los B-trees fundamentales para índices de bases de datos. Los grafos se representan mediante matrices de adyacencia (complejidad espacial cuadrática) o listas de adyacencia (lineal respecto a vértices y aristas), sobre los que se construyen algoritmos de recorrido DFS, BFS, Dijkstra, Floyd-Warshall y ordenamiento topológico.

🧩 Elementos esenciales

• Tipo de dato: Conjunto de valores posibles y operaciones válidas definidas sobre ellos.
• TAD: Especificación matemática que define la interfaz lógica sin determinar la implementación física.
• Estructura de datos: Realización concreta de un TAD en memoria o almacenamiento secundario.
• Abstracción: Principio que separa el comportamiento observable de los detalles de representación interna.
• Tipos primitivos: Enteros, reales, caracteres, booleanos y cadenas que sirven de bloques constructivos básicos.
• Tipos compuestos estáticos: Arrays, registros, conjuntos y ficheros con memoria fijada en compilación.
• Tipos compuestos dinámicos: Listas, pilas, colas, árboles, grafos y tablas hash con gestión flexible de memoria.
• Array: Estructura lineal con acceso O(1) e inserción O(n) por desplazamiento de elementos.
• Lista enlazada: Secuencia nodos con acceso secuencial O(n) e inserción O(1) conocida la posición.
• Pila: Estructura LIFO con operaciones push (apilar) y pop (desapilar) sobre el elemento de la cima.
• Cola: Estructura FIFO con operaciones enqueue (encolar) y dequeue (desencolar) en extremos opuestos.
• Árbol binario de búsqueda: Estructura jerárquica con operaciones O(log n) medias que requieren equilibrio para garantizar eficiencia.
• Grafo: Conjunto de vértices y aristas representable mediante matrices o listas de adyacencia para modelar relaciones complejas.

🧠 Recuerda

• Un TAD especifica el qué y la estructura de datos implementa el cómo.
• La separación entre ambos conceptos materializa los principios de abstracción, encapsulamiento y ocultación de información.
• Los B-trees y B+-trees constituyen la base de los índices en sistemas de bases de datos por su eficiencia en acceso a disco.
• Los grafos permiten modelar relaciones complejas no jerárquicas mediante matrices o listas de adyacencia.
• La elección entre array y lista enlazada implica compensar entre velocidad de acceso directo y flexibilidad de inserción.
• Las operaciones sobre árboles binarios de búsqueda degeneran a O(n) cuando el árbol pierde el equilibrio.
• Las colas de prioridad se implementan habitualmente mediante heaps binarios para obtener inserción y extracción eficientes.
• Los recorridos DFS (profundidad) y BFS (anchura) son fundamentales para resolver problemas sobre grafos.

2. Organizaciones de ficheros

2. Organizaciones de ficheros

🎯 Idea clave

• La organización de ficheros define cómo se estructuran, almacenan, acceden y actualizan los datos persistentes en un sistema informático.
• Un registro es la unidad lógica de información básica, formado por campos relacionados que pueden tener longitud fija o variable.
• La organización secuencial es simple y eficiente para recorridos completos, pero resulta limitada para búsquedas puntuales específicas.
• La organización directa permite el acceso por posición calculable, especialmente cuando existe correspondencia entre clave y posición relativa.
• La organización indexada utiliza estructuras auxiliares para localizar registros por clave, acelerando consultas pero requiriendo mantenimiento.
• La elección entre organizaciones depende del patrón de acceso predominante y del equilibrio entre velocidad de consulta y coste de gestión.

📚 Desarrollo

Definición y estructura básica. La organización de ficheros establece el método mediante el cual se estructuran, almacenan, acceden y actualizan los datos persistentes. El registro constituye la unidad lógica de información formada por campos relacionados entre sí, pudiendo ser de longitud fija o variable, lo cual afecta directamente al acceso, al espacio utilizado y a las operaciones de actualización.

Organización secuencial y ordenada. La organización secuencial resulta simple y eficiente para recorridos completos del fichero, aunque presenta debilidad ante búsquedas puntuales. Su variante ordenada facilita los recorridos por clave y ciertas búsquedas, pero complica significativamente las operaciones de inserción, requiriendo gestionar huecos y reorganizaciones periódicas.

Acceso directo y relativo. La organización directa o relativa permite el acceso mediante posición calculable, donde el registro lógico número n se ubica en una posición determinada. Resulta especialmente eficiente cuando se utilizan registros de longitud fija y existe una correspondencia estable entre la clave y la posición relativa, aunque puede desperdiciar espacio cuando las claves son dispersas.

Estructuras indexadas. La organización indexada incorpora una estructura auxiliar que relaciona claves con posiciones físicas del fichero, funcionando como una tabla de acceso. Puede implementarse mediante índices primarios o secundarios, densos (una entrada por registro) o dispersos (entradas por grupos o bloques), que aceleran las consultas pero consumen espacio adicional y deben mantenerse actualizados.

Alternativas hash y secuencial-indexada. La organización hash favorece las búsquedas exactas por clave, aunque no conserva el orden ni permite consultas por rangos ordenados. La organización secuencial indexada combina las ventajas del recorrido ordenado con el acceso selectivo mediante índice, ofreciendo versatilidad ante distintos patrones de acceso.

Criterios de selección. La elección de una organización depende del patrón de acceso predominante: secuencial para procesamientos totales, índice o hash para búsquedas frecuentes por clave exacta, y organizaciones ordenadas o de tipo árbol para consultas por rango. Además, deben considerarse aspectos de concurrencia, integridad, copias de seguridad y recuperación para una gestión fiable.

🧩 Elementos esenciales

• Registro: Unidad lógica de información formada por campos relacionados entre sí.
• Longitud fija vs variable: Cada tipo afecta de forma diferente al acceso, al espacio ocupado y a la actualización de datos.
• Organización secuencial: Simple y eficiente para recorridos completos, pero lenta para búsquedas puntuales.
• Organización secuencial ordenada: Facilita recorridos por clave y ciertas búsquedas, aunque complica las inserciones y requiere gestionar huecos.
• Organización directa: Permite acceso por posición calculable, especialmente útil con registros de longitud fija y correspondencia clave-posición.
• Organización relativa: Variante donde cada registro se identifica por un número relativo dentro del fichero.
• Organización indexada: Usa estructuras auxiliares para localizar registros por clave, con mayor velocidad de consulta y coste de mantenimiento.
• Índice denso: Contiene una entrada por cada registro del fichero.
• Índice disperso: Contiene entradas por grupos, bloques o puntos de referencia.
• Organización hash: Optimiza búsquedas exactas por clave pero no mantiene orden ni permite consultas por rangos.
• Secuencial indexada: Combina recorrido ordenado con acceso selectivo por índice.
• Gestión fiable: Incluye concurrencia, integridad, copias de seguridad y recuperación de ficheros.

🧠 Recuerda

• La organización define estructura, almacenamiento, acceso y actualización de datos persistentes.
• Los registros son la unidad lógica básica formada por campos relacionados.
• Secuencial: ideal para procesar todo el fichero secuencialmente, ineficiente para búsquedas puntuales.
• Directa: requiere correspondencia clave-posición y funciona mejor con registros de longitud fija.
• Indexada: mayor velocidad de consulta a costa de espacio adicional y mantenimiento del índice.
• Hash: excelente para búsquedas exactas, inadecuado para rangos ordenados.
• Secuencial ordenada: útil para consultas por rango pero costosa en inserciones y eliminaciones.
• Los índices pueden ser primarios, secundarios, densos o dispersos según el diseño requerido.
• La elección depende del patrón de acceso: recorridos totales, búsquedas exactas o consultas por rango.
• Metadatos y directorios son esenciales para localizar, proteger y gestionar la información.

3. Algoritmos

3. Algoritmos

🎯 Idea clave

• Un algoritmo es una secuencia finita, ordenada y precisa de instrucciones que transforma datos de entrada en resultados de salida.
• El algoritmo constituye la solución lógica abstracta, mientras que el programa es su implementación concreta en un lenguaje ejecutable.
• Las propiedades fundamentales son la finitud, la precisión, la efectividad y la existencia de entradas y salidas.
• Las estructuras básicas de control son la secuencia, la selección y la iteración.
• La complejidad algorítmica se expresa mediante notación asintótica para evaluar eficiencia temporal y espacial.
• Las principales técnicas de diseño incluyen divide y vencerás, programación dinámica, algoritmos voraces y backtracking.

📚 Desarrollo

Definición formal. Un algoritmo es una secuencia finita, ordenada y precisa de pasos que transforma unos datos de entrada en un resultado determinado. Constituye el núcleo conceptual de la informática como disciplina científica, describiendo la solución lógica de un problema antes de su codificación. Para que una secuencia sea considerada algoritmo válido, debe cumplir propiedades fundamentales: ser finita (terminar tras número limitado de pasos), precisa (instrucciones claras y no ambiguas), efectiva (operaciones ejecutables realmente) y determinada (proceso claramente definido).

Algoritmo versus programa. Existe una diferencia conceptual crucial entre ambos términos. El algoritmo es la solución lógica abstracta, independiente de la máquina concreta, expresable en pseudocódigo, diagramas de flujo o lenguaje natural estructurado. El programa es la implementación de uno o varios algoritmos en un lenguaje que puede ser traducido o interpretado por un sistema informático, conteniendo instrucciones específicas, estructuras de control y gestión de entrada y salida. Un mismo algoritmo puede implementarse en distintos lenguajes.

Estructuras y corrección. Las estructuras básicas de control fundamentales son la secuencia (ejecución ordenada), la selección (decisiones condicionales) y la iteración (repetición de bloques). La corrección total de un algoritmo exige tanto la obtención del resultado correcto como la garantía de terminación, lo que distingue un procedimiento válido de descripciones procedimentales incompletas o infinitas.

Análisis de complejidad. La eficiencia se mide mediante la notación O grande, que describe el crecimiento asintótico del consumo de recursos respecto al tamaño de la entrada. Este análisis debe abordar tanto la complejidad temporal (tiempo de ejecución) como la espacial (memoria requerida), evaluándolas conjuntamente para determinar la viabilidad práctica del algoritmo.

Algoritmos de búsqueda. La búsqueda secuencial funciona sobre datos no ordenados recorriendo secuencialmente los elementos, presentando un coste lineal O(n) en el peor caso. La búsqueda binaria requiere datos previamente ordenados y acceso eficiente por posición, reduciendo el coste a O(log n), aunque su aplicación está condicionada por estas restricciones previas.

Algoritmos de ordenación. Existen dos familias principales. Las ordenaciones simples (burbuja, selección e inserción) presentan normalmente complejidad cuadrática O(n²). Las ordenaciones eficientes (mergesort, quicksort y heapsort) ofrecen mejores prestaciones generales, aunque presentan matices respecto al uso de memoria auxiliar y comportamiento en el peor caso. La estabilidad es una propiedad relevante que conserva el orden relativo de elementos equivalentes.

Técnicas de diseño. La recursividad requiere definir un caso base y reducir progresivamente el problema. Las estrategias algorítmicas fundamentales incluyen divide y vencerás (descomposición en subproblemas), programación dinámica (almacenamiento de subproblemas resueltos), algoritmos voraces (toma de decisiones locales óptimas) y backtracking (exploración sistemática con retroceso). La elección de la estructura de datos condiciona decisivamente la eficiencia real del algoritmo.

🧩 Elementos esenciales

• Finitud: El algoritmo debe terminar después de un número limitado de pasos para las entradas previstas.
• Precisión: Cada instrucción debe tener un significado claro y no ambiguo, eliminando cualquier interpretación dudosa.
• Efectividad: Los pasos deben ser ejecutables de manera realista por una máquina o procedimiento formal.
• Entradas y salidas: Debe especificar los datos iniciales que recibe y los resultados que produce, aunque las entradas puedan ser cero.
• Corrección total: Exige tanto la obtención del resultado correcto como la garantía de terminación del proceso.
• Notación O grande: Describe el crecimiento asintótico del consumo de recursos, no valores exactos en segundos.
• Búsqueda secuencial: Opera sobre datos no ordenados con coste lineal O(n) en el peor caso.
• Búsqueda binaria: Requiere datos ordenados y acceso por posición, ofreciendo coste logarítmico O(log n).
• Ordenaciones simples: Burbuja, selección e inserción presentan normalmente complejidad O(n²).
• Ordenaciones eficientes: Mergesort, quicksort y heapsort ofrecen mejores prestaciones con distintos matices de memoria y peor caso.
• Estabilidad: Propiedad que conserva el orden relativo original de elementos equivalentes tras la ordenación.
• Recursividad: Técnica que requiere caso base y reducción progresiva del problema para evitar bucles infinitos.

🧠 Recuerda

• El algoritmo es abstracto; el programa es su implementación concreta y ejecutable.
• Complejidad temporal y espacial deben analizarse conjuntamente para evaluar la viabilidad real.
• La estructura de datos elegida condiciona decisivamente la eficiencia del algoritmo.
• La búsqueda binaria requiere obligatoriamente datos ordenados y acceso eficiente por posición.
• La recursividad siempre necesita un caso base bien definido para garantizar la terminación.
• Divide y vencerás, programación dinámica, voracidad y backtracking constituyen las técnicas de diseño fundamentales.
• La notación O grande indica tendencias de crecimiento, no mediciones temporales exactas.
• La estabilidad en ordenación preserva el orden original entre elementos de igual valor.
• Un programa sintácticamente correcto puede ser incorrecto si el algoritmo subyacente no resuelve bien el problema.
• La corrección total exige tanto resultado correcto como terminación garantizada.

4. Formatos de información y ficheros

4. Formatos de información y ficheros

🎯 Idea clave

• La Norma Técnica de Interoperabilidad del Catálogo de Estándares establece los formatos admitidos para el intercambio y conservación en Administraciones Públicas españolas.
• Los formatos abiertos garantizan la interoperabilidad real sin dependencia de proveedores específicos ni restricciones técnicas.
• Se distinguen formatos específicos para documentos, imágenes, audio, vídeo, datos estructurados, información geoespacial y firma electrónica.
• La firma electrónica utiliza formatos estandarizados como XAdES, CAdES, PAdES y ASiC para garantizar autenticidad e integridad.
• Los datos abiertos priorizan formatos legibles por máquina como CSV, JSON, XML, RDF y GeoJSON junto a sindicación ATOM y RSS.
• Los estándares semánticos como ISO/IEC 11179, Dublin Core y DCAT complementan la interoperabilidad sintáctica con metadatos descriptivos.

📚 Desarrollo

Marco normativo. La Norma Técnica de Interoperabilidad del Catálogo de Estándares, derivada del Esquema Nacional de Interoperabilidad, establece los formatos admitidos para el intercambio y conservación de información en las Administraciones Públicas españolas. Esta normalización persigue garantizar que la información generada por una Administración pueda ser leída, procesada e intercambiada por cualquier otra Administración o por la ciudadanía, sin dependencia de un proveedor concreto.

Documentos ofimáticos. Entre los formatos de documento se admiten PDF/A, ODF, OOXML, TXT, RTF y HTML. El formato OOXML corresponde a documentos ofimáticos de Microsoft con extensiones como .docx, .xlsx y .pptx, y está normalizado internacionalmente como ISO/IEC 29500, lo que garantiza su interoperabilidad a pesar de su origen corporativo.

Contenidos multimedia. Para imagen se aceptan JPEG, PNG, TIFF y SVG, mientras que para audio y vídeo se utilizan MP3, AAC, OGG, FLAC, MP4, WebM y MKV. Estos formatos aseguran la compatibilidad para el tratamiento de contenidos audiovisuales y gráficos en el ámbito administrativo, permitiendo su visualización y procesamiento estándar.

Datos estructurados y geoespaciales. Para datos estructurados se admiten XML, JSON, RDF en sus distintas serializaciones como XML y Turtle, y CSV. En el ámbito geoespacial se utilizan GML, KML y Shapefile. GML constituye la base de la directiva INSPIRE para información geográfica vectorial, mientras que KML se emplea frecuentemente en visores como Google Earth.

Firma electrónica. En materia de firma electrónica se admiten los formatos XAdES, CAdES, PAdES y ASiC. El formato XAdES se utiliza profusamente en la Administración Pública española para la firma electrónica avanzada sobre XML, constituyendo un estándar seguro para la autenticación de documentos administrativos y el intercambio electrónico seguro.

Estándares sectoriales y datos abiertos. Para la publicación de datos abiertos se priorizan CSV, JSON, XML, RDF, JSON-LD, GeoJSON y los formatos de sindicación ATOM y RSS. Además, existen estándares sectoriales específicos como HL7 v3 y CDA para el intercambio sanitario, SEPA e ISO 20022 para mensajería bancaria, y BPMN XML y BPEL para el modelado y ejecución de procesos de negocio.

Interoperabilidad semántica. No basta con el formato del fichero para garantizar la interoperabilidad; también es necesario un acuerdo sobre la semántica de los datos. Estándares como ISO/IEC 11179, dedicado a metadatos, Dublin Core, que define un conjunto mínimo de elementos descriptivos, y DCAT, orientado al catálogo de conjuntos de datos abiertos, complementan el plano sintáctico con la dimensión semántica necesaria.

🧩 Elementos esenciales

• PDF/A: formato de documento admitido para la conservación a largo plazo y la preservación de la integridad del contenido.
• ODF: formato abierto para documentos ofimáticos que garantiza la independencia de proveedores específicos.
• OOXML: estándar ISO/IEC 29500 para documentos Microsoft Office que incluye extensiones como .docx, .xlsx y .pptx.
• RDF: modelo de datos para la web semántica que utiliza serializaciones como XML y Turtle para representar información.
• GML: lenguaje de marcado geográfico que constituye la base técnica de la directiva INSPIRE para datos espaciales.
• XAdES: formato de firma electrónica avanzada sobre XML ampliamente utilizado en la Administración Pública española.
• NTI Documento Electrónico (ENI): estructura XML obligatoria para los documentos electrónicos en el ámbito administrativo español.
• Dublin Core: estándar de metadatos que define un conjunto mínimo de elementos descriptivos para recursos digitales.
• DCAT: vocabulario orientado al catálogo de conjuntos de datos abiertos que facilita el descubrimiento de información pública.
• HL7 v3 y CDA: estándares específicos para el intercambio de información sanitaria entre sistemas del sector público.
• SEPA e ISO 20022: normas de mensajería bancaria y de pagos utilizadas en las transacciones financieras de la administración.

🧠 Recuerda

• La Norma Técnica de Interoperabilidad define los formatos válidos para el intercambio administrativo en España.
• Los formatos abiertos evitan la dependencia tecnológica de proveedores comerciales específicos.
• XAdES es el formato de firma electrónica más extendido en la Administración Pública española para documentos XML.
• GML es el estándar obligatorio para la representación de datos geográficos según la directiva INSPIRE.
• La interoperabilidad efectiva requiere tanto formatos sintácticos como estándares semánticos para los datos.
• Dublin Core y DCAT son fundamentales para la descripción y catalogación de metadatos en información pública.
• El formato NTI Documento Electrónico (ENI) es obligatorio para la estructuración de documentos administrativos electrónicos.
• Los datos abiertos priorizan siempre formatos legibles por máquina como JSON y CSV sobre formatos propietarios.