Repositório RCAAP

Cell signaling pathways are composed of a set of biochemical reactions that are associated with signal transmission within the cell and its surroundings. From a computational perspective, those pathways are identified through statistical analyses on results from biological assays, in which involved chemical species are quantified. However, once generally it is measured only a few time points for a fraction of the chemical species, to effectively tackle this problem it is required to design and simulate functional dynamic models. Recently, a method was introduced to design functional models, which is based on systematic modifications of an initial model through the inclusion of biochemical reactions, which in turn were obtained from the interactome repository KEGG. Nevertheless, this method presents some shortcomings that impair the estimated model; among them are the incompleteness of the information extracted from KEGG, the absence of rate constants, the usage of sub-optimal search algorithms and an unsatisfactory overfitting penalization. In this work, we propose a new methodology for identification of cell signaling pathways, based on the aforementioned method, with modifications on the cost function that aims to solve the unsatisfactory overfitting penalization. To this end, we use a cost function based on the marginal likelihood of a model producing the observed experimental data. We show how this new cost function automatically penalize complex models, since marginal likelihood approaches tend to select models with intermediate complexity. The new methodology was tested on artificial instances of model selection; for one of the experiments, we solved the model selection problem as a feature selection problem, walking on the space of solutions to get a glance of the surface induced by the defined cost function. With this work, we expect to contribute towards the solution of the cell signaling pathway identification problem, by providing the implementation of a cost function that can be used in a feature selection approach.

A adoção em larga escala de redes de computadores e gerenciadores de banco de dados contribuiu para o surgimento de sistemas de informação complexos. Atualmente, estes sistemas tornaram-se elementos essenciais na vida das pessoas, dando suporte a processos de negócio e serviços corporativos indispensáveis à sociedade, como automação bancária e telefonia. A utilização de componentes na estruturação destes sistemas promove maior qualidade e flexibilidade ao produto e agiliza o processo de desenvolvimento. Entretanto, para que estes benefícios sejam totalmente observados, é fundamental que os provedores de componentes de prateleira projetem especificações precisas, completas e consistentes. Geralmente, as especificações omitem ou negligenciam o comportamento dos componentes nas situações de falha. Desta forma, a utilização de componentes não confiáveis, cujos comportamentos não podem ser inteiramente previstos, compromete seriamente o projeto de sistemas tolerantes a falhas. Uma estratégia para a especificação de componentes tolerantes a falhas é informar a ocorrência de erros através de exceções e realizar a recuperação dos mesmos por rotinas de tratamento correspondentes. A especificação deve separar claramente o comportamento normal do excepcional, destinado à recuperação do erro. Entretanto, em sistemas concorrentes e distribuídos, a especificação apenas deste tratamento local não é suficiente. Uma exceção pode ser lançada em decorrência de erros sistêmicos (i.e. problemas de rede) que afetam todo o sistema. Assim, determinadas exceções devem ser tratadas em nível arquitetural, envolvendo os demais componentes no tratamento. O modelo conceitual de ações Atômicas Coordenadas (ações CA - Coordinated Atomic actions), bastante aplicado na estruturação de sistemas tolerantes a falhas, define um mecanismo geral para a coordenação do tratamento excepcional dos componentes, que cooperam na execução das atividades e competem por recursos compartilhados. Portanto, o modelo de ações CA oferece uma solução potencialmente viável para a especificação do tratamento de exceções em nível arquitetural. Este trabalho propõe um framework para a especificação do tratamento de exceções em nível arquitetural, baseando-se no modelo de aninhamento de ações CA e utilizando a linguagem orientada a eventos CSP (Communicating Sequential Processes). Sua principal característica é prover um protocolo padronizado para a coordenação do tratamento de exceções, que envolve a cooperação dos componentes do sistema. Além disso, é apresentada uma estratégia para a verificação formal dos sistemas na ferramenta FDR (Failure Divergence Refinement), com base no modelo de refinamento por rastros.

