Disciplina Curricular
Complexidade Computacional CC
Mestrado Bolonha em Ciência de Dados - 1_MCD 2018/19
Contextos
Grupo: 1_MCD 2018/19 > 2º Ciclo > Parte Escolar > Opcionais > 733 - MCD - Grupo 4
Período:
Grupo: 1_MCD 2018/19 > 2º Ciclo > Parte Escolar > Opcionais > 730 - MCD - Grupo 1
Período:
Peso
6.0 (para cálculo da média)
Objectivos
O curso oferecerá uma introdução intensa ao campo da Complexidade Computacional. O curso será organizado historicamente, abrangendo desde o início da área, até o início dos anos 2000.
Programa
Parte 1 - Classes de Complexidade e Diagonalização * A invenção do computador: máquinas de Turing e o problema da paragem * Medidas de complexidade e Máquinas de Acesso Aleatório * Teoremas de hierarquia * A carta perdida de Gödel, reduções, teorema de Cook-Levin, P vs NP * Complexidade de espaço: L vs NL vs P vs PSPACE * A barreira da relativização Parte 2 - A abordagem combinatória * Modelos combinatórios: Circuitos Booleanos, limites inferiores, redução de profundidade * Computação randomizada: ZPP, RP, BPP, desrandomização, dureza vs aleatoriedade * Algoritmos e limites inferiores para circuitos de profundidade constante * A fronteira nos limites inferiores de circuitos: Circuitos de profundidade constante com portas modulares * Complexidade da comunicação e o teorema de Karchmer-Wigderson * Alguns limites inferiores em complexidade da comunicação * A barreira das provas naturais Parte 3 - Outros tópicos (apresentações dos alunos)
Métodos de ensino e avaliação
A avaliação é feita por testes ou exame, com a possibilidade de fazer uma apresentação sobre um tema de Complexidade Computacional, à escolha do aluno.