Repositório RCAAP

O Problema de Steiner em grafos consiste em encontrar, em um grafo com custos nas arestas, uma árvore de custo mínimo contendo um dado conjunto de vértices. Esse problema tem um papel central na área de algoritmos de aproximação e diversas de suas variantes têm aplicações, por exemplo, em projeto de redes de comunicação. Neste trabalho apresentamos um estudo de vários algoritmos de aproximação para este problema. Os algoritmos escolhidos baseiam-se na utilização de árvores k-restritas e formam uma série, cada um deles tendo explorado melhor uma idéia introduzida pelo anterior. Todos eles foram projetados durante a última década, sendo o mais recente, o melhor algoritmo de aproximação para o problema até o momento em termos de razão de aproximação

Esta dissertação apresenta uma análise dos esquemas de Micropagamento Eletrônico PayWord, MicroMint e MilliCent, que empregam técnicas de criptografia para produzir e controlar a utilização da moeda eletrônica, por um Sistema de Pagamento Eletrônico para transações de pequeno valor monetário. O trabalho descreve em detalhes o Sistema Protótipo de Micropagamento que foi desenvolvido utilizando o protocolo PayWord, de forma a não só atender aos requisitos e às características de uma aplicação de comércio eletrônico, como também contemplar operações de venda, pagamento e entrega de produtos e informações pela Internet

Esta dissertação apresenta um arcabouço para implementação de algoritmos de inferência de gramáticas estocásticas. Este arcabouço inclui suporte de software para a geração automática de classificadores de seqüências. O objetivo final do sistema é ser usado no desenvolvimento de novos classificadores para seqüências genéticas

Este trabalho descreve alguns métodos algébricos para o cálculo de grupos de automorfismos de grafos. Dois métodos são enfocados: a utilização da teoria de grupos de permutações, base do algoritmo de Luks, que determina, em tempo polinomial, o grupo de automorfismos de um grafo de grau limitado, e uma reformulação do problema em termos de extensões de corpos, que procura utilizar especializações para obter informações sobre grupos de automorfismos de grafos

Nesse trabalho, estabelecemos uma correspondência entre raciocínio abdutivo no cálculo de eventos e planejamento de ordem parcial. Para tanto, implementamos três sistemas de planejamento abdutivo baseado em cálculo de eventos (Abp, Sabp e Rabp) e três sistemas algorítmicos (de ordem parcial) correspondentes (Pop, Snlp e Tweak). Então, através de uma análise comparativa do comportamento desses sistemas, mostramos que planejadores (lógicos e algorítmicos) que implementam estratégias de planejamento correspondentes apresentam comportamentos idênticos (i.e., examinam o mesmo espaço de busca e apresentam praticamente a mesma eficiência). Também mostramos que, tanto para sistemas lógicos quanto algorítmicos, a eficiência de planejamento não depende apenas da política de proteção de submetas adotadas em cada um deles, mas também das características específicas do domínio de planejamento considerado

A classificação de dados é uma das tarefas importantes realizadas pela mineração de dados. Entretanto, tal classificação não considera a necessidade da comparação automática entre diversas classificações de dados. Este trabalho apresenta um componente para descobrir as relações entre objetos classificados. Esse componente é uma forma de apoio ao processo de descoberta de conhecimento. Para tanto, tal componente oferece uma estrutura de dados para representação, em memória, dos dados gerados pelo processo de classificação, que inclui dados dos classificadores e dos objetos analisados. Além disso, para a manipulação da referida estrutura de dados em memória foi estendido um conjunto de operadores da álgebra relacional, para otimizar o cruzamento dos objetos classificados

Atualmente não se conhece nenhum método de prova para a lógica proposicional clássica que tenha tempo polinomial. Os métodos de tabela-verdade e o de tableux analíticos são imediatamente implementáveis em uma máquina, mas já foi provado [D¦A90] que nenhum dos dois é mais eficiente que o outro no caso geral. Por outro lado, o sistema de tableux KE de D¦Agostino é essencialmente mais eficiente que ambos. Uma outra abordagem para resolver o problema da validade de fórmulas é o raciocínio por aproximações. Cadoli e Schaerf [SC95] propuseram um método de raciocínio por aproximações com respostas aproximadas que: a) dão informações semanticamente claras sobre o problema a cada passo de aproximação, b) cada resposta aproximada é mais fácil de computar que a resposta do problema original, e c) podem ser melhoradas, e eventualmente convergem para a resposta correta. No entanto este método está restrito ao formato clausal e não fornece uma heurística de aproximação. Finger e Wassermann [FW01] propuseram um método que generaliza o raciocínio por aproximações de Cadoli e Schaerf, eliminando a restrição a cláusulas e introduzindo a heurística de aproximação. Eles entendem a semântica da lógica S3 usada no método de Cadoli e Schaerf para a lógica proposicional, e propõem o método de tableux KE-S3 para essa lógica - baseado nos tableux KE de D¦Agostino. O objetivo deste trabalho é implementar o método de Tableux Analíticos, o método de Tableux de KE de D¦Agostino e o método de Tableux KE-S3 e fazer um teste comparativo dos métodos

