RCAAP Repository

O ser humano sempre procura mais conhecimento. Esse é essencial em âmbitos pessoal e também profissional. Para conseguir mais conhecimento, o ser humano armazena volumosos repositórios de dados, dos quais tem que extrair informação. Contudo, a quantidade de dados e a complexidade desses podem prejudicar a extração de informação adequada. Para solucionar tal problema, recorre-se à chamada mineração de dados. Essa fornece um conjunto de métodos para processamento dos dados e extração de informação. Dentre tais métodos, esté a chamada classificação, de especial interesse para este trabalho. Existem diversas propostas de algoritmos de classificação. Algumas são clássicas (bastante conhecidas), como a chamada árvore de decisão. Outras, assunto principal deste trabalho, são propostas alternativas, baseadas por exemplo em análise formal de conceitos. Essas últimas propostas executam a tarefa de classificação por meio de estruturas chamadas reticulados de conceitos; e conseguem bons resultados. Este trabalho apresenta diferentes algoritmos para classificação baseados em análise formal de conceitos, sendo alguns desses propostas inéditas, publicados aqui pela primeira vez. Tais algoritmos têm boas precisões de classificação, mas apresentam alguns desafios, como os custos computacionais.

Extrair informação de grandes bases de dados é um desafio das novas demandas da Ciência da Computação. Além disso, diversas técnicas de Mineração de Dados são propostas continuamente na literatura. Tais algoritmos são computacionalmente intensivos, além do fato de processarem entradas de dados muito grandes. Assim, há uma nova tendência em direção ao alto desempenho de processamento e montagem de clusters de computadores, a um custo mais razoável que os supercomputadores do passado. Essa tendência nos leva a um cenário em que o alto desempenho é alcançado por eficientes implementações de aplicações paralelas e distribuídas. O Anthill é uma solução para processamento distribuído em clusters de computadores onde um alto desempenho é obtido em execuções eficientes e escaláveis de diversos algoritmos de Mineração de Dados. Ele fornece um framework para o desenvolvimento e a execução de aplicações em ambiente distribuído, onde as aplicações devem ser decompostas em filtros que se comunicam através de streams de dados, como em um pipeline. O processo de desenvolvimento das aplicações entretanto demanda do programador decompor as aplicações, que não é o caminho natural de desenvolvimento dos programas. Este trabalho apresenta uma ferramenta de geração semi-automática de filtros a partir de uma implementação seqüencial do algoritmo. Esse processo é divido em duas etapas: a primeira é o particionamento em filtros do código seqüencial, seguido pela geração do código para cada um dos filtros identificados. Este trabalho tem como foco a segunda etapa, a geração do código. Para a primeira etapa, nós realizamos de forma semi-automática alguns passos a serem automatizados em trabalhos futuros. Esse processo determina as dependências de dados no código, e identifica os pontos de corte do mesmo. A partir deste passo, é gerado uma versão anotada do código seqüencial, contendo as informações para sua divisão em filtros. A geração dos filtros é feita a partir do código anotado. Basicamente, as anotações contêm um grafo direcionado onde os vértices representam os filtros e as arestas representam os dados que são trafegados entre os filtros. Nós implementamos um gerador de código fonte onde a entrada é um algoritmos seqüencial escrito em C e a saída são os filtros, também em C, com as extensões do Anthill. A maioria das adaptações necessárias para Anthill são geradas automaticamente por essa ferramenta. O gerador de código automático foi validado usando três aplicações de Mineração de Dados que já haviam sido implementadas no Anthill. Foram gerados de forma automática o código dos filtros Anthill a partir das versões seqüenciais. Nós avaliamos o desempenho do código gerado e observamos que o resultado é similar ao código gerado manualmente na maioria dos casos. Este é um bom resultado, dado que o custo de implementação do código seqüencial é bem menor do que a implementação paralela dos filtros para o Anthill. Também foram observadas algumas otimizações presentes na implementação manual que podem ser realizadas automaticamente pela ferramenta para obtenção de um resultado mais otimizado. Como trabalhos futuros devemos prosseguir com a automatização de mais otimizações na geração do código.

