Teoría de la Computación

Créditos
6
Tipos
Obligatoria de especialidad (Computación)
Requisitos
Departamento
CS
Web
www.cs.upc.edu/tc/
Desde un punto de vista práctico, la teoría de la computación proporciona a los estudiantes métodos para describir y procesar lenguajes. Dependiendo del método utilizado, se obtienen propiedades expresivas y computacionales mejores o peores. Estos métodos tienen aplicaciones en áreas como compiladores, gráficos, lenguajes de programación y algoritmia. De hecho, este conocimiento constituye la base de cualquier otra área de la informática, y es común encontrarlo, por ejemplo, en artículos de investigación de congresos sobre bases de datos o arquitectura de computadores.

Más allá de sus aplicaciones, la teoría de la computación es una asignatura fundamental, ya que estudia los límites computacionales de las máquinas con las que trabajamos hoy en día. Además, su estudio ayuda a desarrollar habilidades que son de gran utilidad en cualquier otro ámbito, como la capacidad de describir información sin ambigüedades, realizar un análisis de casos preciso y exhaustivo, o elaborar argumentaciones correctas.

Profesorado

Responsable

  • Antoni Lozano Boixadors (antoni.lozano@upc.edu)
  • Ilario Bonacina (ilario.bonacina@upc.edu)

Otros

  • Arnau Messegué Buisan (arnau.messegue@upc.edu)
  • Enrique Romero Merino (eromero@cs.upc.edu)

Horas semanales

Teoría
1.4
Problemas
1.5
Laboratorio
1.2
Aprendizaje dirigido
0.2
Aprendizaje autónomo
5.7

Competencias

Competencias Transversales

