Orientador: Secundino Soares Filho / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica / Made available in DSpace on 2018-07-18T13:11:31Z (GMT). No. of bitstreams: 1 Oliveira_GustavoGonzagade_M.pdf: 4858937 bytes, checksum: 1d1d95899c1cb92c5011d66a0dc3f6fc (MD5) Previous issue date: 1993 / Resumo: Este trabalho apresenta um algoritmo determinístico para a etapa de médio prazo do planejamento da operação energética de sistemas hidrotérmicos com representação individualizada das usinas. O problema foi formulado como um fluxo em rede não linear de grande porte com arcos capacitados. A não linearidade e não diferenciabilidade da função de produção das usinas hidroelétricas e do custo da complementação não hidráulica são algumas das características da função objetivo que a torna extremamente complexa. Assim, o planejamento da operação de sistemas hidrotérmicos pode ser classificado como um problema não linear, não diferenciável e de grande porte. A formulação do problema considera alguns aspectos de modelagem importantes como a capacidade do sistema hidráulico atender a demanda de ponta mantendo constante a complementação não hidráulica no decorrer do intervalo. Esta restrição é atendida por uma função de penalização quadrática. Outro aspecto de modelagem normalmente desprezado é o afogamento do canal de fuga de uma usina pelo reservatório da usina diretamente a jusante. Para sistemas com alto nível de afogamento, podem ocorrer mudanças significativas na trajetória ótima dos reservatórios. Todas as particularidades do problema foram exploradas afim de melhorar a eficiência do programa. Foram implementados dois métodos de otimização, o Newton Truncado e o Gradient Reduzido. O Newton Truncado é um método de segunda ordem que calcula a direção iterativamente e possibilita explorar a estrutura tri-diagonal da matriz hessiana do problema. O Gradiente Reduzido foi implementado para avaliar o avanço obtido pelo método de segunda ordem em relação a um de primeira. A estrutura da rede hidráuJica formada pelas equações de balanço de água nos reservatórios é denominada arborescência expandida no tempo. Ela foi explorada através da definição da base pela Matriz de Defluência Básica. A estrutura da árvore formada por esta matriz e os métodos de otimização implementados sugerem a definição de estratégias heurÍsticas de partição de variáveis em básicas, superbásicas e não básicas. Estas estratégias foram baseadas na análise do comportamento ótimo de sistemas sobre diversas condições hidrológicas. Assim, o processo ... Observação: O resumo, na íntegra, poderá ser visualizado no texto completo da tese digital / Abstract: This work presents a nonlinear capacitated network flow algorithm specially designed for mid-term hydrothermal scheduling problem. It has been formulated as a deterministic optimization problem, where each hydro plant is represented individually, and the system operation cost function is defined by a prior optimization of the non-hydraulic sources. The nonlinearity and non-differenciability of the hydro production and operation cost functions characterize the problem as a nonlinear, non-differentiable and large scale one. Some important modeling aspects have been considerated in the problem formulation. The maximal capacity of the hydroelectric power system plus the non-hydraulic power average at each time interval must garantee the peak load requirement. It is formulated by a nonlinear constrain which is attended by a quadratic penalty function. Another unusual modeling aspect is the eventual influence of the forebay elevation of a given plant over the tailrace elevation of its upstream neighbor. The Truncated Newton method has been chosen to calculate second order directions iteratively to expoit the three-diagonal structure of the Hessian matrix. Reduced Gradient method has also been implemented in order to comparatively evaluate with the second order method by comparing to a first order one. The hydro scheduling network structure, so-called temporally expanded arborescence, has been exploit to improve the algorithm's performance. The spanning tree representation makes the algorithm implementation extremely sim pIe and suggests heuristic strategies for variable partition into basic-superbasic-nonbasic sets. These strategies have been based on the system optimal reservoir trajectories obtained by optimal solution analysis of different systems over several inflow conditions. Thus, the variable partition will induce the convergence process straightforward to the optimum, reducing the computation time. This code has been incorporated in a Decision Support System specially developed for the Brazilian Power System ... Note: The complete abstract is available with the full electronic digital thesis or dissertations / Mestrado / Mestre em Engenharia Elétrica

