Guia de Cursos

Queres conhecer a oferta de cursos da NOVA, nas áreas das licenciaturas, mestrados e doutoramentos?
No nosso Guia de Cursos encontras informação útil sobre Faculdades, Institutos e Escolas.
Podes ainda aceder a informações complementares necessárias a uma completa integração.

saber mais Guia de Cursos

Faculdade de Ciências e Tecnologia

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

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 opcional, constituida por quatro mini-testes de resposta múltipla, a realizar em aulas teóricas, valendo cada um 1 valor da nota final. Quem obteve frequência no ano passado mas não aprovou na cadeira pode ter a nota de frequência convertida (multiplicada por 4/5).

A avaliação contínua compreende ainda uma componente obrigatória, constituida por dois testes, valendo para a nota final cada um 8 valores. Para se obter aprovação, a soma das notas deve ser superior ou igual a 7,45.

O exame tem duas partes, correspondendo a cada um dos testes. Pode-se fazer melhoria de qualquer um dos dois testes, mesmo para obter aprovação. Não haverá possibilidade de fazer melhoria dos mini-testes, mas é possível optar por realizar o exame para 20 valores ou cada uma das partes para 10 valores, prescidindo-se da nota obtida nos mini-testes.

Cursos