Estandar De Calidad De Algoritmos

Trabajos Voluntarios de Análisis y Diseño de Algoritmos
16 de octubre de 2007
1. Introducción
El objetivo de la práctica es desarrollar un algoritmo que resuelva de manera lo más eciente posible el problema propuesto, empleando el esquema algorítmico más adecuado de entre los vistos en el curso. ½Es absolutamente fundamental que leaís este documento con cuidado!

2.

Normativa GeneralLas prácticas se realizarán en equipos de dos personas. Tras la formación

de los equipos de prácticas, cada profesor dará a conocer el enunciado de la práctica que a cada uno de sus equipos la ha asignado. Si uno de los miembros del equipo abandona durante la realizacián de la práctica, el otro podrá continuar en solitario. La entrega tendrá dos partes: entrega de documentacion (véase el apartado3) y demostración on-line del funcionamiento de la práctica. La demostración se hará aproximadamente una semana después de la entrega de la documentación. Los dos miembros del equipo deberán hallarse presentes, salvo en caso de fuerza mayor. La documentación en papel y los cheros que conforman la práctica se entregarán no más tarde del día 7 de Enero de 2008 a las 14:00 horas. Los cheros fuentey el ejecutable en un archivo más adelante. El programa se habrá de implementar en C++. Asimismo, el programa debe poder ejecutarse en el sistema operativo Linux. Si el equipo de prácticas quiere utilizar alguna biblioteca no estándar, deberá consultarlo previamente con su profesor.

.tar.gz

se enviarán a través de

correo electrónico y/o de la web, siguiendo las instrucciones que osfacilitaremos

3.

Documentación
La documentación impresa que obligatoriamente ha de entregarse es la si-

guiente:

1

Diseño modular Indicad las relaciones de uso, funcionalidad de cada módulo,
etc. Asimismo, deberá incluir cuando proceda cuáles son las bibliotecas externas que se emplean y dónde.

Descripción detallada y justicación de la corrección del algoritmo Hay
que explicar elfuncionamiento del algoritmo y razonar adecuadamente su corrección. Hay que incluir también el análisis teórico de la eciencia del algoritmo propuesto. Hay que hallar el coste asintótico en caso peor del algoritmo, indicando y justicando los diversos pasos involucrados en su cálculo. En caso que el algoritmo sea el resultado de la exploración de diversas alternativas, es importante que secomenten dichas alternativas y por qué se han descartado. Debe citarse en los puntos adecuados la bibliografía consultada y poner la lista completa de referencias al nal de esta sección. Por ejemplo, en el texto podrá aparecer una frase del estilo este problema es NP-hard [GJ79] y por lo tanto hemos decidido emplear un esquema que nos permita explorar exhaustiva pero lo más ecientemente posible elespacio de soluciones . . . ; y en la lista de referencias encontraríamos: [GJ79] Garey, M. R., Johnson, D. S.: Computers and Intractability: A Guide to the Theory of NP-Completeness, Ed. W. H. Freeman, San Francisco, 1979.

Estudio empírico de la eciencia Describid con precisión los experimentos
realizados. Haced las grácas correspondientes y contrastad las predicciones del análisis teóricocon los resultados experimentales.

Listado del código Sólo se entregará el listado correspondiente al (a los) procedimiento(s) que implementa(n) el algoritmo desarrollado. No se entregará el listado de ninguno de los restantes módulos (entrada/salida, principal, estructuras de datos auxiliares, etc.) Por el contrario, se adjuntará a la documentación una lista con los nombres de los cherosfuente y una breve explicación del contenido de cada uno de ellos.

Breve manual de usuario Explicad brevemente el manejo de la interfaz del
programa. No se ha de describir en ningún momento el funcionamiento interno. En concreto debe describir con cuidado el formato de los cheros de texto que pueden utilizarse para la entrada de datos a vuestro programa. El usuario es potencialmente lego en la...