Repositório RCAAP

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.

O estudo da acústica de salas data do início do século XX e, até então, esta atividade era vista quase como uma arte e não como ciência. Foram desenvolvidas teorias, como a acústica geométrica de salas, que tornou o estudo do fenômeno acústico mais facilmente inteligível. Com o advento dos computadores digitais, os pesquisadores da área de acústica, como Asbjørn Krokstad e Manfred Robert Schroeder desenvolveram, em torno de 1960, os primeiros algoritmos para simular o comportamento do campo sonoro dentro de salas. Desde então, vários métodos de simulação acústica foram criados [QIK+08]. Nesta dissertação descrevemos uma implementação funcional do algoritmo de Traçado de Raios na linguagem Java. Explicamos em nosso trabalho os vários métodos de simulação acústica existentes nos dias de hoje e descrevemos os passos necessários para a correta implementação de um algoritmo de traçado de raios. Nossa implementação foi realizada como um módulo do sistema AcMus, uma ferramenta de software livre que reúne, em um único ambiente integrado, medição, análise e, agora, simulação acústica de salas, tornando-se o único software livre existente a integrar essas três funcionalidades em um único ambiente. O módulo de simulação foi implementado como um arcabouço orientado a objetos de forma que outros pesquisadores possam estendê-lo incluindo, com pouco esforço, novos algoritmos de simulação e novas funcionalidades.

O modelo de programação baseado em atores é frequentemente utilizado para o desenvolvimento de grandes aplicações e sistemas. Podemos citar como exemplo o serviço de bate-papo do Facebook ou ainda o WhatsApp. Estes sistemas dão suporte a milhares de usuários conectados simultaneamente levando em conta estritas restrições de desempenho e interatividade. Tais sistemas normalmente são amparados por infraestruturas de hardware com processadores de múltiplos núcleos. Normalmente, máquinas deste porte são baseadas em uma estrutura de memória compartilhada hierarquicamente (NUMA - Non-Uniform Memory Access). Nossa análise dos atuais ambientes de execução para atores e a pesquisa na literatura mostram que poucos estudos sobre a adequação deste ambientes a essas plataformas hierárquicas foram conduzidos. Estes ambientes de execução normalmente assumem que o espaço de memória é uniforme o que pode causar sérios problemas de desempenho. Nesta tese nós estudamos os desafios enfrentados por um ambiente de execução para atores quando da sua execução nestas plataformas. Estudamos particularmente os problemas de gerenciamento de memória, de escalonamento e de balanceamento de carga. Neste documento nós também analisamos e caracterizamos as aplicações baseadas no modelo de atores. Tal análise nos permitiu evidenciar o fato de que a execução de benchmarks e aplicações criam estruturas de comunicação peculiares entre os atores. Tais peculiaridades podem, então, ser utilizadas pelos ambientes de execução para otimizar o seu desempenho. A avaliação dos grafos de comunicação e a implementação da prova de conceito foram feitas utilizando um ambiente de execução real, a máquina virtual da linguagem Erlang. A linguagem Erlang utiliza o modelo de atores para concorrência com uma sintaxe clara e consistente. As modificações que nós efetuamos nesta máquina virtual permitiram uma melhora significativa no desempenho de certas aplicações através de uma melhor afinidade de comunicação entre os atores. O escalonamento e o balanceamento de carga também foram melhorados graças à utilização do conhecimento sobre o comportamento da aplicação e sobre a plataforma de hardware.

Neste trabalho, investigamos uma série de problemas de clustering NP-difíceis. Começamos estudando o problema dos k-centros, também conhecido como k-center, um problema clássico para o qual Gonzalez apresentou em 1985 um algoritmo de aproximação com a melhor garantia de desempenho possível sob a menos que P = NP. Exploramos, em seguida, resultados disponíveis na literatura para diversas generalizações dos k-centros. Para a maioria desses problemas, ainda há espaço para melhorar os resultados conhecidos, seja na garantia de desempenho dos algoritmos ou em melhores resultados de impossibilidade de aproximação (resultados de inaproximabilidade). O trabalho inclui resultados originais obtidos para variantes do problema que combinam as restrições de capacidades dos centros e tolerância a falhas, Tais resultados incluem algoritmos com garantias de desempenho melhores que as dos algoritmos anteriormente descritos na literatura.

