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 2021

Este es el contenido del curso.

Apuntes del Curso:

  1. Códigos de Huffman. Grafos y el algoritmo de búsqueda de la primera amplitud.
  2. El problema de la multiplicación de una cadena de matrices. Algoritmos glotones.
  3. El árbol de intervalos. Programación dinámica
  4. El árbol de estadísticas de orden dinámico de n nodos. El árbol de intervalos
  5. El invariante al corregir al insertar en un árbol rojo y negro. Estadísticas de orden dinámicas
  6. Programa en python para realizar el diagrama de un árbol con graphviz.
  7. Insertar y borrar en un árbol rojo y negro.
  8. Insertar en un árbol rojo y negro.
  9. Borrar un nodo en un árbol de búsqueda binario.
  10. Operaciones sobre un árbol de búsqueda binario.
  11. Árboles de búsqueda binarios.
  12. Estadísticas de orden y la mediana.
  13. Ordenamientos por conteo, indizado y por cubetas.
  14. Ordenamiento rápido.
  15. Tiempo de ejecución del ordenamiento usando el montón.
  16. Ordenamiento usando el montón.
  17. Algoritmos aleatorizados.
  18. Algoritmos aleatorizados.
  19. Algoritmo para calcular la cubierta convexa. Más recurrencias.
  20. Resolviendo ecuaciones con recurrencias.
  21. El problema del subarreglo máximo. Multiplicación de matrices con el método de Strassen
  22. Código del ordenamiento circular. El problema del subarreglo máximo.
  23. El apunte sobre crecimiento de funciones.
  24. Notación asintótica. Ordenamiento circular.
  25. Notación asintótica. Ordenamiento circular.
  26. Algoritmo de ordenamiento por mezcla, de tiempo de ejecución Theta(n lg n)
  27. Algoritmo de ordenamiento por inseción
  28. Algoritmo incremental de punto medio para el trazo de una línea
  29. Los programas informáticos de Charles Babbage, con Raúl Rojas.
    Charla organizada por la Academia Mexicana de Computación.
    Aquí el Dr. Raúl Rojas muestra como Babbage trabajó parte de su vida
    creando algoritmos para su máquina analítica, que era mecánica y no electrónica
    como las computadoras actuales.
  30. Introducción

Tareas del Curso:

Tarea 11: El problema de la multiplicación de una cadena de matrices
Fecha de entrega: miércoles 15 de diciembre, 2021

  1. Verificar el ejemplo de libro con la cadena de matrices de dimensiones
    (30, 35, 15, 5, 10, 20, 25)
    cuya separación óptima es: ((A1(A2 A3))((A4 A5) A6)) y costo es 15,125 multiplicaciones escalares.
  2. Calcular la partición óptima para calcular el producto de la cadena de matrices cuya secuencia de dimensiones es: (5, 10, 3, 12, 5, 50, 6)
  3. Use el método de sustución para verificat que la solución a la ecuación de recurencias para este problema es Omega(2^n)

Tarea 10: El árbol dinámico de n nodos para calcular estadísticas de orden
Fecha de entrega: miércoles 8 de diciembre, 2021

  1. Realizar primero las funciones para insertar y borrar en un árbol rojo y negro.
  2. Hacer las adecuaciones para el cálculo de las estadísticas de orden.
  3. Leer el apunte de la clase del día 1 de diciembre para la verificación de que el código realizado es correcto.

Tarea 9: Rotaciones sobre los nodos de un árbol
Fecha de entrega: lunes 29 de noviembre, 2021

  1. Realizar el pseudocódigo de la operación rotar_derecha()
  2. Codificar las operaciones de rotar derecha e inquierda en python
  3. Realice una rutina para construir un árbol de búsqueda binario a partir de una lista de llaves. Utilice esta rutina para probar la ejecución correcta de las operaciones de rotación sobre el árbol.
  4. Argumente que para cada árbol de búsqueda binario con n nodos, existen exactamente n-1 rotaciones.

Tarea 8: Estadísticas de orden
Fecha de entrega: miércoles 10 de noviembre, 2021

  1. Programar la rutina para encontrar el mínimo y máximo de un conjunto de n elementos que ocupe a lo más 3 piso(n/2) comparaciones.
  2. Muestre el que segundo más pequeño de n elementos puede encontrarse con n + techo( lg n ) - 2 comparaciones en el peor caso (también se debe encontrar el elemento más pequeño).

Tarea 7: Ordenamiento en tiempo lineal
Fecha de entrega: miércoles 3 de noviembre, 2021

  1. Implementar en python el ordenamiento por indizado para ordenar de forma lexicográfica palabras.
  2. Respondan a la pregunta:
    ¿Tiene que ser el número de cubetas igual al número de llaves?
    O dicho de otra forma ¿si m y n no son iguales se cambia el tiempo de ejecución?

Tarea 6: Ordenamiento del montón
Fecha de entrega: miércoles 27 de octubre, 2021

  1. Programar en python el ordenamiento por el montón
  2. Mostrar al menos el resultado de cuatro ejecuciones revolviendo aleatoriamente la misma entrada
  3. Mostrar que, con la representación con un arreglo para almacenar los n elementos de un montón, las hojas son nodos indexados por piso(n/2)+1, piso(n/2)+2, ..., n

Tarea 5: Algoritmos aleatorizados
Fecha de entrega: miércoles 20 de octubre, 2021
Realice dos codificacion en python para el algoritmo de la contratación de un asistente y el algoritmo de Las Vegas. Debe de poner al menos cinco resultados de sus pruebas.

Tarea 4: Estrategia divide y vencerás
Fecha de entrega: miércoles 29 de septiembre, 2021
Realizar estos dos problemas

Tarea 3: Problemas
Fecha de entrega: miércoles 22 de septiembre, 2021
Realizar estos dos problemas

Tarea 2: Problemas
Fecha de entrega: miércoles 15 de septiembre, 2021
Realizar estos dos problemas

Tarea 1: Algoritmo para el trazo de una línea en cualquier sentido
Fecha de entrega: miércoles 8 de septiembre, 2021

  1. 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.
  2. Hacer una tabla de cada caso y la forma de detectarlo
  3. Codificar el algoritmo en python
  4. 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 con gnuplot.

Última actualización: 13 de diciembre, 2021
Comentarios: fraga en cs cinvestav mx