Prácticas de análisis de algoritmos [ESCOM]

A lo largo del semestre, en la materia de Análisis de Algoritmos que llevo con el profesor Edgardo Franco tenemos que realizar varias prácticas. Las prácticas consisten en programar algoritmos conocidos para analizar su comportamiento, tanto en tiempo como en memoria consumida, mientras resuelven problemas de "gran" tamaño.

Muchas (si no es que todas D:) estarán hechas para C, para Linux, esto debido a la librería empleada para medir los tiempos que consume la ejecución del algoritmo. Para facilitar la compilación cada práctica cuenta con un archivo Makefile, el cual contiene todas las instrucciones para compilar y ejecutar las prácticas. Dado que tenemos que analizar los tiempos de ejecución y a veces estos pueden ser muchos, para la ejecución de cada programa redireccionamos la salida estandar para que escribiera directamente a un archivo que podemos manejar sencillamente en una hoja de cálculo. Esto se puede ver en el archivo .sh que acompaña a cada práctica.

Todas las prácticas tienen comentarios, unas más, otras menos, pero los tienen. Aún así si queda alguna duda pues no dudes en preguntar. Otra cosa importante es que estas son solo las propuestas de solución que presentamos, no las copies directamente, basate en ellas o usa porciones del código, eso se vale. El link de descarga está al final del artículo ;).

Hasta el momento hemos realizado 3 prácticas:

Práctica 1: "Pruebas a posteriori (Algoritmos de ordenamiento)"

Con base en el archivo de entrada proporcionado que tiene 200,000 números diferentes. Ordenarlo bajo los siguientes métodos de ordenamiento y comparar experimentalmente las complejidades de estos.
  • Burbuja (Bubble Sort)
  • Burbuja Simple
  • Burbuja Mejorada
  • Inserción (Insertion Sort)
  • Selección (Selection Sort )
  • Shell (Shell Sort)
  • Ordenamiento con árbol binario de busqueda (Binary Search Tree)

Práctica 2: "Análisis temporal y notación de orden (Algoritmos de busqúeda)"

Con base en el ordenamiento obtenido a partir del archivo de entrada de la práctica 01 que tiene 200,000 números diferentes. Realizar la búsqueda de elementos bajo 3 métodos de búsqueda y variantes con procesos ligeros, realizar el análisis teórico y experimental de las complejidades; así como encontrar las cotas de los algoritmos.
  • Búsqueda lineal o secuencial (No recursiva)
  • Búsqueda binaria o dicotómica (No recursiva)
  • Búsqueda en un árbol binario de búsqueda (No recursiva)
  • Modificar los tres algoritmos para trabajar con procesos ligeros (Hilos).

Práctica 3: "Divide y vencerás (Rotación de una imagen)"

Implementar el algoritmo de rotación de imágenes que emplea la técnica divide y vencerás. La imágen a girar es cuadrada, y es un .bmp de 24 bits.

Descargas:
Como desde hace tiempo, puedes seguir el proyecto en GitHub analizando-algo (recomendado)
O descargar cada una de las tres prácticas de manera individual:
Práctica 3
Práctica 2
Práctica 3


¡Saludos!
@fferegrino :)

No comments:

Post a Comment

¡Hey, gracias por tu comentario! No seas anónimo, inicia sesión para que te responda más fácilmente.