Disciplina Curricular
Elementos de Teoria da Computação ETC
Licenciatura Bolonha em Engenharia Eletrotécnica e de Computadores - LEEC 2021
Contextos
Grupo: LEEC 2021 > 1º Ciclo > Formação Fundamental
Período:
Peso
3.0 (para cálculo da média)
Pré-requisitos
Não tem.
Objectivos
Introduzir o conceito de algoritmo e de modelo de computação, nomeadamente de autómato finito e infinito (autómato de pilha e máquina de Turing). Estudar a hierarquia das linguagens. Resolver problemas algorítmicos através de circuitos booleanos e classificar a sua complexidade em termos de tamanho e profundidade dos circuitos.
Programa
Autómatos finitos; linguagens regulares, expressões regulares e gramáticas regulares. Autómatos de pilha; linguagens e gramáticas livres de contexto. Conceito de algoritmo segundo Turing. Máquinas de Turing. Universalidade. Máquinas de registos. Postulado de Church-Turing. Hierarquia de Chomsky. Problemas decidíveis e indecidíveis. Medidas de eficiência dos algoritmos. Recursos limitados de tempo e de espaço. Classes de complexidade e problemas completos. Circuitos booleanos e famílias de circuitos. Circuitos booleanos sequenciais. Circuitos booleanos combinatórios. Discussão da equivalência entre máquinas de Turing e famílias de circuitos booleanos. Alternação. Problemas completos para classes de circuitos booleanos.
Metodologia de avaliação
Exame/testes, possivelmente com nota mínima, complementado com componente de avaliação contínua.
Componente de Competências Transversais
A UC permite o desenvolvimento de competências transversais em Pensamento Crítico, Criatividade e Estratégias de Resoluções de Problemas, nas aulas, em trabalho autónomo e nas várias componentes de avaliação. A percentagem de avaliação associada a estas competências deverá ser da ordem dos 15%.
Componente Laboratorial
Não tem.
Componente de Programação e Computação
Não se aplica.
Princípios Éticos
Todos os membros de um grupo são responsáveis pelo trabalho do grupo. Em qualquer avaliação, todo aluno deve divulgar honestamente qualquer ajuda recebida e fontes usadas. Numa avaliação oral, todo aluno deverá ser capaz de apresentar e responder a perguntas sobre toda a avaliação.