Relações min-max são objetos centrais em otimização combinatória. Elas basicamente afirmam que, numa dada estrutura, o valor ótimo de um certo problema de minimização é igual ao valor ótimo de um outro problema de maximização. Relações desse tipo fornecem boas caracterizações e descrições poliédricas para diversos problemas importantes, além de geralmente virem acompanhadas de algoritmos eficientes para os problemas em questão. Muitas vezes, tais algoritmos eficientes são obtidos naturalmente das provas construtivas dessas relações; mesmo quando isso não ocorre, essas relações revelam o suficiente sobre a estrutura combinatória dos problemas, levando ao desenvolvimento de algoritmos eficientes. O foco principal desta dissertação é o estudo dessas relações em grafos. Nossa ênfase é sobre grafos orientados. Apresentamos o poderoso arcabouço poliédrico de Edmonds e Giles envolvendo fluxos submodulares, bem como o algoritmo de Frank para um caso especial desse arcabouço: o teorema de Lucchesi-Younger. Derivamos também diversas relações min-max sobre o empacotamento de conectores, desde o teorema de ramificações disjuntas de Edmonds até o teorema de junções disjuntas de Feofiloff-Younger e Schrijver. Apresentamos também uma resenha completa sobre as conjecturas de Woodall e sua versão capacitada, conhecida como conjectura de Edmonds-Giles. Derivamos ainda algumas relações min-max clássicas sobre emparelhamentos, T-junções e S-caminhos. Para tanto, usamos um teorema de Frank, Tardos e Sebö e um arcabouço bastante geral devido a Chudnovsky, Geelen, Gerards, Goddyn, Lohman e Seymour. Ao longo do texto, ilustramos vários aspectos recorrentes, como o uso de ferramentas da combinatória poliédrica, a técnica do descruzamento, o uso de funções submodulares, matróides e propriedades de troca, bem como alguns resultados envolvendo subestruturas proibidas.

Belief Revision addresses the problem of how to change epistemic states, usually represented in the literature by sets of logical sentences. Solid theoretical results were consolidated with the AGM paradigm, which deals with theories (logically closed sets of sentences). After that, the theory was extended to belief bases, that is, arbitrary sets of sentences. Besides all this theoretical framework, AI researchers face serious difficulties when trying to implement belief revision systems. One of the major complications is the closure required by AGM theory, which cannot be easily computed. Even belief bases, which do not require closure, seem to be improper for practical purposes, since their changes are usually very rigid (syntax dependent). Some operations, known as pseudo-contractions, are in the middle ground between belief set change and belief base change. In the present work we have proposed a new pseudo-contraction operation, studied its properties and characterized it. We have also found connections between this operator and some other pseudo-contractions.

A decodificação cerebral ganhou muita atenção durante as últimas décadas. Os primeiros estudosforam baseados em eventos discretos. Recentemente, foram desenvolvidos métodos para decodificarestados cognitivos mais contínuos e puramente subjetivos. Entretanto, todos eles requerem disposi-tivos caros, difíceis de manusear e desconfortáveis para o uso diário. Aqui propomos uma alternativabaseada na frequência cardíaca (FC). Já é bem conhecido que podemos discriminar algumas ativi-dades físicas com base na FC. Entretanto, a questão não intuitiva é: podemos discriminar tarefascognitivas com base na FC? Submetemos 25 sujeitos a quatro tarefas cognitivas: descansar em silên-cio, lembrar dos eventos do dia anterior, cantar e subtrair números. Coletamos o eletrocardiogramaduas vezes para cada indivíduo, separados por aproximadamente uma semana. Para coletar a FC,usamos uma faixa de sensor de tórax comercial utilizada por atletas. Treinamos uma máquina ve-torial de suporte usando os dados coletados no primeiro dia. Depois a validamos no conjunto dedados coletados no segundo dia. Nossos resultados mostram precisão mais significativa do que oque esperamos ao acaso(p <0,001). Dependendo do indivíduo e do conjunto de tarefas cognitivas,obtivemos quase 100% de acurácia. Também verificamos o potencial da FC de ser um biomarcadorpara identificar o indivíduo (acurácia de aproximadamente 18%, p= 0,001). Assim, concluímos quea FC apresenta informações sobre os estados mentais.

