RCAAP Repository

Processos de Decisão Markovianos (Markov Decision Process - MDP) modelam problemas de tomada de decisão sequencial em que as possíveis ações de um agente possuem efeitos probabilísticos sobre os estados sucessores (que podem ser definidas por matrizes de transição de estados). Programação dinâmica em tempo real (Real-time dynamic programming - RTDP), é uma técnica usada para resolver MDPs quando existe informação sobre o estado inicial. Abordagens tradicionais apresentam melhor desempenho em problemas com matrizes esparsas de transição de estados porque podem alcançar eficientemente a convergência para a política ótima, sem ter que visitar todos os estados. Porém essa vantagem pode ser perdida em problemas com matrizes densas de transição, nos quais muitos estados podem ser alcançados em um passo (por exemplo, problemas de controle com eventos exógenos). Uma abordagem para superar essa limitação é explorar regularidades existentes na dinâmica do domínio através de uma representação fatorada, isto é, uma representação baseada em variáveis de estado. Nesse trabalho de mestrado, propomos um novo algoritmo chamado de FactRTDP (RTDP Fatorado), e sua versão aproximada aFactRTDP (RTDP Fatorado e Aproximado), que é a primeira versão eficiente fatorada do algoritmo clássico RTDP. Também propomos outras 2 extensões desses algoritmos, o FactLRTDP e aFactLRTDP, que rotulam estados cuja função valor convergiu para o ótimo. Os resultados experimentais mostram que estes novos algoritmos convergem mais rapidamente quando executados em domínios com matrizes de transição densa e tem bom comportamento online em domínios com matrizes de transição densa com pouca dependência entre as variáveis de estado.

Tratamos da generalização do problema da geração de caminho mínimo, no qual não apenas um, mas vários caminhos de menores custos devem ser produzidos. O problema dos k-menores caminhos consiste em listar os k caminhos de menores custos conectando um par de vértices. Esta dissertação trata de algoritmos para geração de k-menores caminhos em grafos simétricos com custos não-negativos, bem como algumas implementações destes.

Aprender a programar é uma tarefa árdua. Muitos erros são cometidos durante o desenvolvimento de código e aprender com esses erros pode ajudar a evitá-los. Apesar da quantidade considerável de pesquisas sobre esse tema, os professores têm pouco suporte para entender as dificuldades dos alunos. Perante esse cenário, o principal objetivo desta tese é identificar padrões de dificuldades enfrentadas pelos alunos durante o aprendizado de programação. Para realização da pesquisa, trabalhamos com dados de estudantes e professores de disciplinas de introdução à programação de cursos de graduação da USP. A pesquisa foi elaborada em três fases: primeiramente, analisamos dados para avaliar as taxas de insucesso do ensino introdutório de programação na universidade; em seguida, verificamos com alunos, através de diários de estudos, e professores, através de entrevistas semiestruturadas, o que eles entendem como sendo os problemas no ensino e aprendizagem de programação; e, por último, buscamos nos códigos de exercícios desenvolvidos por alunos durante seus cursos evidências sobre as dificuldades encontradas. Com essa última fase, catalogamos os resultados e os validamos através de um questionário com professores brasileiros com experiência no ensino desse conteúdo. Os dados coletados foram examinados utilizando-se de análise quanti e qualitativa. A análise de ~19.500 matrículas, nos possibilitou verificar que ~30% dos alunos matriculados em disciplinas de introdução à programação, no período analisado, não foram aprovados, ou seja, ~1.100 alunos por ano. Possibilitou ainda que fossem criadas listas das dificuldades citadas nos diários e entrevistas. Essas listas foram organizadas por conteúdo e por linguagem de programação (C e Python). Além disso, percebemos nesses dados ligações entre os conteúdos e, com isso, criamos um conjunto de conexões entre tópicos, mostrando a existência de pré-requisitos entre eles. Depois, analisando a evolução no desenvolvimento dos códigos dos estudantes, tivemos a oportunidade de identificar 139 tipos de equívocos cometidos utilizando-se as linguagens C e Python. Os equívocos que eram recorrentes foram considerados antipadrões (soluções comuns, porém com consequências negativas) e agrupados em catálogos. No total, foram criados 3 catálogos: um com antipadrões encontrados nos códigos desenvolvidos em C (21 equívocos), outro em Python (11 equívocos) e o último com a intersecção dos dois, totalizando 9 antipadrões encontrados tanto em C como em Python. Os antipadrões e os catálogos foram avaliados através de uma pesquisa de questionário respondida por 43 professores. Em geral, os professores conheciam os antipadrões apresentados. Além do mais, eles consideraram os catálogos fáceis para usar (~76%) e úteis (~81%); 53% mostraram ter intenção de usá-los regularmente nas suas aulas. Esperamos que os materiais gerados nesta tese possam ajudar professores no planejamento de suas aulas e pesquisadores a desenvolverem novas ferramentas e darem novos passos rumo ao aprimoramento do ensino e aprendizagem de programação.

