Introducció
En aquest tema, explorarem dos conceptes fonamentals en la resolució d'algorismes complexos: la recursió i la programació dinàmica. Aquests mètodes són essencials per abordar problemes que poden ser descompostos en subproblemes més petits i sovint es solapen.
Objectius del Tema
- Comprendre els conceptes bàsics de la recursió.
- Aprendre a identificar problemes que es poden resoldre amb recursió.
- Introduir la programació dinàmica com una tècnica per optimitzar algorismes recursius.
- Aplicar la programació dinàmica a problemes clàssics.
Recursió
Conceptes Bàsics
La recursió és una tècnica en la qual una funció es crida a si mateixa per resoldre subproblemes més petits del problema original. Els elements clau de la recursió són:
- Cas Base: La condició que atura la recursió.
- Cas Recursiu: La part de la funció que inclou la crida recursiva.
Exemple: Factorial d'un Nombre
El factorial d'un nombre n (denotat com n!) és el producte de tots els nombres enters positius fins a n.
Implementació Recursiva
Exercici 1: Implementar la Funció Fibonacci Recursiva
Implementa una funció recursiva per calcular el n-èssim nombre de Fibonacci. Els nombres de Fibonacci es defineixen com:
F(0) = 0F(1) = 1F(n) = F(n-1) + F(n-2)per an > 1
def fibonacci(n):
if n == 0:
return 0 # Cas Base
elif n == 1:
return 1 # Cas Base
else:
return fibonacci(n - 1) + fibonacci(n - 2) # Cas RecursiuSolució de l'Exercici 1
def fibonacci(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fibonacci(n - 1) + fibonacci(n - 2)Programació Dinàmica
Conceptes Bàsics
La programació dinàmica (PD) és una tècnica d'optimització que es basa en descompondre un problema en subproblemes més petits i emmagatzemar els resultats dels subproblemes per evitar càlculs repetits. Hi ha dues tècniques principals:
- Memorització (Top-Down): Emmagatzemar els resultats de subproblemes en una estructura de dades (com un diccionari) per reutilitzar-los.
- Tabulació (Bottom-Up): Construir una taula que emmagatzema els resultats dels subproblemes de manera iterativa.
Exemple: Fibonacci amb Memorització
Implementació amb Memorització
def fibonacci_memo(n, memo={}):
if n in memo:
return memo[n]
if n == 0:
return 0
elif n == 1:
return 1
else:
memo[n] = fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo)
return memo[n]Exemple: Fibonacci amb Tabulació
Implementació amb Tabulació
def fibonacci_tab(n):
if n == 0:
return 0
elif n == 1:
return 1
fib_table = [0] * (n + 1)
fib_table[1] = 1
for i in range(2, n + 1):
fib_table[i] = fib_table[i - 1] + fib_table[i - 2]
return fib_table[n]Exercici 2: Implementar la Solució de la Mochila amb Programació Dinàmica
El problema de la mochila consisteix en seleccionar un conjunt d'objectes amb un pes i un valor determinats per maximitzar el valor total sense excedir un pes màxim.
Implementació
def knapsack(weights, values, W):
n = len(weights)
dp = [[0 for x in range(W + 1)] for y in range(n + 1)]
for i in range(n + 1):
for w in range(W + 1):
if i == 0 or w == 0:
dp[i][w] = 0
elif weights[i - 1] <= w:
dp[i][w] = max(values[i - 1] + dp[i - 1][w - weights[i - 1]], dp[i - 1][w])
else:
dp[i][w] = dp[i - 1][w]
return dp[n][W]Solució de l'Exercici 2
def knapsack(weights, values, W):
n = len(weights)
dp = [[0 for x in range(W + 1)] for y in range(n + 1)]
for i in range(n + 1):
for w in range(W + 1):
if i == 0 or w == 0:
dp[i][w] = 0
elif weights[i - 1] <= w:
dp[i][w] = max(values[i - 1] + dp[i - 1][w - weights[i - 1]], dp[i - 1][w])
else:
dp[i][w] = dp[i - 1][w]
return dp[n][W]Resum
En aquesta secció, hem après els conceptes bàsics de la recursió i la programació dinàmica. Hem vist com la recursió pot ser utilitzada per descompondre problemes en subproblemes més petits i com la programació dinàmica pot optimitzar aquests algorismes recursius mitjançant la memorització i la tabulació. Hem aplicat aquests conceptes a problemes clàssics com el càlcul de nombres de Fibonacci i el problema de la mochila.
Algoritmes Avançats
Mòdul 1: Introducció als Algoritmes Avançats
Mòdul 2: Algoritmes d'Optimització
- Programació Lineal
- Algoritmes d'Optimització Combinatòria
- Algoritmes Genètics
- Optimització de Colònia de Formigues
Mòdul 3: Algoritmes en Grafs
- Representació de Grafs
- Cerca en Grafs: BFS i DFS
- Algoritmes de Camins Mínims
- Algoritmes de Flux Màxim
- Algoritmes d'Aparellament en Grafs
Mòdul 4: Algoritmes de Cerca i Ordenació
Mòdul 5: Algoritmes d'Aprenentatge Automàtic
- Introducció a l'Aprenentatge Automàtic
- Algoritmes de Classificació
- Algoritmes de Regressió
- Xarxes Neuronals i Deep Learning
- Algoritmes de Clustering
Mòdul 6: Casos d'Estudi i Aplicacions
- Optimització en la Indústria
- Aplicacions de Grafs en Xarxes Socials
- Cerca i Ordenació en Grans Volums de Dades
- Aplicacions d'Aprenentatge Automàtic en la Vida Real