RCAAP Repository

Uma função hash perfeita (FHP) h : S ? [0, m - 1] para um conjunto de chaves S ? U de tamanho n, onde m = n e U é um universo de chaves, é uma função injetora que mapeia as chaves de S para valores únicos. Uma função hash perfeita mínima (FHPM) é uma FHP com m = n, o menor intervalo possível. Funções hash perfeitas mínimas são amplamente utilizadas para armazenamento eficiente e recuperação rápida de itens de conjuntos estáticos, como palavras em linguagem natural, palavras reservadas em linguagens de programação ou sistemas interativos, URLs (universal resource locations) em máquinas de busca, ou conjuntos de itens em técnicas de mineração de dados. Nesta tese nós apresentamos um algoritmo de hashing perfeito altamente escalável e de espço quase ótimo. A avaliação de uma FHP sobre um dado elemento de S requer tempo constante, e a fase dominante no algoritmo de construção consiste da ordenação de n fingerprints de O(log n) bits em tempo O(n). A utilização de espaço depende da relação entre m e n. Para m = n a utilização de espaço está dentro do intervalo 2,62n à 3,3n bits, dependendo das constantes envolvidas nas fases de construção e avaliação. Para m = 1,23n a utilização de espaço está dentro do intervalo 1,95n à 2,7n bits. Em todos os casos, isto está distante por um pequeno fator constante do mínimo teórico de aproximadamente 1,44n bits para FHPMs e 0,89n bits para FHPs, uma coisa que nãofoi alcançada por algoritmos anteriores, exceto assintóticamente para valores de n muito grandes. Esta pequena utilização de espaço permitiu o uso de FHPMs em aplicações para as quais elas não eram úteis no passado.Nós demonstramos a escalabilidade do nosso algoritmo ao construir uma FHPM para um conjunto de 1,024 bilhões de URLs da World Wide Web de tamanho médio igual a 64 caracteres em aproximadamente 50 minutos, usando um PC comodite. Nós também apresentamos uma implementação paralela do algoritmo, a qual gera uma FHPM para o mesmo conjunto de URLs, usando um cluster de 14 computadores, em aproximadamente 4 minutos, alcançando um speedup quase linear. Além disso, para 14,336 bilhões de números inteiros de 16 bytes gerados aleatoriamente e distribuídos entre as 14 máquinas participantes, o algoritmo gera uma FHPM em aproximadamente 50 minutos, com uma degradação de desempenho de 20%.

