| Competencias / Resultados do título |
| Código | Competencias / Resultados do título |
| Resultados de aprendizaxe | |||
| Resultados de aprendizaxe | Competencias / Resultados do título | ||
| Coñecer en profundidade a estrutura e función dos sistemas de descrición e recoñecemento de linguaxes formais. | A39 A40 |
B6 |
C7 |
| Estudar os conceptos, modelos e técnicas relacionados con estas cuestións. | A39 A40 |
B6 |
C7 |
| Coñecer as estruturas de datos e os algoritmos utilizados para implementar os distintos modelos de recoñecemento de linguaxes formais, así como os seus posibles dominios de aplicación práctica. | A41 |
B6 |
C6 C7 |
| Realizar implementacións destes modelos nalgún deses dominios. | A41 |
B1 B2 B3 |
C6 |
| Sintetizar todos os conceptos estudados en ideas concretas que permitan comprender mellor os fundamentos da computación. | A39 |
B6 |
C7 |
| Perfeccionar as habilidades para realizar futuros traballos de análises, deseño e programación. | A40 A41 |
B1 B2 B3 |
C6 |
| Considerar a integración das técnicas e estruturas estudadas aquí noutros dominios de aplicación. | A40 A41 |
B1 B2 B3 B8 |
C6 |
| 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 | A39 A40 B8 C6 C7 | 18 | 36 | 54 |
| Prácticas de laboratorio | A40 A41 B1 B2 B3 B6 B8 C6 | 13 | 26 | 39 |
| Proba de resposta breve | A39 A40 B1 C6 C7 | 3 | 6 | 9 |
| Solución de problemas | B1 B3 B6 | 4 | 20.5 | 24.5 |
| Proba obxectiva | A39 A40 B1 C6 C7 | 3 | 16 | 19 |
| Atención personalizada | 4.5 | 0 | 4.5 | |
| *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. |
| 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 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. |
| 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 entregar ao profesor as súas solucións persoais a estes exercicios. O profesor deberá corrixilas, avalialas e comentalas durante polo menos unha sesión. |
| Proba obxectiva | Implementarase baixo a forma dun exame final escrito. |
| Atención personalizada |
|
|
| Avaliación | |||
| Metodoloxías | Competencias / Resultados | Descrición | Cualificación |
| Proba obxectiva | A39 A40 B1 C6 C7 | Exame final escrito. (***) | 0 |
| Solución de problemas | B1 B3 B6 | Boletíns de exercicios e controles dos mesmos. | 10 |
| Proba de resposta breve | A39 A40 B1 C6 C7 | Controles con cuestións teóricas e prácticas ao final de cada bloque temático. (**) | 60 |
| Prácticas de laboratorio | A40 A41 B1 B2 B3 B6 B8 C6 | Implementación de algoritmos nalgunha linguaxe de programación e resolución de problemas. (*) | 30 |
| 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. |