RCAAP Repository

As redes sociais se tornaram um novo e importante meio de intercâmbio de informações, ideias e comunicação que aproximam parentes e amigos sem importar as distâncias. Dada a natureza aberta da Internet, as informações podem fluir muito fácil e rápido na população. A rede pode ser representada como um grafo, onde os indivíduos ou organizações são o conjunto de vértices e os relacionamentos ou conexões entre os vértices são o conjunto de arestas. Além disso, as redes sociais representam intrinsecamente a estrutura de um sistema mais complexo que é a sociedade. Estas estruturas estão relacionadas com as características dos indivíduos. Por exemplo, os indivíduos mais populares são aqueles com maior número de conexões. Em particular, é aceito que a estrutura da rede pode afetar a forma como a informação se propaga nas redes sociais. No entanto, ainda não está claro como a estrutura influencia na propagação, como medir seu impacto e quais as possíveis estratégias para controlar o processo de difusão. Nesta tese buscamos contribuir nas análises da interação entre as dinâmicas de propagação de informações e rumores e a estrutura da rede. Propomos um modelo de propagação mais realista considerando a heterogeneidade dos indivíduos na transmissão de ideias ou informações. Nós confirmamos a presença de propagadores mais influentes na dinâmica de rumor e observamos que é possível melhorar ou reduzir expressivamente a difusão de uma informação ao selecionar uma fração muito pequena de propagadores influentes. No caso em que se objetiva selecionar um conjunto de propagadores iniciais que maximizem a difusão de informação, a melhor opção é selecionar os indivíduos mais centrais ou importantes nas comunidades. Porém, se o padrão de conexão dos vértices está negativamente correlacionado, a melhor alternativa é escolher entre os indivíduos mais centrais de toda a rede. Por outro lado, através de abordagens topológicas e de técnicas de aprendizagem máquina, identificamos aos propagadores menos influentes e mostramos que eles atuam como um firewall no processo de difusão. Nós propomos um método adaptativo de reconexão entre os vértices menos influentes para um indivíduo central da rede, sem afetar a distribuição de grau da rede. Aplicando o nosso método em uma pequena fração de propagadores menos influentes, observamos um aumento importante na capacidade de propagação desses vértices e da rede toda. Nossos resultados vêm de uma ampla gama de simulações em conjuntos de dados artificiais e do mundo real e a comparação com modelos clássicos de propagação da literatura. A propagação da informação em redes é de grande relevância para as áreas de publicidade e marketing, educação, campanhas políticas ou de saúde, entre outras. Os resultados desta tese podem ser aplicados e estendidos em diferentes campos de pesquisa como redes biológicas e modelos de comportamento social animal, modelos de propagação de epidemias e na saúde pública, entre outros.

Os Sistemas Distribuídos (SDs) tem apresentado uma crescente complexidade no seu gerenciamento, além de possuir a necessidade de garantir Qualidade de Serviço (QoS) aos seus usuários. A Computação Autonômica (CA) surge como uma forma de transformar os SDs em Sistemas Distribuídos Autonômicos (SDAs), com capacidade de auto-gerenciamento. Entretanto, não foi encontrado um processo de desenvolvimento de software, focado na criação de SDAs. Na grande maioria dos trabalhos relacionados, simplesmente é apresentado um SD, juntamente com qual aspecto da CA deseja-se implementar, a técnica usada e os resultados obtidos. Isso é apenas uma parte do desenvolvimento de um SDA, não abordando desde a definição dos requisitos até a manutenção do software. Mais importante, não mostra como tais requisitos podem ser formalizados e posteriormente solucionados por meio do auto-gerenciamento fornecido pela CA. Esta tese foca na proposta de um processo de desenvolvimento de software voltado para SDAs. Com esse objetivo, foram integradas diferentes áreas de conhecimento, compreendendo: Processo Unificado de Desenvolvimento de Software (PU), SDs, CA, Pesquisa Operacional (PO) e Avaliação de Desempenho de Sistemas Computacionais (ADSC). A prova de conceito foi feita por meio de três estudos de caso, todos focando-se em problemas NP-Difícil, são eles: (i) otimização off-line (problema da mochila com múltiplas escolhas), (ii) otimização online (problema da mochila com múltiplas escolhas) e (iii) criação do módulo planejador de um gerenciador autonômico, visando realizar o escalonamento de requisições (problema de atribuição generalizado). Os resultados do primeiro estudo de caso, mostram que é possível usar PO e ADSC para definir uma arquitetura de base para o SDA em questão, bem como reduzir o tamanho do espaço de busca quando o SDA estiver em execução. O segundo, prova que é possível garantir a QoS do SDA durante sua execução, usando a formalização fornecida pela PO e sua respectiva solução. O terceiro, prova que é possível usar a PO para formalizar o problema de auto-gerenciamento, bem como a ADSC para avaliar diferentes algoritmos ou modelos de arquitetura para o SDA.

