Orientadora : Profª. Drª. Maria Teresinha Arns Steiner / Co-orientador : Prof. Dr. Cassius Tadeu Scarpin / Dissertação (mestrado) - Universidade Federal do Paraná, Setor de Tecnologia, Programa de Pós-Graduação em Engenharia de Produção. Defesa: Curitiba, 16/02/2016 / Inclui referências : f. 93-99 / Resumo: A educação e o cuidado na primeira infância vêm sendo tratados, cada vez mais, como assuntos prioritários em âmbito nacional. Isto vem ocorrendo, tanto por parte dos governos Federal, Estadual e Municipal, como pelas organizações da sociedade civil, por um número crescente de profissionais, que veem na Educação Infantil uma verdadeira "ponte" para a formação integral do cidadão. Assim, o objetivo do trabalho consiste em estudar a atual distribuição espacial dos centros públicos de Educação Infantil em Curitiba-PR, e otimizar a localização dessas unidades mediante a abordagem de quatro análises complementares, embora bastante independentes entre si. A primeira é a análise da Localização Atual das instalações, importante para efeitos práticos, pois os desequilíbrios podem ser mostrados em um mapa, juntamente com suas magnitudes. A segunda análise é a análise da Localização Proposta, que envolve a proposta de uma relocalização das unidades de toda a rede. A terceira análise é referente a uma estratégia de Expansão da capacidade das unidades existentes. Recorrendo ao modelo de transportes foi possível a avaliação numérica do número de vagas que deveriam ser abertas em cada unidade a fim de que a demanda fosse suprida. A quarta análise baseia-se numa estratégia de construção ou abertura de novas instalações, em que avalia-se dois modelos - o Problema das p-medianas (PPM) capacitado e o não-capacitado. Exceto para a terceira análise, o modelo básico empregado foi o das p-medianas, que pressupõe que o aluno prefere a escola mais próxima de sua residência. Os modelos foram resolvidos pelo solver CPLEX©. Para a representação dos resultados em mapas, utilizou-se o software ArcGis® 10.1, facilitando a interpretação dos mesmos. Em paralelo aos resultados obtidos pelo modelo exato, criou-se uma estratégia de solução do PPM não-capacitado baseada em Algoritmos Genéticos (AG). Os resultados de validação do AG indicaram que o método proposto neste trabalho apresenta soluções satisfatórias. O algoritmo proposto destaca-se pela qualidade de soluções para instâncias de maior porte (com 3282 vértices), por apresentar gaps consideravelmente inferiores às meta-heurísticas da literatura. Em suma, o estudo demonstrou que, de forma geral, existe a necessidade de planejamento imediato para expansão do ensino público infantil em Curitiba-PR, inclusive para o cumprimento efetivo das metas do Plano Nacional da Educação (PNE). Estima-se que a rede pública supra 30,6% em relação a demanda existente. Considerando as vagas absorvidas pela rede privada igual a 50% sobre a demanda, estima-se que ainda faltem 25.177 vagas a serem criadas. Dessa forma, tendo em vista uma evidente necessidade de grandes investimentos nesse campo, os resultados deste trabalho podem contribuir inclusive, para uma melhor estratégia de investimentos em Centros de Educação Infantil. / Abstract: The education and care in early childhood have been treated increasingly as priority issues at the national level. This has been occurring, both by the Federal, State and Municipal governments, as by civil society, a growing number of professionals see in kindergarten a real "bridge" to the integral formation of citizens. This study aims to study the current spatial distribution of public early childhood education facilities in Curitiba, PR, and optimize the location of these units through four complementary analysis approach, though quite independent of each other. The first is to analyze the Current Location of facilities, important for practical purposes, because the imbalances can be displayed on a map along with their magnitudes. The second analysis is the analysis of location proposal, involving a proposed relocation of the entire network drives. The third analysis refers to a strategy of expansion of capacity of existing units. The fourth analysis is based on a strategy of construction or opening of new facilities, in which we evaluate two models - the capacitated PPM and non-capacitated. Except for the third analysis, the basic model employed was the p-median, which assumes that the student prefers the school nearest their home. The models were created using the modeling language VB.NET© and they were solved by the solver CPLEX©. For the representation of the results, we used the ArcGis® 10.1 software, facilitating their interpretation. In parallel to the results obtained from the exact model, it was created a PPM solution strategy non-capacited based on Genetic Algorithm (GA). The GA validation results indicated that the method proposed in this study presents satisfactory solutions, and the goal of establishing a method of solution to the real problem of assessing the location of early childhood education centers has been reached. In short, the study showed that, in general, immediate planning is required to expand the children's public school in Curitiba-PR, including the effective implementation of the goals of the National Education Plan. Similarly, by looking up the obvious need for major investments in this field, the results of this work could contribute even to a better investment strategy in early childhood education centers.

