Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Aplicacoes da Complexidade de Kolmogorov

Carlos A. P. Campani

28 de abril de 2006

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Sumario

1 Introducao

2 Complexidade de Kolmogorov

3 Aleatoriedade

4 Sequencias aleatorias de Martin-Lof

5 Distancia de informacao

6 Grafos k-aleatorios

7 Conclusoes

8 Para saber mais

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Sumario

1 Introducao

2 Complexidade de Kolmogorov

3 Aleatoriedade

4 Sequencias aleatorias de Martin-Lof

5 Distancia de informacao

6 Grafos k-aleatorios

7 Conclusoes

8 Para saber mais

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Objetivos da apresentacao

Objetivo geral

Apresentar a complexidade de Kolmogorov e suas principaispropriedades.

Objetivos especıficos

Apresentar tres aplicacoes da complexidade de Kolmogorov:

Distancia de informacao como metrica para a qualidade deimagem;

Distancia de informacao aplicada na classificacao(clusterizacao) de literatura lusofona segundo o estilo eperıodo literario;

Grafos k-aleatorios aplicados na determinacao depropriedades de redes de computadores.

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Objetivos da apresentacao

Objetivo geral

Apresentar a complexidade de Kolmogorov e suas principaispropriedades.

Objetivos especıficos

Apresentar tres aplicacoes da complexidade de Kolmogorov:

Distancia de informacao como metrica para a qualidade deimagem;

Distancia de informacao aplicada na classificacao(clusterizacao) de literatura lusofona segundo o estilo eperıodo literario;

Grafos k-aleatorios aplicados na determinacao depropriedades de redes de computadores.

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Objetivos da apresentacao

Objetivo geral

Apresentar a complexidade de Kolmogorov e suas principaispropriedades.

Objetivos especıficos

Apresentar tres aplicacoes da complexidade de Kolmogorov:

Distancia de informacao como metrica para a qualidade deimagem;

Distancia de informacao aplicada na classificacao(clusterizacao) de literatura lusofona segundo o estilo eperıodo literario;

Grafos k-aleatorios aplicados na determinacao depropriedades de redes de computadores.

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Objetivos da apresentacao

Objetivo geral

Apresentar a complexidade de Kolmogorov e suas principaispropriedades.

Objetivos especıficos

Apresentar tres aplicacoes da complexidade de Kolmogorov:

Distancia de informacao como metrica para a qualidade deimagem;

Distancia de informacao aplicada na classificacao(clusterizacao) de literatura lusofona segundo o estilo eperıodo literario;

Grafos k-aleatorios aplicados na determinacao depropriedades de redes de computadores.

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Sumario

1 Introducao

2 Complexidade de Kolmogorov

3 Aleatoriedade

4 Sequencias aleatorias de Martin-Lof

5 Distancia de informacao

6 Grafos k-aleatorios

7 Conclusoes

8 Para saber mais

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

O que e a complexidade de Kolmogorov?

Complexidade de Kolmogorov e uma teoria da informacaoe da aleatoriedade baseada no tamanho dos programaspara a maquina de Turing;

Expressa o quanto podemos comprimir algoritmicamenteuma string binaria;

Exemplos: gzip, compress, winzip, etc.

Usa a maquina de Turing (funcoes parciais recursivas)como metodo de descricao.

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

O que e a complexidade de Kolmogorov?

Complexidade de Kolmogorov e uma teoria da informacaoe da aleatoriedade baseada no tamanho dos programaspara a maquina de Turing;

Expressa o quanto podemos comprimir algoritmicamenteuma string binaria;

Exemplos: gzip, compress, winzip, etc.

Usa a maquina de Turing (funcoes parciais recursivas)como metodo de descricao.

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

O que e a complexidade de Kolmogorov?

Complexidade de Kolmogorov e uma teoria da informacaoe da aleatoriedade baseada no tamanho dos programaspara a maquina de Turing;

Expressa o quanto podemos comprimir algoritmicamenteuma string binaria;

Exemplos: gzip, compress, winzip, etc.

Usa a maquina de Turing (funcoes parciais recursivas)como metodo de descricao.

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

O que e a complexidade de Kolmogorov?

Complexidade de Kolmogorov e uma teoria da informacaoe da aleatoriedade baseada no tamanho dos programaspara a maquina de Turing;

Expressa o quanto podemos comprimir algoritmicamenteuma string binaria;

Exemplos: gzip, compress, winzip, etc.

Usa a maquina de Turing (funcoes parciais recursivas)como metodo de descricao.

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Modelo de maquina de Turing

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Definicao de complexidade de Kolmogorov

Complexidade condicional

Definimos a complexidade condicional CM(x |y)(“complexidade de x dado y”) como sendo o tamanho damenor descricao efetiva que computa x na maquina Mrecebendo y como entrada (informacao lateral).

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Observacoes

Os objetos sobre os quais se aplica a complexidade podemser tanto strings binarias, quanto numeros naturais, pois oconjunto das strings binarias e enumeravel:(

0 1 2 3 4 5 6 7 8 · · ·Λ 0 1 00 01 10 11 000 001 · · ·

)

Os programas para a maquina de Turing tambem seraorepresentados como strings binarias.

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Observacoes

Os objetos sobre os quais se aplica a complexidade podemser tanto strings binarias, quanto numeros naturais, pois oconjunto das strings binarias e enumeravel:(

0 1 2 3 4 5 6 7 8 · · ·Λ 0 1 00 01 10 11 000 001 · · ·

)Os programas para a maquina de Turing tambem seraorepresentados como strings binarias.

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Algumas definicoes

Formalizacao

Seja M uma maquina de Turing. Entao,CM(x |y) = minp|Mp(y) = x

Notacao

x denota o tamanho em bits de uma string binaria x(numero de dıgitos);

Mp(y) = x denota que a maquina M computa x pormeio do programa p recebendo y como entrada;

n vezes︷ ︸︸ ︷aaaa . . . a = an;

Sejam n ≥ 0 e m ≥ 0. n m denota n ≤ m + c , paraalgum c > 0.

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Algumas definicoes

