Repositório RCAAP

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.

Com o surgimento da criptografia de chave pública, muito esforço foi feito para a criação de protocolos de criptografia e de assinatura que fossem comprovadamente seguros contra indivíduos maliciosos. Existem várias definições de segurança, tanto para protocolos de criptografia como para protocolos de assinatura, e também existem vários modelos de adversários, que simulam um indivíduo malicioso tentando corromper o protocolo. A família de protocolos de assinatura Rabin possui os recordes de velocidade de vericação da assinatura, chegando a ser até 100 vezes mais rápida do que o RSA. Este trabalho apresenta uma redução eficiente de segurança no modelo do oráculo aleatório para uma variante do protocolo de assinatura Rabin descrito por Bernstein, onde não é necessário o uso de nenhuma função para geração de bits pseudo-aleatórios, o que torna o protocolo mais robusto. A redução apresentada é uma redução polinomial e eficiente do problema da fatoração de inteiros para o problema de quebrar o protocolo Principal Rabin-Williams B = 0.

O tema central deste trabalho é o estudo de problemas sobre caminhos mais longos em grafos, de pontos de vista tanto estrutural como algorítmico. A primeira parte tem como foco o estudo de problemas motivados pela seguinte questão levantada por T. Gallai em 1966: é verdade que em todo grafo conexo existe um vértice comum a todos os seus caminhos mais longos? Hoje, já se conhecem diversos grafos conexos cuja intersecção de todos os seus caminhos mais longos é vazia. Entretanto, existem classes de grafos para as quais a resposta à pergunta de Gallai é afirmativa. Nessa linha, apresentamos alguns resultados da literatura e duas novas classes que obtivemos: os grafos exoplanares e as 2-árvores. Motivado por esse problema, nos anos 80, T. Zamfirescu formulou a seguinte pergunta que permanece em aberto: é verdade que em todo grafo conexo existe um vértice comum a quaisquer três de seus caminhos mais longos? Apresentamos, além de alguns resultados conhecidos, uma prova de que a resposta é afirmativa para grafos em que todo bloco não trivial é hamiltoniano. Notamos que esse último resultado e o acima mencionado para grafos exoplanares generalizam um teorema de M. Axenovich (2009) que afirma que quaisquer três caminhos mais longos em um grafo exoplanar têm um vértice em comum. Finalmente, mencionamos alguns outros resultados da literatura relacionados com o tema. Na segunda parte, investigamos o problema de encontrar um caminho mais longo em um grafo. Este problema é NP-difícil para grafos arbitrários. Isto motiva investigações em duas linhas a respeito da busca de tais caminhos. Pode-se procurar classes especiais de grafos para as quais existem algoritmos polinomiais, ou pode-se abrir mão da busca de um caminho mais longo, e projetar um algoritmo eficiente que encontra um caminho cujo comprimento esteja próximo do comprimento de um mais longo. Nesse trabalho estudamos ambas as abordagens e apresentamos alguns resultados da literatura.

A demonstração feita por Erdos da existência de grafos com cintura e número cromático grandes é uma das primeiras aplicações do método probabilístico. Essa demonstração fornece um limite para o número de vértices de um grafo desse tipo, que é exponencial na cintura quando o número cromático é fixado. O foco deste texto, no entanto, são as construções determinísticas de grafos com cintura e número cromático grandes e os números de vértices dos grafos obtidos. As construções elementares conhecidas fornecem apenas grafos com um número Ackermanniano de vértices. O texto começa com uma breve repetição das demonstrações probabilísticas da existência de grafos e hipergrafos com cintura e número cromático grandes. Depois, a busca por construções determinísticas é motivada apresentando-se algumas construções para o caso particular de grafos livres de triângulo e com número cromático grande. São construídos os grafos de Tutte, Zykov, Mycielski e Kneser, os grafos de shift e os de planos projetivos finitos. Os números de vértices dessas construções são computados e comparados. De fato, a construção a partir de planos projetivos finitos tem um número polinomial de vértices. A parte principal do texto são as construções de grafos e hipergrafos com cintura e número cromático grandes. A primeira construção apresentada foi feita por Kriz. Ela foi a primeira construção para grafos com cintura e número cromático grandes que não envolvia hipergrafos. A segunda construção apresentada foi feita por Nesetril e Rödl. Essa construção antecede a de Kriz. Ela utiliza a amalgamação entre grafos e hipergrafos para obter um hipergrafo uniforme com cintura e número cromático grandes. A terceira e última construção apresentada foi encontrada por Alon, Kostochka, Reiniger, West e Zhu. Essa construção consegue obter hipergrafos uniformes com cintura e número cromático grandes diretamente a partir de um grafo, que é uma certa árvore aumentada. Em particular, essa construção obtém grafos com cintura e número cromático grandes sem envolver hipergrafos. Os números de vértices dos hipergrafos obtidos por essas construções são computados e comparados.

