| Competencias / Resultados do título |
| Código | Competencias / Resultados do título |
| Resultados de aprendizaxe | |||
| Resultados de aprendizaxe | Competencias / Resultados do título | ||
| Comprender os conceptos da teoría de autómatas e das linguaxes formais, e estudar as súas aplicacións. | A2 A3 |
B2 B3 B4 B9 |
C2 |
| Coñecer os diferentes modelos de máquinas computacionales, gramáticas e linguaxes formais, así como a correspondencia entre autómatas, linguaxes e gramáticas. | A2 A3 |
B5 B6 B7 B8 B9 B10 |
C3 |
| Asimilar e aplicar os conceptos de decidibilidade e complexidade computacional. | A2 A3 |
B2 B3 B5 B6 B7 B8 B10 |
C2 C3 |
| Contidos |
| Temas | Subtemas |
| Preliminares sobre linguaxes formais | Alfabetos, palabras e linguaxes Linguaxes regulares e expresións regulares Autómatas finitos |
| Linguaxes independentes do contexto e autómatas de pila | Gramáticas regulares Gramáticas regulares e linguaxes regulares Gramáticas independentes do contexto Árbores de derivación e ambigüidade Simplificación de gramáticas independentes do contexto Propiedades das linguaxes independentes do contexto Algoritmos de análise sintáctico Autómatas de pila Forma normal de Greibach |
| Máquinas de Turing | Definicións básicas Máquinas de Turing como aceptadoras de linguaxes Construción de máquinas de Turing Modificacións das máquinas de Turing Máquina de Turing universal |
| Linguaxes recursivamente enumerables | Linguaxes aceptadas por máquinas de Turing Linguaxes regulares e independentes do contexto como linguaxes recursivas Propiedades das linguaxes recursivas e recursivamente enumerables Gramáticas non restrinxidas e linguaxes recursivamente enumerables Linguaxes sensibles ao contexto e a xerarquía de Chomsky |
| Resolubilidade | O problema da parada O problema de correspondencia de Post Problemas non decidibles en linguaxes independentes do contexto |
| Computabilidade | Fundamentos da teoría de funcións recursivas Alcance das funcións recursivas primitivas Funcións recursivas parciais O poder das linguaxes de programación |
| Planificación | ||||
| Metodoloxías / probas | Competencias / Resultados | Horas lectivas (presenciais e virtuais) | Horas traballo autónomo | Horas totais |
| Sesión maxistral | B3 B4 B5 B6 B9 B10 C3 | 24 | 18 | 42 |
| Solución de problemas | B3 B4 B5 B6 B9 B10 C3 | 3 | 9 | 12 |
| Proba de resposta breve | B3 B4 B5 B6 B9 B10 C3 | 3 | 12 | 15 |
| Prácticas de laboratorio | A2 A3 B2 B6 B7 B8 B9 B10 C2 C3 | 30 | 30 | 60 |
| Proba obxectiva | B3 B4 B5 B6 B9 B10 C3 | 3 | 12 | 15 |
| Atención personalizada | 6 | 0 | 6 | |
| *Os datos que aparecen na táboa de planificación son de carácter orientativo, considerando a heteroxeneidade do alumnado | ||||
| Metodoloxías |
| Metodoloxías | Descrición |
| Sesión maxistral | A técnica que mellor se adapta á impartición dos contidos teóricos desta materia está constituída polas clases maxistrais. Nelas, faremos un uso intensivo da lousa virtual e das transparencias, de modo que o ritmo de exposición de conceptos por parte do profesor e o de asimilación dos mesmos por parte do alumno sexan o máis acordes posible. |
| Solución de problemas | Poranse a disposición dos alumnos unha serie de boletíns de exercicios, correspondentes aos bloques temáticos do programa da materia. Os alumnos deberán elaborar as súas solucións persoais a estes exercicios. O profesor deberá comentar as solucións durante polo menos unha sesión. |
| Proba de resposta breve | Realizaranse controles ao final de cada bloque temático, que permitirán ao profesor coñecer o grao de asimilación da materia por parte dos alumnos, e modificar a estratexia docente se é necesario. |
| Prácticas de laboratorio | Estas prácticas serán utilizadas para implementar nalgunha linguaxe de programación os algoritmos máis destacados, de entre todos aqueles que fosen presentados nas sesións teóricas. |
| Proba obxectiva | Implementarase baixo a forma dun exame final escrito. |
| Atención personalizada |
|
|
| Avaliación | |||
| Metodoloxías | Competencias / Resultados | Descrición | Cualificación |
| Prácticas de laboratorio | A2 A3 B2 B6 B7 B8 B9 B10 C2 C3 | Implementación de algoritmos nalgunha linguaxe de programación e resolución de problemas. (*) | 40 |
| Proba de resposta breve | B3 B4 B5 B6 B9 B10 C3 | Controles con cuestións teóricas e prácticas ao final de cada bloque temático. (**) | 60 |
| Proba obxectiva | B3 B4 B5 B6 B9 B10 C3 | Exame final escrito. (***) | 0 |
| Observacións avaliación | |||
|
(*) Nas prácticas de laboratorio, requírese que o alumno obtenga unha nota mínima de 3 puntos (sobre 10). (**) A materia dividirase en tres bloques temáticos. Ao final de cada bloque temático, realizarase un control con cuestións teóricas e prácticas. Cada control poderá consolidar ata un 20% da cualificación. A porcentaxe correspondente aos controles non superados pasará a computarse na proba obxectiva (examen final). Os alumnos que superen os tres controles, non terán que realizar o exame final. (***) No caso de ter que realizar o exame final, requírese que o alumno obtenga unha nota mínima de 3 puntos (sobre 10). Os alumnos a tempo parcial terán consideracións adecuadas á súa situación. |
|||
| Fontes de información |
| Bibliografía básica |
John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman (2002). Introducción a la teoría de autómatas, lenguajes y computación. Addison Wesley
Thomas A. Sudkamp (1988). Languages and machines: an introduction to the theory of computer science. Addison Wesley
Dean Kelley (1995). Teoría de autómatas y lenguajes formales . Prentice Hall |
|
|
|
| Bibliografía complementaria |
Alan P. Parkes (2008). A concise introduction to languages and machines. Springer-Verlag
Maxim Mozgovoy (2010). Algorithms, languages, automata and compilers, a practical approach. Jones & Bartlet Learning Publishers
Peter Linz (2017). An introduction to formal languages and automata. Jones & Bartlet Learning
Harry R. Lewis, Christos H. Papadimitriou (1998). Elements of the theory of computation . Prentice Hall
Peter J. Denning, Jack B. Dennis, Joseph E. Qualitz (1978). Machines, languages and computation . Prentice Hall
J. Glenn Brookshear (1993). Teoría de la computación: lenguajes formales, autómatas y complejidad . Addison Wesley Iberoamericana |
|
|
| Recomendacións | ||||
| Materias que se recomenda ter cursado previamente | ||||
|
| Materias que se recomenda cursar simultaneamente |
| Materias que continúan o temario | |
|
| Observacións | |
|
-Segundo se recolle nas distintas normativas de aplicación para a docencia universitaria incorporarase a perspectiva de xénero nesta materia (usarase linguaxe non sexista, propiciarase a intervención en clase de alumnos e alumnas., etc.). -Traballarase para identificar e modificar prexuízos e actitudes sexistas e influirase na contorna para modificalos e fomentar valores de respecto e igualdade. - No caso de detectar situacións de discriminación por razón de xénero proporanse accións e medidas para corrixilas. |