A Ciência da Computação tem evoluído e alcançado diversas áreas do conhecimento tais como a biologia, a geografia, a astronomia, entre outras. Os Sistemas de Fluxo de Trabalho Científico foram criados com o objetivo de ajudar os pesquisadores dessas áreas nos seus processos de análise de dados. Esses sistemas permitem aos cientistas criar e organizar tarefas relativas aos seus experimentos; executar essas tarefas eficientemente e transparentemente em um ambiente distribuído; assim como monitorar toda a execução.Os desafios para o projeto e a implementação desses sistemas são muitos, principalmente devido às características das aplicações que geram os fluxos de trabalho científicos. Elas são consideradas aplicações intensivas em dados e processamento as quais criam uma enorme quantidade de dados durante a execução e executam por longos períodos. Desta forma, alguns dos desafios para projetar os sistemas de fluxo de trabalho científico são: armazenar, pesquisar e gerenciar grandes bases de dados distribuídas, gerenciar os dados de entrada e de saída, escalonar e monitorar a execução desses fluxos de trabalho em ambientes distribuídos, assim como tratar a ocorrência de falhas tanto de software quanto de hardware que podem acontecer durante a execução.Este trabalho investiga o uso de mecanismos que, de forma transparente, aumentem a disponibilidade de sistemas de fluxo de trabalho científico, de tal forma que o trabalho a ser refeito após uma falha no sistema seja mínimo. Esses mecanismos utilizam como base características próprias desses sistemas para a construção de um sistema de armazenamento dos dados necessários para a recuperação das aplicações após uma falha. Esse sistema provê um armazenamento assíncrono dos dados de tal forma que não há necessidade do travamento da execução das aplicações para que ele aconteça. Os resultados experimentais mostram que o sistema é capaz escalar a grandes bases de dados, e que a nossa abordagem introduz muito pouco overhead na execução das aplicações.

Um dos recursos mais importantes em redes de sensores é a energia, porque, em geral, as baterias dos nós não podem ser recarregadas. Por isso, quaisquer soluções para essas redes devem ser eficientes em termos de energia. O objetivo deste trabalho é projetar protocolos para disseminar uma informação para todos os nós da rede, ou seja, soluções para realizar difusão de dados em redes de sensores sem fio. Com esse objetivo, é proposto o ``Delay and Energy Based Broadcasting'' (DEBB), um protocolo que utiliza o mapa de energia e o conceito de propagação com atrasos para realizar a difusão de dados eficiente em termos de energia em redes de sensores sem fio. O funcionamento básico do DEBB é simples e otimizado para reduzir a carga de trabalho dos nós sensores. Resultados de simulação mostram a eficiência do protocolo em relação à cobertura da rede, ao número de transmissões e ao consumo de energia. O protocolo apresenta a habilidade de contornar regiões de baixa energia e seu comportamento é escalável quando o número de regiões de baixa energia aumenta. Além disso, o DEBB apresenta um mecanismo para a redução da latência, principal problema dos algoritmos baseados em propagação com atraso.

É notório que o custo final das mercadorias no comércio varejista decorre, em grande parte, dos gastos com o transporte de bens.Neste contexto, surge o problema de roteamento de veículos que visa a otimizar as rotas de uma frota que tem a incumbência de prestar serviços de coleta ou de entrega em pontos de demanda.Diante da necessidade do atendimento de requisições efetuadas no decorrer do período de operação da frota, surge o problema de roteamento dinâmico de veículos. Este trabalho traz uma abordagem capaz de fornecer soluções de boa qualidade para o problema de roteamento dinâmico de veículos com janelas de tempo e tempos de viagem variáveis. Foi proposto um arcabouço, baseado em uma heurística de geração de colunas que utiliza um algoritmo evolucionário dinâmico com o intuito de gerar um conjunto de soluções para o referido problema. Associado a este algoritmo, foi utilizada uma formulação matemática do problema de partição de conjuntos que visa a obter a melhor combinação de rotas que atendem às restrições do problema, tendo como base as rotas pertencentes às soluções encontradas pelo algoritmo evolucionário. Foram apresentadas três políticas de roteamento dinâmico para determinar o momento no qual as novas requisições efetuadas são repassadas ao algoritmo evolucionário dinâmico. A política Online repassa as requisições logo que são geradas. A política Por Demanda aramazena as novas requisições em uma fila e as repassa ao algoritmo dinâmico somente quando a fila atinge o seu limite de capacidade. Já a política Periódica, por sua vez, espera um período de tempo fixo entre os repasses de novas requisições ao algoritmo evolucionário dinâmico.O arcabouço foi testado através de uma adaptação das instâncias clássicas de problemas de roteamento de veículos propostas por Solomon(1987). Foram realizados testes das três políticas de roteamento dinâmico apresentadas e os resultados foram analisados através de estatísticas.

