Cinvestav
Departamento de Computación
Curso: Análisis y Diseño de Algoritmos
Prof. Dr. Luis Gerardo de la Fraga
Cuatrimestre agosto a diciembre de 2025
Este es el contenido del curso.
Apuntes del Curso:
-
13.10.2025 El programa en python que resuelve el problema del corte de una varilla con programación dinámica.
-
13.10.2025 El diagrama del árbol de intervalos visto en clase.
-
30.10.2025 La visualización de árboles binarios con Graphviz.
-
23.10.2025 Las operaciones de búsqueda iterativa, mínimo y máximo en un árbol binario en python.
-
21.10.2025 Un árbol binario en python.
-
7.10.2025 Funciones rand(1,n) y shuffle().
-
18.09.2025 Ordenamiento de un conjunto de puntos en forma circular.
-
09.09.2025 Código en python de los ordenamientos por inserción y por mezcla.
-
02.02.2025 Código en python para el trazo de la línea según el algoritmo del punto medio.
Tareas del Curso:
Tarea 10: : Árbol de intervalos
Fecha de entrega: martes 9 de diciembre, 2025
-
Realizar el árbol de intervalos usando un árbol rojo y negro
-
Llenar el árbol con 10 intervalos
-
Quitar y poner 5 intervalos
-
Repetir tres veces el punto anterior y visualizar los árboles resultantes.
También checar en cada árbol la búsqueda de algún intervalo y reportarlo.
Tarea 9: : Árboles rojos y negros
Fecha de entrega: martes 25 de noviembre, 2025
-
Hacer el pseudocódigo y el código en python para
crear un árbol de búsqueda binario rojo y negro.
-
Con tres entradas a aleatorias cree el árbol rojo y negro
insertando nodos y visualize los tres árboles resultantes
-
Borre nodos de forma aleatoria visualize el resultado
para mostrar que se sigue manteniendo el árbol rojo y negro.
Tarea 8: : Creación de un árbol binario
Fecha de entrega: martes 11 de noviembre, 2025
Hacer el pseudocódigo y el código en python para
crear un árbol de búsqueda binario a partir de una lista de llaves.
Tarea 7: : Estadísticas de orden
Fecha de entrega: martes 4 de noviembre, 2025
-
Implemente la rutina para encontrar la mediana en tiempo lineal.
-
Realize las pruebas necesarias pare mostrar que su tiempo de ejecución es lineal
Tarea 6: Ordenamiento del montón
Fecha de entrega: martes 28 de octubre, 2025
Programar en python el ordenamiento del montón. Mostrar al menos tres ejecuciones con datos de entrada distintos, tal vez revolviendo aleatoriamente el arreglo de entrada.
Tarea 5: Algoritmos aleatorizados
Fecha de entrega: jueves 16 de octubre, 2025
- Probar el algoritmo de la contratación de asistentes.
Reproducir su distribución de probabilidad realizando muchas
contrataciones.
- Reproducir tambien la distribución de probabidades y las
tiradas promedio del algoritmo de Las Vegas para encontrar
una 'a' en un arreglo con la mitad de elementos igual a 'a's y la otra mitad igual a 'b's.
Tarea 4: Ecuaciones de recurrencia
Fecha de entrega: martes 7 de octubre, 2025
Resolver estos dos problemas.
Tarea 3: Búsqueda del subarreglo máximo
Fecha de entrega: martes 30 de septiembre, 2025
Programar en python y verificar el resultado del problema del subarreglo máximo.
Tarea 2: Tamaño del problema que se puede solucionar
Fecha de entrega: jueves 18 de septiembre, 2025
Resolver este problema.
Tarea 1: Algoritmo para el trazo de una línea en cualquier sentido
Fecha de entrega: jueves 11 de septiembre, 2025
-
Se dede analizar el número de casos que se tienen para trazar una línea. Hacer el diagrama como en
clase para visualizar todos los casos.
- Hacer una tabla de cada caso y la forma de detectarlo
- Codificar el algoritmo en python
- Hacer la prueba con este código y realizar la gráfica de salida.
El código de shell se ejecuta como "bash tarea1.sh"
La gráfica debe estar hecha en python con matplotlib.
Última actualización: 13 de noviembre, 2025
Comentarios: fraga en cs cinvestav mx