Orientador : Claudio Leonardo Lucchesi / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Ciencia da Computação / Made available in DSpace on 2018-07-18T14:58:51Z (GMT). No. of bitstreams: 1 Andrade_MarcusViniciusAlvim_M.pdf: 3444335 bytes, checksum: 6e52a27f97f6c0f274e3d33dc944bccc (MD5) Previous issue date: 1993 / Resumo: O problema de reconhecimento de padrões surge muito freqüentem ente em diversas áreas e consiste basicamente em determinar se um dado objeto (padrão) ocorre em alguma parte de um outro objeto (geralmente bem maior). Existem diversas variações sobre o tema, por exemplo, objetos com uma ou mais dimensões, reconhecimento aproximado de padrões etc. Neste trabalho abordaremos a questão do reconhecimento de padrões unidimensionais que na literatura normalmente é citado como reconhecimento de padrões em texto. Além disso, nos concentramos no problema de reconhecimento exato de padrões. Nosso objetivo principal é apresentar (descrever e analisar) de forma clara e precisa os principais algoritmos que solucionam o problema em questão. No capítulo 2 descrevemos o algoritmo de Knuth, Morris e Pratt através de autômatos, sendo que vale destacar que, embora a associação entre este algoritmo e autômatos seja citada na literatura com bastante freqüência, normalmente ela não é efetivamente utilizada na descrição do algoritmo. Esta abordagem tornou a descrição do algoritmo bastante simples. Além disso, na análise do algoritmo, a demonstração de alguns resultados foram realizadas de forma bem mais clara do que a originalmente proposta. No capítulo 3 apresentamos o algoritmo de Boyer e Moore que é um algoritmo extremamente eficiente na prática e no qual se baseiam a maioria dos outros algoritmos existentes. Inclusive, nós apresentamos uma variação deste algoritmo que pode ser descrita de forma mais simples do que o algoritmo original e, em alguns casos, é mais eficiente do que ele. Além disso, neste capítulo tratamos da questão da análise de complexidade do algoritmo de Boyer e Moore que é um problema razoavelmente complexo e apresentamos ainda as principais variações deste algoritmo. No apêndice A descrevemos outros algoritmos propostos recentemente que solucionam o problema de reconhecimento de padrões em textos e finalmente, no apêndice B, analisamos teoricamente o comportamento médio de alguns algoritmos e também descrevemos os resultados de algumas análises empíricas realizadas por outros autores. / Abstract: The pattern matching problem arises very frequently in several areas of knowledge and basically consists in determining if a given object (pattern) occurs in any place of another object (usually bigger). There are many variations of this problem, for exam pie, objects with one or more dimensions, approximate pattern matching etc. In this work we approach the pattern matching problem on one dimension that in the literature is normally named the string matching problem. More precisely, we confined ourselves to the exact pattern matching problem. Our main objective is to present (describe and analyse) dearly and precisely the most important algorithms to solve this problem. In chapter 2 we describe the Knuth, Morris and Pratt algorithm through automata. It is worth mentioning that, although the association between this algorithm and automata is cited in the literature quite often, in general, automata are not effectively used in the description of the algorithm. This approach made the description of the algorithm very sim pie. Moreover, in the analysis of the algorithm, the proofs of some of the results were accomplished in a clearer way. In chapter 3 we present the Boyer and Moore algorithm, which is extremelly efficient in practice and the majority of the algorithms found in the literature are based on the ideas of this algorithm. Actually, we present a little variation of this algorithm that is simpler and, in some cases, more efficient than the original algorithm. Moreover, in this chapter, we deal with the complexity analysis of the Boyer and Moore algorithm. We also present several variations of this algorithm. In appendix A we describe other pattern matching algorithms that were recently developed and finally, in the appendix B, we analise theoretically the average behaviourof some algorithms and also describe the results of some empirical analyses made by other authors. / Mestrado / Mestre em Ciência da Computação

