Complexidade computacional:
Shannon e Turing
01 de Junho de 2012
José Roberto C. Piqueira
[email protected]
Claude E. Shannon
30/04/1916 – 24/02/2001
Doutorado (MIT-1937): Circuitos
Elétricos-Álgebra de Boole
Criptografia e quebra de códigos
(Segunda Guerra)
Teoria da Informação (1948)
Alan Turing
23/06/1912 – 27/06/1954
Formalização do conceito de algoritmo
Quebra do código dos alemães durante a
segunda guerra
Depois da guerra: Manchester University
1952: prisão por homossexualismo,
castração química, suicídio (1954)
Medida da Informação
(Shannon)
• Abordagem probabilística
•
Fonte ....Canal...Receptor
• Informação individual: log2(1/p)
• Entropia informacional: esperança
matemática da informação individual
• Capacidade do Canal
• Exemplo (lousa)
Entropia máxima
Entropia Algorítmica
O foco não é a fonte e a distribuição de
probabilidade de todas as sequencias
possíveis
Interessa uma sequencia particular “x”
Ideias básicas
• Complexidade K(x): menor comprimento do
programa capaz de gerar a sequencia x;
• Conjunto finito de instruções com
comprimento |q(x)| bits;
• O programa pode ser implementado por uma
máquina de Turing.
• min |q(x)| = K(x)
Máquina de Turing
Máquina de Turing
• Fita com uma cabeça de leitura e uma
de escrita
• Fita: comprimento infinito, sucessão de
células de memória (0 ou 1)
• Células não escritas ou tornadas
brancas= 0
• A fita pode ser movida para esquerda
ou para a direita, uma célula por vez
Controle da máquina de
Turing
• Operações da cabeça e da fita são definidas por uma
tabela de instruções {I1, I2,.....In}, chamada tabela de
ação
• Exemplo:
s1;0....1;L;S3
»
s2;1....0;R;S2
Tabela de Ação (Exemplo)
• Criar a sequencia 11011 a partir da
sequencia vazia
Programa (Exemplo)
Soma: sistema unário de
numeração
3.....111
7.....1111111
3+7....1111111111
Delimitador.....0
3 + 7........11101111111.......sequencia inicial
Soma: tabela de ação
Soma: programa
Programas e simuladores
• www.ams.org
• http://ironphoenix.org/tril/tm
Multiplicação e divisão
Qualquer multiplicação de números de
comprimento finito pode ser realizada
O programa de divisão permite mudanças
de base
Parece que qualquer número é
computável em uma máquina de Turing
(falso)
Comprimento
computacional
Número de estados definidos pela tabela
de ação: medida da complexidade do
algoritmo
Noção de comprimento computacional:
Dados dois números de comprimento n,
quantas transições são necessárias
para multiplicá-los? (Próxima figura)
Tese de Church-Turing
Uma máquina de Turing é capaz de
resolver todos os problemas
solucionáveis por um algoritmo ou
um método de computação efetivo
(volta ao slide 7)