Repositório RCAAP

Sistemas baseados na captura de experiências ao vivo têm sido investigados em diversos contextos. O presente trabalho teve como objetivo investigar mecanismos para a captura de informação multimídia em ambientes de reuniões de modo a permitir a geração de documentos hipermídia associados na World Wide Web. O foco do trabalho é na captura e no acesso à informação multimídia associada a reuniões distribuídas síncronas. A investigação resultou no levantamento de requisitos necessários para a construção de uma ferramenta instrumentada para capturar informação multimídia associada; no levantamento das limitações existentes para a implementação da ferramenta; na modelagem e na implementação de uma ferramenta, eMeet/InCA, que atende aos requisitos levantados, consideradas as limitações identificadas.

Muitas de nossas experiências cotidianas são apoiadas pela troca de informações a. qual pode ser capturada de modo a suportar a geração automática de hiperdocumentos que correspondem às experiências capturadas. O Projeto eClass do Geórgia Institute of Technology utiliza computação ubíqua para a captura de informações em ambientes de sala de aula a fim de permitir a produção automática de documentos hipermídia que refletem o conteúdo capturado. Ambientes como os do Projeto eClass permitem a autoria automática de ligações liipertexto a partir da interação do usuário com o ambiente ubíquo. Serviços de criação automática de ligações entre repositórios Web podem explorar técnica, de Recuperação de Informação, como demonstram trabalhos que veem sendo desenvolvidos pelo grupo de pesquisa no qual este trabalho está inserido. No entanto, tais técnicas normalmente permitem a identificação de ligações que não deveriam ser geradas (ligações imprecisas), ao mesmo tempo que não permitem identificar todas as ligações que deveriam ter sido geradas (ligações relevantes). Esses fatos motivaram o trabalho apresentado, que tem como objetivo aprimorar a precisão dos resultados obtidos pelos serviços de criação automática de ligações e. consequentemente, aproximar as ligações criadas àquelas esperadas pelos usuários. Para alcançar esse objetivo. foram utilizadas abordagens de Recuperação de Informação e de Sistemas Hipermídia Abertos para armazenamento das ligações criadas. Através das investigações, foi possível a verificação e a seleção de informações que representam melhor o conteúdo das coleções de informações manipuladas no sentido de prover ligações mais precisas. Como resultado, foram definidos procedimentos, que deram origem a um serviço configurável de criação automática de ligações.

This work focus on the genetic generation of fuzzy systems. One of the main contribution of this work is the proposal of the FCA-BASED method, which generates the genetic search space using the formal concept analysis theory by extracting rules from data. The experimental evaluation results of the FCA-BASED method show its robustness, producing a good trade-off between the accuracy and the interpretability of the generated models. Moreover, the FCA-BASED method presents improvements to the DOC-BASED method, a previously proposed approach, related to the reduction of the computational cost for the generation of the genetic search space. In order to tackle high dimensional datasets, we also propose the FUZZYDT method, a fuzzy version of the classic C4.5 decision tree, a highly scalable method that presents low computational cost and competitive accuracy. Due to these characteristics, FUZZYDT is used in this work as a baseline method for the experimental evaluation and comparisons of other classic and fuzzy classification methods. We also include in this work the use of the FUZZYDT method to a real world problem, the warning of the coffee rust disease in Brazilian crops. Furthermore, this work investigates the task of feature subset selection to address the dimensionality issue of fuzzy systems. To this end, we propose the FUZZYWRAPPER method, a wrapper-based approach that selects features taking the relevant information regarding the fuzzyfication of the attributes into account, in the feature selection process. This work also investigates the automatic design of fuzzy data bases, proposing the FUZZYDBD method, which estimates the number of fuzzy sets defining all the attributes of a dataset and evenly distributing the fuzzy sets in the domains of the attributes. A modified version of the FUZZYDBD method, FUZZYDBD-II, which defines independent numbers of fuzzy sets for each attribute of a dataset, by means of estimation functions, is also proposed in this work

