RAMOS, André Castro. Complexidade e algoritmos de jogos de blocos. 2014. 51 f. : Dissertação (mestrado) - Universidade Federal do Ceará, Centro de Ciências, Departamento de Computação, Fortaleza-CE, 2014. / Submitted by guaracy araujo (guaraa3355@gmail.com) on 2016-05-27T20:03:26Z No. of bitstreams: 1 2014_dis_acramos.pdf: 3052850 bytes, checksum: 1e69aab4f7c65fe5b1dee291b5fa129d (MD5) / Approved for entry into archive by guaracy araujo (guaraa3355@gmail.com) on 2016-05-27T20:03:57Z (GMT) No. of bitstreams: 1 2014_dis_acramos.pdf: 3052850 bytes, checksum: 1e69aab4f7c65fe5b1dee291b5fa129d (MD5) / Made available in DSpace on 2016-05-27T20:03:57Z (GMT). No. of bitstreams: 1 2014_dis_acramos.pdf: 3052850 bytes, checksum: 1e69aab4f7c65fe5b1dee291b5fa129d (MD5) Previous issue date: 2014 / The electronic game concept refers to reserved entertainment to spare time , but in addition to a billion dollar industry , is also potential source of several research topics , both directed to their respective areas of interest as own gaming industry . In this context, in recent decades, work has been done to deal with this type of product based on for problems to be addressed by the theory of algorithms. In this work we bring complexity results and algorithms related to three games with common characteristics , Bloxorz , On The Edge and Bobbin 3D. / A noção de jogo eletrônico remete a entretenimento reservado às horas vagas, mas, além de uma indústria bilionária, também é origem potencial de diversos temas de pesquisa, tanto voltados a suas respectivas áreas quanto de interesse da própria indústria de jogos. Nesse contexto, nas últimas décadas, foram produzidos trabalhos que lidam com esse tipo de produto como base para problemas a serem tratados pela teoria dos algoritmos. Neste trabalho trazemos resultados de complexidade e algoritmos relacionados a 3 jogos com características em comum, Bloxorz, On The Edge e Bobbin 3D.

