/IC-3002-TC9

IC-3002 Análisis de Algoritmos - Tarea Corta #9

Primary LanguagePython

IC-3002 Tarea corta 9

Estamos trabajando en un script para exportar datos de un sistema de información masivo y almacenarlos en una serie de dispositivos de almacenamiento externo para archivarlos como copias de seguridad.

Nuestro script genera múltiples archivos de datos cada uno posiblemente de distinto tamaño a los demás. Por otro lado, el dispositivo de almacenamiento tiene un límite de capacidad, sabemos que no todos los archivos van a caber en un solo dispositivo.

El problema que queremos resolver es el de seleccionar la mayor cantidad de archivos posibles para ser almacenados en un único dispositivo.

En términos computacionales establecemos el problema:

Problema: Dado un conjunto de archivos seleccionar la secuencia de cardinalidad máxima que pueda ser almacenada en un dispositivo de capacidad limitada.

  • Entradas: Un conjunto de archivos As = {(A_1, t_1), (A_2, t_2), ..., (A_n, t_n)} donde cada archivo A_i tiene un tamaño t_i asociado, y un dispositivo de almacenamiento externo con capacidad D, tal que D < sumatoria(t_i).

  • Salidas: Una secuencia M = ((A_1, t_1), ..., (A_m, t_m)) tal que M es el subconjunto de As con cardinalidad máxima y D >= sumatoria(t_i) para todos los t_i en M.

  1. En el archivo almacenamiento.py, implemente la función maximizar(As, D) con un algoritmo que resuelva el problema planteado utilizando la técnica de programación voraz en complejidad temporal O(n log n).

Cómo instalar el ambiente de desarrollo y ejecutar las pruebas localmente

Este proyecto requiere python3. Asegúrese que esté instalado en su distribución de linux.

Si no lo ha hecho anteriormente, crear un ambiente virtual para las dependencias

python3 -m venv .venv

Activar el ambiente virtual

source .venv/bin/activate

Instalar las dependencias

pip3 install -r requirements.txt

Ejecutar las pruebas

pytest -s -W ignore::DeprecationWarning

Rúbrica

Completitud (5 pts)

  • (5 pts) La producción cumple totalmente con los requerimientos solicitados.
  • (3 pts) La producción cumple parcialmente con los requerimientos solicitados.
  • (1 pts) La producción, en su mayor parte, no cumple con los requerimientos solicitados.

Correctitud (5 pts)

  • (5 pts) El código pasa exitosamente todas las pruebas automatizadas.
  • (3 pts) El código pasa la mayoría de las pruebas automatizadas.
  • (1 pts) El código no pasa la mayoría de las pruebas automatizadas.

Diseño del algoritmo (5 pts)

  • (5 pts) El código implementa un algoritmo de programación voraz y corre en la complejidad temporal especificada.
  • (3 pts) El código implementa un algoritmo de programación voraz pero no corre en la complejidad temporal especificada.
  • (1 pts) El código no implementa un algoritmo de programación voraz.