Este trabalho demonstra a utilização da Otimização Paramétrica através da técnica de Algoritmos Genéticos. O método proposto é testado no modelo de uma estrutura utilizada para o carregamento de granéis sólidos em porões de navios graneleiros. A otimização tem dois objetivos principais: a redução de massa total e a redução das máximas tensões absolutas atuantes no modelo, utilizando restrições de flambagem e de deslocamento. A otimização paramétrica modifica as propriedades da seção transversal de cada elemento que compõe o modelo, baseada em uma lista discreta de perfis disponíveis definida pelo usuário. A otimização inicia com um modelo solucionado através do Método dos Elementos Finitos (MEF), utilizando a formulação de elementos de viga. As variáveis de saída do modelo numérico, entre elas as tensões máximas devido à tração, compressão, flexão e torção são calculadas, bem como os deslocamentos e fatores de flambagem da estrutura. Os dados de saída selecionados para representar este modelo inicial são direcionados para o algoritmo genético. As melhores opções da população inicial são combinadas para criar uma nova geração, utilizando o Algoritmo Genético NSGA-II (Nondominated Sorting Genetic Algorithms). Todo o processo é repetido até que o algoritmo atinja o número máximo de geração proposto pelo usuário. Uma vez que os dois objetivos da otimização são contraditórios (minimização de massa e tensão), uma fronteira de Pareto, também conhecida como curva de eficiência, é encontrada com os resultados obtidos, permitindo que o usuário possa escolher nesta fronteira a opção que mais lhe convêm. Ao final do trabalho, os resultados mostram que a otimização estrutural foi bem sucedida e a comparação com o modelo original ilustra as modificações propostas pelo algoritmo de otimização. / The proposed work is a Parametric Optimization study carried out by means of a Genetic Algorithm and applied to a structural problem. The method is tested over a common type of structure used in equipments that load bulk materials into the ship’s hold. The optimization process has two main objectives: reduce the whole structural mass and reduce the model maximum absolute stresses, using buckling and displacement constrains. The parametric optimization changes the cross section properties of each structural element in the frame model, based on a discrete list of available profiles defined by the user. The optimization starts with an initial configuration, which are solved by Finite Element Method (FEM) using beam elements. Output variables, including the maximum stresses due to traction, compression, bending and torsion are computed, as well as structure displacements and buckling factors. The outputs of this first population are sent back to the Genetic Algorithm. The best results are combined to create a new generation, using the NSGA II (Nondominated Sorting Genetic Algorithms). The entire process repeats until the algorithm achieved the maximum number of generations proposed by the user. Since the two optimization objectives (mass and stress reduction) are contradictory, a described Pareto frontier or a called trade-off curve is found with the results, allowing the user to choose where to place the design over this frontier. At the end of the work, results shows that an optimized structure has been achieved and a comparison to the original design illustrate the modifications proposed by the optimization algorithm.

