Submitted by Lucienne Costa (lucienneferreira@ufcg.edu.br) on 2018-05-02T21:20:23Z No. of bitstreams: 1 DIMAS CASSIMIRO DO NASCIMENTO FILHO – TESE (PPGCC) 2017.pdf: 1879329 bytes, checksum: bda72914ec66d17611d9d0ab5b9ec6d5 (MD5) / Made available in DSpace on 2018-05-02T21:20:23Z (GMT). No. of bitstreams: 1 DIMAS CASSIMIRO DO NASCIMENTO FILHO – TESE (PPGCC) 2017.pdf: 1879329 bytes, checksum: bda72914ec66d17611d9d0ab5b9ec6d5 (MD5) Previous issue date: 2017-11-10 / Na era de Big Data, na qual a escala dos dados provê inúmeros desafios para algoritmos clássicos, a tarefa de avaliar a qualidade dos dados pode se tornar custosa e apresentar tempos de execução elevados. Por este motivo, gerentes de negócio podem optar por terceirizar o monitoramento da qualidade de bancos de dados para um serviço específico, usualmente baseado em computação em nuvem. Neste contexto, este trabalho propõe abordagens para redução de custos da tarefa de deduplicação de dados, a qual visa detectar entidades duplicadas em bases de dados, no contexto de um serviço de qualidade de dados em nuvem. O trabalho tem como foco a tarefa de deduplicação de dados devido a sua importância em diversos contextos e sua elevada complexidade. É proposta a arquitetura em alto nível de um serviço de monitoramento de qualidade de dados que emprega o provisionamento dinâmico de recursos computacionais por meio da utilização de heurísticas e técnicas de aprendizado de máquina. Além disso, são propostas abordagens para a adoção de algoritmos incrementais de deduplicação de dados e controle do tamanho de blocos gerados na etapa de indexação do problema investigado. Foram conduzidos quatro experimentos diferentes visando avaliar a eficácia dos algoritmos de provisionamento de recursos propostos e das heurísticas empregadas no contexto de algoritmos incrementais de deduplicação de dados e de controle de tamanho dos blocos. Os resultados dos experimentos apresentam uma gama de opções englobando diferentes relações de custo e benefício, envolvendo principalmente: custo de infraestrutura do serviço e quantidade de violações de SLA ao longo do tempo. Outrossim, a avaliação empírica das heurísticas propostas para o problema de deduplicação incremental de dados também apresentou uma série de padrões nos resultados, envolvendo principalmente o tempo de execução das heurísticas e os resultados de eficácia produzidos. Por fim, foram avaliadas diversas heurísticas para controlar o tamanho dos blocos produzidos em uma tarefa de deduplicação de dados, cujos resultados de eficácia são bastante influenciados pelos valores dos parâmetros empregados. Além disso, as heurísticas apresentaram resultados de eficiência que variam significativamente, dependendo da estratégia de poda de blocos adotada. Os resultados dos quatro experimentos conduzidos apresentam suporte para demonstrar que diferentes estratégias (associadas ao provisionamento de recursos computacionais e aos algoritmos de qualidade de dados) adotadas por um serviço de qualidade de dados podem influenciar significativamente nos custos do serviço e, consequentemente, os custos repassados aos usuários do serviço. / In the era of Big Data, in which the scale of the data provides many challenges for classical algorithms, the task of assessing the quality of datasets may become costly and complex. For this reason, business managers may opt to outsource the data quality monitoring for a specific cloud service for this purpose. In this context, this work proposes approaches for reducing the costs generated from solutions for the data deduplication problem, which aims to detect duplicate entities in datasets, in the context of a service for data quality monitoring. This work investigates the deduplication task due to its importance in a variety of contexts and its high complexity. We propose a high-level architecture of a service for data quality monitoring, which employs provisioning algorithms that use heuristics and machine learning techniques. Furthermore, we propose approaches for the adoption of incremental data quality algorithms and heuristics for controlling the size of the blocks produced in the indexing phase of the investigated problem. Four different experiments have been conducted to evaluate the effectiveness of the proposed provisioning algorithms, the heuristics for incremental record linkage and the heuristics to control block sizes for entity resolution. The results of the experiments show a range of options covering different tradeoffs, which involves: infrastructure costs of the service and the amount of SLA violations over time. In turn, the empirical evaluation of the proposed heuristics for incremental record linkage also presented a number of patterns in the results, which involves tradeoffs between the runtime of the heuristics and the obtained efficacy results. Lastly, the evaluation of the heuristics proposed to control block sizes have presented a large number of tradeoffs regarding execution time, amount of pruning approaches and the obtained efficacy results. Besides, the efficiency results of these heuristics may vary significantly, depending of the adopted pruning strategy. The results from the conducted experiments support the fact that different approaches (associated with cloud computing provisioning and the employed data quality algorithms) adopted by a data quality service may produce significant influence over the generated service costs, and thus, the final costs forwarded to the service customers.

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Com o passar do tempo, a demanda elétrica de diversas áreas varia tornando necessária a construção de novos geradores elétricos e a expansão da rede de transmissão de energia elétrica. Nesta dissertação, focamos no problema de expansão da rede de transmissão, assumindo que novos geradores estão construídos para suprir as novas demandas. Essa expansão exige altos investimentos que precisam ser cuidadosamente planejados. O problema pode ser modelado como um problema de otimização não linear inteira mista e pertence à classe dos problemas NP-difíceis. Desta forma, uma abordagem heurística pode ser adequada para a sua solução pois pode vir a fornecer boas soluções em tempo computacional aceitável. Esta dissertação se propõe a apresentar um estudo do problema de planejamento da expansão de redes de transmissão de energia elétrica estático e multiestágio. Mostramos o que já existe na literatura para o que é chamado de problema sem redimensionamento e as inovações feitas por nós para o problema com redimensionamento. Quanto aos métodos de solução, utilizamos a metaheurística GRASP para o problema estático e combinamos o GRASP com o procedimento Backward-Forward quando falamos em problema multiestágio. Nesta dissertação comparamos os resultados computacionais obtidos com resultados encontrados na literatura. / At times, the electrical load in diferent areas varies, claiming the construction of new electric generators and the expansion of the electrical transmission network. In this dissertation we focus on the transmission expansion planning problem, assuming that new generators are built to meet the new demands. This expansion requires large investments, which need to be carefully planned. This problem can be modeled as a mixed nonlinear programming problem, considered to be a NP-hard problem. Therefore a heuristic approach may be appropriate for its solution because it might be able to provide good solutions in satisfactory computational time. This dissertation intends to present a study of both the static and multistage transmission expansion planning problem. We present first a review of the most interesting works found in the technical literature. Then, we present metaheuristics for the static and multistage problems with re-design. These etaheuristics extend known algorithms for the problems without re-design. For the static problem, we extend a GRASP procedure and for the multistage problem, we embed the GRASP (or an exact method) into a backward-forward algorithm. We test our algorithms on real-based power transmission networks and compare them to the results found in the litterature.