Made available in DSpace on 2016-08-29T15:09:36Z (GMT). No. of bitstreams: 1 tese_2643_Dissertação - kenyo.pdf: 1538823 bytes, checksum: 5f5d581d8ef6f3456294c46a2498b203 (MD5) Previous issue date: 2007-09-28 / Algumas Estações de Tratamento de Esgotos já possuem equipamentos e processos que reduzem as emissões de gases odorantes, entretanto, a população circunvizinha a esse tipo de empreendimento ainda pode ser afetada, visto que o sistema olfativo humano é capaz de perceber a presença de odores em concentrações extremamente baixas e em curtos intervalos de tempo. A estimativa da emissão de gases odorantes em ETE pode ser obtida através de modelos matemáticos que envolvem um balanço de massa em cada unidade da ETE, onde equações empíricas simulam os fenômenos físicos, químicos e biológicos (volatilização, stripping, adsorção, absorção, biodegradação e oxidação química) responsáveis pela remoção dos gases odorantes dissolvidos na massa de esgoto. Lopes (2005) adaptou um modelo de emissão para estimar a concentração e as taxas de remoção e emissão de H2S a partir de uma ETE do tipo compacta, composta por digestor anaeróbio de fluxo ascendente (UASB) associado a um biofiltro aerado submerso (BF). Apesar dos bons resultados apresentados pelo modelo de emissão adaptado, foi verificada a necessidade de sua calibração devido ao uso de parâmetros empíricos obtidos a partir de outros trabalhos que utilizaram outros tipos de ETE. O objetivo deste trabalho consiste na calibração do modelo de emissão adaptado e avaliado por Lopes (2005) através do uso da técnica de algoritmo genético (AG), responsável por reestimar alguns parâmetros associados às equações empíricas do modelo. Os resultados obtidos revelaram que os parâmetros associados à transferência global de massa entre a fase líquida e a fase gasosa diminuíram em torno de 25% após a calibração; o parâmetro associado à correção do oxigênio para H2S aumentou em 66.6%; e o parâmetro associado à biodegradação (remoção de H2S na fase líquida do BF) não sofreu alteração significativa após a calibração do modelo. As novas estimativas da concentração de H2S nas unidades estação elevatória (EE), caixa de areia (CA), UASB e BF, aproximaram-se das concentrações medidas por Sá (2004), comparando com as concentrações estimadas antes da calibração do modelo de emissão, em 0.51%, 0.25%, 0.29% e 1.96%, respectivamente. Em relação as taxas de emissão de H2S estimadas após a calibração do modelo de emissão, houve uma redução de 23% na EE, 11.6% na CA, 1.2% no UASB, 10.5% na CDV e 12.6% no BF, comparando com as taxas de emissão estimadas antes da calibração do modelo. / Some wastewater treatment plants already have equipments and processes that reduce emissions of odorant gases, however, the population surrounding this type of plant can still be affected by it, due to the fact that human olfactory system is capable of perceiving the presence of odors in extremely low concentrations and short time interval.. The estimative of the odorant gases emission in WWTP can be obtained through mathematical models which involve a balance of mass in each of the WWTP units, where empirical equations simulate the physical, chemical and biological phenomena (volatilization, stripping, adsorption, absorption, biodegradation and chemical oxidation) responsible for the removal of the odorant gases dissolved in the wastewater mass. Lopes (2005) adapted an emission model in order to estimate concentration, removal and emission rates of H2S from a compact type of WWTP, composed by upward flow anaerobic digester (UASB) associated with a submerged aired biofilter (BF). In spite of the good results showed by adapted emission model, it was detected a need to calibrate it due to the use of empirical parameters obtained from other works that used other types of WWTP. The goal of this work is to calibrate the adapted and evaluated emission model by Lopes (2005) through the use of the genetic algorithm (AG) technique, responsible for reestimate some of the parameters associated with the empirical equations of the model. The results obtained showed that the parameters associated with the overall mass transfer between the gas phase and liquid phase decreased by around 25% after calibration; the parameter associated with the correction of oxygen to H2S increased by 66.6%, and the parameter associated with biodegradation (H2S removal of the liquid phase of BF) suffered no significant changes after the model calibration. The new estimates of the concentration of H2S in pumping station (EE) units, grid chamber (CA), UASB and BF were similar to the ones measured by Sá (2004), comparing to the concentrations estimated before the calibration of the emissions model, 0.51%, 0.25%, 0.29% and 1.96%, respectively. Regarding the estimated emission rates of H2S after the calibration of the emissions model, there was a reduction of 23% in EE, 11.6% in CA, 1.2% in the UASB, 10.5% in the CDV and 12.6% in BF, compared to the estimated emission rates before the calibration of the model.

Este estudo trata da tomada de decisão com dados replicados e inconsistentes, relativos ao universo de Recursos Humanos, em uma instituição financeira nacional. A replicação ocorre por questões técnicas e/ou econômicas, e visa o atendimento de necessidades corporativas e departamentais dessa instituição. Como metodologia de pesquisa, utilizou-se a observação direta das inconsistências e a simulação com base em dados reais que refletissem a replicação com inconsistências. A aplicação de um método multicritério fez-se necessária ante a necessidade de se tornar racional o processo de tomada de decisão, e que se transformou em elemento de motivação deste estudo. O método utilizado foi a Teoria dos Conjuntos Aproximativos (TCA), tendo em vista que nenhuma outra informação havia sobre a ocorrência de tais inconsistências. Um algoritmo foi desenvolvido para indicação das fontes principais de dados e, posteriormente, implementado em um software para agilizar a pesquisa dessas fontes. A aplicação da TCA mostrou-se uma ferramenta útil para a empresa em questão, dentre outras possíveis soluções, com o intuito de dirimir as conseqüências indesejáveis da tomada de decisão com dados replicados e inconsistentes. / This study deals about decision-making with replicated and inconsistent data, relating to the universe of Human Resources, within a domestic/local financial institution. Replication occurs because of technical and/or economic questions, and seeks to meet corporate and departmental requirements of such an institution. As research methodology, direct observation of such inconsistencies was used as well as a simulation based on actual data which would reflect replication with inconsistencies. Application of a multi-criteria method became necessary in view of the need to render the decision-making process rational, and was transformed into an element that stimulated this study. The method used was the Rough Set Theory (RST), inasmuch as there existed no other information on the occurrence of such inconsistencies. An algorithm was developed to indicate the major data sources and was subsequently implemented into a software to facilitate research of such sources. Application of the RST proved to be a useful tool for the company in question, within other possible solutions, for the purpose of preventing any unwanted consequences of decision-making with replicated and inconsistent data. / Dissertação (mestrado) - Programa de Pós-Graduação em Administração e Economia, Faculdades IBMEC, Rio de Janeiro, 2008. / Bibliografia: p. 81-84.

