Modelos de Computação

Código:

CC218

Sigla:

CC218

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

Ocorrência: 2015/2016 - 2S

Ativa?	Sim
Página Web:	http://www.dcc.fc.up.pt/~apt/aulas/MC/1516
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	1	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:F	0	Plano de estudos a partir de 2008	3	-	5	49	135
L:G	0	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

Língua de trabalho

Português

Objetivos

Ensinar conceitos e resultados fundamentais sobre três modelos de computação básicos (autómatos finitos, autómatos de pilha e máquinas de Turing) e sobre as classes de linguagens formais associadas, com foco nas linguagens regulares e independentes de contexto.

Resultados de aprendizagem e competências

Capacidade de especificar linguagens formais simples usando formas de descrição alternativas e de determinar a sua classificação na hierarquia de poder computacional.

Modo de trabalho

Presencial

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. Autómatos de pilha. 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
Ana Paula Tomás; Introdução às Linguagens Formais e Modelos de Computação, DCC-FCUP, 2014. (Versão revista de Apontamentos de Modelos de Computação;Ana Paula Tomás, DCC-FCUP, 1999)

Métodos de ensino e atividades de aprendizagem

Aulas teóricas de exposição dos conteúdos programáticos.
Aulas práticas de resolução de exercícios propostos semanalmente.

Tipo de avaliação

Avaliação distribuída com exame final

Componentes de Avaliação

Designação	Peso (%)
Exame	100,00
Participação presencial	0,00
Teste	0,00
Total:	100,00

Obtenção de frequência

Perde a frequência o estudante que não estiver presente a pelo menos 75% das aulas práticas previstas.

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

Serão realizados dois testes escritos (TE1, TE2) para dispensa de exame final (Exame). Para acesso ao segundo teste escrito, será exigida uma classificação de pelo menos 8 valores no primeiro teste. O segundo teste é global.

A classificação final será calculada por

      max(05*TE1+0.5*TE2, TE2, Exame)

Melhoria de classificação

Por exame final.