Nesta dissertação coloca-se em destaque o ensino de Funções na preparação para o Exame Nacional do Ensino Médio (ENEM), através da investigação de novas perspectivas para o tratamento do assunto, tendo por base referenciais teóricos das áreas da Matemática e da Educação e saberes produzidos por professores de matemática em seu exercício da docência. Busca-se com este trabalho estabelecer um canal de ligação e de problematização entre professores acerca do ENEM e do ensino de matemática, em especial do ensino de Função. Para tal, se faz um mergulho histórico evolutivo sobre tal conceito, com o apoio de autores como Boyer, Cajori e Eves. Também são analisadas algumas questões do ENEM no que diz respeito ao conceito matemático de Função e às heurísticas possíveis de serem desenvolvidas durante a resolução dessas questões/problemas. Nessa etapa, contase fundamentalmente com a contribuição de Caraça e Polya. E, no sentido de ampliar os referenciais teóricos para uma análise qualitativa do tema, o autor descreve muitas de suas experiências como docente e ainda, apoiado na metodologia da História Oral, utiliza os registros obtidos de entrevistas realizadas com três professores de matemática em exercício, devidamente documentadas através de filmagens e transcrições. Assim, as vozes de professores relativas às suas experiências pedagógicas, desde a sua formação acadêmica até o momento atual e, principalmente, seu posicionamento frente às funções e ao ENEM, vieram a complementar o campo de análise e, inclusive, a expandir as alternativas de investigação. Dos resultados da pesquisa, destaca-se que o assunto Função tem surgido, como um aliado, nas práticas educativas, uma vez que a variabilidade, a relação de dependência, as regularidades estão de tal forma presentes na vida dos alunos que acabam servindo como fonte motivacional à aprendizagem de uma teoria que trata de tais aspectos e, sem dúvida, tudo isso favorece a formulação de problemas, a proposição de experimentos e a utilização da multidisciplinaridade na sala de aula. / On this piece of work it is presented, in a highlighted way, the teaching of Functions for High School National Exam (ENEM), through the investigation of new prospects in dealing with this issue, having theoretical references of Mathematics as well as Education as the bases, along with the knowledge carried by Mathematics teachers when on duty. This work pursues to establish a linking channel among teachers regarding ENEM and the teaching of Math, specially the teaching of Functions. For that, a historical evolutionary diving about such a concept is made, supported by authors as Boyer, Cajori and Eves. It is also analysed some ENEM tests about the Mathematical concept of Functions and the possibly heuristics to be developed during the resolution of those tests / problems. At this point, mainly the contribution of Caraça and Polya is counted. And, for broadening the theoretical references for a qualitative analysis of the theme, the author describes many of his own experiences as a teacher. Besides, supported by the methodology of Oral History, he uses the footages of three math teachers interviewed on duty. So, the teachers’ pedagogical experiences, from their beginning up to now and, mainly, their points of view regarding Functions and ENEM, complemented the analysis and expanded the alternatives of investigation. Out of the research results, it is highlighted that the topic Functions have come up, in educational practices, as an ally, since the variability, the relation of dependence, the regularities are presented in the life of students in such ways that they motivate apprenticeship. Without doubt, all these points benefit the formulation of problems, the proposal of experiments and the use of multidisciplinary in classroom.