A fim de auxiliar usuários durante o consumo de produtos, sistemas Web passaram a incorporar módulos de recomendação de itens. As abordagens mais populares são a baseada em conteúdo, que recomenda itens a partir de características que são do seu interesse, e a filtragem colaborativa, que recomenda itens bem avaliados por usuários com perfis semelhantes ao do usuário alvo, ou que são semelhantes aos que foram bem avaliados pelo usuário alvo. Enquanto que a primeira abordagem apresenta limitações como a sobre-especialização e a análise limitada de conteúdo, a segunda enfrenta problemas como o novo usuário e/ou novo item, também conhecido como partida fria. Apesar da variedade de técnicas disponíveis, um problema comum existente na maioria das abordagens é a falta de informações semânticas para representar os itens do acervo. Trabalhos recentes na área de Sistemas de Recomendação têm estudado a possibilidade de usar bases de conhecimento da Web como fonte de informações semânticas. Contudo, ainda é necessário investigar como usufruir de tais informações e integrá-las de modo eficiente em sistemas de recomendação. Dessa maneira, este trabalho tem o objetivo de investigar como informações semânticas provenientes de bases de conhecimento podem beneficiar sistemas de recomendação por meio da descrição semântica de itens, e como o cálculo da similaridade semântica pode amenizar o desafio enfrentado no cenário de partida fria. Como resultado, obtém-se uma técnica que pode gerar recomendações adequadas ao perfil dos usuários, incluindo itens novos do acervo que sejam relevantes. Pode-se observar uma melhora de até 10% no RMSE, no cenário de partida fria, quando se compara o sistema proposto com o sistema cuja predição de notas é baseada na correlação de notas.

O crescente avanço na geração de dados advindos de várias fontes, tornou necessário o desenvolvimento de métodos de apoio aos processos de gerenciamento de grandes quantidades de dados complexos, como imagens, vídeos e áudios. Entretanto, a ocorrência de falhas durante os processos de coleta e armazenamento dos dados devido a diversas causas resultam na incompletude dos bancos de dados, afetando negativamente a execução de consultas por similaridade em inúmeras tarefas de recuperação de informação. Especificamente em consultas por similaridade, as funções de distâncias tradicionais, como a Euclidiana, não medem a dissimilaridade entre pares de atributos com valores faltantes. Abordagens existentes na literatura lidam com o problema de bases de dados incompletos por meio do descarte de tuplas com valores faltantes, a imputação de valores por meio de várias heurísticas e a indexação de bases de dados incompletos. No entanto, a aplicação do descarte de dados pode ocasionar a redução significativa do conjunto de dados, imputações de valores podem introduzir distorções no conjunto de dados e a indexação de dados oferece tratamentos específicos ao tratamento de dados faltante e muitas vezes custoso. O objetivo deste trabalho consiste em extrair informações intrínsecas dos dados para auxiliar na execução de consultas por similaridade sobre bases incompletas, sem o descarte de dados e nem a utilização de um método de imputação de valores. Nesse contexto, este trabalho de mestrado propõe o método SOLID (Search Over Correlated and Incomplete Data), que utiliza a correlação entre pares de espaços métricos definidos por um conjunto de representações para gerar fatores de compatibilidade a partir da identificação de atributos complexos mais correlacionados com relação às ocorrências de objetos com valores faltantes. As consultas por similaridade são executadas por meio de uma função de distância, cuja construção inclui propriedades propostas neste trabalho. Ela aplica os fatores de compatibilidade de acordo com o cenário da falta de dados ocorrida e consolida as distâncias resultantes, reduzindo a influência dos dados faltantes. Uma análise experimental realizada com o SOLID mostra que, para diferentes bases de dados de dimensionalidades e cardinalidades distintas, a correlação entre espaços métricos altamente correlacionados pode auxiliar na redução da influência de dados faltantes ao executar consultas por similaridade. O SOLID é mais de 55% mais preciso do que métodos de imputação ao recuperar tuplas sobre bases que podem até mesmo conter grandes quantidades de dados faltantes (50%), além de executar consultas até 100x mais rápido do que seus concorrentes.

