📚 ALGORITMOS, ESTRUCTURAS DE DATOS Y TIPOS DE PDF

Clase magistral para el examen TAI

🎓 Cómo usar este documento: Lee la explicación de cada bloque temático y responde las preguntas antes de pasar al siguiente. Las soluciones comentadas están al final.

BLOQUE 1 — COMPLEJIDAD DE ALGORITMOS

Notación O grande — Tipos de complejidad

La complejidad algorítmica mide cómo crece el tiempo de ejecución (o el espacio) en función del tamaño de la entrada n.

💡 Orden de eficiencia (de mejor a peor):
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)

🧪 TEST — BLOQUE 1: Complejidad

1. ¿Cuál de las siguientes complejidades es la más eficiente?

• a) O(n²)
• b) O(n log n)
• c) O(log n)
• d) O(n)

2. Un algoritmo de búsqueda binaria tiene una complejidad de:

• a) O(1)
• b) O(log n)
• c) O(n)
• d) O(n²)

3. Los algoritmos básicos de ordenación (burbuja, inserción, selección) tienen una complejidad de:

• a) O(n)
• b) O(n log n)
• c) O(n²)
• d) O(log n)

BLOQUE 2 — ALGORITMOS DE ORDENACIÓN

Clasificación general

Algoritmos de ordenación
├── Básicos — O(n²)
│     ├── Ordenación por selección
│     ├── Ordenación por inserción
│     └── Ordenación por burbuja (intercambio directo)
├── Eficientes — O(n log n)
│     ├── Mergesort
│     ├── Quicksort  (O(n²) en peor caso)
│     ├── Heapsort
│     └── Shellsort
└── Casos especiales
      └── Binsort / Bucket sort — O(n) bajo ciertas condiciones

💡 Algoritmo estable: mantiene el orden relativo de los elementos con clave repetida. Inestable: no lo garantiza.

💡 Ordenación interna: en memoria principal (acceso aleatorio). Ordenación externa: en memoria secundaria (restricciones de acceso).

Algoritmos básicos — O(n²)

Ordenación por selección

Idea: En cada iteración, selecciona el menor elemento del subvector no ordenado y lo intercambia con el primero de ese subvector.

Ordenación por inserción

Idea: En cada iteración, inserta un elemento del subvector no ordenado en la posición correcta del subvector ya ordenado.

Ordenación por burbuja (intercambio directo)

Idea: Los elementos más ligeros "ascienden" hacia arriba. Compara pares adyacentes e intercambia si están desordenados.

💡 Mejora de la burbuja: usar un centinela que detecte si no hubo intercambios en una pasada → terminar anticipadamente.

Algoritmos eficientes — O(n log n)

Mergesort — "Divide y vencerás"

Idea: Dividir el conjunto en dos mitades, ordenar recursivamente cada mitad y combinar las dos mitades ordenadas.

Mergesort
1. Dividir el vector en dos mitades          → O(1)
2. Ordenar recursivamente cada mitad         → 2T(n/2)
3. Combinar (mezclar) las dos mitades        → O(n)

Recurrencia: T(n) = 2T(n/2) + n  →  T(n) ∈ O(n log₂ n)

Quicksort — "Divide y vencerás"

Idea: Elegir un pivote, dividir el vector de forma que los menores queden a la izquierda y los mayores a la derecha, y ordenar recursivamente cada parte.

Quicksort
1. Elegir un pivote (p)
2. Partir el vector: elementos < p | p | elementos > p
3. Ordenar recursivamente cada parte

⚠️ Dato clave: Quicksort tiene O(n²) en el peor caso pero es muy eficiente en la práctica.

Heapsort — Basado en montículo (heap)

Idea: Construir un árbol parcialmente ordenado (heap) e ir extrayendo el máximo/mínimo sucesivamente.

Heapsort — O(n log n) siempre
1. Construcción inicial del heap:
   n inserciones O(log n)  →  O(n log n)
2. Extracción del mayor elemento:
   n extracciones O(log n)  →  O(n log n)
Total: O(n log n)

Shellsort — Mejora de inserción