O Problema do Lapidário tem como objetivo encontrar o modelo de lapidação que resulte no maior aproveitamento volumétrico para uma dada gema bruta. Nesta dissertação apresentamos um Algoritmo Genético com variáveis de valores reais, e um GRASP Contínuo como heurísticas para resolução deste problema. Ambos os algoritmos maximizam o fator de escala do modelo de lapidação, sobre todas as posições de centro e ângulos de giro que o modelo pode assumir, buscando encontrar o modelo de maior volume inscrito no interior da gema, representada virtualmente por uma malha triangular. Propomos também um algoritmo de avaliação de uma instância do problema, o qual determina eficientemente o maior fator de escala, para um dado centro e orientação, que o modelo de lapidação pode assumir permanecendo completamente no interior da gema. Os algoritmos propostos foram avaliados em um conjunto de 50 gemas reais para o problema, utilizando como modelos base os cortes redondo e oval. Por fim, comparamos os resultados computacionais obtidos em relação a aproveitamento volumétrico e tempo de execução com os principais trabalhos relatados na literatura, demonstrando que as heurísticas propostas são competitivas com as demais abordagens. / The goal of the gemstone cutting problem is to find the largest cutting design which fits inside a given rough gemstone. In this work, we propose a real-valued Genetic Algorithm and a Continuous GRASP heuristic to solve it. The algorithms determine the largest scaling factor, over all possibilities of centers and orientations which the cutting could assume, finding the cutting with the largest volume as possible inside a gemstone, represented by a triangular mesh. We also propose an algorithm to evaluate a problem instance. This method efficiently determines the greatest scaling factor, for a given center and orientation, such that the cutting fits inside the rough gemstone. The proposed algorithms are validated for an instance set of 50 real-world gemstones, using the round and oval cuttings. Finally, we compare our computational results, for volume yield and running time, with the state-of-art. Ours methods are proved be competitive with the previous approachs.

