Algoritmos avanzados

Máster Oficial en Sistemas Telemáticos e Informáticos

Universidad Rey Juan Carlos

[ Foro de la asignatura ]

Ya están disponibles las notas en gsyc.es/~anto/adv-alg/notas.pdf. Si alguien quiere revisar algún ejercicio que se ponga en contacto conmigo cuanto antes por correo electrónico.

Si hay alguien que piense presentarse a la convocatoria de junio/julio (antes llamada de septiembre) que se ponga en contacto conmigo.

Índice General

• Información de la asignatura
  • Lugar y fechas de impartición
  
  
• Evaluación
• Temario tentativo
• Calendario
• Asignaciones
• Bibliografía básica
• Bibliografía
• Bibliografía adicional
• Bibliografía

Información de la asignatura

• Créditos: 3.
• Profesorado: Antonio Fernández Anta, ed. Departamental II, Despacho 134. anto@gsyc.es.
• Tipo: Obligatoria
• Cuatrimestre: Segundo.

Lugar y fechas de impartición

Aula 204, Aulario III, Campus de Móstoles.

Martes de 16:00 a 18:00 h.

Evaluación

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.

Temario tentativo

1. Introducción (Capítulos 1 y 2 de Cormen et al.)
2. Complejidad asintótica (Capítulo 3 de Cormen et al.)
3. Recurrencias (Capítulo 4 de Cormen et al., excepto 4.4)
4. Algoritmos probabilistas y análisis probabilista (Capítulo 5 de Cormen et al.)
5. Algoritmos con programación dinámica (Capítulo 15 de Cormen et al.)
6. Algoritmos en redes (Sección VI de Cormen et al.)
7. Programación lineal (Capítulo 29 de Cormen et al.)
8. Problemas NP-completos (Capítulo 34 de Cormen et al.)
9. Algoritmos de aproximación (Capítulo 35 de Cormen et al.).
10. Aproximación con cotas de Chernoff y dealeatorización. Notas de Goemans.

Calendario

• 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.
• 16-3-2010: Luis López presenta conceptos de redes libres de escala y de pequeño mundo. Utiliza este artículo: [3].
• 23-3-2010: Cubrimos el Capítulo 15.
• 6-4-2010: Cubrimos los Capítulos 22 (excepto 22.4 y 22.5) y 23.
• 13-4-2010: Cubrimos el Capítulo 24 (excepto 24.2, 24.4 y 24.5).
• 20-4-2010: Cubrimos el Capítulo 25 (excepto 25.3).
• 27-4-2010: Cubrimos el Capítulo 34.
• 4-5-2010: Cubrimos el Capítulo 35.

Asignaciones

1. 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).
2. Asignación 2: Resolver el Ejercicio 2.1-3 a entregar el 23-2-2010 en clase o por correo-e (en formato PDF).
3. Asignación 3: Resolver el Problema 3-2 a entregar el 9-3-2010 en clase o por correo-e (en formato PDF).
4. Asignación 4: Resolver el Problema 4-1 a entregar el 16-3-2010 por correo-e (en formato PDF).
5. Asignación 5: Resolver el Ejercicio 5.2-3 a entregar el 23-3-2010 por correo-e (en formato PDF).
6. Asignación 6: Resolver el Problema 15-6 a entregar el 13-4-2010 por correo-e (en formato PDF).
7. Asignación 7: Resolver los Ejercicios 24.1-1 y 24.3-1 a entregar el 27-4-2010 por correo-e (en formato PDF).
8. Asignación 8: Resolver los Ejercicios 25.1-1 y 25.2-1 a entregar el 4-5-2010 por correo-e (en formato PDF).
9. Asignación 9: Resolver el Ejercicio 34.5-6 a entregar el 11-5-2010 por correo-e (en formato PDF).
10. Asignación 10: Resolver el Ejercicio 35.2-3 (suponer que se cumple la propiedad triangular) a entregar el 18-5-2010 por correo-e (en formato PDF).

Bibliografía básica

Bibliografía

CLRS

Cormen, Leiserson, Rivest, and Stein. Introduction to Algorithms, 2nd edition, MIT Press.

Goemans

Michel X. Goemans. Advanced Algorithms, Lecture notes, MIT.

Bibliografía adicional

Bibliografía

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

Réka Albert Albert-László Barabási. "Statistical mechanics of complex networks", Rev. Mod. Phys. 74, 47–97, 2002. PDF

4

Michael Mitzenmacher and Eli Upfal. Probability and Computing: an introduction to randomized algorithms and probabilistic analysis, Cambridge University Press (January 31, 2005), ISBN: 0521835402.

5

Rajeev Motwani and Prabhakar Raghavan. Randomized Algorithms, Cambridge University Press, 1995. ISBN: 0521474655.

6

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.

7

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.

8

Ronald Graham, Oren Patashnik, Donald Ervin Knuth. Concrete Mathematics: A Foundation for Computer Science (2nd Edition), Addison-Wesley Pub Co, ISBN: 0201558025, February 1994.

Sobre este documento...

Algoritmos avanzados

This document was generated using the LaTeX2HTML translator Version 2002-2-1 (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 on 2010-06-04