Este trabalho trata do problema da construção de atributos para classificação quando atributos e rótulos são binários. A abordagem adotada visa reduzir efeitos de interação entre atributos, amenizando a necessidade dos classificadores lidarem com essas interações. Para tanto, é introduzida uma nova técnica que usa uma matriz de cálculo de paridade para transformar as coordenadas do vetor de atributos binários. Tal matriz permite a manipulação de diversas medidas derivadas da teoria da informação. A transformação resultante induz a formação de grupos de variáveis binárias. Baseando-se nessa técnica, um algoritmo inédito de análise de componentes independentes de variáveis binárias é apresentado, assim como um algoritmo que induz a independência condicional entre os atributos (dado o valor do rótulo). Um terceiro algoritmo apresentado reduz a Informação de Interação entre os atributos, uma medida associada ao grau de redundância ou colaboração entre atributos. Tal algoritmo é empregado no problema do projeto de operadores em dois níveis para imagens, em que múltiplos operadores são combinados para a obtenção de uma imagem final. Nesse caso, o algoritmo apresentado guia a estratégia de divisão de uma imagem em sub-regiões. É apresentado um arcabouço para o projeto de operadores de imagens em dois níveis, incorporando métodos de seleção de atributos e comparação de modelos. Os resultados mostram que o método proposto propicia melhor desempenho, em comparação com operadores de nível único.

Esta dissertação apresenta um estudo comparativo de diferentes métodos computacionais de segmentação estrutural musical, onde o principal objetivo é delimitar fronteiras de seções musicais em um sinal de áudio, e rotulá-las, i.e. agrupar as seções encontradas que correspondem a uma mesma parte musical. São apresentadas novas propostas para segmentação estrutural nãosupervisionada, incluindo métodos para processamento em tempo real, alcançando resultados com taxas de erro inferiores a 12%. O método utilizado compreende um estudo dos descritores sonoros e meios de modelá-los temporalmente, uma exposição das técnicas computacionais de segmentação estrutural e novos métodos de avaliação dos resultados que penalizam tanto a incorreta detecção das fronteiras quanto o número incorreto de rótulos encontrados. O desempenho de cada técnica computacional é calculado utilizando diferentes conjuntos de descritores sonoros e os resultados são apresentados e analisados tanto quantitativa quanto qualitativamente.

A área de recuperação de informação baseada em conteúdo visual vem ganhando importância graças ao volume de material visual existente (imagens e vídeo digitais), compartilhado e distribuído principalmente via Internet, e à capacidade de processamento alcançada pelos computadores pessoais na última década. Novas formas de consumo, manipulação e exploração de vídeo digital podem ser criadas através da organização e indexação apropriada desse material. A delimitação de tomadas fornece uma base para a abstração e estruturação de vídeo, agregando quadros contíguos em seqüências de mesmo contexto, isto é, trechos com unidade em termos de tempo e espaço. Nesta dissertação são apresentados os conceitos básicos de delimitação de tomadas e métodos tradicionais utilizados nesse tipo de segmentação, bem como vários resultados experimentais obtidos a partir de seqüências reais de TV. É analisada a distribuição das diferenças entre quadros sucessivos, calculada através de seus histogramas, na tentativa de caracterizar as transições entre tomadas e obter melhores parâmetros para a segmentação. Obtêm-se experimentalmente mais evidências que comprovam a superioridade da medida de intersecção de histogramas sobre outras medidas. A principal contribuição do trabalho consiste no desenvolvimento de um algoritmo baseado no método twin-comparison, que apresenta melhor desempenho que o método original na detecção dos limites de tomadas por utilizar análise local da variação visual entre os quadros do vídeo.