As redes de sensores sem fio (RSSF) são compostas por pequenos dispositivos distribuídos em uma região geográfica com a finalidade de monitorar ou interagir com o ambiente. Esse tipo de rede tem sido alvo de grande atenção da comunidade acadêmica e empresarial, dados os avanços das produções científicas e aplicações comerciais. Além disso, há grande potencial para esse modelo de rede, pois há diversos benefícios em se ter muitos dispositivos de baixo custo trabalhando em cooperação e que ainda podem interagir com o mundo real. As RSSFs apresentam novos desafios, até então inexistentes na maioria das redes modernas. A baixa capacidade de processamento dos dispositivos, a limitação do tamanho de um pacote, a baixa taxa de transferência de pacotes, a baixa capacidade da bateria de um dispositivo e o alcance limitado do rádio dificultam ou até inviabilizam muitas implementações de segurança. Neste sentido, há uma grande variedade de protocolos de segurança, os quais tentam fornecer o máximo de propriedades desejadas, como por exemplo autenticidade e confidencialidade de mensagens. Nesta dissertação, analisamos e comparamos dois pares de protocolos de segurança que possuem grande atenção da comunidade. Os protocolos foram analisados com base em seus mecanismos criptográficos e propriedades oferecidas. Além disso, com o uso de um simulador de RSSFs, realizamos experimentos que ajudam a entender o comportamento de dois protocolos, principalmente no que se relaciona com o consumo de energia dos dispositivos sensores.

Os sistemas de integração de dados que usam a arquitetura de data warehouse (DW) têm se tornado cada vez maiores e mais difíceis de gerenciar devido à crescente heterogeneidade das fontes de dados envolvidas. Apesar dos avanços tecnológicos e científicos, os projetos de DW ainda são muito lentos na geração de resultados pragmáticos. Este trabalho busca responder à seguinte questão: como pode ser reduzida a complexidade do desenvolvimento de sistemas de DW que integram dados provenientes de sistemas transacionais heterogêneos? Para isso, apresenta duas contribuições: 1) A criação de diretrizes metodológicas baseadas em ciclos de modelagem conceitual e análise de dados para guiar a construção de um sistema modular de integração de dados. Essas diretrizes foram fundamentais para reduzir a complexidade do desenvolvimento do projeto internacional Retrovirus Epidemiology Donor Study-II (REDS-II), se mostrando adequadas para serem aplicadas em sistemas reais. 2) O desenvolvimento de um método de validação de lotes de dados candidatos a serem incorporados a um sistema integrador, que toma decisões baseado no perfil estatístico desses lotes, e de um projeto de sistema que viabiliza o uso desse método no contexto de sistemas de DW.

O ramo da cinética química estuda modelos que descrevem o comportamento de reações químicas. Para que o modelo se comporte como esperado e seja válido, é preciso que seus coeficientes de taxa de reação estejam de acordo com a realidade do fenômeno. Nesse contexto, o trabalho apresenta novas formas de realizar a estimação desses valores. Problemas de estimação de parâmetros, também denominados Problemas Inversos, são, especialmente nessa área, notoriamente difíceis por conta do mal condicionamento e não convexidade da superfície a ser otimizada. Propomos um novo método que leva em consideração propriedades das Equações Diferenciais Ordinárias, incorporando técnicas de integração numérica ao estimador. Essa abordagem visa suavizar a superfície de otimização, facilitando a convergência a seu mínimo global. Intitulado Data Shooting, verificamos que seu custo computacional supera em até 4 ordens de magnitude a alternativa clássica, denominada Single Shooting. Sua acurácia, por outro lado, mostra-se inferior para os casos mais complexos. O custo de suavizar a superfície de otimização é a introdução de um viés ao modelo, uma troca conhecida na área de aprendizado de máquina como bias-variance tradeoff. Propomos então a utilização deste método como o primeiro passo em um processo de regularização de duas etapas, desenvolvido na literatura com o objetivo de lidar com o problema de mal condicionamento de Problemas Inversos. Os proponentes deste método mostram que a regularização traz grandes benefícios. Contudo, ressaltam que para fazer uso desse método os pesquisadores devem ter a priori bons valores de referência para os parâmetros que desejam estimar. Infelizmente isso nem sempre é possível na prática. Desse modo, o segundo método desenvolvido, intitulado Data to Single Shooting, consiste em utilizar os valores estimados através do método Data Shooting, em uma primeira etapa, como os valores de referência na regularização de Tikhonov do método Single Shooting, na segunda. Mesmo não obtendo resultados tão precisos quanto a alternativa clássica em alguns dos casos de teste selecionados, o Data Shooting consegue evitar ficar preso em mínimos locais presentes na superfície gerada pelo Single Shooting, gerando portanto boas estimativas iniciais e de forma eficiente. Os resultados obtidos apontam que o método Data to Single Shooting possui uma boa performance na maioria dos casos, sendo aproximadamente 10% mais rápido que o método clássico no geral. Além disso, esse método proposto consegue solucionar problemas de maior complexidade para os quais o método clássico falha em encontrar uma resposta.