Teoria da Computação

Código:

EIC0022

Sigla:

TCOM

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

Ocorrência: 2006/2007 - 2S

Ativa?	Sim
Página Web:	https://www.fe.up.pt/si/conteudos_geral.conteudos_ver?pct_pag_id=1639&pct_parametros=p_ano_lectivo=2006/2007-y-p_cad_codigo=EIC0022-y-p_periodo=2S
Unidade Responsável:	Secção de 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
LEIC	0	Plano de estudos de transição para 2006/07	2	-	6	56	162
MIEIC	137	Plano de estudos oficial a partir de 2006/07	2	-	6	56	162
		Plano de estudos de transição para 2006/07	2	-	6	56	162

Língua de trabalho

Português

Objetivos

O primeiro objectivo é compreender alguns conceitos fundamentais de modelos de computação tais como os autómatos finitos e as máquinas de Turing.
O segundo objectivo é solidificar a capacidade de raciocinar formalmente sobre a computação e distinguir provas rigorosas de "evidências" ad-hoc.

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 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	48,00
Mini-Teste	Exame	1,00		2007-04-19
Exame Final	Exame	2,00
Trabalho de casa	Teste	14,00		2007-06-01
	Total:	-	0,00

Componentes de Ocupação

Descrição	Tipo	Tempo (Horas)	Data Conclusão
Estudo	Estudo autónomo	30	2007-06-29
	Total:	30,00

Obtenção de frequência

Avaliação distribuída não inferior a 6.

Fórmula de cálculo da classificação 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.