Reconocimiento de Patrones - Trabajo I

Detalles
Visto: 4060

Trabajo I: comparación de algoritmos de ordenación:

  1. IMPLEMENTACIÓN. Hay que implementar los siguientes algoritmos de ordenación:
    1. Quicksort, versión recursiva.
    2. Quicksort, versión iterativa.
    3. Quicksort, versión con la mediana (algoritmo de Floyd).
    4. Divide y vencerás, versión recursiva.
    5. Divide y vencerás, versión iterativa.
    6. Inserción (selección del máximo en cada paso).
    7. Recuento (counting sort).
  2. EXPERIMENTOS. Se han de diseñar de acuerdo a las siguientes instrucciones:
    1. Cada uno de los algoritmos ha de ejecutarse sobre un juego de n datos. Los valores de n son: 100, 200, ..., 10.000, esto es, aumentan de 100 en 100 hasta 10.000.
    2. El rango de valores para los datos es de de 1 a 10.000. Los datos se generarán aleatoriamente. Se permiten números repetidos.
    3. Para cada juego de datos, se ejecutarán los algoritmos anteriores y se guardarán los tiempos de ejecución. Con la pareja tamaño de entrada y tiempo de ordenación se generarán gráficas poligonales para comparar los tiempos de ejecución de cada uno.
    4. A partir de las gráficas, se estimarán las siguientes cantidades:
      1. El tamaño de entrada para el cual un algoritmo es más rápido que otro.
      2. Constantes que acompañan a las complejidades.
  3. LENGUAJE. La implementación se puede realizar en el lenguaje que se prefiera (C, Pascal, Maple, C++, etc.). Hay que entregar el código y el ejecutable bien por correo electrónico (Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.) o en persona (despacho 2004).
  4. MEMORIA. Se redactará una memoria en que se explicarán brevemente las implementaciones de los algoritmos, la realización práctica del experimento y, finalmente, se interpretarán los datos del experimento y se obtendrán conclusiones. Se responderán, al menos, a las siguientes preguntas:
    1. ¿Qué algoritmo es mejor y bajo qué circunstancias?
    2. ¿Es el algoritmo de recuento el mejor? Justifica la respuesta.
    3. Dar una clasificación de los algoritmos en términos de tiempo de acuerdo al tamaño de la entrada.
    4. Haciendo uso de la creatividad que se os supone, ofrecer vuestras propias conclusiones. Procurad que vayan acompañadas de razonamientos.
  5. PUNTUACIÓN. Descontaré puntos si la memoria:
    1. Tiene faltas de ortografía.
    2. Está plagada de material irrelevante.
    3. Falta claridad de pensamiento.
    4. Es más larga de lo necesario o es más corta de lo necesario.
  6. ERRORES DE CÓDIGO. Descontaré puntos si el código:
    1. No está comentado debidamente.
    2. No está estructurado claramente.
    3. Las variables tienen nombres absurdos.
    4. Tiene errores de ejecución.
    5. La interfaz es infame.
  7. FECHA LÍMITE. La fecha límite es el 7 de noviembre a las 23:59 horas.
  8. PREGUNTAS Y TUTORÍAS. Estoy dispuesto a responder preguntas sobre el algoritmo, su corrección, su complejidad y similares. No responderé preguntas sobre errores de codificación, pues pienso que, a estas alturas, es responsabilidad vuestra.
Menú

 

Go to top