Idea: Mejora de la ordenación por inserción creada por Donald Shell (1959). Compara elementos separados por varias posiciones y en pasadas con saltos cada vez menores ordena el vector.

Tabla comparativa de algoritmos de ordenación

💡 Timsort: combinación de Mergesort + Inserción. Es el algoritmo usado en Python y Java en la práctica.

🧪 TEST — BLOQUE 2: Algoritmos de ordenación

4. ¿Cuál es la complejidad de Mergesort en el peor caso?

• a) O(n²)
• b) O(n log n)
• c) O(n)
• d) O(log n)

5. ¿Cuál es la complejidad de Quicksort en el peor caso?

• a) O(n log n)
• b) O(n)
• c) O(n²)
• d) O(log n)

6. ¿Qué algoritmo de ordenación fue creado por Donald Shell en 1959 como mejora de la ordenación por inserción?

• a) Heapsort
• b) Mergesort
• c) Shellsort
• d) Quicksort

7. ¿Cuál de los siguientes algoritmos de ordenación es estable y tiene complejidad O(n log n) en todos los casos?

• a) Quicksort
• b) Heapsort
• c) Mergesort
• d) Shellsort

8. La ordenación por inserción tiene un comportamiento casi lineal cuando:

• a) El vector tiene elementos duplicados
• b) El vector está casi ordenado
• c) El vector está ordenado de forma inversa
• d) El vector tiene un tamaño par

9. ¿Qué algoritmo de ordenación combina Mergesort con ordenación por inserción?

• a) Shellsort
• b) Heapsort
• c) Timsort
• d) Quicksort

BLOQUE 3 — ALGORITMOS PARA GRAFOS

¿Qué es un grafo?

Un grafo es una estructura de datos formada por vértices (nodos) y aristas (edges) que los conectan.

Tipos de grafos
├── Dirigido     → las aristas tienen dirección (→)
├── No dirigido  → las aristas no tienen dirección
├── Ponderado    → las aristas tienen peso (coste)
└── No ponderado → las aristas no tienen peso

Tabla completa de algoritmos para grafos

💡 V = número de vértices, E = número de aristas, f = flujo máximo

Resumen por categoría de problema

¿Qué algoritmo uso?

Ruta más corta (sin pesos)          → BFS
Ruta más corta (pesos no negativos) → Dijkstra
Ruta más corta (pesos negativos)    → Bellman-Ford
Rutas más cortas TODOS los pares    → Floyd-Warshall
Árbol de Expansión Mínima (MST)     → Prim o Kruskal
Componentes fuertemente conectados  → Kosaraju o Tarjan
Flujo máximo                        → Ford-Fulkerson o Edmonds-Karp
Detectar ciclos / orden topológico  → DFS

Aplicabilidad por tipo de grafo

🧪 TEST — BLOQUE 3: Algoritmos para grafos

10. ¿Qué algoritmo se usa para encontrar la ruta más corta en un grafo no ponderado?

• a) Dijkstra
• b) BFS
• c) Floyd-Warshall
• d) Bellman-Ford

11. ¿Cuál es la diferencia clave entre Dijkstra y Bellman-Ford?

• a) Dijkstra funciona con grafos no dirigidos; Bellman-Ford solo con dirigidos
• b) Dijkstra no admite pesos negativos; Bellman-Ford sí
• c) Bellman-Ford es más eficiente que Dijkstra en todos los casos
• d) Dijkstra encuentra el MST; Bellman-Ford encuentra el flujo máximo

12. ¿Qué algoritmo encuentra las rutas más cortas entre todos los pares de vértices?

• a) Dijkstra
• b) BFS
• c) Floyd-Warshall
• d) Prim

13. Los algoritmos de Prim y Kruskal se usan para encontrar:

• a) El flujo máximo en una red
• b) Los componentes fuertemente conectados
• c) El Árbol de Expansión Mínima (MST)
• d) La ruta más corta desde un origen

14. ¿Cuál es la complejidad de Floyd-Warshall?

• a) O(V + E)
• b) O(E log V)
• c) O(V³)
• d) O(VE)