Made available in DSpace on 2014-06-11T19:22:33Z (GMT). No. of bitstreams: 0 Previous issue date: 2009-11-30Bitstream added on 2014-06-13T18:08:29Z : No. of bitstreams: 1 martins_wa_me_ilha.pdf: 616652 bytes, checksum: e8d6346d5cc6774ab31d1538b90cb349 (MD5) / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / Neste trabalho é realizada uma análise teórica, a formulação conceitual e a implementação computacional de um algoritmo de vizinhança variável aplicado ao problema de planejamento a longo prazo de sistemas de transmissão de energia elétrica. O problema de planejamento de sistemas de transmissão é um problema muito complexo de resolver porque o modelo matemático é um problema de programação não linear inteiro misto. Por outro lado, a metaheurística de vizinhança variável é uma técnica de otimização que provou excelente desempenho na resolução de problemas complexos no campo da pesquisa operacional. Assim, neste trabalho é desenvolvido um algoritmo de vizinhança variável para o problema de planejamento de sistemas de transmissão. Um conceito importante na implementação desse algoritmo é a definição de vizinhança em relação a caminhos e a técnica de redução do tamanho da vizinhança. Testes realizados mostraram um excelente desempenho do algoritmo VNS, encontrando as melhores soluções conhecidas e mostradas na literatura especializada / In this work a theoretical analysis is carried through, the conceptual formularization and the computational implementation of an applied algorithm of variable neighborhood to the problem of planning in the long run of systems of transmission of electric energy. The problem of planning of transmission systems is a very complex problem from solve because the mathematical model is a programming problem not linear. On the other hand, the metaheuristic of variable neighborhood is one technique of optimization that proved excellent performance in the resolution of complex problems in the field of the operational research. Thus, in this work is developed an algorithm of variable neighborhood for the problem of planning of transmission systems. An important concept in the implementation of this algorithm is the definition of neighborhood in relation the paths and the technique of reduction of the size of the neighborhood. Tests carried through had shown to an excellent performance of algorithm VNS, finding the best solutions known and shown in specialized literature

