Rogério Reis


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


Sumários

7-3-2022 (Aula 1)
  • Apresentação da unidade curricular e modelo de avaliação.
  • Breves notas sobre computabilidade
  • A Hierarquia de Chomsky
  • Determinismo vs não-determinismo
  • Máquinas de Turing e a sua equivalência à luz da Computabilidade
    • Com uma só fita
    • Com várias fitas
    • Determinísticas
    • Não-determinísticas
  • - Linguagens reconhecíveis - reconhecedores & enumeradores
  • - Linguagens decidíveis - decisores
  • - Noção de redução entre linguagens
  • - $A_{TM}$ como problema indecidível (mas obviamente reconhecível)
14-3-2022 (Aula 2)
  • Teorema de Rice
  • Noção de História de Computação Positiva
  • Loção de Linear Bounded Automata (LBA)
  • O Post Correspondence Problem (PCP)
  • Noção de complexidade computacional (no pior caso)
  • Notação de Landau
  • Conversão de TM de várias fitas em TM de uma só fita e sua consequência no tempo de execução
  • A classe de complexidade P
  • Conversão de TM não determinística em TM determinística
Um emulador muito simples de uma Máquina de Turing
Download
0
21-3-2022 (Aula 3)
  • A classe de complexidade NP
  • Linguagens NP-completos
  • Reduções polinomiais de linguagens ($A\leq_PB$)
  • O Teorema de Cook-Levin (SAT é NP-completo)
  • 3SAT é NP-completo (SAT$\leq_P$3SAT)
  • Clique é NP-completo (3SAT $\leq_P$ Clique)
  • VertexCover é NP-completo (3SAT $\leq_P$ VertexCover)
  • HamPath e UHamPath são NP-completos (3SAT$\leq_P$HamPath e HamPath$\leq_P$UHamPath)
  • Knapsack é NP-completo (3SAT$\leq_P$Knapsack)
28-3-2022 (Aula 4)
  • Complexidade por espaço SPACE e NSPACE
  • O teorema de Savitch (NSPACE$(f(n))\subseteq$SPACE$(f(n)^2)$)
  • PSPACE e NPSPACE
  • Linguagens PSPACE-completas
  • TQBF é PSPACE-completa
4–4-2022 (Aula 5)
  • GG é PSPACE-completa
  • Complexidade sub-linear
  • As classes L e NL
  • PATH é NL-completa
  • coNL=NL
9–5-2022 (Aula 6)
  • Intratabilidade
  • Teorema da hierarquia de espaço
  • Teorema da hierarquia de tempo
16–5-2022 (Aula 7)
  • Hierarquia Polinomial: $\Sigma^p_i$
  • Complexidade de Circuitos
  • Nova demonstração do Teorema de Cook-Levin
  • A classe $\mathbf{P}_{/poly}$ e a possível contribuição da complexidade de circuitos para o $\mathbf{P}\neq \mathbf{NP}$
23–5-2022 (Aula 8)
  • Computação probabilística
  • Noção de $\mathbf{BPTime}[t]$
  • A classe $\mathbf{BPP}$
    • Teste probabilístico de primalidade
    • Teste probabilístico de identidade de BDD
30–5-2022 (Aula 9)
  • Mais algoritmos probabilísticos
    • valor mediano de um conjunto
    • identificação de polinómios dados por circuitos algébricos
    • correspondências perfeitas em grafos bipartidos
  • Provas interactivas determinísticas
  • A classe $\mathsf{dIP}$
  • Provas interactivas não determinísticas
  • A classe $\mathsf{IP}$
    • GNI$\in \mathsf{IP}$
  • Provas $\mathsf{AM}$
  • A classe $\mathsf{AM}$
    • GNI$\in \mathsf{AM}$
6–6-2022 (Aula 10)
  • Algoritmos aproximativos
  • Complexidade do caso médio (segundo Levin)
    • distP e distNP
    • noção de distNP-completo
  • Desaleatorização

Última modificação: 20/09/2022