Esta dissertação de mestrado especifica os aspectos de mobilidade de um protocolo de comunicação para computação móvel usando o Ditributed Join-Calculus. A especificação foi utilizada para a verificação das características do protocolo com relação à mobilidade. Além disso, estudamos como o uso do Distrubuted Join-Calculus pode ajudar numa melhor visão e compreensão do comportamento de agentes móveis. O Join-Calculus é um modelo formal de concorrência, com conceitos de mobilidade e distribuição, que pode ser visto de duas formas: como um cálculo de processos e como uma linguagem de programação baseada em técncas de desenvolvimento formal. O formalismo utilizado foi o Distributed Join-Calculus, uma extensão do Join-Calculus com primitivas para mobilidade e localidades explícitas. O protocolo escolhido para a especificação foi o RDP (Result Delivery Protocol). Implementando o modelo para RDP, no Distributed Join-Calculus, em relação às características de mobilidade, analisamos e verificamos se algumas das propriedades esperadas pelo protocolo RDP são atendidas. Além disso, analisamos o uso do Distributed Join-Calculus com relação à especificação do protocolo e às dificuldades de se especificar um protocolo de mobilidade. Para isso, o nosso trabalho foi dividido em três fases: a especificação de um modelo simples e restrito das características de mobilidade do protocolo RDP, para um melhor entendimento do seu funcionamento e das propriedades que analisamos, a especificação deste protocolo de forma global, e a análise final com a verificação de algumas propriedades

Problemas de alinhamento de cadeias são fundamentais em aplicações diversas, das quais se destacam as relacionadas à Biologia Molecular. O alinhamento de duas cadeias A e B indica quão semelhantes elas são ou quais operações são necessárias para transformar uma em outra. Uma variação do problema de alinhamento de cadeias envolve comparar a cadeia A com todas as subcadeias de B. Para este problema, são conhecidos algoritmos seuqenciais que o resolvem em tempo O(|A||B|log(|A|+|B|)), um dos quais é apresentado nesta tese. É também apresentado um algoritmo seqüencial de tempo O(|A||B|) para um caso especial de alinhamento de todas as subcadeias, que envolve a busca pela maior subseqüência comum a duas cadeias. Propomos novos algoritmos paralelos para estes problemas, utilizando um modelo próprio para máquinas de memória distribuída, o CGM (Coarse Grained Multicomputers). Um dos objetivos fundamentais no desenvolvimento de algoritmos CGM é a redução do número de rodadas de comunicação, se possível tornando-o dependente apenas do número de processadores (p). Os algoritmos aqui propostos apresentam aceleração (speed-up) linear e apenas O(log p) etapas de comunicação. Não há algoritmos do nosso conhecimento com tais características na literatura

Os sistemas de data warehouse comerciais (SDWC) IND.1 disponibilizam técnicas de armazenamento de dados para acesso eficiente e facilidades de consultas para o usuário final. As aplicações de SWDC possuem operações clássicas de sincronismo de dados, que não exigem uma atualização imediata dos dados replicados. Entretanto, com a evolução da representação semântica dos dados em ambiente de banco de dados operacionais, as análise realizadas no SWDC requerem novas necessidades de sincronismo. Assim, existe um crescente interesse em SWDC que possam absorver rapidamente as atualizações do banco de dados operacional sem comprometer o processo de consulta aos dados armazenados no ambiente analítico. Com esses novos sistemas, o tempo de atualização dos dados entre o ambiente analítico e o ambiente operacional deve ser reduzido. Nossa pesquisa objetiva a caracterização dos limites dos algoritmos síncronos e assíncronos para atualização de dados em SDWC. Tal caracterização gerou subsídios para a criação de um processo simplificado de propagação das atualizações no SDWC