Nesse trabalho apresentamos dois novos métodos para organização de Redes de Sensores Sem Fio (RSSF). Esses métodos integram o controle de densidade e mobilidade do sorvedouro para otimizar algumas métricas importantes dessas redes. Em métodos tradicionais, com comunicação multi-saltos, o processo de roteamento de dados é apontado por alguns autores com um grande consumidor de energia. Para reduzir esse consumo, a mobilidade do sorvedouro foi integrada as RSSF possibilitando a coleta de dados utilizando comunicação um-salto. Porém, os métodos propostos apresentam um maior atraso na entegra de dados se comparados aos métodos tradicionais. Para tratar esse problema, propomos o método SHS (Single-Hop Strategy) que estende os métodos propostos na literatura com o objetivo de reduzir o atraso na entrega. A imposição da restrição de comunicação um-salto obriga os nós sensores a estarem no raio de comunicação do sorvedouro para reportar seus dados, o que impõe um maior atraso na entrega desses dados. Para aproximar os métodos com sorvedouro móvel ao métodos tradicionais com relaçao ao desempenho no atraso na entrega de mensagens, propomos o MHS (Multi-Hop Strategy). O MHS estende o método SHS implementando um esquema de comunicação multi-saltos com o número de saltos limitado. Com isso, reduzimos o tempo de coleta dos dados através de agrupamentos de maior raio. Os dois métodos integram a mobilidade do sorvedouro com controle de densidade, onde o sorvedouro é o responsável pelo controle e implantação das decisões. Os resultados computacionais mostram uma significativa melhora em métricas como tempo de vida das RSSFs, cobertura e conectividade. Entretanto, na métrica de atraso na entrega de dados os métodos com sorvedouro móvel são significativamente menos eficientes que estratégias multi-saltos. Porém, os resultados também mostram que com o ajuste de alguns parâmetros como velocidade do sorvedouro, densidade da rede e o número de sorvedouros, podemos melhorar significativamente o desempenho dessa métrica.

O modelo de Máquina de Estado Abstrata (ASM - Abstract State Machine) vem sendo amplamente utilizado para especificação formal de diversos tipos de sistemas devido ao seu alto grau de abstração e rigor matemático, o que facilita compreender o sistema modelado e verificar formalmente suas propriedades. Pode-se utilizar uma linguagem baseada no modelo ASM para escrever uma especificação em alto nível, conhecida como Modelo Básico, e posteriormente submetê-la a um processo de transformação baseado no Método de Refinamento ASM para obter a implementação validada e verificada.O principal objetivo do trabalho Método de Refinamento Machina (MRM) é propor um método de especificação em alto nível que represente aspectos de ASM e com a possibilidade de validar e verificar o modelo construído independente da implementação. O processo de refinamento permite obter, automaticamente, o código executável em Machina e realizar a verificação utilizando a ferramenta NuSMV. Assim, pode-se verificar automaticamente a implementação de acordo com a especificação.

O desenvolvimento dirigido por modelos é o processo pelo qual sistemas de software são construídos a partir de representações sobre seus domínios. O não sucesso de projetos de software tem relação a aspectos únicos e específicos de cada projeto, mas todos os projetos de sucesso são semelhantes em vários aspectos. Existem vários elementos que contribuem para um projeto bem-sucedido; um desses componentes é a utilização da modelagem. A escolha dos modelos a serem criados tem profunda influência sobre a maneira como um determinado problema é atacado e como uma solução é definida. Cada modelo pode ser expresso em diferentes níveis de precisão. Determinar o que modelar e como modelar em sistemas complexos não é uma tarefa fácil. Este trabalho propõe a definição de diretrizes sobre quais elementos, atributos e visões de dados para análise e modelagem devem ser observados durante o desenvolvimento de um software. A meta de trabalho é que as definições sejam fundamentadas em técnicas e conceitos consagrados pela literatura, como os conceitos sobre Model Driven Architecture. Para validar as definições sugeridas e exemplificar como as mesmas podem ser aplicadas, este trabalho prevê também a descrição de sua aplicação no processo Praxis Synergia, para o contexto de aplicações web.

