O problema de particionamento balanceado de grafos consiste em encontrar uma partição de tamanho k dos vértices de um grafo, minimizando o número de arestas que participam do corte tal que o tamanho de nenhuma parte exceda [en~k], para algum e e > [1, k). Essa dissertação estuda esse problema, apresentando uma revisão recente de heurísticas construtivas, heurísticas de refinamento e técnicas multinível. Também propomos um novo algoritmo híbrido para resolver esse problema de particionamento. Nós mostramos como diversas estratégias para construir e aprimorar partições, assim como algumas novas propostas, podem ser integradas para formar um GRASP com path-relinking. Reportamos experimentos computacionais que mostram que essa abordagem obtém soluções competitivas com particionadores no estado-da-arte. Em particular, o algoritmo híbrido é capaz de encontrar novos melhores valores conhecidos em algumas das menores instâncias, indicando que tem uma contribuição qualitativa comparado aos métodos existentes. / The balanced graph partitioning problem asks to find a k-partition of the vertex set of an undirected graph, which minimizes the total cut size and such that the size of no part exceeds en/k , for some ee > [1, k]. This dissertation studies this problem, providing a recent review of constructive heuristics, refinement heuristics and multilevel techniques. We also propose a new hybrid algorithm for solving this partitioning problem. We show how several good existing strategies for constructing and improving partitions, as well as some newly proposed ones, can be integrated to form a GRASP with path-relinking. We report computational experiments that show that this approach obtains solutions competitive with state-of-the-art partitioners. In particular, the hybrid algorithm is able to find new best known values in some of the smaller instances, indicating that it can make a qualitative contribution compared to existing methods.

L'analyse de réseaux (représentés par des graphes) est une composante importante dans la compréhension de systèmes complexes issus de nombreuses disciplines telles que la biologie, la géographie ou la sociologie. Nous nous intéressons dans cette thèse aux décompositions de ces réseaux. Ces décompositions sont utiles pour la compression des données, la détection de communautés ou la visualisation de graphes. Une décomposition possible est un partitionnement hiérarchique des sommets du graphe. Nous traitons de l'évaluation de la qualité de telles structures (leur capacité à bien capturer la topologie du graphe) par le biais de mesures de qualité. Nous discutons ensuite l'utilisation de ces mesures en tant que fonctions objectives à maximiser dans le cadre d'algorithmes de partitionnement. Enfin, nous nous intéressons à la définition de métaphores visuelles efficaces permettant de représenter différentes décompositions de graphes. / Network analysis is an important step in the understanding of complex systems studied in various areas such as biology, geography or sociology. This thesis focuses on the problems related to the decomposition of those networks when they are modeled by graphs. Graph decomposition methods are useful for data compression, community detection or network visualisation. One possible decomposition is a hierarchical partition of the set of vertices. We propose a method to evaluate the quality of such structures using quality measures and algorithms to maximise those measures. We also discuss the design of effective visual metaphors to represent various graph decompositions.