A área de Mineração de Opiniões visa a processar automaticamente textos subjetivos que emitem a crítica do autor a respeito de alguma entidade (como produtos ou serviços). Essa área vem crescendo devido às grandes quantidades de dados produzidos na web, tendo como uma de suas aplicações a Sumarização de Opiniões, em que um sistema gera automaticamente um resumo dos principais comentários a respeito da entidade avaliada. Alguns trabalhos mais recentes propõem abordagens baseadas em análises semânticas mais profundas através do uso de representações semânticas, argumentando que essas análises produzem melhores resultados capazes de lidar com sentimentos e informações implícitas no texto. Entre as representações semânticas existentes na literatura, a Abstract Meaning Representation (AMR) vem ganhando notoriedade por se basear em recursos bem consolidados, como o PropBank, e por ter apresentado bons resultados em diversas tarefas, como a Sumarização Automática. Neste trabalho de mestrado, propõe-se fazer o uso da representação AMR na Mineração de Opinião, mais especificamente aplicada à Sumarização de Opiniões, abordando diferentes frentes de trabalho, como a anotação de um córpus de opiniões em AMR e uma análise dos resultados dessa anotação em comparação a textos jornalísticos, bem como o desenvolvimento de novos métodos de sumarização automática de opiniões baseados em AMR. Como principal resultado, foi possível verificar que o uso das representações semânticas explícitas auxiliou na seleção de informações para os resumos. Além disso, alguns dos novos métodos desenvolvidos se mostraram melhores quando comparados às tecnicas baseadas em AMR já existentes na literatura.

Recursos Educacionais Abertos (REA) podem ser definidos como materiais de ensino, aprendizagem e pesquisa, em qualquer meio de armazenamento, que estão amplamente disponíveis por meio de uma licença aberta que permite reuso, readequação e redistribuição sem restrições ou com restrições limitadas. Atualmente, diversas instituições de ensino e pesquisa têm investido em REA para ampliar o acesso ao conhecimento. Entretanto, os usuários ainda têm dificuldades de encontrar os REA com os mecanismos de busca atuais. Essa dificuldade deve-se principalmente ao fato dos mecanismos de busca na Web serem genéricos, pois buscam informação em qualquer lugar, desde páginas de vendas até materiais escritos por pessoas anônimas. De fato, esses mecanismos não levam em consideração as características intrínsecas de REA, como os diferentes padrões de metadados, repositórios e plataformas existentes, os tipos de licença, a granularidade e a qualidade dos recursos. Esta dissertação apresenta o desenvolvimento de um mecanismo de busca na Web especificamente para recuperação de REA denominado SeeOER. As principais contribuições desta pesquisa de mestrado consistem no desenvolvimento de um mecanismo de busca na Web por REA com diferenciais entre os quais se destacam a resolução de conflitos em nível de esquema oriundos da heterogeneidade dos REA, a busca em repositórios de REA, a consulta sobre a procedência de dados e o desenvolvimento de um crawler efetivo para obtenção de metadados específicos. Além disso, contribui na inclusão de busca de REA no cenário brasileiro, no mapeamento de padrões de metadados para mecanismos de busca na Web e a publicação de uma arquitetura de um mecanismo de busca na Web. Ademais, o SeeOER disponibiliza um serviço que traz um índice invertido de busca que auxilia encontrar REA nos repositórios dispersos na Web. Também foi disponibilizada uma API para buscas que possibilita consultas por palavras chaves e o uso de palavras booleanas. A forma de validação em mecanismos de busca na Web, como um todo, e de forma quantitativa e específica por componentes foi feita em grau de especialidade. Para validação de qualidade foram considerados 10 participantes com grupos distintos de escolaridade e área de estudo. Os resultados quantitativos demonstraram que o SeeOER é superior em 23.618 REA indexados em comparação a 15.955 do Jorum. Em relação à qualidade o SeeOER demonstrou ser superior ao Jorum considerando a função penalizada e o score utilizada nesta pesquisa.

Reconstrução a partir de pontos não organizados é um problema relevante e comum a vários tipos de aplicações, como tratamento de imagens médicas e computação gráfica. Este tipo de abordagem é relativamente recente e busca gerar malhas não estruturadas a partir de conjuntos de pontos geralmente fornecidos por scanners tridimensionais, sondas sísmicas, radares e amostragens de superfícies implícitas. O principal desafio a ser superado neste tipo de reconstrução é a falta de informação, tanto geométrica quanto topológica, a respeito do objeto a ser reconstruído. Essa falta de informação tem impossibilitado a elaboração de algoritmos robustos e eficientes. Diversas técnicas para a resolução deste: problema são descritas na literatura, tais como técnicas baseadas em zeros de funções, em \"esculpimento\", em modelos deformáveis e em métodos incrementais. Cada uma delas possui vantagens e desvantagens. No entanto, a maioria utiliza operações geométricas caras e pouco estáveis. Este projeto de doutorado propõe uma nova abordagem para o problema de reconstrução a partir de pontos não organizados. A abordagem é baseada em \"esculpimento\", e sua principal característica é diminuir a quantidade de operações geométricas, substituindo-as por operações topológicas, mais robustas e mais eficientes. Para isso, a teoria de Morse em complexos simpliciais é utilizada como ferramenta de decisão da inclusão ou não de simplexos na malha do objeto reconstruído. Além disso, apresentam-se garantias teóricas de que, sob uma taxa de amostragem adequada, a reconstrução é homeomorfa e próxima do objeto original. Adicionalmente, esse projeto vem atender as necessidades do grupo de mecânica de fluídos computacional do ICMC-USP, fornecendo um gerador de malhas não estruturadas a partir de pontos não organizados, o qual deverá ser empregado onde técnicas mais convencionais, tais como técnicas de triangulação de politopos e de reconstrução por seções planares, não produzem resultados satisfatórios.

