Repositório RCAAP

O MOOC surge em 2008 como um novo modelo de curso na modalidade EAD que, em certo sentido, retoma o antigo modelo dos cursos por correspondência, nos quais existia pouca ou nenhuma interação entre aprendiz e professor. São cursos online com grande quantidade de alunos, por isso denominados MOOC, do inglês, Massive Open Online Course. Esses cursos estão apoiados exclusivamente em tecnologias da Web e na maioria das vezes não exigem pré-requisitos e não fornecem certificados. Outro fator comum a esses cursos é o alto número de desistências, por volta de 95%. A maior parte dos cursos do tipo MOOC disponíveis hoje, apresentam um formato tradicional, no qual o aprendiz fica em condição quase passiva, já que as interações praticamente ficam restritas à controle de visualização de vídeos, com comandos do tipo para, voltar ou continuar. Nesse contexto, o desafio deste trabalho é melhorar o entendimento sobre os modelos de MOOC, examinando as causas de desistência relativas ao conteúdo e formato de apresentação para essa modalidade de EAD, além de propor um curso de Geometria, nessa modalidade, para o ensino básico, empregando ferramentas interativas, como o iGeom, software de Geometria Interativa (GI), e outras mídias, como áudios e vídeos. Nesse curso busca-se uma abordagem motivadora, comparando-o a um curso de controle. Esse modelo foi testado com um público formado por adultos e adolescentes, sendo 37,9% composto de adolescentes provenientes de escolas públicas, apresentando bons resultados. Na análise dos dados obtidos, encontrou-se indícios de que, comparado com o curso de controle, um maior número de alunos permaneceu no curso por mais tempo, possivelmente, pela realização de atividades interativas.

Este trabalho reside no campo de sistemas multiagente (MAS) compostos por agentes inteligentes que são capazes de usar protocolos de comunicação da Internet. Uma plataforma multiagente é um software ou framework capaz de gerenciar múltiplos aspectos da execução de agentes e suas interações. Muitas plataformas MAS foram desenvolvidas nos últimos anos, todas elas compatíveis com padrões de desenvolvimento de sistemas interoperáveis em diferentes níveis. Nos últimos anos,novas linguagens de programação foram definidas e novos protocolos foram adotados para comunicação em sistemas distribuídos. Esses fatos também influenciaram a comunidade multiagente,com a proposição de novas plataformas para apoiar o desenvolvimento de sistemas multiagente. Além disso, a adoção de agentes como paradigma para o desenvolvimento de sistemas distribuídos complexos em larga escala é vista como uma solução interessante na era do grande volume de dados. Portanto, uma comparação entre as plataformas existentes e seu suporte para desenvolver e implantar com eficiência sistemas multiagente de grande escala pode beneficiar a comunidade de desenvolvedores interessada em escolher qual plataforma melhor se adapta a seus projetos. O objetivo deste trabalho é avaliar plataformas multiagente em relação à escalabilidade, desempenho e compatibilidade com outras tecnologias com o objetivo de facilitar a escolha do desenvolvedor que queira projetar Sistemas Multiagente de grande porte. A fim de escolher as plataformas MAS para a comparação proposta, são consideradas plataformas de código aberto que são ativamente utilizadas pela comunidade multiagente. Além disso, tais plataformas MAS devem ser capazes de oferecer uma implantação de forma distribuída, característica essencial de sistemas escaláveis. Depois de restringir a lista de plataformas MAS de acordo com esses critérios, são analisados os sistemas de transporte de mensagens utilizando benchmarks para análise de escalabilidade e desempenho, considerando diferentes cenários de comunicação. Por fim, é apresentado um cenário realístico onde um MAS escalável pode ser adotado como solução.

Computer Vision researchers are constantly challenged with questions that are motivated by real applications. One of these questions is whether a computer program could distinguish groups of people based on their geographical ancestry, using only frontal images of their faces. The advances in this research area in the last ten years show that the answer to that question is affirmative. Several papers address this problem by applying methods such as Local Binary Patterns (LBP), raw pixel values, Principal or Independent Component Analysis (PCA/ICA), Gabor filters, Biologically Inspired Features (BIF), and more recently, Convolution Neural Networks (CNN). In this work we propose to combine the Bag-of-Visual-Words model with new dictionary learning techniques and a new spatial structure approach for image features. An extensive set of experiments has been performed using two of the largest face image databases available (MORPH-II and FERET), reaching very competitive results for gender and ethnicity recognition, while using a considerable small set of images for training.

Degradação do design é um problema central investigado na área de evolução de software. A densa rede de interdependências que emerge entre classes e módulos ao longo do tempo resulta em código difícil de mudar, não reutilizável e que não comunica por si só sua intenção. Dentre outros motivos, designs degradam porque requisitos mudam de maneiras não antecipadas pelo design inicial, ou seja, as modificações no código introduzem dependências novas e não planejadas entre classes e módulos do sistema. A gerência de dependências visa reduzir a degradação do design por meio de uma série de mecanismos que auxiliam na administração da complexidade estrutural inerente de sistemas orientados a objetos. Neste trabalho, investigamos as técnicas de identificação de dependências estruturais e lógicas. Em particular, por meio de um estudo de larga escala, comparamos os conjuntos desses dois tipos de dependências. Em seguida, conduzimos um estudo de caso a fim de identificar as origens de dependências lógicas. Por fim, fazemos um levantamento das técnicas de visualização de dependências e mostramos a ferramenta XFlow.