15. ¿Para qué tipo de grafo se aplican exclusivamente los algoritmos de Prim y Kruskal?

• a) Grafos dirigidos y ponderados
• b) Grafos no dirigidos y ponderados
• c) Grafos dirigidos y no ponderados
• d) Cualquier tipo de grafo

BLOQUE 4 — ESTRUCTURAS DE DATOS: ÁRBOLES

¿Qué es un árbol?

Los árboles son estructuras de datos jerárquicas (no lineales). Sus nodos se almacenan en forma de árbol genealógico con un nodo raíz del que cuelgan los demás.

Terminología de los árboles

Propiedades de los árboles

⚠️ Dato clave: Un árbol vacío tiene 0 niveles. El nivel de la raíz es 1.

Tipos de árboles

Tipos de árboles
├── Árbol n-ario
│     └── Cada nodo puede tener hasta N hijos
├── Árbol binario
│     ├── Cada nodo puede tener máximo 2 hijos
│     ├── Árbol binario lleno → todos los nodos tienen 0 o 2 hijos
│     └── Árbol binario perfecto → lleno + todas las hojas en el mismo nivel

Recorridos sobre árboles binarios

💡 Los recorridos son búsquedas no informadas (a ciegas): recorren el árbol sin saber dónde está el dato buscado.

💡 Mnemotecnia:
- Pre = la raíz es lo primero
- In = la raíz está en medio (intermedio)
- Post = la raíz es lo último

Reconstrucción del árbol binario

Para reconstruir un árbol binario se necesitan dos recorridos, uno de los cuales debe ser siempre el in-orden:

Reconstrucción con In-orden + Pre-orden:
→ El In-orden se coloca horizontalmente
→ El Pre-orden se coloca verticalmente de arriba a abajo (tal cual)
→ Las intersecciones determinan la posición de cada nodo

Reconstrucción con In-orden + Post-orden:
→ El In-orden se coloca horizontalmente
→ El Post-orden se coloca en ORDEN INVERSO verticalmente (de arriba a abajo)
→ Las intersecciones determinan la posición de cada nodo

⚠️ Dato clave: Siempre se necesita el in-orden. Con pre-orden o post-orden solos no es posible reconstruir el árbol de forma unívoca.

Tipos de búsqueda en árboles

🧪 TEST — BLOQUE 4: Árboles

16. ¿Cómo se denomina el nodo que no tiene hijos en un árbol?

• a) Nodo raíz
• b) Nodo rama
• c) Nodo hoja
• d) Nodo hermano

17. En un árbol, ¿cuál es el nivel de la raíz?

• a) 0
• b) 1
• c) Depende del número de nodos
• d) El nivel más alto del árbol

18. En el recorrido in-orden de un árbol binario, ¿en qué posición se visita la raíz?

• a) Primero
• b) En medio (entre los dos subárboles)
• c) Al final
• d) Solo si tiene dos hijos

19. Para reconstruir un árbol binario a partir de sus recorridos, ¿qué recorrido es imprescindible tener siempre?

• a) Pre-orden
• b) Post-orden
• c) In-orden
• d) Cualquiera de los tres

20. ¿Cómo se coloca el Post-orden al reconstruir un árbol junto con el In-orden?

• a) Tal cual, de arriba a abajo en el eje vertical
• b) En orden inverso al escrito, de arriba a abajo en el eje vertical
• c) De izquierda a derecha en el eje horizontal
• d) Empezando desde las hojas hacia la raíz

21. Un árbol binario perfecto se caracteriza por:

• a) Que todos los nodos tienen exactamente 2 hijos
• b) Que es un árbol lleno y todas las hojas están en el mismo nivel
• c) Que tiene el mínimo número posible de nodos para su altura
• d) Que todos los nodos tienen 0 o 1 hijo

BLOQUE 5 — TIPOS DE PDF

Variantes del formato PDF

Todos los tipos de PDF se basan en estándares de la ISO (Organización Internacional de Normalización).