Um novo ciclo de tratamento térmico denominado como têmpera e partição vem sendo desenvolvido em aços com elevados teores de silício, como rota para obtenção de estruturas com frações consideráveis de austenia retida. Essa rota de tratamento m térmico consiste em realizar uma têmpera temperaturas intermediárias entre Ms e Mf, seguido de um reaquecimento com manutenção em patamares isotérmicos por certos intervalos de tempo, objetivando estabilizar a austenita remanescente através da partição do carbono a partir da martensita supersaturada. No presente trabalho, duas ligas de ferros fundidos nodulares convencionais, com diferentes teores de silício e manganês, foram submetidas a ciclos de têmpera e partição. As amostras foram austenitizadas a 900°C por duas horas. Uma das ligas foi temperada em óleo a 160°C e a outra a 170°C por 2 minutos. Imediatamente após a têmpera as amostras foram reaquecidas em temperaturas entre 300 e 450°C por intervalos de tempo que variaram entre 2 e 180 minutos. A caracterização microestrutural foi realizada através de microscopia eletrônica de varredura (MEV) e difração de raios x. A caracterização mecânica foi feita através de ensaios de energia absorvida ao impacto, dureza HRC e ensaios de tração. A caracterização microestrutural evidenciou que os ciclos de têmpera e partição são viáveis na obtenção de frações consideráveis de austenita retida nos ferros fundidos nodulares. A caracterização mecânica evidenciou que foi possível obter boas combinações de energia absorvida ao impacto, resistência à tração e alongamento. Em todas as condições testadas é possível perceber uma janela de processo bem definida caracterizada por valores crescentes das propriedades mecânicas nos primeiros minutos do ciclo de partição e que decrescem após certo intervalo de tempo. O conjunto de propriedades mecânicas obtidas através dessa rota de tratamentos térmicos indica que os ferros fundidos nodulares submetidos ao ciclo de têmpera e partição podem se constituir como alternativa tecnológica para aplicações comerciais nas quais os ferros fundidos nodulares austemperados já são materiais consolidados. / A new heat treatment cycle known as quenching and partitioning has been developed in commercial steel alloys containing silicon as a way to obtain structures with controlled fractions of retained austenite. This heat treatment cycle consists in performing a quenching in temperatures between Ms and Mf, followed by a reheating with isothermal holding by different time intervals. The aim of this cycle is to achieve the austenite stabilization by diffusion of carbon from the supersaturated plates of martensite. In this work, two conventional ductile cast iron alloys, with two different contents of silicon and manganese were heat-treated in quenching and partitioning cycle. The samples were austenitized at 900°C for two hours, followed by quenching in oil at 160° C and 170° C for two minutes. Immediately after quenching, the samples were reheated at temperatures between 300 and 450°C for time intervals between 2 and 180 minutes. The microstructural characterization was performed using electronic microscopy (SEM) and x-ray diffraction. The mechanical characterization was performed using impact tests, hardness and tensile strength tests. The microstructural characterization showed that the cycles of quenching and partitioning are viable to obtain considerable fractions of retained austenite in nodular cast by this heat treatment route. The mechanical characterization showed that it was possible to obtain good combinations of energy absorbed in the impact, tensile strength and elongation. In all tested conditions was possible to perceive a well-defined process window characterized by increasing values of mechanical properties in the first minutes of the partitioning step, and decrease after certain time intervals. The set of mechanical properties obtained by this route of heat treatments indicates that nodular cast iron subjected to tempering and partitioning cycle can be constituted as an alternative technology for commercial applications in which austempered ductile irons are already consolidated materials.

Esta dissertação tem por objetivo apresentar uma abordagem baseada em técnicas de inteligência artificial para automatizar a etapa de particionamento de modelos em simulação distribuída. Essa abordagem utiliza os conceitos da computação evolutiva para o desenvolvimento de um algoritmo genético capaz de otimizar o processo de particionamento e auxiliar a tomada de decisões na tarefa de obtenção dos processos lógicos. Objetiva-se com sua aplicação minimizar o tempo de execução da simulação distribuída, evitando que o pior tempo de execução seja utilizado. Para alcançar esse objetivo, o particionamento apresentado como solução é caracterizado pelo balanceamento de carga e pela baixa latência de comunicação entre processos. Isso é possível porque o algoritmo genético utiliza informações contidas no modelo e na arquitetura de onde a simulação será executada. Esses padrões são utilizados para obter informações sobre a comunicação entre processos, a carga de processamento por centro de serviço e a capacidade de processamento das máquinas / This dissertation presents an approach based on intelligence artificial technics to automatize the model partitioning stage in distributed simulation. This approach makes uses evolutive computing concepts to developed a genetic algorithmic that can optimize the partitioning process and help to take decisions in the task to get the logical process. The propose of this algorithm is reduce to execution time the distributed simulation and to avoid the use of the worst execution time. To reach this target, the partitioning obtained has characteristics such as load balance and the low-communication interprocess. This is possible because the genetic algorithmic uses as input information from the model and the architect where the simulation with be executed. These inputs are used to get information about the interprocess communication, processing load per service center and processing capacity in the machines