Uma tendência crescente entre os pesquisadores da Robótica Móvel é a elaboração de sistemas robóticos descentralizados denominados enxames de robôs, nos quais a ação conjunta de cada agente leva à execução de tarefas de maneira mais robusta que quando realizada por um único robô. Um acréscimo adicional à robustez é conveniente em tais sistemas para que eles sejam de maior confiabilidade no mundo real. Neste trabalho, uma rede neural hierárquica desenvolvida para o aprendizado em tempo real inicialmente elaborada para o aprendizado de navegação de um único robô será estendida para controlar um enxame de robôs. O sistema realiza um balanceamento da influência de comportamentos implementados previamente em um robô de acordo com conhecimentos obtidos através da interação do mesmo com o ambiente. Cada robô possui sua própria rede neural, adquirindo seu conhecimento tanto independentemente quanto com o compartilhamento de informações com outros robôs. Espera-se que o uso de tal arquitetura permita uma adaptação mais rápida dos robôs ao ambiente, permitindo uma mudança em tempo real de seus parâmetros de acordo com as peculiaridades do ambiente no qual os robôs estão inseridos. A tarefa de escolta de um robô pelos demais é adotada para a avaliação de desempenho do modelo de rede neural proposto. Dois comportamentos são ponderados pela rede neural hierárquica: o de manutenção de uma distância preestabelecida a um agente e um outro de cobertura de área baseado em Diagramas Centroidais de Voronoi. Os testes foram feitos nos ambientes Player/Stage e indicam que a rede neural hierárquica torna os robôs capazes não apenas de aprender à medida que interagem com ambiente como de utilizar este conhecimento em tempo real para realizar a escolta de forma bem sucedida

O processo de automatização de teste de software possui alto custo envolvido em sistemas de larga escala, pois exigem cenários de teste complexos e tempos de execução extremamente longos. Além disso, cada etapa do processo de teste requer recursos computacionais e um tempo considerável para a execução de muitos casos de teste, tornando-se um gargalo para as empresas de Tecnologia da Informação (TI). Neste contexto, os benefícios e oportunidades oferecidos pela combinação da computação em nuvem com o Teste como Serviço (Testing as a Service, TaaS), que é considerado um novo modelo de negócio e de serviço atraente e promissor, podem proporcionar um impacto positivo na redução do tempo de execução dos testes de maneira custo-efetiva e aumentar o retorno sobre o investimento ou Return on investment (ROI). Todavia, existe o problema de vendor lock-in, que é o aprisionamento do usuário à plataforma de um fornecedor específico ou serviço de teste, ocasionado pela dificuldade de migrar de um fornecedor TaaS para outro, limitando a utilização dessas novas tecnologias de maneira efetiva e eficiente, impedindo assim, a ampla adoção do TaaS. Como os estudos existentes não são rigorosos ou conclusivos e, principalmente, devido à falta de evidência empírica na área de serviço de teste, muitas questões devem ser investigadas na perspectiva da migração entre os provedores de TaaS. O objetivo deste trabalho é reduzir o impacto ocasionado pelo problema de vendor lock-in no processo de automatização de testes na computação em nuvem, na escrita, configuração, execução e gerenciamento dos resultados de testes automatizados. Neste contexto, foi desenvolvido o protótipo da abordagem intitulada Multi-TaaS por meio de uma biblioteca Java como prova de conceito. A abordagem Multi-TaaS é uma camada de abstração e a sua arquitetura permite abstrair e flexibilizar a troca de fornecedores de TaaS de forma portável, pois permite encapsular toda a complexidade da implementação do engenheiro de software ao desacoplar o teste automatizado de qual plataforma TaaS ele será executado, bem como abstrair os aspectos da comunicação e integração entre as APIs REST proprietárias dos diferentes fornecedores de TaaS. Além disso, a abordagem Multi-TaaS possibilita também sumarizar os resultados dos testes automatizados de forma independente das tecnologias da plataforma TaaS subjacente. Foram realizadas avaliações comparativas da eficiência, efetividade, dificuldade e do esforço de migração entre as abordagens Multi-TaaS e abordagem convencional, por meio de experimentos controlados. Os resultados deste trabalho indicam que a nova abordagem permite facilitar a troca do serviço de teste, melhorar a eficiência e, principalmente, reduzir o esforço e os custos de manutenção na migração entre fornecedores de TaaS. Os estudos realizados no experimento controlado são promissores e podem auxiliar os engenheiros de software na tomada de decisão quanto aos riscos associados ao vendor lock-in no TaaS. Por fim, a abordagem Multi-TaaS contribui, principalmente, para a portabilidade dos testes automatizados na nuvem e da sumarização dos resultados dos testes e, consequentemente, possibilita que o modelo de serviço TaaS na computação em nuvem seja amplamente adotado, de forma consciente, no futuro.