Variantes del formato PDF
├── PDF/A  → Archivado a largo plazo
├── PDF/UA → Accesibilidad Universal
├── PDF/X  → Preimpresión e intercambio gráfico
├── PDF/VT → Impresión de datos variables y transaccional
├── PDF/H  → Industria sanitaria
├── PDF/E  → Documentación técnica e ingeniería
└── PDF con capacidad de búsqueda → resultado de OCR

Descripción de cada variante

PDF/A — Variantes

⚠️ Requisitos PDF/A: los recursos deben estar integrados en el documento y los metadatos en formato XMP.

PDF/E — Características especiales

🧪 TEST — BLOQUE 5: Tipos de PDF

22. ¿Qué tipo de PDF está diseñado para el archivado a largo plazo de documentos?

• a) PDF/X
• b) PDF/E
• c) PDF/A
• d) PDF/VT

23. ¿Qué significa la UA en PDF/UA?

• a) Universal Archive
• b) Universal Accessibility (Accesibilidad Universal)
• c) Unified Architecture
• d) User Application

24. El formato PDF/X fue desarrollado en 2001 para:

• a) El archivado de documentos médicos
• b) La impresión de datos variables
• c) El intercambio de documentos en preimpresión, garantizando la fidelidad del color y las fuentes
• d) La accesibilidad de personas con discapacidad

25. ¿Cuál de las siguientes variantes de PDF no es un estándar oficial de la ISO?

• a) PDF/A
• b) PDF/X
• c) PDF/H
• d) PDF/UA

26. Un PDF con capacidad de búsqueda es el resultado de aplicar:

• a) Compresión ZIP al documento original
• b) OCR (Reconocimiento Óptico de Caracteres) a un documento escaneado
• c) Cifrado AES al documento
• d) Conversión desde formato Word

27. El formato PDF/E es especialmente adecuado para:

• a) Facturas electrónicas y documentos transaccionales
• b) Documentos médicos y registros de pacientes
• c) Documentación técnica de ingeniería con soporte de modelos 3D
• d) Publicaciones periódicas y revistas digitales

✅ SOLUCIONES COMENTADAS

1 → c) El orden de eficiencia de menor a mayor coste es: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!). O(log n) es la segunda más eficiente, solo superada por O(1) que es constante independientemente del tamaño.

2 → b) La búsqueda binaria tiene complejidad O(log n) porque en cada paso descarta la mitad de los elementos restantes. Si hay 1.000 elementos, en ~10 pasos (log₂ 1000 ≈ 10) encuentra el resultado.

3 → c) Los algoritmos básicos de ordenación (burbuja, inserción y selección) tienen complejidad O(n²): requieren comparar cada elemento con todos los demás. Para n=1000 elementos, realizan ~1.000.000 de operaciones.

4 → b) Mergesort tiene complejidad O(n log n) en todos los casos (mejor, medio y peor). Su recurrencia T(n) = 2T(n/2) + n se resuelve en O(n log n). Es uno de sus puntos fuertes frente a Quicksort.

5 → c) El peor caso de Quicksort es O(n²), que ocurre cuando el pivote elegido siempre es el mínimo o el máximo del subvector (vector ya ordenado o inversamente ordenado). En el caso promedio es O(n log n).

6 → c) Shellsort fue creado por Donald Shell en 1959 como mejora de la ordenación por inserción. Compara elementos separados por saltos de tamaño decreciente, obteniendo una complejidad O(n log²n) en lugar de O(n²).

7 → c) Mergesort es el único algoritmo de la lista que es estable y garantiza O(n log n) en todos los casos (mejor, medio y peor). Quicksort no es estable y tiene O(n²) en el peor caso; Heapsort no es estable.

8 → b) La inserción es eficiente con vectores casi ordenados porque cuando un elemento ya está cerca de su posición correcta, requiere muy pocos desplazamientos. En ese caso se aproxima a O(n).

9 → c) Timsort es una combinación de Mergesort + Ordenación por inserción. Es el algoritmo de ordenación utilizado en Python (list.sort()) y Java (Arrays.sort()). Aprovecha las ventajas de ambos.