O advento da computação móvel e o uso de bancos de dados autonômos têm suprido a crescente demanda de recursos computacionais para apoio às bases de dados assíncronas. Mesmo em condições de isolamento de comunicação, os bancos de dados autônomos permitem a comunicação entre os dados por meio de armazenamento de cópias de dados locais, as quais foram obtidas previamente por processos de replicação de dados. Em relação a essa cópia local são permitidas operações de leitura e escrita sobre os dados. Essas operações devem ser repassadas às demais instâncias de banco de dados. Nos ambientes tradicionais também existem justificativas para o uso de banco de dados autonômo. Um exemplo é o incremento da segurança para possíveis falhas de comunicação entre as instâncias dos bancos de dados. Em tais ocorrências de falhas de comunicação, o acesso ao banco de dados torna-se o local para registro das transações pendentes. As transações registradas são propagadas para as demais instâncias após o restabelecimento da comunicação. Nossa proposta apresenta uma alternativa para utilização de instâncias de bases de dados, de modo a permitir a integração de transações conflitantes realizadas sobre réplicas de dados. Este trabalho tem como hipótese de solução a parametrização de transações, de acordo com o conjunto de regras do domínio de aplicação, para diminuir o conflito entre transações postergadas

Um dos grandes desafios atuais na área de Biologia Molecular Computacional é a manipulação de estruturas heterogêneas. Basicamente, podemos dividir este ambiente heterogêneo em dois conjuntos semanticamente distintos: dados e aplicações. A heterogeneidade de dados é representada pela variação estrutural das fontes de dados que armazenam informações biológicas. O crescente volume de dados, sem padronização, tem dificultado cada vez mais a elaboração de estudos conclusivos. A heterogeneidade de aplicações trata as diferenças semânticas e estruturais de um conjunto de implementações algorítimicas (aplicações) utilizadas nas análises dos dados. Nossa pesquisa apresenta uma alternativa para integração de dados e aplicações que usa um ambiente para controle automatizado de um fluxo de execução. Tal controle otimiza o processo computacional de descoberta de conhecimento. Definimos nesse trabalho um metadados para a integração e gerenciamento de dados heterogêneos. Para controlar a heterogeneidade das aplicações definimos um conjunto de operadores para criar um fluxo consecutivo mencionado neste trabalho de gen-pipe

Esta tese aborda o desenvolvimento de software adaptativo, capaz de modificar o seu comportamento dinamicamente em resposta a variações detectadas em seu ambiente de execução. A demanda por software adaptativo tem sido impulsionada por recentes avanços nas áreas de computação distribuída, móvel e ubíqua caracterizadas por um ambiente de execução com um alto grau de dinamismo. O desenvolvimento de aplicações adaptativas é bastante complexo. Os desenvolvedores devem levar em consideração diversas questões além da implementação do comportamento funcional da aplicação. Estas questões incluem a escolha de quais elementos do ambiente de execução devem ser monitorados, como realizar este monitoramento, que ações de adaptação devem ser realizadas e quando elas devem ser executadas. A complexidade inerente ao processo de desenvolvimento de aplicações distribuídas adaptativas é abordada através da proposição de um modelo para construção desta classe de aplicações. Tendo por base este modelo, foi implementado um arcabouço que simplifica o processo de desenvovimento, disponibilizando ferramentas para a monitoração do ambiente de execução, detecção de mudanças no mesmo e reconfiguração dos componentes da aplicação. Descreve-se o modelo e a implementação do arcabouço, bem como resultados experimentais obtidos através da construção de uma aplicação distribuída adaptativa para a disseminação de informações a clientes móveis. Os resultados dos testes reforçam a aplicabilidade do arcabouço, além de evidenciar a importância de levarmos em consideração a análise das interações entre os componentes da aplicação como forma de identificar a necessidade de reconfiguração da mesma

Neste trabalho, estudamos o método estatístico de Maximização de Entropia, exemplificando o seu uso para resolução do problema lingüístico da Análise Morfossintática. Desta forma procuramos tornar o mesmo mais fácil de ser entendido e implementado para outros problemas de aprendizado computacional. Para tanto, o algoritmo de Maximização de Entropia é caracterizado como um método de aprendizado computacional, explicado e matematicamente definido. Em seguida é aplicado ao problema da Análise Morfossintática usando o Corpus Tycho Brahe como base de treinamento, seus resultados são comparados com os obtidos pelo método de Brill já aplicado ao mesmo Corpus e comparado com os resultados obtidos pelo mesmo método, porém aplicado ao Inglês

