Profesorado

Pedro Fernández Fernández
Antonio García Domínguez
Guadalupe Ortiz Bellot
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 las asignaturas de
programación y estructuras de datos de primero, complemento de las estructuras
de datos de segundo, así como un prerrequisito para el ulterior estudio de
técnicas más avanzadas de análisis y diseño de algoritmos.

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 la existencia de una jerarquía de complejidad.
  - Conocer la existencia de problemas intratables.
  - Conocer los principales algoritmos secuenciales.
  - Conocer el lenguaje C++ como mejora del lenguaje C.
  - Conocer los elementos fundamentales de la biblioteca STL.
  

• Procedimentales/Instrumentales(Saber hacer):

  - Distinguir la complejidad de los problemas, algoritmos y programas.
  - Comparar algoritmos según su complejidad asintótica y otros
  criterios relevantes.
  - Analizar matemáticamente la complejidad de algoritmos elementales.
  - Analizar empíricamente la complejidad temporal de los algoritmos.
  - Contrastar los resultados empíricos 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.
  

• 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: Análisis de algoritmos.

0. Introducción y conceptos básicos.
0.1. Problemas, algoritmos y programas.
0.2. Lenguaje de especificación de algoritmos.
0.3. Corrección y eficiencia algorítmicas.
0.4. Ejemplo: algoritmo ruso de multiplicación.
0.5. Principio de invarianza.
0.6. Definición informal de orden asintótico.

1. Órdenes asintóticos.
1.1. Órdenes asintóticos.
1.2. Interpretación gráfica.
1.3. Jerarquía de complejidad.
1.4. Operaciones asintóticas.

2. Análisis de la complejidad de los algoritmos.
2.1. Tiempo y espacio algorítmicos.
2.2. Enfoques en el análisis de los algoritmos.
2.3. Peor caso, mejor caso y caso promedio.
2.4. Análisis de las estructuras de control.
2.5. Ejemplo: algoritmos elementales.

3. Algunos algoritmos clásicos y su análisis.
3.1. Búsqueda.
3.2. Métodos directos de ordenación por comparación.
3.3. Ordenación por montículo.
3.4. Componentes conexas con estructuras de partición.

4. Introducción al estudio de la complejidad de los problemas.
4.1. Problemas tratables e intratables.
4.2. Reducibilidad.
4.3. Clases de complejidad.

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

1. Introducción a la programación genérica con C++.
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.
2.1. Números pseudoaleatorios.
2.2. Permutaciones pseudoaleatorias.

3. Medida del tiempo de ejecución.
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.
4.1. Métodos directos de ordenación por comparación.
4.2. Algoritmos de ordenación de la biblioteca del lenguaje.

Actividades

Examen final

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):  

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.

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] Levitin, Anany V.
Introduction to the design and analysis of algorithms.
Addison-Wesley. 2ª ed. 2007.

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

[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.

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

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.

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

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

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

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

[9] 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.

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

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

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

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

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

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

[16] 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.