José Fidel Argudo Argudo
Francisco Palomo Lozano (coordinador)

Los objetivos que pretende cubrir la asignatura pueden resumirse en los
siguientes puntos:

1. Partiendo del análisis de algoritmos clásicos el alumno aprenderá a
continuación una serie de técnicas que le han de permitir diseñar sus
propios algoritmos. Se insistirá especialmente en el concepto de eficiencia
computacional.

2. Mostrar los detalles de realización de los algoritmos explicados en clase
aplicándolos a la resolución de problemas reales.

Teoría: Diseño de algoritmos. (30h)

1. Algoritmos de divide y vencerás. (8h)
1.1. Esquema general.
1.2. Reducción: búsqueda binaria y potencia rápida.
1.3. Equilibrado: ordenación por fusión.
1.4. Partición: ordenación rápida.

2. Algoritmos devoradores. (8h)
2.1. Esquema general.
2.2. El problema del cambio de moneda.
2.3. El problema de la mochila.
2.4. El problema del árbol de expansión mínimo.
2.5. Caminos mínimos desde un vértice a todos los demás.

3. Programación dinámica. (8h)
3.1. Diseño descendente: funciones con memoria.
3.2. Diseño ascendente: tabla de subproblemas resueltos.
3.3. Ejemplos numéricos.
3.4. El principio de optimalidad.
3.5. El problema del cambio de moneda.
3.6. El problema de la mochila.
3.7. Caminos mínimos entre todas las parejas de vértices.
3.8. Clausura reflexiva y transitiva.

4. Exploración en grafos. (6h)
4.1. Ordenación topológica.
4.2. Búsqueda con retroceso.
4.3. Ramificación y acotación.

Prácticas: Programación y análisis híbrido de algoritmos. (15h)

1. Algoritmos de divide y vencerás. (3h)
1.1. Potencia rápida de una matriz.
1.2. Ordenación por fusión frente a ordenación rápida.
1.3. Influencia del umbral.

2. Algoritmos devoradores. (4h)
2.1. Simulación del reintegro en un cajero automático.
2.2. Trazado de líneas de comunicación de coste mínimo.

3. Programación dinámica. (4h)
3.1. El problema de la mochila discreta.
3.2. Planificación de rutas por carretera de coste mínimo.

4. Exploración en grafos. (4h)
4.1. El problema de las n damas.
4.2. El problema de asignación.

Las clases teóricas constarán fundamentalmente de las explicaciones del
profesor y, ocasionalmente, de resúmenes escritos o ampliaciones de temas
específicos. Los contenidos teóricos se completarán con problemas que serán
propuestos convenientemente a los alumnos. Los más importantes se resolverán
en clase.

Las clases prácticas complementan los contenidos de la parte teórica.  Se
proporcionarán enunciados de las prácticas y ejercicios que se desarrollarán
en el laboratorio a lo largo del curso.

Tanto las  clases teóricas como las  prácticas se servirán  del campus virtual
como apoyo para la  docencia. Estarán disponibles herramientas de comunicación
como foros  especializados y correo electrónico, así  como diversos contenidos
en formato electrónico.

La evaluación de la asignatura se realizará de acuerdo con las convocatorias
de exámenes finales que establecen los Estatutos de la Universidad de Cádiz. A
este efecto, la asignatura se divide en dos partes, correspondientes a la
teoría y la práctica. La superación de la asignatura requiere la de ambas por
separado. La parte práctica sólo será calificada si se supera la teórica. En
caso de superarse únicamente la parte teórica, se mantendrá su calificación
durante las restantes convocatorias del curso académico.

La parte teórica constará de un examen escrito calificable en una escala de
0 a 10. La parte práctica consistirá en la entrega de una memoria de
prácticas calificable como APTO o NO APTO. A este efecto, el alumno debe
desarrollar una memoria de prácticas durante el curso, resolviendo en cada
práctica los ejercicios indicados y consultando con el profesor los problemas
que puedan surgirle en su realización.

La calificación final se calculará de acuerdo con la siguiente fórmula:

Si CP = APTO,  CF = CT
Si CP = NO APTO, CF =  min{4, CT}

donde CF, CT y CP son, respectivamente, la calificación final, la teórica y la
práctica.

El profesor valorará no sólo la corrección y eficiencia de las soluciones
presentadas, sino también la claridad y elegancia de su desarrollo.

Bibliografía básica.

Brassard, Gilles y Bratley, Paul.
Fundamentos de algoritmia.
Prentice-Hall. 1997.

Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. y
Stein, Clifford.
Introduction to algorithms.
MIT Press. 2ª ed. 2001.

Johnsonbaugh, Richard y Schaefer, Marcus.
Algorithms.
Prentice-Hall. 2004.

Levitin, Anany V.
Introduction to the design and analysis of algorithms.
Addison-Wesley. 2003.

Manber, Udi.
Introduction to algorithms. A creative approach.
Addison-Wesley. 1989.

Martí Oliet, Narciso; Ortega Mallén, Yolanda y Verdejo López, José Alberto.
Estructuras de datos y métodos algorítmicos. Ejercicios resueltos.
Prentice-Hall. 2004.

Neapolitan, Richard y Naimipour, Kumarss.
Foundations of algorithms.
Jones and Bartlett. 2ª ed. 1998.

Sedgevick, Robert.
Algorithms in C++. Parts 1-4. Fundamentals. Data
Structures. Sorting. Searching.
Addison-Wesley. 3ª ed. 1999.

Sedgevick, Robert.
Algorithms in C++. Part 5. Graph algorithms.
Addison-Wesley. 3ª ed. 2002.

Bibliografía complementaria

Aho, Alfred; Hopcroft, John y Ullman, Jeffrey.
The design and analysis of computer algorithms.
Addison-Wesley. 1974.

Baase, Sara y Van Gelder, Allen.
Computer algorithms. Introduction to design and analysis.
Addison-Wesley. 3ª ed. 2000.

Brassard, Gilles y Bratley, Paul.
Algorítmica. Concepción y análisis.
Masson. 1990.

Horowitz, Ellis y Sahni, Sartaj.
Fundamentals of computer algorithms.
Pitman. 1978.

McHugh, James A.
Algorithmic graph theory.
Prentice-Hall. 1990.

Parberry, Ian.
Problems on algorithms.
Prentice-Hall. 1995.

Skiena, Steven S.
The algorithm design manual.
Telos. 1998.

Stroustrup, Bjarne.
The C++ programming language. Special edition.
Addison-Wesley. 2000.

Wilf, Herbert S.
Algorithms and complexity.
A. K. Peters. 2ª ed. 2002.

Bibliografía especializada de consulta

Garey, Michael R. y Johnson, David S.
Computers and intractability. A guide to the theory of
NP-completeness.
W. H. Freeman. 1979.

Graham, Ronald L.; Knuth, Donald E. y Patashnik, Oren.
Concrete mathematics. A foundation for Computer Science.
Addison-Wesley. 2ª ed. 1994.

Knuth, Donald E.
The art of computer programming.
Volume I. Fundamental algorithms.
Addison-Wesley. 3ª ed. 1997.

Knuth, Donald E.
The art of computer programming.
Volume II. Seminumerical algorithms.
Addison-Wesley. 3ª ed. 1997.

Knuth, Donald E.
The art of computer programming.
Volume III. Sorting and searching.
Addison-Wesley. 2ª ed. 1997.

Sedgevick, Robert y Flajolet, Philippe.
An introduction to the analysis of algorithms.
Addison-Wesley. 1996.