FenixEdu™

Disciplina

Elementos de Teoria da Computação

Área

Área Científica de Lógica e Computação > Lógica e Computação

Activa nos planos curriculares

AFA_CMA-Eng > AFA_CMA-Eng > 1º Ciclo > Área Principal > Ramo Eletrotecnica > Elementos de Teoria da Computação

LEEC 2021 > LEEC 2021 > 1º Ciclo > Formação Fundamental > Elementos de Teoria da Computação

Nível

Exame/testes, possivelmente com nota mínima, complementado com componente de avaliação contínua.

Tipo

Não Estruturante

Regime

Semestral

Carga Horária

1º Semestre

Aula Teórica (T): 1.0 h/semana

Aula de Problemas (PB): 1.0 h/semana

Trabalho Autónomo: 56.0 h/semestre

Créditos ECTS:

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.

Pré-requisitos

Não tem.

Componente Laboratorial

Não tem.

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.

Componente de Programação e Computação

Não se aplica.

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%.