Em domínios de dados complexos (tais como, dados multimídia, sequências genômicas, entre outros), a similaridade entre elementos surge naturalmente como a maneira mais adequada para consultar esses dados. Existem, basicamente, dois tipos de consulta por similaridade: por abrangência e aos k-vizinhos mais próximos. Com o aumento no volume de dados complexos armazenado em Sistemas de Gerenciamento de Bases de Dados (SGBD), também chamados neste trabalho de gerenciadores, torna-se necessário prover suporte a esses tipos de dados. Um modo de dar suporte a tipos de dados complexos nos gerenciadores atuais é incluir consultas por similaridade em seu processador de consultas, e consequentemente, na álgebra relacional. Este fato leva à produção de maneiras para expressar tais consultas na linguagem do gerenciador como predicados em operações de seleção. Como uma consequência, os principais tipos de consultas por similaridade podem ser compostos em expressões mais complexas por meio de conjunções e disjunções booleanas entre eles, isto é, consultas por similaridade complexas. Entretanto, para que um gerenciador processe consultas por similaridade complexas eficientemente, é necessário dar suporte as etapas de otimização e execução na arquitetura do processamento de consultas. Embora diversos trabalhos envolvam o desenvolvimento de algoritmos para responder a uma simples e específica consulta por similaridade, não há um algoritmo genérico apto a manipular eficientemente consultas por similaridade complexas. Além disso, a otimização de consultas por similaridade é um aspecto ainda pouco explorado na literatura. Esta tese propõe um método estruturado de como analisar consultas por similaridade complexas. Esse método é utilizado para estender a álgebra relacional por meio de regras algébricas e determinar um pequeno conjunto de algoritmos que podem ser utilizados para responder a qualquer consulta por similaridade complexa. O método proposto também permite formalizar regras para estimar a seletividade dessas consultas auxiliando na previsão de custo. Para validar os conceitos apresentados, experimentos são realizados com conjuntos de dados reais e sintéticos destacando os resultados obtidos. As regras algébricas, os algoritmos e as métricas para se estimar a seletividade podem ser utilizados por um gerenciador relacional na etapa de otimização, para derivar planos de execução eficientes para consultas por similaridade complexas. Portanto, os aspectos abordados nesta tese contribuem para permitir o uso prático de consultas por similaridade em gerenciadores relacionais.

Several industrial, scientific and commercial processes produce open-ended sequences of observations which are referred to as data streams. We can understand the phenomena responsible for such streams by analyzing data in terms of their inherent recurrences and behavior changes. Recurrences support the inference of more stable models, which are deprecated by behavior changes though. External influences are regarded as the main agent actuacting on the underlying phenomena to produce such modifications along time, such as new investments and market polices impacting on stocks, the human intervention on climate, etc. In the context of Machine Learning, there is a vast research branch interested in investigating the detection of such behavior changes which are also referred to as concept drifts. By detecting drifts, one can indicate the best moments to update modeling, therefore improving prediction results, the understanding and eventually the controlling of other influences governing the data stream. There are two main concept drift detection paradigms: the first based on supervised, and the second on unsupervised learning algorithms. The former faces great issues due to the labeling infeasibility when streams are produced at high frequencies and large volumes. The latter lacks in terms of theoretical foundations to provide detection guarantees. In addition, both paradigms do not adequately represent temporal dependencies among data observations. In this context, we introduce a novel approach to detect concept drifts by tackling two deficiencies of both paradigms: i) the instability involved in data modeling, and ii) the lack of time dependency representation. Our unsupervised approach is motivated by Carlsson and Memolis theoretical framework which ensures a stability property for hierarchical clustering algorithms regarding to data permutation. To take full advantage of such framework, we employed Takens embedding theorem to make data statistically independent after being mapped to phase spaces. Independent data were then grouped using the Permutation-Invariant Single-Linkage Clustering Algorithm (PISL), an adapted version of the agglomerative algorithm Single-Linkage, respecting the stability property proposed by Carlsson and Memoli. Our algorithm outputs dendrograms (seen as data models), which are proven to be equivalent to ultrametric spaces, therefore the detection of concept drifts is possible by comparing consecutive ultrametric spaces using the Gromov-Hausdorff (GH) distance. As result, model divergences are indeed associated to data changes. We performed two main experiments to compare our approach to others from the literature, one considering abrupt and another with gradual changes. Results confirm our approach is capable of detecting concept drifts, both abrupt and gradual ones, however it is more adequate to operate on complicated scenarios. The main contributions of this thesis are: i) the usage of Takens embedding theorem as tool to provide statistical independence to data streams; ii) the implementation of PISL in conjunction with GH (called PISLGH); iii) a comparison of detection algorithms in different scenarios; and, finally, iv) an R package (called streamChaos) that provides tools for processing nonlinear data streams as well as other algorithms to detect concept drifts.

