RCAAP Repository

O crescimento inexorável do volume de documentos na World Wide Web coloca um grande desafio para as máquinas de busca, não apenas com relação a eficácia as também com relação a eficiência de espaço e de tempo. Esta dissertação apresenta um novo método de compressão com perda (poda) para arquivos invertidos que considera o aspecto eficiência sem desconsiderar a eficácia. O método proposto é baseado na análise de 'logs' de consultas passadas para obter uma grande redução no espaço ocupado pelo índice. O método pode ser utilizado em qualquer máquina de busca para melhorar sua eficiência em termos de tempo de processamento e espaço ocupado pelo índice, praticamente sem perdas na qualidade dos resultados da consulta. Experimentos utilizando uma máquina de busca real mostram que a técnica apresentada reduz os custos de armazenamento do índice em até 50% com relação ao índice sem compressão. Uma consequência dessa redução no tamanho do índice é que o tempo de processamento de uma consulta pode ser reduzido a aproximadamente 45% do tempo original, sem perda na precisão média. Considerando a qualidade do 'ranking' produzido, o espaço ocupado pelo índice e o tempo de resposta a consultas, estudos comparativos com os dois melhores algoritmos de compressão de índices conhecidos na literatura mostram que o algoritmo proposto é bastante competitivo. Por exemplo, tanto a curva de similaridade entre os 'rankings' quanto a precisão média das respostas do algoritmo proposto e o melhor algoritmo dentre os dois considerados na comparação se mantêm aproximadamente iguais para os diferentes níveis de poda. Quanto ao tempo de resposta o algoritmo proposto é mais rápido do que o melhor algoritmo dentre os dois considerados na comparação.

A World Wide Web é hoje um dos maiores repositório de informação existentes e bilhões de páginas web, tratando dos mais variados tópicos, estão ao alcance de pessoas das mais diferentes nacionalidades. Esse conteúdo, porém, é formatado para o consumo humano, e agentes computacionais têm grande dificuldade em acessar e manipular os dados contidos nas páginas da Web. Uma das opções para se contornar esse problema é escrever manualmente extratores para todas as páginas web das quais se deseja extrair dados e,portanto, torná-las adequadas para o consumo por agentes computacionais. Porém, mesmo com o advento de novas ferramentas para geração semi-automática desses extratores, ainda assim não é possível fazer a extração de dados de um grande volume de páginas web, pois, dada a necessidade da intervenção humana, essas ferramentas têm escalabilidade limitada. Esta dissertação apresenta uma nova estratégia para construção de sistemas de extração da dados da Web. Os sistemas criados a partir da estratégia proposta são completamente automáticos e podem ser usados para extração de grandes quantidades de páginas. Em nossos experimentos, realizamos a extração, de forma completamente automática, das notícias de 35 dos principais veículos de comunicação brasileiros, totalizando 4088 páginas, e atingimos um grau de precisão de 87,71%.A chave para obtenção desse resultado é o uso da técnica de distância de edição árvores. Uma vez que páginas Web são árvores serializadas, pode-se usar essa técnica para obter as variações entre as páginas e, então, extrair os dados contidos nestas páginas. Além de uma revisão extensiva do problema de distância de edição em árvores, esta dissertação apresenta um novo algoritmo para o problema. O algoritmo, denominado Restricted Top-Down Mapping, ou simplesmente RTDM, é descrito em detalhes, incluindo pseudo-código, estudo dos limites assintóticos e análise empírica, o que nos levou a conclusão que oalgoritmo supera todos os outros algoritmos, com aplicações a extração de dados da Web, existentes na literatura.

Este trabalho aborda o problema de se estimar o número de peixes que nadam através de mecanismos de transposição, também conhecidos como escadas de peixes. Este mecanismos são construídos com o objetivo de auxiliar os peixes em seus processos migratórios para desova, fenômeno este conhecido no Brasil como Piracema. O sistema de contagem de peixes proposto neste trabalho juntamente com um módulo complementar para classificação das espécies de peixes, compõe um sistema mais amplo cujo objetivo é realizar o monitoramento e a avaliação da eficácia de escadas de peixe. Devido a rica biodiversidade do ecossistema brasileiro, este trabalho representa uma tarefa de grande relevância para o estudo e quantificação dos volumes de espécies de peixes que se encontram em extinção ou ainda que tenham um significativo valor econômico. Diferentemente dos métodos existentes, os quais não fornecem meios adequados para aquisição de informações relevantes sobre espécies diferentes de peixes, tal como suas habilidades de nado, tempos de migração e picos de fluxo, este trabalho apresenta uma abordagem baseada em análise de seqüência de imagens e no uso de um rastreador bayesiano de múltiplos objetos (BraMBLe), a qual permite a realização de um rastreamento mais confiável de peixes mesmo diante de variações ambientais bruscas, como variações de luminosidade e propriedades da água. A direção de migração dos peixes é estimada dividindo a cena em regiões de interesse que são constantemente monitoradas pelo sistema. Nossa metodologia foi validada com sucesso utilizando-se vídeos do mundo real, alcançando uma exatidão de contagem de cerca de 80%.

