Teoria da Computação

Código:

EIC0022

Sigla:

TCOM

Áreas Científicas
Classificação	Área Científica
OFICIAL	Fundamentos da Programação

Ocorrência: 2009/2010 - 1S

Ativa?	Sim
Página Web:	http://moodle.fe.up.pt/0910/course/view.php?id=531
Unidade Responsável:	Departamento de Engenharia Informática
Curso/CE Responsável:	Mestrado Integrado em Engenharia Informática e Computação

Ciclos de Estudo/Cursos

Sigla	Nº de Estudantes	Plano de Estudos	Anos Curriculares	Créditos UCN	Créditos ECTS	Horas de Contacto	Horas Totais
MIEIC	155	Plano de estudos a partir de 2009/10	2	-	6	56	162

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
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
Participação presencial (estimativa)	Participação presencial	52,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 2008/2009 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.