COM167 - Teoria da Computação
Conteúdo das Aulas:
- Aula 15 (24 de junho)
- Definição: Problemas NP-Difíceis e Problemas Intratáveis
- Definição: Complexidade de Espaço
- Aula 14 (18 de junho)
- Definição: Classe NP-Completo
- Teorema 7.28: Se B é NP-Completo e B Î P, então P = NP
- Teorema 7.29: Se B é NP-Completo e B ≤p C, então C é NP-Completo
- Teorema 7.30 (Cook-Levin): SAT é NP-Completo
- Teorema 7.31: 3SAT é NP-Completo
- Corolário: CLIQUE é NP-Completo
- Teorema 7.34: VERTEX-COVER é NP-Completo
- Teorema 7.35: HAM-PATH é NP-Completo
- Teorema 7.36: SUBSET-SUM é NP-Completo
- Aula 13 (17 de junho)
- Definição: Verificador polinomial de uma linguagem
- Definição: Classe NP
- Teorema 7.12: Uma linguagem é NP se e só se é decidida por MT não-det polinomial
- Definição: Classe de Complexidade de Tempo NTIME(t(n))
- Exemplos: CLIQUE e SUBSET-SUM são NP
- Definição: Redução Polinomial: A ≤p B
- Teorema 7.22 (Cook-Levin): SAT Î P Û P = NP
- Teorema 7.25: Se A ≤p B e B Î P, então A Î P
- Teorema 7.26: 3SAT ≤p CLIQUE
- Aula 12 (08 de junho)
- Teorema 5.24: EQTM e seu complemento não são recursivamente enumeráveis
- Definição: Tempo de Processamento de MT det e não-det
- Notação O e o
- Definição: Classe de Complexidade de Tempo TIME(t(n))
- Teorema 7.8: Relação entre Tempos de MT com 1 fita e MT com K fitas
- Teorema 7.10: Relação entre Tempos de MT com 1 fita e MT não-det com 1 fita
- Definição: Classe P
- Aula 11 (07 de junho)
- Teorema 5.4: EQTM é indecidível
- Definição: Post Correspondence Problem - PCP
- Teorema 6.11: PCP é indecidível
- Definição: Função Computável: f: Σ*®Σ*
- Definição: Redutibilidade entre Linguagens: A ≤m B
- Teorema 5.16: Se A ≤m B e B é decidível, então A é decidível
- Corolário: Se A ≤m B e A é indecidível, então B é indecidível
- Teorema 5.22: Se A ≤m B e B é recursivamente enumerável, então A é recursivamente enumerável
- Corolário: Se A ≤m B e A não é recursivamente enumerável, então B não é recursivamente enumerável
- 04 de junho
- Aula 10 (03 de junho)
- 27 e 28 de maio
- Aulas 08 e 09 (21 de maio)
- Teorema 4.9: ATM é indecidível
- Teorema 4.15: Existem infinitas linguagens não recursivamente enumeráveis
- Teorema 4.16: Uma linguagem é recursiva se e só se ela e seu complemento são recursivamente enumeráveis
- Corolário 4.17: O complemento de ATM não é recursivamente enumerável
- Teorema 5.1: O Problema da Parada HALT é indecidível
- Teorema 5.2: ETM é indecidível
- Teorema 5.3: RegTM é indecidível
- Aula 07 (14 de maio)
- Problema da Parada e a Linguagem ATM
- Lema: ATM é recursivamente enumerável
- Método da Diagonalização
- Função de Correspondência entre Conjuntos
- Conjuntos Enumeráveis (ou Contáveis)
- Lema: O Conjunto dos Números Racionais é Enumerável
- Teorema 4.14: O Conjunto dos Números Reais não é Enumerável
- Aula 06 (13 de maio)
- Linguagens Decidíveis
- Teorema 4.5: EQDFA é decidível
- Teorema 4.6: ACFG é decidível
- Teorema 4.7: ECFG é decidível
- Teorema 4.8: Linguagens Livre de Contexto são decidíveis
- EQCFG não é decidível
- Aula 05 (07 de maio)
- Decidibilidade
- Linguagens Recursivas (Decidíveis)
- Teorema 4.1: ADFA é decidível
- Teorema 4.2: ANFA é decidível
- Teorema 4.3: AREG é decidível
- Teorema 4.4: EDFA é decidível
- Aula 04 (30 de abril)
- Máquinas de Turing Não Determinísticas
- Equivalência entre M.T. e M.T. Não Determinísticas
- Linguagens Recursivas e Recursivamente Enumeráveis
- Diferença entre Reconhecer e Decidir Linguagens
- Enumeradores
- Indecidibilidade do Problema 10 de Hilbert
- Aula 03 (29 de abril)
- Exemplos de Funções μ-Recursivas
- Números de Gödel e Função de Ackermann
- Máquina de Turing com K fitas
- Complexidade e Equivalência entre M.T. com K fitas e M.T. padrão
- Aula 02 (23 de abril)
- Funções μ-Recursivas
- Tese de Church-Turing e Problema 10 de Hilbert
- Codificação de Máquinas de Turing como Algoritmos
- Aula 01 (22 de abril)
- Revisão
- Funções Primitivo-Recursivas
- Operador-μ e Minimização Limitada