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 el módulo de formación básica y, al menos, las siguientes
asignaturas adicionales, además de mantener la destreza necesaria en las materias
objeto de su estudio.

- Sistemas Operativos
- Análisis de Algoritmos y Estructuras de Datos
- Estructuras de Datos no Lineales
- Programación Orientada a Objetos
- Diseño de Algoritmos
- Modelos de Computación

En particular, el alumno debe poseer una práctica fluida en el análisis de
algoritmos y estructuras de datos, las técnicas de diseño de algoritmos, 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
MANUEL JESUS	COBO	MARTIN	PROFESOR SUSTITUTO INTERINO	N
FRANCISCO	PALOMO	LOZANO	TEU	S

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. Introducción.

- Recursos computacionales: medidas de complejidad y jerarquía asintótica.
- Complejidad de los problemas: cotas inferiores y ejemplos.
- Tipos de problemas y clases de complejidad.
- Otros modelos (modelos no uniformes): complejidad de circuitos.
        

            Bloque 2. Clases P y NP.

- Problemas de búsqueda frente a problemas de decisión.
- P y NP vistas como clases de problemas de búsqueda.
- P y NP vistas como clases de problemas de decisión.
- Equivalencia de ambas visiones.
- Por qué es probable que P sea distinta de NP.
- Breve bosquejo de otras clases: complementarias, espaciales...
        

            Bloque 3. Reducciones polinómicas

- Noción general de reducción.
- Reducción de problemas de optimización a problemas de búsqueda.
- Reducciones polinómicas (en tiempo): ejemplos.
        

            Bloque 4. Clase NPC.

- Existencia de problemas NPC.
- Ejemplos de problemas NPC.
- Problemas NP que no son P ni NPC (si P es distinta de NP).

        

            Bloque 5. Técnicas para la resolución de problemas complejos.

- Fijación de parámetros.
- Aproximación.
- Aleatorización.
- Heurísticas.
        

Bibliografía

Bibliografía Básica

[1] Goldreich, Oded.
    P, NP, and NP-completeness. The basics of computational complexity.
    Cambridge University Press. 2010.

[2] Hromkovič, Juraj.
    Algorithmics for hard problems. Introduction to combinatorial optimization,
    randomization, approximation, and heuristics.
    Springer-Verlag. 2ª ed. Reimpresión corregida. 2004. 

Bibliografía Específica

[1] Arora, Sanjeev y Barak, Boaz.
    Computational complexity. A modern approach.
    Cambridge University Press. 2009.

[2] Goldreich, Oded.
    Computational complexity. A conceptual perspective.
    Cambridge University Press. 2008.

[3] Wegener, Ingo.
    Complexity theory. Exploring the limits of efficient algorithms.
    Springer-Verlag. 2005.

Bibliografía Ampliación

[1] Du, Ding-Zhu y Ko, Ker-I
    Theory of Computational Complexity.
    Wiley. 2000.

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

[3] Hemaspaandra, Lane A. y Ogihara, Mitsunori.
    The complexity theory companion.
    Springer-Verlag. 2002.

[4] Papadimitriou, Christos H.
    Computational complexity.
    Addison-Wesley. Reimpresión corregida. 1995.

[5] Sipser, Michael
    Introduction to the Theory of Computation.
    Thomson. 2ª ed. 2006.