Formalizacao

Seja M uma maquina de Turing. Entao,CM(x |y) = minp|Mp(y) = x

Notacao

x denota o tamanho em bits de uma string binaria x(numero de dıgitos);

Mp(y) = x denota que a maquina M computa x pormeio do programa p recebendo y como entrada;

n vezes︷ ︸︸ ︷aaaa . . . a = an;

Sejam n ≥ 0 e m ≥ 0. n m denota n ≤ m + c , paraalgum c > 0.

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Algumas definicoes

Formalizacao

Seja M uma maquina de Turing. Entao,CM(x |y) = minp|Mp(y) = x

Notacao

x denota o tamanho em bits de uma string binaria x(numero de dıgitos);

Mp(y) = x denota que a maquina M computa x pormeio do programa p recebendo y como entrada;

n vezes︷ ︸︸ ︷aaaa . . . a = an;

Sejam n ≥ 0 e m ≥ 0. n m denota n ≤ m + c , paraalgum c > 0.

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Algumas definicoes

Formalizacao

Seja M uma maquina de Turing. Entao,CM(x |y) = minp|Mp(y) = x

Notacao

x denota o tamanho em bits de uma string binaria x(numero de dıgitos);

Mp(y) = x denota que a maquina M computa x pormeio do programa p recebendo y como entrada;

n vezes︷ ︸︸ ︷aaaa . . . a = an;

Sejam n ≥ 0 e m ≥ 0. n m denota n ≤ m + c , paraalgum c > 0.

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Algumas definicoes

Formalizacao

Seja M uma maquina de Turing. Entao,CM(x |y) = minp|Mp(y) = x

Notacao

x denota o tamanho em bits de uma string binaria x(numero de dıgitos);

Mp(y) = x denota que a maquina M computa x pormeio do programa p recebendo y como entrada;

n vezes︷ ︸︸ ︷aaaa . . . a = an;

Sejam n ≥ 0 e m ≥ 0. n m denota n ≤ m + c , paraalgum c > 0.

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Observacoes adicionais

A existencia de uma funcao parcial recursiva universal(maquina de Turing universal) garante que,assintoticamente, a complexidade CM(x |y) dependeapenas de x e y ;

Seja φ1, φ2, φ3, . . . uma enumeracao das funcoes parciaisrecursivas;

Existe uma funcao φu, chamada universal, tal queφu(i , x) = φu([i , x ]) = φi (x) para todo i > 0;

[., .] : N× N → N e uma bijecao efetiva.

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Observacoes adicionais

A existencia de uma funcao parcial recursiva universal(maquina de Turing universal) garante que,assintoticamente, a complexidade CM(x |y) dependeapenas de x e y ;

Seja φ1, φ2, φ3, . . . uma enumeracao das funcoes parciaisrecursivas;

Existe uma funcao φu, chamada universal, tal queφu(i , x) = φu([i , x ]) = φi (x) para todo i > 0;

[., .] : N× N → N e uma bijecao efetiva.

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Observacoes adicionais

A existencia de uma funcao parcial recursiva universal(maquina de Turing universal) garante que,assintoticamente, a complexidade CM(x |y) dependeapenas de x e y ;

Seja φ1, φ2, φ3, . . . uma enumeracao das funcoes parciaisrecursivas;

Existe uma funcao φu, chamada universal, tal queφu(i , x) = φu([i , x ]) = φi (x) para todo i > 0;

[., .] : N× N → N e uma bijecao efetiva.

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Observacoes adicionais

A existencia de uma funcao parcial recursiva universal(maquina de Turing universal) garante que,assintoticamente, a complexidade CM(x |y) dependeapenas de x e y ;

Seja φ1, φ2, φ3, . . . uma enumeracao das funcoes parciaisrecursivas;

Existe uma funcao φu, chamada universal, tal queφu(i , x) = φu([i , x ]) = φi (x) para todo i > 0;

[., .] : N× N → N e uma bijecao efetiva.

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Teorema fundamental

Teorema da invariancia

Existe uma maquina U , chamada universal, tal que, paraqualquer maquina M, CU (x |y) CM(x |y);

Prova do teorema

Prova por simulacao de maquinas: Seja M1,M2,M3, . . . umaenumeracao padrao das maquinas. Assim,CM(x |y) = minp|Mp(y) = x e M e a n-esima maquina naenumeracao padrao. Entao:

CU (x |y) = min1n0p|U1n0p(y) = x =

= minp|U1n0p(y) = x+ n + 1 =

= CM(x |y) + n + 1

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Teorema fundamental

Teorema da invariancia

Existe uma maquina U , chamada universal, tal que, paraqualquer maquina M, CU (x |y) CM(x |y);

Prova do teorema

Prova por simulacao de maquinas: Seja M1,M2,M3, . . . umaenumeracao padrao das maquinas. Assim,CM(x |y) = minp|Mp(y) = x e M e a n-esima maquina naenumeracao padrao. Entao:

CU (x |y) = min1n0p|U1n0p(y) = x =

= minp|U1n0p(y) = x+ n + 1 =

= CM(x |y) + n + 1

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Consequencia do teorema da invariancia

Consequencia

Dadas duas maquinas universais U1 e U2 sabemos que:

|CU1(x |y)− CU2(x |y)| ≤ c

para algum c > 0 e c nao depende de x e y .

Exemplo

|CPROLOG(x |y)− CLISP(x |y)| ≤ c

Notacao devido a esta propriedade

Podemos reescrever CU (x |y) como C (x |y).

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Consequencia do teorema da invariancia

Consequencia

Dadas duas maquinas universais U1 e U2 sabemos que:

|CU1(x |y)− CU2(x |y)| ≤ c

para algum c > 0 e c nao depende de x e y .

Exemplo

|CPROLOG(x |y)− CLISP(x |y)| ≤ c

Notacao devido a esta propriedade

Podemos reescrever CU (x |y) como C (x |y).

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Consequencia do teorema da invariancia

Consequencia

Dadas duas maquinas universais U1 e U2 sabemos que:

|CU1(x |y)− CU2(x |y)| ≤ c