A popularização das redes de computadores, o aumento da capacidade computacional e sua utilização para produção musical despertam o interesse na utilização de computadores para comunicação síncrona de conteúdo musical. Esta comunicação pode permitir um novo nível de interatividade entre máquinas e pessoas nos processos de produção musical, incluindo a distribuição de atividades, pessoas e recursos em um ambiente computacional em rede. Neste contexto, este trabalho apresenta uma solução para comunicação síncrona de fluxos de áudio e MIDI em redes de computadores. Além de permitir a comunicação, a solução proposta simplifica a conexão de recursos musicais e permite a integração de sistemas heterogêneos, como diferentes sistemas operacionais, arquiteturas de áudio e formatos de codificação, de forma transparente em um ambiente distribuído. Como meio para alcançar esta solução, mapeamos requisitos e características desejáveis para este domínio de aplicação, a partir da interação com músicos e da análise de ferramentas relacionadas. Com base nestes requisitos e características projetamos uma arquitetura de sistema para o domínio específico de comunicação síncrona de conteúdo musical. Utilizando esta arquitetura como referência, implementamos uma biblioteca que compreende as funcionalidades essenciais para este domínio específico. A fim de integrar esta biblioteca com diferentes bibliotecas de áudio e MIDI, desenvolvemos um conjunto de ferramentas que correspondem aos requisitos propostos e que permite aos usuários a utilização de conexões de rede em diversas ferramentas musicais.

Os efeitos dos dados defeituosos sobre os resultados dos processos analíticos são notórios. Aprimorar a qualidade dos dados exige estabelecer alternativas a partir de vários métodos, técnicas e procedimentos disponíveis. O processo de Avaliação da Qualidade dos Dados - pAQD - provê relevantes insumos na definição da alternativa mais adequada por meio do mapeamento dos defeitos nos dados. Relevantes abordagens computacionais apoiam esse processo. Tais abordagens utilizam métodos quantitativos ou baseados em asserções que usualmente restringem o papel humano a interpretação dos seus resultados. Porém, o pAQD depende do conhecimento do contexto dos dados visto que é impossível confirmar ou refutar a presença de defeitos baseado exclusivamente nos dados. Logo, a supervisão humana é essencial para esse processo. Sistemas de visualização pertencem a uma classe de abordagens supervisionadas que podem tornar visíveis as estruturas dos defeitos nos dados. Apesar do considerável conhecimento sobre o projeto desses sistemas, pouco existe para o domínio da avaliação visual da qualidade dos dados. Isto posto, este trabalho apresenta duas contribuições. A primeira reporta uma taxonomia que descreve os defeitos relacionados aos critérios de qualidade da acuracidade, completude e consistência para dados estruturados e atemporais. Essa taxonomia seguiu uma metodologia que proporcionou a cobertura sistemática e a descrição aprimorada dos defeitos em relação ao estado-da-arte das taxonomias. A segunda contribuição reporta relacionamentos entre propriedades-defeitos que estabelecem que certas propriedades visuais-interativas são mais adequadas para a avaliação visual de certos defeitos em dadas resoluções de dados. Revelados por um estudo de caso múltiplo e exploratório, esses relacionamentos oferecem indicações que reduzem a subjetividade durante o projeto de sistemas de visualização de apoio a avaliação visual da qualidade dos dados.

