José Antonio Alonso de la Huerta
Francisco Palomo Lozano (coordinador)
José Santamaría López

Al término de la asignatura, los alumnos deberán ser capaces de:

- Distinguir entre la complejidad de los problemas y la de los algoritmos,
tener conciencia de la existencia de una jerarquía de complejidad y de
problemas intratables.

- Comparar algoritmos según su complejidad asintótica y otros criterios
relevantes.

- Analizar matemáticamente la complejidad espacio-temporal de
algoritmos elementales.

- Analizar empíricamente la complejidad temporal de los algoritmos y
contrastar
los resultados experimentales con los teóricos.

- Relacionar la eficiencia de los programas con la de sus algoritmos.

- Programar algoritmos en el laboratorio siguiendo el paradigma de la
programación genérica.

- Conocer los aspectos básicos de C++ como mejora del lenguaje C y los
elementos fundamentales de la biblioteca STL.

- Manejar diversas herramientas de software libre.

- Consultar con soltura bibliografía y otros materiales en lengua inglesa.

- Buscar y contrastar información de diversas fuentes de manera
independiente.

- Abordar nuevos problemas y evaluar posibles soluciones con espíritu
crítico.

- Trabajar cooperativamente en pequeños grupos, comunicando ideas con claridad
y rigor.

Teoría: Análisis de algoritmos. (30h)

1. Introducción y conceptos básicos. (4h)
1.1. Problemas, algoritmos y programas.
1.2. Lenguaje de especificación de algoritmos.
1.3. Corrección y eficiencia algorítmicas.
1.4. Ejemplo: algoritmo ruso de multiplicación.
1.5. Principio de invarianza.
1.6. Definición informal de orden asintótico.

2. Órdenes asintóticos. (4h)
2.1. Órdenes asintóticos.
2.2. Interpretación gráfica.
2.3. Jerarquía de complejidad.
2.4. Operaciones asintóticas.

3. Análisis de la complejidad de los algoritmos. (8h)
3.1. Tiempo y espacio algorítmicos.
3.2. Enfoques en el análisis de los algoritmos.
3.3. Peor caso, mejor caso y caso promedio.
3.4. Análisis de las estructuras de control.
3.5. Ejemplo: algoritmos elementales.

4. Algunos algoritmos clásicos y su análisis. (8h)
4.1. Búsqueda.
4.2. Métodos directos de ordenación por comparación.
4.3. Ordenación por montículo.
4.4. Componentes conexas con estructuras de partición.

5. Introducción al estudio de la complejidad de los problemas. (6h)
5.1. Problemas tratables e intratables.
5.2. Reducibilidad.
5.3. Clases de complejidad.

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

1. Introducción a la programación genérica con C++. (5h)
1.1. C++ como un C mejorado.
1.2. Programación genérica en C++.
1.3. Biblioteca STL.

2. Generación de ejemplares de prueba aleatorios. (2h)
2.1. Números pseudoaleatorios.
2.2. Permutaciones pseudoaleatorias.

3. Medida del tiempo de ejecución. (4h)
3.1. Tipos de medida.
3.2. Formas de medir el tiempo.
3.3. Factores que influyen en la medida.
3.4. Elección de los ejemplares de prueba.
3.5. Ejemplo: números de Fibonacci.

4. Comparación entre distintos algoritmos de ordenación. (4h)
4.1. Métodos directos de ordenación por comparación.
4.2. Algoritmos de ordenación de la biblioteca del lenguaje.

1. Conferencia de Richard M. Karp: NP-complete problems.

Esta conferencia, disponible en vídeo, expone magistralmente los conceptos
fundamentales asociados al estudio de la complejidad de los problemas, que
integran el último tema de teoría.

La conferencia se reproducirá en clase y será comentada por el profesor, que
suministrará con antelación su transcripción en el idioma original y resolverá
las dudas que puedan surgir con el idioma o los contenidos. Uno de los
objetivos de esta actividad es mejorar las capacidades de comprensión oral y
escrita de la lengua inglesa.

Los ejercicios del último tema versarán sobre el material expuesto en la
conferencia.

