Teoria da Computação

Código:

L.EIC010

Sigla:

TC

Áreas Científicas
Classificação	Área Científica
OFICIAL	Engenharia Informática e Computação

Ocorrência: 2023/2024 - 2S

Ativa?	Sim
Página Web:	https://moodle2324.up.pt/course/view.php?id=5619
Unidade Responsável:	Departamento de Engenharia Informática
Curso/CE Responsável:	Licenciatura 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
L.EIC	502	Plano Oficial	1	-	6	52	162

Língua de trabalho

Português - Suitable for English-speaking students

Objetivos

Preparar os estudantes em tópicos relacionados com modelos da computação e sobre as classes de linguagens formais associadas.

Munir os estudantes dos conhecimentos necessários que lhes permitam utilizar corretamente  linguagens regulares, expressões regulares, autómatos finitos determinísticos e não-determinísticos, linguagens e gramáticas  independentes de contexto, autómatos de pilha, e Máquinas de Turing.

Capacitar os estudantes para que estes sejam capazes de expressar problemas computacionais usando linguagens formais, autómatos e máquinas de Turing.

Capacitar os estudantes de métodos para formalizar problemas computacionais relacionados com linguagens  formais.

Resultados de aprendizagem e competências

Ao completar a unidade curricular, espera-se que os estudantes sejam capazes de:

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

- Identificar problemas tratáveis com autómatos finitos e exprimi-los com notação rigorosa;

- Comparar os autómatos finitos determinísticos, não-determinísticos e as expressões regulares no reconhecimento das linguagens regulares;

- Usar as propriedades das linguagens regulares;

- Identificar problemas que se podem tratar com gramáticas independentes de contexto e descrevê-los usando esses formalismos;

- Comparar as gramáticas independentes de contexto e os autómatos de pilha no reconhecimento das LICS;

- Exprimir problemas usando máquina de Turing;

- Relacionar os modelos de computação estudados com as suas aplicações na teoria da computabilidade e da complexidade.

Modo de trabalho

Presencial

Pré-requisitos (conhecimentos prévios) e co-requisitos (conhecimentos simultâneos)

É recomendado que os estudantes tenham frequentado a unidade curricular de Matemática Discreta.

Programa

Noção de linguagem formal. Autómatos finitos determinísticos e não determinísticos.

Expressões regulares, autómatos finitos e linguagens regulares.

Propriedades das linguagens regulares;

Minimização de autómatos finitos determinísticos. Lema da repetição para linguagens regulares. 

Linguagens e gramáticas independentes de contexto.

Autómatos de pilha;

Propriedades das linguagens independentes de contexto (LIC). Lema da repetição para LICs.

Introdução às Máquinas de Turing e noção de computabilidade.

Bibliografia Obrigatória

John E. Hopcroft; Introduction to automata theory, languages, and computation. ISBN: 978-1-292-03905-3

Bibliografia Complementar

Hopcroft, John E.; Introdução à teoria de autômatos, linguagens e computação. ISBN: 85-352-1072-5
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.

São propostos exercícios semanais 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.

Software

JFLAP is software for experimenting with formal languages topics. (https://www.jflap.org/)
https://automata-tutor.model.in.tum.de/index
http://turingmachine.io/
https://pypi.org/project/fado/

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 sem exame final

Componentes de Avaliação

Designação	Peso (%)
Teste	90,00
Trabalho prático ou de projeto	10,00
Total:	100,00

Componentes de Ocupação

Designação	Tempo (Horas)
Estudo autónomo	103,00
Frequência das aulas	59,00
Total:	162,00

Obtenção de frequência

Um máximo de 3 faltas (25%) nas aulas TP.

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

Serão realizados dois testes escritos, cada um com peso de 45% da nota final, sendo o segundo na época de exames normal. 

Além disso, os alunos realizarão em algumas aulas TP um exercício a ter correção para avaliação. O total dos exercícios contará 10% da nota final.

Nota final de avaliação contínua: 10% exercício + 45% teste1 + 45% teste2.

Nota final de exame: 100% exame.

Provas e trabalhos especiais

Não há provas nem trabalhos especiais.

Avaliação especial (TE, DA, ...)

No caso de alunos com estatuto TE, serão realizados dois testes escritos, cada um com peso de 50% da nota final, sendo o segundo na época de exames normal. Os alunos terão de obter em cada teste uma nota mínima não inferior a 6 valores (em 20). 

Nota final de avaliação contínua: 50% teste1 + 50% teste2.

Nota final de exame: 100% exame.

Melhoria de classificação

A nota final da disciplina pode ser melhorada através de um exame de melhoria de classificação (implica inscrição para melhoria de nota). Em caso de melhoria, a nota obtida neste exame é a nota final a TC.