View
694
Download
0
Category
Preview:
DESCRIPTION
Lâminas introdutória sobre complexidade de Kolmogorov e suas aplicações
Citation preview
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
Recommended