Algorítmica, Calculabilidad y Complejidad (ALCC)

Conocer los elementos básicos de la teoría de la computación, incluyendo la teoría de autómatas y lenguajes, la teoría de la calculabilidad, la teoría de la complejidad y la algortmia. Los conocimientos y la experiencia necesarios para clasificar problemas según la existencia o no de algoritmos para su resolución y, en este último caso, según la posibilidad de encontrar una solución eficiente.

Conocimientos

1. Conocer algunos modelos abstractos de cálculo clásicos y sus limitaciones y posibilidades.
2. Saber clasificar los problemas en las clases de complejidad definidas por los diferentes modelos de cálculo. En particular, entender el significado de los resultados negativos (no regularidad, intratabilidad, indecibilidad).
3. Comprender el concepto de reducción entre problemas y su uso para mostrar la tratabilidad o intratabilidad.
4. Aprender a analizar el coste de un algoritmo y la complejidad computacional de un problema. Entender la diferencia cualitativa entre tiempo polinómico y tiempo exponencial.
5. Conocer problemas computacionales para los que, a día de hoy, no se conocen algoritmos con coste polinómico.
6. Aprender algunas técnicas algorítmicas para tratar problemas difíciles; en particular, los problemas NP-completos.
7. Entender el uso de la notación lógico-matemática para representar los problemas computacionales y los modelos de cálculo.

Habilidades

Competencias

1. Capacidad para el razonamiento crítico y lógico-matemático.
2. Capacidad para entender y construir demostraciones lógico-matemáticas.
3. Capacidad para resolver problemas aplicando los métodos de la ciencia y la ingeniería.
4. Capacidad para aplicar los conocimientos de matemáticas y lógica a la resolución de problemas.
5. Capacidad de abstracción. Capacidad para enfrentarse a problemas nuevos recurriendo conscientemente a estrategias que han resultado útiles en problemas resueltos anteriormente.
6. Capacidad para actuar autónomamente: saber trabajar de forma independiente, recibiendo solamente la información indispensable y una guía mínima.
7. Capacidad para transmitir ideas efectivamente de forma escrita.
8. Apertura y curiosidad intelectual.

Cada clase de dos horas se divide en una primera hora de teoría y una segunda clase de problemas. Además, se hará evaluación continua consistente en tres pruebas hechas a lo largo del curso (para las partes I-III) en horario lectivo.

La asignatura tiene un sistema de evaluación continua y un examen final. La evaluación continua consta de 3 pruebas hechas a lo largo del quatrimestre, mientras que el examen final consta de 4 partes. Si las notas de las pruebas son p1, p2, p3 y las notas de las partes del examen final son f1, f2, f3, f4, la nota global de la asignatura es

max(p1,f1) + max(p2,f2) + max(p3,f3) + f4

Los cuatro valores de la suma anterior corresponden, respectivamente, a las cuatro partes en las que se divide el temario. Las partes I-III aportan 3 punts cada una, mientras que la IV aporta 1 punto.

Las pruebas tendrán lugar dentro del horario habitual de clase, una vez acabada la materia que incluyen. El calendario de pruebas se anunciará en el Racó a principios de curso.

• Michael Sipser Introduction to the theory of computation, Thomson Course Technology, 2006.
• G. Brassard, T. Bratley Fundamentos de algoritmia, Prentice Hall,, 1996.
• Maria Serna ... [et al.] Els Límits de la computació : indecidibilitat i NP-completesa, Edicions UPC, 2001.
• Thomas H. Cormen ... [et al.] Introduction to algorithms, MIT Press, 2001.

• Efim Kinber, Carl Smith Theory of computing : a gentle introduction, Prentice-Hall, 2001.
• Christos H. Papadimitriou Computational complexity, Addison-Wesley, 1994.
• Michael R. Garey, David S. Johnson Computers and intractability : a guide to the theory of NP-Completeness, W.H. Freeman, 1979.
• Ian Parberry Problems on algorithms, Prentice Hall, 1995.
• Rafel Cases, Lluís Màrquez Llenguatges, gramàtiques i autòmats : curs bàsic, Edicions UPC, 2003.

Conocimientos de programación y estructura de datos.
Familiaridad con el razonamiento lógico-matemático.