Disciplina da Secção de Lógica e Computação.
Curso: LEIC (Licenciatura em Engenharia Informática e de Computadores). Ano: 1. Semestre: 2.
Professor Responsável: Carlos Caleiro.
Semestre corrente: AVISOS e outras informações.
Aprender a trabalhar com modelos computacionais comuns, desde os autómatos finitos às máquinas de registos. Entender e saber utilizar a teoria das linguagens regulares. Compreender o conceito de computabilidade e seus limites.
Autómatos finitos deterministas. Propriedades de fecho de linguagens regulares. Equivalência e minimização de autómatos finitos deterministas. Lema da bombagem para linguagens regulares. Autómatos finitos não deterministas. Equivalência de autómatos finitos deterministas e não deterministas relativamente às linguagens reconhecidas. Gramática, gramática livre de contexto e gramática regular. Expressões regulares. Raciocínio sobre expressões regulares. Conversão entre as diferentes representações de linguagens regulares: da gramática regular para a expressão regular e da expressão regular para a gramática regular; da expressão regular para o autómato finito não determinista com movimentos épsilon; do autómato finito determinista para a gramática regular; da gramática regular para o autómato finito não determinista. Máquina URM. Funções computáveis e predicados decidíveis. A classe das funções parciais recursivas: definição indutiva (estudo detalhado da composição, recursão e minimização). Teorema de Kleene: identidade das classes das funções computáveis pela máquina URM e das funções parciais recursivas. Gödelização de programas URM. Existência de funções não computáveis: diagonalização. O teorema s-m-n e o teorema de Rice. Funções universais e programa universal. Problemas clássicos da computabilidade e da decidibilidade (problema da paragem inter alia) e aplicações.
Fichas semanais (35%) + Fichas electrónicas (15%) + Exame final (50%).
Aulas teóricas: 3h. Aulas práticas: 2h. Estudo recomendado: 3h.
Última actualização: 12 de Fevereiro de 2003.