Curso 2014-15

Sistemas Formales

Titulación: Código: Tipo:
Grado en Ingeniería Informática 21424 Obligatoria 3º curso
Grado en Ingeniería Telemática 22607 Optativa
Grado en Ingeniería en Sistemas Audiovisuales 22673 Optativa

 

Créditos ECTS: 4 Dedicación: 100 horas Trimestre:

 

Departamento: Dpto. de Tecnologías de la Información y las Comunicaciones
Coordinador: Víctor Dalmau
Profesorado:

Víctor Dalmau 

Idioma:

Catalán 

Horario:
Campus: Campus de la Comunicación - Poblenou

 

Presentación de la assignatura

En esta asignatura se introducen y estudian los principales modelos de computación. El curso se estructura en dos bloques. En el primer bloque se estudian las expresiones regulares y las gramáticas libres de contexto. El objetivo es proporcionar al estudiante los fundamentos matemáticos de la tecnología utilizada en el diseño de compiladores y otros procesadores de lenguaje. Los conceptos ver en este bloque también se aplican en el campo de la verificación de sistemas.

En el segundo bloque se estudia la Máquina de Turing. La Máquina de Turing es un modelo matemático que tiene la misma "potencia" que un ordenador. En este bloque primero, se investigará qué tareas pueden o no pueden ser resueltas por una Máquina de Turing. Esta parte del curso se conoce como Teoría de la decibilidad. Se verán resultados sorprendentes cómo es el hecho de que se puede demostrar que hay tareas que no pueden ser resueltas por ningún programa informático. En el segundo, se presentará la teoría de la complejidad donde se investiga qué tareas pueden ser resueltas por una Máquina de Turing (o equivalentemente por un ordenador) de manera eficiente. En particular se presentará la cuestión conocida como P=?NP, considerada como una de las 10 preguntas matemáticas abiertas más importantes en la actualidad (de hecho, el "Clay Institute" concede un premio de un millón de dólares a quien lo solucione).


En esta asignatura se pretende trabajar la capacidad de razonamiento del estudiante, potenciando su capacidad de abstracción. La asignatura tiene un enfoque teórico y deductivo. 

 

Prerequisitos

Los conocimientos previos para el seguimiento de la asignatura son ciertas nociones matemáticas básicas que el estudiante tendría que haber adquirido durante la Enseñanza Secundaria Obligatoria y las asignaturas de matemáticas del primer curso de los estudios:
- Nociones algebraicas básicas.
- Aritmética básica.
- Capacidad básica para comprender y escribir expresiones matemáticas a nivel elemental.
- Familiaridad con las técnicas básicas de demostración: inducción, reducción al absurdo.
- Nociones básicas de teoría de grafos.


Los estudiantes que, debido a que provienen del itinerario humanístico del Bachillerato o a que no han superado con éxito las asignaturas de matemáticas del primer curso del estudios, no están del todo familiarizados con los prerrequisitos matemáticos podrán superar sin problemas la asignatura pero tendrán que dedicar un mayor esfuerzo que el resto de compañeros, dado que tendrán que reforzar estos conocimientos básicos.

También son convenientes algunas nociones básicas sobre algorítmica i sobre lógica que el estudiante tendría que haber adquirido al cursar la asignaturas "Fundamentos de Programación" i "Lógica Computacional". Aún así, los estudiantes que, al no haber cursado estas asignaturas, no estén familiarizados con estos conceptos, también podrán superar sin problemas la asignatura, dedicando algo más de esfuerzo.

 

Competencias

Competencias transversalesCompetencias específicas

 

Instrumentales
G1. Capacidad de análisis y síntesis
G2. Capacidad de organización y planificación
G3. Capacidad para aplicar los conocimientos al análisis de situaciones y la resolución de problemas
G4. Habilidad en la búsqueda y la gestión de la información
G5. Habilidad en la toma de decisiones
G6. Capacidad de comunicarse con propiedad de forma oral y escrita en catalán y en castellano, tanto ante audiencias expertas como inexpertas

Interpersonales
G8. Capacidad de trabajo en equipo Sistémicas
G11. Capacidad de aplicar con flexibilidad y creatividad los conocimientos adquiridos y de adaptarlos a contextos y situaciones nuevas
G12. Capacidad para progresar en los procesos de formación y aprendizaje de manera autónoma y continua
G14. Capacidad de motivación por la calidad y por el logro
G15. Capacidad de generación de nuevas ideas

 