para algum c > 0 e c nao depende de x e y .

Exemplo

|CPROLOG(x |y)− CLISP(x |y)| ≤ c

Notacao devido a esta propriedade

Podemos reescrever CU (x |y) como C (x |y).

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Complexidade incondicional

Definicao

Definimos a complexidade incondicional C (x) (“complexidadede x”) como sendo igual a C (x |Λ).

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Algumas propriedades da complexidade basica

C (x |y) C (x);

C (x |y) x ;

C (x |y) nao e computavel (por reducao ao problema daparada).

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Algumas propriedades da complexidade basica

C (x |y) C (x);

C (x |y) x ;

C (x |y) nao e computavel (por reducao ao problema daparada).

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Algumas propriedades da complexidade basica

C (x |y) C (x);

C (x |y) x ;

C (x |y) nao e computavel (por reducao ao problema daparada).

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Complexidade de prefixo

Existe uma segunda versao da teoria, chamadacomplexidade de prefixo, K (x |y);

Define-se K (x |y) exigindo que as descricoes (programas)usadas sejam livres de prefixo;

Uma codificacao livre de prefixo e aquela em que nenhumadescricao e prefixo de outra;

Um codigo livre de prefixo contem seu proprio tamanho.

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Complexidade de prefixo

Existe uma segunda versao da teoria, chamadacomplexidade de prefixo, K (x |y);

Define-se K (x |y) exigindo que as descricoes (programas)usadas sejam livres de prefixo;

Uma codificacao livre de prefixo e aquela em que nenhumadescricao e prefixo de outra;

Um codigo livre de prefixo contem seu proprio tamanho.

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Complexidade de prefixo

Existe uma segunda versao da teoria, chamadacomplexidade de prefixo, K (x |y);

Define-se K (x |y) exigindo que as descricoes (programas)usadas sejam livres de prefixo;

Uma codificacao livre de prefixo e aquela em que nenhumadescricao e prefixo de outra;

Um codigo livre de prefixo contem seu proprio tamanho.

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Complexidade de prefixo

Existe uma segunda versao da teoria, chamadacomplexidade de prefixo, K (x |y);

Define-se K (x |y) exigindo que as descricoes (programas)usadas sejam livres de prefixo;

Uma codificacao livre de prefixo e aquela em que nenhumadescricao e prefixo de outra;

Um codigo livre de prefixo contem seu proprio tamanho.

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Propriedades da Complexidade de Prefixo

Propriedade

Podemos concatenar strings sem problemas, e recuperar asstrings originais a partir da concatenada.

Propriedade importante

∑x

2−K(x |y) < ∞

Observacao

∑x

2−C(x |y) = ∞

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Propriedades da Complexidade de Prefixo

Propriedade

Podemos concatenar strings sem problemas, e recuperar asstrings originais a partir da concatenada.

Propriedade importante

∑x

2−K(x |y) < ∞

Observacao

∑x

2−C(x |y) = ∞

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Propriedades da Complexidade de Prefixo

Propriedade

Podemos concatenar strings sem problemas, e recuperar asstrings originais a partir da concatenada.

Propriedade importante

∑x

2−K(x |y) < ∞

Observacao

∑x

2−C(x |y) = ∞

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Codificacao livre de prefixo

Definicao

E1(x) =

x vezes︷ ︸︸ ︷1111 . . . 1 0x = 1x0x ou

E2(x) = E1(x)x = 1x0xx ;

E1(x) = 2x + 1 e E2(x) = x + 2x + 1.

Propriedades

Sabemos que x ∼= log x (pela codificacao binaria), entaoE2(x) ∼= x + 2 log x ;

C (x |y) K (x |y) C (x |y) + 2 log C (x |y).

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Codificacao livre de prefixo

Definicao

E1(x) =

x vezes︷ ︸︸ ︷1111 . . . 1 0x = 1x0x ou

E2(x) = E1(x)x = 1x0xx ;

E1(x) = 2x + 1 e E2(x) = x + 2x + 1.

Propriedades

Sabemos que x ∼= log x (pela codificacao binaria), entaoE2(x) ∼= x + 2 log x ;

C (x |y) K (x |y) C (x |y) + 2 log C (x |y).

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Codificacao livre de prefixo

Definicao

E1(x) =

x vezes︷ ︸︸ ︷1111 . . . 1 0x = 1x0x ou

E2(x) = E1(x)x = 1x0xx ;

E1(x) = 2x + 1 e E2(x) = x + 2x + 1.

Propriedades

Sabemos que x ∼= log x (pela codificacao binaria), entaoE2(x) ∼= x + 2 log x ;

C (x |y) K (x |y) C (x |y) + 2 log C (x |y).

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Codificacao livre de prefixo

Definicao

E1(x) =

x vezes︷ ︸︸ ︷1111 . . . 1 0x = 1x0x ou

E2(x) = E1(x)x = 1x0xx ;

E1(x) = 2x + 1 e E2(x) = x + 2x + 1.

Propriedades

Sabemos que x ∼= log x (pela codificacao binaria), entaoE2(x) ∼= x + 2 log x ;

C (x |y) K (x |y) C (x |y) + 2 log C (x |y).

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Sumario

1 Introducao

2 Complexidade de Kolmogorov

3 Aleatoriedade

4 Sequencias aleatorias de Martin-Lof

5 Distancia de informacao

6 Grafos k-aleatorios

7 Conclusoes

8 Para saber mais

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Incompressividade

O proposito original da complexidade de Kolmogorov eradefinir sequencias aleatorias formalmente, embasando umateoria matematica das probabilidades;

Strings binarias podem representar sequencias aleatoriasgeradas pelo lancamento sucessivo de uma moeda.

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Incompressividade

O proposito original da complexidade de Kolmogorov eradefinir sequencias aleatorias formalmente, embasando umateoria matematica das probabilidades;

Strings binarias podem representar sequencias aleatoriasgeradas pelo lancamento sucessivo de uma moeda.

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Incompressividade

Sequencia de eventos

Representacao

1011010

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Incompressividade

Sequencia de eventos

