Repositório RCAAP

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.

This work investigates the use of artificially synthesized images as an attempt to reduce the dependency of modern Deep Learning based Object Detection techniques on expensive supervision. In particular, we propose using a big number of synthesized detection samples to pretrain Object Detection architectures before finetuning them on real detection data. As the major contribution of this project, we experimentally demonstrate how this pretraining works as a powerful initialization strategy, allowing the models to achieve competitive results using only a fraction of the original real labeled data. Additionally, in order to synthesize these samples, we propose a synthesis pipeline capable of generating an infinite stream of artificial images paired with bounding box annotations. We demonstrate how it is possible to design such a working synthesis pipeline just using already existing GAN techniques. Moreover, all stages in our synthesis pipeline can be fully trained using only classification images. Therefore, we managed to take advantage of bigger and cheaper classification datasets in order to improve results on the harder and more supervision hungry Object Detection problem. We demonstrate the effectiveness of this pretraining initialization strategy combined with the proposed synthesis pipeline, by performing detection using four real world objects: QR Codes, Faces, Birds and Cars.

Dada a crescente importância da predição de resistência compressiva do cimento para um uso mais eciente de recursos na indústria, literatura recente busca analisar quais modelos estatísticos podem auxiliar o processo indústrial. Esse trabalho documenta a aplicação de técnicas de Deep Learning Bayesiano para a geração de predições temporais robustas e conáveis para a resistência compressiva do cimento. Os resultados mostram que técnicas de Inferência Bayesiana para modelos de Aprendizado Profundo promovem um ganho sensível de acurácia para o problema de predição de RC, com o benefício adicional das características probabilísticas das predições, tornando-as mais seguras para o possível uso no chão de fábrica.

Modern astronomical sky surveys are providing us with a flood of images with unusual characteristics, such as numerous channels, saturated signals, faint signals, uncertainties, and varying signal-to-noise ratios. The complexity and diversity of these images make them an adequate use case for deep convolutional neural networks. Moreover, they yield millions of detected objects whose classes are mostly unknown. Given this context, the main objective of this work is to investigate deep representation learning approaches for multichannel astronomical images, focusing on finding reasonable representations that do not require labeled data and that make use of some domain knowledge. A reasonable representation may be thought of as one that contains enough discriminative information, that can be later used for higher-level tasks such as object classification, outlier detection and clustering. We propose a self-supervised learning approach that makes use of astronomical properties (more specifically, magnitudes) of the objects in order to pretrain deep neural networks with unlabeled data. We choose the task of classifying galaxies, stars and quasars as a baseline for quantifying the quality of the learned representations, and empirically demonstrate that our approach yields results that are better than -- or at least comparable to -- a benchmark RGB model pretrained on ImageNet.

Na atualidade, o interesse pelo uso de ontologias tem sido incrementado. No entanto, o processo de construção pode ser custoso em termos de tempo. Para uma ontologia ser construída, precisa-se de um especialista com conhecimentos de um editor de ontologias. Com a finalidade de reduzir tal processo de construção pelo especialista, analisamos e propomos um método para realizar aprendizado de ontologias (AO) de forma supervisionada. O presente trabalho consiste em uma abordagem combinada de diferentes técnicas no AO. Primeiro, usamos uma técnica estatística chamada C/NC-values, acompanhada da ferramenta Cogroo, para extrair os termos mais representativos do texto. Esses termos são considerados por sua vez como conceitos. Projetamos também uma gramática de restrições (GR), com base na informação linguística do Português, com o objetivo de reconhecer e estabelecer relações entre conceitos. Para poder enriquecer a informação na ontologia, usamos a análise de conceitos formais (ACF) com o objetivo de identificar possíveis superconceitos entre dois conceitos. Finalmente, extraímos ontologias para os textos de três temas, submetendo-as à avaliação dos especialistas na área. Um web site foi feito para tornar o processo de avaliação mais amigável para os avaliadores e usamos o questionário de marcos de características proposto pelo método OntoMetrics. Os resultados mostram que nosso método provê um ponto de partida aceitável para a construção de ontologias.