O aprendizado de máquina consiste em conceitos e técnicas que permitem aos computadores melhorar seu desempenho com a experiência, ou em outras palavras, aprender com dados. Duas de suas principais categorias são o aprendizado não-supervisionado e o semissupervisionado, que respectivamente consistem em inferir padrões em bases cujos dados não têm rótulo (classe) e classificar dados em bases parcialmente rotuladas. Embora muito estudado, trata-se de um campo repleto de desafios e com muitos tópicos abertos. Sistemas dinâmicos coletivos, por sua vez, são sistemas constituídos por muitos indivíduos, cada qual um sistema dinâmico por si só, de modo que todos eles agem coletivamente, ou seja, a ação de cada indivíduo é influenciada pela ação dos vizinhos. Uma característica notável desses sistemas é que padrões globais podem surgir espontaneamente das interações locais entre os indivíduos, fenômeno conhecido como emergência. Os desafios intrínsecos e a relevância do tema vêm motivando sua pesquisa em diversos ramos da ciência e da engenharia. Este trabalho de doutorado consiste no desenvolvimento e análise de modelos dinâmicos coletivos para o aprendizado de máquina, especificamente suas categorias não-supervisionada e semissupervisionada. As tarefas de segmentação de imagens e de detecção de comunidades em redes, que de certo modo podem ser entendidas como tarefas do aprendizado de máquina, são também abordadas. Em especial, desenvolvem-se modelos nos quais a movimentação dos objetos é determinada pela localização e velocidade de seus vizinhos. O sistema dinâmico assim modelado é então conduzido a um estado cujo padrão formado por seus indivíduos realça padrões subjacentes do conjunto de dados. Devido ao seu caráter auto-organizável, os modelos aqui desenvolvidos são robustos e as informações geradas durante o processo (valores das variáveis do sistema) são ricas e podem, por exemplo, revelar características para realizar soft labeling e determinar classes sobrepostas.

Nos últimos anos o interesse por plataformas de compartilhamento de conteúdo multimídia na Web, como vídeos, tem crescido consideravelmente e atraindo usuários com diferentes perfis, incluindo pessoas com deficiência visual. Para tais usuários, diretrizes de acessibilidade e usabilidade devem ser aplicadas para que o acesso a estes conteúdos multimídias seja garantido. Apesar de iniciativas como a WCAG 2.0 (Web Content Acessibility Guidelines) definirem diretrizes sobre a acessibilidade para reprodutores de vídeos na Web, usuários com deficiência visual ainda encontram barreiras e dificuldades para acessar este tipo de conteúdo. Em muitos casos reprodutores de vídeo na Web não oferecem total suporte a acessibilidade, dificultando assim o acesso ao conteúdo por tal público, seja por meio de mouse ou de navegação por teclado via leitores de tela. Nesse sentindo, este trabalho teve como objetivo investigar se interações por meios de gestos fornecem melhoria nos níveis de acessibilidade durante o acesso a vídeos na Web realizado por usuários com deficiência visual, a fim de que as barreiras de interação fossem reduzidas ou eliminadas. Inicialmente estudou-se os diferentes tipos de sensores gestuais, bem como se estes sensores poderiam ser utilizados para atingir o objetivo proposto. A partir desses estudos, foi desenvolvido um framework para captura, representação e interpretação de gestos. Em seguida, foi desenvolvido uma aplicação Web, utilizando o framework desenvolvido para viabilizar possíveis testes com usuários. Finalmente, um estudo de caso com 38 usuários com deficiência visual foi conduzido, a fim de levantar indícios que ajudem a entender se a utilização de gestos como modo de interação entre pessoas com deficiência visual e reprodutores de vídeo oferece melhoria de acessibilidade.

Neste trabalho, são simulados escoamentos bifásicos viscoelásticos com a técnica VOF, nos sistemas HIG-FLOW/HIG-TREE, ainda em desenvolvimento no ICMC, para simulação de escoamentos em domínios complexos (compostos por blocos cartesianos), em malhas hierárquicas. Considera-se o clássico modelo Oldroyd-B, para modelar a viscoelasticidade, incorporando-se o módulo bifásico ao sistema HIG-FLOW. Uma série de testes numéricos é realizada e, finalmente são apresentados resultados de simulações envolvendo bolhas, comparando-os com os presentes na literatura.