Muitas relações min-max em otimização combinatória podem ser demonstradas através de total dual integralidade de sistemas lineares. O conceito algébrico de bases de Hilbert foi originalmente introduzido com o objetivo de melhor compreender a estrutura geral dos sistemas totalmente dual integrais. Resultados apresentados posteriormente mostraram que bases de Hilbert também são relevantes para a otimização combinatória em geral e para a caracterização de certas classes de objetos discretos. Entre tais resultados, foram provadas, a partir dessas bases, versões do teorema de Carathéodory para programação inteira. Nesta dissertação, estudamos aspectos estruturais e computacionais de bases de Hilbert e relações destas com programação inteira e otimização combinatória. Em particular, consideramos versões inteiras do teorema de Carathéodory e conjecturas relacionadas.

In this thesis our aim is to study problems concerning path covers of graphs. Let G be a graph and let P be a set of pairwise vertex-disjoint paths in G. We say that P is a path cover if every vertex of G belongs to a path in P. In the minimum path cover problem, one wishes to find a path cover of minimum cardinality. In this problem, known to be NP-hard, the set P may contain trivial (single-vertex) paths. We study the problem of finding a path cover composed only of nontrivial paths. First, we consider the corresponding existence problem, and show how to reduce it to a matching problem. From this reduction, we derive a characterization that allows us to find, in polynomial time, a certificate for both the YES-answer and the NO-answer. When trivial paths are forbidden, for the feasible instances, one may consider either minimizing or maximizing the number of paths in the cover. We show that the minimization problem on feasible instances is computationally equivalent to the minimum path cover problem: their optimum values coincide and they have the same approximation threshold. Moreover, we propose integer linear formulations for these problems and present some experimental results. For the maximization problem, we show that it can be solved in polynomial time. Finally, we also consider a weighted version of the path cover problem, in which we seek for a path cover with minimum or maximum total weight (the number of paths does not matter), and we show that while the first is polynomial, the second is NP-hard. Furthermore, for the maximization case, we show a constant-factor approximation algorithm. We also show that, when the input graph has bounded treewidth, both problems can be solved in linear time. To conclude, we present an integer linear formulation for the case of minimum total weight, and study the polytope obtained when the integrality constraint is relaxed. We show that there are graphs for which this polytope has fractional vertices, and we exhibit some classes of inequalities that are valid for the integral polytope and separate these vertices.

Nesta tese, introduzimos o conceito de sequência convergente de permutações e provamos a existência de um objeto limite para tais sequências. Introduzimos ainda um novo modelo de permutação aleatória baseado em tais objetos e introduzimos um conceito novo de distância entre permutações. Provamos então que sequências de permutações aleatórias são convergentes e provamos a equivalência entre esta noção de convergência e convergência nesta nova distância. Obtemos ainda resultados de amostragem e quase-aleatoriedade para permutações. Provamos também uma caracterização para parâmetros testáveis de permutações.

