Modelos de Computação

Código:

CC218

Sigla:

CC218

Áreas Científicas
Classificação	Área Científica
OFICIAL	Ciência de Computadores

Ocorrência: 2011/2012 - 2S

Ativa?	Sim
Unidade Responsável:	Departamento de Ciência de Computadores
Curso/CE Responsável:	Licenciatura em Geologia

Ciclos de Estudo/Cursos

Sigla	Nº de Estudantes	Plano de Estudos	Anos Curriculares	Créditos UCN	Créditos ECTS	Horas de Contacto	Horas Totais
L:AST	0	Plano de Estudos a partir de 2008	3	-	5	49	135
L:B	0	Plano de estudos a partir de 2008	3	-	5	49	135
L:CC	53	Plano de estudos de 2008 até 2013/14	2	-	5	49	135
L:F	1	Plano de estudos a partir de 2008	3	-	5	49	135
L:G	2	P.E - estudantes com 1ª matricula anterior a 09/10	3	-	5	49	135
		P.E - estudantes com 1ª matricula em 09/10	3	-	5	49	135
L:M	0	Plano de estudos a partir de 2009	3	-	5	49	135
L:Q	0	Plano de estudos Oficial	3	-	5	49	135
MI:ERS	70	Plano de Estudos a partir de 2007	2	-	5	49	135

Língua de trabalho

Português

Objetivos

Introdução ao estudo das linguagens formais. Pretende-se que o aluno seja capaz de especificar linguagens formais usando formas de descrição alternativas e determinar a sua classificação na hierarquia de poder computacional.

Programa

Noção de linguagem formal. Autómatos finitos determinísticos e não determinísticos. Expressões regulares e autómatos finitos. Propriedades das linguagens regulares. Minimização de autómatos finitos. Lema da repetição para linguagens regulares. Linguagens e gramáticas independentes de contexto. Árvores de derivação. Ambiguidade. Simplificações de gramáticas independentes de contexto e formas normais. Propriedades das linguagens independentes de contexto (LIC). Lema da repetição para LICs. Máquinas de Turing e noção de computabilidade.

Bibliografia Obrigatória

John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman; Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 2006. ISBN: 0-321-47617-4
Dexter C. Kozen; Automata and Computability, Sringer, 1997. ISBN: ISBN 0-387-94907-0
Mark V. Lawson; Finite Automata, Chapman & Hall/CRC, 2004. ISBN: 1-58488-255-7

Métodos de ensino e atividades de aprendizagem

Exposição da matéria realizada pela docente.
Disponibilização de folhas de exercícios com indicação antecipada dos exercícios a serem tratados nas aulas práticas em cada semana.
Marcação de horário regular de atendimento para apoio aos alunos.

Tipo de avaliação

Avaliação distribuída com exame final

Obtenção de frequência

No dia 18/4/2012 será realizado um teste com valoração total de 6 valores.
Para obter frequência à disciplina é exigida uma classificação mínima de 2 valores no teste.

Os alunos que não obtiverem frequência, não serão admitidos a exame.

Fórmula de cálculo da classificação final

O exame final terá a classificação de 20 valores.

Para os alunos com aprovação no exame a classificação final na disciplina é calculada pela fórmula seguinte:

NotaFinal = max(NE;NE/20*14+NT)

onde NE e NT denotam respetivamente as classificações obtidas no exame e no teste.

Provas e trabalhos especiais

Teste obrigatório no dia 18/4/2012 às 14h30
nas salas de Exposições e Exames (Dep. de Química).

Melhoria de classificação

Não é possível a melhoria da classificação no teste.

Observações

O horário de atendimento é:

3as: 10h30-11h30
5as: 12h30-13h30