Modelos preditivos de mercado são ferramentas importantes para tomadores de decisões no âmbito público e privado. Devido à complexidade dinâmica do mercado imobiliário, composta pela interação de dois submercados distintos (mercado de ativos imobiliários e mercado de consumo de espaço) e pela limitação de dados disponíveis, o estudo analítico de mercados imobiliários requer a modelagem paramétrica de um sistema de equações que os descrevam, seguido pela identificação dos parâmetros deste sistema utilizando dados reais de uma região. Neste trabalho, estudamos o modelo dinâmico de mercado imobiliário proposto por Wheaton (1999), criado a partir do popular modelo de quatro quadrantes de autoria de DiPasquale e Wheaton (1996). Utilizamos técnicas de identificação de sistemas para elaborar um modelo de aprendizado para o estoque imobiliário, e o implementamos em Matlab. Aplicamos o método elaborado em dados simulados, para validá-lo, e então aplicamos o mesmo método, com adaptações, em dados reais do mercado imobiliário canadense. Os resultados obtidos validam o método de identificação de sistema dinâmico quando testado em dados simulados, e corroboram o modelo de Wheaton (1999) como modelo preditivo em dados reais. Ademais, os resultados indicam que um modelo que seja capaz de entender a evolução dinâmica dos parâmetros estáticos do modelo de Wheaton (1999), poderia melhorar os resultados deste como ferramenta preditiva.

Software bots integrate their work with humans\' tasks, serving as conduits between users and other tools. Due to their ability to automate tasks, bots have become particularly relevant for Open Source Software (OSS) projects hosted on GitHub. Commonly, projects use bots to automate various tasks, such as ensuring license agreement signing, reporting continuous integration failures, reviewing code and pull requests, triaging issues, and refactoring the source code. However, in preliminary studies, our findings indicate that the interaction of these bots on pull requests can be disruptive and perceived as unwelcoming by contributors and maintainers. Although bots can be useful for supporting maintainers\' work, sometimes their comments are seen as spam and are quickly ignored by contributors. In this dissertation, our goal was to identify and understand challenges maintainers and contributors face during interaction with bots on pull requests of OSS projects and design and evaluate a software bot that mitigates some of these problems. Toward this end, we conducted multiple studies using multiple research methods. To identify the challenges caused by bots in pull request interactions, we interviewed 21 practitioners, including project maintainers, contributors, and bot developers. The data was qualitatively analyzed using open and axial coding. Subsequently, the analysis resulted in a theory of how human developers perceive annoying bot behaviors as noise on social coding platforms. Based on this theory, we conducted a participatory design fiction study with 32 practitioners and researchers. This study resulted in design strategies that served as insights to create a prototype. We conducted a suitability study with 15 design fiction participants to assess the envisioned solution. By collecting participants perceptions about a prototype implementing the envisioned strategies, we identified improvements to the prototype according to the suggestions received from the study participants. The main contributions of this dissertation are: (i) identifying the changes in project activity indicators after the adoption of a bot; (ii) proposing a theory about how noise introduced by bots disrupts developers\' communication and workflow; (iii) identifying strategies to mitigate the information overload generated by the existing bots\' interaction; and (iv) the concept of a meta-bot to support contribution to OSS projects. These contributions may help practitioners understand the effects of adopting a bot. Researchers and tool designers may leverage our results to better support human-bot interaction on social coding platforms.