Orientador : Claudio Leonardo Lucchesi / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Ciencia da Computação / Made available in DSpace on 2018-07-19T02:33:54Z (GMT). No. of bitstreams: 1 Harada_MarioMassato_M.pdf: 4068868 bytes, checksum: b1c6deba0fdfa1219941651e6678cf3e (MD5) Previous issue date: 1994 / Resumo: Neste trabalho estudaremos alguns algoritmos que fornecem soluções para três variações do problema de casamento aproximado de padrões: k diferenças, k colisões, e padrões com símbolos neutros. Neste último problema não estudaremos um algoritmo específico para solucioná-lo, mas um algoritmo genérico que soluciona os três problemas citados. Nosso objetivo principal é descrever e analisar de forma clara e precisa alguns algoritmos para os três problemas. No Capítulo 2 estudaremos o algoritmo de Ukkonen que servirá de base para alguns algoritmos do Capítulo 3. No Capítulo 3 apresentaremos soluções para o problema das k diferenças. Serão apresentados os algoritmos de Ukkonen, o algoritmo de Galil e Park e o algoritmo de Tarhio e Ukkonen. O algoritmo de Ukkonen é uma modificação do algoritmo original apresentado no Capítulo 2, o algoritmo de Galil e Park é uma melhoria do algoritmo de Ukkonen. Já o algoritmo de Tarhio e Ukkonen utiliza as idéias da programação dinâmica e do pré-processamento do padrão. No Capítulo 4 descreveremos três algoritmos que fornecem soluções para o problema das k colisões: algoritmo de Landau e Vishkin, algoritmo de Baeza-Yates e o algoritmo de Tarhio e Ukkonen. O primeiro utiliza idéias semelhantes às idéias do algoritmo de Knuth, Morris e Pratt, os dois últimos algoritmos usam as idéias de deslocamento do padrão encontradas no algoritmo de Boyer e Moore. Por fim, no Capítulo 5, apresentamos os algoritmos de Baeza- Yates e Gonnet e o algoritmo de Wu e Manber que apresentam algoritmos flexíveis para resolver os três problemas do casamento aproximado de padrões / Abstract: In this work, we study some algorithms that give solutions to the three variations of the problem of approximate string matching: k-differences, k-mismatches, patterns with don't care symbols. In this last problem we will not study a specific algorithm that solves it but we study a generic algorithm that solves the three problems. Our main objective is to describe and analize clearly and precisely some algorithms for the three problems. In Chapter 2 we study the algorithm of Ukkonen that gives a basis for some algorithms in Chapter 3. In Chapter 3 we present solutions to the k-differences problem. It will be presented the algorithm of Ukkonen, the algorithm of Galil and Park and the algorithm of Tarhio and Ukkonen. The algorithm of Ukkonen is a modification of the original one presented in Chapter 2, the algorithm of Galil and Park is an improvement of the algorithm of Ukkonen. The algorithm of Tarhio and Ukkonen uses the ideas from dynamic programming and preprocessing of the pattern.In Chapter 4, we describe three algorithms that solve the k-mismatches problem: algorithm of Landau and Vishkin, algorithm of Baeza and Gonnet and the algorithm of Tarhio and Ukkonen. The first uses the ideas similar to the ideas of the algorithm of Knuth, Morris and Pratt, the last two algorithms use the pattern shift technique introduced in the algorithm of Boyer and Moore. Finally, in Chapter 5, we describe the algorithm of Baeza and Gonnet and the algorithm of Wu and Manber, these algorithms are flexible enough to solve the three problems of approximate string matching / Mestrado / Mestre em Ciência da Computação