Atualmente, observa-se um significativo crescimento na capacidade humana, resultante do emprego generalizado de sistemas computacionais. Consequentemente, têm sido valorizados o raciocínio lógico e o conhecimento de programação de computadores, observando-se, em vários países, iniciativas para sua introdução no ensino formal desde o ciclo fundamental. Nesse contexto, o ensino superior de ciências exatas apresenta um problema. Se de um lado existe uma maior demanda por graduados que saibam programar computadores, de outro a literatura registra uma alta taxa de insucesso em disciplinas de introdução à programação, indicando ainda que isso leva muitos estudantes a se desmotivarem e desistirem de seus cursos. Entretanto, mais recentemente, a literatura também aponta que a adoção de um paradigma de programação visual pode produzir melhores resultados que a programação textual. Este último modelo de programação é baseada na digitação de código, enquanto que no paradigma visual, os aprendizes utilizam recursos visuais como fluxogramas, ícones ou blocos que representam comandos para construírem os algoritmos. Essa abordagem apresenta resultados promissores, inclusive com estudantes do ensino fundamental. Deste modo, uma questão relevante, foco desta dissertação, é saber se, e como, a programação visual difere da textual em termos de esforços empregados pelos estudantes no processo de aprendizagem. Para isso, optou-se por produzir um novo sistema de programação, baseado em duas outras dissertações realizadas no Laboratório de Informática na Educação (LInE) do IME-USP. A primeira gerou o sistema iVProg e a segunda uma Linha de Produto de Software (LPS) em 2010. Após estudos, percebeu-se ser mais eficiente produzir uma nova versão do sistema iVProg baseado na LPS citada do que evoluir o sistema legado. A partir dessa nova versão do iVProg, foi elaborado um experimento para se comparar o modelo de programação textual com o visual. O método empregou o protocolo NASA-TLX para a mensuração da carga de trabalho. Os resultados do experimento sugerem que a abordagem de programação visual demanda menos esforço mental que a programação textual, a partir do que conjectura-se que no modelo visual o aprendiz pode concentrar seus esforços mentais na aprendizagem dos conceitos básicos e fundamentais à programação.

Otimizar simultaneamente os interesses dos usuários, anunciantes e publicadores é um grande desafio na área de publicidade computacional. Mais precisamente, a ordenação de anúncios, ou ad ranking, desempenha um papel central nesse desafio. Por outro lado, nem mesmo as melhores fórmulas ou algoritmos de ordenação são capazes de manter seu status por um longo tempo em um ambiente que está em constante mudança. Neste trabalho, apresentamos uma análise orientada a dados que mostra a importância de combinar diferentes dimensões de publicidade computacional por meio de uma abordagem evolutiva para ordenação de anúncios afim de responder a mudanças de forma mais eficaz. Nós avaliamos as dimensões de valor comercial, desempenho histórico de cliques, interesses dos usuários e a similaridade textual entre o anúncio e a página. Nessa avaliação, nós averiguamos o desempenho e a correlação das diferentes dimensões. Como consequência, nós desenvolvemos uma abordagem evolucionária para combinar essas dimensões. Essa abordagem é composta por três partes: um repositório de configurações para facilitar a implantação e avaliação de experimentos de ordenação; um componente evolucionário de avaliação orientado a dados; e um motor de programação genética para evoluir fórmulas de ordenação de anúncios. Nossa abordagem foi implementada com sucesso em um sistema real de publicidade computacional responsável por processar mais de quatorze bilhões de requisições de anúncio por mês. De acordo com nossos resultados, essas dimensões se complementam e nenhuma delas deve ser neglicenciada. Além disso, nós mostramos que a combinação evolucionária dessas dimensões não só é capaz de superar cada uma individualmente, como também conseguiu alcançar melhores resultados do que métodos estáticos de ordenação de anúncios.

