LINGUAGENS E COMPUTAçãO
Código: 21078
ECTS: 6
Departamento: Departamento de Ciências e Tecnologia
Área Científica: Engenharia Informática
Palavras-Chave:
    1. Linguagens regulares
    2. Linguagens independentes do contexto
    3. Máquinas de Turing
    4. Decidibilidade e tratabilidade
Docente:
Jorge Morais
Correio Eletrónico: jmorais@uab.pt

Sinopse:
A relação entre as linguagens formais e a computação é o tema desta unidade curricular. São abordados os vários formalismos de representação de linguagens, até ao conceito que deu origem ao computador actual: a máquina de Turing. As noções de decidibilidade, tratabilidade e complexidade computacional estão intimamente relacionadas com este conceito.


Competências:
Ao concluir esta unidade curricular o aluno deverá estar capaz de:
Compreender e aplicar os vários tipos de linguagens formais.
Estabelecer relações entre algoritmos/problemas e a sua representação formal em termos de máquina de Turing.


Conteúdos:
Autómatos.
Expressões e linguagens regulares.
Gramáticas e linguagens independentes do contexto.
Máquinas de Turing.
Decidibilidade e Tratabilidade.


Bibliografia:
Hopcroft & Ullman. Introduction to Automata and Language Theory. Addison-Wesley.
Valença & Barros. Fundamentos da Computação, Vol. I & II. Universidade Aberta.


Metodologias de Ensino:

E-learning.




Total de Horas de Trabalho: 156
Total de Horas de Contacto: 26

Avaliação:
O regime de avaliação preferencial é o de avaliação contínua, constituída pela realização de 2/3 e-folios (trabalhos escritos em formato digital), ao longo do semestre letivo, e de um momento final de avaliação presencial (p-fólio), a ter lugar no final do semestre, com peso de, respetivamente, 40% e 60% na classificação final. Os estudantes podem, no entanto, em devido tempo, optar um único momento presencial de avaliação, realizando, então uma prova de Avaliação Final (exame) com o peso de 100%.


Observações:
Apresentação pessoal do docente