O INAF (Indicador de Alfabetismo Funcional), criado para mensurar o nível de letramento da população brasileira entre 15 e 64 anos, apontou, em seu relatório de 2018, que somente um em cada dez brasileiros adultos é considerado letrado de forma proficiente. No setor da agropecuária, apenas uma em cada cem pessoas consegue ler e compreender textos sem enfrentar dificuldades. Isso significa que a grande maioria dos produtores rurais pode não se beneficiar das tecnologias publicadas por entidades de pesquisa como a Embrapa (Empresa Brasileira de Pesquisa Agropecuária). Uma solução bastante viável para esse problema é simplificar essas publicações para torná-las mais acessíveis para público alvo. Uma das etapas da simplificação é a tarefa conhecida como predição da complexidade sentencial, responsável por identificar as sentenças mais complexas de um texto, as quais serão alvo das operações de simplificação subsequentes. Para o português brasileiro, antes do presente trabalho, a tarefa de predição de complexidade sentencial ainda não havia sido avaliada e nem havia córpus criados para o aprendizado da tarefa. Outra lacuna observada foi a falta de um córpus com métricas de rastreamento ocular, semelhante aos disponíveis em inglês e utilizados pelos trabalhos internacionais mais recentes sobre predição de complexidade. O objetivo principal desta pesquisa é avaliar métodos de predição de complexidade sentencial para o português brasileiro escrito, a fim de criar um método no estado da arte para a tarefa. Para implementar esse método, projetou-se um ambiente denominado Simpligo, que tem por objetivo auxiliar na simplificação de textos, especialmente os produzidos pela Embrapa para o domínio rural. Para atingir esses objetivos, foram criados dois córpus: um com as sentenças alinhadas do PorSimples (CASELI et al., 2009), e um com métricas de rastreamento ocular e normas de previsibilidade de estudantes do ensino superior. Também disponibilizou-se a versão de 2021 da ferramenta NILC-Metrix, de código-fonte aberto, com 200 métricas linguísticas e psicolinguísticas, as quais são utilizadas nas avaliações dos métodos de predição de complexidade sentencial . Por fim, nesta pesquisa foram avaliadas abordagens de ranking e transfer learning, sendo que esta última, com a adição das métricas de rastreamento ocular, atingiu o estado da arte para a tarefa de predição da complexidade sentencial na língua portuguesa, com 97,5% de acurácia. Este trabalho contribui com novos córpus, métodos e aplicações, voltados à tarefa de avaliação da complexidade sentencial. Além disso, ao serem disponibilizados publicamente todos os recursos desenvolvidos, torna-se possível sua utilização em outras tarefas e investigações.

In the present Big Data era, many businesses have become more data-driven, seeking to improve their decision-making processes based on solid Data Analytics practices. Several steps constitute the Data Analytics pipeline and all of them involve specific approaches and technologies, which are constantly evolving. In order to accommodate new needs and trends, there is always room for improvements in the steps of Data Analytics. In this context, this PhD research has focused on improving two of those steps: (i) data cleaning and (ii) data analysis. Regarding the first step, we addressed the problem of performing data cleaning incrementally, considering dynamic scenarios with incoming data batches, as well as holistically, that is, jointly taking into account multiple error detection criteria. As a result, we have developed an incremental data cleaning framework which significantly outperforms competitors, enabling higher efficiency while compromising little on repair quality, as well as addresses the problem in an innovative way, hence filling a gap in the literature. Regarding the second improved step, we addressed the problem of handling queries over an Attribute Domain, which consists of the set of stored values within a domain of attributes, usually across multiple relations. As a result, we have proposed three contributions: (a) the Domain Index, an access method for efficiently performing queries over Attribute Domains, which we refer to as Domain Queries; (b) a comprehensive case study of Domain Indexes applied to the medical domain, focusing on content-based Domain Queries for supporting physicians in decision-making; and (c) an approach for including support to Attribute Domains as first-class citizens in a Relational Database Management System (RDBMS). Together, those contributions target a distinct category of queries which, until the execution of this PhD research, had not been addressed in the literature elsewhere. Experimental results highlight the superior performance enabled by the Domain Index compared to existing techniques of modern RDBMSs, which not only are inefficient in several scenarios, but also are not always applicable. Ultimately, those contributions enrich data analyses down the road. Hence, this PhD research advances the state of the art in the field of Data Analytics, as well as opens several directions for future work.

