Teoría de la Computación

Usted está aquí

Inicio » Estudios » Grados » Grado en Ingeniería Informática » Plan de estudios » Asignaturas » Teoría de la Computación
Créditos
6
Tipos
Obligatoria de especialidad (Computación)
Requisitos
  • Prerrequisito: EDA
  • Correquisito: PROP
Departamento
CS
Web
www.cs.upc.edu/~alvarez/tc2.html
Des d'un punt de vista pràctic, la teoria de la computació proporciona als alumnes mètodes de descripció i tractament de llenguatges. Depenent del mètode utilitzat, s'obtenen millors o pitjors propietats expressives i computacionals. Aquests mètodes troben aplicacions en àrees com compiladors, gràfics, llenguatges de programació i algorísmia. Però de fet, aquests coneixements són la base per a qualsevol altra àrea de les ciències de la computació, i és habitual trobar-los, per exemple, en articles de recerca de congressos de bases de dades o arquitectura de computadors. A part de les aplicacions, TC és una assignatura de fonament, doncs estudia quins són els límits computacionals de les màquines amb què treballem avui en dia. A més a més, el seu estudi ajuda a desenvolupar habilitats que són de gran ajuda en qualsevol altre àmbit, tals com la capacitat de descriure la informació sense ambigüitats, fer un anàlisi de casos acurat i exhaustiu, o produir una argumentació correcta.

Profesorado

Responsable

  • Maria del Carme Alvarez Faura ( )

Otros

  • Enrique Romero Merino ( )
  • Ilario Bonacina ( )

Horas semanales

Teoría
1
Problemas
1
Laboratorio
2
Aprendizaje dirigido
0.2
Aprendizaje autónomo
5.8

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 dentro de la jerarquía de Chomsky. En particular, aprender técnicas que permiten determinar cuando un conjunto es regular, incontextual, decidible y semi-decidible.
    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. Lenguajes formales.
    Alfabetos, palabras, lenguajes, operaciones sobre lenguajes (concatenación, reverso, estrella), morfismos, sistemas de reescritura.
  2. 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.
  3. 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.
  4. Expresiones regulares.
    Expresiones regulares, equivalencia con autómatas y Lema de Arden, operaciones sobre expresiones regulares.
  5. Autómatas con pila.
    Autómatas con pila indeterministas y su equivalencia con lenguajes incontextuales, autómatas con pila deterministas, autómatas con pila de aceptación única y su equivalencia con lenguajes incontextuales no ambiguos, operaciones de cierre, jerarquía de Chomsky.
  6. No regularidad y no incontextualidad.
    Demostraciones de no regularidad por repetición de estado y por transformaciones que preservan la regularidad. Demostraciones de no incontextualidad por repetición de variable.
  7. Máquinas de Turing.
    Máquinas de Turing deterministas, extensiones indeterministas o con varias cintas, equivalencia de máquinas de Turing y algoritmos de alto nivel.
  8. Decidibilidad, semi-decidibilidad, computabilidad.
    Lenguajes decidibles, lenguajes semi-decidibles, funciones computables, operaciones de cierre, teorema del complementario, teorema de proyección, conexiones entre semi-decidibilidad y computabilidad.
  9. No decidibilidad, no semi-decidibilidad, no computabilidad.
    El lenguaje K, K es semi-decidible pero no decidible, reducciones para demostrar no decidibilitdad y no semi-decidibilidad, equivalencia entre no semi-decidibilidad y no computabilidad.
  10. Problemas naturales indecidibles.
    Accesibilidad de palabras por reescritura, PCP, intersección no vacía y ambigüidad de gramáticas incontextuales, universalidad de gramáticas incontextuales y satisfactibilidad de lógica de palabras.

Actividades

Actividad Acto evaluativo


Aprendizaje del tema "teoría de lenguajes".

Los alumnos completan los conceptos tóricos introducidos en la clase de teoría estudiando los temas de la bibiografía básica indicados por el profesor o tratando de visionar y entender los videos de este tema (AA: 3h). También tratan de resolver los problemas asignados al respecto (AA: 3h), asisten a clase de teoría sobre este tema y piden al profesor que resuelva sus dudas (T: 2h) y asisten a la clase de problemas donde todos los alumnos presentan públicamente sus problemas sobre este tema (P: 2h).
Objetivos: 3
Contenidos:
Teoría
1h
Problemas
2h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
4h

Aprendizaje del tema "Autómatas finitos".

Los alumnos completan los conceptos tóricos introducidos en la clase de teoría estudiando los temas de la bibiografía básica indicados por el profesor o tratando de visionar y entender los videos de este tema (AA: 3h). También tratan de resolver los problemas asignados al respecto (AA: 4h), asisten a clase de laboratorio sobre este tema y tratan de resolver los problemas delante de la máquina (L: 4h) y asisten a la clase de problemas donde todos los alumnos presentan públicamente sus problemas sobre este tema (P: 2h).
Objetivos: 1 2 3
Contenidos:
Teoría
2h
Problemas
2h
Laboratorio
4h
Aprendizaje dirigido
0h
Aprendizaje autónomo
8h

