Código: 21078ECTS: 6Departamento: Departamento de Ciências e TecnologiaÁrea Científica: Engenharia InformáticaPalavras-Chave: 1. Linguagens regulares
2. Linguagens independentes do contexto
3. Máquinas de Turing
4. Decidibilidade e tratabilidade
Docente:Jorge MoraisCorreio Eletrónico: jmorais@uab.ptSinopse:
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: 156Total de Horas de Contacto: 26Avaliaçã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