Esta tese apresenta uma avaliação do desempenho de simulações distribuídas em tempo de execução. Baseando-se nos resultados obtidos nessa avaliação é proposto um mecanismo em que diferentes protocolos de sincronização coexistem em uma mesma simulação. Esse mecanismo tem por objetivo adequar a simulação em execução ao melhor protocolo de sincronização, para garantir melhor desempenho e, conseqüentemente, resultados mais rápidos. Todas as modificações que são necessárias nos protocolos e a definição da troca de mensagens entre os processos são detalhadas neste trabalho. Esta tese apresenta também os resultados dos testes realizados para identificar os casos onde é melhor manter o protocolo conservador ou onde uma troca de protocolo deve ser considerada. Os resultados obtidos são apresentados e mostram em que momento a troca deve ser considerada. Diferentes abordagens podem ser utilizadas para avaliar o desempenho da simulação, considerando cada processo individualmente ou todos os processos globalmente. De maneira análoga, a troca de protocolos pode ser realizada de forma local ou global. Essas considerações permitem a criação de uma taxonomia para a troca de protocolo que também é apresentada nesta tese.

O aumento no número de dispositivos móveis, como smartphones, tablets e laptops, e o avanço em seu potencial computacional permitiu considerá-los como recursos computacionais. O uso de recursos computacionais com maior proximidade vem crescendo ano após ano, sendo chamado de Fog computing, em que os elementos na borda da Internet são explorados, uma vez que os serviços computacionais convencionais podem estar indisponíveis ou sobrecarregados. Dessa forma, este projeto de Mestrado tem como foco possibilitar o uso de dispositivos móveis no provimento de serviços computacionais entre si de forma colaborativa através da heurística Maximum Regret adaptada, que busca alocar tarefas computacionais em dispositivos locais de forma a minimizar o consumo de energia e evitar dispositivos não confiáveis. Também há uma meta-heurística em um nível global, que interconecta os diferentes aglomerados de dispositivos móveis na borda da Internet, e possui informações globais de Quality of Service (QoS). Foram realizados experimentos que mostraram que evitar dispositivos móveis como recursos com um baixo grau de confiabilidade possibilitou diminuir o impacto no consumo de energia, além de ser possível diminuir os tempos de resposta e de comunicação ao ajustar a política de seleção de aglomerados externos.

Diversas aplicações são responsáveis por gerar dados ao longo do tempo de maneira contínua, ordenada e ininterrupta em um ambiente dinâmico, denominados fluxo de dados. Entre possíveis tarefas que podem ser realizadas com estes dados, classificação é uma das mais proeminentes. Devido à natureza não estacionária do ambiente responsável por gerar os dados, as características que descrevem os conceitos das classes do problema de classificação podem se alterar ao longo do tempo. Por isso, classificadores de fluxo de dados requerem constantes atualizações em seus modelos para que a taxa de acerto se mantenha estável ao longo do tempo. Na etapa de atualização a maior parte das abordagens considera que, após a predição de cada exemplo, o seu rótulo correto é imediatamente disponibilizado sem qualquer atraso de tempo (latência nula). Devido aos altos custos do processo de rotulação, os rótulos corretos nem sempre podem ser obtidos para a maior parte dos dados ou são obtidos após um considerável atraso de tempo. No caso mais desafiador, encontram-se as aplicações em que após a etapa de classificação dos exemplos, os seus respectivos rótulos corretos nunca sã disponibilizados para o algoritmo, caso chamado de latência extrema. Neste cenário, não é possível o uso de abordagens tradicionais, sendo necessário o desenvolvimento de novos métodos que sejam capazes de manter um modelo de classificação atualizado mesmo na ausência de dados rotulados. Nesta tese, além de discutir o problema de latência na tarefa de classificação de fluxo de dados não estacionários, negligenciado por boa parte da literatura, também sã propostos dois algoritmos denominados SCARGC e MClassification para o cenário de latência extrema. Ambas as propostas se baseiam no uso de técnicas de agrupamento para a adaptação à mudanças de maneira não supervisionada. Os algoritmos propostos são intuitivos, simples e apresentam resultados superiores ou equivalentes a outros algoritmos da literatura em avaliações com dados sintéticos e reais, tanto em termos de acurácia de classificação como em tempo computacional. Aléem de buscar o avanço no estado-da-arte na área de aprendizado em fluxo de dados, este trabalho também apresenta contribuições para uma importante aplicação tecnológica com impacto social e na saúde pública. Especificamente, explorou-se um sensor óptico para a identificação automática de espécies de insetos a partir da análise de informações provenientes do batimento de asas dos insetos. Para a descrição dos dados, foi verificado que os coeficientes Mel-cepstrais apresentaram os melhores resultados entre as diferentes técnicas de processamento digital de sinais avaliadas. Este sensor é um exemplo concreto de aplicação responsável por gerar um fluxo de dados em que é necessário realizar classificações em tempo real. Durante a etapa de classificação, este sensor exige a adaptação a possíveis variações em condições ambientais, responsáveis por alterar o comportamento dos insetos ao longo do tempo. Para lidar com este problema, é proposto um Sistema com Múltiplos Classificadores que realiza a seleção dinâmica do classificador mais adequado de acordo com características de cada exemplo de teste. Em avaliações com mudanças pouco significativas nas condições ambientais, foi possível obter uma acurácia de classificação próxima de 90%, no cenário com múltiplas classes e, cerca de 95% para a identificação da espécie Aedes aegypti, considerando o treinamento com uma única classe. No cenário com mudanças significativas nos dados, foi possível obter 91% de acurácia em um problema com 5 classes e 96% para a classificação de insetos vetores de importantes doenças como dengue e zika vírus.