H1. Capacidad de concebir y llevar a cabo proyectos informáticos utilizando los principios y metodologías propios de la ingeniería.
H3. Capacidad para la redacción y desarrollo de proyectos en el ámbito de su especialidad.
H4. Aprender de manera autónoma nuevos conocimientos y técnicas adecuados para la concepción, el desarrollo o la explotación de sistemas
informáticos.
IN25. Conocer la teoría y práctica de autómatas de estados finitos,propiedades de las expresiones y lenguajes regulares, así como técnicas para determinar si un lenguaje es regular o no.

IN26. Conocer los lenguajes libres de contexto y su relación con los autómatas con pila, gramáticas libres de contexto, árboles sintácticos,derivaciones y ambigüedad.


IN27. Conocer la máquina de Turing y la relación con la noción de algoritmo o programa.

 

Evaluación

Los mecanismos de evaluación son los siguientes:
1.-Evaluación continua. Aquí se incluye tanto la participación en clase como el resultado de las entregas u otras actividades. El resultado será una nota, denominada C, entre 0 i 10.

2.- Examen parcial. Consistirá en un examen obligatorio con preguntas de teoría y problemas sobre las unidades 1 y 2 que se hará en medio del trimestre. El resultado será una nota, B1, entre 0 y 10.
3.- Examen final (Diciembre). Consistirá en un examen obligatorio con preguntas de teoría y problemas sobre las unidades 3 y 4 (aunque también pueden aparecer, en menor cantidad, preguntas sobre otras unidades) que se realizará durante el periodo de exámenes del primer trimestre. El resultado del examen final en primera convocatoria será una nota, B2, entre 0 y 10. También se realizará un examen opcional que permitirá reevaluar nuevamente las unidades 1 y 2. Se actualizará la nota B1 si la nota obtenida la mejora.


4.- Examen final (Julio). Consistirá en dos exámenes independientes y opcionales (uno para las unidades 1 y 2 y otro para las unidades 3 y 4). Las notas B1 y B2 se actualizarán en caso de mejora.

Los estudiantes pueden escoger el tipo de evaluación:


A) Evaluación continua.

Para aprobar una convocatoria es necesario que las notas B1 y B2 sean, como mínimo, 4. En este caso la nota de la convocatoria será 0.30*C+0.30*B1+0.40*B2. 

B) Evaluación no continua

Para aprobar una convocatoria es necesario que las notas B1 y B2 sean, como mínimo, 4. En este caso la nota de la convocatoria será (0.30*B1+0.40*B2)/0.7

 

 

 

Contenidos

La asignatura se divide en cuatro unidades didácticas.
1.- Lenguajes regulares.
Autómatas finitos deterministas (AFD) y no deterministas . Expresiones regulares. Equivalencia entre AFDs y expresiones regulares (Teorema de Kleene).
Lenguajes regulares y sus propiedades básicas.
2.- Lenguajes libres de contexto. Gramáticas libres de contexto (GLC). Lenguajes libres de contexto y sus propiedades básicas.
3.- Teoría de la decidibilitat.
Máquinas de Turing (MT). Equivalencia entre MTs y programas. Lenguajes recursivamente enumerables y recursivos. Lenguaje Diagonal, universal, de la parada. 
4.- Teoría de la complejidad
Complejidad temporal de una MT. Las clases P y NP. Reducción en tiempo polinomio. NP-completesa y teorema de Cook.

 

Metodología

Trabajo personal del estudiante antes de cada sesión.

El estudiante preparará, antes de cada sesión, un material que será proporcionado por el profesor con anterioridad. El material puede contener ejercicios que el estudiante también deberá resolver.

Trabajo durante la sesión.

Durante la sesión, los estudiantes trabajarán en grupo los ejercicios y los resolverán en la pizarra.

Adicionalmente, el profesor puede solicitar otras tareas tales como la entrega de ejercicios o la presentación de material en clase.

Tabla de dedicación: 

 Activitades en el aulaActivitades fuera del aulaEvaluación
TemasGrupo grandeGrupo medianoGrupo pequeño  

 Bloque 1

20

 

 

30

 

 Bloque 2

20

 

 

30

 

Total:

 40

 

 

60

 

Total:100 h

 

Recursos

Recursos didácticos. Material docente de la asignatura
- Material proporcionado por el profesor. Soporte electrónico. Accesible al espacio Moddle dedicado a la asignatura.

 
Bibliografía básica
-J. Hopcroft, R. Motwani y J. Ullman. Introducción a la teoría de autómatas, lenguajes y computación. Addison-Wesley, 2007.
Bibliografía complementaria
- D. Kelley. Teoría de autómatas y lenguajes formales. Prentice-Hall, 1995.
- D. Kozen. Automata and Computability. Springer-Verlag, 1997.
- M. Sipser. Introduction to the Theory of Computation. PWS Publishing Company, 1997.
- H. Lewis i C. Papadimitriou. Elements of the Theory of Computation. Prentice-Hall, 1997.