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, en diversas ocasiones al largo del curso, los estudiantes recibirán unos ejercicios para resolver en horas de trabajo personal, que deberán entregar por escrito unos días después.

La asignatura tiene un sistema de evaluación continuada y un examen final. La evaluación continuada consta de k pruebas (3 <= k <= 10) realizadas a lo largo del cuatrimestre, mientras que el examen final consta de k preguntas, cada una de las cuales tiene el mismo peso que la prueba correspondiente. Si las notas de las pruebas son c_1, ..., c_k y las notas de las preguntas del examen final son f_1, ..., f_k, la nota global de la assignatura es

max(c_1,f_1) + ... + max(c_k,f_k).

Cada prueba de la evaluación continuada (y la pregunta correspondiente del examen final) evalua uno o dos temas, y su peso es la suma de los pesos de los temas que evalua. Los pesos de cada tema estarán estre 0.5 y 1.5, y sus valores exactos se anunciarán en el Racó a principio de curso.

Las pruebas tendrán lugar en el aula de clase dentro de la hora de problemas, poco después de acabar la materia que incluyen, y se anunciarán en el Racó con un mínimo de un día de antelación.

• Sipser, M. Introduction to the Theory of Computation, PWS, 1997.
• Brassard, G. i Bratley, P. Fundamentos de Algoritmia, Prentice Hall, 1997.
• Serna, M, Àlvarez, C., Cases, R. i Lozano, A. Els límits de la computació. Indecidibilitat i NP-completesa, Edicions UPC, 2001.
• Cormen, T.H., Leiserson C.E., Rivest, R.L. i Stein, C. Introduction to Algorithms, second edition, MIT i McGraw-Hill, 2001.

• Kinber, E. i Smith, C. Theory of Computing. A Gentle Introduction., Prentice Hall, 2001.
• Papadimitriou, C. Computational Complexity, Addison Wesley, 1994.
• Garey, M. i Johnson, D. Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, 1978.
• Parberry I., Gasarch W. Problems on Algorithms (2nd edition), http://hercule.csci.unt.edu/ian/books/free/, 2002.
• Cases, R. i Màrquez, L. Llenguatges, gramàtiques i autòmats, Edicions UPC, 2000.

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