ContextoHistorico

Prévia do material em texto

Teoria da Computação 
Histórico, 
Modelos Computacionais 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
 
 
 
DCC-UFLA, Lavras 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Agenda 
 Histórico 
 Modelos Computacionais 
 Ferramental matemático (Material separado) 
2 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Breve Histórico 
Muitos personagens ilustres! 
3 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Breve Histórico (2) 
4 
 Em 1900, David Hilbert 
previu corretamente os 23 
problemas que iriam 
concentrar a maior parte 
dos trabalhos de 
matemáticos no restante do 
século 
 Dois problemas tiveram 
particular importância para 
Ciências da Computação… 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Breve Histórico (3) 
 Problema 2: É possível decidir o resultado 
(verdadeiro ou falso) de qualquer proposição 
lógica envolvendo números naturais 
(Entscheidungsproblem)? 
 Problema 10: Existe um processo, que pode ser 
determinado por um número finito de operações, 
que encontre a raiz integral de um polinômio? 
 Ambos podem ser interpretados como: Existe um 
algoritmo para resolver este problema? 
5 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Breve Histórico (4) 
 Em 1930, Kurt Gödel demonstrou que 
existe um algoritmo para provar a 
verdade de qualquer proposição em 
lógica de primeira ordem. Entretanto, 
também foi demosntrado que lógica de 
primeira ordem não consegue capturar 
o princípio de indução necessário para 
caracterizar números naturais 
 No ano seguinte, Gödel publicou o 
celébre “incompleteness theorem“: em 
qualquer linguagem expressiva o 
suficiente para expressar as 
propriedades dos números naturais, 
existem afirmações verdadeiras que são 
indecidíveis, isto é, não podem ser 
decididas por qualquer algoritmo 
6 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Breve Histórico (5) 
 Os resultados de Ködel 
motivaram Alan Turing 
(também Alonzo Church) a 
tentar caracterizar 
precisamente quais 
funções podem ser 
representadas por um 
algoritmo, isto é, quais 
funções podem ser 
computadas 
7 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Breve Histórico (6) 
 Uma Máquina de Turing é capaz de computar 
qualquer função computável. Entretanto, existem 
algumas funções que Máquinas de Turing não 
podem computar 
 Ex.: Nenhuma máquina pode dizer de maneira 
geral se um programa irá retornar uma resposta 
ou ficar “rodando” para sempre 
• Paradoxo de Russel: Em uma cidade, um barbeiro é 
responsável por fazer (apenas) a barba de todos 
aqueles que não fazem a própria barba. Quem faz a 
barba deste barbeiro? 
8 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Breve Histórico (7) 
 Na metade da década de 60, vários 
pesquisadores notaram que certos problemas, 
apesar de serem decidíveis (computáveis), não 
admitiam, aparentemente, uma solução eficiente 
 Soluções para estes problemas restringiam-se a 
buscas exaustivas no espaço de alternativas (força 
bruta) 
 Tempo de execução crescia exponencialmente 
com o tamanho da entrada 
• Entrada de 10 elementos -> 0.5 s, 20 elementos -> 
50m, 50 elementos -> 2x108 séculos! 
9 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Breve Histórico (8) 
 Após estudos subsequentes, duas classes de problemas 
foram definidas 
 Classe P: problemas de decisão que podem ser 
resolvidos em tempo polinomial por um computador 
convencional 
 Classe NP: problemas de decisão para os quais a 
validade de uma solução pode ser verificada em tempo 
polinomial por um computador convencional 
• Problemas intratáveis podem ser resolvidos em tempo 
exponencial apenas, mas uma possível solução pode ser 
verificada em tempo polinomial 
• Note que 𝑃 ⊆ 𝑁𝑃 
10 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Breve Histórico (9) 
 Em 1971, Stephen Cook apresentou 
a classe de problemas NP-Completo 
com a seguinte propriedade: 
• Se um problema NP-Completo é 
reduzível a um problema A, então A é 
provavelmente intratável . Por outro 
lado, se existe uma solução 
polinomial para um problema NP-
Completo, então existe uma solução 
polinomial para todos problemas em 
NP, mesmo aqueles considerados 
intratáveis anteriormente 
 Em 1972, Richard Karp mostrou que 
vários problemas conhecidos eram 
NP-Completos 
11 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Breve Histórico (10) 
 P = NP? 
 Questão fundamental em Ciências da 
Computação e em Matemática em geral 
 Um dos 7 Millennium Prize Problems 
listados pelo Clay Mathematics Institute 
 Um milhão de dólares pela resposta! 
12 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Modelos Computacionais 
 Permitem o estudo do poder de expressão e 
computação baseando-se em conjuntos básicos de 
operações, operandos, e recursos 
 Evita ater-se a aspectos de um hardware específico 
 Possibilita o desenvolvimento de uma teoria 
matemática 
 Modelo de custos para a análise de algoritmos 
 Nenhum modelo computacional é adequado para 
todas situações 
 
13 
A key task in computer science is 
sistematic abstraction (H. Wedekind) 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exemplo: 
Modelo Computacional RAM 
 Instruções executadas sequencialmente 
 Instruções simples encontradas na maioria das 
arquiteturas (adição, subtração, divisão resto, 
load, store, chamadas de subrotinas, 
operações bitwise) 
 Cada instrução é executada em tempo 
constante 
 Paralelismo, hierarquia de mémoria (caches e 
memória virtual) não são considerados 
14