O presente trabalho abordou a simulação numérica de problemas relacionados a um tópico de grande importância na área médica: o comportamento de tecidos ósseos. Foram utilizadas ferramentas computacionais, fundamentos de Mecânica dos Sólidos e teorias baseadas em estudos e experimentos, para simular o comportamento desses tecidos vivos. Aqui se desenvolveu uma metodologia para criar modelos computacionais de ossos fazendo uso de leituras tomográficas, designando as propriedades em função do valor das densidades. A metodologia foi aplicada juntamente com algoritmos genéticos e o método dos elementos finitos para obter a melhor posição de implantes ortodônticos, visando uma homogeneização da tensão no osso na região de colocação do implante. Também foi possível fazer uma comparação entre modelos utilizados na literatura e o desenvolvido aqui. Em particular, foi demonstrado que o uso de materiais isotrópicos homogêneos e materiais com propriedades variáveis de acordo com a densidade levam a resultados diferentes para a otimização da orientação do implante. Foi criado um modelo computacional de remodelamento ósseo com isotropia transversal, com base no modelo de crescimento ósseo isotrópico de Stanford e utilizando as relações constitutivas dos tecidos ósseos. Foi realizada uma comparação entre os modelos isotrópico e isotrópico transversal na simulação do processo de remodelamento ósseo, sendo possível destacar as principais diferenças entre eles. A seguir foi realizada a aplicação do remodelamento ósseo para a otimização de próteses femorais. Foram construídos modelos computacionais integrando o método dos elementos finitos, um modelo matemático do comportamento adaptativo do material ósseo e o método dos algoritmos genéticos, visando a minimização da perda de massa óssea após a inserção de próteses em um osso hospedeiro. Foram realizadas três otimizações para combinações diferentes de parâmetros de projeto de uma prótese femoral. Na primeira, foi realizada a otimização da geometria e do módulo de Young da prótese. Na segunda, foi otimizado apenas o módulo de Young da prótese. Na terceira, foi proposto um modelo de prótese bimaterial, no qual os módulos de Young e a posição da divisão entre os materiais são os parâmetros de projeto escolhidos. A partir dos resultados obtidos, foi possível fazer comentários e sugestões sobre o material utilizado para construção de próteses femorais, bem como sobre a aplicabilidade da metodologia empregada na simulação de problemas de biomecânica. / The present work is addressed to the numerical simulation of problems related to an important topic in the medical area, namely, bone tissues. Computational methods, solid mechanics and theoretical/experimental studies were used to simulate the behavior of live bone tissues. A methodology was developed to create computational models using tomography data, assigning the mechanical properties from the corresponding densities map. The methodology was applied with genetic algorithms and the finite element method to predict the optimal position of orthodontic implants, aiming the homogenization stress in the bone. It was possible to compare some models found in literature and the one developed here. In particular, it was showed that homogeneous isotropic materials and materials with variable density result in different predictions in the optimization of the implant orientation. A computational scheme for bone remodeling was developed using three material behavior laws: transversally isotropic, isotropic Stanford model and classical constitutive relations for bone tissues. A comparison between the isotropic model and the transversally isotropic in the simulation of the bone remodeling was carried out, and the main differences between them were highlighted. Then the proposed bone remodeling scheme was applied to optimize femoral prosthesis. The computational models integrated the finite element method, a mathematical model to describe the behavior of adaptive bone material, and the genetic algorithm. The optimization aimed reduction of bone absorption after the insertion of a prosthesis in a bone host. Three cases of cemented femoral prosthesis were optimized. In the first case, the Young Modulus and geometry of the prosthesis were selected as design variable. In the second case, only the Young Modulus was used as design variable. In the third case, a bi-material prosthesis was proposed was proposed and optimized. Conclusions about the applicability of the proposed formulation for the simulation of biomechanics problems are drawn.

