Algoritmos: Teoria e Engenharia Eduardo Sany Laber Departamento de Informática PUC-RIO

Algoritmos: Teoria e Engenharia

Eduardo Sany Laber

Departamento de InformáticaPUC-RIO

• Permite armazenar e processar uma quantidade enorme de dados

• Impacto gigantesco em diversos ramos da ciência

O Computador

• Quais problemas podem ser resolvidos com o auxílio de um computador ?

– Modelo formal de um computador (Turing, Church, década de 30)

– Existem problemas que não podem ser resolvidos por um computador (Turing, Church, década de 30)

Ciência da Computação

• Quais problemas podem ser resolvidos eficientemente com o auxílio de um computador ?

– Teoria da complexidade computacional (Cook, Levin e Karp, anos 70)

– Fortes evidências que milhares de problemas de diversas áreas do conhecimento são intratáveis computacionalmente

Ciência da Computação

Minha Pesquisa

Projetar e analisar algoritmos e técnicas algorítmicas para problemas relevantes que emergem em diferentes áreas do

conhecimento

Minha Pesquisa

• Compressão de Dados

• Sistemas de Diagnóstico

• Tratamento de Informações em Grandes Coleções de Dados

• Transporte em oleodutos

• Desenho de Leilões

Compressão de Dados

CompressorDado Original Dado Comprimido

• Aplicações– Transmissão de dados– Armazenamento de diferentes mídias: som,

imagem, texto e vídeo (gzip,jpeg,mp3)

Tamanho original 769 Kb

Dado Comprimido 49 kb



• Códigos de Huffman

– Técnica fundamental para compressão de dados

– Utilizado em compressão sem perda (texto) e em compressão com perda (som, imagem e vídeos)


• Códigos de Huffman– Associa caracteres mais (menos) frequentes

a códigos com menos (mais) bits

ASCII

A 1000001

B 1000010

.

.

. Z 1000110

Huffman

A 100

B 110001

.

.

. Z 1010110010


• Contribuições – Algoritmos eficientes para construir códigos

de Huffman com restrição de comprimento. • aumenta sensivelmente a velocidade de

decodificação

– Prova de que restringir o comprimento produz uma perda de compressão muito pequena.


• Contribuições

– Análise da taxa de compressão de códigos de Huffman dinâmicos

– Prova da conjectura de J. Vitter (JACM) sobre a taxa de compressão dos códigos de Huffman dinâmicos

• Perda de compressão é de no máximo 2 bits/símbolo


• Principais Publicações– Siam Journal on Computing– Journal of Algorithms– Algorithmica – IEEE Transactions on Information Theory– IEEE Data Compression Conference

• Prêmio– Primeiro prêmio no concurso de teses de doutorado

da Sociedade Brasileira de Computação 2000

Sistemas de Diagnósticos

O paciente tem uma doença Y?Se teste HB1 e

(OU TAC > 70% E histórico familiar )

(OU biopsia E pressão alta )

(OU MRI negativo E teste XK2 positivo )

Então Sim

• Diagnóstico depende de um conjunto de diferentes exames com diferentes custos de realização

Como obter o diagnóstico correto com o menor custo possível ?



Framework• Entrada

– Diagnóstico/função f sobre variáveis x1,...,xn

– Vetor de custos c=(c(x1),,... c(xn)), que define o custo de obter a informação associada a cada variável

• Objetivo – Projetar métodos que permitam determinar o valor

da função f gastando o mínimo possível com a aquisição de informações

• Outras Aplicações– Planejamento estratégico

• Decisão sobre investimento em projeto depende de uma série de informações que têm diferentes custos de aquisição

– Jogos para computadores

– Otimização de consultas em Banco de Dados



• Contribuições

– Metodologia baseada em programação linear que permite projetar e analisar algoritmos eficientes para minimizar o custo de computar diagnósticos

– Caracterização da solução ótima para importantes classes de diagnósticos/funções (e.g. funções booleanas monótonas)

Sistemas de Diagnósticos• Principais Publicações

– ACM Symposium on Theory of Computing – ACM-SIAM Symposium on Discrete Algorithms– European Symposium on Algorithms– ICALP– Journal of ACM (submetido)

Tratamento de Informações em Grandes Coleções de Dados (WWW)

• World Wide Web (WWW)– Conteúdo altamente dinâmico– Usuários com diversos interesses– Dados poucos estruturados– Diferentes formatos

Como encontrar informações de interesse ?


• Taxonomias ( Yahoo!, ODP)– Bastante populares no final da década de 90

• Motores de Busca (MSN,Google,Yahoo!)– Bastante populares atualmente

Como encontrar informações de interesse ?


Política

Economia

Esportes

Basquete

Futebol

Tênis

Seleção Brasileira

Clubes

Brasil

Mundo

InformaçãoInformação


Informação

Informação

Informação

Taxonomia


Como otimizar a taxonomia de modo a minimizar o tempo médio de acesso do usuário a informação desejada ?


Clubes de Futebol

Política

Economia

EsportesBasquete

Futebol

Tênis

Seleção Brasileira

Clubes

Brasil

Mundo



Informação

Informação

Informação


• Contribuições– Métodos que permitem adicionar poucos links

por página e minimizar sensivelmente o tempo de acesso do usuário a informação desejada

– Melhores métodos existentes


• Principais Publicações

– ACM Transactions on Information Systems

– ISAAC

– ALENEX


Criadores de Conteúdo

Consumidores de Conteúdo

Motores de

Busca


• Motores de busca

– Selecionam páginas relacionadas com a consulta do usuário

– Ordenam as páginas selecionadas segundo algum critério de relevância


• Contribuições– Novas métricas para o problema de extração

de detecção de conteúdo relevante– Métodos para extração automática de

conteúdo relevante– Transferência Tecnológica



• Quantidade significativa de conteúdo ‘não relevante ‘ – Estima-se que o volume deste conteúdo represente

entre 40% e 50% do volume total da Web.

• A remoção de conteúdo não relevante melhora a qualidade de tarefas importantes realizadas por máquinas de busca: – detecção de páginas e ranking

Documents

Algoritmos: Teoria e Engenharia Eduardo Sany Laber Departamento de Informática PUC-RIO