Baseando-se em discussoes relacionadas a simulacao de sistemas quanticos, Feynman sugeriu na decada de 80 a construcao de computadores que pudessem explorar as caracteristicas quanticas da natureza. A consequencia disso foi o inicio do desenvolvimento da teoria de computacao quantica, que consiste num modelo de computacao possivelmente mais poderoso que o modelo classico. O algoritmo de Shor para fatoracao de inteiros reforcou as suspeitas a respeito da superioridade desse modelo. No mesmo periodo, um novo conjunto de ferramentas foi desenvolvido dentro da teoria de complexidade computacional Os sistemas interativos de prova foram introduzidos na decada de 80 e, com eles, muitos resultados importantes foram obtidos, como o teorema PCP. Recentemente, surgiram alguns novos resultados envolvendo sistemas interativos de prova e o modelo qsuantico de computacao. Esta dissertacao apresenta alguns desses resultados com o intuito de evidenciar algumas das potenciais diferencas entre os modelos quanticos e classico de computacao.

Neste trabalho estudamos problemas relacionados com a busca de pontos e segmentos em janelas retangulares com os lados paralelos aos eixos. É dado um conjunto de segmentos (ou pontos) no plano. Em uma primeira fase estes segmentos são organizados em estruturas de dados de tal forma a tornar buscas por aqueles que estão contidos em janelas retangulares mais eficiente. Na segunda fase são dadas as janelas de maneira online. Várias destas estruturas de dados são baseadas em árvores balanceadas, tais como, árvore limite, árvore de busca com prioridade, árvore de intervalos e árvore de segmentos. Na dissertação mostramos detalhadamente estas estruturas de dados e os algoritmos para resolver este problema para conjuntos de pontos (versão unidimensional do problema) e para segmentos no plano, tanto horizontais e verticais como com qualquer orientação (sem cruzamentos). Os algoritmos são analisados de forma rigorosa quanto ao seu uso de espaço e de tempo. Implementamos também os vários algoritmos estudados, construindo uma biblioteca destas estruturas de dados. Apresentamos, finalmente os resultados de experimentos computacionais com instâncias do problema.

The intention of this work is to study problems about transversals of graphs. A transversal of a graph is a set of vertices or edges that intersects every object of some type. We study three types of transversals: of longest paths, of longest cycles, and of triangles. For each such type of transversal, we show upper bounds on the minimum cardinality of a transversal in a given graph class. The problems we study here have a strong connection with two well-known questions in graph theory: Gallais question and Tuzas Conjecture. Gallai asked whether all longest paths in a connected graph intersect. In terms of transversals, Gallai was asking whether there is a transversal of longest paths of cardinality one. Although the answer to this question is negative, it is still open for several classes of graphs. One part of this work is as an attempt to solve Gallais question, and its corresponding analogous question for cycles, on important classes of graphs. In some of these classes we are able to solve the question and in others we present significant advances. Tuza conjectured whether the minimum cardinality of a transversal of triangles is at most twice the cardinality of a maximum packing of triangles, where a packing of triangles is a set of edge-disjoint triangles in a graph. This conjecture is still open and several related advances have been made in the literature. One part of this work is an attempt to solve Tuzas Conjecture for several classes of graphs. For some of these classes we prove the conjecture. For some other classes, the conjecture was already proved, so we show stronger results.