A mineração de dados é uma área de pesquisa que vem recebendo muita atenção nos últimos anos, pelo seu enorme potencial de extrair informações úteis de grandes volumes de dados. Entretanto, a despeito da sua grande aplicabilidade, as técnicas de mineração de dados ainda não ganharam ampla aceitação entre os usuários leigos, em função principalmente da complexidade dos conceitos envolvidos, que não fazem parte do domínio desses usuários. Uma das mais populares tarefas de mineração de dados é a mineração de regras de associação, que tem aplicação em diferentes contextos, como detecção de fraude em compras públicas, ciências sociais e marketing. A mineração de regras de associação apresenta dois grandes problemas relacionados à interação humana. Em primeirolugar, o volume de regras geradas é muito grande, o que dificulta a identificação das regras mais interessantes. Em segundo lugar, os conceitos relacionados à técnica são complexos, e quando o usuário não consegue compreender esses conceitos, ele não consegue utilizar o sistema de forma satisfatória.Nesta dissertação, abordamos esses dois problemas. Para o problema de identificação das regras mais interessantes, apresentamos duas estratégias de visualização do conjunto de regras geradas. Além disso, mostramos como a segunda estratégia supera a primeira, com base em avaliações com usuários e naliteratura. Para o segundo problema, identificamos, a partir da literatura e da nossa experiência com o sistema Tamanduá, os principais aspectos que devem ser comunicados pelos projetistas de sistemas de mineração de regras de associação aos usuários, de acordo com a teoria da engenharia semiótica. Paracada um dos aspectos levantados, discutimos sua importância para a interação e o custo para o usuário de ele não ser bem comunicado através da interface.

O advento da digitalização transformou o significado de captura, controle, entrega e uso dos recursos de informação na sociedade. Indivíduos, instituições e comunidades são capazes de publicar e disseminar informação sobre seus patrimônios culturais e criar suas próprias bibliotecas digitais, que aumentam o potencial para diversidade, pluralidade de vozes e fortalecimento dessas comunidades. Sistemas hipermídia estão emergindo como uma nova classe de sistemas de informação complexos. Esses sistemas permitem as pessoas criar, anotar, ligar e compartilhar informações de uma grande variedade de mídias, como texto, gráficos, áudio, vídeo, animação e programas. Entretanto, muitas pessoas tendem a pensar que, diferentemente da informação analógica, a informação digital existirá para sempre e não percebem a fragilidade dos documentos digitais. Este trabalho apresenta uma abordagem metodológica para o desenvolvimento de sistemas de informação hipermídia para gerenciamento de acervos multimídia. O trabalho também foca no problema da preservação digital. Um estudo é feito para determinar um fluxo de trabalho (workflow) de digitalização que permita gerar documentos digitais de alta qualidade, tentando minimizar os custos de redigitalização.

O problema de alocação de tripulações em redes de transporte (PAT) é uma tarefa bastante rotineira no contexto de grandes empresas de transporte. Tal atividade envolve, basicamente, subdividir um conjunto de jornadas entre diferentes tripulações respeitando legislações trabalhistas e normas operacionais vigentes e impostas às empresas que atuam nesse setor. Por se tratar de um problema de grande complexidade computacional, o mesmo costuma ser divido em dois subproblemas: problema de recobrimento e problema de seqüenciamento de jornadas. Essa dissertação tem seu foco no Problema de Recobrimento. Além da definição formal do mesmo e de uma revisão da literatura, também são apresentados dois algoritmos para a sua resolução: um algoritmo lagrangeano e um genético. Por fim, resultados computacionais são apresentados com o objetivo de avaliar o desempenho dos algoritmos apresentados. Palavras-chave: Escalonamento de Tripulações, Problema de Recobrimento, Algoritmo Genético, Algoritmo Lagrangeano, Problema de Seqüenciamento de Jornadas.