Representacao

1011010

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Strings binarias

Seria este um bom modelo para estudar o fenomeno daaleatoriedade?

Strings binarias podem representar qualquer fenomenoaleatorio por meio de uma codificacao apropriada;Embora limitado a distribuicao uniforme, podemosextender o modelo para outras distribuicoes.

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Strings binarias

Seria este um bom modelo para estudar o fenomeno daaleatoriedade?

Strings binarias podem representar qualquer fenomenoaleatorio por meio de uma codificacao apropriada;

Embora limitado a distribuicao uniforme, podemosextender o modelo para outras distribuicoes.

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Strings binarias

Seria este um bom modelo para estudar o fenomeno daaleatoriedade?

Strings binarias podem representar qualquer fenomenoaleatorio por meio de uma codificacao apropriada;Embora limitado a distribuicao uniforme, podemosextender o modelo para outras distribuicoes.

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Lei dos grandes numeros

(Teoria do limite da frequencia relativa) Em umasequencia longa de tentativas, as frequencias relativas dasocorrencias de sucesso ou fracasso em um experimentodevem convergir a um limite,

limn→∞

λ(n)/n = p

No caso particular da distribuicao uniforme (moedahonesta), p = 1/2.

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Lei dos grandes numeros

(Teoria do limite da frequencia relativa) Em umasequencia longa de tentativas, as frequencias relativas dasocorrencias de sucesso ou fracasso em um experimentodevem convergir a um limite,

limn→∞

λ(n)/n = p

No caso particular da distribuicao uniforme (moedahonesta), p = 1/2.

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Problema!

Problema

O que e “uma sequencia longa”?

Andrei Kolmogorov

A teoria do limite de frequencia (lei dos grandes numeros) tempouca ou nenhuma utilidade pratica em teoria dasprobabilidades e estatıstica, pois todas as amostras sao semprefinitas.

John Keynes

“In the long run we shall be dead.”

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Problema!

Problema

O que e “uma sequencia longa”?

Andrei Kolmogorov

A teoria do limite de frequencia (lei dos grandes numeros) tempouca ou nenhuma utilidade pratica em teoria dasprobabilidades e estatıstica, pois todas as amostras sao semprefinitas.

John Keynes

“In the long run we shall be dead.”

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Problema!

Problema

O que e “uma sequencia longa”?

Andrei Kolmogorov

A teoria do limite de frequencia (lei dos grandes numeros) tempouca ou nenhuma utilidade pratica em teoria dasprobabilidades e estatıstica, pois todas as amostras sao semprefinitas.

John Keynes

“In the long run we shall be dead.”

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Nossa percepcao da aleatoriedade

Um exemplo

Segundo a nossa intuicao, o que poderiamos dizer sobre aaleatoriedade das seguintes strings binarias?

111111111111111111110101010101010101010101001101011000110101

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Aleatoriedade

Podemos abordar o fenomeno da aleatoriedade dasseguintes formas:

Sequencias que possuem um limite de frequencia relativa(lei dos grandes numeros);Pertinencia a maiorias (probabilidade de ocorrencia);Incompressividade das sequencias.

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Aleatoriedade

Podemos abordar o fenomeno da aleatoriedade dasseguintes formas:

Sequencias que possuem um limite de frequencia relativa(lei dos grandes numeros);

Pertinencia a maiorias (probabilidade de ocorrencia);Incompressividade das sequencias.

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Aleatoriedade

Podemos abordar o fenomeno da aleatoriedade dasseguintes formas:

Sequencias que possuem um limite de frequencia relativa(lei dos grandes numeros);Pertinencia a maiorias (probabilidade de ocorrencia);

Incompressividade das sequencias.

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Aleatoriedade

Podemos abordar o fenomeno da aleatoriedade dasseguintes formas:

Sequencias que possuem um limite de frequencia relativa(lei dos grandes numeros);Pertinencia a maiorias (probabilidade de ocorrencia);Incompressividade das sequencias.

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Incompressividade e irregularidade

String regular

11111111111111111111

FOR I:=1 TO 20 PRINT 1

String irregular

01001101011000110101

PRINT 01001101011000110101

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Incompressividade e Irregularidade

Definicao

Uma string binaria x e incompressıvel se C (x |n) ≥ n − c , onden = x e c e a deficiencia de aleatoriedade.

Observacao

Chamamos x de c-aleatoria.

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Incompressividade e Irregularidade

Definicao

Uma string binaria x e incompressıvel se C (x |n) ≥ n − c , onden = x e c e a deficiencia de aleatoriedade.

Observacao

Chamamos x de c-aleatoria.

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Teorema fundamental

Teorema da incompressividade

Seja c > 0. Fixando y , todo conjunto A de cardinalidade mtem ao menos m(1− 2−c) + 1 elementos x comC (x |y) ≥ log m − c .

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Sumario

1 Introducao

2 Complexidade de Kolmogorov

3 Aleatoriedade

4 Sequencias aleatorias de Martin-Lof

5 Distancia de informacao

6 Grafos k-aleatorios

7 Conclusoes

8 Para saber mais

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Sequencias aleatorias de Martin-Lof

Sequencias tıpicas

Uma sequencia e atıpica se ela pertence a um conjuntocom medida zero;

Cada sequencia tıpica pertence a uma maioria;

O conjunto das sequencias tıpicas e a interseccao doscomplementos destes conjuntos de medida zero.

Problema!

Cada sequencia x em particular induz um teste dealeatoriedade que a exclui de uma maioria;

A interseccao de todas as maiorias seria vazia, ou seja,nao existiriam sequencias aleatorias!

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Sequencias aleatorias de Martin-Lof

Sequencias tıpicas

Uma sequencia e atıpica se ela pertence a um conjuntocom medida zero;

Cada sequencia tıpica pertence a uma maioria;

O conjunto das sequencias tıpicas e a interseccao doscomplementos destes conjuntos de medida zero.

Problema!

Cada sequencia x em particular induz um teste dealeatoriedade que a exclui de uma maioria;