A presente tese de doutorado insere-se na área de interação pelo olhar. A interação pelo olhar é uma forma de comunicação com o computador utilizando os movimentos oculares do usuário. Pessoas com deficiência física, que não conseguem usar dispositivos convencionais como um teclado e um mouse de computador, podem se beneficiar da interação pelo olhar para se comunicarem e se inserirem na sociedade. Para isso a entrada de texto ou digitação pelo olhar é um recurso importante e assunto principal dessa tese. O instrumento mais comum para entrada de texto pelo olhar consiste de um teclado virtual onde os caracteres são selecionados por tempo de latência. Essa forma de interação, embora simples, sofre de seleções involuntárias (problema conhecido como toque de Midas) se o tempo de latência for curto (menos de 500 ms). Já para tempos de latência mais longos, a interação se torna lenta. Alternativas para entrada de texto pelo olhar são os gestos discretos ou contínuos do olhar. O uso de gestos discretos permite reduzir o toque de Midas, porém o desempenho é inferior ao tempo de latência. Já nos métodos baseados em gestos contínuos, o olhar está sempre preso ao controle da interface. Uma técnica de interação proposta recentemente, chamada de \"alternância entre contextos\", permite reduzir o efeito do toque de Midas, utilizando apenas uma sacada para cada seleção. Além disso, essa técnica permite aos usuários manterem o ritmo de interação sem ajustar nenhum parâmetro na interface. A presente tese de doutorado visa melhorar a usabilidade e experiência dos usuários na interação pelo olhar com teclados virtuais. Os objetivos específicos são: investigar a relação entre a manipulação do contraste dos estímulos visuais e o tempo de reação sacádico para facilitar os movimentos oculares e tornar a interação mais rápida e agradável; propor e investigar novas extensões e aplicações da alternância entre contextos, visando reduzir o toque de Midas e ao mesmo tempo generalizar o método para outras tarefas de navegação e seleção de objetos pelo olhar; e desenvolver novos métodos de entrada de texto pelo olhar para melhorar a velocidade de digitação dos usuários, sem incrementar a carga de trabalho e mantendo a interação simples e fácil de aprender. A avaliação dos novos métodos e modelos propostos foi feita por meio de vários estudos com usuários. Os dados coletados nos estudos, tanto quantitativos quanto qualitativos, foram analisados com métodos estatísticos utilizados na área de interação homem-computador. As contribuições originais apresentadas na presente tese são: a proposta e a avaliação do efeito gap gradiente como feedback visual para facilitar a execução de movimentos sacádicos durante a interação pelo olhar; a proposta e investigação de contextos dinâmicos como extensão da alternância entre contextos, para permitir um melhor aproveitamento da área útil do monitor com uma baixa taxa de erros de seleção, assim como de meta-keys para navegação e execução de comandos de forma geral; e a proposta e a avaliação de AugFix, um novo modelo de feedback visual que melhora a velocidade e a experiência dos usuários na entrada de texto pelo olhar, com aplicação em teclados virtuais baseados nos paradigmas do tempo de latência e a alternância entre contextos.

A graph property P is said to be testable with sample complexity q(\\eps) if, for every \\eps>0, there is a randomized decision algorithm that distinguishes objects satisfying P from graphs ``\\eps-far\'\' from satisfying P, after inspecting a sample of size at most q(\\eps) of the input graph G (in particular, the sample size does not depend on |V(G)|). Although the set of testable graph properties is now well understood, results for general properties P tipically rely on variants of Szemerédi\'s regularity lemma, giving tower-type upper bounds for the sample complexity q(\\eps). Therefore, current research in the area is focused on obtaining better bounds for the sample complexity required to test specific properties P. A (normalized) graph parameter f is said to be estimable with sample complexity q(\\eps) if, for every \\eps>0, there is a randomized algorithm that estimates the parameter f(G) up to an additive error of \\eps, after inspecting a sample of size at most q(\\eps) of the input G. If the graph parameter being estimated is the distance \\dP to a graph property P, Fischer and Newman proved that \\dP is estimable for every testable P, but their proof provides a tower-type upper bound for estimating \\dP, even if P can be efficiently testable. This thesis focuses on getting better upper bounds for the sample complexity required to estimate certain parameters and test certain properties. Our first contribution states that one can test the property of having a partition of size k with any given prescribed pairwise densities with a sample complexity polynomial in \\eps^ and k. This result, which improves upon a previous (exponential in k) bound given by Goldreich, Goldwasser and Ron (1998), is an important tool for achieving our other contributions. Our main contribution shows that if a hereditary property P is testable with sample complexity q(\\eps), then distance \\dP is estimable with sample complexity at most exponential in q(\\eps). In particular, for hereditary properties P known to be be efficiently testable, our method provides much better bounds than the ones relying on Szemerédi\'s regularity lemma. Our techniques also allow one to get more reasonable bounds for estimating other graph parameters. We also prove negative results about testing graph properties described by linear constraints of subgraph densities, which were considered by Goldreich and Shinkar (2016). We conclude this thesis by proving bounds for the complexity of testing that every hereditary property of configurations of points in the plane is testable.