Com a popularização do computador, a necesidade pelos mais diversos tipos de softwares se multiplicou fazendo com que o proceso de desenvolvimento de sistemas e aplicações se tornasse necessariamente mais ágil. A tecnologia de componentes trouxe essa agilidade necesária ao possibilitar a reutilização de código, de uma forma organizada e simples, favorecendo a construção de sistemas complexos simplesmente encaixando-se `componentes de prateleira` uns aos outros. Tecnologias de programação distribuídas e arquiteturas de servidores baseados em componentes surgiram para auxiliar ainda mais nesse desenvolvimento. Contudo não solucionaram todos os problemas, ainda continuaram existindo dificuldades de desenvolvimento de softwares confiáveis, eficientes e dinamicamente configuráveis baseados em componentes. Alguns trabalhos surgiram mostrando como a representação das dependências entre os componentes auxilia na construção de softwares mais confiáveis, eficientes e dinamicamente configuráveis. Nessa dissertação, mostramos esses trabalhos e suas características. Também transportamos o arcabouço (framework) de um desses trabalhos para plataforma Enterprise JavaBeans (EJB) mostrando sua viabilidade também nessa plataforma. Outra contribuição dessa dissertação é a extensão do arcabouço de forma a possibilitar a utilização de operadores booleanos na descrição das dependências e a utilização dos serviços de nomes e diretórios na resolução das dependências

Neste trabalho discutimos os principais modelos de computação paralela e apresentamos, como principal foco do trabalho, soluções para alguns problemas em classes especiais de grafos usando modelos de granularidade grossa que acreditamos sirvam de reflexão para a validação de tais modelos. Tratamos alguns problemas em grafos bipartidos convexos. Estes problemas são: encontrar um emparelhamento máximo, encontrar um conjunto independente máximo, determinar um circuito hamiltoniano e determinar os caminhos mínimos entre todos os pares de vértices em grafos bipartidos biconvexos. Relatamos os resultados experimentais da implementação de alguns dos algoritmos apresentados. Como principais contribuições, descrevemos uma adaptação para o Modelo BSP/CGM de um algoritmo PRAM para encontrar uma coloração em grafos cujo grau máximo é limitado por uma constante, fazemos uma correção no algoritmo BSP/CGM de Bose et al [BCDL99] para encontrar um emparelhamento máximo em grafos bipartidos convexos, descrevemos um novo algoritmo seqüencial para encontrar um conjunto independente máximo nesta classe de grafo e estendemos a idéia deste algoritmo formulando um algoritmo para o modelo BSP/CGM, e desenvolvemos um algoritmo seqüencial linear para encontrar um circuito hamiltoniano de fácil paralelização nesta mesma classe

Em um ambiente tradicional de Computação Móvel, as unidades móveis se comunicam através de comunicação sem fio com bases, que por sua vez estão ligadas à rede fixa. Um processo denominado alocação de canais disponibiliza recursos para que uma unidade móvel possa se conectar à rede. Uma célula é uma área geográfica atendida por um transmissor, ou melhor, por uma estação base de rádio. Em uma região podem ser instaladas mais de uma estação, ocasionando a sobreposição de células. Quando uma unidade em movimento atravessa a região de fronteira entre estações base adjacentes, ela ativa um processo chamado hand-off, que negocia a transição desta unidade para a nova base. Em grande parte dos trabalhos da literatura, as áreas de cobertura das bases são consideradas disjuntas. Entretanto, existem áreas de inserção onde sinais de mais de uma base estão disponíveis. Nós propomos novas políticas onde o hand-off também pode ser realizado por iniciativa das bases, ou seja, a decisão de transferir uma unidade móvel, em uma área de intersecção, também fica a cargo da base que está responsável por ela. Este trabalho apresenta algumas estratégias para repartir as unidades móveis ativas em áreas de intersecção entre as bases, de forma a aproveitar melhor os recursos disponíveis