Aprendizaje del tema "Gramáticas incontextuales".

Los alumnos completan los conceptos tóricos introducidos en la clase de teoría estudiando los temas de la bibiografía básica indicados por el profesor o tratando de visionar y entender los videos de este tema (AA: 3h). También tratan de resolver los problemas asignados al respecto (AA: 4h), asisten a clase de laboratorio sobre este tema y tratan de resolver los problemas delante de la máquina (L: 4h) y asisten a la clase de problemas donde todos los alumnos presentan públicamente sus problemas sobre este tema (P: 2h).
Objetivos: 1 2 3
Contenidos:
Teoría
2h
Problemas
2h
Laboratorio
6h
Aprendizaje dirigido
0h
Aprendizaje autónomo
8h

Aprendizaje del tema "Expresiones regulares".

Los alumnos tratan de visionar y entender los videos de este tema (AA: 3h), tratan de resolver los problemas asignados al respecto (AA: 3h), asisten a clase de laboratorio sobre este tema y tratan de resolver los problemas delante de la máquina (L: 2h) y asisten a la clase de problemas donde todos los alumnos presentan públicamente sus problemas sobre este tema (P: 2h).
Objetivos: 1 2 3
Contenidos:
Teoría
0h
Problemas
2h
Laboratorio
2h
Aprendizaje dirigido
1.5h
Aprendizaje autónomo
6h

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
Tipo: examen de laboratorio
Teoría
0h
Problemas
0h
Laboratorio
3h
Aprendizaje dirigido
0h
Aprendizaje autónomo
8h

Aprendizaje del tema "Autómatas con pila".

Los alumnos estudian la teorís a partir de los temas de la bibliografía indicados por el profesor o visionando y entendiendo los videos de este tema (AA: 3h), tratan de resolver los problemas asignados al respecto (AA: 3h), asisten a clase de laboratorio sobre este tema y tratan de resolver los problemas delante de la máquina (L: 2h) y asisten a la clase de problemas donde todos los alumnos presentan públicamente sus problemas sobre este tema (P: 2h).
Objetivos: 1 2 3
Contenidos:
Teoría
0h
Problemas
0h
Laboratorio
2h
Aprendizaje dirigido
0h
Aprendizaje autónomo
6h

Aprendizaje del tema "teoría de lenguajes".

Los alumnos completan los conceptos básicos introducidos en clase de teoría (T: 1h) estudiando los temas de la bibliografía básica indicados por el profesor o visionando y entendiendo los videos de este tema (AA: 3h), tratan de resolver los problemas asignados al respecto (AA: 3h), y asisten a la clase de problemas donde todos los alumnos presentan públicamente sus problemas sobre este tema (P: 1h).
Objetivos: 1 3
Contenidos:
Teoría
1h
Problemas
1h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
6h

Aprendizaje del tema "Máquinas de Turing".

Los alumnos tratan completar lod conceptos introducidos en clase de toería (T: 1h) estudiando los temas de la bibliografía básica indicados por el professor o visionando y entendiendo los videos de este tema (AA: 3h), tratan de resolver los problemas asignados al respecto (AA: 3h) y asisten a la clase de problemas donde todos los alumnos presentan públicamente sus problemas sobre este tema (P: 1h).
Objetivos: 1 3
Contenidos:
Teoría
2h
Problemas
1h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
6h

Aprendizaje del tema "Decidibilidad, semi-decidibilidad, computabilidad".

Los alumnos tratan de completar los conceptos introducidos en clase de teoría (T: 1h) estudiando los temas de la bibliografía básica indicados por el profesor o tratando de visionar y entender los videos de este tema (AA: 3h), tratan de resolver los problemas asignados al respecto (AA: 3h), asisten a clase de laboratorio sobre este tema y tratan de resolver los problemas delante de la máquina (L: 2h) y asisten a la clase de problemas donde todos los alumnos presentan públicamente sus problemas sobre este tema (P: 1h).
Objetivos: 1 3
Contenidos:
Teoría
2h
Problemas
1h
Laboratorio
2h
Aprendizaje dirigido
0h
Aprendizaje autónomo
6h

Aprendizaje del tema "No decidibilidad, no semi-decidibilidad, no computabilidad".