A interseccao de todas as maiorias seria vazia, ou seja,nao existiriam sequencias aleatorias!

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Sequencias aleatorias de Martin-Lof

Sequencias tıpicas

Uma sequencia e atıpica se ela pertence a um conjuntocom medida zero;

Cada sequencia tıpica pertence a uma maioria;

O conjunto das sequencias tıpicas e a interseccao doscomplementos destes conjuntos de medida zero.

Problema!

Cada sequencia x em particular induz um teste dealeatoriedade que a exclui de uma maioria;

A interseccao de todas as maiorias seria vazia, ou seja,nao existiriam sequencias aleatorias!

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Sequencias aleatorias de Martin-Lof

Sequencias tıpicas

Uma sequencia e atıpica se ela pertence a um conjuntocom medida zero;

Cada sequencia tıpica pertence a uma maioria;

O conjunto das sequencias tıpicas e a interseccao doscomplementos destes conjuntos de medida zero.

Problema!

Cada sequencia x em particular induz um teste dealeatoriedade que a exclui de uma maioria;

A interseccao de todas as maiorias seria vazia, ou seja,nao existiriam sequencias aleatorias!

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Sequencias aleatorias de Martin-Lof

Sequencias tıpicas

Uma sequencia e atıpica se ela pertence a um conjuntocom medida zero;

Cada sequencia tıpica pertence a uma maioria;

O conjunto das sequencias tıpicas e a interseccao doscomplementos destes conjuntos de medida zero.

Problema!

Cada sequencia x em particular induz um teste dealeatoriedade que a exclui de uma maioria;

A interseccao de todas as maiorias seria vazia, ou seja,nao existiriam sequencias aleatorias!

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Sequencias aleatorias de Martin-Lof

Solucao

Martin-Lof restringiu os testes de aleatoriedade aoscomputaveis;

Conjunto das sequencias aleatorias possui complementorecursivamente enumeravel;

As sequencias regulares formam um conjunto nulo(medida zero);

Teorema: Existe um conjunto efetivo nulo maximal;

Ou seja, se M e o conjunto efetivo nulo maximal entaoX ⊂ M, para todo conjunto efetivo nulo X ;

Isto significa que a uniao de todos os conjuntos efetivosnulos e tambem um conjunto efetivo nulo.

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Sequencias aleatorias de Martin-Lof

Solucao

Martin-Lof restringiu os testes de aleatoriedade aoscomputaveis;

Conjunto das sequencias aleatorias possui complementorecursivamente enumeravel;

As sequencias regulares formam um conjunto nulo(medida zero);

Teorema: Existe um conjunto efetivo nulo maximal;

Ou seja, se M e o conjunto efetivo nulo maximal entaoX ⊂ M, para todo conjunto efetivo nulo X ;

Isto significa que a uniao de todos os conjuntos efetivosnulos e tambem um conjunto efetivo nulo.

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Sequencias aleatorias de Martin-Lof

Solucao

Martin-Lof restringiu os testes de aleatoriedade aoscomputaveis;

Conjunto das sequencias aleatorias possui complementorecursivamente enumeravel;

As sequencias regulares formam um conjunto nulo(medida zero);

Teorema: Existe um conjunto efetivo nulo maximal;

Ou seja, se M e o conjunto efetivo nulo maximal entaoX ⊂ M, para todo conjunto efetivo nulo X ;

Isto significa que a uniao de todos os conjuntos efetivosnulos e tambem um conjunto efetivo nulo.

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Sequencias aleatorias de Martin-Lof

Solucao

Martin-Lof restringiu os testes de aleatoriedade aoscomputaveis;

Conjunto das sequencias aleatorias possui complementorecursivamente enumeravel;

As sequencias regulares formam um conjunto nulo(medida zero);

Teorema: Existe um conjunto efetivo nulo maximal;

Ou seja, se M e o conjunto efetivo nulo maximal entaoX ⊂ M, para todo conjunto efetivo nulo X ;

Isto significa que a uniao de todos os conjuntos efetivosnulos e tambem um conjunto efetivo nulo.

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Sequencias aleatorias de Martin-Lof

Solucao

Martin-Lof restringiu os testes de aleatoriedade aoscomputaveis;

Conjunto das sequencias aleatorias possui complementorecursivamente enumeravel;

As sequencias regulares formam um conjunto nulo(medida zero);

Teorema: Existe um conjunto efetivo nulo maximal;

Ou seja, se M e o conjunto efetivo nulo maximal entaoX ⊂ M, para todo conjunto efetivo nulo X ;

Isto significa que a uniao de todos os conjuntos efetivosnulos e tambem um conjunto efetivo nulo.

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Sequencias aleatorias de Martin-Lof

Solucao

Martin-Lof restringiu os testes de aleatoriedade aoscomputaveis;

Conjunto das sequencias aleatorias possui complementorecursivamente enumeravel;

As sequencias regulares formam um conjunto nulo(medida zero);

Teorema: Existe um conjunto efetivo nulo maximal;

Ou seja, se M e o conjunto efetivo nulo maximal entaoX ⊂ M, para todo conjunto efetivo nulo X ;

Isto significa que a uniao de todos os conjuntos efetivosnulos e tambem um conjunto efetivo nulo.

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Definicao de Martin-Lof

Definicao

Uma string x = x1x2x3 · · · e Martin-Lof aleatoria se e somentese, para alguma constante c > 0, K (x1x2x3 · · · xn) ≥ n − c ,para todo n.

Equivalencia entre as definicoes

Ou seja, ha equivalencia entre a definicao de aleatoriedadede Martin-Lof e a definicao via incompressividade destrings binarias;

Esta equivalencia e uma evidencia da correcao desta teoria.

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Definicao de Martin-Lof

Definicao

Uma string x = x1x2x3 · · · e Martin-Lof aleatoria se e somentese, para alguma constante c > 0, K (x1x2x3 · · · xn) ≥ n − c ,para todo n.

Equivalencia entre as definicoes

Ou seja, ha equivalencia entre a definicao de aleatoriedadede Martin-Lof e a definicao via incompressividade destrings binarias;

