Introducción
En este tema, exploraremos dos técnicas algorítmicas fundamentales: la recursión y la programación dinámica. Ambas son herramientas poderosas para resolver problemas complejos de manera eficiente.
Objetivos
- Comprender el concepto de recursión y cómo se utiliza en algoritmos.
- Aprender a identificar problemas que pueden ser resueltos mediante recursión.
- Introducir la programación dinámica como una mejora a la recursión para optimizar el rendimiento.
- Aplicar la programación dinámica a problemas clásicos.
Conceptos Básicos de Recursión
¿Qué es la Recursión?
La recursión es una técnica en la que una función se llama a sí misma para resolver subproblemas más pequeños del problema original. Es especialmente útil para problemas que pueden ser divididos en subproblemas similares.
Ejemplo de Recursión: Factorial de un Número
El factorial de un número \( n \) (denotado como \( n! \)) es el producto de todos los números enteros positivos menores o iguales a \( n \).
Definición Matemática
\[ n! = \begin{cases}
1 & \text{si } n = 0
n \times (n-1)! & \text{si } n > 0
\end{cases} \]
Implementación en Python
def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n - 1)
# Ejemplo de uso
print(factorial(5)) # Salida: 120Ejercicio Práctico: Serie de Fibonacci
La serie de Fibonacci es una secuencia de números donde cada número es la suma de los dos anteriores, comenzando con 0 y 1.
Definición Matemática
\[ F(n) = \begin{cases}
0 & \text{si } n = 0
1 & \text{si } n = 1
F(n-1) + F(n-2) & \text{si } n > 1
\end{cases} \]
Implementación en Python
def fibonacci(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fibonacci(n - 1) + fibonacci(n - 2)
# Ejemplo de uso
print(fibonacci(6)) # Salida: 8Conceptos Básicos de Programación Dinámica
¿Qué es la Programación Dinámica?
La programación dinámica es una técnica de optimización que mejora la eficiencia de algoritmos recursivos almacenando los resultados de subproblemas ya resueltos (memoización) o construyendo soluciones de subproblemas más pequeños de manera iterativa (tabulación).
Ejemplo de Programación Dinámica: Factorial de un Número
Podemos optimizar el cálculo del factorial utilizando una tabla para almacenar los resultados intermedios.
Implementación en Python
def factorial_dp(n):
dp = [1] * (n + 1)
for i in range(2, n + 1):
dp[i] = i * dp[i - 1]
return dp[n]
# Ejemplo de uso
print(factorial_dp(5)) # Salida: 120Ejercicio Práctico: Serie de Fibonacci con Programación Dinámica
Podemos optimizar el cálculo de la serie de Fibonacci utilizando una tabla para almacenar los resultados intermedios.
Implementación en Python
def fibonacci_dp(n):
if n == 0:
return 0
elif n == 1:
return 1
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
# Ejemplo de uso
print(fibonacci_dp(6)) # Salida: 8Comparación entre Recursión y Programación Dinámica
| Aspecto | Recursión | Programación Dinámica |
|---|---|---|
| Complejidad Temporal | Exponencial en muchos casos | Polinómica o mejor |
| Uso de Memoria | Puede ser alto debido a la pila | Puede ser optimizado con tabulación |
| Facilidad de Implementación | Sencilla para problemas pequeños | Más compleja pero eficiente |
Ejercicios Adicionales
Ejercicio 1: Suma de Subconjuntos
Dado un conjunto de números y un número objetivo, determinar si existe un subconjunto cuya suma sea igual al número objetivo.
Implementación en Python
def subset_sum(nums, target):
n = len(nums)
dp = [[False] * (target + 1) for _ in range(n + 1)]
for i in range(n + 1):
dp[i][0] = True
for i in range(1, n + 1):
for j in range(1, target + 1):
if nums[i - 1] <= j:
dp[i][j] = dp[i - 1][j] or dp[i - 1][j - nums[i - 1]]
else:
dp[i][j] = dp[i - 1][j]
return dp[n][target]
# Ejemplo de uso
print(subset_sum([3, 34, 4, 12, 5, 2], 9)) # Salida: TrueEjercicio 2: Caminos en una Matriz
Dada una matriz \( m \times n \), contar el número de caminos posibles desde la esquina superior izquierda hasta la esquina inferior derecha, moviéndose solo hacia abajo o hacia la derecha.
Implementación en Python
def count_paths(m, n):
dp = [[1] * n for _ in range(m)]
for i in range(1, m):
for j in range(1, n):
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
return dp[m - 1][n - 1]
# Ejemplo de uso
print(count_paths(3, 3)) # Salida: 6Conclusión
En esta sección, hemos aprendido sobre la recursión y la programación dinámica, dos técnicas fundamentales para resolver problemas algorítmicos complejos. La recursión nos permite dividir un problema en subproblemas más pequeños, mientras que la programación dinámica optimiza este proceso almacenando resultados intermedios. Con estos conceptos, estamos mejor preparados para abordar problemas más avanzados en los siguientes módulos del curso.
Algoritmos Avanzados
Módulo 1: Introducción a los Algoritmos Avanzados
Módulo 2: Algoritmos de Optimización
- Programación Lineal
- Algoritmos de Optimización Combinatoria
- Algoritmos Genéticos
- Optimización de Colonia de Hormigas
Módulo 3: Algoritmos en Grafos
- Representación de Grafos
- Búsqueda en Grafos: BFS y DFS
- Algoritmos de Caminos Mínimos
- Algoritmos de Flujo Máximo
- Algoritmos de Emparejamiento en Grafos
Módulo 4: Algoritmos de Búsqueda y Ordenación
Módulo 5: Algoritmos de Aprendizaje Automático
- Introducción al Aprendizaje Automático
- Algoritmos de Clasificación
- Algoritmos de Regresión
- Redes Neuronales y Deep Learning
- Algoritmos de Clustering
Módulo 6: Casos de Estudio y Aplicaciones
- Optimización en la Industria
- Aplicaciones de Grafos en Redes Sociales
- Búsqueda y Ordenación en Grandes Volúmenes de Datos
- Aplicaciones de Aprendizaje Automático en la Vida Real