Competencias do título |
Código
|
Competencias da titulación
|
A39 |
Capacidade para ter un coñecemento profundo dos principios fundamentais e modelos da computación, e saber aplicalos para interpretar, seleccionar, valorar, modelar, e crear novos conceptos, teorías, usos e desenvolvementos tecnolóxicos relacionados coa informática. |
A40 |
Capacidade para coñecer os fundamentos teóricos das linguaxes de programación e as técnicas de procesamento léxico, sintáctico e semántico asociadas, e saber aplicalas para a creación, o deseño e o procesamento de linguaxes. |
A41 |
Capacidade para avaliar a complexidade computacional dun problema, coñecer estratexias algorítmicas que poidan conducir á súa resolución e recomendar, desenvolver e implementar aquela que garanta o mellor rendemento de acordo cos requisitos establecidos. |
B1 |
Capacidade de resolución de problemas |
B2 |
Traballo en equipo |
B3 |
Capacidade de análise e síntese |
B6 |
Toma de decisións |
B8 |
Capacidade de traballar nun equipo interdisciplinar |
C6 |
Valorar criticamente o coñecemento, a tecnoloxía e a información dispoñible para resolver os problemas cos que deben enfrontarse. |
C7 |
Asumir como profesional e cidadán a importancia da aprendizaxe ao longo da vida. |
Resultados de aprendizaxe |
Competencias de materia (Resultados de aprendizaxe) |
Competencias da titulación |
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 |
Horas presenciais |
Horas non presenciais / traballo autónomo |
Horas totais |
Sesión maxistral |
18 |
36 |
54 |
Prácticas de laboratorio |
13 |
26 |
39 |
Proba de resposta múltiple |
2 |
4 |
6 |
Traballos tutelados |
1 |
5.5 |
6.5 |
Solución de problemas |
4 |
17 |
21 |
Proba de ensaio |
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 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 |
As prácticas de laboratorio terán horas de laboratorio reservadas, con computadores a disposición dos alumnos. Estas horas 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 múltiple |
Realizaranse controles tipo test 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. |
Traballos tutelados |
Os traballos de grupos autónomos tutelados realizaranse ao longo de todo o cuadrimestre. O profesor elixirá un tema de traballo que será asignado por igual a todos os grupos. O tema será presentado polo profesor nunha sesión na aula, será desenvolvido polos alumnos en horas non presenciais, e será supervisado e avaliado polo profesor nas titorías en grupo. A avaliación realizarase a partir da exposición dunha memoria final por parte dos alumnos. |
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 na aula. |
Proba de ensaio |
Implementarase baixo a forma dun exame final escrito. |
Atención personalizada |
Metodoloxías
|
Traballos tutelados |
Prácticas de laboratorio |
|
Descrición |
Dado o carácter personalizado das prácticas de laboratorio, dos traballos tutelados e das titorías, estas actividades non deben dedicarse a estender os contidos con novos conceptos, senón a aclarar os conceptos xa expostos.
O profesor debe ademais utilizalas como unha interacción que lle permita extraer conclusións respecto ao grao de asimilación da materia por parte dos alumnos.
Desta maneira, poderá desenvolver as clases maxistrais e o resto de actividades non personalizadas atendendo ao progreso dos alumnos nas capacidades de comprensión e asimiliación dos contidos impartidos, compaxinando o avance xeral da clase cunha atención específica a aqueles alumnos que presenten maiores dificultades na tarefa da aprendizaxe e cun apoio adicional a aqueles outros que presenten maior soltura e desexen ampliar coñecementos.
|
|
Avaliación |
Metodoloxías
|
Descrición
|
Cualificación
|
Proba de ensaio |
Exame final escrito. |
40 |
Solución de problemas |
Boletíns de exercicios e controis dos mesmos. |
10 |
Proba de resposta múltiple |
Controles tipo test e cuestións. |
5 |
Traballos tutelados |
Traballo de grupos autónomos tutelados. |
5 |
Prácticas de laboratorio |
Implementación de algoritmos nalgunha linguaxe de programación e resolución de problemas. |
40 |
|
Observacións avaliación |
No exame final requírese 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
|
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 |
Representación do Coñecemento e Razoamento Automático/614G01036 | Recuperación da Información/614G01040 | Deseño das Linguaxes de Prgramación/614G01065 | Procesamento de Linguaxes/614G01067 |
|
Materias que se recomenda cursar simultaneamente |
|
Materias que continúan o temario |
Programación I/614G01001 | Matemática Discreta/614G01004 | Programación II/614G01006 | Álxebra/614G01010 | Algoritmos/614G01011 | Paradigmas de Programación/614G01014 |
|
|