O problema de sobrecarga informacional gerado pelo sucesso da Web provocou o surgimento de serviços que reúnem informações em contextos específicos, conhecidos como bibliotecas digitais. Bibliotecas digitais reúnem informações digitais e metadados que freqüentemente são obtidos a partir de fontes diversas. A não padronização dos metadados oriundos dessas fontes traz como consequência a ambiguidade em determinados campos. Nesta dissertação apresentamos uma estratégia para o tratamento de ambiguidades encontradas em campos referentes a nomes de autores em bibliotecas digitais. Nossa estratégia utiliza técnicas de recuperação de informação associadas a um algoritmo de agrupamento que permite a criação de arquivos de autoridade. Demonstramos a eficácia de nossa estratégia através da realização de experimentos sobre duas coleções de teste derivadas da Biblioteca Digital Brasileira de Computação (BDBComp) e Digital Bibliography of Library Project (DBLP). Para a coleção da BDBComp, a média entre a qualidade dos grupos gerados e sua fragmentação foi superior à marca de 90%, e para a coleção da DBLP, essa média foi superior a 65%.

A s redes de sensores sem fio (RSSFs) podem ser vistas como um vasto campo para pesquisa e aplicações relacionadas à obtenção, processamento e comunicação de dados. Em RSSF, um problema importante é a comunicação de dados entre um nó sink (nó responsável por coletar dados) e os nós sensores. Baseado em algoritmos de disseminação de dados, o nó sink pode realizar diferentes atividades como alterar o modo de funcionamento da rede (ou de uma parte da mesma), disseminar informações relevantes, ativar/desativar um ou mais nós sensores, e enviar requisições para a rede. Em [17], Haas, Halpern e Li propõem o Gossiping, um protocolo baseado em fofoca para reduzir o overhead em algoritmos de roteamento para redes sem fio. O protocolo consiste em um flooding probabilístico, ou seja, cada nó transmite uma mensagem com uma probabilidade p. O Gossiping apresenta um comportamento distinto em função da densidade da rede e da probabilidade utilizada. Se a rede for esparsa ou probabilidade for pequena, as rotas são quebradas com muita facilidade e poucos nós são cobertos pelo algoritmo. Por outro lado, em redes densas ou quando a probabilidade for suficiente, o protocolo apresenta um desempenho extremamente satisfatório em relação aos números de nós cobertos e de transmissões. Resultados de simulação mostram que para as redes consideradas em [17], a probabilidade p entre 0; 6 e 0; 8 foi suficiente para que praticamente todos os nós fossem cobertos em praticamente todas as disseminações realizadas. Um protocolo de disseminação de dados interessante é o Trajectory Based Forwarding (TBF) no qual pacotes são disseminados pelo nó sink para um conjunto de nós ao longo de uma equação de curva. A idéia principal consisteem inserir uma equação de curva no cabeçalho do pacote a ser disseminado e os nós intermediários propagam esse pacote de forma unicast para os nós que estiverem mais próximos da trajetória. Como a trajetória não especifica explicitamente quais nós farão parte do caminho, observa-se uma certa pendência da topologia da rede. As principais vantagens desse protocolo são a representação compacta e a independência de nós.A informação sobre a quantidade de energia disponível em cada parte da rede é chamada de mapa de energia e ela pode ser explorada pelos algoritmos de disseminação para minimizar o consumo de energia dos nós sensores durante os processos de disseminação de dados. O presente trabalho propõe um protocolo para a disseminação de dados que adapta dinamicamente as rotas de acordo com o nível de energia dos nós sensores. Essa capacidade dinâmica é muito importante em um sistema como as redes de sensores sem fio quedevem possuir a capacidade de adaptarem dinamicamente seus respectivos comportamentos em função dos recursos existentes no ambiente. Em RSSF, um recurso importante é a energia, uma vez que, em geral, as bateria não podem ser recarregadas.A idéia principal da solução proposta é combinar os conceitos da disseminação baseada em trajetória com a informação fornecida pelo mapa de energia para determinar as rotas dinamicamente e, assim, disponibilizar informações para rede toda ou para uma parte da mesma. Resultados de simulação mostram que a energia consumida pelas atividades de disseminação de dados pode ser concentrada em nós com maiores reservas de energia. Osnós com as menores reservas podem utiliza-las para executarem atividades de sensoriamento e para receberem pacotes destinados a eles. Dessa forma, o particionamento da rede devido a falta de energia é adiado e o tempo de vida da rede é estendido.

