RSS

5. Apuntes y Problemas de Algorítmica.

http://dis.um.es/~domingo/alg.html

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

  • Libro  Apuntes y Problema resueltos (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.

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

introducción

notaciones asintóticas

ecuaciones de recurrencia

divide y vencerás

avance rápido

programación dinámica

backtracking

branch and bound

  •   Lenguaje C

Enlace a un  tutorial de C

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

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

Primera práctica

Segunda práctica

 

Estamos en Contacto