Rogério Reis

Err and err and err again, but less and less and less.

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: 27/05/2025