Teaching‎ > ‎

Análisis y Diseño de Algoritmos (AyDA) - 16I


I decry the current tendency to seek patents on algorithms... There are better ways to earn a living than to prevent other people from making use of one’s contributions to computer science.

Donald Knuth 
(Premio Turing 1974)








Información general
Clave: 4600013 
Trimestre: 16-I
Grupo: CE01C
Profesor: Antonio López Jaimes (Cubículo C-802, alopez <arroba> correo.cua.uam.mx, tonio.jaimes <arroba> gmail.com).

Calificaciones finales
Acá pueden ver la hoja con las calificaciones finales. El acta la entregaré este viernes, así que si hay algún error en su calificación aún hay tiempo de corregirlo.



Proyecto final (3ra evalución del curso)
Para estos proyectos deberán resolver de manera individual su problema correspondiente usando 
la técnica de backtracking.
  • Este miércoles 6 deberán presentar de manera obligatoria sus avances y el código que lleven hasta el momento.
  • El lunes 11 será el examen de reposición (1er o 2do parcial según elijan) de 8am-10am.
  • El martes 12 deberán entregar la implementación final de su proyecto a más tardar a las 11:59pm.
  • El miércoles 13 deberán presentar brevemente (5-7min) su implementación. 
    •   Presentador(es) Problema Topping
        1er sesión 8am-10am 
       1José Luis y Mauricio L-triomino Gráfica de tiempos
       2David L-triomino 
       3Alexis Herández Olvera L-triomino  
       4Antonio y Fritz Monitos  Gráfica de tiempos
       5Esteban Paseo del caballo 
       6Tonatiuh Paseo del caballo 
       7Carlos Paseo del caballo 
       8Iván  Paseo del caballo 
       9Marco Criptoarimtos 
       10Kevin Criptoarimtos 
       11Roberto Sudoku  
       12Carolina  y Héctor Sudoku Gráfica de tiempos
          
        2da sesión 11am-12:10pm 
       13Belén y Viviana Laberinto Gráfica de tiempos
       14Dante Laberinto 
       15Diego Laberinto 
       16Miguel Scrabble 
       17Liliana Scrabble 
       18Sebastián N reinas 
       19Alexis Herández Gómez N reinas 

Partes que debe incluir su presentación (de 5 a 7 min):
  1. Explicación del problema a resolver (breve).
  2. Presentación del pseudocódigo.
  3. Explicación del código, mencionando:
    1. Estructura de datos que usaron para representar la solución: arreglos, matriz de adyacencia, etc.
    2. ¿Cómo identifican las opciones de cada nivel usando su estructura de datos?
    3. ¿Cómo verifican las condiciones de corte usando su estructura de datos?
  4. Para los que estén en equipo, la gráfica como se explica más abajo.
Los equipos de 2 personas deberán entregar adicionalmente lo siguiente:
  1. Resultados experimentales del tiempo de ejecución real de su algoritmo al cambiar el tamaño de la entrada. Es decir ejecutar su algoritmo para diferentes valores de n (p. ejemplo 15 valores entre n=1 y n=20) y graficar estos tiempos en una gráfica.


Exámenes
  1. Primer exámen parcial: lunes 29 de febrero.
  1. Aquí están las calificaciones del 1er examen
  2. Calificaciones del 2do examen parcial.

Tareas
 Número tarea (click para detalles)    Fecha entrega Comentario
Tarea 1
 viernes 22 de eneroEntregar físicamente a la hora de clase, escrita a mano o usando algún editor.
Tarea 2 viernes 29 de enero Subir a su carpeta compartida de Google Drive (versión digital a mano o con editor). Si la tarea es entregada después de las 8:30am ya se considerará con una clase de retraso.
 Tarea 3 jueves 11 de febreroSubir a su carpeta compartida de Google Drive antes de las 8pm una copia digital (foto o escaneada) de su tarea.
 Tarea 4viernes  26 de febrero Entregar en salón de clases. No hay prórroga.
 Tarea 5miércoles 9 de marzoTarea del algoritmo recursivo para encontrar el máximo. Se entregó en clase. 
 Tarea 6miércoles 23 de marzo Subir al aula virtual o entregar en salón.

RecordatorioLa carpeta compartida para sus tareas debe tener el nombre ayda_<nombre alumno>. Por ejemplo, la carpeta de Donald Knuth, se llamaría ayda_donald knuth. Lo importante es que tenga el prefijo "ayda" al inicio.



Aquí está la presentación sobre nociones
de análisis a
sintótico.









Herramientas útiles para el curso:
  • gnuplot: esta herramienta permite graficar fácilmente funciones en 2 o 3 dimensiones. Para instalar en Windows ir a http://www.gnuplot.info/ ; para instalar en Linux es mejor ir al administrador de paquetes de sus distribución y buscar gnuplot.

Contenido del curso (resumen)
  1. Introducción [semanas 1 y 2]

    1. Algoritmos y pseudocódigo

    2. Crecimiento de funciones

    3. Recurrencias

    4. Análisis probabilístico y algoritmos aleatorios

  2. Análisis de la complejidad y corrección de algoritmos [semanas 3 a 5]

    1. Medidas asintóticas

    2. Cálculo de la eficiencia de un algoritmo

    3. Estudio de la corrección de un algoritmo

  3. Diseño de algoritmos [semanas 6 a 10]

    1. Estrategia voraz

    2. Divide y vencerás

    3. Backtracking

    4. Programación dinámica

    5. Ramificación y poda

  4. Introducción a la teoría de NP-completez [semana 11]

 
La planeación detallada del curso la encuentran aquí.


Ponderación y escala de calificaciones
Para calcular la calificación final se tomarán en cuenta los siguientes porcentajes:

Intervalos para la calificación:

NA: 0.0 ≤ Cal <  6.0
S:  6.0 ≤ Cal <  7.8
B:  7.8 ≤ Cal <  9.0
MB: 9.0 ≤ Cal ≤ 10.0