A busca por características de dependabilidade em aplicações distribuídas está cada vez maior. Para tanto, técnicas de tolerância a falhas são componentes importantes no processo de desenvolvimento de um software, e requerem a reprodução de cenários espe- cíficos de falhas para possibilitar uma avaliação adequada. Nestes casos, resta ao engenheiro de teste a integração de experimentos da aplicação- alvo com ferramentas auxiliares para emulação de um ambiente fiel para a execução de testes. Entretanto, tais ferramentas auxiliares, designadas injetores de falhas de comuni- cação, muitas vezes não estão disponíveis para a comunidade ou, na melhor das hipóteses, apresentam baixa funcionalidade, seja pela incompatibilidade com sistemas mais atuali- zados, seja pela implementação superficial de funções específicas (protótipos). Outro fator agravante para a realização de avaliações experimentais em aplicações distribuídas está no suporte a falhas distribuídas, ou seja, injetores de falhas de comunica- ção não, obrigatoriamente, estão aptos a reproduzir os comportamentos necessários para emulação de ambientes distribuídos adequados. Desta forma, este trabalho destina-se ao estudo e proposta de uma solução para injeção de falhas em ambientes distribuídos, em especial o particionamento de rede, e deu origem ao injetor de falhas PIE. PIE (Partitioning Injection Environment) é um injetor de falhas de comunicação vol- tado para injeção de particionamentos de rede. Sua arquitetura distribuída permite o con- trole centralizado do ambiente por parte do engenheiro de testes. Com isso, a criação de uma única carga de falhas pode ser facilmente replicada para os demais nodos componen- tes do ambiente experimental. Apesar de adotar um coordenador de experimentos, durante a execução de testes, cada nodo interpreta sua carga de falhas e processa-a localmente, ga- rantindo a baixa intrusividade da ferramenta e evitando a ocorrência de comportamentos inesperados pela aplicação-alvo. Como mecanismo de avaliação desta proposta foram realizados experimentos com diferentes aplicações-alvo, disponibilizadas pelo framework JGroups, com um conjunto de cenários de falha específico para cada aplicação. Desta forma, foi possível comprovar a viabilidade e utilidade do modelo e arquitetura do injetor de falhas PIE levando em consideração sua funcionalidade, intrusividade e corretude dos resultados experimentais. / Communication Fault Injection in Distributed Environments The search for dependability characteristics in distributed applications is increasing quickly. For these, fault tolerance techniques are important components in software de- velopment and requires the emulation of specific scenarios to allow a proper evaluation. In these cases, it remains to the test managers the integration of the target application with extra tools for a faithful emulation environment. However, such tools, named com- munication fault injectors, are not available to the community or, in other cases, presents a very poor functionality, incompatibility with current systems, either by superficial im- plementation of specific functions (prototypes). Another problem for achieving experimental evaluations in distributed applications is the support to distributed faults. Communication fault injectors not necessarily are able to reproduce the behaviors required for proper environment emulation. Thus, this work aims to study and propose a solution for fault injection in distributed environments in particular network partitioning, and led to PIE fault injector. PIE (Partitioning Injection Environment) is a communication fault injector aimed to network partitioning injection. Its distributed architecture allows centralized control by the test manager. Thus, a fault load can be easily replicated to other nodes. Despite adopting a experiment coordinator, each node interprets its fault load and processes it locally during testing, ensuring PIE low intrusiveness and avoiding the occurrence of unexpected behavior by the target application. As an assessment of this work, experiments were done with different target appli- cations, provided by JGroups framework, with a set of specific fault scenarios to each application. Thus, it was able to prove the feasibility and usefulness of the model and architecture of the PIE fault injector considering its functionality, intrusiveness and cor- rectness of the experimental results.

O problema de particionamento balanceado de grafos consiste em encontrar uma partição de tamanho k dos vértices de um grafo, minimizando o número de arestas que participam do corte tal que o tamanho de nenhuma parte exceda [en~k], para algum e e > [1, k). Essa dissertação estuda esse problema, apresentando uma revisão recente de heurísticas construtivas, heurísticas de refinamento e técnicas multinível. Também propomos um novo algoritmo híbrido para resolver esse problema de particionamento. Nós mostramos como diversas estratégias para construir e aprimorar partições, assim como algumas novas propostas, podem ser integradas para formar um GRASP com path-relinking. Reportamos experimentos computacionais que mostram que essa abordagem obtém soluções competitivas com particionadores no estado-da-arte. Em particular, o algoritmo híbrido é capaz de encontrar novos melhores valores conhecidos em algumas das menores instâncias, indicando que tem uma contribuição qualitativa comparado aos métodos existentes. / The balanced graph partitioning problem asks to find a k-partition of the vertex set of an undirected graph, which minimizes the total cut size and such that the size of no part exceeds en/k , for some ee > [1, k]. This dissertation studies this problem, providing a recent review of constructive heuristics, refinement heuristics and multilevel techniques. We also propose a new hybrid algorithm for solving this partitioning problem. We show how several good existing strategies for constructing and improving partitions, as well as some newly proposed ones, can be integrated to form a GRASP with path-relinking. We report computational experiments that show that this approach obtains solutions competitive with state-of-the-art partitioners. In particular, the hybrid algorithm is able to find new best known values in some of the smaller instances, indicating that it can make a qualitative contribution compared to existing methods.

