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 2022

Este es el contenido del curso.

Apuntes del Curso:

  1. Pseudocódigo para borrar un nodo en un árbol rojo y negro.
  2. Pseudocódigo para insertar un nodo en un árbol rojo y negro.
  3. El script para optener el diagrama de un árbol con Graphviz.
  4. Codificación de un árbol de búsqueda binario.
  5. El ordenamiento por conteo.
  6. Los funciones en pseudocódigo para el ordenamiento del montón.
  7. Realización de la distribución de una variable aleatoria con distribución uniforme.
  8. El problema del subarreglo máximo.
  9. El ordenamiento circular.
  10. El invariante de ciclo para la función Mezcla().
  11. El invariante de ciclo del ordenamiento por inserción.
  12. Ordenamiento por inserción.
  13. Código en python para el trazo de la línea por el algoritmo de punto medio.

Tareas del Curso:

Tarea 10: Árbol de búsqueda rojo y negro para implementar el cálculo de las estadísticas de orden con datos dinámicos
Fecha de entrega: jueves 8 de diciembre, 2022

  1. Hacer las adecuaciones para el cálculo de las estadísticas de orden.
  2. ¿Cómo convencer que el código es correcto?
  3. Hacen el árbol con 10 nodos, usando insertar_rn( ), muestran su diagrama.
  4. Insertar 10 nodos más. Borrar 10 nodos más, tal vez distintos que los insertados. Mostrar el diagrama del árbol.
  5. Calcular algunas estadísticas de orden( mínimo, máximo y la mediana ).

Tarea 9: Operaciones sobre un árbol de búsqueda rojo y negro
Fecha de entrega: jueves 1 de diciembre, 2022

  1. Programar en python las operaciones insertar_arbol_rn() y borrar_arbol_rn( )
  2. Crear tres pruebas para verificar que el árbol rojo y negro resultante de insertar y borrar varios de sus nodos, sigue siendo un árbol balanceado.

Tarea 8: Operaciones sobre un árbol de búsqueda binario
Fecha de entrega: jueves 24 de noviembre, 2022

  1. Programar en python las operaciones sobre un árbol de búsqueda binario: buscar, minimo, máximo, sucesor, predecesor, insertar y borrar.
  2. Crear a mano un árbol de búsqueda binario y mostrar que las operaciones son correctas sobre ese árbol.

Tarea 7: Estadísticas de orden
Fecha de entrega: martes 15 de noviembre, 2022

  1. Programar en python el cálculo simultáneo del máximo y minimo haciendo 3*piso(n/2) comparaciones.
  2. Programar en python el cálculo de la mediana. Realizar el experimento revolviendo aleatoriamene el arreglo de entrada y contar el número de comparaciones realizadas para 30 repeticiones. Reportar el promedio del número de comparaciones realizadas.

Tarea 6: Ordenamientos en tiempo lineal
Fecha de entrega: martes 8 de noviembre, 2022

  1. Programar el ordenamiento por conteo
  2. Programar el ordenamiento por cubetas

Tarea 5: El ordenamiento del montón
Fecha de entrega: jueves 27 de octubre, 2022

  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 techo(n/2)+1, techo(n/2)+2, ..., n

Tarea 4: Problema de contratación
Fecha de entrega: jueves 20 de octubre, 2022

  • Realizar la codificación en python del problema de contratación de 15 asistentes y realizar el resultado desde 2 hasta 10 contrataciones. Repetir el experimento al menos 50 veces y reportar el promedio del número de entrevistas realizadas.
  • Reportar también la salida de al menos cinco ejecuciones del programa individual para 6 contrataciones con la lista de calidades de los asistentes he indicar los que son contratados.

    • Tarea 3: Problema del subarreglo máximo
    Fecha de entrega: jueves 29 de septiembre, 2022

    Realizar la codificación en python del problema del subarreglo máximo.

    Tarea 2: Tamaño del problema que se puede solucionar
    Fecha de entrega: jueves 15 de septiembre, 2022

    Resolver este problema.

    Tarea 1: Algoritmo para el trazo de una línea en cualquier sentido
    Fecha de entrega: jueves 8 de septiembre, 2022

    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: 24 de noviembre, 2022
    Comentarios: fraga en cs cinvestav mx