Ultrapassando a tecnologia embutida de hoje, a próxima geração de micro-sensores irá incorporar a tecnologia sem fio, o que irá permitir que um grande número de pequenos dispositivos de baixo preço sejam conectados, formando as Redes de Sensores Sem Fio (RSSFs), também chamadas de 'poeira inteligente'. Essa tecnologia irá possibilitar novos tipos de computação ubíqüa e ambientes inteligentes.O problema de roteamento em RSSFs é freqüentemente denominado 'disseminação de dados'. Uma técnica interessante de disseminação de dados é a baseada em trajetórias, ou disseminação sobre curvas. A inovação dessa abordagem está na representação de rotas através de funções contínuas, ao invés de conjuntos de pontos discretos. A idéia principal é embutir uma equação de curva no cabeçalho do pacote e deixar que nós intermediários o transmitam para nós próximos à curva. Essa técnica é imune a mudanças na conectividade da rede e é escalável em relação ao tamanho da rede e ao número de nós compondo a rota. A técnica de roteamento sobre curva pressupõe que exista um mecanismo de geração de trajetórias. No entanto, pelo nosso conhecimento, o problema de geração de curvas não possui nenhuma proposta de solução na literatura. Neste trabalho é proposto um método de geração dinâmica de curvas de roteamento baseado no mapa de energia da rede. Os resultados de simulação revelaram que, através da política de geração de curvas proposta, é possível evitar que nós-sensores localizados em regiões de baixa energia gastem suas reservas com atividades de retransmissão de pacotes e se concentrem exclusivamente em tarefas de sensoriamento. Dessa forma, particionamentos da rede podem ser significativamente adiados, e o seu tempo de vida, estendido.

O aumento da criminalidade violenta nos centros urbanos tem sido observado ano após ano. As instituições policiais possuem enormes massas de dados digitalizadas acerca de suas atividades e dos crimes reportadas, porém os dados não são utilizados de forma a obter informações que auxiliem o combate e a prevenção de crimes. Esta dissertação define uma metodologia de tratamento e análise dos dados existentes, propondo estratégias de uso minimizado de recursos para melhor atendimento às solicitações da população. O conhecimento das características de incidência de ocorrências, de acordo com suas naturezas, localizações e momentos de surgimento, promove o desenvolvimento de políticas de prevenção de crimes e de previsão de uso de recursos que atendam à demanda existente. Portanto, a eficiência nos atendimentos reativos leva ao aumento de recursos para as atividades preventivas e maior satisfação da comunidade com os serviços prestados pela polícia. Tais fatores proporcionam maior nível de segurança. Esta dissertação realiza a caracterização espaço-temporal do processo de consumo de recursos dos órgãos reguladores; propõe e avalia o uso de políticas de alocação semicompartilhada de recursos e de despacho de viaturas segundo duração e prioridades dos atendimentos. O objetivo do uso dessas estratégias e propiciar melhor utilização dos recursos policiais para combate eficiente da criminalidade. Para tanto, resulta em um conjunto de ferramentas de obtenção de conhecimento a partir dos dados de ocorrências policiais, e de auxílio às análises sociológicas dos crimes documentados.

Esta dissertação apresenta o MultiMAD (Multimodel Mobile Application Development Tool, Ferramenta Multimodelo de Desenvolvimento de Aplicações para Dispositivos Móveis), uma ferramenta de desenvolvimento rápido especializada em dispositivos móveis. Ela provê uma interface gráfica na qual uma aplicação é descrita a partir de blocos de construção que podem ou não ser específicos para um determinada plataforma de aplicações móveis. Isto permite que aplicações possam ser desenvolvidas para diversas plataformas utilizando todos os seus recursos, característica não encontrada na quase totalidade das outras ferramentas similares. Quando esta descrição está pronta, o usuário a submete para um gerador de aplicações que irá gerar parcialmente, de forma automática, código-fonte e outros arquivos que eventualmente façam parte da implementação da aplicação. Atualmente, o MultiMAD gera código-fonte que implementa a interface gráfica de usuário e o relacionamento entre seus elementos, possibilitando que o desenvolvedor possa focar seus esforços na lógica da aplicação. O MultiMAD também é uma ferramenta de prototipagem rápida, já que ele também gera um protótipo de implementação da lógica e, por conseqüência, gera um protótipo de aplicação compilável e testável sem que o usuário tenha que escrever uma única linha de código ou tenha que sair da ferramenta. Este protótipo de implementação é o ponto de partida da implementação definitiva da lógica da aplicação. Foram implementados geradores para as plataformas Wireless Application Protocol (WAP) 1.1 e2.0 e Java 2 Micro Edition (J2ME). Também é proposto o MobileVC, uma arquitetura especialmente criada para aplicações para dispositivos móveis.