Orientador: Lucio Tunes dos Santos / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Científica / Made available in DSpace on 2018-07-19T02:36:37Z (GMT). No. of bitstreams: 1 Castro_SuzanaLimadeCampos_M.pdf: 1382178 bytes, checksum: 716b1bad6fba3a4e8ed12867940ed411 (MD5) Previous issue date: 1994 / Resumo: A subrotina computacional BOX-QUACAN, desenvolvida por Friedlander, Martinez e Santos (1992) para resolver problemas de minimização de funções com restrições de canalização, tem sido muito utilizada por ser robusta e indicada para problemas de grande porte. Os resultados práticos, porém, demonstram que o seu desempenho está intimamente relacionado com o valor dos parâmetros de entrada. Neste trabalho nos propomos a estudar o problema de determinar os parâmetros de entrada que tornem a subrotina o mais eficiente possível, quanto ao tempo computacional e à convergência. Para isto, ele foi modelado como um problema de otimização, através de uma função que associa a cada conjunto de parâmetros o grau de eficiência da subrotina, e devido às suas características, optamos por resolvê-lo através de um Algoritmo Genético (Goldberg (1989)). Os algoritmos genéticos são algoritmos gerais de busca de conjuntos de soluções para problemas de otimização, utilizando em geral, apenas o valor da função objetivo. A principal diferença em relação a outros métodos de busca é que eles analisam e manipulam, simultaneamente, um conjunto de possíveis soluções a cada iteração, de modo a obter pontos cada vez mais próximos do ótimo global. Utilizamos também o método de Nelder - Mead (ver, por exemplo, Himmelblau (1972)), que pertence à classe dos algoritmos de otimização que não necessitam de derivadas e, apesar de não ser global, é adequado às condições da função objetivo do problema. / Abstract: Not informed. / Mestrado / Mestre em Matemática Aplicada

Orientador: Rogerio Drummond Burnier Pessoa de Mello Filho / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Ciencia da Computação / Made available in DSpace on 2018-07-19T11:06:10Z (GMT). No. of bitstreams: 1 Silva_MariaInesValeda_M.pdf: 3521468 bytes, checksum: 2114bcfe1332db2ea52a7d4663b551f0 (MD5) Previous issue date: 1994 / Resumo: Diagramas são largamente utilizados como forma de representação gráfica dos mais diversos tipos de informação. A LegoShell [Dru89] é uma linguagem gráfica, em desenvolvimento no Projeto A_HAND, projetada para representar objetos distribuídos. Nos diagramas LegoShell, tais objetos aparecem conectados entre si na forma de um grafo orientado. A legibilidade de um diagrama LegoShell é uma qualidade muito desejável. Dependendo da complexidade, o desenho de um diagrama LegoS~ell pode ser. bastante confuso. Desse modo, uma função de desenho automático de seus diagramas pode ser necessária, para garantir a clareza de sua informação. Para definir legibilidade em um diagrama, estabelecemos alguns,' cr:itérios de estética, que denotam aspectos gráficos desejados em um desenho legível. Critérios, como distribuição uniforme dos objetos e minirnização do número de cruzamentos entre conexões, devem ser considerados no desenho de diagramàs da LegoShell. Assim, algoritrnos para o desenho de diagramas são projetados a partir da definição de tais critérios. Neste trabalho, foi realizado um levantamento de algoritrnos propostos para o desenho de diagramas ou grafos, a papir da definição de alguns critérios de estética, e do tipo do diagrama que está sendo representado. Alguns desses algoritrnos foram implementados para experimentação e análise junto aos diagramas da LegoShell. / Abstract: Diagrams are widely used as graphical representation for many types of information. LegoShell [Dru89] is a graphical language, under development at A_HAND Project, designed to represent distributed objects. In LegoShell diagrams, these objects appear connected like an oriented graph. Since LegoShell's practical exarnples can get very confusing, automatic layout tools can be necessary if we want to guarantee the clarity of its information. We establish some criteria to evaluate a diagrarn's readability, expressing some graphical aspects expected from a readable drawing. Criteria as uniform distribution of objects and minimization of the number of crossings between connections should be considered in drawings of LegoShell-like diagrarns. Algorithms for diagram drawing are designed from these criteria definitions. This work includes a survey about algorithms for diagrarn or graph drawing. This survey derives from the definition of some criteria and the type of the represented diagrarn. Some algorithms were implemented in order to experiment and analyze their performance with LegoShell diagrarns as subjects. / Mestrado / Mestre em Ciência da Computação

