Curso 2013-14
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: | 1º |
| 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 |
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 sorpresivos 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 (oro 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.
Prerrequisitos para el seguimiento del itinerario formativo
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 grafs
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. Para tal fin la bibliografía contiene varías referencias en la que los estudiantes que necesiten reforzar los conocimientos matemáticos necesarios para la asignatura puedan hacerlo.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 transversales | Competencias específicas |
|---|---|
|
Instrumentales Interpersonales |
H1. Capacidad de concebir y llevar a cabo proyectos informáticos utilizando los principios y metodologías propios de la ingeniería. 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.
|
Los mecanismos de evaluación son los siguientes:
1.-Evaluación continua. Durante el curso, los estudiantes tendrán que preparase ejercicios que se resolveran en la pizarra y/o se entregarán. El estudiante deberá haver resuelto los ejercicios durante el periodo de estudio dedicado a la asignatura en colaboración con otros estudiantes de su grupo. No todos los ejercicios entregados o presentados seran evaluados. El resultado será una nota, denominada L, entre 0 y 10.
2.- Examen parcial. Consistirá en un examen obligatorio con preguntas de teoría y problemas que se hará en medio del trimestre. El resultado será una nota, EP, entre 0 y 10.
3.- Examen final (en primera convocatoria). Consistirá en un examen obligatorio con preguntas de teoría y problemas que se realizará durante el periodo de exámenes del primer trimestre. El resultado del examen final en primera convocatoria será una nota, EF1, entre 0 y 10.
4.- Examen final (en segunda convocatoria). Consistirá en un examen obligatorio con preguntas de teoría y problemas que realizarán, durante el periodo de exámenes de septiembre, aquellos estudiantes que se presentan a la convocatoria de septiembre. El resultado del examen final en segunda convocatoria será una nota, EF2, entre 0 y 10.
La nota es calculará de la siguiente manera:
- Primera convocatoria. Para aprobar la convocatoria de diciembre es necesario que la nota del examen de diciembre, EF1, sea como mínimo 5. En este caso la nota de la convocatoria será 0.20*L+0.15*EP+0.65*EF1.
- Convocatoria de julio. Para aprobar la convocatoria de septiembre es necesario que la nota del examen de septiembre, EF2, sea como mínimo 5. En este caso la nota final será 0.20*L+0.15*EP+0.75*EF2.
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.
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. En general (aunque no necesariamente siempre) este material consistirá de algunas secciones de los apuntes de la asignatura que el estudiante deberá leer detenidamente. Los apuntes contienen ejercicios que el estudiante también deberá resolver.
Trabajo durante la sesión.
Durante la sesión, los estudiantes resolverán en la pizarra ejercicios. La contribución del profesor en el aula será mínima, limitándose generalmente, a hacer preguntas.
Adicionalmente, el profesor puede solicitar otras tareas tales como la entrega de ejercicios o la presentación de material en clase.
Recursos didácticos. Material docente de la asignatura
- Apuntes de Sistemas Formales. Apoyo 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.