CNPq / As redes ad hoc são aquelas em que os próprios nós funcionam como roteadores, clientes e servidores ao mesmo tempo. As redes ad hoc móveis são conhecidas como MANETs (Mobile Ad hoc Network) e as VANETs (Vehicle Ad hoc Network) são um tipo de MANET específica para redes veiculares, onde os nós das redes são os próprios veículos equipados com antenas wireless para que possam trocar informações entre si. Na comunicação entre veículos acontecem problemas que as MANETs não estão habilitadas a solucionar. Neste contexto, enquanto nas redes móveis comuns as pessoas se deslocam em pequenos espaços com seus computadores e normalmente existem pontos fixos que facilitam a comunicação constante, nas VANETs a alta mobilidade dos veículos causa diversos problemas como mudanças rápidas e frequentes na topologia da rede, veículos heterogêneos, nós e caminhos disjuntos, obstáculos e exigência de entrega rápida para os quais as MANETs não foram preparadas. O Dynamic Source Route (DSR) é um protocolo de roteamento MANET reativo, ou seja, só descobre rotas entre um nó de origem e um destino quando necessita enviar dados. Por ser “source route”, o protocolo DSR armazena e utiliza vetores de rota (rotas completas) da origem até o destino, diferente de protocolos hop-by-hop que conhecem apenas o próximo salto. Este trabalho apresenta uma proposta de protocolo de roteamento, baseado no DSR, com o uso de algoritmo genético (AG) para atender as exigências das redes VANET. O DSR foi adotado pelo fato de ser um protocolo “source route” que possibilita utilizar técnicas de algoritmo genético, onde os nós podem ser os genes e as rotas são os cromossomos. O novo protocolo criado é chamado de G-Net e possui uma nova forma de funcionamento, modificando totalmente a etapa de manutenção de rotas do DSR. Ele tem o objetivo de atualizar e otimizar as rotas periodicamente de tal forma que as rotas com menor latência sejam escolhidas para transmissão de dados. O trabalho investiga o comportamento do G-Net com relação a taxa média de entrega de dados e sobrecarga de roteamento em relação ao DSR e o AODV (Ad hoc On-demand Distance Vector). A análise destes protocolos de roteamento foi realizada com o gerador de mobilidade VanetMobiSim, para simulação mais realista de movimentos veiculares em ambiente urbano, além de software de simulação de redes ns-3. Experimentos foram realizados com diferentes números de veículos e os resultados mostram que apesar de aumentar a sobrecarga de roteamento em relação ao DSR, o G-Net continua com a sobrecarga inferior ao AODV e apresenta taxa média de entrega de dados superior aos outros dois protocolos nos cenários analisados. / Ad hoc networks are those the nodes themselves work like routers, clients and servers simultaneously. Mobile ad hoc networks are known as MANETs and VANETs are a specific MANET to vehicle networks that the nodes are vehicles with wireless radios to exchange information. On communication between vehicles happen problems that MANETs are not qualified to solve. Thus, on simple mobile networks the people move in small spaces with their computers and usually have fixed points that facilitate the constant communication. But in VANETs, the high mobility of vehicles causes many problems as rapid and frequent changes in network topology, heterogeneous vehicles, disjoints nodes and links, obstacles and requiring fast delivery that MANETs were not prepared to solve. The DSR is a reactive routing protocol for MANET that only discovers routes when it needs to send data. The DSR is source route, for this it stores and uses route vectors (complete routes) from source to destination, unlike hop-by-hop protocols that know only the next hop. This document proposes a new routing protocol based on DSR, using genetic algorithm to meet the requirements of VANET networks. The DSR was adopted because it is a source route protocol that enables using genetic algorithm techniques, which nodes can be genes and chromosomes are routes. The new protocol is called G-Net and has a new mode of operation, modifying completely the maintaining routes of DSR. The G-Net aims to update and optimize routes periodically so that the routes with lower latency are chosen for data transmission. The dissertation investigates the behavior about average delivery ratio and routing overhead of the G-Net compared to DSR and AODV. The analysis of these routing protocols was performed with the generator mobility VanetMobiSim for more realistic simulation of vehicle movements in an urban environment, as well as network simulation ns-3 software. Experiments were conducted with different number of vehicle and the results show that despite increasing the routing overhead with respect to DSR, G-net continues with lower overhead in relation to AODV and has an average delivery ratio higher than the two other protocols in analyzed scenarios.

Este trabalho propõe a utilização da técnica de computação evolucionária conhecida como algoritmos genéticos (AGs) na predição da estrutura de proteínas para o modelo 2D HP. A metodologia tem como principal proposta a utilização uma função de fitness melhorada, que utiliza o conceito de raio de giração. Operadores genéticos especiais foram desenvolvidos e acrescentados aos comumente usados em AG, além de novas estratégias utilizadas para auxiliar o algoritmo no processo de busca de conformações de proteínas. Estas modificações levaram ao desenvolvimento de um sistema de software com diversos recursos gráficos e apresentação de relatórios dos resultados, denominado GANDALF PRED. Uma certa quantidade de experimentos foi realizada com o objetivo de avaliar a influência parâmetros do AG no resultado obtido. Foram realizados dois conjuntos de testes para avaliar a metodologia proposta. O primeiro utilizou 9 seqüências de resíduos, manualmente definidas, cujos máximos de ligações são conhecidos e comprimento variando de 20 a 85 resíduos. Os resultados obtidos foram comparados com duas outras implementações encontradas na literatura. No segundo, 7 proteínas com características globulares foram escolhidas do PDB e traduzidas para o modelo HP. Seus comprimentos variam de 288 a 842 resíduos. Seus resultados foram apresentados e discutidos, já que nenhuma comparação pôde ser realizada. Para ambos os casos de teste, as conformações encontradas podem ser consideradas bons dobramentos. / This work suggests the use of an evolutionary computation technique known as genetic algorithms (GAs) for predicting protein structures in the 2D HP model. The methodology has the main proposal the use of an enhanced fitness function, which makes use of the radius of gyration concept. Special genetic operators were developed and added to those commonly used in GAs, besides new strategies to aid the algorithm in the search of protein conformations. These changes led to the development of a user-friendly software system, with several graphical resources and result reports, named GANDALF PRED. A certain amount of experiments were done with the objective of evaluating the influence of GA parameters in the result obtained. Two test cases were set to evaluate the proposed methodology. The first used 9 manually defined chains whose maximum number of hydrophobic non-local bonds is known a priori and length varying from 20 to 85 residues. The results were compared to two other implementations available in the literature. In the second, 7 proteins with globular traits were taken from PDB and translated to the HP model. Their lengths vary from 288 to 842 residues. The results were presented and discussed, since no comparison could be done. For both test cases, the conformations found can be considered good folds.