A segmentação é um passo importante em praticamente todas as tarefas que envolvem processamento de imagens digitais. Devido à variedade de imagens e diferentes necessidades da segmentação, a automação da segmentação não é uma tarefa trivial. Em muitas situações, abordagens interativas, nas quais o usuário pode intervir para guiar o processo de segmentação, são bastante úteis. Abordagens baseadas na transformação watershed mostram-se adequadas para a segmentação interativa de imagens: o watershed a partir de marcadores possibilita que o usuário marque as regiões de interesse na imagem; o watershed hierárquico gera uma hierarquia de partições da imagem sendo analisada, hierarquia na qual o usuário pode navegar facilmente e selecionar uma particular partição (segmentação). Em um trabalho prévio, propomos um método que integra as duas abordagens de forma que o usuário possa combinar os pontos fortes dessas duas formas de interação intercaladamente. Apesar da versatilidade obtida ao se integrar as duas abordagens, as hierarquias construídas dificilmente contêm partições interessantes e o esforço de interação necessário para se obter um resultado desejado pode ser muito elevado. Nesta tese propomos um método, baseado em aprendizagem computacional, que utiliza imagens previamente segmentadas para tentar adaptar uma dada hierarquia de forma que esta contenha partições mais próximas de uma partição de interesse. Na formulação de aprendizagem computacional, diferentes características da imagem são associadas a possíveis contornos de regiões, e esses são classificados como contornos que devem ou não estar presentes na partição final por uma máquina de suporte vetorial previamente treinada. A hierarquia dada é adaptada de forma a conter uma partição que seja consistente com a classificação obtida. Essa abordagem é particularmente interessante em cenários nos quais lotes de imagens similares ou sequências de imagens, como frames em sequências de vídeo ou cortes produzidas por exames de diagnóstico por imagem, precisam ser segmentadas. Nesses casos, é esperado que, a cada nova imagem a ser segmentada, o esforço de interação necessário para se obter a segmentação desejada seja reduzido em relação ao esforço que seria necessário com o uso da hierarquia original. Para não dependermos de experimentos com usuários na avaliação da redução no esforço de interação, propomos e utilizamos um modelo de interação que simula usuários humanos no contexto de segmentação hierárquica. Simulações deste modelo foram comparadas com sequências de interação observadas em experimentos com usuários humanos. Experimentos com diferentes lotes e sequências de imagens mostram que o método é capaz de reduzir o esforço de interação.

A Identificação por radiofrequência (Radio Frequency Identification - RFID) tem revolucionado a forma de identificar objetos, sendo usada desde aplicações de controle de estoques até o processo automatizado de pagamentos. Sua ampla aceitação e aplicabilidade tem estimulado pesquisadores a criar cada vez mais aplicações. Um problema chave da RFID são as colisões que ocorrem na identificação por meio dos protocolos de acesso múltiplo. Como, na prática, um leitor precisa identificar várias etiquetas em sua área de cobertura, algumas etiquetas podem responder ao mesmo tempo o que gera colisões e desperdício de recursos. Por este motivo, torna-se de grande valor um estudo abrangente sobre como melhorar a identificação das etiquetas de modo a reduzir o número de colisões. Além disso, aspectos como consumo de energia e tempo necessário para identificação também devem ser levados em consideração, uma vez que a utilização cada vez maior de dispositivos alimentados à bateria tem sido observada na prática. Esta tese investiga a categoria de protocolos anticolisão denominada Frame Slotted Aloha - FSA, pois é a categoria que possui maior potencial de utilização prática em sistemas RFID. Além disso, as diferentes métricas de análise de desempenho são também analisadas e categorizadas, uma vez que identificou-se que um conjunto de métricas devem ser observadas com o intuito de realizarem-se comparações justas com as propostas da literatura. Descobriu-se que a maioria das propostas não levam em consideração os aspectos chave de tempo e energia, assim como a característica de ser fácil de implementar e baixa complexidade. Esta tese propõe quatro algoritmos que visam diminuir o consumo de energia e o tempo do processo de identificação das etiquetas mantendo-se as características de baixa complexidade e similaridade com o padrão atual EpcGlobal Classe 1 Geração 2 (C1G2). O primeiro mecanismo visa diminuir a quantidade de respostas desnecessárias em cenários de localização e rastreamento. Os demais consistem em três propostas de algoritmos anticolisão para sistemas RFID. Os dois primeiros diferem na forma como o tamanho inicial de quadro é definido e como as colisões são tratadas, representando evoluções progressivas em direção a um melhor desempenho. O terceiro considera a ocorrência do efeito captura, o que traz a necessidade de mudanças no funcionamento do algoritmo anterior. Resultados de simulação mostram que os quatro mecanismos podem melhorar propostas existentes sem aumento de complexidade, resultando consequentemente em diminuição de recursos desperdiçados. Além disso também foram desenvolvidos dois softwares de apoio aos mecanismos propostos: nsRFIDsim e jRFIDsim. O primeiro trata-se de um módulo para o simulador ns-2 que simula um sistema RFID passivo. O segundo implementa uma proposta de benchmark para avaliação de desempenho de algoritmos anticolisão para RFID, visando fornecer para a comunidade científica uma forma padronizada de avaliar este tipo de algoritmo.