Orientador: Pedro Jussieu de Rezende / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Ciencia da Computação / Made available in DSpace on 2018-07-19T10:53:17Z (GMT). No. of bitstreams: 1 Fileto_Renato_M.pdf: 3121262 bytes, checksum: a6037b4da4c9e84f67c253e598cf0cce (MD5) Previous issue date: 1994 / Resumo: o tema central deste trabalho é a pesquisa de soluções para problemas de busca em subespaços (range search), sob o enfoque de projeto de algoritmos eficientes e geometria computacional, considerando objetos de dados em forma de pontos dispersos num espaço multidimensional e explorando diversos formatos de subespaços de busca encontrados na literatura. O objetivo é reunir diversas formulações e métodos de solução em um compêndio, onde estes são descritos sob uma mesma ótica, com notação uniforme e de forma mais simples que nos textos originais, de modo a facilitar um estudo mais detalhado e comparações, no que diz respeito à natureza e ao funcionamento das soluções. Pretende-se com isso tornar as idéias provenientes da pesquisa atualmente em processo na área de algoritmos acessíveis de forma mais integrada e simples, tanto aos interessados na pesquisa de métodos mais eficientes e adequados para problemas em teoria da computação, quanto àqueles mais interessados na aplicação dessas idéias. Um estudo abrangente das soluções encontradas na literatura permite perceber diversas semelhanças de concepção nos métodos empregados. Freqüentemente, pode-se observar a ocorrência de abordagens e técnicas comuns em diversas situações. A estas abordagens e técnicas de aplicação geral atribuímos o nome de paradigmas de algoritmos. O estudo e a utilização de paradigmas de algoritmos possibilitam um certo grau de sistematização das soluções de problemas de busca em subespaços, uma vez que eles permitem encarar diversas soluções distintas, de diversas variações do problema como manifestações de um mesmo fundamento racional. Alem disso, o estudo de paradigmas é instrutivo, pois promove o desenvolvimento de raciocínios sistemáticos, aplicáveis na resolução de diversos problemas em computação. A divisão do conteúdo é efetuada de maneira a fornecer primeiro o fundamento: teórico, necessário à compreensão dos métodos de solução, que são tratados posteriormente. No capítulo 1, são fornecidos os conceitos e classificações básicos, relativos a problemas de busca em geral e particularmente busca em subespaços, a fim de prover uma fundamentação teórica e situar a área de estudo.. No capítulo 2, são descritos alguns paradigmas de algoritmos aplicados a problemas de busca em subespaços, com o intuito de prover ao leitor maneiras alternativaS de relacionar as soluções apresentadas posteriormente, induzindo-o a desenvolver raciocínios que lhe habilitem a perceber os fundamentos e técnicas em comum. Nos capítulos 3 a 6, são abordados os sub.problemas caracterizados pelos formatos clássicos de subespaços de busca encontrados na literatura, ordenados da maneira que parece mais conveniente e que reflete a complexidade das soluções, a natureza das mesmas e sua evolução histórica. Em cada um destes capítulos, os sub-problemas são discutidos em detalhes, algumas soluções e limites inferiores são descritos superficialmente e há uma seção de notas bibliográficas, com referências para assuntos específicos. Finalmente, no capítulo 7, são sintetizadas as contribuições do trabalho e relacionados alguns assuntos para possíveis extensões no futuro. / Abstract: The main, objective of this work is the study of solutions found in the literature to range search, from the view point of algorithm design and computational geometry, considering only data objects; in the form of points embedded1 in a multidimensional space, and investigating various shapes of ranges. Several formulations and solutions to range search problems are surveyed. These are described under one abstract view, with uniform notation and in a form hopefully clearer than, the original sources, in such way that comparisons of the nature and functionality of the solutions and more detailed studies may be facilitated. Our purpose is to make the ideas deriving from the research on range search available in a more integrated and simpler way, to people interested in the discovery of more suitable and. efficient methods for problems in theoretical computer science as well as to those interested in the applications of these ideas. A wide study of the solutions found in the literature shows many conceptual similarities in the employed methods. Frequently, the same approaches and' techniques are seen in distinct situations. These general purpose approaches and techniques are called "algorithm paradigms". The study and application of these paradigms allow a certain level of generalization of the solutions to range search problems, because they allow one to perceive several solutions of vario1ls instances of a general problem as the manifestation of the same rationale. The study of algorithm paradigms is instructive in its own right, since it propitiates the development of systematic reasoning, useful in the solution of many problems in computer science. The contents herein are arranged so as to first give the theoretical basis necessary to understanding the methods given later. In chapter 1, we provide the basic concepts and classifications related to search problems in general and to range search in particular, and establish the scope of our research. In chapter 2, we describe some algorithm paradigms applied to range search problems, with the purpose of supplying the reader with alternative ways of establishing connections among the solutions presented later leading him to develop a reasoning that allows the identification of the fundamentals and techniques shared by tile sol1itions. In, chapters 3 to 6, we deal with the variations of' the range search problem characterized by the classical shapes of ranges considered in the literature. These chapters are arranged in a convenient way in order to reflect the complexity ofthe discussed solutions, their nature and the historical evolution. In each one of these chapters the problems are discussed in detail, some solutions and lower bounds are briefly described and bibliographic notes containing references to specific subjects are presented. Finally, in chapter 7, we summarize the contributions of this work and extensions that can be undertaken in the future. / Mestrado / Mestre em Ciência da Computação

