Sumários
15-02-2018 (Aula 1)
- A apresentação do programa e objectivos da unidade curricular, assim como condições de obtenção de frequência e formas de avaliação.
- Linguagens regulares. Autómatos finitos determinísticos e não determinísticos.
20-02-2018 (Aula 2)
- Transformação de um NFA num DFA.
- O Lema da Repetição para linguagens regulares.
27-02-2018 (Aula 3)
- 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
01-03-2018 (Aula 4)
- Forma Normal de Chomsky para CFG
- Autómatos de Pilha (PDA) determinísticos e não-deterministicos
08-03-2018 (Aula 5)
- Máquinas de Turing
- Tese de Church-Turing
- Reconhecedores e decisores
13-03-2018 (Aula 6)
- Máquinas de Turing não deterministicas
- Equivalência de modelos de máquinas de Turing
- Diagonalização de Cantor
- Existência de linguagens não decidíveis
- Enumeradores
15-03-2018 (Aula 7)
- 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 linguagem co-reconhecível
- $A_{TM}$ é reconhecível mas não é decidível.
20-03-2018 (Aula 8)
- O "Halting Problem": $HALT_{TM}$ não é decidível
- $E_{TM}$ e $REGULAR_{TM}$ são não decidíveis.
- O teorema de Rice e as suas consequências.
22-03-2018 (Aula 9)
- $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
03-04-2018 (Aula 10)
- O problema da Correspondência de Post ($PCP$) e a sua indecidibilidade
- Reduções de problemas e respectivas implicações sobre decibilidade
05-04-2018 (Aula 11)
- \(AMBIG_{CFG}\) é não decidível
- \(EQ_{TM}\) é não reconhecível e não co-reconhecível
- O Teorema da Recursão de Kleene
- Teorema o ponto fixo
- $MIN_{TM}$ não é reconhecível
10-04-2018 (Aula 12)
- Breve introdução à complexidade Kolmogorov
- Noção de $c$-compressibilidade e existência de $c$-incompressíveis
- O número $\Omega$ de Chaitin
12-04-2018 (Aulas 13)
- Complexidade computacional
- Notação $\mathcal{O}$ e $o$ de comparação de comportamento de funções
- Noção de $TIME(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
17-04-2018 (Aulas 14)
- 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$
19-04-2018 (Aula 15)
- $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
24-04-2018 (Aula 16)
- $SAT$ é $NP$-completa (Teorema de Cook-Levin)
- $3SAT$ é $NP$-completa
3-05-2018 (Aula 17)
- $\mathsf{SubSetSum}$ é $NP$-completo
- $\neq \mathsf{SAT}$ é $NP$-completo ($3\mathsf{SAT}\leq_P\neq \mathsf{SAT}$)
- $\mathsf{MaxCut}$ é $NP$-completo ($\neq\mathsf{SAT}\leq_P\mathsf{MaxCut}$)
15-05-2018 (Aula 18)
- Noção de complexidade por espaço.
- $\mathsf{PSPACE}$ e $\mathsf{NPSPACE}$
- O Teorema de Savitch.
17-05-2018 (Aulas 19)
- Noção de linguagem $\mathsf{PSPACE}$-completa.
- $\mathsf{TQBF}$ é $\mathsf{PSPACE}$-completa.
22-05-2018 (Aula 20)
- Noção de complexidade por espaço sub linear. As classes $\mathsf{L}$ e $\mathsf{NL}$.
- $\{0^k1^k\mid k\in\mathbb{N}\}\in \mathsf{L}$
- $\mathsf{PATH}\in \mathsf{NL}$
24-05-2018 (Aulas 21)
- Noção de Transdutor em espaço logarítmico e de redução em espaço logarítimico.
- Noção de linguagens $\mathsf{NL}$-completas
- $\mathsf{PATH}$ é $\mathsf{NL}$-completa
- $\mathsf{NL}\subseteq \mathsf{P}$
Última modificação: 20/05/2025