Multi-label classification consists of learning a function that is capable of mapping an object to a set of relevant labels. It has applications such as the association of genes with biological functions, semantic classification of scenes and text categorization. Traditional classification (i.e., single-label) is therefore a particular case of multi-label classification in which each object is associated with exactly one label. A successful approach to constructing classifiers is to obtain a probabilistic model of the relation between object attributes and labels. This model can then be used to classify objects, finding the most likely prediction by computing the marginal probability or the most probable explanation (MPE) of the labels given the attributes. Depending on the probabilistic models family chosen, such inferences may be intractable when the number of labels is large. Sum-Product Networks (SPN) are deep probabilistic models, that allow tractable marginal inference. Nevertheless, as with many other probabilistic models, performing MPE inference is NP- hard. Although, SPNs have already been used successfully for traditional classification tasks (i.e. single-label), there is no in-depth investigation on the use of SPNs for Multi-Label classification. In this work we investigate the use of SPNs for Multi-Label classification. We compare several algorithms for learning SPNs combined with different proposed approaches for classification. We show that SPN-based multi-label classifiers are competitive against state-of-the-art classifiers, such as Random k-Labelsets with Support Vector Machine and MPE inference on CutNets, in a collection of benchmark datasets.

Neste trabalho estudamos aspectos algorítmicos do Problema da Cobertura por Sensores. Em linhas gerais, este problema a entrada consiste em uma região a ser monitorada por um conjunto de sensores previamente posicionados, cada qual dotado de bateria com duração limitada, e o objetivo é atribuir a cada sensor um tempo de início, de modo que toda a região seja coberta o maior tempo possível. Focamos nosso estudo no caso unidimensional do problema, chamado Problema da Cobertura de Faixa Restrita, no qual a região a ser monitorada é um intervalo (da reta real). Estudamos diversas variantes, de acordo com os subintervalos que os sensores cobrem (se de tamanhos fixos ou variados), e de acordo com a duração das baterias (se uniformes ou não). Estudamos também o caso preemptivo: quando os sensores podem ser ligados mais de uma vez. Para este último caso, projetamos um algoritmo polinomial bem simples. O Problema da Cobertura de Faixa Restrita é NP-difícil no caso não-preemptivo em que os sensores têm bateria de duração variável. Para este caso, em 2009 Gibson e Varadarajan apresentaram um algoritmo polinomial que provaram ser uma 5-aproximação. Provamos que este algoritmo tem fator de aproximação 4, e mostramos que este fator é justo. Apresentamos também formulações lineares inteiras para este caso, e os resultados computacionais obtidos.

O principal sucesso de aprendizado de máquina profundo está na extração automática de características dos dados, sem a necessidade de um especialista no domínio. Porém, a qualidade desta extração automática está condicionada a uma grande quantidade de dados. Em vista disso, houve uma popularização do uso de transferência de aprendizado (transfer learning) em que redes neurais treinadas em um domínio com muitos dados são transferidas e adaptadas a domínios similares necessitando assim de poucos dados. Essa técnica é amplamente utilizada em tarefas de classificação de imagens, nas quais uma rede neural convolucional (CNN), previamente treinada para uma tarefa origem, tem parte de suas camadas transferidas para uma rede similar e adaptada a uma nova tarefa meta com o uso de poucos dados de treinamento. No entanto, o sucesso das soluções que utilizam transferência de aprendizado depende da complexidade das camadas transferidas: adaptar uma rede com muitos parâmetros para a nova tarefa pode implicar em um alto custo computacional. Para mitigar este problema, investigamos o uso de uma técnica de compressão de modelos conhecida por poda de parâmetros (model prunning) que define diferentes critérios de eliminação de parâmetros de uma rede neural previamente treinada, gerando uma rede mais compacta sem afetar significativamente sua acurácia. Assim, o objetivo deste trabalho é investigar a viabilidade de podar um modelo treinado para uma tarefa origem antes de transferi-lo para outras tarefas meta. Para isso, utilizamos o arcabouço chamado de prune2transfer, que seleciona a melhor poda de parâmetros antes da transferência de aprendizado. Foram realizados experimentos de transferência de aprendizado com a rede VGG-19 para 22 novas tarefas meta usando poda não-estruturada baseada em magnitude e poda estruturada baseada na norma-L1. Também foram realizados experimentos usando um algoritmo de aprendizado por reforço (DQN) para poda estruturada e não-estruturada. Os resultados mostram que, com o uso de um agente de aprendizado por reforço aplicando uma poda não- estruturada, é possível eliminar cerca de 93% dos parâmetros da rede VGG-19 sem afetar sua capacidade de extração de características na tarefa original e nas 22 tarefas investigadas.