Orientador: Norai Romeu Rocco / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Científica / Made available in DSpace on 2018-07-19T14:11:03Z (GMT). No. of bitstreams: 1 Maldonado_AngelaMabel_M.pdf: 3014977 bytes, checksum: 729fd219615f4c01f74c43e795ecb40c (MD5) Previous issue date: 1994 / Resumo: O propósito deste trabalho é estudar os aspectos teóricos e certos detalhes da implementação do Algoritmo para geração de p-grupos desenvolvido por M.F. Newman e E.A. O'Brien. A implementação deste algoritmo permite o cálculo de certas extensões particulares de p-grupos; possibilitando assim, a determinação dos p-grupos finitos. Fazemos isto no capítulo 3, onde também incluímos um exemplo de algumas iterações deste procedimento, calculando manualmente 0s 2-grupos 2-gerados de ordem menor o igual a 24 / Abstract: Not informed / Mestrado / Mestre em Matemática

Orientador: Ana Friedlander / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Científica / Made available in DSpace on 2018-07-19T17:33:43Z (GMT). No. of bitstreams: 1 Bitar_SandroDimyBarbosa_M.pdf: 580688 bytes, checksum: db0d10109993c41a5e242807ab824dbc (MD5) Previous issue date: 1994 / Resumo: Neste trabalho, demonstramos os teoremas de identificação de restrições ativas para um algoritmo de região de confiança apresentado em [13] para resolver o problema min f(x) sujeita a ¿Observação: O resumo, na íntegra poderá ser visualizado no texto completo da tese digital. / Abstract: Not informed. / Mestrado / Mestre em Matemática Aplicada