Nesse trabalho, estudamos um problema de otimização combinatorial conhecido por Problema da Mochila Compartimentada, que é uma extensão do clássico Problema da Mochila. O problema consiste em determinar as capacidades adequadas de vários compartimentos que podem vir a ser alocados em uma mochila e como esses compartimentos devem ser carregados, respeitando as restrições de capacidades dos compartimentos e da mochila. Busca-se maximizar o valor de utilidade total. O problema é muito pouco estudado na literatura, apesar de surgir naturalmente em aplicações práticas. Nesse estudo, propomos uma modelagem matemática não linear para o problema e verificamos algumas heurísticas para sua resolução.

Este trabalho propõe o desenvolvimento de Algoritmos Evolutivos (AEs) para estimação dos parâmetros que modelam sinais elétricos (frequência, fase e amplitude) em tempo-real. A abordagem proposta deve ser robusta a ruídos e harmônicos em sinais distorcidos, por exemplo devido à presença de faltas na rede elétrica. AEs mostram vantagens para lidar com tais tipos de sinais. Por outro lado, esses algoritmos quando implementados em software não possibilitam respostas em tempo-real para uso da estimação como relé de frequência ou Unidade de Medição Fasorial. O desenvolvimento em FPGA apresentado nesse trabalho torna possível paralelizar o cálculo da estimação em hardware, viabilizando AEs para análise de sinal elétrico em tempo real. Além disso, mostra-se que AEs multiobjetivos podem extrair informações não evidentes das três fases do sistema e estimar os parâmetros adequadamente mesmo em casos em que as estimativas por fase divirjam entre si. Em outras palavras, as duas principais contribuições computacionais são: a paralelização do AE em hardware por meio de seu desenvolvimento em um circuito de FPGA otimizado a nível de operações lógicas básicas e a modelagem multiobjetiva do problema possibilitando análises dos sinais de cada fase, tanto independentemente quanto de forma agregada. Resultados experimentais mostram superioridade do método proposto em relação ao estimador baseado em transformada de Fourier para determinação de frequência e fase

A atenção voltada à produção de conteúdos 3D atualmente tem sido alta, em grande parte devido à aceitação e à manifestação de interesse do público para esta tecnologia. Isso reflete num maior investimento das indústrias cinematográfica, de televisores e de jogos visando trazer o 3D para suas produções e aparelhos, oferecendo modos diferentes de interação ao usuário. Com isso, novas técnicas de captura, codificação e modos de reprodução de vídeos 3D, em especial, os vídeos estereoscópicos, vêm surgindo ou sendo melhorados, visando aperfeiçoar e integrar esta nova tecnologia com a infraestrutura disponível. Entretanto, notam-se divergências nos avanços feitos no campo da codificação, com cada método de visualização estereoscópica utilizando uma técnica de codificação diferente. Isso leva ao problema da incompatibilidade entre métodos de visualização. Uma proposta é criar uma técnica que seja genérica, isto é, independente do método de visualização. Tal técnica, por meio de parâmetros adequados, codifica o vídeo estéreo sem nenhuma perda significativa tanto na qualidade quanto na percepção de profundidade, característica marcante nesse tipo de conteúdo. A técnica proposta, denominada RevGlyph, transforma um par estéreo de vídeos em um único fluxo anaglífico, especialmente codificado. Tal fluxo, além de ser compatível com o método anaglífico de visualização, é também reversível a uma aproximação do par estéreo original, garantindo a independência do método de visualização