Nos últimos anos, as redes sociais na Web 2.0 vêm ganhando cada vez mais importância para trabalhar e compartilhar ideias. As redes sociais armazenam informações do usuário, como preferências, experiência profissional, dados pessoais e com quem o usuário interage. Essas informações são úteis para diversos fins, como oferecer produtos e serviços personalizados. Com a aparição de cada vez mais redes sociais, surgem problemas como a duplicação de perfis de usuários. Atualmente há algumas técnicas para interoperar as redes sociais, como serviços de autenticação única ou representação padrão para compartilhamento de dados. O objetivo deste trabalho foi realizar um estudo dessas técnicas e tecnologias disponíveis, implementá-las por meio de componentes do Groupware Workbench, e implantar e avaliar os componentes desenvolvidos na rede social Arquigrafia. A avaliação dos componentes foi realizada por meio dos aspectos e questões propostos pelo projeto DataPortability. A avaliação mostrou que as questões diretamente relacionadas com a interoperabilidade técnica e semântica foram respondidas.

Os W-operadores são operadores invariantes por translação e localmente definidos dentro de uma janela W. Devido a sua grande utilidade em análise de imagens, estes operadores foram extensamente pesquisados, sendo que uma abordagem para o seu estudo é a partir da Morfologia Matemática. Uma propriedade interessante de W-operadores é que eles possuem uma sup-decomposição, ou seja, um W-operador pode ser decomposto em termos de uma família de operadores sup-geradores que, por sua vez, são parametrizados por elementos da base desse $W$-operador. No entanto, a sup-decomposição tem uma estrutura intrinsecamente paralela que não permite uma implementação eficiente em máquinas de processamento sequencial. Em um trabalho publicado em 2001, Hashimoto e Barrera formalizaram o problema de transformar a sup-decomposição em decomposições puramente sequenciais como um problema de encontrar soluções discretas de uma equação. Neste texto, estendemos o trabalho desenvolvido por eles. Estudamos e exploramos as propriedades matemáticas do problema, e desenvolvemos estratégias heurísticas para encontrar uma decomposição sequencial de um $W$-operador a partir de sua base que seja eficiente ao ser executado.

Em um problema de natureza hierárquica, o nível mais influente toma certas decisões que afetam o comportamento dos níveis inferiores. Cada decisão do nível mais influente é considerada como fixa pelos níveis inferiores, que, com tais informações, tomam decisões que maximizam seus objetivos. Essas decisões podem influenciar os resultados obtidos pelo nível superior, que, por sua vez, também anseia pela decisão ótima. Em programação matemática, este problema é modelado como um problema de programação em níveis. Neste trabalho, consideramos uma classe particular de problemas de programação em níveis: os problemas de programação matemática em dois níveis. Estudamos uma técnica de resolução que consiste em substituir o problema do nível inferior por suas condições necessárias de primeira ordem, que podem ser formuladas de diversas maneiras, conforme as restrições de complementaridade são modificadas. O novo problema torna-se um problema de programação não linear e pode ser resolvido com algoritmos clássicos de otimização. Com o auxílio de condições de otimalidade de primeira e segunda ordem mostramos as relações entre o problema original e o problema reformulado. Aplicamos a técnica a problemas encontrados na literatura, analisamos o seu comportamento e apresentamos estratégias para eliminar certos inconvenientes encontrados.

O computador tem sido empregado na educação praticamente desde seu surgimento e a literatura tem apontado como vantagens de sua incorporação no processo de ensino-aprendizagem, seu potencial de promoção de interatividade e de resposta rápida (retroação). Mais recentemente, com a grande popularização da Web, o uso de Sistemas Gerenciadores de Cursos (SGC) passou a ser ferramenta necessária para personalizar o aprendizado do aluno e para sintetizar informações ao professor. Além disso os SGC viabilizaram o surgimento de uma grande quantidade de cursos na modalidade de Educação a Distância (EAD). Dentre os SGC um que merece destaque é o Moodle, em função de ser um sistema livre e por adotar uma arquitetura modular que permite a incorporação de novas ferramentas. Entretanto, nota-se atualmente uma carência no Moodle de ferramentas que proporcionem aprendizado interativo e que eventualmente permita retroação imediata. Deste modo, a proposta deste trabalho é o enriquecimento do Moodle, apresentando um novo pacote, o iTarefa, que possibilita o gerenciamento de atividades interativas. O iTarefa possibilita a incorporação de qualquer applet Java, desde que este esteja na forma de um Módulo de Aprendizagem Interativa (iMA). Neste trabalho serão apresentados, além do pacote iTarefa, os resultados de seu uso em disciplina de graduação e alguns minicursos para professores e alunos do ensino fundamental e médio.