Este trabalho apresenta um novo algoritmo de diagnóstico distribuído em nível de sistema, Distributed Network Reachability (DNR). O algoritmo permite que cada nodo de uma rede particionável de topologia arbitrária determine quais porções da rede estão alcançáveis e inalcançáveis. DNR é o primeiro algoritmo de diagnóstico distribuído que permite a ocorrência de eventos dinâmicos de falha e recuperação de nodos e enlaces, inclusive com partições e healings da rede. O estado diagnosticado de um nodo é ou sem-falha ou inatingível; o estado diagnosticado de um enlace é ou sem-falha ou não-respondendo ou inatingível. O algoritmo consiste de três fases: teste, disseminação e cálculo de alcançabilidade. Durante a fase de testes cada enlace é testado por um de seus nodos adjacentes em intervalos de teste alternados. Após a detecção de um novo evento, o testador inicia a fase de disseminação, na qual a nova informação de diagnóstico é transmitida para os nodos alcançáveis. A cada vez que um novo evento é detectado ou informado, a terceira fase é executada, na qual um algoritmo de conectividade em grafos é empregado para calcular a alcançabilidade da rede. O algoritmo DNR utiliza o número mínimo de testes por enlace por rodada de testes e tem a menor latência possível de diagnóstico, assegurada pela disseminação paralela de eventos. A correção do algoritmo é provada formalmente. Uma prova de correção no arcabouço bounded correctness também foi elaborada, incluindo latência delimitada de diagnóstico, latência delimitada de inicialização e acuidade. Um simulador do algoritmo foi implementado. Experimentos foram executados em diversas topologias incluindo grafos aleatórios (k-vertex connected e Power-Law) bem como grafos regulares (meshes e hipercubos). Extensivos resultados de simulação de eventos dinâmicos de falha e recuperação em nodos e enlaces são apresentados. / This thesis introduces the new Distributed Network Reachability (DNR) algorithm, a distributed system-level diagnosis algorithm that allows every node of a partitionable general topology network to determine which portions of the network are reachable and unreachable. DNR is the first distributed diagnosis algorithm that works in the presence of network partitions and healings caused by dynamic fault and repair events. A node is diagnosed as either working or unreachable and a link is diagnosed either as working or unresponsive or unreachable. The algorithm is formally specified and consists of three phases: test, dissemination, and reachability computation. During the testing phase each link is tested by one of the adjacent nodes at alternating testing intervals. Upon the detection of a new event, the tester starts the dissemination phase, in which the new diagnostic information is received by every reachable node in the network. New events can occur before the dissemination completes. After a new event is detected or informed, a working node runs the third phase, in which a graph connectivity algorithm is employed to compute the network reachability. The algorithm employs the optimal number of tests per link per testing interval and the best possible diagnosis latency, assured by the parallel dissemination of event information. The correctness of the algorithm is proved, including the bounded diagnostic latency, bounded start-up and accuracy. Experimental results obtained from simulation are presented. Simulated topologies include random graphs (k-vertex connected and Power-Law) as well as regular graphs (meshes and hypercubes). Extensive simulation results of dynamic fault and repair events on nodes and links are presented.

