Disciplina Curricular
Introdução à Computabilidade e Complexidade ICC
Licenciatura Bolonha em Matemática Aplicada e Computação - LMAC 2021
Contextos
Grupo: LMAC 2021 > 1º Ciclo > Área Principal
Período:
Peso
6.0 (para cálculo da média)
Objectivos
Dominar os conceitos, técnicas e resultados fundamentais da teoria da computabilidade e complexidade. Conhecer diversos modelos de computação e entender a sua equivalência. Conhecer as noções básicas da complexidade de Kolmogorov e complexidade computacional.
Programa
Função computável. Função universal e universal própria. Conjunto decidível e listável. Teorema de Post. Índices. Teoremas de Rice, Rice-Shapiro e Rice-Shapiro-McNaughton-Myhill. Computação com oráculos. Função computável face a um conjunto finito de oráculos. Operador computável. Preservação da computabilidade de funções por operador computável. Operador finitário e monótono. Critério de Myhill-Shepherdson. Teorema do ponto fixo de Kleene. Teoremas de Rogers e da recursão. Redutibilidade m. Graus decidíveis. Conjuntos efectivamente não listáveis, produtivos e completos m. Máquina de Turing e redutibilidade T. Complexidade de Kolmogorov. Axiomas de Blum para medidas de complexidade computacional. Tempo e espaço determinístico e não-determinístico. Problemas P, NP, NP-difíceis e NP-completos. Teorema de Cook. Hierarquia polinomial. Resultados elementares de complexidade computacional.
Metodologia de avaliação
Exame/testes 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 aplicável.
Componente de Programação e Computação
Não aplicável.
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.