A geração de quadros de horários escolares é um problema clássico de otimização que tem sido largamente estudado devido a sua importâncias prática e teórica. O problema consiste em alocar um conjunto de aulas entre professor-turma em períodos de tempo pré-determinados, satisfazendo diferentes tipos de requisitos. Devido a natureza combinatória do problema, a resolução de instâncias médias e grandes torna-se uma tarefa desafiadora. Quando recursos são escassos, mesmo uma solução factível pode ser difícil de ser encontrada. Várias técnicas tem sido propostas na literatura científica para resolver o problema de geração de quadros de horários escolares, no entanto, métodos robustos ainda não existem. Visto que o uso de métodos exatos, como por exemplo, técnicas de programação matemática, não podem ser utilizados na prática, para resolver instâncias grandes da realidade, meta-heurísticas e meta-heurísticas híbridas são usadas com frequência como abordagens de resolução. Nesta pequisa, são desenvolvidas técnicas que combinam programação matemática e heurísticas, denominadas mateheurísticas, para resolver de maneira eficiente e robusta algumas variações de problemas de geração de quadros de horários escolares. Embora neste trabalho sejam abordados problemas encontrados no contexto de instituições brasileiras, os métodos propostos também podem ser aplicados em problemas similares oriundo de outros países. / The school timetabling is a classic optimization problem that has been extensively studied due to its practical and theoretical importance. It consists in scheduling a set of class-teacher meetings in a prefixed period of time, satisfying requirements of different types. Given the combinatorial nature of this problem, solving medium and large instances of timetabling to optimality is a challenging task. When resources are tight, it is often difficult to find even a feasible solution. Several techniques have been developed in the scientific literature to tackle the high school timetabling problem, however, robust solvers do not exist yet. Since the use of exact methods, such as mathematical programming techniques, is considered impracticable to solve large real world instances, metaheuristics and hybrid metaheuristics are the most used solution approaches. In this research we develop techniques that combine mathematical programming and heuristics, so-called matheuristics, to solve efficiently and in a robust way some variants of the high school timetabling problem. Although we pay special attention to problems arising in Brazilian institutions, the proposed methods can also be applied to problems from different countries.

O objetivo do artigo apresentado é analisar dilemas de efetividade na atividade de Inteligência Governamental. Explorando a literatura sobre falhas de inteligência e surpresa estratégica, avançamos em um campo pouco explorado pelos Estudos de Inteligência no Brasil: os aspectos cognitivos dos analistas de inteligência e as relações entre a comunidade política e a comunidade de inteligência. Primeiramente discorremos sobre os desafios de se avaliar a Inteligência Governamental como política pública, em especial no que se refere à dimensão da efetividade. Na segunda sessão abordamos os principais vieses cognitivos e heurísticas possíveis de ocorrer durante a análise de inteligência. A terceira sessão trata das tensões relacionais características entre a esfera política e a comunidade de inteligência e como essa relação afeta no resultado final da atividade de inteligência. Nas considerações finais apontamos para os limites e possibilidades das reformas organizacionais e procedimentais no que se refere à efetividade dos sistemas de inteligência. / The objective of this paper is to analyze the effectiveness‟ dilemmas of government intelligence activities. Exploring the literature on intelligence failures and strategic surprise, we move towards a little explored field on Brazilian Intelligence Studies: the cognitive aspects of intelligence analysts and the relations between the political community and the intelligence community. First we balance the challenges of evaluating government intelligence as public policy, particularly regarding the effectiveness dimension. In the second session, we discuss the main cognitive biases and heuristics that can occur during intelligence analysis. The third section discusses the typical relational tensions between the political sphere and the intelligence community and how that relationship affects the final result of intelligence activity. In the concluding remarks, we point to the limits and possibilities of organizational and procedural reforms on the effectiveness of intelligence systems.

The anchoring effect is defined as the tendency of human thought to the fixation on certain pieces of information that affect decision-making. In the same context, the underconfidence bias is understood as an agent’s propensity to underestimate his or her own objective performance. While some aspects of these phenomena are well known, there are no formal models that specifically describe the relationship between both. This paper presents: i) an experiment that illustrates the anchoring effect on the underconfidence bias by both reducing and amplifying such bias in the domain of geographic decision tasks and ii) the foundations of a new mathematical model that promotes precision in the study of the relationship between anchoring and underconfidence. / Se define el efecto de anclaje como la tendencia del pensamiento humano a la fijación endeterminados fragmentos de información que afectan la toma de decisiones. El sesgo de subconfianza, por su parte, se entiende como la propensión de un agente a subestimar su desempeño objetivo. Si bien se conocen algunos aspectos de la interacción entre ambos efectos, no se dispone de modelos formales que describan tal relación específica. Este estudio presenta: i) un experimento que pone en evidencia el efecto que ejerce el anclaje tanto para reducir, como para amplificar la subconfianza en tareas de decisión geográfica y ii) los fundamentos de un modelo matemático novedoso que permite estudiar con mayor precisión la relación del anclaje con la subconfianza

