Seminários

< Computabilidade

Sábado, 10 de dezembro de 2016, de 10h às 12h e 13h às 15h
Laboratório de Introdução a Informática (LII), Bloco E. (Engenharia)

Duplas

Os números ao lado dos temas denotam as referências sugeridas ao final da página.

• João Miguel e Alan – Complexidade computacional [5,6]
• Carlos e Diogo – Algoritmos de Markov [1]
• Wesley e Juliana – LP [1]
• Wagner e William – Conjuntos Recursivos [3], Ábaco [4] ou Máquinas com registro [2]
• Maurício e Rodrigo – Lógica combinatória [1]
• Vitor e Ronald – Lambda Cálculo [1]

Estrutura das apresentações

Modelos de computação

1. Descrição do modelo
2. Mapeamento do modelo escolhido para um outro modelo Turing-completo

Complexidade computacional

• Speed up
• Hierarquia de classes de problemas
• K-completude, onde K é uma classe de complexidade
• NP = PSPACE

Avaliação das apresentações

• Conteúdo - 40%
• Domínio do tema - 40%
• Clareza - 15%
• Qualidade da apresentação - 5%

Referências Bibliográficas Sugeridas

1. Theory of computation – Walter S. Brainerd & Lawrence H. Landweber
2. Computability Theory: An Introduction to Recursion Theory – Herbert B. Enderton
3. Computability: Computable Functions Logic and the Foundations of Math – Richard L. Epstein e Walter Carnielli
4. Computability and Logic – George S. Boolos, John P. Burgess e Richard C. Jeffrey
5. Introduction to Automata Theory, Languages, and Computation – John E. Hopcroft, Rajeev Motwani e Jefrey D. Ullman
6. Introduction to theory of computation – Michael Sipser