A recuperação de informação é ainda um assunto essencial a melhorar nos diferentes tipos de sistemas web. Um tipo de sistema web que é muito utilizado na atualidade, é o sistema colaborativo. Estes sistemas permitem que os usuários estejam mais envolvidos, seja contribuindo com a inserção de textos, imagens ou dados, assim como utilizando etiquetas (tags) para identificar aos elementos existentes no sistema e que serão compartilhados com outros usuários. Nesta dissertação utilizamos um sistema colaborativo de compartilhamento de imagens arquitetônicas, onde os usuários podem inserir títulos e tags livremente para descrever uma imagem. Contudo as tags podem ter um significado ambíguo, resultando em imagens recuperadas que não são relevantes, quando são utilizadas técnicas tradicionais, como por exemplo busca booleana ou por palavra-chave. Além disso, os usuários podem utilizar consultas mais complexas utilizando uma linguagem livre, e utilizando as técnicas mencionadas podem recuperar informação não relevante. Assim, esta pesquisa aborda, a construção de uma ontologia no domínio arquitetônico denominada OntoArq, baseada no vocabulário controlado da USP e no tesauro experimental de arquitetura brasileira, a qual possibilitou fortalecer a relação entre as tags e os conceitos estruturados da ontologia, por meio de uso de hierarquias de classes e relações semânticas existentes entre as classes. A ontologia também ajudou a melhorar a recuperação de documentos para consultas complexas que utilizam uma linguagem livre, por meio da adição de termos arquitetônicos relacionados à consulta original dada pelo usuário. E quando a consulta expandida é utilizada em conjunto com o modelo de espaço vetorial existente no sistema de recuperação, auxilia na recuperação de imagens mais relevantes. A avaliação de nossa abordagem foi realizada através de experimentos que utilizaram os dados do sistema Arquigrafia, dois conjuntos de consultas e medidas de avaliação como precisão, cobertura e medida-F. Os conjuntos eram compostos por 11 consultas dada por especialistas da área de arquitetura e 9 consultas aleatórias extraídas do log de busca do Google Analytics do sistema Arquigrafia, tendo um total de 20 consultas. Para nossos experimentos utilizamos as 20 consultas que pertenciam aos dois conjuntos de consultas mencionados, dentre os quais obtivemos resultados positivos para 16 consultas, considerando um valor de precisão, cobertura e medida-F maior do que 50%, com nossa abordagem. Em comparação a outra abordagem, que usa a técnica de busca boolena, obteve-se 1 consulta com resultado positivo, também considerando precisão, cobertura e medida-F maior do que 50%. Assim, podemos concluir que nossa abordagem obteve melhores resultados. Além disso, pelos resultados obtidos, consideramos que nossa abordagem, ao utilizar uma ontologia, pode ser um inicio de como empregar as ontologias como ferramenta de apoio para dar um maior significado semântico às tags que existem num sistema colaborativo e como as ontologias permitem a adição de termos na consulta, sendo estes termos relacionados a uma área do conhecimento, que para nosso caso, a área da arquitetura. Desta maneira podemos recuperar os documentos associados às imagens, os quais serão mais relevantes para consulta feita pelo usuário.

In this work we address the Optimal Communication Spanning Tree (OCST) problem. An instance of this problem consists of a tuple (G, c, R, w) composed of a connected graph G = (V, E), a nonnegative cost function c defined on E, a set R of pairs of vertices in V , and a nonnegative function w, called demand, defined on R. Each pair (u, v) of R is called a requirement, the vertex u is called origin, and the vertex v is called destination of the pair. For a given spanning tree T of G, the communication cost of a requirement pair r = (u, v) is defined as the demand w(r) multiplied by the distance between u and v in T (the distance being the sum of the costs of the edges in the path from u to v). In the Optimal Communication Spanning Tree (OCST) problem, we are given an instance (G, c, R, w) and we seek a spanning tree in G that minimizes the overall sum of the communication costs of all requirements in R. This problem was introduced by T. C. Hu in 1974 and is known to be NP-hard. Some of its special cases, not so trivial, can be solved in polynomial time. We address two such special cases of the OCST problem, both restricted to complete graphs. The first one is the Optimum Requirement Spanning Tree (ORST) problem, in which all edges have the same cost (a constant). In this case, an optimal solution is given by a Gomory-Hu tree of a certain associated network. The second one is a special case of the OCST problem, in which all requirements have the same demand. This problem is called Minimum Routing Cost Spanning tree (MRCT) (and is also known as the Optimum Distance Spanning Tree problem). We also study the main mixed integer linear programming (MILP) formulations for the OCST problem. For that, we first study formulations for the spanning tree problem, some purely combinatorial and some based on flows (leading to mixed formulations). Furthermore, we exhibit the computational results of the experiments we conducted with our implementation of a branch-and-cut approach for the different MILP formulations that we studied.