Sistemas multi-agente têm sido usados na resolução de diversosproblemas em áreas que podem variar do comércio eletrônico à robótica móvel. Nesses sistemas, um agente pode necessitar cooperar com outros para atingir um objetivo. Uma forma de cooperação é a realização de contratos pelos quais um agente pode contratar outro queesteja melhor capacitado para realizar uma tarefa. Os contratos sãoparticularmente importantes quando os agentes não compartilham omesmo objetivo. Nesse caso, um agente poderá encarregar uma tarefa a outro, que não compartilha os mesmos objetivos, mas realizaráa tarefa incentivado por uma recompensa. Atualmente, com os avançosda computação massiva, tem surgido a necessidade de construirsistemas compostos por um número cada vez maior de agentes, emquantidades que podem chegar a centenas ou mesmo milhares. Nestes sistemas, a contratação de agentes deve ser escalável. Este trabalho propõe um protocolo escalável para a contratação de agentes com interesses próprios em grupos de larga escala, geralmente chamados swarms. O protocolo permite a formação de contratos mediante um processo que passa por três etapas: uma etapa de descoberta, onde os agentes encontram outros agentes que podem ser contratados, uma etapa de negociação, onde os agentes envolvidos determinam o preço da contratação e uma etapa de execução, onde a tarefa é alocada e o preço do contrato é pago após a execução da tarefa. No protocolo, o uso de limiares dinâmicos facilita a descoberta de agentes e uma mistura de leilões simultâneos permite aos agentes negociar e definir o preço do contrato. O protocolo foi testado em simulações onde times de robôs pertencentes a diferentes companhias são contratados para transportar mercadorias. Os resultados obtidos mostraram que o protocolo proposto é racional, pareto--eficiente, distribuído e justo, características desejáveis em todo protocolo de contratação. Além disso, o protocolo mostrou-se escalável utilizando níveis baixos de comunicação e consumindo poucos recursos computacionais sendo,portanto, adequado para swarms.

Esta dissertação propõe um processo que utiliza resultados de consultas submetidas a máquinas de busca para encontrar a URL do texto completo correspondente, ou de qualquer outro material relacionado, a artigos catalogados em uma biblioteca digital que não possuem tal informação registrada. Apresentamos um estudo desse processo para investigar diferentes estratégias de consultas aplicadas a três máquinas de busca de propósito geral (Google, Yahoo!, MSN) e a duas especializadas (Scholar e CiteSeer) considerando vários cenários caracterizados por usuários com diferentes níveis de exigências. Especificamente, conduzimos um conjunto de experimentos com artigos provenientes da BDBComp - Biblioteca Digital Brasileira de Computação e da DBLP - Digital Bibliography & Library Project. De acordo com os resultados, Scholar mostrou-se mais eficaz nesta tarefa do que as outras máquinas de busca testadas em todos os cenários estudados. Além disso, nossos experimentos mostraram que estratégias simples para combinação e reordenação fornecem resultados ainda melhores. Nosso estudo também apresenta uma análise do impacto de diferentes fatores na chance de se encontrar o texto completo dos artigos procurados.

