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: 15/03/2024