O teste baseado em modelos visa à derivação de casos de teste a partir de modelos produzidos ao longo do desenvolvimento de software. Nesse contexto, as Máquinas de Estados Finitos têm sido amplamente pesquisadas e utilizadas para derivação de seqüências de teste. Para isso, vários métodos de geração de seqüências de teste têm sido desenvolvidos há várias décadas. O objetivo desses métodos é a obtenção de um conjunto de teste que seja capaz de revelar os defeitos de uma implementação. Entretanto, muitas vezes os conjuntos gerados são muito grandes, o que torna sua aplicação inviável. Trabalhos recentes definiram condições que podem ser utilizadas para investigar mecanismos de redução de casos de teste. Este trabalho apresenta uma estratégia para a redução de conjuntos de seqüências de teste a partir de Máquinas de Estados Finitos com base em condições de suficiência. A estratégia baseia-se na combinação de seqüências de um conjunto de teste, de forma a reduzir o número de seqüências e o tamanho delas, mantendo a completude do conjunto. São apresentadas seis abordagens de redução baseadas na estratégia proposta, as quais foram implementadas em uma ferramenta. Para avaliar as abordagens foram conduzidos estudos experimentais, os quais também serviram para inferir sobre as características e propriedades de cada abordagem. Além disso, um estudo de caso com MEFs reais também foi realizado

Diversos pesquisadores vêm investigando métodos e técnicas para tornar possível às pessoas anotarem vídeos de modo transparente. A anotação pode ser realizada com a fala, com o uso de tinta digital ou algum outro meio que possa ser capturado enquanto a pessoa assiste ao vídeo. Tais anotações podem ser compartilhadas com outras pessoas, que podem estar assistindo ao mesmo vídeo em um mesmo instante ou em momentos diferentes, sendo interessante ainda que as anotações possam ser realizadas por várias pessoas de modo colaborativo. O paradigma Watch-and-Comment (WaC) propõe a captura transparente de anotações multimodais de usuários enquanto os mesmos assistem e comentam um vídeo. Como resultado desse processo, é gerado um vídeo digital interativo integrando o conteúdo original às anotações realizadas. Esta dissertação tem por objetivo explorar conceitos de computação ubíqua, redes sociais, redes peer-to-peer e TV interativa na proposta de um modelo arquitetural de ciência de informações de contexto para aplicações definidas segundo o paradigma WaC. O modelo explora a integração de um serviço ao paradigma, que auxilie ou forneça alternativas para que aplicações, do momento da captura ao acesso das anotações, utilizem informações de contexto do usuário, do vídeo e das anotações. O modelo também auxilia no estudo de colaboração entre usuários que realizam anotações em vídeos. Outra contribuição da dissertação é a prototipação de aplicações para avaliar e refinar o modelo proposto. São apresentadas extensões para a aplicação WaCTool, considerando o uso de redes sociais e de alternativas para a anotação em vídeos

