Aviso: Se está a ler esta mensagem,
provavelmente, o browser que utiliza não é
compatível com os "standards" recomendados pela W3C. Sugerimos vivamente que actualize
o seu browser para ter uma melhor experiência de
utilização deste "website". Mais
informações em webstandards.org.
Warning: If you are reading this message, probably,
your browser is not compliant with the standards recommended by the W3C. We suggest that you upgrade your
browser to enjoy a better user experience of this website. More
informations on webstandards.org.
Ser English-friendly ou qualquer outra língua-friendly, significa que a UC é leccionada numa língua mas que se pode verificar qualquer uma das
seguintes condições:
1. Existem materiais de apoio em língua inglesa/outra língua;
2. Existem exercícios, testes e exames em língua inglesa/outra língua;
3. Existe a possibilidade de se apresentar trabalhos escritos ou orais em língua inglesa/outra língua.
1
6.0
0.0 h/sem
54.0 h/sem
0.0 h/sem
0.0 h/sem
0.0 h/sem
0.0 h/sem
1.0 h/sem
55.0 h/sem
95.0 h/sem
0.0 h/sem
150.0 h/sem
Em vigor desde o ano letivo
2018/2019
Pré-requisitos
Nenhum
Objectivos
Aprendizagem de modelos computacionais (desde autómatos finitos às máquinas de Turing), sua utilização na resolução de problemas e estudo das suas limitações.
Programa
I Notação matemática e técnicas de demonstração Objectos matemáticos básicos: conjuntos, funções, relações e linguagens; Lógica, demonstrações e o princípio de indução matemática.
II Autómatos Finitos e Linguagens Regulares Linguagens regulares e expressões regulares. Autómatos finitos deterministas e não deterministas. Reconhecimento de linguagens regulares.
III Autómatos de Pilha e Linguagens Livres de Contexto Linguagens livres de contexto e gramáticas livres de contexto. Autómatos de pilha. Reconhecimento de linguagens livres de contexto.
IV Máquinas de Turing e Linguagens Recursivamente Enumeráveis Linguagens Recursivamente Enumeráveis. Máquinas de Turing. Tese de Church-Turing.
Processo de avaliação
I Avaliação periódica: 10 mini avaliações semanais online (10%) e duas frequências (90 %). Na avaliação periódica é obrigatório efetuar no mínimo 7 mini avaliações online. A presença nas aulas não é obrigatória.
ou
II Exame final.
A presença nas aulas não é obrigatória.
Processo de ensino-aprendizagem
Aulas teorico-práticas.
Observações
Nenhum
Bibliografia básica
J. Martin, Introduction to Languages and the Theory of Computation, McGraw-Hill, (3ª edição)2003, (4ª edição) 2011.
F. Santos, Teoria da Computação - Folhas de Apoio, ISCTE-IUL, 2013.
F. Santos, Teoria da Computação - Exercícios, ISCTE-IUL, 2015.
Bibliografia complementar
N. Cutland, Computability: An Introduction to Recursive Function Theory, Cambridge University Press, 1980.
J. Hopcroft, R. Motwani e J. Ullman, Introduction to Automata Theory, Languages and Computation, Addison Wesley, 2001.
D. Mandrioli e C. Ghezzi, Theoretical Foundations of Computer Science, John Wiley, 1987