10 → b) BFS (Búsqueda en Anchura) es el algoritmo adecuado para encontrar la ruta más corta en grafos no ponderados, ya que explora los nodos nivel a nivel y el primero en llegar al destino lo hace por el camino más corto.

11 → b) La diferencia clave es que Dijkstra no admite pesos negativos en las aristas (se comporta incorrectamente), mientras que Bellman-Ford sí los admite y además puede detectar ciclos negativos.

12 → c) Floyd-Warshall encuentra las rutas más cortas entre todos los pares de vértices del grafo. Su complejidad es O(V³). Dijkstra solo encuentra las rutas desde un único vértice origen.

13 → c) Los algoritmos de Prim y Kruskal se usan para encontrar el Árbol de Expansión Mínima (MST, Minimum Spanning Tree), que conecta todos los nodos con el coste total mínimo. Ambos funcionan en grafos no dirigidos y ponderados.

14 → c) Floyd-Warshall tiene complejidad O(V³) porque usa tres bucles anidados sobre todos los vértices. Es el más costoso de los algoritmos de rutas más cortas, pero el único que resuelve todos los pares a la vez.

15 → b) Prim y Kruskal solo se aplican a grafos no dirigidos y ponderados. Ambos buscan el MST, que solo tiene sentido en grafos no dirigidos con pesos que representan costes.

16 → c) El nodo hoja es aquel que no tiene hijos y siempre se encuentra en los extremos de la estructura del árbol. No confundir con nodo raíz (el primero) ni nodo rama (tiene al menos un hijo y no es la raíz).

17 → b) El nivel de la raíz es 1 (la primera generación). Un árbol vacío tiene 0 niveles. El nivel de cada nodo se calcula contando los nodos que hay sobre él hasta la raíz y sumando 1.

18 → b) En el recorrido in-orden el orden es: Izquierda → Raíz → Derecha. La raíz se visita en posición intermedia. Pre-orden: Raíz primero. Post-orden: Raíz al final.

19 → c) Para reconstruir un árbol binario de forma unívoca siempre es imprescindible el in-orden. Combinado con pre-orden o post-orden, permite determinar la estructura completa del árbol.

20 → b) Al reconstruir con In-orden + Post-orden, el Post-orden se coloca en orden inverso al escrito, de arriba a abajo en el eje vertical. Si el post-orden es A-C-F-J... se colocaría ..J-F-C-A de arriba a abajo.

21 → b) Un árbol binario perfecto es aquel que es lleno (todos los nodos tienen 0 o 2 hijos) Y además todas las hojas están en el mismo nivel. Un árbol lleno no tiene por qué ser perfecto si sus hojas están en niveles distintos.

22 → c) PDF/A (Archive) es el formato diseñado para el archivado de documentos a largo plazo. Basado en la norma ISO 19005-1, requiere que los recursos estén integrados y los metadatos en formato XMP.

23 → b) UA significa Universal Accessibility (Accesibilidad Universal). PDF/UA garantiza que cualquier persona, incluidas las que tienen discapacidades, pueda acceder y usar la información del documento.

24 → c) PDF/X fue desarrollado en 2001 específicamente para el intercambio de documentos en preimpresión (artes gráficas). La X significa "intercambio" y su objetivo es garantizar que el color y las fuentes se reproduzcan fielmente.

25 → c) PDF/H (Healthcare, 2008) para la industria sanitaria no es un estándar oficial de la ISO. Sienta las bases para la conversión de registros médicos a PDF, pero actualmente no está formalmente estandarizado.

26 → b) Un PDF con capacidad de búsqueda es el resultado de aplicar OCR (Optical Character Recognition, Reconocimiento Óptico de Caracteres) a un documento escaneado o imagen, convirtiendo las imágenes de texto en texto seleccionable y buscable.

27 → c) PDF/E (Engineering) fue desarrollado para documentación técnica de ingeniería, siendo especialmente adecuado para planos de construcción y dibujos con modelos 3D que se pueden expandir o rotar dentro del propio archivo.

📊 TABLA FLASH FINAL — Datos clave Algoritmos, Árboles y PDF