O presente trabalho tem por objetivo apresentar uma formulação para a otimização estrutural de treliças planas e espaciais submetidas a restrições de tensão e deslocamento, combinando técnicas que consideram o espaço de busca contínuo e discreto. É implementado um algoritmo cuja finalidade é incorporar a simplicidade, eficiência e velocidade dos métodos determinísticos com a capacidade de produzir resultados mais realísticos dos métodos estocásticos. O programa desenvolvido possui módulos de elementos finitos, análise de sensibilidade e otimização. Os problemas são resolvidos em duas etapas: A primeira etapa é baseada em Programação Linear Seqüencial (PLS). Este método de programação matemática necessita que a função objetivo e as restrições sejam sucessivamente linearizadas por expansão em séries de Taylor e a análise de sensibilidade é resolvida utilizando o método analítico. A segunda etapa usa Algoritmos Genéticos (AG) e emprega o método das funções penalizadas, no qual o problema restrito é transformado em irrestrito, associando uma penalidade às restrições violadas. Os resultados encontrados na primeira etapa são utilizados para melhorar a convergência da segunda etapa. Para ilustrar o desempenho do algoritmo proposto são apresentados exemplos numéricos de problemas clássicos comparando-os com outros métodos encontrados na literatura. / The present work has as objective the presentation a formulation for structural optimization of plane or space truss with local stress and displacement constraints, combining techniques that consider the search space continuous and discrete. An algorithm was implemented with the purpose to incorporate the simplicity, efficiency and rapidity of the deterministic methods with the ability to produce more realistic results of stochastic methods. The software developed has modules for finite element, sensitivity analysis and optimization. Problems are solved in two steps: The first is based on Sequential Linear Programming (SLP). This method of mathematical programming requires that the objective function and constraints are successively linearized applying a Taylor series expansion and sensitivity analysis is solved using the analytical method. The second step uses genetic algorithms (GA) and Penalty function methods for transform the constrained problem into an unconstrained problem, associating a penalty if a constraint is violated. The results in the first stage are used to improve the convergence of the second stage. Numerical examples are presented to illustrate the performance of the proposed algorithm comparing with other methods found in literature.

O objetivo do trabalho é estudar a viabilidade de tratar problemas de otimização, considerados intratáveis, através de Algoritmos Genéticos, desenvolvendo critérios para a avaliação qualitativa de um Algoritmo Genético. Dentro deste tema, abordam-se estudos sobre complexidade, classes de problemas, análise e desenvolvimento de algoritmos e Algoritmos Genéticos, este ultimo sendo objeto central do estudo. Como produto do estudo deste tema, é proposto um método de desenvolvimento de Algoritmos Genéticos, utilizando todo o estudo formal de tipos de problemas, desenvolvimento de algoritmos aproximativos e análise da complexidade. O fato de um problema ser teoricamente resolvível por um computador não é suficiente para o problema ser na prática resolvível. Um problema é denominado tratável se no pior caso possui um algoritmo razoavelmente eficiente. E um algoritmo é dito razoavelmente eficiente quando existe um polinômio p tal que para qualquer entrada de tamanho n o algoritmo termina com no máximo p(n) passos [SZW 84]. Já que um polinômio pode ser de ordem bem alta, então um algoritmo de complexidade polinomial pode ser muito ineficiente. Genéticos é que se pode encontrar soluções aproximadas de problemas de grande complexidade computacional mediante um processo de evolução simulada[LAG 96]. Como produto do estudo deste tema, é proposto um método de desenvolvimento de Algoritmos Genéticos com a consciência de qualidade, utilizando todo o estudo formal de tipos de problemas, desenvolvimento de algoritmos aproximativos e análise da complexidade. Uma axiomatização tem o propósito de dar a semântica do algoritmo, ou seja, ela define, formalmente, o funcionamento do algoritmo, mais especificamente das funções e procedimentos do algoritmo. E isto, possibilita ao projetista de algoritmos uma maior segurança no desenvolvimento, porque para provar a correção de um Algoritmo Genético que satisfaça esse modelo só é necessário provar que os procedimentos satisfazem os axiomas. Para ter-se consciência da qualidade de um algoritmo aproximativo, dois fatores são relevantes: a exatidão e a complexidade. Este trabalho levanta os pontos importantes para o estudo da complexidade de um Algoritmo Genético. Infelizmente, são fatores conflitantes, pois quanto maior a exatidão, pior ( mais alta) é a complexidade, e vice-versa. Assim, um estudo da qualidade de um Algoritmo Genético, considerado um algoritmo aproximativo, só estaria completa com a consideração destes dois fatores. Mas, este trabalho proporciona um grande passo em direção do estudo da viabilidade do tratamento de problemas de otimização via Algoritmos Genéticos. / The objective of the work is to study the viability of treating optimization problems, considered intractable, through Genetic Algorithms, developing approaches for the qualitative evaluation of a Genetic Algorithm. Inside this theme, approached areas: complexity, classes of problems, analysis and development of algorithms and Genetic Algorithms, this last one being central object of the study. As product of the study of this theme, a development method of Genetic Algorithms is proposed, using the whole formal study of types of problems, development of approximate algorithms and complexity analysis. The fact that a problem theoretically solvable isn’t enough to mean that it is solvable in pratice. A problem is denominated easy if in the worst case it possesses an algorithm reasonably efficient. And an algorithm is said reasonably efficient when a polynomial p exists such that for any entrance size n the algorithm terminates at maximum of p(n) steps [SZW 84]. Since a polynomial can be of very high order, then an algorithm of polynomial complexity can be very inefficient. The premise of the Genetic Algorithms is that one can find approximate solutions of problems of great computational complexity by means of a process of simulated evolution [LAG 96]. As product of the study of this theme, a method of development of Genetic Algorithms with the quality conscience is proposed, using the whole formal study of types of problems, development of approximate algorithms and complexity analysis. The axiom set has the purpose of giving the semantics of the algorithm, in other words, it defines formally the operation of the algorithm, more specifically of the functions and procedures of the algorithm. And this, facilitates the planner of algorithms a larger safety in the development, because in order to prove the correction of a Genetic Algorithm that satisfies that model it is only necessary to prove that the procedures satisfy the axioms. To have conscience of the quality of an approximate algorithm, two factors are important: the accuracy and the complexity. This work lifts the important points for the study of the complexity of a Genetic Algorithm. Unhappily, they are conflicting factors, because as larger the accuracy, worse (higher) it is the complexity, and vice-versa. Thus, a study of the quality of a Genetic Algorithm, considered an approximate algorithm, would be only complete with the consideration of these two factors. But, this work provides a great step in direction of the study of the viability of the treatment of optimization problems through Genetic Algorithms.

