Domingo Giménez Cánovas
DOCENCIA cursos anteriores
Algorítmica
segundo curso de Ingeniería Técnica de Gestión y Sistemas
3
créditos teóricos y 3 prácticos
Primer cuatrimestre
Apuntes (modificados a julio del 2001, contienen exámenes anteriores al 2001): postscript, pdf
Se ha editado un texto-guía de la asignatura de "Algoritmos y Estructuras de Datos" del plan nuevo. Uno de los tomos 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, NOTAS
examen de septiembre 2003: postscript, pdf, NOTAS
examen de diciembre 2003: postscript, pdf, NOTAS
examen de febrero 2004: postscript, pdf, NOTAS
parcial de algoritmos de AED, mayo 2004: postscript, pdf, NOTAS
final de AED, junio 2004 (en postscipt: enunciado, soluciones): NOTAS
final de AED, septiembre 2004 (en postscipt: enunciado, soluciones): NOTAS
Diciembre 2004 (el de diciembre de AED, que contiene la parte de algoritmos, en postscript): NOTAS
Examen 10 de junio, coincidiendo con el segundo parcial 2005, algoritmos, de AED, postscript, pdf, NOTAS.
Examen 28 de junio , postscript, pdf, NOTAS.
Examen 6 de septiembre 2005, pdf, NOTAS
Examen 1 de diciembre 2005, pdf , NOTAS
Examen febrero 2006, NOTAS
Examen parcial junio 2006, NOTAS
Examen final junio 2006, NOTAS
Examen septiembre 2011, parte de algoritmos, 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,
Transparencias en power point:
Lenguaje C
Enlace a un tutorial de C
Enlaces a la asignatura de ISO: apuntes de C , sobre make
Conexiones a otros cursos:
Curso de Richard Brent. En inglés
Curso de Khatib y Shoaff. En inglés
Curso de la Universidad Virtual, de Méjico
Prácticas
Son las del curso 2003/2004, que valen para la convocatoria de gracia de 2005. Los programas son en C sobre Linux, y hay que asegurarse de que funcionan bien en el Laboratorio 1.5. A partir de octubre del 2004 el profesor encargado de prácticas, tanto en Gestión como en Sistemas será Domingo Giménez.
PRÁCTICAS 2004-2005 (siguen siendo las mismas para la convocatoria de gracia de 2005)
TEMARIO:
Tema 1: Introducción.
1.1 Noción de algoritmo.
Algoritmos, programas y problemas.
Tema 2: Análisis de Algoritmos.
2.1 Notaciones asintóticas.
2.2 Resolución de ecuaciones recurrentes. Cambio de variable y
transformación de la imagen.
Tema 3: Diseño de Algoritmos.
3.1 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.
3.2 Algoritmos voraces:
Método general.
Problema de la
mochila.
Secuenciamiento de trabajos a plazos.
Heurísticas
voraces.
3.3 Programación dinámica:
Descripción.
Problema de la
mochila 0/1.
3.4 Backtracking:
Descripción.
Problema de las n reinas.
Problema de la mochila.
Análisis.
3.5 Branch and Bound:
Estrategias FIFO, LIFO, LC, LC-FIFO,
LC-LIFO.
Secuenciamiento de trabajos.
Problema de la mochila.
Tema 4: Complejidad Algorítmica.
4.1 Cota inferior de un
problema.
4.2 Equivalencia de problemas.
4.3 Clasificación
de problemas.
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.
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.