Requisitos previos

Es muy recomendable que el alumno haya adquirido las competencias
correspondientes a las materias de los dos primeros cursos, así como que sepa
expresarse con fluidez, corrección y precisión en español.

Recomendaciones

Haber superado las siguientes asignaturas y mantener la destreza necesaria en las
materias objeto de su estudio.

- Introducción a la Programación
- Matemática Discreta
- Metodología de la Programación
- Sistemas Operativos
- Análisis de Algoritmos y Estructuras de Datos
- Estructuras de Datos no Lineales
- Programación Orientada a Objetos

En particular, el alumno debe saber cómo resolver las sumas y ecuaciones de
recurrencia fundamentales, así como poseer una práctica fluida en el diseño
iterativo y recursivo elemental, las técnicas de transformación, la programación
en lenguaje C++ y el manejo de las herramientas básicas de programación
disponibles a través de un intérprete de órdenes en un sistema operativo
GNU/Linux.

Por último, se recomienda poseer los suficientes conocimientos de lengua inglesa
como para, al menos, ser capaz de leer y comprender los materiales y bibliografía
recomendados.

Profesores

Nombre	Apellido 1	Apellido 2	C.C.E.	Coordinador
PABLO	DE LA TORRE	MORENO	PROFESOR SUSTITUTO INTERINO	N
PEDRO	FERNANDEZ	FERNANDEZ	PROFESOR ASOCIADO	N
FRANCISCO	PALOMO	LOZANO	TEU	S
ALBERTO GABRIEL	SALGUERO	HIDALGO	PROFESOR SUSTITUTO INTERINO	N

Competencias

Se relacionan aquí las competencias de la Materia/módulo o título a que pertenece la asignatura, entre las que el profesor podrá indicar las relacionadas con la asignatura.

Resultados Aprendizaje

Actividades formativas

En las clases de teoría se aprenderán los
fundamentos teóricos de la materia y se
ilustrarán sus conceptos mediante ejemplos
paradigmáticos.

En las clases de problemas se aplicarán los
conocimientos aprendidos en las clases de teoría
a la resolución de problemas relacionados.

Las clases prácticas se desarrollarán en un
laboratorio de informática. Previamente se
proporcionará a los alumnos a través del campus
virtual un guión de las actividades a realizar.
Cada guión podrá abarcar varias sesiones de
laboratorio y contendrá ejercicios en los que
habrá que programar los algoritmos pertinentes
como forma de resolver los problemas planteados.

Estas actividades engloban la dedicación personal
al estudio del alumno, que debe incluir tanto el
repaso de los materiales suministrados, como la
resolución de problemas y la realización de
prácticas de programación.

Exámenes escritos.

Evaluación

Criterios Generales de Evaluación

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

Se prestará especial atención a la capacidad del alumno para explicar las
soluciones desarrolladas claramente, con precisión, sin errores gramaticales ni
ortográficos. Una mera solución sin explicación o justificación podrá no ser
tenida en cuenta.

En el caso de programas de ordenador, estos deberán estar escritos conforme al
estándar en uso del lenguaje y poseer un comportamiento inequívocamente definido.

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.

Procedimiento de Evaluación

Procedimiento de calificación

Las calificaciones se otorgarán mediante un sistema de evaluación continua en el
que la nota final de la asignatura se calculará mediante la siguiente fórmula:

NF = 0,75 NT + 0,25 NP

donde:

1. NT es la nota de teoría: la media en una escala de 0 a 10 de las
calificaciones obtenidas en los exámenes parciales durante el curso o, en el caso
de examen final, la nota de dicho examen, con la salvedad de la primera
convocatoria, que se corresponderá con el último examen parcial.
2. NP es la nota de prácticas: la media en una escala de 0 a 10 de las
calificaciones de las prácticas desarrolladas durante el curso.

La presentación de memorias por cada práctica a través del campus virtual en las
fechas indicadas por el profesor es obligatoria. Con carácter general, las
prácticas no serán recuperables, NI SIQUIERA EN LOS EXÁMENES FINALES. Así, la NP
que se obtenga durante el curso será la que se mantenga para todas las
convocatorias de dicho curso académico.

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 que no presenten alguna de las memorias de prácticas, obtendrán una
calificación de 0 en su NP.

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á una calificación de 0 en su NP.

Descripcion de los Contenidos

            Bloque 1. Algoritmos de divide y vencerás.

Sesiones de teoría y problemas:

- Esquema general.
- Reducción: búsqueda binaria, potencia rápida.
- Equilibrado: extremos, ordenación por fusión.
- Partición: ordenación rápida, selección rápida.

Sesiones de laboratorio:

- Potencia rápida de una matriz.
- Ordenación por fusión frente a ordenación rápida.
- Influencia del umbral.

        

            Bloque 2. Algoritmos devoradores.

Sesiones de teoría y problemas:

- Esquema general.
- El problema del cambio de moneda.
- El problema de la mochila.
- El problema del árbol de expansión mínimo.
- Caminos mínimos desde un vértice a todos los demás.

Sesiones de laboratorio:

- Simulación del reintegro en un cajero automático.
- Trazado de líneas de comunicación de coste mínimo.
        

            Bloque 3. Programación dinámica.

Sesiones de teoría y problemas:

- Diseño descendente: funciones con memoria.
- Diseño ascendente: tabla de subproblemas resueltos.
- Ejemplos numéricos.
- Principio de optimalidad.
- El problema del cambio de moneda.
- El problema de la mochila.
- Caminos mínimos entre todas las parejas de vértices.
- Clausura reflexiva y transitiva.

Sesiones de laboratorio:

- Impacto de la memorización.
- Aprovechamiento óptimo de espacios publicitarios.
- Planificación de rutas por carretera de coste mínimo.

        

            Bloque 4. Exploración en grafos.

Sesiones de teoría y problemas:

- Recorridos de un grafo: aplicaciones, ordenación topológica.
- Búsqueda con retroceso.
- Ramificación y acotación.

Sesiones de laboratorio:

- Secuenciación de tareas interdependientes
- Resolución del problema de las n damas.
- Asignación óptima de recursos en proyectos.

        

Bibliografía

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] Sedgewick, Robert y Wayne, Kevin.
     Algorithms.
     Addison-Wesley. 4ª ed. 2011.
     Material complementario en http://www.cs.princeton.edu/algs4.

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

Bibliografía Específica

[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] Parberry, Ian y Gasarch, William.
    Problems on algorithms.
    http://www.eng.unt.edu/ian/books/free/poa.pdf. 2002.
   
[9] Lippman, Stanley B.; Lajoie, Josée y Moo, Barbara E.
    C++ Primer.
    Addison-Wesley. 5ª ed. 2012.

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

Bibliografía Ampliación

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

[2] Kao, Ming-Yang (ed.)
    Encyclopedia of algorithms.
    Springer. 2008.

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