Código: 21078
ECTS: 6
Departamento: Departamento de Ciências e Tecnologia
Área Científica: Engenharia Informática
Palavras-Chave:
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:
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
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
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