Área de Concentração: 45134
Concentration area: 45134
Criação: 25/06/2021
Creation: 25/06/2021
Ativação: 25/06/2021
Activation: 25/06/2021
Nr. de Créditos: 8
Credits: 8
Carga Horária:
Workload:
Teórica (por semana) |
Theory (weekly) |
Prática (por semana) |
Practice (weekly) |
Estudos (por semana) |
Study (weekly) |
Duração | Duration | Total | Total |
---|---|---|---|---|---|---|---|---|---|
4 | 2 | 4 | 12 semanas | 12 weeks | 120 horas | 120 hours |
Docente Responsável:
Professor:
Marcelo Finger
Objetivos:
Estudar os conceitos fundamentais de computação modelado do ponto de vista da Lógica Formal. Estudar as noções de funções compatíveis, problemas tratáveis e intratáveis, do ponto de vista da Lógica Formal.
Justificativa:
Há muitos problemas computacionais indecidíveis, e mesmo entre os decidíveis há uma larga classe de problemas intratáveis. Estes problemas se originaram no estudo de diversos fragmentos da lógica clássica: as lógicas de primeira e segunda ordem, e a lógica proposicional. Na formação básica de um aluno de pós-graduação, identificar e demonstrar a (in)computabilidade e (in)tratabilidade de um problema é uma habilidade fundamental, de grande interesse tanto teórico quanto prático.
Conteúdo:
1. Computabilidade: algoritmos, máquinas de Turing, funções recursivas primitivas e parciais. 2. Lógica: Proposicional, Primeira e Segunda Ordem. Satisfatibilidade, decidibilidade. Aritmética de Primeira Ordem. Funções Representáveis na Aritmética. Funções aritméticas recursivas e decidibilidade. 3. Teoremas de Incompletude Gödel. Incompletude de Lógica de Segunda Ordem. 4. Simulação de Máquinas de Turing em Lógica de Primeira Ordem. Indecidibilidade da Lógica de Primeira Ordem. 5. Tratabilidade: Máquinas de Turing não-determinística. Reduções polinomiais e a classe NP. Problemas NP-completos. Teorema de Cook-Levin. O fragmento existencial de Segunda Ordem e o Teorema de Fagin. 6. Lógica Booleana Quantificada e a caracterização lógica da classe PSPAÇO. 7. Hierarquias de complexidade: a hierarquia polinomial e sua caracterização em termos de fórmulas de Lógica Booleana Quantificada. Noções de classes Exponenciais. Noções de complexidade da classe não-elementar.
Forma de Avaliação:
Bibliografia:
[1] Walter Carnielli and Richard Epstein, Computabilidade, Funções Computáveis, Lógica e seus Fundamentos, Editora da UNESP. 2005. [2] M.R. Garey and D.S. Johnson, Computers and Intractability: a Guide to the Theory of NP-completeness, W.H. Freeman and Company, New York, 1979, 338p. [3] George S. Boolos and Richard C. Jeffrey, Computability and Logic, third edition ed., Cambridge University Press, 1989. [4] Christos H. Papadimitriou, Computational Complexity, Addison Wesley, 1994. [5] Stephen Cole Kleene, Introduction to metamathematics, Bibl. Matematica, North-Holland, Amsterdam, 1952.
Tipo de oferecimento da disciplina:
Presencial
Class type:
Presencial