Disciplina Curricular
Teoria da Computação TCom
Licenciatura Bolonha em Engenharia Informática e de Computadores - Alameda - LEIC-A 2021
Contextos
Grupo: LEIC-A 2021 > 1º Ciclo > Formação Fundamental
Período:
Peso
6.0 (para cálculo da média)
Objectivos
Aprender a trabalhar com modelos computacionais comuns: autómatos finitos, autómatos de pilha e máquinas de Turing. Entender e saber utilizar os conceitos de maquinismo, linguagem formal, gramática, recursos computacionais. Compreender e aprofundar os conceitos de ''tarefa'' algorítmica e de ''tarefa'' não algorítmica. Conhecer os limites para ''tarefas'' algorítmicas e recursos computacionais envolvidos numa computação. Entender a computação como conceito físico-matemático e não como conceito puramente matemático.
Programa
Autómatos finitos determinísticos e não determinísticos. Linguagens e gramáticas regulares, expressões regulares. Autómatos de pilha. Linguagens e gramáticas livres de contexto. Lemas de bombagem. Hierarquia de Chomsky. Máquinas de Turing determinísticas e não determinísticas. Funções computáveis. Linguagens reconhecíveis e decidíveis. Postulado de Church-Turing. Propriedades de fecho das linguagens decidíveis e reconhecíveis. Conjuntos e cardinalidade. Representação canónica de máquinas de Turing. Existência de linguagens indecidíveis. Indecidibilidade do problema da terminação (introdução à técnica da diagonalização). Reduções computáveis. Teorema de Rice e aplicações. Teorema da recursão e vírus auto-replicáveis. Recursos computacionais. Classes de complexidade: P, PSPACE, NP, EXPTIME. Relações estruturais. Teorema de Savitch. Reduções polinomiais. P versus NP e linguagens NP-completas. Teorema de Cook-Levin. Teoremas de hierarquia. Separação de classes de complexidade.
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%.
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.