Com o advento da Web e de outros repositórios de informação, como Bibliotecas Digitais, a tarefa de recuperação de informação transformou-se em um problema extremamente complexo e desafiador. Neste contexto, as máquinas de busca surgiram como ferramentas fundamentais para a tarefa de recuperação de informação em uma coleção de documentos. Estas ferramentas são baseadas em modelos de recuperação de informação, cujo principal objetivo é definir a ordem na qual os documentos são retornados para os usuários em resposta a uma consulta, através de uma função de ordenação. Diversas funções de ordenação têm sido investigadas ao longo dos anos. No entanto, a maioria delas tem um caráter geral, isto é, são projetadas para serem efetivas em qualquer coleção.Neste trabalho é proposto um novo método para descobrir funções de ordenação adaptadas a uma coleção baseado em Programação Genética (GP). O processo evolutivo da Abordagem de Componentes Combinados (CCA), proposta por este trabalho, diferentemente de outras abordagens baseadas em GP, utiliza componentes de diferentes funções de ordenação comprovadamente eficazes e conhecidas da literatura de recuperação de informação. Parte-se da hipótese de que estes componentes são individualmente representativos e ricos de significado e podem ser combinados para a geração de uma nova função de ordenação mais efetiva e específica para uma determinada coleção.Os resultados experimentais mostram que a abordagem CCA foi capaz de superar em até 40% as abordagens clássicas da literatura tais como tf-idf, BM25 e outra abordagem baseada em GP (denominada FAN-GP) em duas coleções diferentes. O processo evolutivo CCA também foi capaz de reduzir o problema do 'treinamento exagerado', geralmente encontrado em métodos de aprendizado de máquina, especialmente programação genética.

Bibliotecas digitais são sistemas de informação complexos e que muitas vezes sofrem mudanças em suas estruturas, conteúdo e serviços. Estas complexidade e dinamicidade tornam a tarefa de manutenção destes sistemas não trivial, pois exigem avaliações de diferentes componentes da biblioteca digital recorrentemente. Estas avaliações geralmente são customizadas para o sistema em questão e acontecem à medida que os problemas aparecem e intervenções urgentes da administração são requeridas. Objetivando mudar este quadro, neste trabalho é apresentada a 5SQual, uma ferramenta que provê meios para a realização de avaliações automáticas e configuráveis de objetos digitais, metadados e serviços de uma biblioteca digital. A ferramenta implementa diversos indicadores numéricos associados a 8 dimensões descritas no modelo 5S de qualidade e a sua arquitetura foi desenvolvida visando a aplicabilidade em diversas bibliotecas digitais. Dentre as contribuições deste trabalho podem-se destacar ainda a implementação e avaliação (com especialistas de usabilidade) de uma interface gráfica auxiliar para a configuração de avaliações da 5SQual e a realização de uma pesquisa sobre a expectativa em relação à ferramenta feita com administradores de bibliotecas digitais reais.

Neste trabalho apresentamos uma caracterização detalhada dos padrões de acesso a um serviço de blogs, uma nova forma de disponibilizar conteúdo na Web. Os blogs são compostos por uma série de textos escritos em publicações e comentários por um crescente número de usuários, que em conjunto constituem uma blogosfera. Nossa caracterização de mais de 35 milhões de requisições deleitura, de escrita e administrativas, enviadas em um período de 28 dias, foi feita sob três diferentes pontos de vista da blogosfera. Na visão do servidor, caracterizamos os padrões de acesso de todos usuários para todos os blogs; na visão dos usuários, caracterizamos como cada um dos usuários interagem com os blogs; e, na visão dos objetos, caracterizamos como cada um dos blogs são acessados. Nossos resultados sugerem duas importantes conclusões. Em primeirolugar, mostramos que a natureza mais interativa da blogosfera gera padrões interessantes de tráfego e de comunicação que são diferentes dos observados em serviços estáticos da Web. Consideramos os acessos aos objetos da blogosfera como parte de interações entre os donos e os leitores dos blogs. Com base em nosso estudo sobre a conversação entre os usuários da blogosfera, classificamos os blogs em três grupos, que chamamos de broadcast, livro de visitas e fórum.As interações entre membros de grupos de interesse criam uma comunicação mais freqüente dos donos dos blogs para seus leitores em blogs do tipo broadcast, mais freqüente dos leitores para os donos dos blogs, em blogs do tipo livro de visitas, e mais distribuída em ambas direções em blogs do tipo fórum. Em segundo lugar, identificamos e caracterizamos novas propriedades da carga de trabalho de uma blogosfera e investigamos as similaridades ediferenças entre cargas de trabalho de servidores típicos da Web e cargasde trabalho de servidores de blogs.