Esta equivalencia e uma evidencia da correcao desta teoria.

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Definicao de Martin-Lof

Definicao

Uma string x = x1x2x3 · · · e Martin-Lof aleatoria se e somentese, para alguma constante c > 0, K (x1x2x3 · · · xn) ≥ n − c ,para todo n.

Equivalencia entre as definicoes

Ou seja, ha equivalencia entre a definicao de aleatoriedadede Martin-Lof e a definicao via incompressividade destrings binarias;

Esta equivalencia e uma evidencia da correcao desta teoria.

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Sumario

1 Introducao

2 Complexidade de Kolmogorov

3 Aleatoriedade

4 Sequencias aleatorias de Martin-Lof

5 Distancia de informacao

6 Grafos k-aleatorios

7 Conclusoes

8 Para saber mais

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Distancia de informacao

A distancia de informacao e uma metrica universal a priorisobre as strings binarias;

Embora nao computavel, podemos obter uma aproximacaocomputavel usando programas de compressao de dados(gzip, bzip2, etc.).

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Distancia de informacao

A distancia de informacao e uma metrica universal a priorisobre as strings binarias;

Embora nao computavel, podemos obter uma aproximacaocomputavel usando programas de compressao de dados(gzip, bzip2, etc.).

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Aplicacoes

Precedentes

Classificacao automatica de musica (por genero e autor);

Determinacao do parentesco de lınguas humanas;

Reconhecimento de DNA mitocondrial.

Aplicacoes desenvolvidas

Classificacao (clustering) de literatura lusofona segundoestilo e perıodo literario;

Como uma metrica de qualidade de imagem.

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Aplicacoes

Precedentes

Classificacao automatica de musica (por genero e autor);

Determinacao do parentesco de lınguas humanas;

Reconhecimento de DNA mitocondrial.

Aplicacoes desenvolvidas

Classificacao (clustering) de literatura lusofona segundoestilo e perıodo literario;

Como uma metrica de qualidade de imagem.

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Aplicacoes

Precedentes

Classificacao automatica de musica (por genero e autor);

Determinacao do parentesco de lınguas humanas;

Reconhecimento de DNA mitocondrial.

Aplicacoes desenvolvidas

Classificacao (clustering) de literatura lusofona segundoestilo e perıodo literario;

Como uma metrica de qualidade de imagem.

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Aplicacoes

Precedentes

Classificacao automatica de musica (por genero e autor);

Determinacao do parentesco de lınguas humanas;

Reconhecimento de DNA mitocondrial.

Aplicacoes desenvolvidas

Classificacao (clustering) de literatura lusofona segundoestilo e perıodo literario;

Como uma metrica de qualidade de imagem.

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Aplicacoes

Precedentes

Classificacao automatica de musica (por genero e autor);

Determinacao do parentesco de lınguas humanas;

Reconhecimento de DNA mitocondrial.

Aplicacoes desenvolvidas

Classificacao (clustering) de literatura lusofona segundoestilo e perıodo literario;

Como uma metrica de qualidade de imagem.

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Metrica de qualidade de imagem

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Metrica de qualidade de imagem

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Metrica de qualidade de imagem

Necessidade

Muitas vezes ha a necessidade de transformar uma imagempara armazena-la.

Exemplos

Tratamento de imagens;

Compressao de dados com perdas;

Similaridade entre imagens

Medida da similaridade ou distancia entre imagens;

Isto e o que chamamos de metrica de qualidade deimagem.

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Metrica de qualidade de imagem

Necessidade

Muitas vezes ha a necessidade de transformar uma imagempara armazena-la.

Exemplos

Tratamento de imagens;

Compressao de dados com perdas;

Similaridade entre imagens

Medida da similaridade ou distancia entre imagens;

Isto e o que chamamos de metrica de qualidade deimagem.

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Metrica de qualidade de imagem

Necessidade

Muitas vezes ha a necessidade de transformar uma imagempara armazena-la.

Exemplos

Tratamento de imagens;

Compressao de dados com perdas;

Similaridade entre imagens

Medida da similaridade ou distancia entre imagens;

Isto e o que chamamos de metrica de qualidade deimagem.

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Metrica de qualidade de imagem

Necessidade

Muitas vezes ha a necessidade de transformar uma imagempara armazena-la.

Exemplos

Tratamento de imagens;

Compressao de dados com perdas;

Similaridade entre imagens

Medida da similaridade ou distancia entre imagens;

Isto e o que chamamos de metrica de qualidade deimagem.

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Metrica de qualidade de imagem

Necessidade

Muitas vezes ha a necessidade de transformar uma imagempara armazena-la.

Exemplos

Tratamento de imagens;

Compressao de dados com perdas;

Similaridade entre imagens

Medida da similaridade ou distancia entre imagens;

Isto e o que chamamos de metrica de qualidade deimagem.

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Definicao de distancia

Seja S um espaco. Uma metrica para S e uma funcao definidasobre o produto cartesiano S × S , d : S × S → R, se e somentese para todo x , y , z ∈ S :

1 d(x , y) ≥ 0 e d(x , y) = 0 se e somente se x = y ;

2 d(x , y) = d(y , x) (simetria);

3 d(x , y) ≤ d(x , z) + d(z , y) (desigualdade triangular).

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Definicao de distancia

Seja S um espaco. Uma metrica para S e uma funcao definidasobre o produto cartesiano S × S , d : S × S → R, se e somentese para todo x , y , z ∈ S :

1 d(x , y) ≥ 0 e d(x , y) = 0 se e somente se x = y ;

2 d(x , y) = d(y , x) (simetria);

3 d(x , y) ≤ d(x , z) + d(z , y) (desigualdade triangular).

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Definicao de distancia

Seja S um espaco. Uma metrica para S e uma funcao definidasobre o produto cartesiano S × S , d : S × S → R, se e somentese para todo x , y , z ∈ S :

1 d(x , y) ≥ 0 e d(x , y) = 0 se e somente se x = y ;

2 d(x , y) = d(y , x) (simetria);

3 d(x , y) ≤ d(x , z) + d(z , y) (desigualdade triangular).

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Definicao de distancia