Resumo: O comportamento mecanico dos materiais viscoelasticos (MVEs) e influenciado, entre outros, por parametros como tempo e temperatura. O estudo da influencia destes parametros e objeto frequente de pesquisas que visam buscar uma metodologia mais adequada para determinar seu impacto no comportamento de estruturas construidas com MVEs. Este texto apresenta uma metodologia para a caracterizacao de MVEs termorreologica e piezorreologicamente simples no dominio do tempo a partir de dados experimentais, utilizando as Series de Prony e uma tecnica mista de otimizacao baseada em Algoritmos Geneticos (AG) e Programacao Nao Linear (PNL). O resultado final de caracterizacao e a obtencao das constantes relacionadas a cada termo da Serie de Prony, que foi utilizada na analise por Elementos Finitos (EF) do material viscoelastico (MVE). Alem disso, o texto discute tambem as influencias da pressao e da temperatura sobre o comportamento mecanico desses materiais. Os resultados desta analise sao comparados aos dados experimentais com o intuito de validar a metodologia. Os resultados finais se mostram bastante promissores e a metodologia se apresenta eficiente para identificacao de MVEs.

A área de pesquisa de testes não-destrutivos é muito importante, trabalhando com o diagnóstico e o monitoramento das condições dos componentes estruturais prevenindo falhas catastróficas. O uso de algoritmos genéticos para identificar mudanças na integridade estrutural através de mudanças nas respostas de vibração da estrutura é um método não-destrutivo que vem sendo pesquisado. Isto se deve ao fato de que são vantajosos em achar o mínimo global em situações difíceis de problemas de otimização, particularmente onde existem muitos mínimos locais como no caso de detecção de dano. Neste trabalho é proposto um algoritmo genético para localizar e avaliar os danos em membros estruturais usando o conceito de mudanças nas freqüências naturais da estrutura. Primeiramente foi realizada uma revisão das técnicas de detecção de dano das últimas décadas. A origem, os fundamentos, principais aspectos, principais características, operações e função objetivo dos algoritmos genéticos também são demonstrados. Uma investigação experimental em estruturas de materiais diferentes foi realizada a fim de se obter uma estrutura capaz de validar o método. Finalmente, se avalia o método com quatro exemplos de estruturas com danos simulados experimentalmente e numericamente. Quando comparados com técnicas clássicas de detecção dano, como sensibilidade modal, os algoritmos genéticos se mostraram mais eficientes. Foram obtidos melhores resultados na localização do que na avaliação das intensidades dos danos nos casos de danos propostos.