Este trabalho propõe uma nova heurística de decisão para solucionadores do problema da satisfabilidade (SAT) baseados no algoritmo de Davis Putnam, Logemann e Loveland (DPLL). Essa heurística se baseia na subtração de cubos. Cada cláusula negada é visualizada como um cubo no espaço de procura booleano n-dimensional, denotando um subespaço onde nenhuma atribuição de valores às variáveis, que satisfaça a instância do problema, possa ser encontrada. A subtração dos cubos, sistematicamente subtrai todas as cláusulas-cubo do cubo universal, que representa todo o espaço booleano de procura. Se o resultado for um cubo vazio o problema não admite uma solução que o torne satisfazível, caso contrário, o problema é satisfazível. Esse algoritmo pode ser implementado modificando-se o mecanismo de decisão de solucionadores do problema da satisfabilidade baseados no algoritmo DPLL. Essas modificações restringem a escolha da próxima variável de decisão após um retrocesso cronológico. A intuição do algoritmo é confinar a procura a uma cláusula ou a um grupo de cláusulas, com o objetivo de escapar o mais rapidamente possível de regiões onde a solução não possa ser encontrada, ou uma resposta sim ou não possa ser dada para a instância, ou permitir o aprendizado de cláusulas mais úteis à solução do problema. Inicialmente foram utilizadas duas versões básicas de um solucionador DPLL, sem quaisquer das melhorias atualmente encontradas na literatura e posteriormente em um solucionador no estado-da-arte, o zChaff. Para o teste foram utilizados 1252 instâncias de problemas do DIMACS, IBM CNF BMC e resultados de verificação formal de microprocessadores. Observa-se uma melhoria significativa no tempo de execução e uma redução do número de instâncias não resolvidas dentro de um tempo limite, em todos os casos. Considerando a avaliação experimental, podemos concluir que a subtração de cubos é um algoritmo efetivo para a melhoria do desempenho de solucionadores do problema da satisfabilidade baseados no algoritmo DPLL.

Neste trabalho é abordado o Problema de Roteamento de Veículos com Coleta e Entrega Simultâneas (VRPSPD) que é um problema básico de logística reversa, definido como: Dados uma rede de transporte com $n$ consumidores e um depósito, na qual cada consumidor possui uma demanda de coleta e/ou umademanda de entrega, e um conjunto de veículos com capacidade limitada, o VRPSPD consiste em definir rotas otimizadas que satisfaçam todas as demandas dos clientes, respeitando a capacidade dos veículos.Devido à complexidade computacional do VRPSPD, o desenvolvimento e análise de heurísticas construtivas é de extrema importância. Este trabalho compara cinco heurísticas construtivas conhecidas da literatura e propõe três novas heurísticas. Os resultados mostram que as heurísticas propostas são melhores em 90% das instâncias testadas considerando a redução da distância trafegada pelos veículos.A heurística com os melhores resultados da literatura (Heurística Baseada em Inserção) é estendida em duas direções. Na primeira pela introdução de alternativas permitindo que as rotas sejam finalizadas mais cedo e, na segunda direção, pelo uso de ferramentas de apoio a decisão multicritério para escolher o vértice a ser inserido na rota a cada passo da heurística. Os resultados também apresentaram uma melhora significativa da distância trafegada em 92% das instâncias.As 4 melhores heurísticas analisadas neste trabalho foram utilizadas na fase de construção da heurística baseada no GRASP. Na fase de busca local foram aplicados movimentos de intercâmbio, realocação, eliminação de rotas, cruzamento e 2Opt. Os resultados obtidos foram comparados aos melhoresresultados da literatura. Em 64% das instâncias analisadas, as soluções apresentadas pela heurística proposta reduziram a distância trafegada total significativamente. Os resultados também comprovaram que a utilização de uma boa heurística nesta fase melhora a qualidade dos resultados finais da heurística baseada no GRASP.

Recentes avanços tecnológicos possibilitaram a combinação de sistemas embutidos e comunicação sem fio, viabilizando um novo tipo de rede móvel ad-hoc, conhecida como Rede de Sensores Sem Fio (RSSF). Estas redes têm a capacidade de monitorar o mundo físico através de pequenos sensores que operam de maneira integrada e colaborativa. Devido à natureza bastante compacta dos nós sensores, um dos principais focos no projeto das RSSF é a restrição de energia. Dessa forma, estudos que visam melhorar as condições de operação destas redes, bem como prolongar seu tempo de vida mostram-se muito importantes. Neste trabalho foi estudado o problema de atribuição de papéis em RSSF, cujo objetivo é definir papéis específicos para os sensores, tal que o tempo de vida da rede seja maximizado, garantindo a cobertura dos pontos de demanda e o roteamento das informações. O problema foi tratado em diferentes abordagens, e os resultados computacionais apresentados mostram que é possível prover uma melhoria no projeto de redes através de técnicas de otimização.