ANP / O scheduling operacional de uma rede de distribuição de produtos derivados do petróleo é um problema combinatório complexo, de difícil resolução computacional. Este problema pode ser decomposto em três subproblemas de acordo com os elementos chaves do scheduling: aloca- ção dos recursos, seqüenciamento das atividades, e determinação do tempo para a utilização dos recursos pelas atividades. O presente trabalho apresenta o desenvolvimento de um modelo para a solução do subproblema de seqüenciamento das atividades. O seu principal objetivo é propor uma solução baseada em metaheurística para a geração de ordenações das bateladas de produtos derivados do petróleo, criando um modelo de auxílio à tomada de decisão durante as operações de uma malha dutoviária. Da prática operacional, sabe-se que o seqüenciamento de bateladas tem grande influência no resultado final do scheduling. Além disto, a escolha da me- lhor sequencia é um problema multiobjetivo, dependente dos critérios considerados na escolha (atendimento à demanda ou à produção, ocupação dos dutos, etc.). Neste trabalho realizou-se a implementação de várias técnicas metaheurísticas para a solução do problema de seqüencia- mento. Foram analisados os resultados alcançados com o uso de diferentes funções objetivo na otimização. Os resultados mostraram um bom desempenho das metaheurísticas estudadas no seqüenciamento, o que possibilitou a obtenção de boas soluções em um curto tempo computacional. Estudou-se mais profundamente o modelo baseado em algoritmo genético que permite fornecer um conjunto de soluções que representam diferentes opções de possíveis sequencias a serem escalonadas na rede. Este modelo foi, em seguida, extendido para tratar o caso de múltiplos objetivos. Desenvolve-se então uma abordagem baseada em MOGA (Multiobjective Genetic Algorithm) que apresentou bons resultados além de uma maior diversificação de sequencias quando comparado com a solução com objetivo único. Os modelos propostos foram validados em instâncias reais da rede de dutos brasileira e constituem uma ferramenta de auxílio à tomada de decisão operacional, resultando num uso mais eficiente da malha dutoviária estudada. / The scheduling of activities to distribute oil derivate products through a pipe network is a complex combinatorial problem, that presents a difficult computational solution. This problem can be decomposed on three sub-problems according to the key elements of scheduling: assignment of resources, sequencing of activities, and determination of resource timing utilization by these activities. This work develops an approach to the sequencing sub-problem. The main objective is to develop an approach based on metaheuristic for the order generation of oil derivate products batches. The approach goals is to aid the operational decision making of the schedu- ling problem in a pipeline network. From the operational practice, the batches sequencing has great influence on the final scheduling result. Moreover the best order choice is a multiobjective problem and depends on the considered criteria (fulfillment of demand and production, pipe- line occupation rate, etc.). Some metaheuristic techniques were implemented to the sequencing problem. Results in using different objective functions on sequencing optimization were also analyzed. The metaheuristic showed a good performance in sequencing, which resulted on good solutions in a small computational time. A model based on genetic algorithm was intensively studied and it has provided a set of solutions that means different options of possible sequences to be schedule in the pipeline network. This model was also extended to treat multiple ob- jectives. A model based on MOGA (Multiobjective Genetic Algorithm) was developed and it showed good results and also good batches sequencing diversification. The proposed models were validated for real scenarios in the Brazilian pipeline network and have become a tool to aid the operational decision making, resulting in an improvement of the study of this pipeline network.

Este trabalho propõe a utilização da técnica de computação evolucionária conhecida como algoritmos genéticos (AGs) na predição da estrutura de proteínas para o modelo 2D HP. A metodologia tem como principal proposta a utilização uma função de fitness melhorada, que utiliza o conceito de raio de giração. Operadores genéticos especiais foram desenvolvidos e acrescentados aos comumente usados em AG, além de novas estratégias utilizadas para auxiliar o algoritmo no processo de busca de conformações de proteínas. Estas modificações levaram ao desenvolvimento de um sistema de software com diversos recursos gráficos e apresentação de relatórios dos resultados, denominado GANDALF PRED. Uma certa quantidade de experimentos foi realizada com o objetivo de avaliar a influência parâmetros do AG no resultado obtido. Foram realizados dois conjuntos de testes para avaliar a metodologia proposta. O primeiro utilizou 9 seqüências de resíduos, manualmente definidas, cujos máximos de ligações são conhecidos e comprimento variando de 20 a 85 resíduos. Os resultados obtidos foram comparados com duas outras implementações encontradas na literatura. No segundo, 7 proteínas com características globulares foram escolhidas do PDB e traduzidas para o modelo HP. Seus comprimentos variam de 288 a 842 resíduos. Seus resultados foram apresentados e discutidos, já que nenhuma comparação pôde ser realizada. Para ambos os casos de teste, as conformações encontradas podem ser consideradas bons dobramentos. / This work suggests the use of an evolutionary computation technique known as genetic algorithms (GAs) for predicting protein structures in the 2D HP model. The methodology has the main proposal the use of an enhanced fitness function, which makes use of the radius of gyration concept. Special genetic operators were developed and added to those commonly used in GAs, besides new strategies to aid the algorithm in the search of protein conformations. These changes led to the development of a user-friendly software system, with several graphical resources and result reports, named GANDALF PRED. A certain amount of experiments were done with the objective of evaluating the influence of GA parameters in the result obtained. Two test cases were set to evaluate the proposed methodology. The first used 9 manually defined chains whose maximum number of hydrophobic non-local bonds is known a priori and length varying from 20 to 85 residues. The results were compared to two other implementations available in the literature. In the second, 7 proteins with globular traits were taken from PDB and translated to the HP model. Their lengths vary from 288 to 842 residues. The results were presented and discussed, since no comparison could be done. For both test cases, the conformations found can be considered good folds.

