En esta sección, los estudiantes tendrán la oportunidad de aplicar todos los conceptos aprendidos a lo largo del curso en proyectos integrales. Estos proyectos están diseñados para desafiar sus habilidades en análisis y diseño de algoritmos, así como en la optimización del rendimiento del código. Cada proyecto incluye una descripción detallada, requisitos específicos y sugerencias para la implementación.
Proyecto 1: Sistema de Recomendación de Libros
Descripción
Desarrolla un sistema de recomendación de libros basado en las preferencias de los usuarios. El sistema debe ser capaz de analizar las calificaciones de los libros proporcionadas por los usuarios y recomendar libros que puedan ser de su interés.
Requisitos
- Entrada de Datos: Una lista de usuarios y sus calificaciones para una serie de libros.
- Algoritmo de Recomendación: Implementar un algoritmo de recomendación, como filtrado colaborativo.
- Optimización: Mejorar la eficiencia del algoritmo para manejar grandes volúmenes de datos.
- Interfaz de Usuario: Crear una interfaz simple para que los usuarios puedan ver sus recomendaciones.
Sugerencias para la Implementación
- Utiliza estructuras de datos eficientes para almacenar y acceder a las calificaciones.
- Implementa técnicas de optimización para reducir el tiempo de ejecución del algoritmo de recomendación.
- Considera el uso de técnicas de paralelización si los datos son muy grandes.
Ejemplo de Código
import numpy as np
# Datos de ejemplo: calificaciones de usuarios para libros
ratings = np.array([
[5, 3, 0, 1],
[4, 0, 0, 1],
[1, 1, 0, 5],
[1, 0, 0, 4],
[0, 1, 5, 4],
])
def cosine_similarity(a, b):
return np.dot(a, b) / (np.linalg.norm(a) * np.linalg.norm(b))
def recommend_books(user_ratings, ratings_matrix, top_n=3):
similarities = []
for i in range(ratings_matrix.shape[0]):
if i != user_ratings:
sim = cosine_similarity(ratings_matrix[user_ratings], ratings_matrix[i])
similarities.append((i, sim))
similarities.sort(key=lambda x: x[1], reverse=True)
recommendations = []
for i in range(top_n):
recommendations.append(similarities[i][0])
return recommendations
# Recomendaciones para el usuario 0
print(recommend_books(0, ratings))Ejercicio
- Implementa el algoritmo de recomendación utilizando filtrado colaborativo basado en usuarios.
- Optimiza el algoritmo para manejar un conjunto de datos más grande.
- Crea una interfaz de usuario simple para mostrar las recomendaciones.
Proyecto 2: Planificador de Rutas de Transporte Público
Descripción
Desarrolla un planificador de rutas para un sistema de transporte público. El planificador debe ser capaz de encontrar la ruta más corta entre dos puntos en una red de transporte.
Requisitos
- Entrada de Datos: Un grafo que representa la red de transporte, con estaciones como nodos y rutas como aristas.
- Algoritmo de Búsqueda: Implementar el algoritmo de Dijkstra para encontrar la ruta más corta.
- Optimización: Mejorar la eficiencia del algoritmo para manejar redes de transporte grandes.
- Interfaz de Usuario: Crear una interfaz para que los usuarios puedan ingresar sus puntos de partida y destino y ver la ruta recomendada.
Sugerencias para la Implementación
- Utiliza estructuras de datos como colas de prioridad para mejorar la eficiencia del algoritmo de Dijkstra.
- Implementa técnicas de optimización para reducir el tiempo de ejecución en redes grandes.
- Considera el uso de técnicas de paralelización si la red es muy grande.
Ejemplo de Código
import heapq
def dijkstra(graph, start):
queue = []
heapq.heappush(queue, (0, start))
distances = {node: float('inf') for node in graph}
distances[start] = 0
while queue:
current_distance, current_node = heapq.heappop(queue)
if current_distance > distances[current_node]:
continue
for neighbor, weight in graph[current_node].items():
distance = current_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(queue, (distance, neighbor))
return distances
# Grafo de ejemplo
graph = {
'A': {'B': 1, 'C': 4},
'B': {'A': 1, 'C': 2, 'D': 5},
'C': {'A': 4, 'B': 2, 'D': 1},
'D': {'B': 5, 'C': 1}
}
# Distancias desde el nodo 'A'
print(dijkstra(graph, 'A'))Ejercicio
- Implementa el algoritmo de Dijkstra para encontrar la ruta más corta en una red de transporte.
- Optimiza el algoritmo para manejar redes de transporte más grandes.
- Crea una interfaz de usuario simple para que los usuarios puedan ingresar sus puntos de partida y destino y ver la ruta recomendada.
Proyecto 3: Compresor de Archivos
Descripción
Desarrolla un compresor de archivos que utilice el algoritmo de Huffman para comprimir y descomprimir archivos de texto.
Requisitos
- Entrada de Datos: Un archivo de texto para comprimir.
- Algoritmo de Compresión: Implementar el algoritmo de Huffman para la compresión de datos.
- Optimización: Mejorar la eficiencia del algoritmo para manejar archivos grandes.
- Interfaz de Usuario: Crear una interfaz para que los usuarios puedan seleccionar archivos para comprimir y descomprimir.
Sugerencias para la Implementación
- Utiliza estructuras de datos eficientes para construir el árbol de Huffman.
- Implementa técnicas de optimización para reducir el tiempo de ejecución del algoritmo de compresión.
- Considera el uso de técnicas de paralelización si los archivos son muy grandes.
Ejemplo de Código
from collections import Counter, heapq
class Node:
def __init__(self, char, freq):
self.char = char
self.freq = freq
self.left = None
self.right = None
def __lt__(self, other):
return self.freq < other.freq
def build_huffman_tree(text):
frequency = Counter(text)
heap = [Node(char, freq) for char, freq in frequency.items()]
heapq.heapify(heap)
while len(heap) > 1:
left = heapq.heappop(heap)
right = heapq.heappop(heap)
merged = Node(None, left.freq + right.freq)
merged.left = left
merged.right = right
heapq.heappush(heap, merged)
return heap[0]
def build_codes(node, prefix="", codebook={}):
if node is not None:
if node.char is not None:
codebook[node.char] = prefix
build_codes(node.left, prefix + "0", codebook)
build_codes(node.right, prefix + "1", codebook)
return codebook
def huffman_encoding(text):
root = build_huffman_tree(text)
codebook = build_codes(root)
encoded_text = ''.join(codebook[char] for char in text)
return encoded_text, root
def huffman_decoding(encoded_text, root):
decoded_text = []
node = root
for bit in encoded_text:
node = node.left if bit == '0' else node.right
if node.char is not None:
decoded_text.append(node.char)
node = root
return ''.join(decoded_text)
# Texto de ejemplo
text = "this is an example for huffman encoding"
encoded_text, tree = huffman_encoding(text)
print(f"Encoded Text: {encoded_text}")
print(f"Decoded Text: {huffman_decoding(encoded_text, tree)}")Ejercicio
- Implementa el algoritmo de Huffman para comprimir y descomprimir archivos de texto.
- Optimiza el algoritmo para manejar archivos de texto más grandes.
- Crea una interfaz de usuario simple para que los usuarios puedan seleccionar archivos para comprimir y descomprimir.
Conclusión
Estos proyectos finales están diseñados para consolidar y aplicar los conocimientos adquiridos a lo largo del curso. Al completar estos proyectos, los estudiantes habrán demostrado su capacidad para analizar, diseñar y optimizar algoritmos en contextos prácticos. Además, habrán desarrollado habilidades importantes en la implementación de algoritmos eficientes y en la creación de interfaces de usuario funcionales.
Curso de Análisis y Diseño de Algoritmos
Módulo 1: Introducción a los Algoritmos
Módulo 2: Análisis de Algoritmos
- Análisis de Complejidad Temporal
- Análisis de Complejidad Espacial
- Casos de Complejidad: Mejor, Peor y Promedio
Módulo 3: Estrategias de Diseño de Algoritmos
Módulo 4: Algoritmos Clásicos
- Búsqueda Binaria
- Ordenamiento por Inserción
- Ordenamiento por Mezcla (Merge Sort)
- Ordenamiento Rápido (Quick Sort)
- Algoritmo de Dijkstra
- Algoritmo de Floyd-Warshall