Prácticas de la asignatura de Algorítmica de la Universidad de Granda (2014-2015)

1. Eficiencia: ejemplos sobre el cálculo de eficiencia en trozos de código y funciones.
2. Divide y Vencerás: consiste en implementar la multiplicación clásica de enteros largos y la multiplicación de enteros largos mediante el algoritmo de Karatsuba y Offman y comparar la eficiencia de ambos algoritmos.
3. Algoritmos Greedy: implementación del problema de la mochila fraccional en C++. Teniendo un conjunto inicial de objetos, escoge aquellos que aportan mayor beneficio para una mochila de peso M, ya sea objetos enteros o fraccionados. Esto se resuelve haciendo uso de un algoritmo Greedy.
4. Programación Dinámica: implementación del problema de la mochila 0/1 en C++, pero en este caso sólo cogiendo objetos enteros (coger o no coger el objeto) y haciendo uso de un algoritmo de Programación Dinámica.
5. Branch & Bound: implementación de la mochila 0/1 en C++ haciendo uso de un algoritmo Branch and Bound.
6. Guión: guión de prácticas donde están explicados los ejercicios y los distintos algoritmos de forma más extendida.

1. Eficiencia: para compilar usar:
   • pdflatex -shell-escape efic.tex: compilar dos veces para ver bien los enlaces. Nota: hay que tener el paquete minted de LaTeX, además de todo lo necesario para LaTeX.
2. Divide y Vencerás: al estar escrito en Python, es solo llamar de la siguiente forma:
   • python multc.py entero1 entero2 para la multiplicación clásica de enteros largos.
   • python multd.py entero1 entero2 para la multiplicación con el algortimo Divide y Vencerás de enteros largos.
3. Algoritmos Greedy: para poder ejecutar hay que hacer lo siguiente:
   • make: para compilar
   • ./bin/mochila B P B P ... PESOMOCHILA siendo B el beneficio del objeto y P el peso del objeto
4. Programacion Dinámica: igual que el anterior:
   • make: para compilar
   • ./bin/mochila B P B P ... PESOMOCHILA
5. Branch & Bound: igual que las dos anteriores:
   • make: para compilar
   • ./bin/mochila B P B P ... PESOMOCHILA
6. Guión: para compilar y que aparezcan los enlaces, hay que compilar dos veces usando el comando en terminal:
   • pdflatex -shell-escape Entrega.tex Nota: Hay que tener el paquete de minted y pygmentize instalados.