Existem bases para as quais os dados são naturalmente representados por mais de uma visão. Por exemplo, imagens podem ser descritas por atributos de cores, textura e forma. Proteínas podem ser caracterizadas pela sequência de aminoácidos e pela representação tridimensional. A unificação das diferentes visões de uma base de dados pode ser problemática porque elas podem não ser comparáveis entre si ou podem apresentar diferentes graus de importância. Esses graus de importância podem, inclusive, se manifestar de maneira local, de acordo com a subestrutura dos dados em questão. Isso motivou o surgimento de algoritmos de agrupamento de dados capazes de lidar com bases multi-representadas (i.e., que possuem mais de uma visão dos dados), como o algoritmo SCAD. Esse algoritmo se mostrou promissor em experimentos relatados na literatura, mas possui problemas críticos identificados neste trabalho que o impedem de funcionar em determinados cenários. Tais problemas foram solucionados por meio da proposição de uma nova versão do algoritmo, denominada ASCAD, fundamentada em provas formais sobre a sua convergência. Foram desenvolvidas versões relacionais do algoritmo ASCAD, capazes de lidar com bases descritas apenas por relações de proximidade entre os objetos. Foi desenvolvido também um índice de validação interna e relativa de agrupamento voltado para dados multi-representados. A avaliação de agrupamento possibilístico e de bi-agrupamento por meio da comparação entre solução encontrada e solução de referência (validação externa) também foi explorada. Algoritmos de bi-agrupamento têm ganhado um interesse crescente da comunidade de análise de expressão gênica. No entanto, pouco se conhece do comportamento e das propriedades das medidas voltadas para validação externa de bi-agrupamento, o que motivou uma análise teórica e empírica dessas medidas. Essa análise mostrou que a maioria das medidas de biagrupamento possui problemas críticos e destacou duas delas como sendo as mais promissoras. Foram inclusas nessa análise três medidas de agrupamento particional não exclusivo, cujo uso na comparação de bi-agrupamentos é possível por meio de uma nova abordagem de avaliação de bi-agrupamento proposta nesta tese. Agrupamento particional não exclusivo faz parte de um domínio mais geral de soluções, i.e., o domínio dos agrupamentos possibilísticos. Observou-se algumas falhas conceituais importantes das medidas de agrupamento possibilístico, o que motivou o desenvolvimento de novas medidas e de uma análise empírica e conceitual envolvendo 34 medidas. Uma das medidas propostas se destacou como sendo a única que apresentou avaliações imparciais com relação ao número de grupos, o valor máximo de similaridade ao comparar a solução ideal encontrada com a solução de referência e avaliações sensíveis às diferenças das soluções em todos os cenários considerados

Com o objetivo de auxiliar a definição e evolução de estratégias de testes, estudos experimentais vêm sendo realizados comparando diferentes técnicas e critérios de teste em relação ao custo, eficácia e dificuldade de satisfação (strength). Entretanto poucos estudos buscam avaliar os critérios em diferentes paradigmas. Esta avaliação é importante pois o paradigma de implementação influência significativamente no programa gerado e as características entre programas implementados em diferentes paradigmas pode influenciar em diversos aspectos da atividade de teste. Este estudo é complementar a um outro trabalho do grupo do laboratório de engenharia de software do ICMC em que foram comparados o custo da aplicação dos critérios da técnica Estrutural em relação aos paradigmas Procedimental e Orientado a Objetos. Este trabalho apresenta um estudo experimental comparando o custo e o strength do critério Análise de Mutantes nos dois paradigmas. Além da avaliação do critério Análise de Mutantes, o material gerado para este estudo será construído de forma que possa ser utilizado para o ensino e treinamento das principais técnicas e critérios de teste e espera-se que este possa contribuir de alguma forma para que o ensino de teste de software possa ser aplicado em paralelo com o ensino de algoritmos e estrutura de dados. Para a condução deste estudo, foi utilizado um conjunto de 32 programas do domínio de estrutura de dados com versões implementadas em C e em Java. O critério Análise de Mutantes foi aplicado com auxílio das ferramentas Proteum e MuClipse. Para a avaliação do strength, o conjunto de casos de teste adequado a um programa foi executado contra os mutantes gerados na mesma versão do programa implementado no outro paradigma de interesse e o escore de mutação avaliado (cross scoring). Resultados indicam que tanto o custo quanto o strength do teste de mutação é maior em programas implementados no paradigma Procedimental do que no paradigma OO. Resultados estes certamente influenciados pelo conjunto de operadores implementado nas duas ferramentas. No paradigma procedimental, também foi avaliado o escore de mutação obtido por um subconjunto dos operadores da Proteum, construído com o objetivo de reduzir o custo da aplicação do critério. O escore obtido foi satisfatório e as reduções no custo significativas. Também foi avaliado strength das técnicas Funcional e Estrutural em relação ao critério AM nos dois paradigmas. Os resultados mostram que os conjuntos de casos de teste adequados aos critérios das técnicas Funcional e Estrutural no paradigma OO obtiveram, em geral, um escore de mutação maior do que no paradigma Procedimental