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

Grupo 7051, 60 lugares. 45 alumnos.

 

Curso a distancia en general asíncrono, los horarios establecidos se manejarán para establecer videoconferencias por Meet de manera esporádica para clase en línea o para dudas y comentarios que surjan como producto del material que se suba. Se podrá mantener también contacto con el ayudante y el profesor mediante sus direcciones de correo de la Facultad de Ciencias y por medio del foro cuya dirección se publicará por aquí cuando esté disponible.

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%

• Discusiones

Las tareas consisten en ejercicios de reforzamiento y creatividad del material de clase, que varian entre la descripción de algoritmos en pseudocódigo, realizar demostraciones, analizar la complejidad de algoritmos yaplicar de forma detallada los mismos para casos concretos; se entregan de manera individual, salvo que se indique lo contrario. 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 pordí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.

El rubro de discusiones consiste en intervenciones en clases que se hagan en línea o por el foro que aporten valor al tema que se esté viendo y se aplicarán por lo general, como puntuación adicional sobre las tareas.

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. En este caso, la evaluación considera los siguientes rubros y la entrega del proyecto es obligatoria:

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

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.