Teoria da Computação
Áreas Científicas |
Classificação |
Área Científica |
OFICIAL |
Fundamentos da Programação |
Ocorrência: 2010/2011 - 1S
Ciclos de Estudo/Cursos
Língua de trabalho
Português
Objetivos
Ao completar a disciplina, espera-se que os estudantes 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
Sipser, Michael;
Introduction to the theory of computation. ISBN: 0-619-21764-2
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 > Ciência de computadores
Ciências Físicas > Matemática > Matemática computacional
Tipo de avaliação
Avaliação distribuída com exame final
Componentes de Avaliação
Descrição |
Tipo |
Tempo (Horas) |
Peso (%) |
Data Conclusão |
Participação presencial (estimativa) |
Participação presencial |
54,00 |
|
|
Exame |
Exame |
2,50 |
|
|
Mini-teste |
Exame |
1,50 |
|
|
|
Total: |
- |
0,00 |
|
Componentes de Ocupação
Descrição |
Tipo |
Tempo (Horas) |
Data Conclusão |
Estudo semanal |
Estudo autónomo |
78 |
|
Preparação para Exame/Mini-teste |
Estudo autónomo |
26 |
|
|
Total: |
104,00 |
|
Obtenção de frequência
Avaliação distribuída (AD) com nota do mini-teste (MT) não inferior a 6
e entrega da resolução de 8 das 9 fichas de exercícios sugeridas para TPC.
Fórmula de cálculo da classificação final
AD: avaliação distribuída constituída pelas componentes MT e TPC = 0,80 MT + 0,20 TPC
TPC: resolução das fichas de exercícios entregues nas aulas teórico-práticas.
MT: mini-teste.
EF: exame final.
Nota = arredonda(0,4 AD + 0,6 EF).
Provas e trabalhos especiais
Não há provas nem trabalhos especiais.
Avaliação especial (TE, DA, ...)
Uma das possibilidades seguintes:
- Exame final, ou
- Exame final + mini-teste (MT), e neste caso: Nota = arredonda(0,3 MT + 0,7 EF).
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 pré-requisitos o domínio das matérias de Lógica e teoria de prova e conhecimentos de programação.
- Os estudantes que tenham obtido frequência no ano lectivo de 2009/2010 e que não queiram repetir a frequência poderão utilizar a nota da AD obtida nesse ano lectivo.
- A lingua oficial das aulas é o Português. No entanto, adimite-se que as aulas possam ser leccionadas em Inglês.