Teoria da Computação
Código
2468
Unidade Orgânica
Faculdade de Ciências e Tecnologia
Departamento
Departamento de Informática
Créditos
6.0
Professor responsável
António Maria Lobo César Alarcão Ravara, Luís Manuel Marques da Costa Caires
Horas semanais
5
Total de horas
70
Língua de ensino
Português
Objectivos
Usar a lógica e a teoria de conjuntos para modelar dados e sistemas. Conhecer os fundamentos teóricos da computação, o conceito formal de algoritmo e a existência de problemas indecidíveis. Conhecer as classes de linguagens formais, os modelos computacionais associadas e a sua relação mútua. Compreender o conceito de universalidade Turing.
Modelar o espaço de estados de sistemas com conjuntos e lógica de 1º ordem. Distinguir conjuntos contáveis de não contáveis. Modelar sistemas com autómatos finitos (DFA e NFA). Construir um autómato dada uma expressão regular e o inverso. Construir um DFA equivalente a um NFA. Definir linguagens independentes de contexto com gramáticas. Construir analisadores LL e LR. Reconhecer a (in)decidibilidade de problemas computacionais.
Conteúdo
1. Modelação com Conjuntos e Lógica
Conjuntos, Funções, Relações (revisão). Finito e Infinito, argumento diagonal de Cantor. Diferença entre função e algoritmo. Definições indutivas. Modelos de sistemas simples e tipos abstractos de dados.
2. Máquinas, Autómatos e Especificações
O que é um modelo computacional? Automátos finitos deterministas e expressões regulares. Determinismo e não determinismo. Linguagens independentes de contexto e máquinas de pilha. Análise sintática (LL e LR).
3. Computabilidade
Complexidade básica (P,NP). Expressividade computacional. Equivalência entre programação funcional e imperativa. Máquinas abstractas e níveis de interpretação. Universalidade Turing. Tese de Church-Turing. Indecidibilidade (da terminação).
Bibliografia
Notas da UC ITC (Luís Caires, 2011).
Christos Papadimitriou and Harry Lewis: “Elements of the theory of computation”, Prentice-Hall, 1982, second edition 1997.
Método de ensino
O ensino está organizado em aulas teóricas e práticas. Existem notas escritas, que seguem de perto os conteúdos das aulas teóricas.
Nas aulas práticas os alunos discutem e resolvem exercícios propostos pelo docente, de uma lista predefinida. Nas aulas teóricas são apresentados os conceitos e discutidas situações problemáticas, em geral motivadas por desafios gerais de várias áreas da informática. Tipicamente as competências de saber fazer são também exercitadas nas aulas teóricas, de forma a aumentar a ligação entre os conceitos teóricos e a sua aplicação.
Método de avaliação
A cadeira tem uma componente de avaliação prática, constituida por quatro mini-testes a realizar em aulas práticas, valendo cada um 1 valor da nota final. Para se obter aprovação, a soma das notas, arredondada às décimas, deve ser superior ou igual a 2,2 valores (em 4).
A avaliação contínua compreende ainda uma componente teórica, constituida por dois testes, valendo para a nota final cada um 8 valores. Para se obter aprovação, a soma das notas, arredondada às décimas, deve ser superior ou igual a 6,5 (em 16).
O exame tem duas partes: uma prática, para ser realizada por quem não obteve nota mínima nos mini-testes (para 4 valores), e outra teórica, para ser realizada por quem não obteve nota mínima nos testes (para 16 valores). A parte prática tem a nota mínima dos mini-testes; a parte teórica tem a nota mínima dos testes.
Quem não obteve nota mínima em algumas das partes, tem que a repetir integralmente no exame. Quem obteve nota mínima, pode fazer melhoria de qualquer uma das partes que desejar, mas se ainda não obteve aprovação, a nota obtida nessa melhoria substitui a nota anterior.