Multi-agent systems (MASs) can be used to model phenomena that can be decomposed into several interacting agents which exist within an environment. In particular, they can be used to model human and animal societies, for the purpose of analysing their properties by computational means. This thesis is concerned with the automated analysis of a particular kind of such social models, namely, those based on behaviourist principles, which contrasts with the more dominant cognitive approaches found in the MAS literature. The hallmark of behaviourist theories is the emphasis on the definition of behaviour in terms of the interaction between agents and their environment. In this manner, not merely re exive actions, but also learning, drives, and emotions can be defined. More specifically, in this thesis we introduce a formal agent architecture (specified with the Z Notation) based on the Behaviour Analysis theory of B. F. Skinner, and provide a suitable formal notion of environment (based on the pi-calculus process algebra) to bring such agents together as an MAS. Simulation is often used to analyse MASs. The techniques involved typically consist in implementing and then simulating a MAS several times to either collect statistics or see what happens through animation. However, simulations can be used in a more verification-oriented manner if one considers that they are actually explorations of large state-spaces. In this thesis we propose a novel verification technique based on this insight, which consists in simulating a MAS in a guided way in order to check whether some hypothesis about it holds or not. To this end, we leverage the prominent position that environments have in the MASs of this thesis: the formal specification of the environment of a MAS serves to compute the possible evolutions of the MAS as a transition system, thereby establishing the state-space to be investigated. In this computation, agents are taken into account by being simulated in order to determine, at each environmental state, what their actions are. Each simulation execution is a sequence of states in this state-space, which is computed on-the-fly, as the simulation progresses. The hypothesis to be investigated, in turn, is given as another transition system, called a simulation purpose, which defines the desirable and undesirable simulations (e.g., \"every time the agent does X, it will do Y later\"). It is then possible to check whether the MAS satisfies the simulation purpose according to a number of precisely defined notions of satisfiability. Algorithmically, this corresponds to building a synchronous product of these two transitions systems (i.e., the MAS\'s and the simulation purpose) on-the-fly and using it to operate a simulator. That is to say, the simulation purpose is used to guide the simulator, so that only the relevant states are actually simulated. By the end of such an algorithm, it delivers either a conclusive or an inconclusive verdict. If conclusive, it becomes known whether the MAS satisfies the simulation purpose with respect to the observations made during simulations. If inconclusive, it is possible to perform some adjustments and try again. In summary, then, in this thesis we provide four novel elements: (i) an agent architecture; (ii) a formal specification of the environment of these agents, so that they can be composed into an MAS; (iii) a structure to describe the property of interest, which we named simulation purpose; and (iv) a technique to formally analyse the resulting MAS with respect to a simulation purpose. These elements are implemented in a tool, called Formally Guided Simulator (FGS). Case studies executable in FGS are provided to illustrate the approach.

Uma das questões mais importantes nas linguagens e arcabouços orientados a aspectos atuais é a expressividade da linguagem ou mecanismo de definição de pointcuts. A expressividade de uma linguagem de pointcuts impacta diretamente a qualidade dos pointcuts, uma propriedade que pode ser decisiva para a eficácia das implementações de aspectos. Neste trabalho, propomos os seletores de pontos de junção como um mecanismo de extensão simples para enriquecer linguagens de pointcut atuais com elementos que fazem o papel de \"novos pointcuts primitivos\". Os seletores de pontos de junção permitem a criação de pointcuts com maior valor semântico. Apesar de existirem mecanismos similares em algumas abordagens existentes, o conceito subjacente não foi claramente definido ou completamente explorado. Apresentamos também uma arquitetura simples para a adição de seletores de pontos de junção a um arcabouço orientado a aspectos existente, e mostramos exemplos do uso de seletores para melhorar a qualidade de pointcuts e facilitar o desenvolvimento de aspectos.

A tecnologia atual não oferece prevenção contra cópia, adulteração ou plágio de uma imagem estática em meio digital sem autorização do verdadeiro autor. Dado que tais mal feitos não podem ser evitados, resta ao criador da obra original lutar a posteriori por seus direitos nos fóruns adequados (no tribunal, por exemplo). Na época da fotografia analógica com filme, o negativo poderia ser utilizado como prova. Hoje este recurso raramente está disponível e se faz necessária uma solução alternativa. A técnica de Marca d´Água é uma das possibilidades criptográficas existentes para apoiar o autor em sua defesa. O principio da Marca d´Água é o encapsulamento de informações relevantes, preferencialmente de forma imperceptível, na imagem a ser protegida. Tais informações, quando extraídas da imagem marcada, devem revelar o verdadeiro autor num processo de disputa. Soluções de Marca d´Água combinada com Criptografia Visual são encontradas na literatura. A principal vantagem deste caminho é a propriedade Imperceptível por segurança perfeita que a Marca d´Água assume quando tratada por Criptografia Visual. O segredo (neste caso, a Marca d´Água) é segmentado via Criptografia Visual em 2 transparências: uma delas é encapsulada na imagem a ser protegida e a outra é mantida pelo verdadeiro autor. Basta a sobreposição de tais transparências para que a Marca d´Água seja revelada. Nesta pesquisa propomos um novo método, denominado MACV, que combina Marca d´Água, Criptografia Visual e um algoritmo de hashing. O MACV apresenta, entre outras, as seguintes propriedades desejáveis de Marca d´Água: imperceptível por segurança perfeita, alta entropia, armazenamento na própria imagem e sem ambiguidade. Veremos em nossa pesquisa bibliográfica que há uma lacuna de soluções que apresentem, simultaneamente, todas estas propriedades. Esta lacuna torna o MACV único em sua categoria.

A computacao paralela, empregada no meio cientifico para resolucao de problemas que de- mandam grande poder computacional, teve nos ultimos anos o surgimento de um novo tipo de comunicacao entre instancias do paralelismo. Trata-se da Comunicacao Unilateral (CUL), onde somente uma instancia realiza a operacao de transferencia de informacoes, e esta ocorre em segundo plano, ao contrario da Comunicacao Bilateral (CBL), onde uma instancia envia a informacao e a outra recebe. Neste contexto se buscou analisar os beneficios que a CUL agrega ao paralelismo de um programa que se utiliza de uma grade nao estruturada em me- moria. Duas formas de apoio ao paralelismo foram utilizadas: uma biblioteca, a \"Message Passing Interface\" (MPI) (especificamente a sua parte que descreve a CUL), e uma extensao a linguagem Fortran, o Coarray Fortran (CAF). A semantica do MPI CUL e mais complexa que a do CAF, mas a do CAF e mais restritiva. Para analisar a semantica e desempenho da CUL foi realizada uma ambientacao utilizando MPI CUL e CAF no paralelismo de um programa simples, denominado jogo da Vida (Game of Life), com grade estruturada e com otimo desempenho paralelo atraves do MPI CBL. Na programacao o MPI CUL se mostrou verborragico (aumento do numero de linhas de codigo) e complexo, principalmente quando se utiliza um controle refinado de sincronismo entre as imagens. Ja o CAF reduziu o nu- mero de linhas de codigo (entre 20% e 40%), e o sincronismo e muito mais simples. Os resultados mostraram uma piora no desempenho no caso do MPI CUL, mas para o CAF o desempenho absoluto foi melhor que a implementacao original ate o numero de nucleos de processamento que compartilham a mesma memoria. Para grades nao estruturadas se utilizou o Ocean Land Atmospheric Model (OLAM), um modelo de simulacao do sistema terrestre com grade baseada em prismas triangulares, paralelizado atraves de MPI CBL. A implementacao da comunicacao por MPI CUL na estrutura do paralelismo existente mos- trou que esta semantica possui alguns pontos que podem prejudicar a programacao, como o tratamento da exposicao de memoria (cada instancia tem uma memoria exposta de tamanho diferente) e como e realizado o sincronismo entre as instancias. Em termos de desempenho as curvas de speed-ups mostraram que o MPI CUL prejudicou o OLAM independentemente da implementacao das bibliotecas ou do equipamento utilizado, com reducao de pelo menos 20% no speed-up para sete ou mais processadores. Assim como no jogo da Vida o MPI com comunicacao unilateral penalizou o desempenho.