1_alg

Vista previa del material en texto

Universidad Nacional de San Agust́ın
Maestŕıa en Ciencia de la Computación
Estructura de datos y algoritmos
Práctica 01
DOCENTE CARRERA CURSO
Vicente Machaca Arceda Maestŕıa en Ciencia de la
Computación
Estructura de datos y
algoritmos
PRÁCTICA TEMA DURACIÓN
01 Algoritmos de ordenamiento 3 horas
1. Competencias del curso
Analiza e implementa algoritmos eficientes para la solución de problemas computacionales.
Implementa estructuras de datos adecuadas, según el tipo de problema.
2. Competencias de la práctica
Implementa y analiza algoritmos básicos de ordenamiento.
3. Equipos y materiales
Latex
Pyhton y C++
4. Entregables
Se debe elaborar un informe donde se responda a cada ejercicio de la Sección 5.
El informe debe contener un enlace al código fuente (github).
Por cada 30 minutos de retraso, el alumno tendrá un punto menos.
Vicente Machaca Arceda Estructura de datos y algoritmos Página 1
Universidad Nacional de San Agust́ın
Maestŕıa en Ciencia de la Computación
Estructura de datos y algoritmos
5. Ejercicios
En esta práctica usted implementará los principales algoritmos de ordenamiento y comparará su
desempeño en tiempo de ejecución.
1. Preparación de los datos. Usted debe generar varios conjuntos de datos (archivos .txt), por
ejemplo va a generar números aleatorios y los va a almacenar en varios archivos. Cada archivo
deberá contener respectivamente 100, 500, 1000, 2000, 3000, ... , 10000, 20000, 30000, ... ,100000
datos.
2. Implemente los siguientes algoritmos en C++ y Python:
Bubble sort
Counting sort
Heap sort
Insertion sort
Merge sort
Quick sort
Selection sort
3. Realice comparaciones del tiempo de procesamiento de cada algoritmo por cada lenguaje de
programación. Debe generar las siguientes gráficas:
Comparar el tiempo de procesamiento de los dos lenguajes de programación por cada algo-
ritmo. Por ejemplo en la Figura 1, se muestra una comparación del Buble sort, en C++, Java
y Python. El eje x representa diferentes tamaños de vector a ordenar y el eje y, representa
el tiempo de procesamiento.
Figura 1: Comparación de Buble Sort en C++, Java y Python.
Vicente Machaca Arceda Estructura de datos y algoritmos Página 2
Universidad Nacional de San Agust́ın
Maestŕıa en Ciencia de la Computación
Estructura de datos y algoritmos
Comparar el tiempo de procesamiento de todos los algoritmos implementados en Python y
C++. Por ejemplo en la Figura 2, se muestra la comparación en C++.
Figura 2: Comparación de los algoritmos de ordenamiento en C++.
Vicente Machaca Arceda Estructura de datos y algoritmos Página 3
Universidad Nacional de San Agust́ın
Maestŕıa en Ciencia de la Computación
Estructura de datos y algoritmos
6. Rúbricas
Rúbrica Cumple Cumple con obs. No cumple
Informe: El informe debe estar
en Latex, con un formato limpio,
buena presentación y redacción.
2 1 0
Implementación: Implementa
todos los algoritmos y realiza las
comparaciones solicitadas.
10 5 0
Trabajo en equipo: Toda la
implementación esta en Github y
se aprecia el trabajo en equipo.
6 3 0
Presentación: El alumno de-
muestra dominio del tema y co-
noce con exactitud cada parte de
su trabajo.
2 1 0
Errores ortográficos: Por cada
error ortográfico, se le descontará
un punto.
- - -
Vicente Machaca Arceda Estructura de datos y algoritmos Página 4
	Competencias del curso
	Competencias de la práctica
	Equipos y materiales
	Entregables
	Ejercicios
	Rúbricas