TEMARIO: ALGORITMOS Y ESTRUCTURAS DE DATOS (EDA 2)
---
1. ALGORITMOS DE ORDENAMIENTO
---
Concepto: Organizar elementos en un orden específico.
Importancia: Eficiencia en búsqueda, preprocesamiento para otros algoritmos, análisis de
datos, comprensión de complejidad.
Conceptos Clave:
- Comparación: Base de muchos algoritmos.
- Estabilidad: Mantiene orden relativo de elementos iguales.
- In-place: No requiere memoria adicional significativa (O(1) extra).
- Out-of-place: Requiere memoria adicional.
- Complejidad Temporal (Peor, Promedio, Mejor Caso):
- O(n^2): Bubble Sort, Insertion Sort, Selection Sort. Para N pequeños o listas casi
ordenadas (Insertion).
- O(n log n): Merge Sort, Quick Sort, Heap Sort. Eficientes para N grandes.
- Complejidad Espacial: Memoria adicional usada.
Algoritmos Principales:
* Bubble Sort: Compara e intercambia pares adyacentes. O(n^2) general, O(n) mejor.
Estable. In-place. Didáctico.
* Selection Sort: Encuentra el mínimo/máximo y lo coloca. O(n^2) siempre. No estable.
In-place. Minimiza swaps.
* Insertion Sort: Inserta elementos uno por uno en la parte ordenada. O(n^2) general, O(n)
mejor (casi ordenado). Estable. In-place. Eficiente para N pequeños.
* Merge Sort: Divide y vencerás. Divide, ordena sub-listas, mezcla. O(n log n) siempre.
Estable. Out-of-place (O(n) espacio). Fiable, bueno para ordenamiento externo.
* Quick Sort: Divide y vencerás. Elige pivote, particiona, ordena recursivamente. O(n log n)
promedio, O(n^2) peor (mitigable con buena elección de pivote). No estable. Espacio O(log
n) promedio (pila recursión). Muy rápido en promedio.
* Heap Sort: Usa estructura Max-Heap. Construye heap, extrae máximo repetidamente. O(n
log n) siempre. No estable. In-place (O(1) espacio).
* Counting Sort: Para enteros en rango [0, k]. Cuenta frecuencias. O(n+k) tiempo, O(k)
espacio. Estable.
* Radix Sort: Ordena por dígitos/caracteres usando un ordenamiento estable (como
Counting Sort). O(d(n+k)) tiempo. Estable.
* Bucket Sort: Distribuye en cubetas, ordena cubetas, concatena. O(n+k) promedio si
distribución uniforme.
---
2. ALGORITMOS DE BÚSQUEDA
---
Concepto: Encontrar un elemento en una colección.
Importancia: Recuperación de información, validación.
Algoritmos Principales:
* Búsqueda Lineal (Secuencial): Recorre uno por uno. O(n) tiempo. Para datos no
ordenados o pequeños.
* Búsqueda Binaria: Divide y vencerás. REQUIERE DATOS ORDENADOS. O(log n) tiempo.
Muy eficiente.
* Tablas Hash (Hashing):
- Mecanismo: Función hash mapea clave a índice de arreglo.
- Componentes: Función hash, tabla hash, manejo de colisiones (encadenamiento o
direccionamiento abierto).
- Complejidad: O(1) promedio para búsqueda, inserción, borrado. O(n) peor caso.
- Uso: Diccionarios, conjuntos. No mantiene orden.
* Búsquedas en Árboles (ver tema 4): BST (O(log n) promedio), árboles balanceados (AVL,
Rojo-Negro) garantizan O(log n).
---
3. ALGORITMOS DE GRAFOS
---
Concepto: Grafos (V, E) modelan relaciones entre entidades (vértices) mediante conexiones
(aristas).
Importancia: Modelado de redes, optimización de rutas/flujos.
Conceptos Clave:
- Representación:
- Matriz de Adyacencia: VxV. O(V^2) espacio. Rápido para chequear arista. Para grafos
densos.
- Lista de Adyacencia: Arreglo de listas de vecinos. O(V+E) espacio. Para grafos
dispersos.
- Tipos: Dirigidos/No dirigidos, Ponderados/No ponderados.
- Recorridos:
- BFS (Búsqueda en Amplitud): Explora por niveles usando una COLA. O(V+E). Camino
más corto (no ponderado), componentes conexas.
- DFS (Búsqueda en Profundidad): Explora ramas a fondo usando una PILA (o recursión).
O(V+E). Detección de ciclos, ordenamiento topológico, componentes (fuertemente)
conexas.
- Caminos Mínimos (Ponderados):
- Dijkstra: Desde un nodo fuente, pesos NO NEGATIVOS. Voraz, usa cola de prioridad.
O((V+E)logV) o O(E+VlogV).
- Bellman-Ford: Desde un nodo fuente, permite pesos NEGATIVOS, detecta ciclos
negativos. O(VE).
- Floyd-Warshall: Todos los pares de caminos mínimos. Programación dinámica. O(V^3).
- Árbol de Expansión Mínima (MST) (No dirigidos, ponderados, conexos): Conectar todos
los nodos con coste mínimo.
- Kruskal: Ordena aristas, añade si no forma ciclo (usa Union-Find). O(E log E).
- Prim: Crece el MST desde un nodo, añadiendo arista más barata a nodo fuera del MST.
O(E log V).
---
4. ÁRBOLES
---
Concepto: Grafo acíclico y conectado. Estructura jerárquica.
Importancia: Representación jerárquica, búsquedas eficientes.
Conceptos Clave:
- Terminología: Raíz, nodo, hoja, padre, hijo, profundidad, altura.
- Árboles Binarios: Máximo 2 hijos por nodo.
- Recorridos: Preorden (Raíz,Izq,Der), Inorden (Izq,Raíz,Der), Postorden (Izq,Der,Raíz).
- Árboles Binarios de Búsqueda (BST): Izq < Raíz < Der. Búsqueda, inserción, borrado O(h).
Promedio O(log n), peor O(n).
- Árboles Balanceados (para garantizar O(log n) altura):
- AVL: Auto-balanceo con rotaciones (diferencia de alturas de subárboles max 1).
- Rojo-Negro: Propiedades de color para balanceo.
- Heaps (Montículos): Árbol binario (casi) completo.
- Min-Heap: Nodo <= hijos. Raíz es mínimo.
- Max-Heap: Nodo >= hijos. Raíz es máximo.
- Uso: Colas de prioridad, Heap Sort. Operaciones O(log n), construir O(n).
- B-Trees (y B+ Trees): Para discos. Muchos hijos por nodo. Altura baja. Bases de datos.
- Tries (Árboles de Prefijos): Búsqueda de cadenas, autocompletado.
---
5. ARCHIVOS
---
Concepto: Gestión de datos persistentes.
Importancia: Guardar/recuperar datos, I/O.
Conceptos Clave:
- Tipos: Texto (legible, caracteres, ej. config, logs) vs. Binarios (bytes, compacto, eficiente,
ej. imágenes, objetos serializados).
- Operaciones: Abrir (modos: 'r' leer, 'w' escribir, 'a' añadir, 'b' binario), cerrar (crucial), leer,
escribir, buscar (seek).
- Manejo de Errores: EOF, permisos.
- Buffering: Mejora eficiencia de I/O.
- Serialización/Deserialización: Convertir objetos a formato almacenable (JSON, XML,
binario) y viceversa.
- Acceso: Secuencial (en orden) vs. Aleatorio (saltar a posiciones).
---
6. INTRODUCCIÓN A LOS ALGORITMOS PARALELOS
---
Concepto: Diseñar algoritmos para ejecución simultánea en múltiples unidades de
procesamiento.
Importancia: Rendimiento, escalabilidad, aprovechar hardware multinúcleo.
Conceptos Clave:
- Modelos:
- Memoria Compartida: Threads acceden a memoria común (OpenMP). Requiere
Sincronización.
- Memoria Distribuida: Procesos con memoria propia, se comunican por mensajes (MPI).
- Métricas:
- Speedup: TiempoSecuencial / TiempoParalelo.
- Eficiencia: Speedup / NumProcesadores.
- Ley de Amdahl: Límite de speedup basado en fracción secuencial. $1 / ((1-P) + P/N)$.
Si $N \to \infty$, speedup $\to 1/(1-P)$.
- Desafíos:
- Condiciones de Carrera (Race conditions).
- Bloqueos Mutuos (Deadlocks).
- Sincronización: Mutex, semáforos, barreras.
- Balanceo de Carga.
- Overhead de Comunicación.
- Patrones: MapReduce, Fork-Join.
---
TEMARIO: PROGRAMACIÓN ORIENTADA A OBJETOS (POO)
---
---
1. EL PARADIGMA ORIENTADO A OBJETOS (POO)
---
Core Idea: Organizar código alrededor de "objetos" (instancias de clases) que agrupan
datos (atributos) y comportamientos (métodos).
Importancia: Modularidad, reusabilidad, mantenibilidad, escalabilidad.
Principios Fundamentales (Pilares):
* Encapsulamiento:
- Concepto: Agrupar datos y métodos, ocultar estado interno y exponer interfaz pública.
- Beneficios: Protección de datos, reduce complejidad, facilita modificaciones internas.
- Mecanismos: Modificadores de acceso (public, private, protected).
* Abstracción:
- Concepto: Enfocarse en características esenciales, ignorar detalles irrelevantes. "Qué
hace" vs. "cómo lo hace".
- Beneficios: Simplifica interacción, modelado natural.
* Herencia:
- Concepto: Subclase hereda atributos/métodos de superclase. Relación "es un".
- Beneficios: Reutilización de código, jerarquías, extensibilidad.
- Conceptos: Sobrescritura (override), super.
* Polimorfismo:
- Concepto: "Muchas formas". Objetos de diferentes clases responden al mismo mensaje
de forma específica.
- Beneficios: Código genérico y flexible.
- Tipos: De Subtipo (más común, herencia + override + enlace dinámico), Paramétrico
(genéricos), Ad-hoc (sobrecarga).
---
2. UML (UNIFIED MODELING LANGUAGE)
---
Core Idea: Lenguaje gráfico estandarizado para visualizar, especificar, construir y
documentar sistemas de software.
Importancia: Comunicación, diseño, documentación.
Diagramas Clave:
* Estructurales (estructura estática):
- Diagrama de Clases: Clases, atributos, métodos, relaciones (asociación, agregación,
composición, herencia). Fundamental en POO.
- Diagrama de Objetos: Instancias y sus relaciones en un momento.
- Diagrama de Componentes: Organización y dependencias de componentes software.
- Diagrama de Despliegue: Configuración física de hardware y software.
* De Comportamiento (comportamiento dinámico):
- Diagrama de Casos de Uso: Funcionalidad desde perspectiva del usuario (actores).
- Diagrama de Secuencia: Interacción entre objetos ordenada en el tiempo (énfasis en
orden de mensajes).
- Diagrama de Actividad: Flujos de trabajo o procesos (similar a diagrama de flujo).
- Diagrama de Estados: Estados de un objeto y transiciones.
Relaciones (Diagrama de Clases):
- Asociación: Relación estructural ("trabaja para").
- Agregación: "Tiene un", partes pueden existir independientemente (rombo hueco).
- Composición: "Tiene un", partes NO pueden existir sin el todo (rombo relleno).
- Herencia/Generalización: "Es un tipo de" (flecha triangular hueca).
- Dependencia: Un cambio en una afecta a otra (flecha discontinua).
- Realización: Clase implementa interfaz (flecha discontinua triangular hueca).
---
3. TIPOS, EXPRESIONES Y CONTROL DE FLUJO
---
Core Idea: Bloques de construcción de programas.
Importancia: Base de la lógica de programación.
Tipos de Datos:
- Primitivos (int, float, char, boolean): Tamaño fijo, manipulación directa.
- De Referencia (Objetos): Dirección de memoria del objeto.
- Estático (Java, C++): Tipos conocidos en compilación. Detección temprana de errores.
- Dinámico (Python, JS): Tipos verificados en ejecución. Más flexible.
- Fuerte (Java, Python): Restricciones estrictas de mezcla de tipos.
- Débil (C, JS a veces): Conversiones implícitas laxas.
Expresiones: Combinación de literales, variables, operadores, llamadas a función, que
evalúan a un valor.
- Operadores: Aritméticos, Relacionales, Lógicos, Asignación, Bit a bit.
- Precedencia y Asociatividad: Orden de evaluación.
Control de Flujo: Orden de ejecución de instrucciones.
- Secuencial.
- Condicional: if-else if-else, switch.
- Iterativo (Bucles): for, while, do-while.
- Salto: break, continue, return.
---
4. HERENCIA Y POLIMORFISMO
---
(Refuerzo de los pilares de POO)
Herencia:
- "Es un". Reutilización. Extensibilidad.
- Constructores: Subclase llama a constructor de superclase (super()).
- Modificadores: protected para acceso de subclases.
- Clases Abstractas: No instanciables, pueden tener métodos abstractos (a implementar por
subclases) y concretos. Plantilla.
- Interfaces: Contrato de métodos abstractos públicos. Una clase implementa interfaz(ces).
Polimorfismo (de Subtipo):
- Objeto de subclase tratado como de superclase.
- Enlace Dinámico (Late Binding): Decisión de qué método (sobrescrito) ejecutar se toma en
tiempo de ejecución.
- Beneficio: Código genérico, reduce if/else basados en tipo.
---
5. MANEJO DE EXCEPCIONES Y ERRORES
---
Core Idea: Manejar condiciones anómalas sin que el programa termine abruptamente.
Importancia: Robustez, fiabilidad, separación de lógica de error.
Conceptos:
- Excepción: Evento que interrumpe flujo normal. Objeto con info del error.
- Lanzar (Throw/Raise): Crear y "lanzar" excepción.
- Capturar (Catch): Bloques try-catch para manejar tipos específicos.
- try: Código que podría generar excepción.
- catch: Se ejecuta si excepción del tipo especificado ocurre en try.
- finally: Se ejecuta siempre (haya o no excepción). Para liberar recursos (cerrar
archivos).
- Jerarquía de Excepciones: Permite capturar de forma general o específica.
- Excepciones Verificadas (Java): Compilador obliga a manejarlas (errores
recuperables/esperados).
- Excepciones No Verificadas (Runtime): No obligatorio manejarlas (errores de
programación).
- Propagación: Si no se captura, sube en pila de llamadas.
---
6. FLUJO DE ENTRADA Y SALIDA (I/O STREAMS)
---
Core Idea: Abstracción para leer de fuente (input stream) y escribir a destino (output
stream).
Importancia: Interacción con exterior, leer/guardar datos.
Conceptos:
- Stream (Flujo): Secuencia de datos (bytes o caracteres).
- Input Stream (lectura), Output Stream (escritura).
- Fuentes/Destinos: Archivos, consola, red, memoria.
- Clases Envoltorio (Wrapper/Decorator): Añaden funcionalidad.
- BufferedInputStream/Reader: Buffer para eficiencia.
- DataInputStream/OutputStream: Tipos primitivos en binario.
- ObjectInputStream/OutputStream: Serialización de objetos.
- InputStreamReader/OutputStreamWriter: Puente bytes <-> caracteres (manejan
codificación).
- Codificación de Caracteres: ASCII, UTF-8.
- Manejo de Recursos: CRUCIAL cerrar streams (try-with-resources o finally).
- flush(): Forzar escritura de buffer.
---
7. PROGRAMACIÓN DE HILOS (THREADS)
---
Core Idea: Unidad más pequeña de ejecución planificable. Múltiples hilos en un proceso
comparten memoria.
Importancia: Responsividad UI, rendimiento (multicore), servidores.
Conceptos:
- Proceso (programa en ejecución, memoria propia) vs. Hilo (secuencia en proceso,
comparte memoria).
- Creación/Gestión: start(), join(), sleep(), interrupt().
- Ciclo de Vida: Nuevo, Ejecutable, Bloqueado, Terminado.
- Compartición de Datos y Sincronización:
- Riesgos: Condiciones de Carrera, Interbloqueos (Deadlocks).
- Secciones Críticas: Código que accede a recursos compartidos.
- Mecanismos de Sincronización (Java):
- synchronized (monitores/locks implícitos).
- Locks explícitos (ReentrantLock).
- Semáforos.
- Variables de Condición.
- Variables Atómicas.
- Pool de Hilos: Reutilizar hilos para evitar overhead de creación/destrucción.
---
8. INTRODUCCIÓN A PATRONES (DE DISEÑO)
---
Core Idea: Soluciones probadas, generales, reutilizables a problemas comunes de diseño
de software.
Importancia: Lenguaje común, soluciones probadas, flexibilidad, mantenibilidad.
Patrones "Más Importantes" Resumidos:
* Creacionales:
- Singleton: Una única instancia, acceso global. (Ej: config, logger).
- Factory Method: Interfaz para crear objetos, subclases deciden qué instanciar.
Flexibilidad en creación.
* Estructurales:
- Adapter: Interfaces incompatibles trabajan juntas. Reutilización.
- Decorator: Añade responsabilidades dinámicamente. Extensión flexible.
- Facade: Interfaz simplificada a subsistema complejo. Reduce acoplamiento.
* De Comportamiento:
- Observer: Dependencia uno-a-muchos para notificaciones automáticas. (Ej: UI,
eventos).
- Strategy: Familia de algoritmos intercambiables. Flexibilidad en comportamiento.
- Command: Encapsula solicitud como objeto. (Ej: undo, colas de tareas).