Several configurations of Unmanned Aerial Vehicles (UAVs) were proposed to support different applications. One of them is the tailsitter, a fixed-wing aircraft that takes off and lands on its own tail, with the high endurance advantage from fixed-wing aircraft and, as helicopters and multicopters, not requiring a runway during takeoff and landing. However, a tailsitter has a complex operation with multiple flight stages, each one with its own particularities and requirements, which emphasises the necessity of a reliable autopilot for its use as a UAV. The literature already introduces tailsitter UAVs with complex mechanisms or with multiple counter-rotating propellers, but not one with only one propeller and without auxiliary structures to assist in the takeoff and landing. This thesis presents a tailsitter UAV, named AVALON (Autonomous VerticAL takeOff and laNding), and its autopilot, composed of 3 main units: Sensor Unit, Navigation Unit and Control Unit. In order to choose the most appropriate techniques for the autopilot, different solutions are evaluated. For Sensor Unit, Extended Kalman Filter and Unscented Kalman Filter estimate spatial information from multiple sensors data. Lookahead, Pure Pursuit and Line-of-Sight, Nonlinear Guidance Law and Vector Field path-following algorithms are extended to incorporate altitude information for Navigation Unit. In addition, a structure based on classical methods with decoupled Proportional-Integral-Derivative controllers is compared to a new control structure based on dynamic inversion. Together, all these techniques show the efficacy of AVALONs autopilot. Therefore, AVALON results in a small electric tailsitter UAV with a simple design, with only one propeller and without auxiliary structures to assist in the takeoff and landing, capable of executing all flight stages.

O operador de Junção é um operador importante da Álgebra Relacional que combina os pares de tuplas que atendem a uma dada condição de comparação entre os valores dos atributos de duas relações. Quando a comparação avalia a similaridade entre pares de valores, o operador é chamado Junção por Similaridade. Esse operador tem aplicações em diversos contextos, tais como o suporte de tarefas de mineração e análise de dados em geral, e a detecção de quase-duplicatas, limpeza de dados e casamento de cadeias de caracteres em especial. Dentre os operadores de junção por similaridade existentes, a Junção por Abrangência (range join) é a mais explorada na literatura. Contudo, ela apresenta limitações, tal como a dificuldade para se encontrar um limiar de similaridade adequado. Nesse contexto, a Junção por k-vizinhos mais próximos (knearest neighbor join kNN join) é considerada mais intuitiva, e portanto mais útil que o range join. Entretanto, executar um kNN join é computacionalmente mais caro, o que demanda por abordagens baseadas na técnica de laço aninhado, e as técnicas existentes para a otimização do algoritmo são restritas a um domínio de dados em particular. Visando agilizar e generalizar a execução do kNN join, a primeira contribuição desta tese foi o desenvolvimento do algoritmo QuickNearest, baseado na técnica de divisão e conquista, que é independente do domínio dos dados, independente da função de distância utilizada, e que computa kNNjoins de maneira muito eficiente. Os experimentos realizados apontam que o QuickNearest chega a ser 4 ordens de magnitude mais rápido que os métodos atuais. Além disso, o uso de operadores de junção por similaridade em ambientes relacionais é problemático, principalmente por dois motivos: (i)emgeral o resultado tem cardinalidade muito maior do que o realmente necessário ou esperado pela maioria das aplicações de análise de dados; e (ii) as consultas que os utilizam envolvem também operações de ordenação, embora a ordem seja um conceito não associado à teoria relacional. A segunda contribuição da tese aborda esses dois problemas, tratando os operadores de junção por similaridade existentes como casos particulares de um conjunto mais amplo de operadores binários, para o qual foi definido o conceito de Wide-joins. Os operadores wide-joins recuperam os pares mais similares em geral e incorporam a ordenação como uma operação interna ao processamento, de forma compatível com a teoria relacional e que permite restringir a cardinalidade dos resultados a tuplas de maior interesse para as aplicações. Os experimentos realizados mostram que os wide-joins são rápidos o suficiente para serem usados em aplicações reais, retornam resultados de qualidade melhor do que os métodos concorrentes e são mais adequados para execução num ambiente relacional do que os operadores de junção por similaridade tradicionais.