Razonamiento

  • G9 [Avaluable] - Capacidad de razonamiento crítico, lógico y matemático. Capacidad para resolver problemas dentro de su área de estudio. Capacidad de abstracción: capacidad de crear y utilizar modelos que reflejen situaciones reales. Capacidad de diseñar y realizar experimentos sencillos, y analizar e interpretar sus resultados. Capacidad de análisis, síntesis y evaluación.
    • G9.3 - Capacidad crítica, capacidad de evaluación.

    • Aprendizaje autónomo

  • G7 [Avaluable] - Detectar carencias en el propio conocimiento y superarlas mediante la reflexión crítica y la elección de la mejor actuación para ampliar este conocimiento. Capacidad para el aprendizaje de nuevos métodos y tecnologías y versatilidad para adaptarse a nueves situaciones.
    • G7.3 - Aprendizaje autónomo: Capacidad de planificación y organización del trabajo personal. Aplicar los conocimientos adquiridos a la realización de una tarea en función de la pertenencia y la importancia, decidiendo la manera de llevarla a cabo y el tiempo que hay que dedicarle y seleccionando las fuentes de información más adecuadas. Identificar la importancia de establecer y mantener contactos con los compañeros de estudios, con el profesorado y con profesionales (networking). Identificar fórums de información sobre ingeniería TIC, sus avances y su impacto en la sociedad (IEEE, asociaciones, etc.).

    • Competencias Técnicas de cada especialidad

    Especialidad de computación

  • CCO1 - Tener un conocimiento profundo de los principios fundamentales y de los modelos de la computación y saberlos aplicar para interpretar, seleccionar, valorar, modelar y crear nuevos conceptos, teorías, usos y desarrollos tecnológicos relacionados con la informática.
    • CCO1.1 - Evaluar la complejidad computacional de un problema, conocer estrategias algorítmicas que puedan conducir a su resolución, y recomendar, desarrollar e implementar la que garantice el mejor rendimiento de acuerdo con los requisitos establecidos.
    • CCO1.2 - Demostrar conocimiento de los fundamentos teóricos de los lenguajes de programación y las técnicas de procesamiento léxico, sintáctico y semántico asociadas, y saber aplicarlas para la creación, el diseño y el procesamiento de lenguajes.
    • CCO1.3 - Definir, evaluar y seleccionar plataformas de desarrollo y producción hardware y software para el desarrollo de aplicaciones y servicios informáticos de diversa complejidad.
  • CCO2 - Desarrollar de forma efectiva y eficiente los algoritmos y el software apropiados para resolver problemas complejos de computación.
    • CCO2.2 - Capacidad para adquirir, obtener, formalizar y representar el conocimiento humano de una forma computable para la resolución de problemas mediante un sistema informático en cualquier ámbito de aplicación, particularmente los relacionados con aspectos de computación, percepción y actuación en ambientes o entornos inteligentes.
  • CCO3 - Desarrollar las soluciones informáticas que, considerando el entorno de ejecución y la arquitectura del computador sobre el cual se ejecutan, consigan el mejor rendimiento.
    • CCO3.1 - Implementar código crítico siguiendo criterios de tiempo de ejecución, eficiencia y seguridad.

    • Objetivos

    1. Aprender a clasificar problemas en las clases de complejidad. En particular, aprender técnicas que permiten determinar cuando un conjunto es regular, incontextual, polinómico, exponencial, decidible o semidecidible.
      Competencias relacionadas: G9.3, CCO1.2, CCO1.1,
    2. Aprender a describir lenguajes según sistemas formales como autómatas y gramáticas incontextuales. Conocer las capacidades computacionales de estos formalismos y sus aplicaciones prácticas.
      Competencias relacionadas: G9.3, CCO1.2, CCO1.1, CCO1.3, CCO2.2, CCO3.1,
    3. Resolver problemas teóricos y prácticos de esta materia y hacer presentaciones públicas de las soluciones obtenidas.
      Competencias relacionadas: G9.3, CCO1.2, CCO1.1, G7.3,

    Contenidos

    1. Introducción matemática.
      Conjuntos, tuplas, relaciones, funciones y homomorfismos. Métodos de demostración.
    2. Lenguajes formales.
      Alfabetos, palabras, lenguajes, operaciones sobre lenguajes (concatenación, reverso, estrella). Clases de lenguajes y propiedades de cierre.
    3. Autómatas finitos.
      Autómatas finitos deterministas, autómatas finitos indeterministas, autómatas finitos con lambda-transiciones, equivalencia entre modelos de autómatas, operaciones sobre autómatas, minimización de autómatas.
    4. Expresiones regulares.
      Expresiones regulares, equivalencia con autómatas y Lema de Arden, operaciones sobre expresiones regulares.
    5. Gramáticas incontextuales.
      Gramàticas incontextuales, lenguaje generado por una gramática, árbol de derivación, ambigüidad, operaciones sobre gramáticas, depuración de gramáticas. Algoritmo CYK y parsing.
    6. Autómatas con pila.
      Autómatas con pila indeterministas y su equivalencia con los lenguajes incontextuales, autómatas con pila deterministas, autómatas con pila de aceptación única y su equivalencia con los lenguajes incontextuales no ambiguos, operaciones de cierre.
    7. No regularidad y no incontextualidad.
      Demostraciones de no regularidad por el lema de bombeo, por propiedades de cierre y por extensiones distinguidoras. Demostraciones de no incontextualidad por el lema de bombeo para incontextuales y por propiedades de cierre.
    8. Máquinas de Turing.
      Máquinas de Turing deterministas, indeterministas y con varias cintas, equivalencia de máquinas de Turing y algoritmos de alto nivel. Máquina de Turing universal y tesis de Church-Turing.
    9. Decidibilidad, semi-decidibilidad, computabilidad.
      Lenguajes decidibles, lenguajes semi-decidibles, funciones computables, operaciones de cierre, teorema del complementario, teorema de proyección, jerarquía aritmética.
    10. No decidibilidad, no semi-decidibilidad, no computabilidad.
      Diagonalización. Lenguajes semidecidibles pero indecidibles (K, HALT). Reducciones "many-one" para demostrar no decidibilitdad y no semi-decidibilidad, equivalencia entre no semi-decidibilidad y no computabilidad. Ejemplos de roblemas naturales indecidibles: intersección no vacía y ambigüedad de gramáticas incontextuales, totalidad de gramáticas incontextuales.
    11. Elementos de teoría de la complejidad
      Definición formal de las clases P, NP y coNP. Reducciones en tiempo polinómico y NP-completitud. Teoremas de jerarquía de tiempo. Complejidad en espacio. Jerarquía polinómica.

    Actividades

    Actividad Acto evaluativo


    Aprendizaje del tema "Teoría de lenguajes".

    Los estudiantes asisten a clases de teoría (T: 2h) y completan los conceptos teóricos introducidos mediante el estudio de la bibliografía recomendada o visualizando los vídeos indicados para este tema (AA: 4h). Además, asisten a clases de resolución de problemas relacionadas con este tema (P: 2h).
    Objetivos: 3
    Contenidos:
    Teoría
    2h
    Problemas
    2h
    Laboratorio
    0h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    4h

    Aprendizaje del tema "Lenguajes regulares".

    Los estudiantes asisten a clases de teoría sobre este tema (T: 4h) y completan los conceptos teóricos introducidos mediante el estudio de la bibliografía recomendada o visualizando los vídeos de este tema (AA: 7h). Asisten a sesiones de laboratorio y resuelven los problemas utilizando el ordenador (L: 3h). También trabajan en la resolución de los problemas asignados sobre este tema (AA: 7h) y asisten a las clases de problemas/laboratorio, donde todos los estudiantes presentan públicamente sus soluciones (P: 4h).
    Objetivos: 1 2 3
    Contenidos:
    Teoría
    4h
    Problemas
    4h
    Laboratorio
    3h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    14h

    Aprendizaje del tema "Lenguajes incontextuales".

    Los estudiantes asisten a clases de teoría sobre este tema (T: 4h) y completan los conceptos teóricos introducidos mediante el estudio de la bibliografía recomendada o visualizando los vídeos de este tema (AA: 7h). Asisten a sesiones de laboratorio y resuelven los problemas utilizando el ordenador (L: 3h). También trabajan en la resolución de los problemas asignados sobre este tema (AA: 8h) y asisten a las clases de problemas/laboratorio, donde todos los estudiantes presentan públicamente sus soluciones (P: 4h). Esta parte incluye una revisión exhaustiva de la primera parte de la asignatura como preparación para el primer examen parcial (AD: 1,5h).
    Objetivos: 1 2 3
    Contenidos:
    Teoría
    4h
    Problemas
    4h
    Laboratorio
    3h
    Aprendizaje dirigido
    1.5h
    Aprendizaje autónomo
    15h

    Primer examen.

    Un examen de 3h de duración, realizado parcialmente delante del ordenador y parcialmente por escrito, donde se evalúa la habilidad de describir lenguajes regulares e incontextuales.
    Objetivos: 1 2
    Semana: 7
    Teoría
    0h
    Problemas
    0h
    Laboratorio
    0h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    0h

    Aprendizaje del tema "Autómatas con pila".

    Los estudiantes asisten a sesiones de laboratorio y resuelven los problemas utilizando el ordenador (L: 3h). También trabajan en la resolución de los problemas asignados sobre este tema (AA: 5h) y preparan la presentación pública de sus soluciones.
    Objetivos: 1 2 3
    Contenidos:
    Teoría
    0h
    Problemas
    0h
    Laboratorio
    3h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    5h

    Aprendizaje del tema "Teoría de la calculabilidad".

    Los estudiantes asisten a clases de teoría sobre este tema (T: 4h) y completan los conceptos teóricos introducidos mediante el estudio de la bibliografía recomendada o visualizando los vídeos de este tema (AA: 5h). Asisten a sesiones de laboratorio y resuelven los problemas utilizando el ordenador (L: 3h). También trabajan en la resolución de los problemas asignados sobre este tema (AA: 6,5h) y asisten a las clases de problemas/laboratorio, donde todos los estudiantes presentan públicamente sus soluciones (P: 6,5h).
    Objetivos: 1 3
    Contenidos:
    Teoría
    4h
    Problemas
    6.5h
    Laboratorio
    3h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    11.5h

    Aprendizaje del tema "Elementos de la teoría de la complejidad".

    Los estudiantes asisten a clases de teoría sobre este tema (T: 4h) y completan los conceptos teóricos introducidos mediante el estudio de la bibliografía recomendada o la visualización de los vídeos correspondientes a este tema (AA: 5h). También trabajan en la resolución de los problemas asignados sobre este tema (AA: 7h) y asisten a las clases de problemas, donde todos los estudiantes presentan públicamente sus soluciones (P: 6h). Esta parte incluye una revisión exhaustiva de la segunda parte de la asignatura como preparación para el segundo examen parcial y el examen final (AD: 1,5h).
    Objetivos: 1 3
    Contenidos:
    Teoría
    4h
    Problemas
    6h
    Laboratorio
    0h
    Aprendizaje dirigido
    1.5h
    Aprendizaje autónomo
    12h

    Segundo examen

    Un examen de 3h de duración, realizado parcialmente delante del ordenador y parcialmente por escrito, donde se evalúa la habilidad de analizar la regularidad e incontextualidad de lenguajes, así como ladecidibilidad de problemas y de construir reducciones para demostrar no decidibilidad y no semi-decidibilidad.
    Objetivos: 1 2
    Semana: 15 (Fuera de horario lectivo)
    Teoría
    0h
    Problemas
    0h
    Laboratorio
    0h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    0h

    Examen final.


    Objetivos: 1 2
    Semana: 15 (Fuera de horario lectivo)
    Teoría
    0h
    Problemas
    0h
    Laboratorio
    0h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    0h

    Metodología docente

    En las clases de teoría, el profesor presenta los fundamentos teóricos básicos de cada tema y resuelve algunos problemas. Los estudiantes profundizan en la teoría durante su tiempo de estudio personal utilizando los recursos indicados por el profesor (libros, vídeos y otros materiales complementarios).

    En las clases de problemas y en las sesiones de laboratorio, los estudiantes exponen las soluciones a problemas que se les han asignado previamente. El profesor interviene durante las explicaciones para corregir errores o proponer mejoras. Además, toma notas sobre las presentaciones de los estudiantes para tenerlas en cuenta en la evaluación final de la asignatura. En las sesiones de laboratorio, los estudiantes resuelven problemas frente al ordenador que son evaluados automáticamente.

    Método de evaluación

    Esta asignatura puede superarse mediante evaluación continua o mediante un examen final.

    La nota de evaluación continua, C, se obtiene combinando las calificaciones de los dos exámenes parciales (cada uno con un peso del 40%) y la calificación correspondiente a la evaluación de las presentaciones en la pizarra de los problemas asignados a los estudiantes (con un peso del 20%).

    Los estudiantes que no se presenten al examen final tendrán como nota final de la asignatura (NF) la nota C de evaluación continua.

    Los estudiantes que se presenten al examen final (con nota F) renuncian a la nota C de evaluación continua como nota final de la asignatura, y la nueva nota final se calcula según la fórmula:

    NF = max{ F, 0.5F + 0.5C }.

    Los estudiantes que no se presenten a ningún examen (Parcial 1, Parcial 2 y Examen Final) obtendrán la calificación NP ("No Presentado").

    La evaluación de las competencias G7.3, G9.1 y CCO1.1 es realizada individualmente por cada profesor para los estudiantes de su grupo, basándose en las presentaciones públicas realizadas durante la evaluación continua. La evaluación de estas competencias no afecta a la calificación de la asignatura.

    Bibliografía

    Básico

    Complementario

    Web links

    Capacidades previas

    * Capacidad para expresar mediante fórmulas lógicas los enunciados descritos en lenguaje natural.
    * Capacidad para manipular fórmulas lógicas.
    * Conocimientos algebraicos fundamentales, incluyendo aritmética modular.
    * Conocimientos básicos de combinatoria.
    * Conocimiento de las estructuras de datos básicas y de la algoritmia fundamental.
    * Capacidad para evaluar la complejidad temporal de un algoritmo.