Los alumnos tratan de completar los conceptos teóricos introducidos en las clases de teoria (T: 1h) o visionando y entendiendo los videos de este tema (AA: 4h), tratan de resolver los problemas asignados al respecto (AA: 4h), asisten a clase de laboratorio sobre este tema y tratan de resolver los problemas delante de la máquina (L: 4h) y asisten a la clase de problemas donde todos los alumnos presentan públicamente sus problemas sobre este tema (P: 3h).
Objetivos: 1 3
Contenidos:
Teoría
2h
Problemas
3h
Laboratorio
4h
Aprendizaje dirigido
0h
Aprendizaje autónomo
8h

Aprendizaje del tema "Problemas naturales indecidibles".

Los alumnos tratan de entender los conceptos teóricos correpondientes etudiando los temas de la bibliografía básica indicados por el profesor o visionarndo y entendiendo los videos de este tema (AA: 4h), tratan de resolver los problemas asignados al respecto (AA: 4h), asisten a clase de laboratorio sobre este tema y tratan de resolver los problemas delante de la máquina (L: 4h) y asisten a la clase de problemas donde todos los alumnos presentan públicamente sus problemas sobre este tema (P: 4h).
Objetivos: 1 3
Contenidos:
Teoría
0h
Problemas
1h
Laboratorio
4h
Aprendizaje dirigido
1.5h
Aprendizaje autónomo
3h

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)
Tipo: examen de laboratorio
Teoría
0h
Problemas
0h
Laboratorio
3h
Aprendizaje dirigido
0h
Aprendizaje autónomo
8h

Examen final.


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

Metodología docente

La principal característica de esta metodología docente es el auto-aprendizaje basado en la utilización del material docente para el estudio de los fundamentos teóricos de la asignatura y también en la resolución de problemas en la pizarra. El profesor introduce los fundamentos teóricos básicos de cada tema durante la clase de teoría y soluciona algunos problemas. Los estudiantes aprenden la teoría durante su tiempo de trabajo personal mediante el estudio de los temas indicados por el profesor de la bibliografía o de los vídeos y otros materiales complementarios como apuntes, libros y listas de problemas resueltos, todos ellos libremente accesibles a través de la web.

Durante las horas de problemas, los estudiantes salen a la pizarra a explicar soluciones a problemas que se les han asignado con anterioridad. El profesor interviene para corregir una solución, matizar un argumento, o poner énfasis en aquellos aspectos que considera relevantes y que no han quedado del todo claros en la explicación del alumno. También toma nota de cada presentación para tenerla en cuenta en el momento de la evaluación de la asignatura.

Durante las horas de laboratorio, los estudiantes tratan de resolver problemas en frente de la máquina que son evaluados automáticamente. El profesor está presente para atender las dudas que los alumnos le puedan plantear. Los estudiantes pueden aprovechar estas clases para preparar los problemas que se les han asignado con anterioridad, pero
también para estudiar el material teórico si no ho han hecho con anterioridad por su cuenta, y para preguntar dudas sobre la teoria.

Método de evaluación

Esta asignatura se puede aprobar por evaluación contínua (sin asistir al examen final). La nota de la evaluación contínua se obtiene de la nota L correspondiente a los 2 exámenes del curso (los actos evaluativos, que valen entre 0 y 8 puntos en total, el primer examen con un peso de un 50% y el segundo con un peso de un 50%) y de la nota P correspondiente a la evaluación de las presentaciones en la pizarra de los problemas que se han asignado a los alumnos (entre 0 y 2 puntos). La nota de la evaluación contínua C se obtiene sumando estas dos notas, C=L+P.

Aquellos estudiantes tales que su nota C sea mayor o igual a 5 y no vayan al examen final tienen como nota final de curso la nota de la evaluación contínua C.

Aquellos estudiantes cuya nota C sea menor que 5 y que no hagan el examen final obtendrán calificación NP.

Aquellos estudiantes que hagan el examen final renuncian a la nota de la evaluación contínua (en caso de que hubiesen aprobado). En tal caso, la nota de la asignatura se obtiene de las notas C y de la nota F del examen final (entre 0 y 10) según la fórmula:

max(F,0.5 F+0.5 C)



La evaluación de las competencias G7.3, G9.1 y CCO1.1 la realiza cada profesor individualmente para cada alumno de su grupo basándose en las presentaciones públicas de la evaluación contínua. La evaluación de las competencias no afecta a la evaluación de la asignatura.

Bibliografía

Básica:

Complementaria:

Web links

Capacidades previas

Capacidad para expresar en fórmulas lógicas los enunciados descritos en lengua común.
Capacidad para manipular fórmulas lógicas.
Conocimientos algebraicos fundamentales: monoides, grupos, cierres, morfismos.
Conocimientos básicos de combinatoria.
Capacidad para utilizar con facilidad las propiedades de un álgebra de Boole.
Conocimiento de las estructuras de datos básicos y de algoritmia fundamental.
Capacidad para evaluar la complejidad temporal de un algoritmo.