Os Métodos Ágeis surgiram no final da década de 90, como uma alternativa aos métodos prescritivos de desenvolvimento de software. Eles propõem uma nova abordagem de desenvolvimento, eliminando gastos com documentação excessiva e burocrática, enfatizando a interação entre as pessoas e as atividades que efetivamente trazem valor ao cliente. Nos últimos anos, diversos princípios e práticas baseados na indústria de manufatura foram incorporadas pelos Métodos Ágeis de desenvolvimento de software. Um dos princípios absorvidos é o de melhorar a eficácia de uma organização através de melhorias globais. Embora este princípio seja bem difundido nos Métodos Ágeis, utilizá-lo não é uma tarefa fácil. Nem sempre é fácil ter uma visão global do processo de desenvolvimento. Além disso, para realizar melhorias globais é necessário descobrir a causa para possíveis problemas, o que também pode ser uma tarefa difícil. Esse trabalho investiga duas abordagens da indústria de manufatura que enxergam uma organização como um sistema no qual todas as partes são inter-relacionadas. Com base nelas, três abordagens de desenvolvimento de software existentes são analisadas. Finalmente, um estudo comparativo foi feito para avaliar as principais características dos métodos de desenvolvimento estudados. Esse estudo estende o trabalho feito por Abrahamssom et al., no livro Agile Software Development: Current Research and Future Directions, avaliando o desempenho dos métodos seguindo o arcabouço proposto pelos mesmos autores.

Os principais objetos de estudo neste trabalho são os números de Ramsey para circuitos e o lema da regularidade de Szemerédi. Dados grafos $L_1, \\ldots, L_k$, o número de Ramsey $R(L_1,\\ldots,L_k)$ é o menor inteiro $N$ tal que, para qualquer coloração com $k$ cores das arestas do grafo completo com $N$ vértices, existe uma cor $i$ para a qual a classe de cor correspondente contém $L_i$ como um subgrafo. Estaremos especialmente interessados no caso em que os grafos $L_i$ são circuitos. Obtemos um resultado original solucionando o caso em que $k=3$ e $L_i$ são circuitos pares de mesmo tamanho.

Em anos recentes, muitos algoritmos bio-inspirados têm surgido para resolver problemas de classificação. Em confirmação a isso, a revista Nature, em 2002, publicou um artigo que já apontava para o ano de 2003 o uso comercial de Sistemas Imunológicos Artificiais para detecção de fraude em instituições financeiras por uma empresa britânica. Apesar disso, não observamos, a luz de nosso conhecimento, nenhuma publicação científica com resultados promissores desde então. Nosso trabalho tratou de aplicar Sistemas Imunológicos Artificiais (AIS) para detecção de fraude em cartões de crédito. Comparamos AIS com os métodos de Árvore de Decisão (DT), Redes Neurais (NN), Redes Bayesianas (BN) e Naive Bayes (NB). Para uma comparação mais justa entre os métodos, busca exaustiva e algoritmo genético (GA) foram utilizados para selecionar um conjunto paramétrico otimizado, no sentido de minimizar o custo de fraude na base de dados de cartões de crédito cedida por um emissor de cartões de crédito brasileiro. Em adição à essa otimização, fizemos também uma análise e busca por parâmetros mais robustos via multi-resolução, estes parâmetros são apresentados neste trabalho. Especificidades de bases de fraude como desbalanceamento de dados e o diferente custo entre falso positivo e negativo foram levadas em conta. Todas as execuções foram realizadas no Weka, um software público e Open Source, e sempre foram utilizadas bases de teste para validação dos classificadores. Os resultados obtidos são consistentes com Maes et al. que mostra que BN são melhores que NN e, embora NN seja um dos métodos mais utilizados hoje, para nossa base de dados e nossas implementações, encontra-se entre os piores métodos. Apesar do resultado pobre usando parâmetros default, AIS obteve o melhor resultado com os parâmetros otimizados pelo GA, o que levou DT e AIS a apresentarem os melhores e mais robustos resultados entre todos os métodos testados.

Neste projeto analisamos jogos de formação de redes que são variantes do problema da floresta de Steiner, nos quais indivíduos desejam conectar conjuntos de vértices terminais em um grafo de forma a minimizar seus custos, podendo dividir o custo das arestas com os demais participantes. Estudamos como o método de divisão de custos influencia na existência e na qualidade dos equilíbrios desses jogos em comparação com o valor da solução ótima centralizada.