Uma hiper-heurística é uma heurística que pode ser utilizada para lidar com qualquer problema de otimização, desde que a ela sejam fornecidos alguns parâmetros, como estruturas e abstrações, relacionados ao problema considerado. As hiper-heurísticas têm sido aplicadas a alguns problemas práticos e apresentadas como métodos de grande potencial, no que diz respeito à capacidade de possibilitar o desenvolvimento, em tempo bastante reduzido, de algoritmos capazes de lidar satisfatoriamente, do ponto de vista prático, com problemas de otimização complexos e pouco conhecidos. No entanto, é difícil situar as hiper-heurísticas em algum nível de qualidade e avaliar a robustez dessas abordagens caso não as apliquemos a problemas para os quais existam diversas instâncias disponíveis publicamente e já experimentadas por algoritmos relevantes. Este trabalho procura dar alguns passos importantes rumo a essas avaliações, além de ampliar o conjunto das hiper-heurísticas, compreender o impacto de algumas alternativas naturais de desenvolvimento e estabelecer comparações entre os resultados obtidos por diferentes métodos, o que ainda nos permite confrontar as duas diferentes classes de hiper-heurísticas que identificamos. Com essas finalidades em mente, desenvolvemos 3 novas hiper-heurísticas e implementamos 2 das hiper-heurísticas mais importantes criadas por outros autores. Para estas últimas, experimentamos ainda algumas extensões e modificações. Os dois métodos hiper-heurísticos selecionados podem ser vistos como respectivos representantes de duas classes distintas, que aparentemente englobam todas as hiper-heurísticas já desenvolvidas e nos permitem denominar cada um desses métodos como \"hiper-heurística de busca direta por entornos\" ou como \"hiper-heurística evolutiva indireta\". Implementamos cada hiper-heurística como uma biblioteca (em linguagem C), de forma a evidenciar e estimular a independência entre o nível em que se encontra a hiper-heurística e aquele onde se apresentam as estruturas e abstrações diretamente relacionadas ao problema considerado. Naturalmente, essa separação é de ingente importância para possibilitar a reutilização imediata das hiper-heurísticas e garantir que nelas haja total ausência de informações relativas a um problema de otimização específico.

Dois modelos principais de planejamento em inteligência artificial são os usados, respectivamente, em planejamento probabilístico (MDPs e suas generalizações) e em planejamento não-determinístico (baseado em model checking). Nessa dissertação será: (1) exibido que planejamento probabilístico e não-determinístico são extremos de um rico contínuo de problemas capaz de lidar simultaneamente com risco e incerteza (Knightiana); (2) obtido um modelo para unificar esses dois tipos de problemas usando MDPs imprecisos; (3) derivado uma versão simplificada do princípio ótimo de Bellman para esse novo modelo; (4) exibido como adaptar e analisar algoritmos do estado-da-arte, como (L)RTDP e LDFS, nesse modelo unificado. Também será discutido exemplos e relações entre modelos já propostos para planejamento sob incerteza e o modelo proposto.

Nesta tese, estudamos um arcabouço, introduzido por Frank, que denominamos de sistemas generalizados de núcleos. Provamos teoremas sobre empacotamentos de certos objetos combinatórios neste arcabouço, tanto para o caso inteiro quanto para o fracionário. Estes teoremas, em particular, implicam em uma melhora nos limitantes superiores de Schrijver, para o empacotamento de ramificações, e de Gabow e Manu, para o empacotamento de arborescências. Além disso, também provamos que o problema de minimização num poliedro relacionado pode ser resolvido em tempo polinomial, dado um oráculo de separação.

