Ciencias de la Computación (plan 2013) 2022-2

Curso a distancia en general asíncrono, los horarios establecidos se manejarán para establecer videoconferencias en línea por las plataformas Meet o Zoom de manera esporádica para resolver dudas y aportar comentarios que surjan como producto del material, el cual será difundido por Classroom y la invitación será enviada para los alumnos inscritos únicamente. A manera de aclaración, se aceptan estudiantes que se inscriban en modalidad ordinaria y de extraordinario largo, no se aceptan oyentes. Se sugiere registrar el correo @ciencias como contacto personal para poderlos dar de alta en la plataforma. Esta presentación estará disponible a detalle el Lunes 14 de Febrero en Classroom a las 12 hrs, dia de inicio de semestre.

Estudiantes interesados en inscribir la asignatura que por límite de cupo fueron rechazados pueden escribir a zeron@ciencias.unam.mx para que las inscripciones se traten como casos especiales.

Contenido del curso

1) Fundamentos

1.1 Problemas, Ejemplares, Algoritmos y Soluciones.

1.2 Características de los Algoritmos.

1.3 Tipos de Problemas.

2) Análisis de Complejidad de Algoritmos

2.1 Modelos de Cómputo.

2.2 Tiempo de Ejecución.

2.3 Complejidad.

3) Justificación de Algoritmos

3.1 Algoritmos Recursivos.

3.2 Algoritmos Iterativos.

4) Diseño de Algoritmos

4.1 Divide y Vencerás

4.2 Algoritmos Codiciosos

4.3 Programación Dinámica

5) Algoritmos de Búsqueda

5.1 Mapas y diccionarios

5.2 Búsqueda Binaria y Variantes.

6) Algoritmos de Ordenamiento

6.1 Ordenamientos por Comparaciones.

6.2 Cota Mínima de Ordenamiento.

6.3 Ordenamientos para Casos Especiales.

7) Algoritmos Fundamentales en Gráficas

7.1 Recorridos.

7.2 Ordenamiento Topológico.

8) Algoritmos para Optimización en Gráficas

8.1 Problema del Arbol Generador de Costo Mínimo.

8.2 Problema de la Ruta más Corta.

8.3 Flujo en Redes

9) Temas Selectos *

9.1 Calendarización

9.2 Apareamiento de cadenas *

Evaluación

• 9 - 10 Tareas 60%

• Programas 20%

• Proyecto final 20%

• Asistencias (máximo 5% adicional)

Las tareas consisten en ejercicios de reforzamiento y creatividad correspondientes al material de clase, que varian entre la descripción de algoritmos en pseudocódigo, realizar demostraciones, analizar la complejidad de algoritmos y aplicar de forma detallada los mismos para casos concretos; se entregan de manera individual, salvo que se indique otra cosa. Se admiten archivos escritos con tinta legible escaneados o tareas hechas directamente en computadora, en el editor de texto de su preferencia. En caso de entrega retrasada, se penalizan dos puntos por día de retraso, salvo en casos de fuerza mayor que sean comprobables.

Los programas consisten en implementaciones en Java (versión 8 o superior) de algoritmos vistos en clase o como complemento de la descripción de ellos. Las normas de entrega se definirán en cuanto se deje el primer programa. En caso de entrega retrasada, se penalizan dos puntos por día de retraso, salvo en casos de fuerza mayor que sean comprobables.

El proyecto involucra una parte que requiera investigación sobre algún problema y otra de implementación de los algoritmos involucrados en Java. La fecha de entrega es única, salvo por causa de fuerza mayor que sea comprobable.

Las asistencias se tomarán sólo en sesiones de videollamada y suman un porcentaje proporcional a la calificación final; en particular, si se cuenta con todas las asistencias, se sumará un 5%.

Se puede presentar la reposición de dos tareas, o bien, un examen final con el cual se renuncia a las calificaciones obtenidas en las tareas y al registro de asistencias. En este último caso, la evaluación sólo considera los siguientes rubros y la entrega del proyecto es obligatoria:

• Examen final 60%
• Programas 20%
• Proyecto final 20%

Solamente tendrán derecho a NP quienes no entreguen ninguna tarea ni presenten examen final. No se puede renunciar a calificaciones finales aprobatorias.

Referencias

[1] J.Kleinberg and E.Tardos. Algorithms Design. AddisonWesley, 2005.

[2] T.H.Cormen, C.E.Leiserson, R.L.Rivest and C.Stein. Introduction to Algorithms. 3rd edition, MIT Press, 2009.

[3] S. Dasgupta, C. Papadimitriou y U. Vazirani. Algorithms. McGraw-Hill, 2006.

[4] M.T. Goodrich and R. Tamassia. Algorithm Design and Applications. John Wiley and Sons, 2015.

[5] U.Manber. Introduction to Algorithms. A creative approach. AddisonWesley, 1989.

[6] S.S.Skiena. The Algorithm Design Manual. 2nd edition, Springer-Verlag, 2008.

[7] M.A.Weiss. Data Structures and Algorithm Analysis in Java. Addison Wesley. 3rd edition, 2012.

[8] R.E.Neapolitan. Foundations of Algorithms. Jones and Bartlett Learning. 5th edition, 2015.

[9] J.Kingston. Algorithms and Data Structures: Design, Correctness and Analysis. Addison Wesley, 1990.

[10] R.Sedgewick, K.Wayne. Algorithms. 4th edition, Addison Wesley, 2011.