Domingo Giménez Cánovas

Curso 2013-2014

Prácticas de Algoritmos y Estructuras de Datos II

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

Profesor de Teoría Norberto Marín, de prácticas Domingo Giménez.

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

Tutoríasde prácticas martes, miércoles y jueves de 12 a 14 (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. A partir de una cierta nota en esa prueba se puede no realizar el parcial de Análisis de Algoritmos, y a partir de otra nota se puede optar por hacer la media entre la nota de la prueba y la del parcial.

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, ya sea no teniendo que realizar el problema o obteniéndose la nota en ese problema con la media entre lo obtenido en la prueba y en el problema del examen.

La segunda práctica estará dedicada a avance rápido, backtracking y ramificación y poda.

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

febrero 2014

                                                                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

• 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.

Tema 6: Branch and Bound:
Estrategias FIFO, LIFO, LC, LC-FIFO, LC-LIFO.
Secuenciamiento de trabajos.
Problema de la mochila.

·           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.