O tráfego devido a aplicações P2P tem aumentado consideravelmente nos últimos anos e, apesar de ser hoje o responsável pela maior parte de todo o tráfego da Internet, não existem muitas ferramentas que auxiliem na monitoração e portanto no entendimento desse tráfego, tanto sob um ponto de vista acadêmico como sob um ponto de vista prático. Nesse trabalho abordamos as dificuldades em se construir umasolução que viabilize a análise e a caracterização de tráfego de aplicações em tempo real, tendo como foco principal as aplicações P2P de troca de arquivo e propomos o 'Palantír', uma sistema de monitoração passiva com recuperação de estado em tempo real de tráfego em enlaces de alta-velocidade.Esse sistema é capaz de, além da monitoração, realizar a remontagem dos arquivos trocados no tráfego monitorado. Mesmo à velocidade de 500 Mbps, considerada alta para os objetivos propostos, o sistema trabalha com uma taxa de perda de pacote da ordem de 3,3 % e um desempenho 99 % superior ao que poderia ser obtido utilizando abordagens tradicionais. Mesmo operando nessa condição de cargaextrema, o sistema ainda é capaz de recuperar 70 % dos dados observados nos nossos experimentos, um valor que é mais de 100 vezes superior ao que pode ser obtido utilizando-se um sistema não otimizado. Além disso, identificamos que dos principais pontos de contenção no processo de coleta deve-seao custo da passagem dos dados através da fronteira do sistema operacional entre o modo usuário e o modo protegido do 'kernel'.Apresentamos um estudo de caso onde analisou-se e caracterizou-se, usando o 'Palantír', o tráfego associado a dois sistemas P2P em um provedor de acesso a Internet de banda larga por um período de aproximadamente 10 dias. A análise dos resultados obtidos a partir desses esforços nos permitiu observar que existe uma significativa diferença tanto na natureza do tráfego gerado pelos usuários dos dois sistemas como dos recursos trocados nas duas redes.

A maioria das pesquisas feitas sobre calibração de fontes de luz pontuais baseiam-se no modelo de fontes distantes, isto é, se propõem a determinar a direção de um iluminante localizado a uma distância infinita da cena. Esse modelo é conveniente principalmente para as aplicações baseadas na iluminação solar, mas revela-se inadequado quando os iluminantes estão em uma distância relativamente próxima da cena - situação comum em ambientes fechados, onde geralmente a claridade parte de um conjunto de lâmpadas localizadas a poucos metros do observador. Este trabalho apresenta uma nova abordagem para a calibração de fontes de luz cuja principal vantagem está em considerar que as fontes pontuais são próximas (não distantes).Assim, o objetivo da calibração é recuperar não a direção, mas as coordenadas tridimensionais do ponto emissor de luz. O método proposto não faz qualquer restrição sobre as características das superfícies dos objetos, requer um conjunto mínimo de informações sobre a cena e é estatisticamente ótimo, no sentido de considerar as métricas de erro baseadas em um modelo realístico de propagação de ruídos. Em paralelo, o método também é capaz de realizar a reconstrução parcial da geometria da cena: são claculadas as coordenadas tridimensionais de alguns pontos-chave dos objetos, como extremidades e vértices. Os testes realizados, tanto com simulações em computador quanto com cenas reais, comprovam a eficácia do método mesmo na presença de ruídos significativos. Alémdisso, o tempo requerido para a solução de uma instância do problema - na ordem de décimos de segundo, utilizando um computador pessoal comum - sugere que o método poderá ser utilizado em aplicações de tempo real.

Esta tese aborda o problema de se estimar o alinhamento espaço-temporal entre N sequências de vídeo não-sincronizadas referentes à mesma cena dinâmica 3D e capturadas a partir de pontos de vista distintos. Diferentemente dos métodos existentes, os quais funcionam somente para N = 2, este trabalho apresenta uma abordagem inovadora que reduz o problema caracterizado por um N qualquer ao problema de se estimar uma única reta em RN. Esta reta captura todas as relações temporais entre os videos, podendo ser calculada sem qualquer conhecimento a priori sobre as mesmas. Considerando que o alinhamento espacial é capturado por parâmetros de tensores bilineares (matrizes fundamentais), um algoritmo iterativo é usado para refinar simultaneamente os parâmetros temporais e espaciais que definem o alinhamentoentre as sequências, uma vez que o refinamento exclusivo dos parâmetros temporais é subótimo. Resultados experimentais obtidos com sequências de vídeo reais demonstram que a metodologia proposta é capaz de recuperar eficazmente o alinhamento entre as sequências mesmo diante da existência de grandes desalinhamentos, diante da presença de ambiguidades (por exemplo, cenas com movimentos periódicos) e quando um alinhamento manual preciso é inviável. Finalmente, experimentos com sequências sintéticas demonstram a escalabilidade e acurácia de nossa abordagem, fornecendo medidas quantitativas para a qualidade dos alinhamentos estimados.