Cette thèse propose une approche originale d’ordonnancement de la production de plates-formes de machines hétérogènes et distribuées, utilisées en parallèle pour fournir un service global commun. L’originalité de la contribution réside dans la proposition de modifier les conditions opératoires des machines au cours de leur utilisation. Il est supposé qu'utiliser une machine avec des performances dégradées par rapport à un fonctionnement nominal permet d'allonger sa durée de vie avant maintenance. L’étude s’inscrit dans la partie décisionnelle du PHM (Prognostics and Health Management), au sein duquel une étape de pronostic permet de déterminer les durées de vie résiduelles des machines. Le problème d’optimisation consiste à déterminer à chaque instant l’ensemble des machines à utiliser et un profil de fonctionnement pour chacune d’entre elles de manière à maximiser l’horizon de production de la plate-forme avant maintenance. Deux modèles sont proposés pour la définition des profils de fonctionnement. Le premier traduit le comportement à l'usure de machines pouvant fournir un nombre discret de performances. Pour ce cas, la complexité de plusieurs variantes du problème d'optimisation est étudiée et plusieurs méthodes de résolution optimales et sous-optimales sont proposées pour traiter le problème d'ordonnancement. Plusieurs méthodes de résolution sous-optimales sont ensuite proposées pour le second modèle, qui s'applique à des machines dont le débit peut varier de manière continue entre deux bornes. Ces travaux permettent de déterminer la durée maximale d’utilisation avant défaillance d’un système à partir des durées de vie résiduelles des équipements qui le composent. / This thesis addresses the problem of maximizing the production horizon of a heterogeneous distributed platform composed of parallel machines and which has to provide a global production service. Each machine is supposed to be able to provide several throughputs corresponding to different operating conditions. It is assumed that using a machine with degraded performances compared to nominal ones allows to extend its useful life before maintenance. The study falls within the decisional step of PHM (Prognostics and Health Management), in which a prognostics phase allows to determine remaining useful lives of machines. The optimization problem consists in determining the set of machines to use at each time and a running profile for each of them so as to maximize the production horizon before maintenance. Machines running profiles are defined on the basis of two models. First one depicts the behavior of machines used with a discrete number of performances. For this case, the problem complexity is first studied considering many variants of the optimization problem. Several optimal and sub-optimal resolution methods are proposed to deal with the scheduling problem. Several sub-optimal resolution methods are then proposed for the second model, which applies to machines whose throughput rate can vary continuously between two bounds. These research works allow to determine the time before failure of a system on the basis of its components remaining useful lives.