Planejamento sob incerteza vem sendo cada vez mais requisitado em aplicações práticas de diversas áreas que eequerem soluções confiáveis para metas complexas. Em vista disso, nos últimos anos, algumas abordagens baseadas no uso de métodos formais para síntese automática de planos têm sido propostas na área de Planejamento em Inteligência Artificial. Entre essas abordagens, planejamento baseado em verificação de modelos tem se mostrado uma opção bastante promissora; entretanto, conforme observamos, a maioria dos trabalhos dentro dessa abordagem baseia-se em CTL e trata apenas problemas de planejamento para metas de alcançabilidade simples (como aquelas consideradas no planejamento clássico). Nessa tese, introduzimos uma classe de metas de planejamento mais expressivas (metas de alcançabilidade estendidas) e mostramos que, para essa classe de metas, a semântica de CTL não é adequada para formalizar algoritmos de síntese (ou validação) de planos. Como forma de contornar essa limitação, propomos uma nova versão de CTL, que denominamos alpha-CTL. Então, a partir da semântica dessa nova lógica, implementamos um verificador de modelos (Vactl), com base no qual implementamos também um planejador (Pactl) capaz de resolver problemas de planejamento para metas de alcançabilidade estendidas, em ambientes não-determinísticos com observabilidade completa. Finalmente, discutimos como garantir a qualidade das soluções quando dispomos de um modelo de ambiente onde as probabilidades das transições causadas pela execução das ações são conhecidas.

Hermes é um arcabouço para a programação de aplicações P2P. Com ele, pode-se criar diversos tipos de aplicações distribuídas, sem se preocupar com a camada de comunicação. O Hermes não é uma implementação de uma rede de sobreposição P2P, e sim uma camada acima das implementações já existentes. O desenvolvedor da aplicação fica isolado da implementação da rede de sobreposição utilizada. Esse isolamento é feito de forma tal que não há limitações quanto à arquitetura de rede utilizada pela implementação, seja ela centralizada, descentralizada, distribuída estruturada ou distribuída não-estruturada. Entre os serviços oferecidos pelo Hermes estão: troca de mensagens, busca, comunicação em grupo e armazenamento distribuído. Geralmente, no início do desenvolvimento de uma aplicação distribuída, tem-se poucas informações sobre o seu tamanho final ou perfil de utilização. O Hermes possibilita ao desenvolvedor da aplicação adiar, até o momento da efetiva implantação do sistema, a decisão sobre qual arquitetura de rede ou qual implementação de rede de sobreposição são as mais apropriadas para suas necessidades. Possibilita também, quando o perfil de utilização muda com o tempo, a troca da implementação utilizada por uma outra que se adeque mais ao novo perfil sem alterações no código da aplicação.