Seja S um espaco. Uma metrica para S e uma funcao definidasobre o produto cartesiano S × S , d : S × S → R, se e somentese para todo x , y , z ∈ S :

1 d(x , y) ≥ 0 e d(x , y) = 0 se e somente se x = y ;

2 d(x , y) = d(y , x) (simetria);

3 d(x , y) ≤ d(x , z) + d(z , y) (desigualdade triangular).

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Distancia de informacao

Definicao

d(x , y) =max(K (x |y),K (y |x))

max(K (x),K (y))

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Distancia de informacao

Propriedades

Distancia de informacao satisfaz uma versao fraca de metrica:

Simetria d(x , y) = d(y , x);

Identidade fraca d(x , x) = O(1/K (x)) pois K (x |x) ≈ O(1);

Desigualdade triangular fraca d(x , y) ≤d(x , z) + d(z , y) + O

(1

max(K(x),K(y),K(z))

).

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Distancia de informacao

Propriedades

Distancia de informacao satisfaz uma versao fraca de metrica:

Simetria d(x , y) = d(y , x);

Identidade fraca d(x , x) = O(1/K (x)) pois K (x |x) ≈ O(1);

Desigualdade triangular fraca d(x , y) ≤d(x , z) + d(z , y) + O

(1

max(K(x),K(y),K(z))

).

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Distancia de informacao

Propriedades

Distancia de informacao satisfaz uma versao fraca de metrica:

Simetria d(x , y) = d(y , x);

Identidade fraca d(x , x) = O(1/K (x)) pois K (x |x) ≈ O(1);

Desigualdade triangular fraca d(x , y) ≤d(x , z) + d(z , y) + O

(1

max(K(x),K(y),K(z))

).

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Distancia de informacao

Propriedades

Distancia de informacao satisfaz uma versao fraca de metrica:

Simetria d(x , y) = d(y , x);

Identidade fraca d(x , x) = O(1/K (x)) pois K (x |x) ≈ O(1);

Desigualdade triangular fraca d(x , y) ≤d(x , z) + d(z , y) + O

(1

max(K(x),K(y),K(z))

).

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Distancia de informacao

Propriedade da universalidade

d(x , y) ≤ f (x , y) + O

(log max(K (x),K (y))

max(K (x),K (y))

),

onde f (., .) e uma distancia normalizada semi-computavel porcima qualquer.

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Uso de aproximacao

Aplicacao da distancia

Para aplicar na pratica a medida e necessario obter umaaproximacao computavel usando um programa de compressaode dados.

Problema

Nao podemos aproximar complexidades condicionais.

Solucao (Peter Gacs)

K (x |y) ≈ K (yx)− K (y)

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Uso de aproximacao

Aplicacao da distancia

Para aplicar na pratica a medida e necessario obter umaaproximacao computavel usando um programa de compressaode dados.

Problema

Nao podemos aproximar complexidades condicionais.

Solucao (Peter Gacs)

K (x |y) ≈ K (yx)− K (y)

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Uso de aproximacao

Aplicacao da distancia

Para aplicar na pratica a medida e necessario obter umaaproximacao computavel usando um programa de compressaode dados.

Problema

Nao podemos aproximar complexidades condicionais.

Solucao (Peter Gacs)

K (x |y) ≈ K (yx)− K (y)

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Classificacao de literatura lusofona

Ideia

Usar a distancia de informacao como um discriminante paraagrupar (clustering) obras da literatura lusofona,classificando-as automaticamente em relacao ao estilo eperıodo literario.

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Classificacao de literatura lusofona

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Classificacao de literatura lusofona

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Sumario

1 Introducao

2 Complexidade de Kolmogorov

3 Aleatoriedade

4 Sequencias aleatorias de Martin-Lof

5 Distancia de informacao

6 Grafos k-aleatorios

7 Conclusoes

8 Para saber mais

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Grafos aleatorios

Objetivo

Expressar propriedades de grafos cujas arestasdistribuem-se de forma aleatoria;

Estas propriedades valem com probabilidade 1 para grafoscom um numero infinito de vertices;

As propriedades destes grafos podem ser generalizadas(assintoticamente) para grafos com um numero finito devertices;

Aplicacao

Provar propriedades de redes de computadores com conexoesquase aleatorias (que se interconecta de forma caotica).

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Grafos aleatorios

Objetivo

Expressar propriedades de grafos cujas arestasdistribuem-se de forma aleatoria;

Estas propriedades valem com probabilidade 1 para grafoscom um numero infinito de vertices;

As propriedades destes grafos podem ser generalizadas(assintoticamente) para grafos com um numero finito devertices;

Aplicacao

Provar propriedades de redes de computadores com conexoesquase aleatorias (que se interconecta de forma caotica).

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Grafos aleatorios

Objetivo

Expressar propriedades de grafos cujas arestasdistribuem-se de forma aleatoria;

Estas propriedades valem com probabilidade 1 para grafoscom um numero infinito de vertices;

As propriedades destes grafos podem ser generalizadas(assintoticamente) para grafos com um numero finito devertices;

Aplicacao

Provar propriedades de redes de computadores com conexoesquase aleatorias (que se interconecta de forma caotica).

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Grafos aleatorios

Objetivo

Expressar propriedades de grafos cujas arestasdistribuem-se de forma aleatoria;

Estas propriedades valem com probabilidade 1 para grafoscom um numero infinito de vertices;

As propriedades destes grafos podem ser generalizadas(assintoticamente) para grafos com um numero finito devertices;

Aplicacao

Provar propriedades de redes de computadores com conexoesquase aleatorias (que se interconecta de forma caotica).

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Grafo rotulado

Definicao

Um grafo rotulado e um par G = (V ,A) (V , conjunto devertices e A, conjunto de arestas) sobre n verticesV = 1, 2, . . . , n, tal que podemos representa-lo por umastring binaria E (G ) de tamanho

(n2

).

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Diagrama

Um exemplo

/.-,()*+2nnnnnnnnnnnnnn

AAAA

AAAA

0000

0000

0000

0

/.-,()*+1AA