Neste trabalho é realizado um estudo sobre o problema da geração de trajetórias para veículos aéreos autônomos não-tripulados. O objetivo principal é prover ferramentas de planejamento para robôs aéreos, levando em conta algumas de suas principais restrições físicas de movimento. Para isso, são discutidas inicialmente algumas das técnicas mais utilizadas para o planejamento de movimento de robôs autônomos terrestres, cujo espaço de navegação é bidimensional. Duas técnicas em especial (o \textit{Dubins' Path} e o Hodográfico Pitagoreano) são analisadas em detalhes, uma vez que essas levam em consideração as principais restrições cinemáticas estudadas neste trabalho. O foco principal deste texto é a geração de trajetórias no espaço tridimensional, e por isso, são analisadas também algumas das técnicas mais recentemente utilizadas para esse fim. Duas novas abordagens são propostas neste trabalho. A primeira constitui uma extensão do caminho ótimo de \textit{Dubins} para o espaço 3D. A segunda promove a unificação das duas técnicas citadas anteriormente para o caso 2D, visando produzir curvas no espaço que sejam realizáveis por um veículo aéreo específico. Descreve-se ainda neste trabalho, a implementação de um sistema \textit{Hardware-in-the-Loop}, utilizado para a realização de testes com o intuito de validar as metodologias propostas. Esse sistema utiliza um simulador de vôo como plataforma virtual para o estudo dos módulos de controle e planejamento de veículo aéreo autônomo real. Tais módulos são implementados em um computador de bordo, que por sua vez é conectado ao simulador de vôo via interface de rede. Assim, um modelo (matemático) aerodinâmico de um veículo virtual é utilizado como aeronave de testes para as tarefas de navegação e planejamento de trajetórias no \textit{hardware} embarcado. Outros testes são ainda realizados utilizando-se o modelo matemático de um robô aéreo real desenvolvido pela Universidade Federal de Minas Gerais.

Para produzir softwares de qualidade, de uma forma eficiente, é necessário um reuso sistemático de modelos, desenhos e implementações que tenham sido previamente testados. Dentre as principais formas de reuso, destacam-se os arcabouços de software (ou frameworks). Estes, combinando reuso de desenho com reuso de código, representam o estado da arte em termos de reutilização em softwares orientados a objetos. Este trabalho apresenta o Crux, um arcabouço criado para auxiliar o desenvolvimento de aplicações no domínio da Web. Estas aplicações são sistemas distribuídos complexos que estão crescendo em número e em importância, tornando-se, para muitas empresas, um recurso chave para realizar seus negócios. O Crux visa auxiliar a criação de interfaces ricas, oporcionando uma maior qualidade de interação para os usuários e um modelo de desenvolvimento mais simples para os desenvolvedores.

Avanços em técnicas de compressão, diminuição no custo de armazenamento e transmissões em grande velocidade, têm facilitado a forma como os vídeos são criados, armazenados e distribuídos. Devido ao aumento na quantidade de dados dos vídeos distribuídos e usados em diversas aplicações, tais como máquinas de busca e bibliotecas digitais, estes se destacam como um tipo de dado multimídia, introduzindo, porém, a necessidade de um gerenciamento mais eficiente destes dados. Tudo isto tem aberto o caminho para novas áreas de pesquisa, tal como a sumarização automática de vídeos. Basicamente, esta área consiste em gerar pequenos resumos de vídeos, que são classificados em dois tipos: resumo estático (conjunto de quadros-chave) ou resumo dinâmico (conjunto de segmentos do vídeo). Neste trabalho, é apresentada uma metodologia para a elaboração automática de resumos estáticos de vídeos. O método é baseado na extração das características de cor dos quadros do vídeo e na classificação não-supervisionada destes. Os resumos produzidos são avaliados através de usuários e comparados com abordagens da literatura pesquisada. A solução proposta apresentou, com um nível de confiança de 98%, resultados com qualidade superior em relação às abordagens comparadas.

Em problemas de alocação de tripulação, a cada membro da tripulação é designada uma jornada de trabalho, composta por uma seqüência de viagens a serem cobertas. O objetivo é selecionar as jornadas de forma a cobrir todas as viagens com custo operacional total mínimo. Embora haja várias restrições na combinação das viagens para a formação de uma jornada de trabalho, a quantidade total de jornadas viáveis possíveis é geralmente muito grande. Para instâncias pequenas é possível enumerar todas as jornadas viáveis, e encontrar a solução ótima resolvendo-se um problema de particionamento ou de cobrimento de conjuntos. Mas esta abordagem exata consome bastante tempo e memória para instâncias baseadas em dados reais. Por outro lado, soluções heurísticas podem se perder no grande espaço de soluções. Já que a solução ótima geralmente contém apenas um número bastante reduzido de jornadas, o método de geração de colunas parece ser a opção ideal. O problema é então decomposto em um problema mestre e um subproblema, responsáveis respectivamente por selecionar o melhor conjunto de jornadas, e gerar novas jornadas. O foco principal deste trabalho é a solução do subproblema, pois embora ambos sejam NP-hard, o problema mestre pode ser rapidamente resolvido pelos atuais pacotes de programação linear inteira, desde que o número de jornadas consideradas não seja grande, o que normalmente acontece quando se usa geração de colunas. Neste trabalho são usadas uma heurística gulosa e as meta-heurísticas Grasp e Genético para acelerar a geração de colunas, assegurando-se a otimalidade da solução combinando essas heurísticas com programação linear inteira. São reportados resultados computacionais para dados da literatura e de instâncias reais, mostrando que esse método híbrido pode resolver de forma exata problemas de alocação de tripulação mais rapidamente que utilizando-se apenas métodos exatos.

Mineração Web pode ser vista como o processo de encontrarpadrões na Web por meio de técnicas de mineração de dados.Mineração Web é uma tarefa computacionalmente intensiva, e amaioria dos softwares de mineração são desenvolvidosisoladamente, o que torna escalabilidade e reusabilidadedifícil para outras tarefas de mineração. Mineração Web é umprocesso iterativo onde prototipagem tem um papel essencialpara experimentar com diferentes alternativas, bem como paraincorporar o conhecimento adquirido em iterações anteriores doprocesso. O objetivo desta tese é o desenvolvimento de ummodelo para prototipagem rápida em mineração Web, chamado WIM -Web Information Mining. A principal motivação para desenvolvero WIM é o fato de que seu modelo conceitual provê os seususuários com um nível de abstração apropriado para prototipageme experimentação durante a tarefa de mineração.WIM é composto de um modelo de dados e de uma álgebra. O modelode dados WIM é uma visão relacional dos dados Web. Os trêstipos de dados existentes na Web, chamados de conteúdo, deestrutura e dados de uso, são representados por relações. Osprincipais componentes de entrada do modelo de dados WIM são aspáginas Web, a estrutura de hiperlinks que interliga as páginasWeb, e os históricos (logs) de consultas obtidos de máquinas debusca da Web. A programação WIM é baseada em fluxos de dados(dataflows), onde sequências de operações são aplicadas àsrelações. As operações são definidas pela álgebra WIM, quecontém operadores para manipulação de dados e para mineração dedados. WIM está implementado contendo uma linguagem deprogramação declarativa provida por sua álgebra. A arquiteturado software WIM é apresentada, juntamente com suas questões deimplementação, e projetos de arquiteturas alternativas sãodiscutidos, sobre o qual uma versão futura do software WIM paraescala industrial poderia ser implementada.WIM é aplicado a um conjunto de cinco casos de uso reais emmineração Web, como uma maneira de demonstrar os recursos doWIM. O principal caso de uso, chamado Árvores Genealógicas naWeb, é um estudo de como o conteúdo da Web evolui com o tempo.Esse caso de uso foi escolhido para realização de uma análisecompleta dos resultados, os quais apresentam evidências de queparte dos usuários editores de conteúdo na Web realizamconsultas em máquinas de busca para encontrar conteúdo e entãorepublicar o que foi encontrado como resultado de consulta. Aconclusão é que máquinas de busca influenciam o conteúdo daWeb. A experimentação do WIM nos cinco casos de uso mostrou queo seu uso facilita significantemente a prototipagem rápida emmineração Web. O uso experimental da linguagem de programaçãoWIM mostrou que ela reduz o tamanho do código escrito para umaaplicação em ordens de magnitude, quando comparada comimplementações isoladas.

Redes de sensores sem fio (RSSF) estão mais sujeitas à ação de um inimigo que as redes convencionais devido às suas limitações de hardware e de energia e devido ao ambiente hostil em que podem ser inseridas. Esse cenário é muito favorável aos ataques de negação de serviço, especialmente na função de roteamento, que é crítica em uma rede. Este trabalho está focalizado na proteção do roteamento em RSSF. Para tanto apresenta um estudo sobre a segurança nas RSSF com enfoque no roteamento e propõe uma arquitetura de gerenciamento que possibilita estender o tempo de vida da rede pelo uso racional das diversas soluções de segurança e dois mecanismos de segurança. O primeiro mecanismo apresentado é um protocolo de estabelecimento de chaves proposto para que nós sensores vizinhos utilizem algoritmos criptográficos com o objetivo de garantir o controle de acesso no enlace, inibindo a presença de nós intrusos à rede. O segundo mecanismo é um algoritmo de roteamento com rotas alternativas para aumentar a resiliência da rede à presença de intrusos e, ainda, possibilitar a detecção de nós intrusos que estejam promovendo ataques de negação de serviço no roteamento. A arquitetura de gerenciamento de segurança apresentada possibilita que os mecanismos de segurança sejam usados apenas quando necessário, evitando, assim, um consumo desnecessário de energia quando não existe a presença de intrusos. Esse trabalho avalia o custo computacional, o consumo de energia, a eficácia e a escalabilidade das soluções apresentadas, indicando sua viabilidade para RSSF. Também são avaliados os impactos dos ataques e a eficácia dos mecanismos propostos para a defesa da rede contra os ataques. Os resultados indicam que a solução tem escalabilidade, é eficaz e o consumo adicional de energia pelas soluções apresentadas não afetam significativamente o tempo de vida da rede.

Os circuitos integrados encontram-se cada dia mais presentes em nossas vidas. Dos celulares que falamos aos carros que dirigimos, em quase todos os momentos é possível encontrarmos um dispositivo eletrônico em ação. Isto gera uma crescente demanda por circuitos mais ágeis e compactos, fazendo com que estes se tornem complexos e caros. Uma parte considerável do tempo e dinheiro dedicados ao projeto e desenvolvimento de circuitos é destinado a verificar a presença de erros dos mesmos. A verificação de equivalência entre dois circuitos combinacionais é uma das técnicas mais utilizadas atualmente para verificar se, dadas as mesmas entradas para dois circuitos combinacionais, em qualquer estágio do projeto, eles geram saídas equivalentes. Por ser um tema atual, diversas abordagens têm sido propostas no intuito de aumentar a capacidade de verificar circuitos cada vez maiores em um menor espaço de tempo, entretanto nenhuma obteve notório sucesso quando os circuitos são dissimilares. Este trabalho apresenta e analisa metodologias para o reaproveitamento das cláusulas de conflito entre partições adjacentes durante a verificação de equivalência entre dois circuitos combinacionais dissimilares particionados, utilizando resolvedores SAT.

Esse trabalho aborda um estudo sobre o método de iluminação global conhecido como radiosidade, num esforço de obter uma implementação eficiente para determinar a mesma. A radiosidade é um método clássico e muito importante para a computação gráfica ao sintetizar imagens foto-realísticas, pois foi um dos primeiros a considerar informações de vários objetos para determinar a iluminação de uma cena. Como o método apresenta uma grande demanda de processamento, foi utilizada a GPU como forma de otimização, pois a mesma possui uma capacidade de processamento massivo considerável.Foram realizadas duas implementações distintas que utilizam-se da GPU para acelerar alguma parte ou todo o algoritmo. Como resultado, foram comparados diferentes métodos para resolver sistemas de equações lineares em ambos, GPUs e CPUs, e propusemos uma abordagem para melhorar a determinação de visibilidade da implementação relacionada à GPU.

A predição do tempo de execução de jobs para recursos de grades computacionais (grid) é uma dado importante para escalonadores e brokers. As grades computacionais, por configurarem ambientes compostos por diversos e diferentes recursos e usuários, com diferentes tipos de jobs, não seguindo um padrão para sua submissão, tornam a predição do tempo de execução de jobs um grande desafio. Neste trabalho abordamos o problema de predição do tempo de execução de jobs para recursos não dedicados. Para tratar deste problema baseamo-nos em uma metodologia proposta no trabalho de tese de doutorado de Lílian Noronha Nassif, chamada PredCase, que se mostrou eficiente para predição do tempo para recursos dedicados. Em nosso método, chamado NdrPredCase, utilizamos casos passados de execução de jobs para calcular a predição do tempo de execução para um novo job, como é feito no PredCase. A partir do paradigma de Raciocínio Baseado em Casos (RBC) desenvolvemos as fases do NdrPredCase: recuperação dos casos similares ao novo job, reúso dos casos recuperados para gerar uma solução inicial, adaptação da solução para a carga de trabalho prevista e armazenamento das informações de descrição do job, do cálculo da predição e de sua execução. A maior contribuição deste trabalho é a adaptação da solução inicial obtida a partir dos casos passados, utilizando a relação entre a carga de trabalho passada com a carga de trabalho prevista para a execução do job. Os resultados dos experimentos realizados mostraram que o NdrPredCase tem uma boa acurácia para o cálculo de predição de jobs para recursos não dedicados quando temos um número de casos passados suficientemente grande, e é eficiente quanto ao desempenho para calcular a predição.

A habilidade de extrair conhecimento usável de grandes massas de dados tornou-se um dos mais importantes desafios para diversas comunidades, sejam elas científicas, industriais ou governamentais. A extração de tal conhecimento requer que os dados estejam representados de uma forma que não somente capture a informação relacional, mas também proporcione uma mineração efetiva e eficiente desses dados e uma capacidade de compreensão do conhecimento resultante. Na maioria dos casos, entretanto, os dados são modelados em grafos que não permitem a representação de relacionamentosmúltiplos. Essa restrição, por sua vez, pode causar uma falha na capacidade de abstração entre os dados e o modelo, fazendo com que informações essenciais da aplicação real sejam completamente negligenciadas. Este trabalho, portanto, versa sobre mineração de dados baseadas em relações, em que, em contraste a técnicas tradicionais, propomos uma heurística inovadora de mineraçãode multigrafos capaz de tratar relacionamentos múltiplos e indiretos nos dados, utilizando esses relacionamentos para identificar grupos correlacionados. Assim, construímos uma base teórica sobre a qual diversas aplicações reais podem ser modeladas, de forma a preservar relações importantes existentes nos dados, que eram ignoradaspor outros modelos. Aplicamos, então, a nossa técnica em um cenário real de redes de co-autoria, buscando agrupar e classificar fóruns científicos com base em afinidades de autoria. Para tal, modelamos os dados dessas redes como uma floresta de multigrafos e, então, osutilizamos para encontrar conjuntos de conferências que estejam interligadas. Caso tais conjuntos possam ser identificados em, pelo menos, um dado número de partes distintas da floresta, os mesmos serão vistos como pertencentes a uma mesma área de conhecimento.Resultados experimentais demonstram que a técnica é efetiva em extrair áreas distintas, mesmo diante de dados esparsos, a despeito do problema ser NP-Completo e o custo computacional da heurística ainda apresentar uma alta variabilidade.

Considere o problema de sequenciar um conjunto de tarefas, a serem processadas exatamente uma vez em qualquer máquina de um conjunto de máquinas não-relacionadas, sem preempção. Cada tarefa tem uma data de entrega, um peso e, para cada máquina, além de um tempo de processamento, um tempo de preparação dependente da sequência. Em todo este trabalho, o objetivo é minimizar a soma dos atrasos ponderados das tarefas, mas outros objetivos, como a minimização do makespan e da soma das folgas também são discutidos.Inicialmente, este trabalho propõe e analisa implementações eficientes de diversas heurísticas baseadas em buscas locais para abordar o problema. Fatores como o desenho e detalhes de implementação dos algoritmos são discutidos. As heurísticas propostas são então comparadas com outrasimplementações bem sucedidas, para mostrar suas vantagens em termos de qualidade e tempo de computação, principalmente para instâncias de grande porte.Para medir a qualidade das soluções, os valores de função objetivo das soluções obtidas são comparados com limites inferiores do problema. Para obter tais limites, um algoritmo Non-Delayed Relax-and-Cut é desenvolvido a partir de uma relaxação lagrangeana de uma formulação indexada no tempo. Para obter-se soluções aproximadas para o problema, a relaxação lagrangeana apresentada também é utilizada para

Os sistemas computacionais são utilizados nas mais variadas áreas da vida cotidiana, desde o controle das contas bancárias até os pacientes nos hospitais. Nas aplicações onde vidas humanas ou altos investimentos estão em risco, a qualidade dos sistemas computacionais tem uma importância fundamental para eliminar ou reduzir as falhas. A utilização de modelos formais no processo de desenvolvimento de sistemas apresentam uma resposta ao problema citado, pois oferecem uma descrição das partes mais relevantes do sistema com um nível adequado de abstração. Este trabalho apresenta o Modelo de Desenvolvimento Bare, para o desenvolvimento de aplicações em Sistemas Reativos Autônomos e mostra a possibilidade de modelar aplicações para diversas área. O modelo inicia com a descrição da aplicação por meio de uma máquina de estados finito, chamada X-machine. A aplicação a ser desenvolvida é a peça principal, ou núcleo, de um sistema reativo onde os eventos detectados no ambiente são capturados, avaliados com base no estado corrente da máquina, produzindo como resposta ao evento uma transição de estado e um elemento de atuação, que pode ser um novo evento ou uma comunicação. No Modelo Bare a especificação da aplicação é feita usando uma ferramenta gráfica chamada GeradorXM, após a modelagem da aplicação a X-machine resultante é transformada para um modelo tabular, onde cada linha é independente e contém informação suficiente para executar uma computação. A aplicação no modelo tabular é carregada na plataforma alvo, onde é interpretada por um programa pequeno, chamado ExecutorXM, que é o responsável pela execução da aplicação. Antes de executar a aplicação um modelo do sistema é gerado pelo GeradorXM para ser utilizado como entrada para a ferramenta de verificação de modelos NuSMV. Com isso as propriedades desejáveis para a aplicação podem ser verificadas para confirmar a sua correção. A execução do modelo Bare fecha um ciclo de desenvolvimento de aplicação para sistemas reativos autônomos por meio de um modelo formal, com geração automática de código para um interpretador e verificação de propriedades para o modelo do sistema.

A WWW apresenta duas características que desafiam a avaliação de desempenho e as propostas de solução para seus problemas: larga escala e grande variabilidade. Esta tese trata de sistemas de cache cujos objetos apresentam variabilidade extrema nos seus tamanhos. Os caches da WWW são um exemplo. Esta tese apresenta um estudo sobre a influência da variabilidade dos tamanhos dos objetos da WWW no desempenho dos seus sistemas de cache e uma solução para o problema gerado por essa variabilidade, o modelo de organização do espaço denominado PART.Esta tese propõe que o gerenciamento do espaço destes caches seja feito em dois níveis: a organização do espaço e a política de reposição. Para a organização do espaço é proposto o modelo PART. O espaço do cache é dividido em partições que armazenam classes de arquivos definidas pelo tamanho. O PART impõe restrições de tamanho para as substituições no cache minimizando os efeitos da variabilidade. A classificação dos tamanhos se adequa bem à implementação de políticas específicas para a otimização de cada métrica. Os parâmetros do modelo permitem ajustes para adequação do modelo à carga. A combinação dos vários benefícios assegura o melhor desempenho conjunto em HR e BHR. Estes resultados foram obtidos por simulação e comprovados através do conceito de mapas de desempenho, também introduzido nesta tese. Os mapas de desempenho são construídos a partir do teorema original que estabelece a relação entre HR e BHR e auxiliam o entendimento do comportamento das estratégias para gerência de espaço nos caches.

Este trabalho apresenta uma metodologia que fornece subsídios para se avaliar o desempenho de aplicações multimídia em Redes Locais Sem Fio. Para se entender o contexto do trabalho primeiro descrevemos algumas fundamentações teóricas sobre Rede Local Sem Fio (Wireless Local Area Network - WLAN) e Aplicações Multimídia. No que diz respeito à Rede Local Sem Fio, padronizado como 802.11, apresentamos conceitos básicos sobre WLAN, levando o leitor a conhecer os padrões e componentes deste tipo de rede, bem como, suas vantagens e desvantagens, segurança, protocolos, tecnologias de transmissão e as suas arquiteturas.Quanto as Aplicações Multimídia, concentramos esforços para descrever o seu conceito e funcionamento para que o leitor compreendesse o modelo do tráfego que influenciaria no desempenho da rede. As aplicações multimídia trabalhadas nesta pesquisa foram a telnet, ftp, http, áudio e vídeo.Como ganho principal deste trabalho apresentamos uma metodologia para simular e avaliar o desempenho de aplicações multimídia em WLAN, considerando a qualidade de serviço (Quality of Service - QoS) para tráfegos heterogêneos oriundos destas aplicações. Para mostrar a aplicação da metodologia realizamos um estudo de caso onde passo a passo ensinamos como usá-la. Além disso, a ferramenta de simulação utilizada foi a ns (Network Simulator), dada a sua grande usabilidade e aceitação no universo acadêmico.

Com o atual desenvolvimento do mercado de dispositivos de comunicação sem o e também da infra-estrutura e tecnologia relacionados a demanda pela disponibilização de serviços e aplicações úteis vem aumentando cada vez mais. A rede de comunicação celular, uma das grandes forças propulsoras deste mercado, já vem possibilitando o desenvolvimento de tecnologias que permitem o acesso a dados. Entretanto, mesmo com as facilidades oferecidas por estas tecnologias, o meio de comunicação sem o apresenta sérias restrições que infuenciam na oferta de serviços aos usuários. Para que as aplicações especícas para dispositivos móveis sem o possam estar disponíveis, os desenvolvedores deverão agora se preocupar com as restrições impostas pelo ambiente, que traz à tona uma nova abordagem na construção das mesmas. Considerando a relevância dos aspectos mencionados acima, este trabalho tem como proposta principal o desenvolvimento de uma arquitetura que utiliza técnicas de adaptação como uma solução para que as aplicações possam contornar os problemas existentes no meio sem o. Como estudo de caso para a validação da arquitetura e das técnicas propostas foi desenvolvida uma aplicação de localização de endereços mais próximos do usuário para o ambiente móvel. Esta aplicação pertence a uma das categorias de aplicações móveis mais atraente no mercado. Ela é composta pelos chamados serviços LBS (Location Based Services) que oferecem facilidades relacionadas à própria localização física do usuário através de tecnologias especícas da infra-estrutura existente. Aplicações do tipo 'Páginas amarelas', por exemplo, oferecem uma grande riqueza de informações ao usuário possibilitando que o mesmo possa localizar endereços e outras ocorrências geográcas em uma cidade No decorrer do texto da dissertação são descritas as especicações e as soluções de implementação utilizadas no desenvolvimento da arquitetura e da aplicação, além da validação destas realizada com um simulador.

Verificação funcional é o principal gargalo na produtividade de empresas desenvolvedoras de chips. Como a verificação funcional é um problema NP-completo, ela depende de um grande número de heurísticas e seus parâmetros (resolvedores). Normalmente o número de resolvedores disponíveis excede em muito o poder de processamento disponível. Com o advento da programação paralela, a verificação funcional pode ser otimizada através da seleção dos n melhores resolvedores para rodar em paralelo, aumentando assim a chance de se alcançar o término da verificação. Este trabalho apresenta um modelo estatístico baseado em métricas estruturais para construir estimadores de tempo para os resolvedores, permitindo então a seleção dos melhores resolvedores. Esta metodologia considera tanto o tempo de execução estimado dos resolvedores quanto a correlação entre os mesmos. Resultados confirmaram que a metodologia pode ser um mecanismo muito rápido e eficaz para a seleção dos melhores resolvedores.

A alocação de veículos para uma determinada demanda de consumidores está sujeita a uma explosão combinatória de possibilidades, devido ao aumento exponencial de alternativas e de acordo com o crescimento do tamanho do problema. Quando são consideradas alterações no ambiente, como o surgimento de novos consumidores, o Problema de Roteamento de Veículos (PRV) se torna dinâmico e ainda mais complexo e imprevisível. É comum encontrar na literatura do Problema Dinâmico de Roteamento de Veículos (PDRV) trabalhos que utilizam uma abordagem periódica para o roteamento dos veículos. Esta forma de tratamento divide o dia em intervalos bem definidos e trata vários problemas estáticos ao longo do tempo. Como principal contribuição, este trabalho propõe a utilização de algoritmos de roteamento como tomada de decisão imediata ou de curto prazo para tratar os PDRVs. Nesta abordagem, os consumidores são informados rapidamente (online) quando serão atendidos. Este trabalho mostra que a abordagem de roteamento online pode ter maior impacto sobre os custos se comparada a abordagem periódica. Além da contribuição sobre o roteamento online, este trabalho apresenta duas heurísticas híbridas para resolver o Problema estático de Roteamento de Veículos com Janela de Tempo (PRVJT). Ambas exploram a formulação do Problema de Particionamento de Conjuntos para solucionar o PRVJT. O primeiro algoritmo híbrido é especialmente proposto para atender contextos dinâmicos do PRVJT, em que novas soluções devem ser encontradas rapidamente. O segundo algoritmo híbrido é mais robusto, alcança melhores resultados e é indicado para contextos estáticos. Resultados computacionais mostram que as heurísticas propostas são competitivas em comparação com outros algoritmos da literatura que tratam a bem conhecida base de testes de Solomon. Este trabalho superou o melhor resultado conhecido em oito instâncias, considerando a minimização da distância total do PRVJT. Além disso, o segundo algoritmo melhorou ou igualou 82,1% dos melhores resultados conhecidos para a base de testes de Solomon

A Família Miner de Agentes para a World-Wide Web é um conjunto de ferramentas que objetiva auxiliar usuários a localizarem informações na Internet. A Família Miner é baseada na API Miner e dividida em quatro grupos maiores de agentes: agentes de busca utilizados para a procura de informações genéricas na Web; agentes de compra utilizados para localizar e comparar preços de produtos vendidos online;agentes de notícias utilizados para coletar e elaborar clippings de notícias veiculadas online na Web; e agentes de monitoramento utilizados para gerenciar e monitorar toda a Família Miner.

Flebotomíneos transmissores de leishmanioses são geralmente capturados sugando humanos e/ou animais e ainda, por armadilhas luminosas iscadas ou não, dentre outras. O presente trabalho teve como objetivo avaliar o efeito de cairomônios (odores sintéticos de hospedeiros) em armadilha luminosa CDC (modelo HP) em campo no Brejo do Mutambal (Varzelândia, MG) visando aumentar o potencial das armadilhas luminosas. Tubos de polietileno, silicone e frascos de vidro foram avaliados com possíveis liberadores de 1-octen-3-ol (octenol). O cairomônio octenol foi liberado em frascos de vidro nas taxas de evaporação de 0,5; 5; 15 e 30 mg/h e os resultados demonstraram que, embora não tenha aumentado a captura indiscriminada do gênero Lutzomyia, em armadilha luminosa, o cairomônio foi eficiente para L. intermedia, em resposta dose-dependente. O cairomônio BG Mesh Lure® sozinho e associado ao octenol (5mg/h) foi avaliado e mostrou eficiência na captura de várias espécies de flebotomíneos, quando comparado às armadilhas controle (somente a luz). Das espécies mais abundantes, somente L. intermedia respondeu ao atraente BG Mesh Lure® associada a taxa de 5mg/h de octenol em comparação ao controle. O efeito da atratividade do BG Mesh Lure® e de seus compostos individualizados (ácido lático, ácido capróico e amônia) também foram avaliados visando conhecer a especificidade de cada componente cairomonal. As maiores médias de captura para armadilhas iscadas com BG Mesh Lure® foram observadas para L. longipalpis e L. intermedia quando comparadas ao controle. O ácido lático se mostrou mais atrativos para a espécie L. lenti, embora L. longipalpis, L. intermedia e L. renei tenham apresentado capturas maiores para este cairomônio, quando comparadas ao controle. O ácido capróico foi mais eficiente na de captura da espécie L. renei, quando comparado à amônia. Armadilhas luminosas contendo amônia capturaram mais flebotomíneos das espécies L. longipalpis; L. intermedia e L. lenti que armadilhas iscadas com ácido capróico. O octenol e o BG Mesh Lure® associado à taxa de 15mg/h foram eficientes na captura de L. intermedia, que foi uma das espécies mais abundantes durante os experimentos. O BG Mesh Lure® apresentou um potencial de captura maior para flebotomíneos antropofílicos quando comparado aos seus compostos individualizados, mostrando-se como uma possível isca para atração destes flebotomíneos. Das 20 espécies capturadas em Brejo do Mutambal, L. lutziana, L. longipennis e L. goiana foram observadas pela primeira vez no município de Varzelândia.