Um Data Warehouse (DW) é um banco de dados centralizado, orientado por assunto, integrado, não volátil e histórico, criado com o objetivo de dar apoio ao processo de tomada de decisão e que estrutura os dados em uma arquitetura analítica bastante distinta da arquitetura relacional utilizada nos bancos de dados transacionais. Construir um DW é um projeto de engenharia bastante complexo pois envolve muitas tecnologias e muitas pessoas, de diferentes equipes, em um grande esforço conjunto para construir esta base central de informações corporativas. O processo tradicional de construção de um DW não utiliza conceitos ágeis e, pelo escopo de desenvolvimento ser grande, pode levar muito tempo até que funcionalidades sejam entregues aos clientes. Os métodos ágeis de engenharia de software são muito usados como uma alternativa aos métodos tradicionais de desenvolvimento e têm diferenciais que trazem muito valor a projetos grandes pois, além de buscar desenvolver versões funcionais em prazos curtos, defendem que todos os sistemas têm a constante necessidade de se adaptar a mudanças. Neste trabalho são aplicadas práticas ágeis no processo tradicional de engenharia de DW para que o desenvolvimento seja realizado em ciclos iterativos curtos, tornando possível o desenvolvimento rápido e evolutivo de um DW com entregas constantes de novas funcionalidades. A contínua evolução deste complexo ambiente analítico é apoiada por conceitos de banco de dados evolutivos e também por fundamentos de métodos ágeis.

A busca de palavras em uma grande coleção de documentos é um problema muito recorrente nos dias de hoje, como a própria utilização dos conhecidos \"motores de busca\" revela. Para que as buscas sejam realizadas em tempo que independa do tamanho da coleção, é necessário que a coleção seja indexada uma única vez. O tamanho destes índices é tipicamente linear no tamanho da coleção de documentos. A compressão de dados é outro recurso bastante utilizado para lidar com o tamanho sempre crescente da coleção de documentos. A intenção deste estudo é aliar a indexação utilizada nas buscas à compressão de dados, verificando alternativas às soluções já propostas e visando melhorias no tempo de resposta das buscas e no consumo de memória utilizada nos índices. A análise das estruturas de índice com os algoritmos de compressão mostra que arquivo invertido por blocos em conjuntos com compressão Huffman por palavras é uma ótima opção para sistemas com restrição de consumo de memória, pois proporciona acesso aleatório e busca comprimida. Neste trabalho também são propostas novas codificações livres de prefixo a fim de melhorar a compressão obtida e capaz de gerar códigos auto-sincronizados, ou seja, com acesso aleatório realmente viável. A vantagem destas novas codificações é que elas eliminam a necessidade de gerar a árvore de codificação Huffman através dos mapeamentos propostos, o que se traduz em economia de memória, codificação mais compacta e menor tempo de processamento. Os resultados obtidos mostram redução de 7% e 9% do tamanho dos arquivos comprimidos com tempos de compressão e descompressão melhores e menor consumo de memória.

No presente trabalho, estudamos alguns conceitos relacionados ao desenvolvimento de programas paralelos, algumas formas de aplicar computação paralela em métodos de otimização contínua e dois métodos que envolvem o uso de otimização. O primeiro método que apresentamos, chamado PUMA (Pointwise Unconstrained Minimization Approach), recupera constantes óticas e espessuras de filmes finos a partir de valores de transmitância. O problema de recuperação é modelado como um problema inverso e resolvido com auxílio de um método de otimização. Através da paralelização do PUMA viabilizamos a recuperação empírica de constantes e espessuras de sistemas compostos por até dois filmes sobrepostos. Relatamos aqui os resultados obtidos e discutimos o desempenho da versão paralela e a qualidade dos resultados obtidos. O segundo método estudado tem o objetivo de obter configurações iniciais de moléculas para simulações de dinâmica molecular e é chamado PACKMOL. O problema de obter uma configuração inicial de moléculas é modelado como um problema de empacotamento e resolvido com o auxílio de um método de otimização. Construímos uma versão paralela do PACKMOL e mostramos os ganhos de desempenho obtidos com a paralelização.