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: 2024/2025 - 2S

Ativa?	Sim
Página Web:	https://moodle2425.up.pt/course/view.php?id=5426
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	401	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	100,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

Os alunos terão de frequentar pelo menos 75% das aulas TP.

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

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

Nota final de exame: 100% exame.

Provas e trabalhos especiais

Não há provas nem trabalhos especiais.

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.