Apesar de todo o avanço obtido pelo método de análise sintática LALR criado por DeRemer no fim dos anos 60, conflitos ainda são removidos de forma não produtiva, pela análise de extensos arquivos de log criados por geradores de analisadores sintáticos. De forma a alterar este cenário, apresentamos um gerador de analisador sintático capaz de remover automaticamente certos tipos de conflitos, em conjunto com uma metodologia que guia o processo de remoção manual. Discutimos também os algoritmos internos da ferramenta e como os analisadores sintáticos produzidos são compactos em termos de utilização de memória.

Em um ambiente pervasivo, passamos a ter uma abundância de dispositivos computacionais capazes de se comunicarem. Estes dispositivos podem se encontrar muitas vezes em estado ocioso, o que os permite doar parte de seus recursos às aplicações em outros dispositivos. Esta dissertação apresenta um modelo de distribuição com foco neste ambiente e um Arcabouço para o desenvolvimento de soluções de distribuição para aplicações Java, que habilita aplicações centralizadas a se distribuírem pelos dispositivos do ambiente, aproveitando os recursos disponíveis.

A digitalização de documentos históricos apresenta-se como forma eficaz de viabilizar o acesso público a grandes acervos e equalizar o severo compromisso entre conservação e acesso. Freqüentemente, documentos históricos apresentam alto grau de degradação, causada pela ação do tempo ou danos sofridos, resultando em imagens digitais com baixo nível de legibilidade e em alguns casos extremos, totalmente ilegíveis. Técnicas de processamento digital de imagens e análise de documentos são empregadas na solução deste problema. A maioria das abordagens para limiarização e segmentação de documentos históricos utiliza características globais do documento para eliminar o ruído de fundo e outros problemas de degradação, buscando aprimorar a legibilidade. No entanto, a distribuição dos problemas de degradação não é uniforme e nem linear na imagem do documento. Desta forma, após a aplicaçãodestes algoritmos, algumas regiões apresentam melhoria da legibilidade, porém, em outras, observa-se o efeito reverso. Este trabalho apresenta uma nova abordagem para o problema de melhorar a qualidade visual e a legibilidade de imagens de documentos históricos. A solução utiliza uma abordagem híbrida, combinando características globais e locais. Pode-se dividir o processamento em quatro etapas. Primeiro, as características globais do documento são extraídas. Na segunda etapa, são identificadas as linhas que apresentam conteúdo textual. Na próxima etapa, é realizada a limiarização das linhas selecionadas, combinando características locais e globais. Finalmente, na última etapa, é realizada a binarizaçãoglobal do documento. Experimentos realizados com imagens de documentos históricos do acervo Dops/MG demonstram que a abordagem proposta foi eficiente em melhorar a qualidade visual e legibilidade em 80 por cento dos documentos.

Rede de sensores sem fio é um tipo de rede ad hoc que pode ser usada com o propósito de monitorar uma variedade de características ambientais, tais como som, temperatura, umidade, pressão, níveis de ruído, dentre outros. Um problema típico dessas redes é como coletar eenviar informações históricas de todos os nós sensores da rede para a estação base. Como a energia disponível desses nós é um recurso crítico, é impraticável transmitir todo o conjunto de dados de cada nó sensor para o nó sorvedouro. Há, portanto, a necessidade de minimizara comunicação entre os nós sensores e o nó sorvedouro, visto que a comunicação no meio sem fio é o consumidor primário de energia nessas redes. Conseqüentemente, é importante aplicar técnicas para redução dos dados para que menos bits possam ser transmitidos pelo meio sem fio. Neste trabalho, é proposto um algoritmo de codificação diferenciada para redes de sensores sem fio, no qual os nós de sensoriamento enviam apenas as diferenças de suas leituras parauma base comum de dados. Os resultados de simulação mostraram que o algoritmo apresentou um bom desempenho em aplicações onde os nós sensores coletam leituras similares ao longo do tempo.