O objetivo do presente trabalho é a identificação de sistemas dinâmicos finitos, nos quais o tempo é considerado discreto à escala de valores discreta e finita. Estes sistemas modelam adequadamente a evolução temporal dos graus de ativação dos genes numa rede de expressão gênica (REG). Os genes que integram uma rede deste tipo são segmentados de DNA que codificam proteínas específicas. A expressão gênica consiste de dois passos: i) transcrição da informação codificada no DNA em moléculas de RNA e ii) tradução da informação codificada no mRNA (um dos tipos de RNA sintetizados no passo anterior) em uma seqüência definida de aminoácios de uma proteína. As proteínas produzidas, como conseqüência da expressão gênica, formam complexos multiproteicos inter-atuantes os quais enviam sinais ao núcleo da célula para mudar os padrões da expressão gênica. Assim, os genes formam uma rede, que é chamada de expressão gênica, na qual o grau de ativação (ou nível de expressão) de cada gene depende dos níveis de expressão dele mesmo e de outros genes em instantes anteriores, e de estímulos externos. O estado de um sistema dinâmico finito num instante de tempo é definido pelo valor de um vetor de variáveis chamadas de variáveis de estado, no caso de uma REG, o nível de expressão de cada gene. O valor de uma variável de estado num instante de tempo depende dos estados anteriores e de estímulos externos em instantes anteriores. As transições de estado são definidas pela função de transição do sistema, que é na verdade um vetor de funções cujas componentes determinam as transições de cada variável de estado. Foram realizadas a modelagem e simulação do ciclo celular hipotético, a partir de fatos conhecidos e conjecturas sobre a dinâmica desse fenômeno. Para testar técnicas de identificação de sistemas, foi simulado também um sistema mais simples, sem vínculo co fenômenos biológicos. A partir de amostras incompletas das transições de ) estado destas simulações, foi realizada a identificação do sistema dinâmico por técnicas de aprendizado computacional. Tal identificação consiste em achar as componentes da função de transição. Também foi efetuada a identificação com a aplicação de restrição de envelope dinâmico (limite inferior e superior das dinâmicas). Finalmente, ambos os sistemas identificados (com e sem restrição de envelope) foram simulados e comparados com as respectivas simulações do sistema ideal, medindo-se os erros de estimação. Também foi desenvolvida uma técnica de geração automática de árvores de classificação por multirresolução, a qual poderá vir a ser aplicada no futuro à identificação de sistemas dinâmicos finitos

O problema da planaridade consiste em: dado um grafo G, decidir se G é ou não é planar. A resposta deve vir acompanhada de uma justificativa. Se G é planar, então uma justificativa é uma representação de um desenho de G no plano sem cruzamento de arestas. Se G não é planar, então uma justificativa é uma subdivisão do 'K IND.3,3' ou do 'K IND. 5' em G. Existem vários algoritmos lineares para testar planaridade. Dois deles são bem conhecidos: o algoritmo proposto por Auslander e Parter [1], posteriormente corrigido por Goldstein [9] (APG), e o algoritmo proposto por Lempel, Even e Cederbaum [12] (LEC). Hopcroft e Tarjan [10] apresentaram em 1974 a primeira implementação linear do algoritmo de APG. Pouco depois, Booth e Lueker apresentaram uma implementação linear do algoritmo de LEC, introduzindo uma nova estrutura de dados chamada PQ-árvore. Recentemente, Shih e Hsu [15] e Boyer e Myrvold [3] publicaram duas implementações lineares do algoritmo de LEC que evitam o uso da PQ-árvore. Este trabalho apresenta uma descrição do algoritmo de LEC e uma descrição da implementação de Shih e Hsu, bem como um estudo comparativo desta implementação com as implementações de Hopcroft e Tarjan, Booth e Lueker e de Boyer e Myrvold

Neste trabalho, reavaliamos o uso do cache comprimido adaptativo para melhorar o desempenho do sistema através da redução dos acessos aos dispositivos secundários de armazenamento. Nós propomos uma nova política de adaptabilidade que ajusta o tamanho do cache comprimido em tempo de execução, e avaliamos o sistema de cache comprimido com essa política através de uma implementação em um sistema operacional amplamente usado, o Linux. Também reprojetamos o cache comprimido de modo a prover melhoras de desempenho para todos os workloads testados e acreditamos que ele aborde os problemas encontrados em trabalhos e implementações anteriores. Entre essas modificações fundamentais, o nosso cache comprimido é o primeiro a também comprimir páginas do cache de arquivos e a desabilitar adaptativamente a compressão de páginas limpas quando necessário. Testamos um sistema com o nosso cache comprimido adaptativo com muitos aplicativos e benchmarks, cada um com diferentes pressões de memória. Os resultados mostraram melhoras de desempenho (até 171,4%) em todos eles se há pressão de memória, overhead mínimo (até 0,39%) quando há muito baixa pressão de memória e praticamente nenhum overhead quando não há nenhuma pressão de memória. Acreditamos que esse trabalho mostre que esse projeto de cache comprimido adaptativo deva ser considerado como um efetivo mecanismo para melhoras no desempenho do sistema