O Problema de Roteamento de Veículos com Janela de Tempo (PRVJT) estático é um dos problemas bem conhecidos em otimização combinatória que mais tem recebido atenção nos últimos anos. O objetivo do problema é planejar rotas para uma frota de veículos, sem violação das restrições de tempo e capacidade, minimizando custos. Os custos normalmente estão relacionados à distância total percorrida, ao número de veículos necessário ao atendimento, ao tempo total de espera dos veículos nos consumidores ou à combinação destes. O Problema de Roteamento de Veículos Dinâmico com Janela de Tempo (PRVDJT), por outro lado, é uma generalização do anterior onde parte das informações relevantes são conhecidas somente após o início do processo de otimização.Métodos exatos têm sido normalmente propostos para a versão estática do PRVJT. Melhores resultados com este tipo de método têm sido possível devido ao uso de modernas técnicas de planos de corte (branch-and-cut) e implementações paralelas. Entretanto, 23 dos 56 problemas de Solomon continuam em aberto. Adicionalmente, em muitos casos um tempo proibitivo é necessário para encontrar a solução exata. Muitas heurísticas têm sido desenvolvidas para possibilitar uma solução de boa qualidade dentro de um intervalo aceitável de processamento. Utilizando a distância total percorrida como único objetivo, uma abordagem híbrida é proposta neste trabalho para o PRVJT, utilizando um eficiente algoritmo genético combinado com uma formulação do problema por particionamento de conjunto. Testes foram realizados utilizando cálculos com dupla precisão e com inteiros, possibilitando comparar os resultados com aqueles anteriores, gerados por métodos exatos e heurísticas. Os resultados computacionais mostram que a heurística proposta supera todas as anteriores em termos de distância total percorrida. Os resultados utilizando cálculos com inteiros também são muito competitivos, comparados aos ótimos conhecidos na literatura.Entretanto, a maioria das heurísticas utilizam a redução do número de veículos como primeiro objetivo e a distância total percorrida somente como segundo, sujeito ao primeiro. Uma fase adicional foi então proposta minimizando o número de veículos. Uma seleção baseada em um processo de torneio utilizando critérios hierárquicos foi proposta para o algoritmo genético. Todos os melhores resultados da literatura em termos de número de veículos para as instâncias de Solomon foram alcançados. Depois de minimizado o número de veículos, a proposta inicial para minimização de distância é utilizada, sob uma população de indivíduos solução com número de veículos reduzido.Finalmente, a proposta é aplicada ao problema dinâmico, onde parte dos consumidores são incluídos ou cancelados após o início do processo de otimização. As instâncias de Solomon foram modificadas, possibilitando considerar vários graus de dinamismo. Com resultados desejados para o problema dinâmico, foi possível avaliar a qualidade dos resultados alcançados na proposta para o PRVDJT. Os resultados foram significativos, e mostram que o algoritmo proposto é superior àqueles do tipo re-otimização.

