Complexidade computacional: Shannon e Turing

01 de Junho de 2012 José Roberto C. Piqueira

jose.piqueira@poli.usp.br

Spi

na

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)

Spi

na

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)

Spi

na

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)

Spi

na

Entropia máxima

Spi

na

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”

Spi

na

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)

Spi

na

Máquina de Turing

Spi

na

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

Spi

na

• 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

Controle da máquina de Turing

Spi

na

Tabela de Ação (Exemplo)

• Criar a sequencia 11011 a partir da sequencia vazia

Spi

na

Programa (Exemplo)

Spi

na

3.....111 7.....1111111 3+7....1111111111

Delimitador.....0

3 + 7........11101111111.......sequencia inicial

Soma: sistema unário de numeração

Spi

na

Soma: tabela de ação

Spi

na

Soma: programa

Spi

na

Programas e simuladores• www.ams.org

• http://ironphoenix.org/tril/tm

Spi

na

Multiplicação e divisão Qualquer multiplicação de números de

comprimento finito pode ser realizadaO programa de divisão permite mudanças

de baseParece que qualquer número é

computável em uma máquina de Turing (falso)

Spi

na

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)

Spi

na

Spi

na

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)