As imagens de Angiografia por Ressonância Magnética (angio-RM) e Tomografia Computadorizada (angio-TC) são ferramentas amplamente usadas em processos de quantificação vascular e no diagnóstico de doenças cardiovasculares, as quais são consideradas entre as principais causas de morte. Contudo, a análise dos vasos em larga escala a partir das imagens é dificultada, tanto pela variabilidade natural dos vasos no corpo humano, quanto pela grande quantidade de dados disponíveis. Além disso, os métodos de quantificação existentes, usualmente extraem as características a partir dos esqueletos, ou até mesmo das próprias imagens de angiografia, razão pela qual tais métodos podem fazer necessária a reanálise das imagens repetidas vezes. Com o intuito de facilitar a análise e de fornecer uma ferramenta de apoio ao diagnóstico, neste trabalho são apresentados um modelo de representação textual de redes vasculares e uma metodologia de quantificação vascular automática, que é feita a partir dessa representação. A representação é obtida a partir da segmentação de imagens volumétricas de angio-RM e angio-TC, seguida da extração de trajetórias e diâmetros de redes vasculares. Tal representação é híbrida, combinando grafos e uma sequência textual de instruções, e permite não apenas a extração de caraterísticas morfológicas da rede vascular, como também a compressão das imagens e, ainda, a reconstrução de imagens similares às imagens originais. A partir das características extraídas, foram realizados estudos comparativos entre arquiteturas vasculares, o que é feito tanto por meio do uso de imagens sintéticas, como por meio de imagens reais, imagens nas quais foi possível encontrar diferenças entre arquiteturas, além de viabilizar a caracterização de aneurismas em um indivíduo. Paralelamente, desenvolvemos um método que permite identificar similaridade entre segmentos vasculares, o que por sua vez possibilita o reconhecimento e rotulação de segmentos em um conjunto de redes vasculares. A metodologia por nós desenvolvida deve também auxiliar no desenvolvimento de processos de classificação de vasos sanguíneos, de ferramentas para o diagnóstico automático de doenças vasculares, e para a melhora de técnicas utilizadas na prática clínica.

Galerias, Bibliotecas, Arquivos e Museus (GLAMs) têm enfrentado o desafio de envolver os usuários na seleção, catalogação, contextualização e curadoria de coleções por meio de crowdsourcing. Esse novo modo de interação se estende além do acesso passivo e pode levar a um nível mais profundo de engajamento com coleções. Como a participação do usuário é a chave para o sucesso nesse contexto, GLAMs precisam criar e manter sistemas de colaboração aberta. Contudo, tais sistemas precisam fomentar um senso de comunidade em torno dos artefatos e as comunidades dependem, dentre outros fatores, do engajamento de colaboradores. O termo engajamento indica a profundidade de investimento de um ator quando interagindo com um sistema digital. Para promover o engajamento dos usuários com comunidades online, tem-se discutido o uso da gamificação. Gamificação é o uso de elementos de projeto de jogos em contextos que não são jogos e tem como meta estimular a participação e engajar pessoas. Nos estudos teóricos sobre gamificação, a motivação intrínseca e a autodeterminação do usuário são as principais bases para a construção de aplicações. No entanto, a maior parte da literatura que descreve a implementação de gamificação utiliza elementos de recompensa, como pontos, distintivos e quadros de liderança, associados à pontificação, um subconjunto da gamificação; e não apresenta o monitoramento e a análise de cada elemento de jogo inserido durante o desenvolvimento, de modo a avaliar o impacto no comportamento dos usuários. Há também a necessidade de explorar como a gamificação pode ser implementada em domínios específicos. Esta pesquisa propõe uma abordagem para integrar gamificação e avaliação de engajamento durante o desenvolvimento de comunidades online de colaboração aberta. Nesse contexto, uma pesquisa-ação foi realizada no domínio de uma GLAM sobre arquitetura e urbanismo, chamada Arquigrafia, para investigar as práticas atuais de gamificação e uma proposta de abordagem. As métricas de engajamento foram analisadas estatisticamente por meio de pesquisas quantitativas experimentais e não-experimentais sobre dados coletados em três anos de monitoramento (2015-2018). Os resultados indicam que o uso de elementos de jogos em uma comunidade online de colaboração aberta, no domínio de GLAMs, tem um efeito positivo sobre o engajamento de usuários sob certas condições, as quais são consideradas na proposta de abordagem desta tese.

