Sumários
07-02-2017
Apresentação do programa e objectivos do curso, bibliografia básica e regime de avaliação.
Linguagens Regulares.
Autómatos finitos determinísticos (DFA) e não determinísticos (NFA).
10-02-2017
Equivalência dos modelos determinísticos (DFA) e não determinísticos (NFA) de Automatos Finitos.
Lema da repetição para linguagens regulares.
14-02-2017
Linguagens Independentes do Contexto
Propriedades da CFL
Noção de derivação de de árvore de derivação
Ambiguidade de Gramáticas e de Linguagens Independentes do Contexto
17-02-2017
Forma Normal de Chomsky (CNF) para CFG
Autómatos de Pilha (PDA) determinísticos e não determinísticos
21-02-2017
"Lema da Repetição" para CFL
"Lema de Ogden"
24-02-2017
A tese de Church- Turing
Definição formal de Máquina de Turing (TM)
Linguagens reconhecíveis e decidíveis.
07-03-2017
Equivalência os diversos modelos de TM: fitas duplamente infinitas, com diversas fitas e não determinísticas
Existência de linguagens não-computáveis. O argumento diagonal de Cantor
10-03-2017
Noção de Enumerador
Equivalência da noção de linguagem recursivamente enumerável e de linguagem reconhecível
As linguagens \(A_{DFA}\), \(A_{NFA}\), \(E_{DFA}\), \(EQ_{DFA}\) e \(E_{CFG}\) são linguagens decidíveis
Noção de linguagen co-reconhecível
Máquina de Turing Universal
\(A_{TM}\) é reconhecível mas não é decidível.
14-03-2017
O "Halting problem": \(HALT_{TM}\) é não decidível.
\(E_{TM}\) e \(REGULAR_{TM}\) são linguagens não decidíveis
O Teorema de Rice e as suas consequencias.
17-03-2017
\(EQ_{TM}\) é não indecidível
Máquinas de Turing com fita linearmente limitada ($LBT$}
\(A_{LBT}\) é decidível
Noção de história de computação positiva
\(E_{LBT}\) é não decidível
\(ALL_{CFG}\) é não decidível
21-03-2017
O problema da Correspondência de Post (\(PCP\)) e a sua indecidibilidade
Reduções de problemas e respectivas implicações sobre decibilidade
24-03-2017
Aplicação do \(PCP\): a linguagem das CFG's ambíguas (\(AMBIG_{CFG}\)) é não decidível.
\(EQ_{TM}\) é ireconhecível e co-irreconhecível
O Teorema da recursão
A linguagem das \TM minimais (\(MIN_{TM}\)) é não reconhecível.
28-03-2017
Breve introdução à complexidade Kolmogorov
Noção de $c$-compressibilidade e existência de $c$-incompressíveis
O número \(\Omega\) de Chaitin
Provas de não regularidade usando complexidade Kolmogorov
31-03-2017
Complexidade computacional
Notação \(\mathcal{O}\), \(o\) e \(\Theta\) de comparação de comprtamentode funções
Noção de \(TIME(t(n))\) e de \(NTIME(t(n))\)
Comparação do tempo de execução de uma TM com uma fita e de várias fitas
Comparação do tempo de execução de uma TM determinística e de uma TM não determinística
07-04-2017
Definição da classe de complexidade \(NP\)
Equivalência da existência de um verificador determinístico polinomial e de um decisor não-determinístico polinomial.
\(HAMPATH\in NP\)
18-04-2017
\(SUBSET-SUM\in NP\)
\(CLIQUE\in NP\)
Noção de redução em tempo polinomial de uma linguagem a outra.
\(3SAT\leq_P CLIQUE\)
Noção de linguagem $NP$-completa
21-04-2017
\(SAT\) é $NP$-completa (Teorema de Cook-Levin)
\(3SAT\) é $NP$-completa
28-04-2017
\(VERTEXCOVER\) é NP-completo (\(3SAT \leq_P VERTEXCOVER\))
\(HAMPATH\) é NP-completo (\(3SAT\leq_P HAMPATH\))
\(UHAMPATH\) é NP-completo (\(HAMPATH\leq_P UMPATH\))
02-05-2017
- \(3DM\) é NP-completo (\(3SAT\leq_P3DM\))
05-05-2017
\(\neq SAT\) é NP-completo (\(3SAT\leq_p\neq SAT\))
\(PAR\) é NP-completo (\(3DM\leq_pPAR\))
16-05-2017
Noção de \(SPACE(n)\) e \(NSPACE(n)\)
\(SAT\in\) PSPACE
\(\overline{ALL_{NFA}}\in\) NPSPACE
O Teorema de Savitch: PSPACE\(=\)NPSPACE
Noção de linguagem PSPACE-completa
\(TQBF\) é PSPACE-Completo
19-05-2017
Formula-Game\(=\)TQBF (e portanto é PSPACE-completo)
GG é PSPACE-completo (pois GG\(\leq_P\)Formula-Game)
Nocão de complexidade por espaço sub linear. As classes L e NL
\(\{0^k1^k\mid k\in\mathbb{N}\}\in\)L
PATH\(\in\)NL
23-05-2017
Noção de Transdutor em espaço logarítmico e de redução em espaço logarítimico
Noção de linguagens NL-completas
PATH é NL-completa
NL\(\subseteq P\)