Avanços significativos no reconhecimento de manuscritos rasurados e na recuperação de textos degradados tem sido obtidos através do uso de técnicas de aprendizado de máquina. No entanto, o grande número de exemplos necessários na etapa de treinamento pode comprometer o uso prático de tais métodos. Este trabalho descreve um modelo de aprendizado para a classificação de dígitos rasurados denominado de \"aprendizado por um tiro\'\', pois que permite uma caracterização mais próximo ao de um ser humano. O termo \"aprendizado por um-tiro\'\' especifica que o aprendizado de um novo conceito é obtido pelo reconhecimento dos principais traços característicos de um objeto, palavra ou símbolo dado um conhecimento a priori relativamente pequeno sobre um novo objeto ainda não identificado. Deste modo, este pré conceito sobre sua caracterização admite a construção de classificadores que realizem a predição a partir de uma imagem de teste como entrada com um conjunto reduzido de imagens de treinamento. Este projeto cria um método que busca classificar imagens rasuradas de manuscritos a partir de um conjunto reduzido de imagens de treinamento sem rasura. Todo o pré-ajuste calculado através dessas imagens são separados por amostras chamadas de \"programas\'\', ou seja, uma composição do conhecimento a priori de todos os traços e sub-traços existentes na imagem, componentes estas que atribuem variabilidades locais e globais que poderão ser reconhecidas estatisticamente por Inferência Bayesiana. Destacamos aqui que o modelo consegue predizer dígitos e símbolos independentemente das rasuras pré-dispostas no conjunto de imagens de testes, onde este conhecimento a priori é inexistente dentro do conjunto de imagens de treinamento. Apresentamos em nossos resultados uma análise que, dado o ajuste inicial aplicado pelo aprendizado Bayesiano de Programas (BPL), nos permitiu utilizar características locais (traços) retiradas de cada símbolo para mensurar o custo referente entre todos os traços de uma imagem de teste e os traços em cada classe representado como imagem de treinamento. Para a obtenção do custo, utilizamos da métrica de deformação dinâmica aplicado em séries temporais (DTW). Finalmente, realizamos a predição para cada grupo de execuções considerando três conjuntos de dados: no primeiro com o grupo de imagens de teste rasuradas, no qual se obteve uma média global de acertos de 76%; no segundo conjunto com imagens de testes sem rasura (com diferença nos traços entre teste e treinamento), obtivemos uma média de 90% para com os acertos; e o terceiro conjunto usando o Omniglot. Tais reajustes adquiridos com poucos exemplos vislumbram futuras aplicações mais complexas em manuscritos degenerados ainda não digitalizados.

A interação entre instituições heterogêneas tem sido cada vez mais necessária para obter e disponibilizar informações e serviços para seus usuários internos e externos. Esta interação tem sido sustentada principalmente pelo uso das novas tecnologias da informação e comunicação. A interoperabilidade entre instituições heterogêneas garante esta interação e proporciona vários benefícios como, por exemplo, utilizar toda a plataforma legada das instituições e ainda permitir a interação entre os sistemas. Entretanto, para que esta interoperabilidade seja possível é necessária a definição de conceitos comuns que padronizam e orientam as interações entre as instituições. Através destes conceitos comuns, as instituições podem trocar informações entre si e ainda manter sua independência e as particularidades em seus sistemas internos. Em nosso trabalho, propomos um Modelo para Interoperabilidade entre Instituições Heterogêneas (MIIH). A especificação das regras de interação e, especificamente, os protocolos de interoperabilidade entre as instituições são escritas usando JamSession, que é uma plataforma para a coordenação de serviços de software heterogêneos e distribuídos. O modelo também define uma arquitetura baseada em Artefatos do Conhecimento Institucionais para lidar com as conexões com os sistemas das instituições. Estes Artefatos do Conhecimento Institucionais são baseados no conceito geral de Artefatos do Conhecimento, ou seja, \"objetos que contêm e transmitem uma representação utilizável do conhecimento\". Os Artefatos do Conhecimento Institucionais são padrões arquitetônicos recorrentes que são observados no projeto de mecanismos de interoperabilidade para conectar instituições heterogêneas e são usados como uma descrição de alto nível da arquitetura para um projeto de sistema. Eles funcionam como padrões arquiteturais pré-concebidos que norteiam e padronizam as interações e, portanto, a interoperabilidade organizacional e semântica entre as instituições. Os Artefatos do Conhecimento Institucionais são fundamentados sobre uma ontologia de conceitos relevantes para os serviços destas instituições, cujo nível de abstração pode variar, dependendo do nível de integração necessário para as instituições - quanto mais sofisticada a interação, mais detalhes devem ser representados explicitamente na ontologia. Os Artefatos do Conhecimento Institucionais implementados também se comunicam com a camada de interação com o usuário, baseada em mundos virtuais, para garantir a comunicação adequada com estes usuários. Além do modelo conceitual proposto, apresentamos como resultado deste trabalho, um exemplo de uso do MIIH no contexto das instituições relacionadas à herança cultural (museus, galerias, colecionadores, etc.). Tendo reconhecido que este contexto dos museus é importante para toda a sociedade, verificamos mais profundamente o funcionamento dos museus e suas interações entre si e com seus usuários. Identificamos neste cenário a aplicação direta de nosso projeto, uma vez que a interoperabilidade entre os museus é fundamental para o desempenho de suas funções e a interoperabilidade com seus usuários define a razão de sua existência, conforme identificamos na definição de museu apresentada pela UNESCO. Este exemplo de uso é construído seguindo a metodologia proposta neste trabalho e serve para mostrar a utilização do nosso modelo no desenvolvimento de uma aplicação concreta para uso em instituições de arte e também por seus usuários.

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

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

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

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

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

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

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

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

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

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

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

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

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

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