Este texto apresenta a tese de doutorado em Ciência da Computação na linha de pesquisa de Inteligência Artificial, dentro da área de IAD – Inteligência Artificial Distribuída (mais especificamente os Sistemas Multiagentes – SMA). O trabalho aborda a formação de grupos colaborativos em um ambiente multiagente interativo de aprendizagem na web, através da utilização de técnicas de Inteligência Artificial. O trabalho apresenta a definição e implementação de uma arquitetura de agentes modelados com algoritmos genéticos, integrada a um ambiente colaborativo de aprendizagem, o TelEduc. Inicialmente faz-se um breve estudo sobre as áreas envolvidas na tese: Informática na Educação, Educação a Distância, Inteligência Artificial, Inteligência Artificial Distribuída e Inteligência Artificial Aplicada à Educação. Abordam-se, também, as áreas de pesquisa que abrangem os Sistemas Multiagentes e os Algoritmos Genéticos. Após este estudo, apresenta-se um estudo comparativo entre ambientes de ensino e aprendizagem que utilizam a abordagem de agentes e a arquitetura proposta neste trabalho. Apresenta-se, também, a arquitetura de agentes proposta, integrada ao ambiente TelEduc, descrevendo-se o funcionamento de cada um dos agentes e a plataforma de desenvolvimento. Finalizando o trabalho, apresenta-se o foco principal do mesmo, a formação de grupos colaborativos, através da implementação e validação do agente forma grupo colaborativo. Este agente, implementado através de um algoritmo genético, permite a formação de grupos colaborativos seguindo os critérios estabelecidos pelo professor. A validação do trabalho foi realizada através de um estudo de caso, utilizando o agente implementado na formação de grupos colaborativos em quatro turmas de cursos superiores de Informática, na Região Metropolitana de Porto Alegre, em disciplinas que envolvem o ensino de programação de computadores.