Nos últimos anos o grande desenvolvimento dos sistemas de comunicação e a miniaturização e evolução tecnológica dos sistemas de hardware permitiram o desenvolvimento de novas aplicações. A área de redes de sensores é uma destas novas aplicações. As aplicações em rede de sensores se caracterizam pela presença de inúmeros sensores (nodos) de uma rede de comunicação sem fio, com limite de alcance do sinal e limitação de fonte de energia, pôr serem operados a bateria. Estes sensores têm capacidade de detectar ou medir algum fenômeno da natureza, processar e transmitir os dados ou a informação para outros sensores (nodos) até chegar em um ponto desta rede de tomada de decisão. Trata-se então primordialmente de um sistema distribuído com sérias restrições para implementação. O desenvolvimento destas aplicações exige os desenvolvimento de técnicas de tolerância à falhas e adaptação a novas condições ambientais com a finalidade de que o tempo de vida do sistema seja o mais longo possível. Diversos autores têm trabalhado no desenvolvimento de sistemas que suportem estas características. Alguns trabalhos estão na área de 'middleware' e outros na área de desenvolvimento de aplicações. Poucos autores têm se preocupado com a interface aplicação- 'middleware'. Nos últimos anos a área de fusão de dados também tem tido um grande crescimento pelas novas exigências das aplicações que estão sendo criadas e pelo aprimoramento e desenvolvimento de novas técnicas estatísticas e de inteligência artificial. Entretanto, pouco tem sido feito na área de arquitetura de fusão de dados, e na sua implementação em redes de sensores. Além disto, a interface aplicação -middleware nos parece ser altamente dependente da implementação de fusão de dados e de sua arquitetura. O presente trabalho se propõe a estudar o problema de como implementar fusão de dados em rede de sensores, levando em consideração a adaptação à falhas e mudanças no ambiente monitorado. Estes aspectos são determinantes para que o sistema possa degradar progressivamente, mas mantendo as necessidades exigidas pela aplicação (qualidade de serviço). Neste sentido, o presente trabalho propõe uma nova arquitetura de fusão de dados, dinâmica e adaptável a diferentes sistemas, sejam eles distribuídos ou centralizados e independente de contexto. Além disto, o desenvolvimento de um software para implementação centralizada e distribuída desta arquitetura associada ao desenvolvimento de uma linguagem para comunicação aplicação -'middleware' pôr meio da fusão de dados, vem completar o que achamos ser necessário para o desenho e desenvolvimento de uma aplicação em rede de sensores. Todas estas ferramentas também são importantes contribuições para a área de fusão de dados e redes de sensores. Como prova de conceito, desenvolvemos uma aplicação (protótipo) centralizada de um monitor multiparamétrico móvel para monitoração da freqüência cardíaca e simulamos uma implementação de fusão de dados em rede de sensores distribuída no corpo humana. Esta aplicação demonstrou ser uma importante contribuição na área de diagnóstico precoce e prevenção de enfermidades cardiovasculares.

Esta tese trata do problema de adquirir os modelos de uma cena a partir de imagens, onde a correspondência entre as intensidades dos pixels das imagens e as cores reais da cena não podem ser explicadas a partir de um modelo de iluminação local da interação da luz com a cena. Mais especificamente, o problema é abordado em dois casos particulares tratados em cenários distintos.No primeiro caso, têm-se cenas submersas em água turva onde a luz interage globalmente com o meio, ao qual é desenvolvida uma metodologia para extrair a geometria da cena, utilizando-se um modelo de propagação da luz na água integrado a um algoritmo de visão estéreo, recuperando o mapa de disparidades a partir de um par estéreo da cena adquirido em pontos de vista distintos. Resultados experimentais comparam favoravelmente o método proposto nesta tese a um método de estéreo denso bem estabelecido. O método permite, ainda, restaurar as imagens da cena subaquática.No segundo caso, têm-se cenas onde a luz interage globalmente com objetos com superfícies homogêneas, reflexivas e translúcidas, apresentando sombras e inter-reflexão entre objetos, ao qual é desenvolvido um método para adquirir os parâmetros de um modelo de reflectância de cada objeto da cena, resolvendo um sistema de equações fatorado obtido a partir de uma única renderização e tendo como restrições uma imagem da cena, cuja solução é mais estável e eficiente em comparação a métodos similares.

Neste trabalho, propomos uma modelagem que combina representações explícitas e simbólicas em um modelo de verificação formal explícito-simbólico. Os modelos explícitos e simbólicos têm sido usados com sucesso na verificação de sistemas concorrentes de estados finitos, como circuitos sequenciais complexos e protocolos de comunicação. A modelagem proposta tem como objetivo combinar as técnicas explícitas e simbólicas para verificação de um mesmo modelo e permitir o emprego da técnica mais eficiente à verificação de cadaaspecto do modelo. Inicialmente, apresentamos uma visão geral do processo de verificação do modelo de um sistema e discutimos como propriedades temporais podem ser especificadas para este modelo. A discussão é focalizada em lógica temporal CTL, mas também consideramos a lógica temporal LTL. Em seguida, introduzimos os modelos explícitos e seus algoritmos básicos. As principais técnicas de refinamento dos verificadores de modelos explícitos são apresentados, tais como redução de ordem parcial, bit-state hashing, automatosminimizados, compressão de vetores de estados e análise estática. Discutimos, também, a verificação de modelos simbólicos e os diagramas de decisão binária. Caracterizações em ponto fixo são dadas para as versões simbólicas dos algoritmos de verificação de modelos.Apresentamos a linguagem de descrição do verificador de modelos explícito-simbólico, o Interchange Format [Bozga et al., 1999] desenvolvido nos laboratórios Verimag. Com isso, concluímos a apresentação dos conceitos básicos necessários à introdução da modelagem explícito-simbólica. A concepção do modelo combinado explícito-simbólico e algoritmos relacionados é a base teórica de nosso trabalho. Adaptamos descrições em Interchange Format à modelagem teórica do modelo combinado. Após isso, discutimos a implementaçãodo verificador de modelos explícito-simbólico, trazendo informações sobre suas estruturas de dados mais importantes e o processo geral de verificação, desde a coleta de símbolos até a construção do modelo combinado. Finalmente, mostramos resultados experimentais e sugerimos trabalhos futuros.

