Profesorado

José Fidel Argudo Argudo
Antonio García Domínguez
Francisco Palomo Lozano (coordinador)

Situación

Prerrequisitos

1. Haber aprobado las siguientes asignaturas de primer curso:

- Álgebra.
- Cálculo.
- Matemática discreta.
- Introducción a la Programación.
- Metodología de la Programación.
- Estructura de Datos I.

En especial, se asume que el alumno tiene conocimientos sobre la resolución
de sumatorios y ecuaciones de recurrencia.

2. Cursar o haber aprobado las siguientes asignaturas de segundo curso:

- Estructura de Datos II.

3. Poseer conocimientos de lengua inglesa.

Contexto dentro de la titulación

Esta asignatura es la continuación natural de la asignatura de análisis y
diseño de algoritmos de primer cuatrimestre.

Recomendaciones

Las indicadas en los prerrequisitos.

Competencias

Competencias transversales/genéricas

- Análisis y síntesis.
- Razonamiento abstracto.
- Pensamiento crítico.
- Resolución de problemas.
- Planificación y organización.
- Comunicación y trabajo en equipo.
- Expresión oral y escrita.
- Preparación y presentación de documentación técnica.

Competencias específicas

• Cognitivas(Saber):

  - Conocer las principales técnicas de diseño de algoritmos.
  - Conocer los algoritmos paradigmáticos de las distintas técnicas.
  - Conocer los algoritmos fundamentales de la biblioteca STL.
  - Conocer algunas aplicaciones de los algoritmos explicados en clase
  a problemas reales.
  

• Procedimentales/Instrumentales(Saber hacer):

  - Diseñar y analizar algoritmos empleando distintas técnicas.
  - Distinguir, para problemas sencillos, qué técnica de diseño es la
  más apropiada para su resolución.
  

• Actitudinales:

  - Apreciar las ventajas del empleo de diversas herramientas de
  software libre.
  - Valorar la importancia de consultar con soltura bibliografía y
  otros materiales en lengua inglesa.
  - Estar dispuesto a buscar y contrastar información de diversas
  fuentes de manera independiente.
  - Ser consciente de la necesidad de abordar nuevos problemas y
  evaluar posibles soluciones con espíritu crítico.
  - Apreciar las ventajas de trabajar cooperativamente en pequeños
  grupos, comunicando ideas con claridad y rigor.
  

Objetivos

Adquirir las competencias específicas reseñadas.

Programa

Teoría: Diseño de algoritmos.

1. Algoritmos de divide y vencerás.
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.
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.
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.
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.

1. Algoritmos de divide y vencerás.
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.
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.
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.
4.1. El problema de las n damas.
4.2. El problema de asignación.

Actividades

1. Resolución de problemas seleccionados del primer tema.

2. Resolución de problemas seleccionados del segundo tema.

3. Resolución de problemas seleccionados del tercer tema.

4. Resolución de problemas seleccionados del cuarto tema.

Metodología

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.

Distribución de horas de trabajo del alumno/a

Nº de Horas (indicar total): 87,5

• Clases Teóricas: 22  
• Clases Prácticas: 13  
• Exposiciones y Seminarios:  
• Tutorías Especializadas (presenciales o virtuales):
  • Colectivas:  
  • Individules:  
• Realización de Actividades Académicas Dirigidas:
  • Con presencia del profesorado: 10  
  • Sin presencia del profesorado: 11,5  
• Otro Trabajo Personal Autónomo:
  • Horas de estudio: 28  
  • Preparación de Trabajo Personal:  
  • ...
     
• Realización de Exámenes:
  • Examen escrito: 3  
  • Exámenes orales (control del Trabajo Personal):  

Técnicas Docentes

- Resolución de ejercicios por parejas.
- Sesiones de evaluación/coevaluación.

Criterios y Sistemas de Evaluación

CRITERIOS DE EVALUACIÓN

Los profesores valorarán no sólo la corrección y eficiencia de las soluciones
obtenidas, sino también aspectos subjetivos como la presentación, claridad y
elegancia de su desarrollo en los que se incidirá durante todo el curso.

La nota final de la asignatura se calculará mediante el siguiente algoritmo:

si NFT < 5 v NGP = "APTO"
NFA <- NFT
si no
NFA <- 4

donde:

1. NFT es la nota final de teoría.
2. NGP es la nota global de prácticas.
3. NFA es la nota final de la asignatura.

La nota global de prácticas será de "APTO" o "NO APTO". En general, 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. En caso de ser convocados a defensa, los alumnos
deberán acudir portando copias impresas de las memorias entregadas
electrónicamente. El desconocimiento de las cuestiones planteadas implicará un
"NO APTO".

