Algoritmos avanzados
- Créditos: 3.
- Profesorado: Antonio Fernández Anta, ed. Departamental II,
Despacho 134.
anto@gsyc.es.
- Tipo: Obligatoria
- Cuatrimestre: Segundo.
Aula 204, Aulario III, Campus de Móstoles.
Martes de 16:00 a 18:00 h.
Trabajo en casa: 100 %.
Cada trabajo para casa tiene una fecha de entrega. Los trabajos
entregados en fecha se puntuarán de 0 a 10. Los trabajos entregados hasta 4
semanas después de esa fecha se puntuarán de 0 a 8 para la convocatoria de mayo.
Los entregados más tarde ya sólo serán válidos para la convocatoria de junio.
- Introducción (Capítulos 1 y 2 de Cormen et al.)
- Complejidad asintótica (Capítulo 3 de Cormen et al.)
- Recurrencias (Capítulo 4 de Cormen et al., excepto 4.4)
- Algoritmos probabilistas y análisis probabilista (Capítulo 5 de Cormen et al.)
- Hashing (Capítulo 11 de Cormen et al.)
- Algoritmos en redes (Sección VI de Cormen et al.)
- Programación lineal (Capítulo 29 de Cormen et al.)
- Problemas NP-completos (Capítulo 34 de Cormen et al.)
- Algoritmos de aproximación (Capítulo 35 de Cormen et al.).
- Aproximación con cotas de Chernoff y dealeatorización. Notas
de Goemans.
- 4-2-2010:
Empezamos con el Capítulo 1.
- 9-2-2010:
Completamos el Capítulo 1 y comenzamos con el 2.
- 16-2-2010:
Completamos el Capítulo 2. Hacemos hincapié en los invariantes de bucle.
- 23-2-2010:
Cubrimos el Capítulo 3.
- 2-3-2010:
Cubrimos el Capítulo 4. No vemos la Sección 4.4.
- 9-3-2010:
Cubrimos el Capítulo 5. No vemos la Sección 5.4.
Asignaciones
- Asignación 1:
- Leer el cuento [2]. No hay que entregar nada.
- Resolver los Ejercicios 1.1-5 y 1.2-3 a entregar el 16-2-2010 en clase o por correo-e (en formato PDF).
- Asignación 2: Resolver el Ejercicio 2.1-3 a entregar el 23-2-2010 en clase o por correo-e (en formato PDF).
- Asignación 3: Resolver el Problema 3-2 a entregar el 9-3-2010 en clase o por correo-e (en formato PDF).
- Asignación 4: Resolver el Problema 4-1 a entregar el 16-3-2010 por correo-e (en formato PDF).
- Asignación 5: Resolver el Ejercicio 5.2-3 a entregar el 23-3-2010 por correo-e (en formato PDF).
- CLRS
-
Cormen, Leiserson, Rivest, and Stein. Introduction to Algorithms,
2nd
edition, MIT Press.
- Goemans
-
Michel X. Goemans. Advanced
Algorithms,
Lecture notes, MIT.
-
- 1
-
Jon Kleinberg, Éva Tardos.
Algorithm Design,
Addison Wesley (March 16, 2005),
ISBN: 0321295358.
- 2
-
Isaac Asimov. "Profesión",
Cuentos Completos I,
Ediciones B, 2005.
PDF
- 3
-
Michael Mitzenmacher and Eli Upfal.
Probability and Computing: an introduction to randomized algorithms and
probabilistic analysis, Cambridge University Press (January 31, 2005),
ISBN: 0521835402.
- 4
-
Rajeev Motwani and Prabhakar Raghavan.
Randomized Algorithms, Cambridge University Press, 1995.
ISBN: 0521474655.
- 5
-
Michael R. Garey and David S. Johnson. Computers and
Intractability: A Guide to the Theory of NP-Completeness, W.H.
Freeman & Co., San Francisco, 1979.
- 6
-
Joel Spencer. Ten Lectures on the Probabilistic Method, Second Edition, CBMS-NSF
Regional Conference Series in Applied Mathematics, No 64,
Society for Industrial and Applied Mathematics (SIAM), 1994.
- 7
-
Ronald Graham, Oren Patashnik, Donald Ervin Knuth. Concrete
Mathematics: A Foundation for Computer Science (2nd Edition),
Addison-Wesley Pub Co, ISBN: 0201558025, February 1994.
Algoritmos avanzados
This document was generated using the
LaTeX2HTML translator Version 2008 (1.71)
Copyright © 1993, 1994, 1995, 1996,
Nikos Drakos,
Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999,
Ross Moore,
Mathematics Department, Macquarie University, Sydney.
The command line arguments were:
latex2html -no_navigation -split 0 index
The translation was initiated by Antonio Fernandez Anta on 2010-03-09
Antonio Fernandez Anta
2010-03-09