En esta Tesis Doctoral se propone una solución para el soporte de la clase de servicio ABR que utiliza técnicas de planificación equitativa (fair queueing). La clase de servicio ABR especifica un reparto equitativo del ancho de banda disponible en la red entre las conexiones que la atraviesan. Para efectuar este reparto, la provisión de ABR se basa en un control de flujo por realimentación explícita de tasa. LOS ALGORITMOS de conmutador son los encargados de generar la señal de realimentación para el control de flujo en ABR. En esta Tesis se propone un algoritmo de conmutador original que asume planificación equitativa en los puertos de salida de los conmutadores. La estimación de tasa equitativa que efectúa este algoritmo de conmutador se hace a partir del tiempo de cabeza de cola de las células de cada conexión, el cual es una medida del ancho de banda que asigna el algoritmo de planificación equitativa a cada conexión. LOS ALGORITMOS DE PLANIFICACION EQUITATIVA REALIZAN UN REPARTO DEL ANCHO DE BANDA DISPONIBLE EN EL ENLACE QUE EQUITATIVO EN EL SENTIDO MAX-MIN: De este modo el algoritmo de conmutador propuesto genera una señal de realimentación que resulta también en una distribución del ancho de banda disponible en la red que es equitativo max-min. A partir del algoritmo de conmutador propuesto, se han incorporado dos extensiones que permiten, por un lado, que la asignación de ancho de banda en los puertos (y, por tanto, la distribución del ancho de banda de la red) pueda ponderarse / Guijarro Coloma, LA. (1998). Contribución al soporte de la clase de servicio ABR en redes ATM mediante Técnicas de planificación equitativa [Tesis doctoral no publicada]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/4182

El objetivo de esta tesis ha sido diseñar nuevas estrategias de procesamiento paralelo en entornos de cómputo distribuido heterogéneo para facilitar la resolución de problemas tanto estructurales como numéricos del campo de la ingeniería de procesos. Como resultado de estas investigaciones se ha logrado el desarrollo de técnicas robustas y eficientes aplica-bles a un amplio espectro de problemas de búsquedas en gra-fos y de optimización con función objetivo y restricciones no lineales. En términos generales, es posible distinguir dos líneas de investigación para el desarrollo de algoritmos paralelos dis-tribuidos: la paralelización de algoritmos secuenciales existen-tes y la creación de alternativas intrínsecamente paralelas. En el caso de problemas estructurales, se estudiaron los métodos secuenciales clásicos de búsqueda en grafos y se establecie-ron las limitaciones para su uso en redes de estaciones de tra-bajo. Sobre esta base se propuso un nuevo método de distri-bución semi-dinámica y se la aplicó al algoritmo GS-FLCN para análisis de observabilidad. Por otra parte, en la línea de los algoritmos intrínsecamente paralelos se desarrolló un nuevo algoritmo de búsqueda totalmente distribuido con el objeto de aumentar la eficiencia de los recorridos para esta aplicación específica. En cuanto a los problemas numéricos, se conside-raron estrategias para aplicar el paralelismo a las secciones de cómputo intensivo de algoritmos secuenciales existentes para optimización no lineal con restricciones conocidos como GRG y SQP. Asimismo se desarrolló una nueva técnica de descompo-sición de dominio con el objeto de ampliar el rango de aplica-bilidad de un algoritmo intrínsecamente paralelo concebido originalmente para problemas sin restricciones de modo que se lo pudiera utilizar en forma eficiente para el tratamiento de los problemas de optimización no lineal con restricciones que sur-gen en ingeniería de procesos. En cuanto a las verificaciones de desempeño, se adaptaron las métricas de speedup con el objeto de tener en cuenta la heterogeneidad de los procesa-dores y así poder asegurar comparaciones justas. En tal senti-do, todos los nuevos algoritmos propuestos lograron un muy buen desempeño en cuanto al tiempo de ejecución en compa-ración con los algoritmos secuenciales correspondientes. Se analizaron casos de estudio académicos y problemas industria-les reales de mediano y gran tamaño pertenecientes al área de ingeniería de procesos. Por último, cabe destacar que los beneficios derivados de las propuestas descriptas en esta te-sis doctoral no se limitan al ámbito de ingeniería de proce-sos. Tanto las búsquedas en grafos como los problemas de optimi-zación surgen naturalmente en otras ramas de la inge-niería así como también en biología, economía, etc. No solo es fac-tible emplear en otras disciplinas los mismos algoritmos sino también aplicar la filosofía subyacente, tal como el criterio de descomposición de dominio o la distribución semidinámica de carga.