Teoria da Computação
Áreas Científicas |
Classificação |
Área Científica |
OFICIAL |
Fundamentos da Programação |
Ocorrência: 2007/2008 - 2S
Ciclos de Estudo/Cursos
Língua de trabalho
Português
Objetivos
Ao completar a disciplina, espera-se que os alunos sejam capazes de:
- Nomear as contribuições significativas para a teoria da computação e os seus protagonistas;
- Identificar problemas tratáveis com autómatos finitos e exprimi-los com notação rigorosa;
- Comparar os autómatos finitos deterministas, não deterministas e as expressões regulares no reconhecimento das linguagens regulares;
-Aplicar as propriedades das linguagens regulares em provas;
- Identificar problemas que se podem tratar com gramáticas sem contexto e usar notação rigorosa para os descrever;
- Comparar as gramáticas sem contexto e os autómatos de pilha no reconhecimento das linguagens sem contexto;
- Exprimir problemas de computação com recurso ao modelo da máquina de Turing;
-Relacionar os modelos de computação estudados com as suas aplicações na teoria da computabilidade e da complexidade.
Programa
Teoria dos Autómatos. Autómatos finitos.
Expressões regulares e linguagens. Propriedades das linguagens regulares.
Gramáticas e linguagens sem contexto.
Autómatos de pilha.
Propriedades das linguagens sem contexto.
Introdução às máquinas de Turing.
Bibliografia Obrigatória
Hopcroft, John E.;
Introdução à teoria de autômatos, linguagens e computação. ISBN: 85-352-1072-5
Bibliografia Complementar
Sudkamp, Thomas A.;
Languages and Machines. ISBN: 0-201-15768-3
Métodos de ensino e atividades de aprendizagem
As aulas teóricas são usadas para exposição formal da matéria, acompanhada da apresentação de exemplos, realização de exercícios e sua discussão.
Nas aulas teórico-práticas são propostos exercícios de aplicação. Aproximadamente a meio do semestre é realizado um mini-teste com o objectivo de testar se os conceitos básicos estão a ser dominados pela generalidade dos alunos.
O esforço previsto para além das aulas é de cerca de 4H semanais.
Palavras Chave
Ciências Físicas > Matemática > Matemática computacional
Ciências Físicas > Ciência de computadores
Tipo de avaliação
Avaliação distribuída com exame final
Componentes de Avaliação
Descrição |
Tipo |
Tempo (Horas) |
Peso (%) |
Data Conclusão |
Aulas da disciplina (estimativa) |
Participação presencial |
56,00 |
|
|
Exame Final |
Exame |
2,00 |
|
|
Mini-Teste |
Exame |
1,00 |
|
2008-04-08 |
|
Total: |
- |
0,00 |
|
Componentes de Ocupação
Descrição |
Tipo |
Tempo (Horas) |
Data Conclusão |
Estudo e realização de exercícios |
Estudo autónomo |
56 |
2008-07-31 |
|
Total: |
56,00 |
|
Obtenção de frequência
Avaliação distribuída não inferior a 6.
Fórmula de cálculo da classificação final
AD: avaliação distribuída.
TPC: exercícios entregues nas aulas teórico-práticas.
EF: exame final.
Nota = arredonda(0,3 AD + 0,1 TPC + 0,6 EF).
Provas e trabalhos especiais
Não há provas nem trabalhos especiais.
Avaliação especial (TE, DA, ...)
Exame final.
Melhoria de classificação
A nota final da disciplina pode ser melhorada através de um exame de melhoria de classificação.
Observações
Consideram-se pre-requisitos o domínio das matérias de Lógica e teoria de prova e conhecimentos de programação.