Population ageing has been taking place all over the world, being estimated that 2.1 billion people will be aged 60 or over in 2050. Healthcare Supportive Home (HSH) Systems have been proposed to overcome the high demand of remote home care for assisting an increasing number of elderly people living alone. Since a heterogeneous team of healthcare professionals need to collaborate to continually monitor health status of chronic patients, a cooperation of pre-existing e-Health systems, both outside and inside home, is required. However, current HSH solutions are proprietary, monolithic, high coupled, and expensive, and most of them do not consider their interoperation neither with distributed and external e-Health systems, nor with systems running inside the home (e.g., companion robots or activity monitors). These systems are sometimes designed based on local legislations, specific health system configurations (e.g., public, private or mixed), care plan protocols, and technological settings available; therefore, their reusability in other contexts is sometimes limited. As a consequence, these systems provide a limited view of patient health status, are difficult to evolve regarding the evolution of patients health profile, do not allow continuous patients monitoring, and present limitations to support the self-management of multiple chronic conditions. To contribute to solve the aforementioned challenges, this thesis establishes HomecARe, a reference architecture for supporting the development of quality HSH systems. HomecARe considers HSH systems as Systems-of-Systems (SoS) (i.e., large, complex systems composed of heterogeneous, distributed, and operational and managerial independent systems), which achieve their missions (e.g., improvement of patients quality of life) through the behavior that emerges as result of collaborations among their constituents. To establish HomecARe, a systematic process to engineer reference architectures was adopted. As a result, HomecARe presents domain knowledge and architectural solutions (i.e., architectural patterns and tactics) described using conceptual, mission, and quality architectural viewpoints. To assess HomecARe, a case study was performed by instantiating HomecARe to design the software architecture of DiaManT@Home, a HSH system to assist at home patients suffering of diabetes mellitus. Results evidenced HomecARe is a viable reference architecture to guide the development of reusable, interoperable, reliable, secure, and adaptive HSH systems, bringing important contributions for the areas of e-Health, software architecture, and reference architecture for SoS.

The Division operator (&division;) from the Relational Algebra allows simple and intuitive representation of queries with the concept of \"for all\", and thus it is required by many real applications. However, the Relational Division is unable to support the needs of modern applications that manipulate complex data, such as images, audio, long texts, genetic sequences, etc. These data are better compared for similarity, whereas the Division always compares values for equality. Recent works focused on extending the Relational Algebra and database operators to support similarity comparison. This project incorporated the Similarity-Aware Divison Operator in a Relational Database Management System (RDBMS) and studied its relationship with other query operators. We extended a similarity-oriented SQL to represent the Similarity-Aware Division Operator in a simple and intuitive manner and implemented state-of-art algorithms, internal database queries and resources for similarity data manipulation all inside the RDBMS. This solution presents strategies for efficient and improved performance queries. For semantical validation, it was performed a case study of an application that finds prospective companies able to bid in public request for tenders (RFT) using similarity comparison on RFTs documents and companies\'s catalogs. We evaluated the quality of results in a case study with real datasets from request for tenders from public brazilian food companies. In the experiments, the Similarity-Aware Division Operator was able to identify which RFT which company can participate in with 90% recall.

O Aprendizado de Máquina trata da questão de como desenvolver programas de computador capazes de aprender um conceito ou hipótese a partir de um conjunto de exemplos ou casos observados. Baseado no conjunto de treinamento o algoritmo de aprendizado induz a classificação de uma hipótese capaz de determinar corretamente a classe de novos exemplos ainda não rotulados. Linguagens de descrição são necessárias para escrever exemplos, conhecimento do domínio bem como as hipóteses aprendidas a partir dos exemplos. Em geral, essas linguagens podem ser divididas em dois tipos: linguagem baseada em atributo-valor ou proposicional e linguagem relacional. Algoritmos de aprendizado são classificados como proposicional ou relacional dependendo da liguagem de descrição que eles utilizam. Além disso, no aprendizado simbólico o objetivo é gerar a classificação de hipóteses que possam ser facilmente interpretadas pelos humanos. Algoritmos de aprendizado proposicional utilizam a representação atributo-valor, a qual é inadequada para representar objetos estruturados e relações entre esses objetos. Por outro lado, a Programação lógica Indutiva (PLI) é realizada com o desenvolvimento de técnicas e ferramentas para o aprendizado relacional. Sistemas de PLI são capazes de aprender levando em consideração conhecimento do domínio na forma de um programa lógico e também usar a linguagem de programas lógicos para descrever o conhecimento induzido. Neste trabalho foi implementado um módulo chamado Kaeru para converter dados no formato atributo-valor para o formato relacional utilizado pelo sistema de PLI Aleph. Uma série de experimentos foram realizados com quatro conjuntos de dados naturais e um conjunto de dados real no formato atributo valor. Utilizando o módulo conversor Kaeru esses dados foram convertidos para o formato relacional utilizado pelo Aleph e hipóteses de classificação foram induzidas utilizando aprendizado proposicional bem como aprendizado relacional. É mostrado também, que o aprendizado proposicional pode ser utilizado para incrementar o conhecimento do domínio utilizado pelos sistemas de aprendizado relacional para melhorar a qualidade das hipóteses induzidas.

