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.

Profesorado

Nombre	Apellido 1	Apellido 2	C.C.E.	Coordinador
Juan José	Domínguez	Jiménez	Profesor Titular Universidad	N
FRANCISCO	PALOMO	LOZANO	TEU	S

Competencias

Se relacionan aquí las competencias de la materia/módulo o título al que pertenece la asignatura, entre las que el profesorado 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.

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.

Presentaciones orales o 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 las presentaciones orales o 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.

El presente documento es propiedad de la Universidad de Cádiz y forma parte de su Sistema de Gestión de Calidad Docente. En aplicación de la Ley 3/2007, de 22 de marzo, para la igualdad efectiva de mujeres y hombres, así como la Ley 12/2007, de 26 de noviembre, para la promoción de la igualdad de género en Andalucía, toda alusión a personas o colectivos incluida en este documento estará haciendo referencia al género gramatical neutro, incluyendo por lo tanto la posibilidad de referirse tanto a mujeres como a hombres.