Nós consideramos o seguinte problema. Fixado um grafo H e um número real \\alpha \\in (0,1], determine o menor \\beta = \\beta(\\alpha, H) que satisfaz a seguinte propriedade: se G é um grafo de ordem n no qual cada subconjunto de [\\alpha n] vértices induz mais que \\beta n^2 arestas então G contém H como subgrafo. Este problema foi iniciado e motivado por Erdös ao conjecturar que todo grafo livre de triângulo de ordem n contém um subconjunto de [n/2] vértices que induz no máximo n^2 /50 arestas. Nosso resultado principal mostra que i) todo grafo de ordem n livre de triângulos e pentágonos contém um subconjunto de [n/2] vértices que induz no máximo n^2 /64 arestas, e ii) se G é um grafo regular de ordem n livre de triângulo, com grau excedendo n/3, então G contém um subconjunto de [n/2] vértices que induz no máximo n^2 /50 arestas. Se além disso G não é 3-cromático então G contém um subconjunto de [n/2] vértices que induz menos de n^2 /54 arestas. Como subproduto e confirmando uma conjectura de Erdös assintoticamente, temos que todo grafo regular de ordem n livre de triângulo com grau excedendo n/3 pode ser tornado bipartido pela omissão de no máximo (1/25 + o(1))n^2 arestas. Nós também fornecemos um contraexemplo a uma conjectura de Erdös, Faudree, Rousseau e Schelp.

Causal inference may help us to understand the underlying mechanisms and the risk factors of diseases. In Genetics, it is crucial to understand how the connectivity among variables is influenced by genetic and environmental factors. Family data have proven to be useful in elucidating genetic and environmental influences, however, few existing approaches are able of addressing structure learning of probabilistic graphical models (PGMs) and family data analysis jointly. We propose methodologies for learning, from observational Gaussian family data, the most likely PGM and its decomposition into genetic and environmental components. They were evaluated by a simulation study and applied to the Genetic Analysis Workshop 13 simulated data, which mimic the real Framingham Heart Study data, and to the metabolic syndrome phenotypes from the Baependi Heart Study. In neuroscience, one challenge consists in identifying interactions between functional brain networks (FBNs) - graphs. We propose a method to identify Granger causality among FBNs. We show the statistical power of the proposed method by simulations and its usefulness by two applications: the identification of Granger causality between the FBNs of two musicians playing a violin duo, and the identification of a differential connectivity from the right to the left brain hemispheres of autistic subjects.

Cidades ao redor do mundo enfrentam diversos desafios para proporcionar uma boa qualidade de vida aos seus cidadãos. Sistemas de software vêm sendo desenvolvidos com objetivo de melhorar os serviços e otimizar o uso da infraestrutura da cidade. Desenvolver ambientes de experimentação para esses sistemas na escala de grandes cidades ainda é um desafio, devido ao alto custo e problemas de infraestrutura. Por sua vez, a simulação é um mecanismo que vem sendo utilizado na realização de experimentos em diversas áreas do conhecimento. O objetivo deste trabalho é auxiliar na construção de um ambiente de experimentação de larga escala e interativo para plataformas de Cidades Inteligentes através de simulação. Para tanto, desenvolvemos uma arquitetura de software visando permitir a integração de plataformas e simuladores de Cidades Inteligentes. Dois estudos de caso demostraram a viabilidade da solução, integrando o simulador InterSCSimulator e a plataforma InterSCity, envolvendo uma série de melhorias em ambas as ferramentas. Apresentamos detalhes de como implementar a arquitetura proposta, além da execução de experimentos na escala da cidade de São Paulo. Acreditamos que a solução nos levou a resultados satisfatórios, tendo em vista que, foi possível realizar experimentos de larga escala através de simulação por meio da implementação da arquitetura apresentada. Portanto, projetamos uma arquitetura de software que poderá servir de base para integração de plataformas e simuladores de Cidades Inteligentes com o intuito de realizar experimentos de larga escala e interativo, visando principalmente questões de desempenho e escalabilidade.

