View
114
Download
4
Category
Preview:
Citation preview
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
Compressão de Dados
Compressão de Dados
• 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)
Compressão de Dados
• 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
Compressão de Dados
• 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.
Compressão de Dados
• 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
Compressão de Dados
• 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 ?
Sistemas de Diagnósticos
Sistemas de Diagnósticos
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
Sistemas de Diagnósticos
Sistemas de Diagnósticos
• 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 ?
Tratamento de Informações em Grandes Coleções de Dados (WWW)
• 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 ?
Tratamento de Informações em Grandes Coleções de Dados (WWW)
Política
Economia
Esportes
Basquete
Futebol
Tênis
Seleção Brasileira
Clubes
Brasil
Mundo
InformaçãoInformação
InformaçãoInformação
Informação
Informação
Informação
Taxonomia
Tratamento de Informações em Grandes Coleções de Dados (WWW)
Como otimizar a taxonomia de modo a minimizar o tempo médio de acesso do usuário a informação desejada ?
Tratamento de Informações em Grandes Coleções de Dados (WWW)
Clubes de Futebol
Política
Economia
EsportesBasquete
Futebol
Tênis
Seleção Brasileira
Clubes
Brasil
Mundo
InformaçãoInformação
InformaçãoInformação
Informação
Informação
Informação
Tratamento de Informações em Grandes Coleções de Dados (WWW)
• 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
Tratamento de Informações em Grandes Coleções de Dados (WWW)
• Principais Publicações
– ACM Transactions on Information Systems
– ISAAC
– ALENEX
Tratamento de Informações em Grandes Coleções de Dados (WWW)
Criadores de Conteúdo
Consumidores de Conteúdo
Motores de
Busca
Tratamento de Informações em Grandes Coleções de Dados (WWW)
• 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
Tratamento de Informações em Grandes Coleções de Dados (WWW)
• 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
Tratamento de Informações em Grandes Coleções de Dados (WWW)
Tratamento de Informações em Grandes Coleções de Dados (WWW)
• 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
Recommended