Este trabalho apresenta um novo algoritmo de diagnóstico distribuído em nível de sistema, Distributed Network Reachability (DNR). O algoritmo permite que cada nodo de uma rede particionável de topologia arbitrária determine quais porções da rede estão alcançáveis e inalcançáveis. DNR é o primeiro algoritmo de diagnóstico distribuído que permite a ocorrência de eventos dinâmicos de falha e recuperação de nodos e enlaces, inclusive com partições e healings da rede. O estado diagnosticado de um nodo é ou sem-falha ou inatingível; o estado diagnosticado de um enlace é ou sem-falha ou não-respondendo ou inatingível. O algoritmo consiste de três fases: teste, disseminação e cálculo de alcançabilidade. Durante a fase de testes cada enlace é testado por um de seus nodos adjacentes em intervalos de teste alternados. Após a detecção de um novo evento, o testador inicia a fase de disseminação, na qual a nova informação de diagnóstico é transmitida para os nodos alcançáveis. A cada vez que um novo evento é detectado ou informado, a terceira fase é executada, na qual um algoritmo de conectividade em grafos é empregado para calcular a alcançabilidade da rede. O algoritmo DNR utiliza o número mínimo de testes por enlace por rodada de testes e tem a menor latência possível de diagnóstico, assegurada pela disseminação paralela de eventos. A correção do algoritmo é provada formalmente. Uma prova de correção no arcabouço bounded correctness também foi elaborada, incluindo latência delimitada de diagnóstico, latência delimitada de inicialização e acuidade. Um simulador do algoritmo foi implementado. Experimentos foram executados em diversas topologias incluindo grafos aleatórios (k-vertex connected e Power-Law) bem como grafos regulares (meshes e hipercubos). Extensivos resultados de simulação de eventos dinâmicos de falha e recuperação em nodos e enlaces são apresentados. / This thesis introduces the new Distributed Network Reachability (DNR) algorithm, a distributed system-level diagnosis algorithm that allows every node of a partitionable general topology network to determine which portions of the network are reachable and unreachable. DNR is the first distributed diagnosis algorithm that works in the presence of network partitions and healings caused by dynamic fault and repair events. A node is diagnosed as either working or unreachable and a link is diagnosed either as working or unresponsive or unreachable. The algorithm is formally specified and consists of three phases: test, dissemination, and reachability computation. During the testing phase each link is tested by one of the adjacent nodes at alternating testing intervals. Upon the detection of a new event, the tester starts the dissemination phase, in which the new diagnostic information is received by every reachable node in the network. New events can occur before the dissemination completes. After a new event is detected or informed, a working node runs the third phase, in which a graph connectivity algorithm is employed to compute the network reachability. The algorithm employs the optimal number of tests per link per testing interval and the best possible diagnosis latency, assured by the parallel dissemination of event information. The correctness of the algorithm is proved, including the bounded diagnostic latency, bounded start-up and accuracy. Experimental results obtained from simulation are presented. Simulated topologies include random graphs (k-vertex connected and Power-Law) as well as regular graphs (meshes and hypercubes). Extensive simulation results of dynamic fault and repair events on nodes and links are presented.