Esta Dissertação aborda o Problema de Alocação de Aulas a Salas (PAAS), também conhecido como Problema de Alocação de Salas (PAS). As instituições de ensino superior, no começo de seus calendários letivos, resolvem um PAAS ao determinar os espaços a serem utilizados para as atividades didáticas. Porém, em muitas destas instituições o PAAS é ainda resolvido manualmente, gerando altas cargas de trabalho para os responsáveis. Neste trabalho, o Instituto de Ciências Matemáticas e de Computação (ICMC) da Universidade de São Paulo (USP) foi tomado como caso de estudo para o PAAS. Um modelo de programação matemática inteiro é proposto e abordado por técnicas de resolução exata, metaheurísticas mono-objetivo e uma abordagem multi-objetivo. Uma estrutura de vizinhança proposta obteve resultados comparáveis à da metodologia exata, para um tempo fixo de execução. Demonstra-se que, a abordagem multi-objetivo é uma possibilidade de contornar algumas dificuldades clássicas do problema, como incertezas sobre a escolha dos pesos das métricas. Os métodos de solução propostos para o problema fornecem, aos responsáveis, bons instrumentos de auxílio à tomada de decisão para o PAAS.

The two-dimensional irregular cutting and packing problems (aka nesting problems) have been studied over the past six decades and consist in cutting (packing) convex and non-convex small pieces from (in) large boards without overlapping. There are several variants of this problem that are defined according to the board shapes and the objective of each problem. There are a number of heuristics proposed in the literature to solve irregular cutting and packing problems, but only few mixed-integer programming models. Specifically, these models were developed for the irregular strip packing problem, that consists in packing pieces into a single board with fixed width and length to be minimized. For the other problem variants, there is no exact methods presented in the literature. The main difficulty in solving irregular cutting and packing problems is how to handle with the geometric constraints. These constraints depend on the type of placement of the pieces on the board that can be continuous or discrete. In this thesis, we present two mixed-integer programming models for the irregular strip packing problem in which the pieces can be continuously placed on the board. These models do not demand complex structures to be built. We also present a new dot data structure to store the information on the placement of the pieces and overlapping positions bringing flexibility and efficiency to discrete approaches. Using this structure, a matheuristic is proposed, combining the advantages of the models with discrete and continuous placement positions for the pieces on the board. Furthermore, constraint programming models for several variants of irregular cutting and packing problems are exploited. For some variants, these models are the first modelling representation. A new global constraint is developed to eliminate the overlap among pieces. Computational experiments were conducted to evaluate the developed approaches.

A área de aprendizado de máquina adquiriu grande importância na última década graças à sua capacidade de analisar conjuntos de dados complexos em larga escala. Em diversas áreas do conhecimento existe a demanda pela análise de dados por especialistas, seja para obter agrupamentos latentes ou classificar instâncias em classes conhecidas. As ferramentas acessíveis a especialistas leigos em programação são limitadas a problemas específicos e demandam um custo de desenvolvimento às vezes proibitivo, sendo interessante buscar por ferramentas genéricas e aplicáveis a qualquer área do conhecimento. Este trabalho busca estender e implementar uma metodologia genérica de aprendizado de máquina capaz de analisar quaisquer conjuntos de arquivos de forma praticamente livre de configuração. Foram obtidos resultados satisfatórios de sua aplicação em um conjunto amplo de problemas para agrupamento e classificação de executáveis, spam e detecção de línguas.

