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.

ELECCIÓN DEL SISTEMA DE EVALUACIÓN

Para la primera convocatoria se dispone de dos sistemas de evaluación
diferentes: evaluación continua y evaluación final. Para el resto de
convocatorias, dado que ya no hay docencia, se utilizará exclusivamente la
evaluación final. No se guardará ningún tipo de calificación parcial entre
convocatorias.

Durante el primer mes del curso los alumnos que lo deseen deberán solicitar
explícitamente acogerse al sistema de evaluación continua, a través de una
consulta electrónica que se habilitará en el campus virtual. En caso de no
hacerlo, se entenderá que optan por evaluación final. No obstante, los
profesores recomiendan, siempre que sea posible, acogerse al sistema de
evaluación continúa.

Transcurrido este periodo, el alumno que haya optado por el sistema de
evaluación continua no podrá cambiar al sistema de evaluación final salvo por
causas sobrevenidas, justificadas documentalmente, que le imposibiliten la
asistencia a las clases y que sean comunicadas por correo electrónico al
profesor coordinador en un plazo de quince días naturales desde que surja tal
imposibilidad. A continuación se establecen las causas reconocidas y la
justificación documental exigible:

1. Problemas de salud: documento expedido por un facultativo médico
2. Contrato de trabajo: alta en la seguridad social y documento acreditativo
donde figure el periodo y el horario
3. Contrato de becario: documento acreditativo donde figure el periodo y el
horario

CÓDIGOS DE LAS DISTINTAS CALIFICACIONES

1. NEC: nota de evaluación continua
2. NET: nota del examen de teoría
3. NPR: nota de prácticas
4. NFT: nota final de teoría
5. NFA: nota final de la asignatura

SISTEMA DE EVALUACIÓN FINAL

El sistema de evaluación final consta de dos componentes:

1. Examen final de teoría
2. Memoria de prácticas y defensa

El examen final 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 final de teoría (NET) se realizará en
una escala de 0 a 10.

Los alumnos deberán presentar una memoria final de prácticas a través del
campus virtual en las fechas indicadas por el profesor.

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

NFT = NET
si NPR = APTO o NFT < 5
NFA = NFT
si no
NFA = 4

SISTEMA DE EVALUACIÓN CONTINUA

El sistema de evaluación continua consta de dos componentes:

1. Evaluación continúa
2. Memorias de prácticas y defensa

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

NFT = NEC
si NPR = APTO o NFT < 5
NFA = NFT
si no
NFA = 4

A lo largo del curso se realizarán varios controles. A cada control se
dedicará una sesión de control seguida de su correspondiente sesión de
coevaluación. Estas sesiones tendrán lugar durante las propias clases de
teoría, en fechas publicadas con suficiente antelación. En cada sesión de
coevaluación los alumnos deberán calificar, bajo la supervisión del profesor,
los ejercicios de dos compañeros elegidos al azar correspondientes al control
previo. Para ello, el profesor presentará una solución canónica y los
criterios de corrección a emplear.

La asistencia a las sesiones de control y coevaluación es obligatoria.

- Si un alumno no asiste a una sesión de control o de coevaluación, su control
se calificará con 0.

- Si tras revisar el resultado de una coevaluación los profesores detectan
negligencia o fraude, el control del alumno corrector se calificará con 0.

La calificación de la evaluación continua (NEC) será la correspondiente, en
una escala de 0 a 10, a la media aritmética de las calificaciones de los
controles que la integran, siempre que se cumplan los requisitos de asistencia
y de presentación de memorias de prácticas indicados.

La asistencia a prácticas y la presentación de memorias parciales por cada
práctica a través del campus virtual en las fechas indicadas por el profesor
es obligatoria.

- Si un alumno no asiste, al menos, al 75% de las clases prácticas,
contabilizadas tras el primer mes del curso, obtendrá un NO APTO en su NPR.

- Si un alumno no presenta alguna de las memorias, obtendrá un NO APTO en su
NPR.

NORMAS COMUNES PARA AMBOS SISTEMAS

La calificación de las prácticas (NPR) será APTO o NO APTO. Sólo se corregirán
las memorias de aquellos alumnos con NFT >= 5. Los alumnos podrán ser
convocados para la defensa de sus prácticas en determinadas fechas indicadas
por el profesor. A dicha defensa deberá acudir con una copia impresa de la
memoria (o memorias parciales, en el caso de evaluación continua) entregada
electrónicamente. El desconocimiento de las cuestiones planteadas implicará
que NPR = NO APTO.

CRITERIOS DE EVALUACIÓN

Entre los criterios de evaluación, cabe destacar que los profesores valorarán
no sólo la corrección y eficiencia de las soluciones presentadas, sino también
la claridad y elegancia de su desarrollo, aspectos éstos en los que se
incidirá durante todo el curso.

Bibliografía básica

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

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

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

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

[5] Neapolitan, Richard y Naimipour, Kumarss.
Foundations of algorithms using C++ pseudocode.
Jones and Bartlett. 3ª ed. 2004.

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

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

Bibliografía complementaria

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

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

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

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

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

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

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

[8] Parberry, Ian.
Problems on algorithms.
Prentice-Hall. 1995.

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

[10] Skiena, Steven S.
The algorithm design manual.
Telos. 1998.

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

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

Bibliografía especializada de consulta

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

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

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

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

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

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