Modelos de Computação
Áreas Científicas |
Classificação |
Área Científica |
OFICIAL |
Ciência de Computadores |
Ocorrência: 2024/2025 - 2S ![Requerida a integração com o Moodle Ícone do Moodle](/fcup/pt/imagens/MoodleIcon)
Ciclos de Estudo/Cursos
Docência - Responsabilidades
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
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 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 |
114,00 |
Frequência das aulas |
48,00 |
Total: |
162,00 |
Obtenção de frequência
Presença a pelo menos 3/4 das aulas práticas
Fórmula de cálculo da classificação final
Classificação final corresponde à classificação obtida
- como média aritmética dos dois testes, o primeiro a realizar durante o semestre e o segundo na data do exame da época normal (cada um com nota mínima de 6 valores). Os dois testes incidem respectivamente sobre a matéria lecdionada durante a primeira e a segunda parte do semestre.
- o exame da época de recurso não contabiliza a nota obtida nos testes e aborda toda a matéria leccionada durante o semestre.
Melhoria de classificação
Exame final (época de recurso)