Los alumnos deben asegurarse de realizar correctamente las entregas
electrónicas a través del campus virtual en tiempo y forma. En particular,
deben observarse estrictamente las normas de entrega publicadas en el campus
virtual.

Los alumnos deben comprobar periódicamente el estado del curso en el campus
virtual, donde se publicarán con la debida antelación diversos materiales
docentes, convocatorias, calificaciones y, en definitiva, información vital
para el seguimiento de la asignatura.

En particular, los alumnos tienen la obligación de conocer las noticias
publicadas a través del tablón de anuncios virtual del curso, cuyos mensajes
sustituyen a los que tradicionalmente se colocaban en un tablón físico y que
se consideran la fuente oficial de comunicación de la asignatura.

Los alumnos son responsables de proteger sus ficheros y datos personales,
incluyendo sus contraseñas de acceso al correo electrónico y al campus
virtual.

La copia total o parcial de exámenes o prácticas, así como cualquier otro tipo
de fraude detectado por los profesores, podrá ser motivo de SUSPENSO INMEDIATO
EN TODAS LAS CONVOCATORIAS del curso académico para todos los implicados, sea
cual fuere su papel. En particular, se informa de que las entregas
electrónicas podrán almacenarse durante un plazo de 5 años para ulteriores
comprobaciones.

SISTEMAS DE EVALUACIÓN

Para la primera convocatoria se dispone de dos sistemas de evaluación
diferentes: evaluación continua y evaluación final. Para las restantes
convocatorias, que se encuentran fuera del periodo docente de la asignatura,
se utilizará exclusivamente el sistema de evaluación final. No se guardará
ningún tipo de calificación parcial entre convocatorias.

El alumno que se presente a algún control del sistema de evaluación continua
se encontrará automáticamente asignado a dicho sistema y 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.

Los profesores recomiendan, siempre que sea posible, acogerse al sistema de
evaluación continua.

SISTEMA DE EVALUACIÓN FINAL

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

1. Examen final de teoría.
2. Evaluación global de las prácticas.

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.

En este sistema, la NFT corresponderá a la calificación de dicho examen, que
se realizará en una escala de 0 a 10.

Para la evaluación global de las prácticas, los alumnos deberán presentar una
memoria final de prácticas a través del campus virtual en las fechas indicadas
por el profesor.

SISTEMA DE EVALUACIÓN CONTINUA

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

1. Evaluación continua de teoría.
2. Evaluación global de las prácticas.

A lo largo del curso se realizarán varios controles de teoría. 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, 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 una
diferencia significativa e injustificada en la puntuación otorgada, los
controles de los alumnos correctores se calificarán con 0.

En este sistema, la NFT 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 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 presenta alguna de las memorias en tiempo y forma, obtendrá
un "NO APTO" en su NGP.

Recursos Bibliográficos

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. 3ª ed. 2009.

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

[4] Kleinberg, Jon y Tardos Éva.
Algorithm Design.
Addison-Wesley. 2005.

[5] Levitin, Anany V.
Introduction to the design and analysis of algorithms.
Addison-Wesley. 2ª ed. 2007.

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

[7] Neapolitan, Richard y Naimipour, Kumarss.
Foundations of algorithms.
Jones and Bartlett. 4ª ed. 2009.

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

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

[10] Sedgewick, Robert y Wayne, Kevin.
Algorithms.
Addison-Wesley. 4ª ed. 2011.
Material complementario en http://www.cs.princeton.edu/algs4.

[11] Skiena, Steven S.
The algorithm design manual.
Springer. 2ª ed. 2008.

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] Brassard, Gilles y Bratley, Paul.
Algorítmica. Concepción y análisis.
Masson. 1990.

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

[5] Horowitz, Ellis; Sahni, Sartaj y Rajasekaran, Sanguthevar.
Computer algorithms / C++.
Universities Press. 2ª ed. 2008.

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

[7] Martí Oliet, Narciso; Segura Díaz, Clara M. y Verdejo López, José A.
Especificación, derivación y análisis de algoritmos. Ejercicios resueltos.
Prentice-Hall. 2007.

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

[9] Parberry, Ian y Gasarch, William.
Problems on algorithms.
http://www.eng.unt.edu/ian/books/free/poa.pdf. 2002.

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

[11] Stroustrup, Bjarne.
Programming: Principles and practice using C++.
Addison-Wesley. 2008.

[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] Kao, Ming-Yang (ed.)
Encyclopedia of algorithms.
Springer. 2008.

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

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

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

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