G4011321 - Teoría de Autómatas e Linguaxes Formais (Sistemas Inteligentes) - Curso 2013/2014
Información
- Créditos ECTS
- Créditos ECTS: 6.00
- Total: 6.0
- Horas ECTS
- Clase Expositiva: 25.00
- Clase Interactiva Laboratorio: 25.00
- Horas de Titorías: 1.00
- Total: 51.0
Outros Datos
- Tipo: Materia Ordinaria Grao RD 1393/2007
- Departamentos: Electrónica e Computación
- Áreas: Ciencia da Computación e Intelixencia Artificial
- Centro: Escola Técnica Superior de Enxeñaría
- Convocatoria: 1º Semestre de Titulacións de Grao/Máster
- Docencia e Matrícula: null
Profesores
| Nome | Coordinador |
|---|---|
| Bugarín Diz, Alberto José. | NON |
| Mucientes Molina, Manuel. | SI |
Horarios
| Nome | Tipo Grupo | Tipo Docencia | Horario Clase | Horario exames |
|---|---|---|---|---|
| Grupo CLE01 | Ordinario | Clase Expositiva | SI | SI |
| Grupo CLIL_01 | Ordinario | Clase Interactiva Laboratorio | SI | SI |
| Grupo CLIL_02 | Ordinario | Clase Interactiva Laboratorio | SI | SI |
| Grupo CLIL_03 | Ordinario | Clase Interactiva Laboratorio | SI | SI |
| Grupo TI-ECTS01 | Ordinario | Horas de Titorías | NON | NON |
| Grupo TI-ECTS02 | Ordinario | Horas de Titorías | NON | NON |
| Grupo TI-ECTS03 | Ordinario | Horas de Titorías | NON | NON |
| Grupo TI-ECTS04 | Ordinario | Horas de Titorías | NON | NON |
| Grupo TI-ECTS05 | Ordinario | Horas de Titorías | NON | NON |
Programa
Existen programas da materia para os seguintes idiomas:
Obxectivos da materia
Introducir os conceptos da teoría de autómatas e das linguaxes formais, e estudar as súas aplicacións. Na materia realizarase o estudo dos diferentes modelos de máquinas computacionais, gramáticas e linguaxes formais, así como a correspondencia entre autómatas, linguaxes e gramáticas. Tamén se estudarán os conceptos de decidibilidade e complexidade computacional.
Contidos
PROGRAMA DE TEORÍA
1. Introdución: linguaxes, gramáticas formais, autómatas
2. Autómatas finitos
Autómatas finitos deterministas (AFD)
Autómatas finitos non deterministas (AFN)
Transformación de AFN en AFD
Minimización de AFD
3. Linguaxes regulares
Expresións regulares
Autómatas finitos e expresións regulares
Álxebra de expresións regulares
Lema de bombeo para linguaxes regulares
4. Gramáticas independentes do contexto (GIC)
Definición de gramáticas
Derivacións
Árbores de derivación
Ambigüidade
Formas normais para GIC
5. Autómatas con pila
Autómatas con pila non deterministas
Recoñecemento por baleirado de pila e por estado final
Transformación de gramáticas a autómatas con pila
Autómatas con pila deterministas
Lema de bombeo para linguaxes independentes do contexto (LIC)
6. Máquinas de Turing
Máquina de Turing básica
Extensións á máquina de Turing básica
Máquinas de Turing restrinxidas
7. Decidibilidade e complexidade
Linguaxes recursivas e recursivamente enumerables
Problemas indecidibles
Problemas intratables: as clases P e NP
Problemas NP-completos
PROGRAMA DE PRÁCTICAS
O programa de prácticas divídese en tres bloques:
1. Autómatas de estados finitos e expresións regulares
2. Autómatas con pila e gramáticas independentes do contexto
3. Máquinas de Turing
Bibliografía básica e complementaria
Básica
P. Linz. “An Introduction to Formal Languages and Automata”. Jones and Bartlett Publishers, Inc. 2006.
J.E. Hopcroft, R. Motwani, e J.D. Ullman. “Teoría de Autómatas, Lenguajes y Computación”. Addison Wesley. 2008.
Complementaria
E. Alfonseca, M. Alfonseca, e R. Moriyón. “Teoría de Autómatas y Lenguajes Formales”. McGraw-Hill. 2007.
J. G. Brookshear. “Teoría de la Computación: Lenguajes Formales, Autómatas y Complejidad”. Addison Wesley. 1999.
P. Isasi, P. Martínez, e D. Borrajo. “Lenguajes, gramáticas y autómatas. Un enfoque práctico”. Addison Wesley. 2001.
D. Kelley. “Teoría de autómatas y lenguajes formales”. Prentice Hall. 1995.
T.A. Sudkamp. “Languages and machines: an introduction to the theory of computer science”. Addison Wesley. 2005
Competencias
Capacidade para resolver problemas con iniciativa, autonomía e creatividade. Capacidade de análise e síntese. Capacidade para comprender e dominar os conceptos básicos de algorítmica e complexidade computacional, e a súa aplicación para a resolución de problemas propios da enxeñaría.
Coñecer e comprender a capacidade que aportan os distintos modelos abstractos de computación. Coñecer e comprender os fundamentos e límites da computación, e así a existencia de problemas computables e non computables, e entre os primeiros, a existencia de problemas tratables e intratables. Coñecer, comprender e saber aplicar un conxunto de técnicas da investigación en operacións que dan lugar a algoritmos ben coñecidos na resolución de problemas de enxeñaría. Coñecer, comprender e manexar as técnicas de resolución de problemas baseadas nunha representación do coñecemento. Coñecer, comprender e saber aplicar as metodoloxías de deseño de sistemas baseados no coñecemento.
Metodoloxía da ensinanza
Clases de teoría.
O profesor elaborará material de estudo para cada un dos temas, de tal forma que o alumno poida seguir a clase. Nas transparencias tamén se inclúen problemas, algúns dos cales serán resoltos en clase, mentres que outros deberá solucionalos o propio alumno dentro do seu tempo de estudo da materia. Moitos dos exercicios foron extraídos de exames de anos anteriores.
Sesións de prácticas.
As sesións de prácticas serán de dúas horas de duración, e proporanse 12 boletíns. Antes de acudir a cada sesión de prácticas é imprescindible estudar a teoría correspondente. Tamén é aconsellable que o alumno resolva pola súa conta algún problema do tema.
Empregarase o Campus Virtual da USC como ferramenta de apoio ao proceso de aprendizaxe nos seguintes aspectos: respositorio de materiais (transparencias, exercicios), entrega e avaliación comentada de traballos obrigatorios e titorización virtual (correo electrónico e foros).
Sistema de evaluación
A avaliación da materia realizarase en dúas partes: teoría e prácticas. Para aprobar a materia é imprescindible superar ámbalas dúas partes por separado.
A parte teórica avaliarase cun exame final escrito co que o alumno poderá lograr un máximo de 10 puntos. Ademais, ao longo do curso realizaranse tres exames parciais que permitirán sumar até un máximo de 1,5 puntos á nota do exame final de teoría.
A parte práctica da materia avaliarase mediante a entrega dos boletíns de prácticas correspondentes a cada sesión, así como por medio dun test semanal no que se responderán preguntas relativas ó boletín entregado.
A nota final da materia será a media aritmética das partes teórica e práctica, excepto naquelas situacións nas que non se aprobou algunha das dúas partes, nese caso a nota final será o mínimo entre a parte teórica e a práctica.
A entrega dalgún dos boletíns de prácticas ou dalgunha das probas de avaliación continua suporá que o alumno se presenta á materia. Por tanto, a partir dese momento, non presentarse ao exame final suporá o suspenso na materia.
Na avaliación de xullo conservarase sen variación as notas de prácticas e das probas de avaliación continua de teoría obtidas ao longo do cuadrimestre. Deberase facer o exame final de teoría, non conservándose a nota anterior.
A copia total ou parcial dalgún exercicio de prácticas ou teoría supoñerá o suspenso nas dúas oportunidades do curso coa cualificación de 0 en ambos os dous casos.
Tempo de estudo e traballo persoal
O tempo de traballo do alumno na materia ao longo do curso desglósase do seguinte xeito:
(1) 25 horas de asistencia ás clases teóricas (2h/semana).
(2) 25 horas de asistencia obrigatoria a clases de prácticas (2h/semana).
(3) 7,5 horas dedicadas á realización de actividades de avaliación (exames parciais e final).
(4) 85 horas de estudo autónomo e de realización de traballos e prácticas (5-6h/semana).
(5) 7,5 horas de avaliación de traballos e prácticas mediante test.
Recomendacións para o estudo da materia
Recoméndase levar o estudo da teoría e a realización de prácticas e problemas ao día, xa que a avaliación mediante test semanais así o require. Do mesmo xeito, considérase importante facer un uso intenso das titorías para a resolución de dúbidas.