Domingo Giménez Cánovas

Curso 2018-2019

Prácticas de Algoritmos y Estructuras de Datos II

grupo3 y PCEO

segundo curso del Grado en Ingeniería Informática,
3 créditos teóricos y 3 prácticos
Segundo cuatrimestre

Profesor de Teoría Norberto Marín, de prácticas Domingo Giménez Subgrupos 3.1 (miércoles 18:50-20:30, Lab 1.5), PCEO (jueves 15:30-17:10, Lab 2.1) y José Ramón Hoyos (subgrupos 3.2 y 3.3).

Texto-guía de Algoritmos y Estructuras de Datos, y su fe de erratas

Tutorías de prácticas de Domingo Giménez, jueves de 12 a 14 y 17:15 a 18:15 (mejor quedar antes por correo a domingo@um.es, para esas horas u otras)

· Planificación general

Habrá sesiones de prácticas dedicadas a resolver problemas y otras para dudas de prácticas.

Inicialmente, en las sesiones de análisis de algoritmos se resolverán problemas y al final se realizará una prueba de resolución de problemas, pudiendo utilizar material bibliográfico. Aprobando esta prueba no será necesario realizar el parcial de Análisis de Algoritmos.

Habrá una primera práctica dedicada a Análisis y Divide y Vencerás.

En las sesiones prácticas de Programación Dinámica se procederá como en las de análisis, en este caso pudiendo servir el resultado de esta prueba de programación dinámica como nota del problema de programación dinámica en el examen final.

La segunda práctica estará dedicada a avance rápido y backtracking.

· Documentos (de cursos anteriores, podrán usarse estos u otros este curso 2018-2019):

problemas de análisis

ejemplos de capítulo 6 del texto guía

· Planificación temporal (que puede sufrir ligeros cambios)

                                                               febrero 2019

                                                               Marzo

                                                                Abril

                                                         Mayo

·         Apuntes (modificados a julio del 2001, contienen exámenes anteriores al 2001): postscript, pdf

En 2003 se editó un texto-guía de la asignatura de "Algoritmos y Estructuras de Datos" del plan antiguo. El segundo volumen es de la parte de Algorítmica, y básicamente contiene los apuntes y problemas, revisados y (esperamos) mejorados.

·           Exámenes

examen de febrero 2001: postscript, pdf,

examen de septiembre 2001: postscript, pdf,

examen de diciembre 2001: postscript, pdf,

examen de febrero 2002: postscript, pdf,

examen de septiembre 2002: postscript, pdf,

examen de diciembre 2002: postscript, pdf,

examen de febrero 2003: postscript, pdf,

examen de septiembre 2003: postscript, pdf,

examen de diciembre 2003: postscript, pdf,

examen de febrero 2004: postscript, pdf,

parcial de algoritmos de AED, mayo  2004: postscript, pdf,

final de AED, junio  2004 (en postscipt: enunciado, soluciones)

final de AED, septiembre  2004 (en postscipt: enunciado, soluciones)

Diciembre  2004 (el de diciembre de AED, que contiene la parte de algoritmos, en postscript)

Examen 10 de junio, coincidiendo con el segundo parcial 2005, algoritmos, de AED, postscript, pdf,

Examen 28 de junio , postscript, pdf,

Examen 6 de septiembre 2005, pdf,

Examen 1 de diciembre 2005, pdf

Examen 9 de marzo 2011 (Análisis de Algoritmos), pdf

Examen final junio 2011 enunciados y solución: pdf 

Examen septiembre 2011, por ahora sólo están las soluciones de los problemas de avance rápido, programación dinámica, backtracking y branch-and-bound, pdf,

Examen parcial 1 de marzo 2012 (Análisis de Algoritmos), pdf

Final 1 de junio de 2012, pdf

Examen parcial marzo 2013 (Análisis de Algoritmos), Enunciado del Grupo 3, Enunciado del PES, Solución del PES

Final 7 de junio de 2013, enunciado y solución

Pruebas de Análisis de Algoritmos, marzo 2014, enunciado1, enunciado2, enunciado3