AAAA

AA

UUUUUUUUUUUUUUUUUUUU /.-,()*+3/.-,()*+5 /.-,()*+4

Representacao

1011︸ ︷︷ ︸1

110︸︷︷︸2

00︸︷︷︸3

1︸︷︷︸4

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Diagrama

Um exemplo

/.-,()*+2nnnnnnnnnnnnnn

AAAA

AAAA

0000

0000

0000

0

/.-,()*+1AA

AAAA

AA

UUUUUUUUUUUUUUUUUUUU /.-,()*+3/.-,()*+5 /.-,()*+4

Representacao

1011︸ ︷︷ ︸1

110︸︷︷︸2

00︸︷︷︸3

1︸︷︷︸4

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Deficiencia de aleatoriedade

Um grafo rotulado G sobre n vertices tem deficiencia dealeatoriedade no maximo δ(n), e e chamado de δ(n)-aleatorio,se satisfaz:

C (E (G )|n) ≥(

n

2

)− δ(n)

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Propriedades

A fracao de pelo menos 1− 1/2δ(n) de todos os grafosrotulados G sobre n vertices e δ(n)-aleatorio (peloTeorema da Incompressividade);

Todo grafo aleatorio rotulado (grafo que tem “altacomplexidade de Kolmogorov”) possui n/4 caminhosdisjuntos de tamanho 2 entre quaisquer dois vertices;

Para todo grafo aleatorio rotulado o grau de nodo paratodo vertice e n/2.

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Propriedades

A fracao de pelo menos 1− 1/2δ(n) de todos os grafosrotulados G sobre n vertices e δ(n)-aleatorio (peloTeorema da Incompressividade);

Todo grafo aleatorio rotulado (grafo que tem “altacomplexidade de Kolmogorov”) possui n/4 caminhosdisjuntos de tamanho 2 entre quaisquer dois vertices;

Para todo grafo aleatorio rotulado o grau de nodo paratodo vertice e n/2.

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Propriedades

A fracao de pelo menos 1− 1/2δ(n) de todos os grafosrotulados G sobre n vertices e δ(n)-aleatorio (peloTeorema da Incompressividade);

Todo grafo aleatorio rotulado (grafo que tem “altacomplexidade de Kolmogorov”) possui n/4 caminhosdisjuntos de tamanho 2 entre quaisquer dois vertices;

Para todo grafo aleatorio rotulado o grau de nodo paratodo vertice e n/2.

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Sumario

1 Introducao

2 Complexidade de Kolmogorov

3 Aleatoriedade

4 Sequencias aleatorias de Martin-Lof

5 Distancia de informacao

6 Grafos k-aleatorios

7 Conclusoes

8 Para saber mais

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Conclusoes

Existem boas possibilidades de pesquisa na area decomplexidade de Kolmogorov;

Aplicacoes da complexidade de Kolmogorov podem seruteis na pratica de ciencia da computacao, como porexemplo:

Determinar a qualidade de imagens submetidas adistorcoes;Classificacao (clustering) de literatura lusofona;Estabelecer propriedades topologicas de redes decomputadores (com conexoes caoticas).

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Conclusoes

Existem boas possibilidades de pesquisa na area decomplexidade de Kolmogorov;

Aplicacoes da complexidade de Kolmogorov podem seruteis na pratica de ciencia da computacao, como porexemplo:

Determinar a qualidade de imagens submetidas adistorcoes;Classificacao (clustering) de literatura lusofona;Estabelecer propriedades topologicas de redes decomputadores (com conexoes caoticas).

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Conclusoes

Existem boas possibilidades de pesquisa na area decomplexidade de Kolmogorov;

Aplicacoes da complexidade de Kolmogorov podem seruteis na pratica de ciencia da computacao, como porexemplo:

Determinar a qualidade de imagens submetidas adistorcoes;

Classificacao (clustering) de literatura lusofona;Estabelecer propriedades topologicas de redes decomputadores (com conexoes caoticas).

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Conclusoes

Existem boas possibilidades de pesquisa na area decomplexidade de Kolmogorov;

Aplicacoes da complexidade de Kolmogorov podem seruteis na pratica de ciencia da computacao, como porexemplo:

Determinar a qualidade de imagens submetidas adistorcoes;Classificacao (clustering) de literatura lusofona;

Estabelecer propriedades topologicas de redes decomputadores (com conexoes caoticas).

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Conclusoes

Existem boas possibilidades de pesquisa na area decomplexidade de Kolmogorov;

Aplicacoes da complexidade de Kolmogorov podem seruteis na pratica de ciencia da computacao, como porexemplo:

Determinar a qualidade de imagens submetidas adistorcoes;Classificacao (clustering) de literatura lusofona;Estabelecer propriedades topologicas de redes decomputadores (com conexoes caoticas).

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Sumario

1 Introducao

2 Complexidade de Kolmogorov

3 Aleatoriedade

4 Sequencias aleatorias de Martin-Lof

5 Distancia de informacao

6 Grafos k-aleatorios

7 Conclusoes

8 Para saber mais

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Para saber mais

H. Buhrman, Ming Li, J. Tromp, and Paul Vitanyi.Kolmogorov random graphs and the incompressibilitymethod.SIAM J. Comput., 29(2):590–599, 1999.

Ming Li, Xin Chen, Xin Li, Bin Ma, and Paul Vitanyi.The similarity metric.In 14th ACM-SIAM Symp. Discrete Algorithms, SODA,2003.

Ming Li and Paul Vitanyi.An Introduction to Kolmogorov Complexity and itsApplications.Springer, New York, 1997.

Aplicacoes daComplexidade

deKolmogorov

Carlos A. P.Campani

Introducao

ComplexidadedeKolmogorov

Aleatoriedade

Sequenciasaleatorias deMartin-Lof

Distancia deinformacao

Grafosk-aleatorios

Conclusoes

Para sabermais

Links

Grupo Ω− π http://minerva.ufpel.tche.br/~campani/grupo.htm

Kolmogorov Complexity and Solomonoff Inductionhttp://www.hutter1.de/kolmo.htm