23 de Fevereiro Considerações sobre a disciplina, incluindo programa,
bibliografia, objectivoe e método de avaliação
28 de Fevereiro Algoritmos e sua análise. Definições indutivas, recursividade e
recorrências. Ordens de grandeza O(), Omega() e
Theta(). Exercícios.
2 de Março Resolução de exercícios sobre ordens de grandeza. O algoritmo "mergesort": determinação de uma recorrência que
define um majorante do número de comparações efectuadas; solução
dessa recorrência pelo método "tabelar, suspeitar, demonstrar".
7 de Março Utilização dos seguintes métodos na solução das recorrências:
"tabelar, suspeitar, demonstrar", diferenças finitas constantes,
mudança de variável.
9 de Março Método da equação característica: equação geral
homogénea e equação geral não homogénea. Aplicações e exercícios.
14 de Março Minorantes de complexidade baseados na Teoria da Informação.
Princípio da informação necessária. Aplicação à determinação de
minorantes relativos ao problema da pesquisa e ao problema da
ordenação.
16 de Março Funções e modelos de computação. Modelos e linguagens que definem
funções totais. Caracterização indutiva das funções definidas por
"recursão primitiva" (classe PR). Exercícios.
21 de Março Caracterização das funções da classe PR através de uma linguagem de
registos (FOR). Terminação dos programas em FOR. Exercícios.
23 de Março Prova contendo exercícios variados.
28 de Março Mais exemplos de caracterização de funções da classe PR pelo
método indutivo e por programas FOR. Incompletude de qualquer
modelo de funções computáveis totais: demonstração por
diagonalização. Função de Ackermann. Problemas decidíveis e indecidíveis. A indecidibilidade do
problema da (auto-)paragem (PAP). Redução entre problemas de
decisão. Exemplo simples: PAP <= PGP. Tese de Church-Turing.
30 de Março Caracterização das funções recursivas parciais por uma linguagem
de registos (WHILE) e por um método indutivo que inclui a minimização. Problemas decidíveis, semi-decidíveis e complementares de
semi-decidíveis. Linguagem associada a um problema de decisão;
linguagens recursivas, recursivamente enumeráveis e complementares
de recursivamente enumeráveis.
04 de Abril A noção de redução entre 2 problemas e entre 2
linguagens. Propriedades.
06 de Abril A indecidibilidade do problema PAP (problema da auto-paragem).
11 de Abril Exercícios: reduções PAP <= PGP e a indecidibilidade do problema
PGP (problema geral da paragem). Exercícios de reduções e
deindecidibilidade.
13 de Abril Noção de problema completo numa classe. PGP é completo na classe das
linguagens recursivamente enumeráveis.
18 de Abril Demonstrações de alguns resultados: Teorema do contra-domínio,
Teorema de Rice. Resolução de exercícios sobre classes de
decidibilidade.
Indecidibilidade de outros problemas: equações
diofantinas, equivalência de CFGs,...
20 de Abril <Não houve aulas no DCC>.
27 de Abril Exercícios de "computabilidade para complexidade"
02 de Maio Introdução à teoria dos problemas completos em NP. Eficiência dos
problemas de decisão. Alguns exemplos de problemas de decisão:
SAT, 3SAT, 2SAT, Clique, VC. Redução polinomial entre problmas de
decisão.
04 de Maio Exemplos de reduções polinomiais entre problemas de decisão: 3SAT a
4SAT, 3SAT a STA, SAT a 3SAT, 3SAT a VC, VC a Clique.
09 de Maio Caracterizações da classe NP. As classes co-NP, NPC (problemas
completos em NP), co-NPC.
11 de Maio Teorema de Cook; ideia básica da demonstração. Método de se
mostrar que um probleme é completo na classe NP.
16 de Maio Representação das fórmulas proposicionais em CNF e em DNF.
Análise da classe de complexidade de alguns problemas de decisão:
(ELS) "expressão lógica satisfazível", (ELF) "expressão lógica
falsificável", (TAUT) tautologia, "2 Cliques".
18 de Maio A hierarquia polinomial. Definição baseada em quantificadores
alternados. O problema "expressão mínima equivalente" e a sua
posição na hierarquia polinomial.
23 de Maio Definição da hierarquia polinomial baseada em máquinas de
Turing com oráculos. Resolução de exercícios. Introdução às classes
de complexidades aleatorizadas; primalidade.
23 de Maio Exercícios sobre a 3a parte da matéria (teoria dos problemas
completos em NP).