A queda do interesse por parte de novos universitários, para cursos de ciência da computação em várias universidades do mundo [55, 68], é um sinal para começarmos a pensar se um dos motivos dessa queda tem relação com a forma pela qual o ensino de computação está sendo conduzido. Nessa linha, perguntamos se existem maneiras de tornar o ensino de computação mais interativo e motivante para os alunos da nova geração, os quais cresceram no meio de uma das categorias mais complexas de software existentes hoje: os jogos de computador [10]. Esses softwares ficam cada vez mais interativos, complexos e ricos em detalhe com o passar do tempo. Conforme será exposto, por meio do estudo de algumas iniciativas de pesquisadores nesse sentido, o ensino de ciência da computação pode se tornar mais interessante e rico com a utilização de jogos de computador como recurso didático, para capturar a atenção dessa nova geração de estudantes. Com base nesse resultado, vamos focar nossa contribuição no ensino de lógica em cadeiras de Inteligência Artificial (IA), uma área de concentração da Ciência da Computação. Apresentamos uma ferramenta que chamamos de Odin, para construir e visualizar especificações executáveis de IA, por meio da linguagem PROLOG, em ambientes tridimensionais de jogos de computador. Entendemos que essa ferramenta pode ser utilizada como um recurso didático em cursos de lógica para alunos em nível de graduação. Como principal benefício, o aluno tem a possibilidade de explorar, observar e interagir com os resultados de seu trabalho. Essa possibilidade de visualização é o que parece reter a atenção do aluno, de acordo com pesquisadores na área. Disponibilizamos dois cenários de uso: O labirinto e o Mundo de Wumpus, dois cenários que juntos podem ser utilizados para cobrir uma boa parte da carga didática de um curso de lógica para graduação. Outros cenários podem ser desenvolvidos posteriormente por meio de extensão do framework composto por classes C++. A ferramenta foi utilizada em duas cadeiras de inteligência artificial no Instituto de Matemática e Estatística, da Universidade de são Paulo. Consideramos que a recepção da ferramenta por parte dos alunos foi positiva.

Esta tese analisa aplicações de transmissão de voz e vídeo sobre redes Wi-Fi (IEEE 802.11). Os principais problemas observados foram a maior incidência de tráfegos em rajada e os problemas associados à execução de handoffs. Foram propostos algoritmos adaptativos para monitorar e contornar esses problemas.

Este trabalho compara o desempenho e a estabilidade de dois arcabouços para o processamento de Big Data: Apache Spark e High Performance Analytics Toolkit (HPAT). A comparação foi realizada usando duas aplicações: soma dos elementos de um vetor unidimensional e o algoritmo de clusterização K-means. Os experimentos foram realizados em ambiente distribuído e com memória compartilhada com diferentes quantidades e configurações de máquinas virtuais. Analisando os resultados foi possível concluir que o HPAT tem um melhor desempenho em relação ao Apache Spark nos nossos casos de estudo. Também realizamos uma análise dos dois arcabouços com a presença de falhas.

Casamento de padrões de pontos é um problema fundamental em reconhecimento de padrões. O objetivo é encontrar uma correspondência entre dois conjuntos de pontos, associados a características relevantes de objetos ou entidades, mapeando os pontos de um conjunto no outro. Este problema está associado a muitas aplicações, como por exemplo, reconhecimento de objetos baseado em modelos, imagens estéreo, registro de imagens, biometria, entre outros. Para encontrar um mapeamento, os objetos são codificados por representações abstratas, codificando as características relevantes consideradas na comparação entre pares de objetos. Neste trabalho, objetos são representados por grafos, codificando tanto as características `locais\' quanto as relações espaciais entre estas características. A comparação entre objetos é guiada por uma formulação de atribuição quadrática, que é um problema NP-difícil. Para estimar uma solução, duas técnicas de casamento entre grafos são propostas: uma baseada em grafos auxiliares, chamados de grafos deformados; e outra baseada em representações `esparsas\', campos aleatórios de Markov e propagação de crenças. Devido as suas respectivas limitações, as abordagens são adequadas para situações específicas, conforme mostrado neste documento. Resultados envolvendo as duas abordagens são ilustrados em quatro importantes aplicações: casamento de imagens de gel eletroforese 2D, segmentação interativa de imagens naturais, casamento de formas, e colorização assistida por computador.