Pruebas de Programación Dinámica, mayo 2014, enunciados

Prueba de Análisis de Algoritmos, marzo 2015, enunciado y solución subgrupo 3.3

Pruebas de Programación Dinámica, abril 2015, enunciados

Pruebas de Programación Dinámica, mayo 2016, enunciados

Prueba de Análisis de Algoritmos, marzo 2017, enunciado y solución subgrupos 3.1 y 3.2

Prueba de Programación Dinámica, mayo 2017, enunciado y solución subgrupos 3.1 y 3.2

Prueba de Análisis de Algoritmos, marzo 2018, enunciado y solución subgrupos 1.3, 3.1+PES, y 3.2

Prueba de Programación Dinámica, mayo 2018, enunciado y solución subgrupos 1.3, 3.1+PES y 3.2

Prueba de Análisis de Algoritmos, marzo 2019, enunciado y solución subgrupos 3.1 y PCEO

Prueba de Programación Dinámica, mayo 2019, enunciado y solución subgrupos 3.1 y PCEO

• Lenguaje C

Enlace a un  tutorial de C

Enlaces a la asignatura de ISO:  apuntes de C ,  sobre make

·          TEMARIO:

Tema 0: Introducción.
Noción de algoritmo. Algoritmos, programas y problemas.

Tema 1: Análisis de Algoritmos.
Notaciones asintóticas.
Resolución de ecuaciones recurrentes. Cambio de variable y transformación de la imagen.

Tema 2: Divide y vencerás:
Método general.
Ordenación por mezcla.
Ordenación rápida.
Multiplicación rápida de enteros.
Multiplicación rápida de matrices.

Tema 3: Algoritmos voraces:
Método general.
Problema de la mochila.
Secuenciamiento de trabajos a plazos.
Heurísticas voraces.

Tema 4: Programación dinámica:
Descripción.
Problema de la mochila 0/1.

Tema 5: Backtracking:
Descripción.
Problema de las n reinas.
Problema de la mochila.
Análisis.

·           BIBLIOGRAFÍA:
Aho, Hoptcroft, Ullman: The design and analysis of computer algorithms. Addison-Wesley. 1974.
Aho, Hoptcroft, Ullman: Estructuras de datos y algoritmos. Addison-Wesley. 1988.
Baase: Computer algorithms. Introduction to design and analysis. Addison-Wesley. 1983.
Brassard, Bratley: Algorítmica. Concepción y análisis. Masson. 1990.
Brassard, Bratley: Fundamentos de Algoritmia. Prentice-Hall. 1996. (BÁSICA)
Cormen, Leiserson, Rivest: Introduction to Algorithms. MIT Press. 1991.
Galve, González, Sánchez y Velázquez: Algoritmia: diseño y análisis de algoritmos Funcionales e Imperativos. Ed ra-ma. 1993.
Giménez Cánovas, Domingo; Cervera López, Joaquín; García Mateos, Ginés; Marín Pérez, Norberto: Algoritmos y Estructuras de Datos. Volumen II. Algoritmos. Texto guía. DM 2003. (BÁSICA)
Gonnet, Baeza-Yates: Handbook of Algorithms and Data Structures. Second Edition. Addison-Wesley. 1991.
Horowitz, Sahni: Fundamentals of computer algorithms. Pitman. 1978.
Knuth: El arte de programar ordenadores. Vol 3: Clasificación y búsqueda. Reverté. 1987.
Mehlhorn: Data structures and algorithms. Vol 1: Sorting and Searching. Springer-Verlag. 1984.
Mehlhorn: Data structures and algorithms. Vol 2: Graph algorithms and NP-Completeness. Springer-Verlag. 1984.
Troya Linero: Análisis y diseño de algoritmos. VI Escuela de Verano de Informática. AEIA. 1984.
Wirth: Algoritmos + Estructuras de Datos = Programas. Ediciones del Castillo. 1980.
Wirth: Algoritmos y estructuras de datos. Prentice-Hall. 1987.