RODRIGUES, Carlos Diego. Limites inferiores para o problema de coloração de vértices via geração de cortes e colunas. 2008. 79 f. Dissertação (Mestrado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2008. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-07-11T11:50:40Z No. of bitstreams: 1 2005_dis_cdrodrigues.pdf: 545679 bytes, checksum: 7cceeca6a76bce10cbde4bfb4ef0ee02 (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2016-07-14T15:28:23Z (GMT) No. of bitstreams: 1 2005_dis_cdrodrigues.pdf: 545679 bytes, checksum: 7cceeca6a76bce10cbde4bfb4ef0ee02 (MD5) / Made available in DSpace on 2016-07-14T15:28:23Z (GMT). No. of bitstreams: 1 2005_dis_cdrodrigues.pdf: 545679 bytes, checksum: 7cceeca6a76bce10cbde4bfb4ef0ee02 (MD5) Previous issue date: 2008 / In this work the vertex coloring problem is approached via integer programming. A tighter version of the independent set formulation is used, where the vertex-related constraints are substituted by subgraph-related constraints. Each constraint establishes a lower bound on the number of independent sets intersecting a subgraph H. It is shown a sufficient condition for this inequality to define a facet of the associated polytope. Basically, H is required to be color critical, not included in another color critical subgraph, and to have a connected complement. Also, the column generation algorithm proposed by Mehotra and Trick (INFORMS Journal in Computing, 1996) is adapted to allow the addition of cutting planes and to provide lower bounds along the process, which may abbreviate its end. Some computational experiments are reported. / Neste trabalho abordamos o problema de coloração de vértices via programação inteira. Uma versão expandida da formulação por conjuntos independentes é utilizada para abrigar outras sub-estruturas do grafos além dos vértices. Cada uma dessas sub-estruturas define uma restrição que determina quantos conjuntos independentes são necessarios para cobrir aquele subgrafo. Experimentos com um método de geração de cortes e colunas para o problema são feitos para determinar um limite inferior para um conjunto de instâncias classicas para esse problema a biblioteca DIMACS.

LIMA, Francisco Fabrício de Paula. SysSU - Um sistema de suporte para computação ubíqua. 2011. 107 f. Dissertação (Mestrado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2011. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-07-11T15:53:35Z No. of bitstreams: 1 2011_dis_ffplima.pdf: 1543787 bytes, checksum: 3b02c96cda4fd7f0e19e88d80edc5ee5 (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2016-07-15T15:39:54Z (GMT) No. of bitstreams: 1 2011_dis_ffplima.pdf: 1543787 bytes, checksum: 3b02c96cda4fd7f0e19e88d80edc5ee5 (MD5) / Made available in DSpace on 2016-07-15T15:39:54Z (GMT). No. of bitstreams: 1 2011_dis_ffplima.pdf: 1543787 bytes, checksum: 3b02c96cda4fd7f0e19e88d80edc5ee5 (MD5) Previous issue date: 2011 / The hardware technologies necessary for the realization of Ubiquitous Computing (eg, smartphones, tablets, sensors and smart appliances) have evolved and, today, software components that enable new forms of interaction, able to recognize the face and voice of users, track its location and provide ways to incorporate augmented reality, needed in ubiquitous environments, are being widely developed. In addition, the Software Engineering has evolved to incorporate new development techniques seeking to increase quality and reduce production time of these software artifacts. However, in Ubiquitous Computing difficulties arise in the design of architectures, modeling collaboration among heterogeneous software components, system engineering, and marketing, implementation and validation of the system as a whole. Thus, the development of ubiquitous systems still presents many challenges due to the great diversity and complexity of your requirements. Especially, in ubiquitous environments, where the volatility and heterogeneity of devices, services and applications are common features, and unbound forms of interactions between entities in interoperable distributed software system becomes essential. This volatility and heterogeneity influence the way services are provided in the system, as they are discovered and invoked and how their activities are coordinated to achieve the ultimate goal of the applications. Therefore, this dissertation proposes a new software infrastructure in the form of a support system, called SysSU (System Support for Ubiquity). This support system is shown by a reference architecture and a formal specification. The architecture is based on models Linda and publish / subscribe for the purpose of achieving the desired decoupling. Since the formal specification determines the semantics of the primitives used for the interactions between software components and syntax of the messages exchanged between them in order to standardize implementations. To validate the proposed work, a reference implementation, based on formal specification and architecture, was built. This implementation was used to develop a case study consisting of two separate applications, and UbiPrinter GREat Tour, which exhibit characteristics of volatility and heterogeneity. / As tecnologias de hardware necessárias para a realização da Computação Ubíqua (e.g., smartphones, tablets, sensores e eletrodomésticos inteligentes) evoluíram e, atualmente, componentes de software que possibilitam novas formas de interação, capazes de reconhecer a face e a voz dos usuários, rastrear a sua localização e prover formas de incorporar realidade aumentada, necessários em ambientes ubíquos, estão sendo largamente desenvolvidos. Além disso, a Engenharia de Software evoluiu e passou a incorporar novas técnicas de desenvolvimento buscando aumentar a qualidade e diminuir o tempo de produção desses artefatos de software. Contudo, na Computação Ubíqua as dificuldades surgem no projeto das arquiteturas, na modelagem da colaboração entre os componentes de software heterogêneos, na engenharia do sistema, e na comercialização, implantação e validação do sistema como um todo. Assim, o desenvolvimento de sistemas ubíquos ainda apresenta inúmeros desafios devido à grande diversidade e complexidade dos seus requisitos. Particularmente, em ambientes ubíquos, onde a volatilidade e a heterogeneidade de dispositivos, serviços e aplicações são características comuns, formas de interações desacopladas e interoperáveis entre as entidades de software distribuídas no sistema tornam-se essenciais. Essa volatilidade e heterogeneidade influencia a forma como os serviços são disponibilizados no sistema, como são descobertos e invocados e como suas atividades são coordenadas para se atingir o objetivo final das aplicações. Nesse contexto, este trabalho de dissertação propõe uma nova infraestrutura de software, na forma de um sistema de suporte, denominada SysSU (System Support for Ubiquity). Esse sistema de suporte é apresentado por meio de uma arquitetura de referência e de uma especificação formal. A arquitetura é baseada nos modelos Linda e publish/subscribe com o propósito de se atingir o desacoplamento desejado. Já a especificação formal determina a semântica das primitivas utilizadas para as interações entre os componentes de software e a sintaxe das mensagens trocadas entre eles com o objetivo de padronizar as implementações. Para validar o trabalho proposto, uma implementação de referência, baseada na arquitetura e na especificação formal, foi construída. Essa implementação foi utilizada no desenvolvimento de um estudo de caso consistindo de duas aplicações distintas, GREat Tour e UbiPrinter, que apresentam características de volatilidade e heterogeneidade.

SILVA, Jefferson de Carvalho. Infra-estrutura de componentes paralelos para aplicações de computação de alto desempenho. 2008. 116 f. Dissertação (Mestrado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2008. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-07-11T17:12:14Z No. of bitstreams: 1 2008_dis_jcsilva.pdf: 2178874 bytes, checksum: 5bcf83ebb42062e08e5e2782af8986e8 (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2016-07-18T14:56:45Z (GMT) No. of bitstreams: 1 2008_dis_jcsilva.pdf: 2178874 bytes, checksum: 5bcf83ebb42062e08e5e2782af8986e8 (MD5) / Made available in DSpace on 2016-07-18T14:56:45Z (GMT). No. of bitstreams: 1 2008_dis_jcsilva.pdf: 2178874 bytes, checksum: 5bcf83ebb42062e08e5e2782af8986e8 (MD5) Previous issue date: 2008 / The development of new High Performance Computing (HPC) application has demanded a set of tools for reconciling high level of a abstraction with software integration. In particular, we are interested in component-based solutions presented by the scientific community in the last years. Components have been applied to meet new requirements of high performance application such as: interoperability, reusability, maintainability and productivity. Recent approaches for component based development time in HPC context, however, have not reconciled more expressive ways for parallel programming and efficiency. Unfortunately, this issue increases the software development time and gets worse when user have poor knowledge of architectural details of parallel computers and of requirements of applications. Precious time is lost optimizing parallel code, probably with non-portable results, instead of being applied to the solutions of the problem. This dissertation presents the Hash Programming Environment (HPE), a solution based on the # (reads "Hash") Component Model and on the Hash Framework Architecture. HPE defines a set of component kinds for building, deploying and executing parallel programs targeted at clusters of multiprocessors. The Hash Framework Architecture has three loosely coupled modules: the Front-End, the Back-End and the Core. The main contribution of this work is the implementation of the Back-End and the Core. The main contribution of this work is the implementation of the Back-End, since we have an early version of the Front-End and Core, both developed in Java on top of the Eclipse Platform. The Back-End was implemented as a parallel extension of a Mono, an open source component platform based on CLI (Common Language Interface) standard. Once independently done, we bound all the modules together, using web services technology. For evaluating the proposed Back-End, we have developed a small conceptual test application, composed by # components. / A construção de novas aplicações voltadas à Computação de Alto Desempenho (CAD) têm exigido ferramentas que conciliem um alto poder de abstração e integração de software. Dentre as soluções apresentadas pela comunidade científica estamos particularmente interessados naquelas baseadas em tecnologia de componentes. Os componentes têm sido usados para abordar novos requisitos de aplicações de alto desempenho, entre as quais destacamos: interoperabilidade, reusabilidade, manutenibilidade e produtividade. As abordagens das aplicações atuais baseadas em tecnologia de componentes, no entanto, não conseguem abstrair formas mais gerais de paralelismo de maneira eficiente, tornando ainda o processo de desenvolvimento difícil, principalmente se o usuário for leigo no conhecimento das peculiaridades de arquiteturas de computação paralela. Um tempo precioso, o qual deveria ser utilizado para a solução do problema, é perdido na implementação eficiente do código de paralelização. Diante desse contexto, esta dissertação apresenta o HPE (Hash Programming Environment), uma solução baseada no modelo # de componentes paralelos e na arquitetura Hash. O HPE define um conjunto de espécies de componentes responsáveis pela construção, implantação e execução de programas paralelos sobre clusters de multiprocessadores. A arquitetura Hash é constituída de três módulos distintos: o Front-End, o Back-End e o Core. A contribuição principal deste trabalho reside na implementação de um Back-End, como uma plataforma de componentes paralelos que estende o Mono, plataforma de componentes de código aberto baseado no padrão CLI (Common Language Interface). Feito isso, unimos o back-End às implementações já existentes do Front-End e do Core, ambos em java e sobre a plataforma de desenvolvimento Eclipse, através de serviços web (web service). Ao final, apresentaremos um pequeno teste de conceito, construído por um programa paralelo construído a partir de componentes #, segundo as premissas e conceitos apresentados neste trabalho.

CESAR, Ricardo Lenz. Geração de malhas por refinamento adptativo usando GPU. 2009. 100 f. Dissertação (Mestrado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2009. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-07-12T16:29:15Z No. of bitstreams: 1 2009_dis_rlcesar.pdf: 14357749 bytes, checksum: 7bad74a149a075f4d9479d6efb083e77 (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2016-07-21T16:11:41Z (GMT) No. of bitstreams: 1 2009_dis_rlcesar.pdf: 14357749 bytes, checksum: 7bad74a149a075f4d9479d6efb083e77 (MD5) / Made available in DSpace on 2016-07-21T16:11:41Z (GMT). No. of bitstreams: 1 2009_dis_rlcesar.pdf: 14357749 bytes, checksum: 7bad74a149a075f4d9479d6efb083e77 (MD5) Previous issue date: 2009 / The high performance of the GPU and the increasing use of its programming mechanisms have stimulated several graphic applications of virtual reality to explore the potential of this device to achieve higher levels of realism. Studies have emerged with a focus on refining the silhouette of geometric meshes, seeking to express better the surface of three-dimensional objects being represented. The type of refining can be applied, for example, a fabric softening raw an avatar by means of an interpolation curve on their surface faces. Basic idea is to make an adaptive mesh discretization of the object and then generate a new silhouette using this discretization. Previous methods are analyzed and improvements are presented which together form the proposed method. The performance obtained is superior due to a better exploitation of parallelism of the GPU, and the proposed technique works well enough with existing mesh without the need to design new models for this. / O alto desempenho da GPU e o crescente uso dos seus mecanismos de programação têm estimulado diversas aplicações gráficas de realidade virtual a explorar melhor o potencial desse dispositivo para alcançar níveis mais altos de realismo. Trabalhos têm surgido com um enfoque no refinamento da silhueta de malhas geométricas, buscando expressar melhor a superfície dos objetos tridimensionais sendo representados. O tipo de refinamento aplicado pode ser, por exemplo, uma suavização da malha bruta de um avatar, por meio da interpolação de uma superfície curva sobre suas faces. A ideia básica é fazer uma discretização adaptativa da malha do objeto e então gerar uma nova silhueta usando essa discretização. Métodos anteriores são analisados e são apresentadas melhorias que juntas formarão o método proposto. O desempenho obtido é superior devido a uma exploração melhor do paralelismo da GPU, e a técnica proposta funciona suficientemente bem com malhas existentes sem necessidade de se projetar novos modelos para isso.

ALMEIDA, Rodrigo Félix de. BenchXtend: uma ferramenta para medir a elasticidade de sistemas de banco de dados em nuvem. 2013. 87 f. Dissertação (Mestrado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2013. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-07-12T16:54:55Z No. of bitstreams: 1 2013_dis_rfalmeida.pdf: 2089098 bytes, checksum: 5261a9b1bad7546693a182bbdc551ea5 (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2016-07-21T16:12:56Z (GMT) No. of bitstreams: 1 2013_dis_rfalmeida.pdf: 2089098 bytes, checksum: 5261a9b1bad7546693a182bbdc551ea5 (MD5) / Made available in DSpace on 2016-07-21T16:12:56Z (GMT). No. of bitstreams: 1 2013_dis_rfalmeida.pdf: 2089098 bytes, checksum: 5261a9b1bad7546693a182bbdc551ea5 (MD5) Previous issue date: 2013 / Nos últimos anos, a computação em nuvem tem atraído a atenção tanto da indústria quanto do meio acadêmico, tornando-se comum encontrar na literatura relatos de adoção de computação em nuvem por parte de empresas e instituições acadêmicas. Uma vez que a maioria das aplicações em nuvem são orientadas a dados, sistemas de gerenciamento de bancos de dados são componentes críticos das aplicações. Novos sistemas de bancos de dados surgiram para atender a novos requisitos de aplicações altamente escaláveis em nuvem. Esses sistemas possuem diferenças marcantes quando comparados com sistemas relacionais tradicionais. Além disso, uma vez que elasticidade é um recurso chave da computação em nuvem e um diferencial desse paradigma, esses novos sistemas de bancos de dados também devem prover elasticidade. Juntamente com o surgimento desses novos sistemas, surge também a necessidade de avaliá-los. Ferramentas tradicionais de benchmark para bancos de dados não são suficientes para analisar as especificidades desses sistemas em nuvem. Assim, novas ferramentas de benchmark são necessárias para avaliar adequadamente esses sistemas em nuvem e como medir o quão elásticos eles são. Antes de avaliar e calcular a elasticidade desses sistemas, se faz necessária a definição de um modelo com métricas de elasticidade que façam sentido tanto para consumidores quanto provedores. Nesse trabalho apresentamos BenchXtend, uma ferramenta, que estende o Yahoo! Cloud Serving Benchmark (YCSB), para benchmarking e medição de elasticidade de bancos de dados em nuvem. Como parte desse trabalho, propomos um modelo com métricas a partir das perspectivas dos consumidores e dos provedores para medir a elasticidade. Por fim, avaliamos nossa solução através de experimentos e verificamos que nossa ferramenta foi capaz de variar a carga de trabalho, como esperado, e que nossas métricas conseguiram capturar a variação de elasticidade nos cenários analisados. / In recent years, cloud computing has attracted attention from industry and academic world, becoming increasingly common to find cases of cloud adoption by companies and research institutions in the literature. Since the majority of cloud applications are data-driven, database management systems powering these applications are critical components in the application stack. Many novel database systems have emerged to fulfill new requirements of high-scalable cloud applications. Those systems have remarkable differences when compared to traditional relational databases. Moreover, since elasticity is a key feature in cloud computing and it is a differential of this computing paradigm, novel database systems must also provide elasticity. Altogether with the emergence of these new systems, the need of evaluating them comes up. Traditional benchmark tools for database systems are not sufficient to analyze some specificities of these systems in a cloud. Thus, new benchmark tools are required to properly evaluate such cloud systems and also to measure how elastic they are. Before actually benchmarking and measuring elasticity of cloud database systems, it becomes necessary to define a model with elasticity metrics that makes sense both for consumers and providers. In this work we present BenchXtend, a tool, that extends Yahoo! Cloud Serving Benchmark (YCSB), to benchmark cloud database systems and to measure elasticity of such systems. As part of this work, we propose a model with metrics from consumer and provider perspectives to measure elasticity. Finally, we evaluated our solution by performing experiments and we verified that our tool could properly vary the load during execution, as expected, and that our elasticity model could capture the elasticity differences between the studied scenarios.

THIAGO, Vinicius da Silva. Arquitetura multi-agentes para detecção de intrusão distribuida. 2012. 101 f. Dissertação (Mestrado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2012. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-07-12T18:46:20Z No. of bitstreams: 1 2012_dis_vsthiago.pdf: 6549625 bytes, checksum: 57aa3af5bfc03f007d9bea048190cfb7 (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2016-07-22T12:47:27Z (GMT) No. of bitstreams: 1 2012_dis_vsthiago.pdf: 6549625 bytes, checksum: 57aa3af5bfc03f007d9bea048190cfb7 (MD5) / Made available in DSpace on 2016-07-22T12:47:27Z (GMT). No. of bitstreams: 1 2012_dis_vsthiago.pdf: 6549625 bytes, checksum: 57aa3af5bfc03f007d9bea048190cfb7 (MD5) Previous issue date: 2012 / The growing concern about information security in computer networks is responsible for constantly producing new ways to defend them. Within this context, the development of new ways of intrusion detection plays an important role in protecting the information. Detection systems must be efficient and, at the same time, must not overload the network or the processing capabilities of the nodes within it. In order to be effective, a system must base its decisions on as many sources of information as possible and organize knowledge in a way that allows a functional communication between those sources. This dissertation describes the proposal for a Distributed Intrusion Detection System architecture that uses mobile agents and an ontology for information sharing. Mobile agents provide a convenient way to distribute the detection process, enabling peer to peer cooperation between network nodes without generating much additional traffic. The ontology provides an organized way of storing and sharing knowledge. The proposed architecture has been implemented using the Java programming language and JADE framework and a test laboratory has been assembled to verify the operation of the system. The tests results confirmed that a distributed multi-agent architecture that uses an ontology can be effective in detecting attacks on networks and systems. / A crescente preocupação com a segurança da informação em redes de computadores é responsável por produzir constantemente novas formas de defender as mesmas. Dentro desse contexto, o desenvolvimento de novas formas de detecção de intrusão assume um papel muito importante na proteção das informações. Os sistemas de detecção de intrusão precisam ser eficientes e ao mesmo tempo não devem sobrecarregar a rede ou a capacidade de processamento dos nós que a compõem. Com o objetivo de ser eficiente, um sistema deve basear as suas decisões em tantas fontes de informação quanto forem possíveis e organizar o conhecimento de forma que permita uma comunicação funcional entre essas fontes. Este trabalho descreve a proposta de uma arquitetura de um Sistema de Detecção de Intrusão Distribuído que utiliza agentes móveis e uma ontologia para o compartilhamento da informação. Os agentes móveis proporcionam uma maneira prática de distribuir o processo de detecção, possibilitando cooperação ponto a ponto entre os nós da rede sem gerar muito tráfego adicional. A ontologia fornece uma maneira organizada de armazenar e compartilhar o conhecimento. A arquitetura proposta foi implementada utilizando a linguagem de programação Java e o framework JADE e foi montado um laboratório de testes para verificar o funcionamento do sistema. Os resultados obtidos com os testes confirmaram que uma arquitetura distribuída multi-agentes que faz uso de uma ontologia pode ser eficiente na detecção de ataques a redes e sistemas.

Submitted by Reginaldo Soares de Freitas (reginaldo.freitas@ufv.br) on 2016-04-27T09:48:38Z No. of bitstreams: 1 texto completo.pdf: 1187966 bytes, checksum: 9ba7c5ee8c3eafbfbcf97aa8cf96eae5 (MD5) / Made available in DSpace on 2016-04-27T09:48:38Z (GMT). No. of bitstreams: 1 texto completo.pdf: 1187966 bytes, checksum: 9ba7c5ee8c3eafbfbcf97aa8cf96eae5 (MD5) Previous issue date: 2015-12-10 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Este trabalho aborda o problema de sequenciamento de tarefas em máquinas parale- las não-relacionadas considerando restrições de precedência entre as tarefas e tempos de preparação dependentes da sequência e da máquina. Este problema tem como objetivo minimizar o tempo máximo de conclusão do sequenciamento, conhecido como makespan. Em problemas que consideram restrições de precedência, nenhuma tarefa pode iniciar seu processamento sem que todas as suas tarefas predecessoras tenham sido concluídas. Para resolver este problema foram desenvolvidos três mo- delos de programação linear inteira mista (PLIM), denotados por Modelo 1, Modelo 2 e Modelo 3. Em seguida, sete heurísticas construtivas foram desenvolvidas, deno- tadas por HC1 a HC7, as quais se diferenciam pelas regras de prioridade utilizadas. Neste trabalho também é implementado o método chamado Proximity Search (PS), que tenta determinar soluções ótimas para o problema. O método PS precisa de uma solução inicial e de um modelo base de PLIM. Neste método a função objetivo do modelo é substituída por uma função de proximidade e o conjunto de soluções viáveis é reduzido através da adição de cortes. A ideia é, iterativamente, resolver o modelo com a tentativa de melhorar a solução corrente. Foram desenvolvidas três versões do PS denotadas por P S1, P S2 e P S2RIN S . Neste trabalho também foram desenvolvidos algoritmos baseados em meta-heurísticas a fim de resolver o problema de forma aproximada. Primeiramente, foram desenvolvidas duas buscas locais denotadas por BL1 e BL2 baseadas na estratégia de inserção por vizinhança. Em seguida, foram implementadas duas meta-heurísticas: GRASP (Greedy Ran- domized Adaptive Search) e IG (Iterated Greedy). Experimentos computacionais e análises estatísticas foram realizados a fim de comparar o desempenho dos modelos, das versões do P S e das heurísticas propostas. De acordo com os experimentos, o Modelo 1 apresentou-se mais eficiente na qualidade das soluções obtidas e a heurís- tica HC7 mostrou-se mais eficiente na geração de uma solução razoavelmente boa. Além disso, as versões do PS obtiveram melhorias na qualidade da solução obtida e redução no tempo computacional gasto se comparado ao Modelo 1. Em seguida, o IG obteve desempenho significativamente melhor que o GRASP e o PS em relação à qualidade da solução final e a velocidade com que a solução corrente é melhorada. / In this work we address the scheduling problem in unrelated parallel machine with precedence constraints between the jobs and sequence-dependent and machine- dependent setup times. The objective of this problem is to minimize the maximum completion time of sequence, called makespan. The precedence constraints force a job not to be started before all its predecessors are finished. To solve this problem, we developed three models of mixed integer programming (MIP), denoted by Model 1, Model 2 and Model 3. Next, seven constructive heuristics were developed, deno- ted by HC1 to HC7, which differ in the priority rules. Also in this work, a method called Proximity Search (PS) is implemented, which tries to find optimal solutions to the problem. The method requires an initial solution and a MILP-based model. In this method, the objective function of the model is replaced by a proximity func- tion and the set of feasible solutions is reduced by the addition of cuts. The idea is to iteratively solve the model trying to improve the current solution. We deve- loped three versions of the P S denoted by P S1, P S2 and P S2RIN S . In addition, we developed algorithms based on metaheuristics to solve the problem approxima- tely. First, were developed two local searches denoted by BL1 and BL2 based on the insertion neighborhood. Next, were implemented two metaheuristics: GRASP (Greedy Randomized Adaptive Search) and IG (Iterated Greedy). Computational experiments and statistical analyzes were performed in order to compare the per- formance of models, PS versions and heuristics. According to the experiments, the Model 1 is more efficient in the quality of solutions and the HC7 heuristic is more efficient in generating a reasonably good solution. In addition, the versions of the PS obtained improvements in the quality of the obtained solution and reduction in computational time spent compared to Model 1. Then, the IG obtained significantly better performance than the GRASP and PS in relation to the quality of the final solution and the speed with which the current solution is improved.

Submitted by Marco Antônio de Ramos Chagas (mchagas@ufv.br) on 2016-09-13T12:57:14Z No. of bitstreams: 1 texto completo.pdf: 716367 bytes, checksum: 3555ebb07d86905dcc01ee33b9bc59f9 (MD5) / Made available in DSpace on 2016-09-13T12:57:14Z (GMT). No. of bitstreams: 1 texto completo.pdf: 716367 bytes, checksum: 3555ebb07d86905dcc01ee33b9bc59f9 (MD5) Previous issue date: 2016-02-26 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / A cada dia mais dados são gerados das mais diversas fontes. A extração de conheci- mento das bases de dados torna-se cada vez mais desafiadora, visto que os processos utilizados não são triviais. O agrupamento de dados usa técnicas que são capa- zes de trabalhar com dados pouco conhecidos de forma não supervisionada. Essas técnicas dividem os dados em grupos tentando capturar a estrutura presente nos dados para obter um conhecimento que servirá de ponto inicial para seu estudo. Poucos algoritmos de agrupamentos conseguem trabalhar em um contexto escalá- vel. Um dos algoritmos mais influentes no agrupamento é o k -médias, que possui complexidade linear e duas fases bem distintas, facilmente adaptada para modelos escaláveis. Porém, k -médias possui limitações, como sensibilidade à inicialização e especificação do número de grupos k, que geralmente é desconhecido. O obje- tivo desta pesquisa é estudar e desenvolver algoritmos de agrupamento para este contexto escalável. Especificamente, procura-se trabalhar com meta-heurísticas que proporcionem o agrupamento escalável sem a necessidade de especificação do nú- mero de grupos k. Essa dissertação propõe dois novos algoritmos de agrupamento que encontram um valor para k automaticamente em um modelo escalável chamado MapReduce. Adicionalmente, foi estudado um algoritmo com o mesmo propósito encontrado na literatura. Todos os algoritmos foram desenvolvidos e comparados de duas maneiras: pela sua complexidade assintótica e através de experimentos em bases artificiais e reais. Com base em testes estatísticos, foi possível verificar as principais diferenças entre a performance dos algoritmos. / Everyday more data are generated from several sources. The knowledge extraction from datasets becomes more and more challenging as the applied techniques are not trivial. Data clustering techniques are able to work with little knowledge about the data in a totally unsupervised manner. These techniques divide data into clusters trying to capture the structure of the data to obtain knowledge that will serve as a starting point for further studies. Few clustering algorithms are able to work in a scalable scenario. One of the most influential clustering algorithms is k -means, which has linear asymptotic complexity and two distinct phases, which can be easily adapted for scalable models. However, k -means has limitations such as sensitivity to initialization and previous specification of the numbers of clusters k, which is generally unknown, specially for real world scenarios. The objective of this rese- arch is to study and develop scalable clustering algorithms. Specifically, the use of meta-heuristics for scalable clustering to automatically determine the number of k clusters. This dissertation proposes two new clustering algorithms that are able to automatically find the value k in a scalable programing model called MapRe- duce. Additionally, an state-of-art algorithm from the literature has been studied and compared. All algorithms were developed and compared in two ways: based on their asymptotic complexity and through experiments in artificial and real datasets. Based on statistical tests, is was possible to find the main differences among quality and performance of all compared algorithms.

ARAÚJO NETO, Antônio Cavalcante. G2P-DBSCAN: Estratégia de Particionamento de Dados e de Processamento Distribuído fazer DBSCAN com MapReduce. 2016. 63 f. Dissertação (mestrado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2016. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-03-22T19:21:02Z No. of bitstreams: 1 2016_dis_acaraujoneto.pdf: 5671232 bytes, checksum: ce91a85d087f63206ad938133c163560 (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2016-04-25T12:33:12Z (GMT) No. of bitstreams: 1 2016_dis_acaraujoneto.pdf: 5671232 bytes, checksum: ce91a85d087f63206ad938133c163560 (MD5) / Made available in DSpace on 2016-04-25T12:33:12Z (GMT). No. of bitstreams: 1 2016_dis_acaraujoneto.pdf: 5671232 bytes, checksum: ce91a85d087f63206ad938133c163560 (MD5) Previous issue date: 2016 / Clustering is a data mining technique that brings together elements of a data set such so that the elements of a same group are more similar to each other than to those from other groups. This thesis studied the problem of processing the clustering based on density DBSCAN algorithm distributedly through the MapReduce paradigm. In the distributed processing it is important that the partitions are processed have approximately the same size, provided that the total of the processing time is limited by the time the node with a larger amount of data leads to complete the computation of data assigned to it. For this reason we also propose a data set partitioning strategy called G2P, which aims to distribute the data set in a balanced manner between partitions and takes into account the characteristics of DBSCAN algorithm. More Specifically, the G2P strategy uses grid and graph structures to assist in the division of space low density regions. Distributed DBSCAN the algorithm is done processing MapReduce two stages and an intermediate phase that identifies groupings that can were divided into more than one partition, called candidates from merging. The first MapReduce phase applies the algorithm DSBCAN the partitions individually. The second and checks correcting, if necessary, merge candidate clusters. Experiments using data sets demonstrate that true G2P-DBSCAN strategy overcomes the baseline adopted in all the scenarios, both at runtime and quality of obtained partitions. / Clusterizaçao é uma técnica de mineração de dados que agrupa elementos de um conjunto de dados de forma que os elementos que pertencem ao mesmo grupo são mais semelhantes entre si que entre elementos de outros grupos. Nesta dissertação nós estudamos o problema de processar o algoritmo de clusterização baseado em densidade DBSCAN de maneira distribuída através do paradigma MapReduce. Em processamentos distribuídos é importante que as partições de dados a serem processadas tenham tamanhos proximadamente iguais, uma vez que o tempo total de processamento é delimitado pelo tempo que o nó com uma maior quantidade de dados leva para finalizar a computação dos dados a ele atribuídos. Por essa razão nós também propomos uma estratégia de particionamento de dados, chamada G2P, que busca distribuir o conjunto de dados de forma balanceada entre as partições e que leva em consideração as características do algoritmo DBSCAN. Mais especificamente, a estratégia G2P usa estruturas de grade e grafo para auxiliar na divisão do espaço em regiões de baixa densidade. Já o processamento distribuído do algoritmo DBSCAN se dá por meio de duas fases de processamento MapReduce e uma fase intermediária que identifica clusters que podem ter sido divididos em mais de uma partição, chamados de candidatos à junção. A primeira fase de MapReduce aplica o algoritmo DSBCAN nas partições de dados individualmente, e a segunda verifica e corrige, caso necessário, os clusters candidatos à junção. Experimentos utilizando dados reais mostram que a estratégia G2P-DBSCAN se comporta melhor que a solução utilizada para comparação em todos os cenários considerados, tanto em tempo de execução quanto em qualidade das partições obtidas.

PINHEIRO, Ângela Maria Alves. OntologyManagementTool - uma ferramenta para gerenciamento de ontologias como teorias lógicas. 2013. 76 f. : Dissertação (mestrado) - Universidade Federal do Ceará, Centro de Ciências, Departamento de Computação, Fortaleza-CE, 2013. / Submitted by guaracy araujo (guaraa3355@gmail.com) on 2016-05-30T18:23:33Z No. of bitstreams: 1 2013_dis_amapinheiro.pdf: 2709642 bytes, checksum: f720a93925601ca802e5474df0a4501c (MD5) / Approved for entry into archive by guaracy araujo (guaraa3355@gmail.com) on 2016-05-30T18:24:26Z (GMT) No. of bitstreams: 1 2013_dis_amapinheiro.pdf: 2709642 bytes, checksum: f720a93925601ca802e5474df0a4501c (MD5) / Made available in DSpace on 2016-05-30T18:24:26Z (GMT). No. of bitstreams: 1 2013_dis_amapinheiro.pdf: 2709642 bytes, checksum: f720a93925601ca802e5474df0a4501c (MD5) Previous issue date: 2013 / Diversos projetos nacionais e internacionais, como o dados.gov.br e o Linking Open Data, foram desenvolvidos com a finalidade de fomentar a criação da Web de dados, que surge como uma nova abordagem para efetivamente publicar, recuperar e descrever dados distribuídos na Web. Diante desse cenário, tais projetos enfrentam o desafio de criar e manter os dados estruturados que seguem os princípios do Linked Data, descritos no modelo de dados RDF e representados por ontologias. Esse desafio envolve outras tarefas complexas, tais como: reusar o vocabulário das ontologias largamente utilizadas na elaboração de novas ontologias (com a finalidade de promover a interoperabilidade e a integração entre as aplicações) e permitir a detecção de inconsistências entre os termos de uma determinada ontologia. Com o objetivo de propor uma solução para esse desafio, o problema de gerenciamento de ontologias foi abordado nesta dissertação. Na literatura, existe uma grande variedade de trabalhos disponíveis com diferentes enfoques e processos que propõem o gerenciamento de ontologias. Entretanto, poucos trabalhos preocupam-se em auxiliar o especialista do domínio na elaboração de uma ontologia que representa um entendimento correto sobre a semântica das ontologias envolvidas, visto que, para isso faz-se necessário considerar as restrições lógicas das ontologias originais e propagá-las para as novas ontologias. Além disso, foi percebido que, nos trabalhos anteriores, existe a necessidade de utilizar várias ferramentas durante o processo de gerenciamento de ontologias, o que aumenta o esforço manual a ser despendido pelo especialista do domínio na elaboração de novas ontologias. Sendo assim, a fim de oferecer algumas funcionalidades diferenciadas e de modo integrado ao gerenciamento de ontologias, foi desenvolvido um protótipo, denominado OntologyManagementTool. O protótipo desenvolvido considera as ontologias não apenas como vocabulário, mas como teorias lógicas, isto é, leva em conta também o seu conjunto de restrições. Cada ontologia manipulada é primeiramente normalizada para atender ao formalismo da Lógica Descritiva, com um número específico de restrições. Posteriormente, essa ontologia é transformada em um grafo de restrições, e assim, é possível gerenciá-la a partir de um conjunto de operações algébricas sobre o grafo. Destacam-se as seguintes operações: união, interseção, diferença eprojeção. Após a execução de cada uma dessas operações, é possível obter uma nova ontologia, bem como, o mapeamento entre as ontologias envolvidas. O trabalho proposto teve a sua aplicabilidade comprovada a partir de experimentos executados em ontologias descrevendo fontes de dados reais. Os resultados obtidos mostraram que a complexidade para gerar o grafo de restrições é linear em relação ao número de restrições das ontologias; já a complexidade do processamento das operações algébricas (interseção, diferença e projeção) é quadrática em relação ao número de vértices do grafo de restrições, sendo importante evidenciar que o fator determinante para obtenção dessa complexidade é o procedimento escolhido para lidar com as restrições de inclusão, denominado fecho transitivo.