Neste trabalho apresentamos uma nova abordagem para a ordenação de documentos a partir do modelo de espaço vetorial. A sua originalidade apresenta-se em dois pontos principais: Primeiro, padrões de correlação entre os termos são levados em consideração e processados de forma eficiente. Segundo, a ponderação dos termos é baseada em uma técnica de mineração de dados chamada de regras de associação. A partir desses pontos definimos um novo mecanismo de ordenação chamado modelo de espaço vetorial baseado em conjuntos. Os componentes desse modelo deixam de ser os termos, e passam a ser os conjuntos de termos. Os conjuntos de termos capturam a intuição que termos semanticamente relacionados aparecem próximos em um documento. Esses conjuntos podem ser eficientemente gerados limitando sua computação a pequenos trechos de texto. Uma vez computados os conjuntos de termos, a função de ordenação é calculada a partir da freqüência de um conjunto no documento e sua raridade na coleção. Nossa abordagem provê uma forma simples, efetiva, eficiente e parametrizada para o processamento de consultas disjuntivas, conjuntivas, por frases, além de ser usada para a estruturação automática de consultas. Todas as abordagens conhecidas que levam em consideração a correlação entre os termos foram projetadas somente para o processamento de consultas disjuntivas. Resultados experimentais mostram que o nosso modelo aumenta a precisão média para todas as coleções e tipos de consultas avaliados, mantendo o custo computacional adicional aceitável. Para a coleção TREC-8 de 2 gigabytes, a utilização do nosso modelo implica em um ganho de precisão média de 14.7% e 16.4% para consultas disjuntivas e conjuntivas, respectivamente, em relação ao modelo de espaço vetorial padrão. Esses ganhos aumentam para 24.9% e 30.0%, respectivamente, quando a informação de proximidade é levada em consideração. Os tempos de processamento das consultassão maiores, mas continuam comparáveis com os tempos obtidos para o modelo de espaço vetorial (o crescimento no tempo médio de processamento varia de 30% a 300%). Os resultados experimentais também mostram o sucesso do nosso modelo para a estruturação automática de consultas. Por exemplo, utilizando a TREC-8, nosso modelo gera ganhos de precisão média de aproximadamente 28\% em comparação com o mecanismo de ordenação baseado na fórmula de ponderação BM25. Nossos resultados sugerem que a fórmula de ordenação do modelo de espaço vetorial baseado em conjuntos é bastante efetiva e computacionalmente viável para coleções genéricas.

Uma referência espacial indireta é qualquer elemento textual capaz de identificar um lugar sem fazer uso explícito de suas coordenadas geográficas. Nomes de lugares, endereços, códigos postais e números de telefone são alguns exemplos de referências espaciais indiretas. Um gazetteer é um dicionário de nomes de lugares. Sua utilidade é informar a localização geográfica de referências espaciais indiretas. Nos últimos anos, alguns gazetteers digitais têm surgido com o objetivo principal de apoiar atividades nas áreas de recuperação de informação geográfica e georreferenciamento de dados. Esta dissertação apresenta o Locus, um sistema de localização através de referências espaciais indiretas. O Locus é fundamentado em um gazetteer digital, cuja modelagem seguiu os conceitos definidos em uma ontologia, a ontologia de lugar. Essa metodologia de desenvolvimento resultou na construção de um gazetteer mais elaborado e poderoso que os disponíveis atualmente. Na formação do conteúdo inicial do Locus, foram utilizadas fontes de dados urbanos, regionais e nacionais, obtidos em organizações de natureza bastante diversa, como os Correios, a ANATEL, o IBGE e a Prefeitura de Belo Horizonte. A esses dados foram acrescentados 29.139 nomes de lugares obtidos diretamente a partir da Internet, usando um mecanismo de coleta baseado em exemplos. Esta dissertação inclui uma avaliação do potencial de uso do Locus em uma aplicação de recuperação de informação geográfica, e propõe aplicações do localizador em diferentes áreas, tanto por meio de uma interface interativa quanto através de Web services.