Online social networks (OSNs) are Web platforms providing different services to facilitate social interaction among their users. A particular kind of OSNs is the location-based social network (LBSN), which adds services based on location. One of the most important challenges in LBSNs is the link prediction problem. Link prediction problem aims to estimate the likelihood of the existence of future friendships among user pairs. Most of the existing studies in link prediction focus on the use of a single information source to perform predictions, i.e. only social information (e.g. social neighborhood) or only location information (e.g. common visited places). However, some researches have shown that the combination of different information sources can lead to more accurate predictions. In this sense, in this thesis we propose different link prediction methods based on the use of different information sources naturally existing in these networks. Thus, we propose seven new link prediction methods using the information related to user membership in social overlapping groups: common neighbors within and outside of common groups (WOCG), common neighbors of groups (CNG), common neighbors with total and partial overlapping of groups (TPOG), group naïve Bayes (GNB), group naïve Bayes of common neighbors (GNB-CN), group naïve Bayes of Adamic-Adar (GNB-AA) and group naïve Bayes of Resource Allocation (GNB-RA). Due to that social groups exist naturally in networks, our proposals can be used in any type of OSN.We also propose new eight link prediction methods combining location and social information: Check-in Observation (ChO), Check-in Allocation (ChA), Within and Outside of Common Places (WOCP), Common Neighbors of Places (CNP), Total and Partial Overlapping of Places (TPOP), Friend Allocation Within Common Places (FAW), Common Neighbors of Nearby Places (CNNP) and Nearby Distance Allocation (NDA). These eight methods are exclusively for work in LBSNs. Obtained results indicate that our proposals are as competitive as state-of-the-art methods, or better than they in certain scenarios. Moreover, since our proposals tend to be computationally more efficient, they are more suitable for real-world applications.

O aprendizado semissupervisionado baseado em uma única classe, amplamente conhecido pelo termo em inglês Positive and Unlabeled Learning (PUL), é um método atrativo para aplicações práticas, pois o usuário só precisa rotular documentos de seu interesse, evitando o esforço de rotular documentos para todas as classes da coleção, tarefa necessária nos métodos multiclasse. Além dos documentos de interesse do usuário, são utilizados também documentos não rotulados durante o processo de aprendizagem, para então classificar os documentos entre classe de interesse ou não (também denominados como documentos positivos e negativos respectivamente). Esse método de aprendizado pode ser utilizado para construir modelos de classificação, recuperação de informação, ou sistemas de recomendação. As abordagens PUL encontradas na literatura raramente fazem uso da representação de dados por meio de grafos. Dado que esse meio de representação de dados é pouco explorado no contexto de PUL, e dado que seu uso em abordagens do aprendizado semissupervisionado para classificação de textos produz resultados tão bons quanto e até melhores que abordagens baseadas no modelo espaço-vetorial, neste projeto de mestrado, é proposto uma abordagem baseada em grafo para PUL denominada, Label Propagation for Positive and Unlabeled Learning (LP-PUL). O método proposto consiste de 3 etapas: (i) construção do grafo para representação da coleção textual, (ii) identificação de documentos negativos, e (iii) propagação dos rótulos positivo e negativo para os demais documentos não rotulados. Foi realizada uma extensa avaliação empírica utilizando um grande número de coleções e parâmetros para cada algoritmo utilizado. Durante a avaliação, foi medido o impacto das diferentes escolhas de algoritmos para cada etapa acima mencionadas. Além disso, o método proposto foi comparado com algoritmos PUL baseados em grafos e no modelo espaço-vetorial. Ao final, foi demonstrado que o método proposto obtém melhor performance de classificação que os demais algoritmos PUL.

A navegação autônoma é um dos problemas fundamentais da robótica móvel. Para um robô executar esta tarefa, é necessário determinar a região segura para a navegação. Este trabalho propõe um sistema de identificação de superfícies navegáveis baseado em visão computacional utilizando redes neurais artificiais. Mais especificamente, é realizado um estudo sobre a utilização de diferentes atributos de imagem, como descritores estatísticos e elementos de espaços de cores, para serem utilizados como entrada das redes neurais artificiais que tem como tarefa a identificação de superfícies navegáveis. O sistema desenvolvido utiliza resultados de classificação de múltiplas configurações de redes neurais artificiais, onde a principal diferença entre elas é o conjunto de atributos de imagem utilizados como entrada. Essa combinação de diversas classificações foi realizada visando maior robustez e melhor desempenho na identificação de vias em diferentes cenários