O objetivo do trabalho é estudar a viabilidade de tratar problemas de otimização, considerados intratáveis, através de Algoritmos Genéticos, desenvolvendo critérios para a avaliação qualitativa de um Algoritmo Genético. Dentro deste tema, abordam-se estudos sobre complexidade, classes de problemas, análise e desenvolvimento de algoritmos e Algoritmos Genéticos, este ultimo sendo objeto central do estudo. Como produto do estudo deste tema, é proposto um método de desenvolvimento de Algoritmos Genéticos, utilizando todo o estudo formal de tipos de problemas, desenvolvimento de algoritmos aproximativos e análise da complexidade. O fato de um problema ser teoricamente resolvível por um computador não é suficiente para o problema ser na prática resolvível. Um problema é denominado tratável se no pior caso possui um algoritmo razoavelmente eficiente. E um algoritmo é dito razoavelmente eficiente quando existe um polinômio p tal que para qualquer entrada de tamanho n o algoritmo termina com no máximo p(n) passos [SZW 84]. Já que um polinômio pode ser de ordem bem alta, então um algoritmo de complexidade polinomial pode ser muito ineficiente. Genéticos é que se pode encontrar soluções aproximadas de problemas de grande complexidade computacional mediante um processo de evolução simulada[LAG 96]. Como produto do estudo deste tema, é proposto um método de desenvolvimento de Algoritmos Genéticos com a consciência de qualidade, utilizando todo o estudo formal de tipos de problemas, desenvolvimento de algoritmos aproximativos e análise da complexidade. Uma axiomatização tem o propósito de dar a semântica do algoritmo, ou seja, ela define, formalmente, o funcionamento do algoritmo, mais especificamente das funções e procedimentos do algoritmo. E isto, possibilita ao projetista de algoritmos uma maior segurança no desenvolvimento, porque para provar a correção de um Algoritmo Genético que satisfaça esse modelo só é necessário provar que os procedimentos satisfazem os axiomas. Para ter-se consciência da qualidade de um algoritmo aproximativo, dois fatores são relevantes: a exatidão e a complexidade. Este trabalho levanta os pontos importantes para o estudo da complexidade de um Algoritmo Genético. Infelizmente, são fatores conflitantes, pois quanto maior a exatidão, pior ( mais alta) é a complexidade, e vice-versa. Assim, um estudo da qualidade de um Algoritmo Genético, considerado um algoritmo aproximativo, só estaria completa com a consideração destes dois fatores. Mas, este trabalho proporciona um grande passo em direção do estudo da viabilidade do tratamento de problemas de otimização via Algoritmos Genéticos. / The objective of the work is to study the viability of treating optimization problems, considered intractable, through Genetic Algorithms, developing approaches for the qualitative evaluation of a Genetic Algorithm. Inside this theme, approached areas: complexity, classes of problems, analysis and development of algorithms and Genetic Algorithms, this last one being central object of the study. As product of the study of this theme, a development method of Genetic Algorithms is proposed, using the whole formal study of types of problems, development of approximate algorithms and complexity analysis. The fact that a problem theoretically solvable isn’t enough to mean that it is solvable in pratice. A problem is denominated easy if in the worst case it possesses an algorithm reasonably efficient. And an algorithm is said reasonably efficient when a polynomial p exists such that for any entrance size n the algorithm terminates at maximum of p(n) steps [SZW 84]. Since a polynomial can be of very high order, then an algorithm of polynomial complexity can be very inefficient. The premise of the Genetic Algorithms is that one can find approximate solutions of problems of great computational complexity by means of a process of simulated evolution [LAG 96]. As product of the study of this theme, a method of development of Genetic Algorithms with the quality conscience is proposed, using the whole formal study of types of problems, development of approximate algorithms and complexity analysis. The axiom set has the purpose of giving the semantics of the algorithm, in other words, it defines formally the operation of the algorithm, more specifically of the functions and procedures of the algorithm. And this, facilitates the planner of algorithms a larger safety in the development, because in order to prove the correction of a Genetic Algorithm that satisfies that model it is only necessary to prove that the procedures satisfy the axioms. To have conscience of the quality of an approximate algorithm, two factors are important: the accuracy and the complexity. This work lifts the important points for the study of the complexity of a Genetic Algorithm. Unhappily, they are conflicting factors, because as larger the accuracy, worse (higher) it is the complexity, and vice-versa. Thus, a study of the quality of a Genetic Algorithm, considered an approximate algorithm, would be only complete with the consideration of these two factors. But, this work provides a great step in direction of the study of the viability of the treatment of optimization problems through Genetic Algorithms.

Neste trabalho fazemos revisão de alguns dos principais métodos para análise não-linear de séries temporais originadas a partir de sistemas de baixa dimensionalidade com dinâmica predominantemente determinística, dando ênfase ao problema de classificação/clusterização nãosupervisionada destas mesmas séries. Várias medidas de dissimilaridade são utilizadas em conjunto com métodos heurísticos baseados em algoritmos estocásticos, para a organização de segmentos de séries temporais não estacionárias em grupos com características em comum, na tentativa de associar a estes alguma característica clínica previamente conhecida. O método é implementado com diferentes medidas de dissimilaridade e um experimento feito com séries temporais sintéticas (obtidas a partir de simulação numérica) com fins de validação e posteriormente aplicado a um problema real, o problema de segmentação de estágios de sono. Os resultados indicam certa promissoriedade do método para aplicação na classificação estágios de sono em eletroencefalogramas. / In this work we make a review of some of the main methods available for nonlinear time series analysis for low-dimensional deterministic systems, giving emphasis to the problem of unsupervised classification/clustering of this kind of data. Various dissimilarity measures are used together with heuristic search methods based on stochastic algorithms to organize segments of one (big) nonstationary time series in groups with common characteristics, trying to relate these groups to some known clinical property. The method is implemented with different dissimilarity measures and one experiment made with synthetic (generated by numerical simulations) time series for validation and lately applied to a real problem, the problem of sleep stages segmentation. The results look promising with respect to the applicability of the method to classify sleep stages in electroencephalographic recordings.