Une carte généralisée est un modèle topologique permettant de représenter implicitementun ensemble de cellules (sommets, arêtes, faces , volumes, . . .) ainsi que l’ensemblede leurs relations d’incidence et d’adjacence au moyen de brins et d’involutions. Les cartes généralisées sont notamment utilisées pour modéliser des images et objets3D. A ce jour il existe peu d’outils permettant l’analyse et la comparaison de cartes généralisées.Notre objectif est de définir un ensemble d’outils permettant la comparaisonde cartes généralisées.Nous définissons tout d’abord une mesure de similarité basée sur la taille de la partiecommune entre deux cartes généralisées, appelée plus grande sous-carte commune.Nous définissons deux types de sous-cartes, partielles et induites, la sous-carte induitedoit conserver toutes les involutions tandis que la sous-carte partielle autorise certaines involutions à ne pas être conservées. La sous-carte partielle autorise que les involutionsne soient pas toutes conservées en analogie au sous-graphe partiel pour lequelles arêtes peuvent ne pas être toutes présentes. Ensuite nous définissons un ensembled’opérations de modification de brins et de coutures pour les cartes généralisées ainsiqu’une distance d’édition. La distance d’édition est égale au coût minimal engendrépar toutes les successions d’opérations transformant une carte généralisée en une autrecarte généralisée. Cette distance permet la prise en compte d’étiquettes, grâce à l’opérationde substitution. Les étiquettes sont posées sur les brins et permettent d’ajouter del’information aux cartes généralisées. Nous montrons ensuite, que pour certains coûtsnotre distance d’édition peut être calculée directement à partir de la plus grande souscartecommune.Le calcul de la distance d’édition est un problème NP-difficile. Nous proposons unalgorithme glouton permettant de calculer en temps polynomial une approximation denotre distance d’édition de cartes. Nous proposons un ensemble d’heuristiques baséessur des descripteurs du voisinage des brins de la carte généralisée permettant de guiderl’algorithme glouton, et nous évaluons ces heuristiques sur des jeux de test générésaléatoirement, pour lesquels nous connaissons une borne de la distance.Nous proposons des pistes d’utilisation de nos mesures de similarités dans le domainede l’analyse d’image et de maillages. Nous comparons notre distance d’éditionde cartes généralisées avec la distance d’édition de graphes, souvent utilisée en reconnaissancede formes structurelles. Nous définissons également un ensemble d’heuristiquesprenant en compte les étiquettes de cartes généralisées modélisant des images etdes maillages. Nous mettons en évidence l’aspect qualitatif de notre appariement, permettantde mettre en correspondance des zones de l’image et des points du maillages. / A generalized map is a topological model that allows to represent implicitly differenttypes of cells (vertices, edges, volumes, . . . ) and their relationship by using a set of dartsand some involutions. Generalized maps are used to model 3D meshes and images.Anyway there exists only few tools to compare theses generalized maps. Our main goalis to define some tools tolerant to error to compare them.We define a similarity measure based on the size of the common part of two generalizedmaps, called maximum common submap. Then we define two types of submaps,partial and induced, the induced submap needs to preserve all the involutions whereasthe partial one can allow some involutions to be removed. Then we define a set of operationsto modify a generalized map into another and the associated edit distance. Theedit distance is equal to the minimal cost of all the sequences of operations that modifya generalized map into the other. This edit distance can use labels to consider additionalinformation, with the operation called ’substitution’. Labels are set on darts. Wenext showa relation between our edit distance and the distance based on the maximumcommon submap.Computing theses distance are aNP-hard problem.We propose a greedy algorithmcomputing an approximation of it. We also propose a set of heuristics based on thedescription of the neighborhoob of the darts to help the greedy algorithm.We try thesesheuristics on a set of generalized maps randomly generated where a lower bound of thedistance is known. We also propose some applications of our similarity measures inthe image analysis domain. We compare our edit distance on generalized maps withthe edit distance on graphs. We also define a set of labels specific on images and 3Dmeshes. And we show that the matching computed by our algorithm construct a linkbetween images’s areas.

Este trabalho é direcionado ao problema de Programação de Operações No-Idle Flow Shop Permutacional. Uma propriedade do problema, oriunda de estudo sobre a sua característica, é apresentada e utilizada para o desenvolvimento de um novo método heurístico construtivo, com o objetivo de minimizar a Duração Total da Programação (makespan). O novo método é comparado com os melhores heurísticos construtivos reportados na literatura, conhecidos por IG, KK e FRB3. Os resultados da experimentação computacional mostraram o melhor desempenho do método proposto, denominado BHBN, para os problemas testes de Ruiz et al. (2008) e Taillard (1993), quanto à qualidade da solução, apresentando também eficiência computacional. / This work is addressed to the No-Idle Flow Shop Sequencing problem. As a result of an investigation on the problem characteristics it is presented a property of this scheduling problem, which is used for the development of a new constructive heuristic with the objective of minimizing the Total Time to complete the schedule (makespan). The new method is compared with the best constructive heuristics reported in the literature, named IG, KK and FRB3. Results from computational experience showed the best performance of the proposed method, denoted by BHBN, for the instances of Ruiz et al. (2008) and Taillard (1993), as to the quality of the solution, and also computational efficiency.