In several types of embedded systems the applications are deployed both as software and as hardware components. For such systems, the partitioning decision is highly important since the implementation in software or hardware heavily influences the system properties. In the industry, it is rather common practice to take deployment decisions in an early stage of the design phase and based on a limited number of aspects. Often such decisions are taken based on hardware and software designers‟ expertise and do not account the requirements of the entire system and the project and business development constraints. This approach leads to several disadvantages such as redesign, interruption, etc. In this scenario, we see the need of approaching the partitioning process from a multiple decision perspective. As a consequence, we start by presenting an analysis of the most important and popular Multiple Criteria Decision Analysis (MCDA) methods and tools. We also identify the key requirements on the partitioning process. Subsequently, we evaluate all of the MCDA methods and tools with respect to the key partitioning requirements. By using the key partitioning requirements the methods and tools that the best suits the partitioning are selected. Finally, we propose two MCDA-based partitioning processes and validate their feasibility thorough an industrial case study.

In 2003 at Eurocomb conference J. Barát and C. Thomassen presented definition and basic results in edge partitioning of graphs. Edge partitioning is basically possibility to cover edges of the graph using connected subgraphs of prescribed size. Graph has edge partitioning property if and only if it can be covered for all prescribed subgraphs sizes. Our work is focused on edge partitioning, in which there are less results known, compared to vertex partitioning. We proof, that edge partitioning is implied by existence of open dominating trail and therefore with edge 4-connectivity. We also define limited version of edge partitioning, spectrum of partitioning and we proof some claims that are true for all graphs. We also explore limited partitioning on some specific classes of graphs.

Several studies were done to illustrate the versatillity of the Abraham model in mathematically describing the various solute-solvent interactions found in a wide range of different chemical and biological systems. The first study focused on using the solvation model to construct mathematical correlations describing the minimum inhibitory concentration of organic compounds for growth inhibition towards the three bacterial strains Porphyromonas gingivalis, Selenomonas artemidis, and Streptococcus sobrinus. The next several studies expand the practicallity of the Abraham model by predicting free energies of partition in chemical systems. The free energy studies expand the use of the Abraham model to other temperatures and properties by developing correlations for the enthalpies of solvation of gaseous solutes of various compounds dissolved in water, 1-octanol, hexane, heptane, hexadecane, cyclohexane, benzene, toluene, carbon tetrachloride, chloroform, methanol, ethanol, 1-butanol, propylene carbonate, dimethyl sulfoxide, 1,2-dichloroethane, N,N-dimethylformamide, tert-butanol, dibutyl ether, ethyl acetate, acetonitrile, and acetone. Also, a generic equation for linear alkanes is created for use when individual datasets are small. The prediction of enthalpies of solvation is furthered by modifying the Abraham model so that experimental data measured at different temperatures can be included into a single correlation expression. The temperature dependence is directly included in the model by separating each coefficient into an enthalpic and entropic component. Specifically, the final study describes the effects of temperature on the sorption coefficients of organic gases onto humic acid. The derived predicted values for each research study show a good correlation with experimental values.

In the present study, the influence of the quenching temperature and partitioning conditions (temperature and time) have been investigated on a 0.6%C-1.2%Mn-1.6%Si-1.75%Cr alloy. Maps of hardness, impact toughness and amount of retained austenite have been developed for three quenching temperatures as a function of partitioning temperature and partitioning time. Results demonstrate that, in this material, the carbon depletion of the martensite and the stabilization of austenite can be achieved significantly faster at high partitioning temperatures, promoting higher retained austenite fractions, lower hardness, and maximizing the energy absorbed in a Charpy V‑Notch test. In addition, the effect of the partitioning time was also analysed, presenting different behaviour at high and low partitioning temperatures. Whereas an increment of time at high partitioning temperatures (>400 ºC) leads to an austenite consumption, at low partitioning temperatures it is effective to retain a higher amount of austenite.  Furthermore, tensile properties are shown to be better than in conventional alloys utilized in industry. Whilst, for example, the AISI 52100 alloy achieves 2 GPa of tensile strength and 1‑2% of fracture deformation, in the present study the notable combination of 2.5 GPa of tensile strength and 5.7 % of fracture deformation was achieved in samples quenched until room temperature. Untempered martensite transformed during final cooling in samples quenched until higher temperatures was shown to be detrimental for tensile properties. A comparison between the Q&P process and the austempering process on this alloy has been carried out. Results reveal that the quenching and partitioning heat treatment is presented as a promising alternative to reach higher hardness (>700 HV) and similar specific wear rates in dry conditions performing a shorter heat treatment.    Finally, a complementary study about the effect of micro-segregation on the Q&P process and an optimization method to minimize the inhomogeneity of the structure by a correct selection of the quenching temperature were established.