Se empleará una metodología cuyo objetivo es lograr el aprendizaje a través
de
la resolución de problemas. Las clases correspondientes a los créditos
teóricos
constarán, fundamentalmente, de sesiones de resolución de problemas
propuestos
con antelación en las que los alumnos podrán emplear cuantos materiales
estimen
convenientes.

Los alumnos deberán primero intentar resolver los problemas por sí mismos,
para
luego trabajar por parejas, explicándose mutuamente la solución obtenida e
intentando encontrar errores en la solución del compañero, o bien,
intentando
llegar juntos a una solución. Posteriormente, las soluciones se pondrán en
común en grupo y se invitará a su exposición. El objetivo es fomentar el
trabajo cooperativo, el espíritu crítico y la comunicación.

Se hará especial hincapié en la necesidad de comprobar la corrección de
la
solución final obtenida y su bondad respecto a distintos criterios, al
objeto
de fomentar el espíritu crítico.

El profesor expondrá los conocimientos teóricos y técnicos necesarios
bajo
demanda, conforme los alumnos los requieran para resolver los problemas
planteados, limitándose a actuar de guía en el proceso de aprendizaje. El
alumno es responsable de su propio aprendizaje.

No obstante, el profesor realizará al principio de cada tema una breve
introducción de sus aspectos principales y de dónde encontrar información
adicional, proporcionando diversos materiales como transparencias,
resúmenes,
gráficas y programas de computadora a lo largo del curso.

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, tutorías electrónicas privadas y correo
electrónico, así como diversos contenidos en formato digital.

El sistema de evaluación consta de tres componentes:

1. Evaluación continua de teoría
2. Examen final de teoría
3. Presentación y defensa de prácticas

La calificación final se obtiene de la siguiente forma:

NFT = 0,35 · NEC + 0,65 · NET
si NPR = APTO
NFA = NFT
si no
NFA = mín { NFT, 4 }

NFA: Nota final de la asignatura
NFT: Nota final de teoría
NEC: Nota de evaluación continua de teoría
NET: Nota del examen de teoría
NPR: Nota de prácticas

Los alumnos que justifiquen documentalmente la imposibilidad de asistir a
clase de teoría, y la comuniquen durante el primer mes de clase o en un plazo
de quince días naturales desde que surja tal imposibilidad, podrán solicitar
su renuncia al sistema de evaluación continua, en cuyo caso, NFT = NET.

Durante el curso se realizará una sesión de control tras determinados temas
de
teoría en fechas publicadas con suficiente antelación, empleando para ello
una
sesión de clase. Posteriormente, se dedicará una sesión a la coevaluación
cuyo
objetivo es presentar la solución y criterios de corrección con los que los
alumnos deberán calificar, bajo la supervisión del profesor, el examen de un
compañero elegido al azar.

La asistencia a las sesiones de control y coevaluación es obligatoria, ya que
forman parte del sistema de evaluación continua de la asignatura.

- Si un alumno no asiste a la sesión de control obtendrá un 0 como
calificación de su examen.

- Si un alumno no asiste a la sesión de coevaluación su examen no será
corregido, obteniendo en él un 0 como calificación, salvo justificación
documental oficial. Si tras revisar el resultado de una coevaluación los
profesores detectan negligencia o fraude, el alumno corrector obtendrá un 0
en
su propia calificación.

La calificación de la evaluación continua de teoría (NEC) será la
correspondiente, en una escala de 0 a 10, a la media aritmética de las
calificaciones de los controles que la conforman.

El examen de teoría será un examen escrito que se realizará de acuerdo con
las
convocatorias oficiales de exámenes finales que establecen los Estatutos de
la
Universidad de Cádiz y que el centro publica con la debida antelación. La
calificación del examen de teoría (NET) se realizará en una escala de 0 a 10.

La calificación de prácticas (NPR) será 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. El alumno podrá ser convocado
por el profesor para su defensa. El desconocimiento de las cuestiones
planteadas implicará que NPR = NO APTO.

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, aspectos
estos en los que se incidirá durante todo el curso.

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.

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.

Balcázar, José Luis.
Programación metódica.
McGraw-Hill. 1993.

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.

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

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

Peña Marí, Ricardo.
Diseño de programas. Formalismo y abstracción.
Prentice-Hall. 3ª ed. 2005.

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.