Este repositorio documenta e implementa los conceptos fundamentales de Algoritmos y Estructuras de Datos (AED), cubriendo desde fundamentos y programación modular hasta estructuras estáticas, dinámicas y externas, así como técnicas algorítmicas avanzadas, complejidad, fórmulas de análisis y eficiencia.
- Fundamentos de Programación y Estructuras de Control
1.1 Concepto de Algoritmo
1.2 Estructura de un Programa - Programación Modular y Abstracción de Datos
2.1 Modularización
2.2 Tipos Abstractos de Datos (TAD) - Estructuras de Datos Estáticas
- Estructuras de Datos Dinámicas
- Estructuras de Datos Externas (Archivos)
- Técnicas Algorítmicas Avanzadas
6.1 Recursión y Backtracking
6.2 Ordenamiento
6.3 Búsqueda - Clasificación de Estructuras de Datos
- Complejidad y Eficiencia
Los programas se componen de datos e instrucciones, y la resolución de un problema requiere:
- Estratégico: Comprender el objetivo.
- Metodológico: Determinar los pasos y la lógica de resolución.
- Herramental: Elegir la representación de los pasos (pseudocódigo, diagramas, flujo).
Un algoritmo es un conjunto finito de acciones ordenadas que produce un resultado específico en tiempo limitado y sin ambigüedad.
Propiedades:
| Concepto | Descripción |
|---|---|
| Correcto | Cumple la especificación y finaliza correctamente. |
| Eficiente | Optimiza tiempo y espacio. |
| Claro | Lógica comprensible y documentada. |
| Confiable | Garantiza resultados válidos bajo condiciones definidas. |
| Mantenible | Permite modificaciones sin romper la integridad. |
- Cabecera: Nombre del programa.
- Declaraciones: Constantes, variables, tipos, subprogramas.
- Cuerpo Principal: Secuencia de instrucciones.
- Localidad: Locales y globales.
- Constantes: Valores fijos.
- Operaciones: Asignación, lectura y escritura.
| Estructura | Mecánica |
|---|---|
| Secuencial | Orden lineal. |
| Decisión Simple | Evalúa condición; ejecuta si es verdadera. |
| Decisión Condicional | Rama verdadera o falsa. |
| Decisión Múltiple | Varias opciones; ejecuta la primera que coincide. |
| Repetición Fija | Itera n veces. |
| Repetición Condicional (Pre) | Evalúa antes de ejecutar; puede no ejecutarse. |
| Repetición Condicional (Post) | Ejecuta primero, luego evalúa; al menos una ejecución. |
- Contadores y Acumuladores: Variables que suman o contabilizan valores.
- Subprogramas: Funciones (retornan valor) y procedimientos.
- Alcance de Variables: Locales (temporales) y globales (persistentes).
- Pasaje de Parámetros: Por valor o referencia.
Un TAD incluye:
- Interfaz Pública: Qué operaciones se pueden hacer y con qué parámetros.
- Operaciones Fundamentales: Creación, modificación, consulta.
- Registros: Colecciones heterogéneas de campos.
- Vectores: Elementos homogéneos accesibles por índice
icon1 ≤ i ≤ n. - Matrices: Bidimensionales, accesibles mediante
(i, j)con1 ≤ i ≤ filas,1 ≤ j ≤ columnas.
Tamaño de matriz: |M| = filas × columnas
- Punteros: Contienen dirección de memoria de otra variable.
- Listas Encadenadas: Nodos con dato + puntero al siguiente.
- Listas Especiales: Doblemente encadenadas, circulares.
- Pilas y Colas: LIFO y FIFO respectivamente.
Complejidad Temporal Básica:
| Operación | Lista Simple | Lista Doble | Pila/Cola |
|---|---|---|---|
| Inserción | O(1) cabeza / O(n) posición | O(1) | O(1) |
| Eliminación | O(1) cabeza / O(n) posición | O(1) | O(1) |
| Acceso | O(n) | O(n) | O(1) |
- Apertura, Lectura y Grabado: Manejo de registros con punteros.
- Acceso Directo vs Secuencial: Organización de Archivos Directos (AOD) permite inserciones sin reescritura completa.
Posición de registro i: Pos = inicio + (i-1) × tamañoRegistro
- Recursión: Resolución de un problema mediante subproblemas más pequeños.
- Caso Base: Detiene la recursión.
- Pila de Ejecución: Registros de Activación apilados.
- Backtracking: Retroceso sistemático para explorar todas las soluciones posibles.
Complejidad Recursiva:
Si T(n) es el tiempo de un algoritmo recursivo, frecuentemente se expresa como:
T(n) = a T(n/b) + f(n)(División y Conquista)- Método maestro:
T(n) ∈ O(n^log_b(a))(sif(n)es polinómica y menor quen^log_b(a))
| Método | Complejidad Temporal | Complejidad Espacial |
|---|---|---|
| Burbuja | O(n²) | O(1) |
| Inserción | O(n²) | O(1) |
| Selección | O(n²) | O(1) |
| Mezcla | O(n log n) | O(n) |
| Rápido | O(n log n) promedio, O(n²) peor caso | O(log n) recursivo |
| Método | Complejidad Temporal |
|---|---|
| Secuencial | O(n) |
| Binaria | O(log n) |
| Indexada | O(1) acceso directo |
Fórmulas:
- Promedio de búsqueda secuencial:
T_avg = (n+1)/2comparaciones. - Búsqueda binaria:
T_max = log2(n)comparaciones.
| Criterio | Tipos | Descripción |
|---|---|---|
| Residencia/Permanencia | Internas / Externas | RAM temporal o archivos permanentes. |
| Uso de Memoria | Estáticas / Dinámicas | Tamaño fijo vs tamaño variable. |
| Tipo de Datos | Homogéneas / Heterogéneas | Igual tipo o combinación de tipos. |
- Tiempo de Ejecución: Número de operaciones.
- Uso de Memoria: Dependencia de la estructura y el algoritmo.
- Escalabilidad: Capacidad de manejar grandes volúmenes de datos.
- O(f(n)): Cota superior (peor caso)
- Ω(f(n)): Cota inferior (mejor caso)
- Θ(f(n)): Cota ajustada (caso promedio)
- Suma de n elementos:
S = Σ_{i=1}^{n} i = n(n+1)/2 - Factorial:
n! = Π_{i=1}^{n} i - Complejidad recursiva divide y vencerás:
T(n) = a T(n/b) + f(n)