O objetivo principal deste trabalho é o desenvolvimento e avaliação de algoritmos numéricos paralelos e sua execução em máquinas paralelas (máquinas multiprocessadas, máquinas vetoriais e máquinas paralelas virtuais). Os algoritmos desenvolvidos foram executados em diferentes condições tanto em termos de plataformas utilizadas como em termos de tamanho da aplicação considerada. Os resultados obtidos na implementação dos algoritmos numéricos são analisados baseando-se em algumas métricas (tempo de execução e operações em ponto flutuante) comuns aos resultados apresentados nos principais benchmarks estudados. Através dos resultados obtidos, o desempenho das bibliotecas de passagem de mensagem MPI e PVM, o desempenho das arquiteturas consideradas e da implementação dos algoritmos numéricos são analisados. / The main objective of this dissertation is the development and evaluation of numerical parallel algorithms and their execution on parallel machines (multiprocessor machines, vectorial machines and parallel virtual environments). The algorithms developed have been executed under different conditions both in terms of the hardware plataform adopted and the problem size. The results obtained with the numerical algorithms implementation are all analyzed according to some metrics (execution time and float-point operations) available in the main benchmarks studied. The performance reached with the message passing libraries PVM and MPI together with the performance observed from the different architectures considered and the numerical algorithms implemented are ali analyzed according to the result obtained in this work.

O avanço de algumas áreas como computação e comunicação de dados, bem como a busca incessante pelo domínio das informações, contribui para aumentar cada vez mais as pesquisas relacionadas com aquisição de conhecimento, tema central da área de Inteligência Artificial. A aquisição implícita de conhecimento é realizada utilizando-se algoritmos de Aprendizado de Máquina. No caso de algoritmos simbólicos supervisionados, o conhecimento adquirido é representado em estruturas lógicas, tais como regras do tipo se então, que são entendíveis pelo ser humano. Quando o número de regras é elevado, ou as regras consideram muitas condições no seu corpo, torna-se difícil, ao ser humano, a análise desse conhecimento. Uma solução para esta questão é o desenvolvimento de boas medidas de avaliação de regras. Independentemente da quantidade de regras, essas medidas ajudam a selecionar aquelas que são mais úteis e interessantes, pois parte do conhecimento adquirido dos exemplos pode ser muito óbvio ou irrelevante. Neste trabalho são discutidas algumas medidas propostas na literatura, com a finalidade de auxiliar o usuário no entendimento e utilização proveitosa do conhecimento adquirido. Com base nos estudos realizados foi projetado e implementado um sistema computacional, denominado 7.0 system , para auxiliar na avaliação dessas regras de conhecimento. 0 RQsystem foi desenvolvido na linguagem de programação lógica Prolog e consiste de dois módulos principais. O primeiro é responsável pelo pré-processamento dos dados de entrada. O segundo módulo é responsável por fornecer diversar informações pré-definidas no sistema ou construídas e formuladas pelo usuário. o TZQsystern está descrito neste trabalho utilizando um pequeno conjunto de dados do mundo real e as regras geradas pelos algoritmos de Aprendizado de Máquina C.111-2 e C4.5. Esse sistema tem características interessantes que lhe conferem uma boa utilidade tanto na avaliação de regras quanto no estudo de outras questões relacionadas com as regras. Extensões futuras do sistema poderão ser particularmente úteis em Data Mining. / The field of Machine Learning (ML) is concerned with the development of computational methods to implement various forms of learning, in particular methods capable of inducing knowledge from examples, i.e. determining a concept description from a set of provided concept examples. Learning algorithms can generally be classified into one of two,major categories: black-box methods and knowledge-oriented methods. The description produced by the black-box approach cannot be easily interpreted by the user and does not provide explanation of the recognition process. On the other hand, knowledgeoriented methods aim at creating symbolic knowledge structures that satisfy the principie of comprehensibility, providing explanation of the recognition process. In this work we consider knowledge-oriented ML algorithms that express the discovered concept in the form of if-then rules. An important problem is related to the reliability, quality and interestingness of the rules generated by these algorithms. Still, when the quantity of mie generated is lane, the selection of good rules can became a serious problem for the human user. In this work we present and discuss several measures that can provide useful support in interpreting and ranking the rules generated by Machine Learning algorithms. These measures were implemented in a computational system called R.Qsystem. The system uses as input a common file format for data sets and features description which is independent of the ML algorithm used to generate the if-then rules. The file format for the rules generated is algorithm dependent. The R.Qsystem has been implemented in Prolog and it is query-centered, permitting the user to specify any constraints on the desired result of a query. The user can either specify the constraints in terms of procedures already implemented in the system or can define his/her new procedures to be considered as new constraints. The RQsystem is described in this work using a small real world data set and the rules generated by CAI2 and C4.5 Machine Learning algorithms. Future extensions to the system that, we consider will be particularly useful in Data Mining are also discussed.

O objetivo deste trabalho é apresentar pares de matrizes de conexão para o índice de Conley discreto. Na primeira, parte do texto introduzimos os conceitos e resultados básicos da Teoria do índice de Conley para aplicações contínuas definidas em espaço métrico localmente compacto. Dedicamos a segunda parte deste trabalho para discutir decomposições de Morse parcialmente ordenadas de conjuntos invariantes isolados para aplicações contínuas e introduzir o conceito de pares de matrizes de conexão. Provamos sua existência para decomposições atratoras-repulsoras de 11111 conjunto invariante isolado e finalizamos com alguns resultados que ilustram como os pares de matrizes de conexão podem implicar a existência de órbitas de conexão entre conjuntos de Morse. / The goal of this work is t,o present the connection matrix pairs for discrete Conley index. The first, part of this manuscript consists of introducing the basic concepts and results of the Conley index theory for continuotts maps defined ou a locally compact inetric space. \\\\Te devote the se.cond part of the work to discuss partially ordered Morse decompositions of isolated invariant seis for continuous maps and introduce the concept, of connection matrix pairs. We prove the existence of such pairs for attractor-repeller decompositions of an isolated invariant set and finish with some results that, Mustrate how connection matrix pairs may imply the existence of connecting orbit,s between Morse sets.

O reconhecimento automático de faces é um dos problemas mais desafiadores no campo da visão computacional e de reconhecimento. Métodos seguros e robustos podem ser usados em uma grande variedade de aplicações, como em sistemas de identificação de suspeitos pela polícia. A identificação de suspeitos com auxílio de testemunhas ou vítimas é muito usada na solução de crimes. Um dos métodos mais usados na identificação é o álbum de fotografia, que é desgastante, toma tempo, e confimde a testemunha que examina milhares de fotos. Pode-se, entretanto, desenvolver um sistema que combine a descrição da testemunha com as descrições contidas numa base de dados, ordenando as fotos a serem apresentadas para a vitima em ordem de similaridade, tomando menos tediosa e mais rápida a identificação correta do suspeito pela testemunha. Este trabalho diz respeito à seleção de técnicas e à criação de um sistema de catinstramento multimidia de suspeitos, com utilização de um algoritmo de reconhecimento de fotos para apoio à ordenação da base de fotografias policiais. Entre os algoritmos existentes para reconhecimento de faces, foi selecionado o PCA (Principal Component Analisys). Uma base de dados para cadastramento foi criada, incluindo fotografias, e o algoritmo de reconhecimento foi implementado para completar a funcionalidade do sistema. Testes sugerem bom grau de reconhecimento e boa adaptação à tarefa de ordenação do conjunto de fotos. / Face recognition is one of the most challenging subjects in computational vision. Methods that are safe and reliable are employed in a variety of applications, like the suspect identification case treated here. Suspect identification is usually carried out with help from witnesses and victims, with the use of photo albume. However, this method is tiresome, time consuming and misleading to the victim, particularly after a number of photos have been examined. It is possible, nowadays, to use available algoritluns and techniques to support suspect identification tasks, by sorting photographs using similarities as keys. This work regards the study and implementation of teclunques for filing and browsing suspect information, with use of a face recognition algoritlun to help identification. Amongst the face recognition algoriduns available, a version of PCA (Principal Component Analysis) was implemented. A multimedia database was created to help register individuais and occurrences, and the recognition algoridun was written to work with the data base. Tests suggest good recognition and suitability for database ordering.

Este trabalho apresenta um protótipo de ferramenta, a Html2Hip, que proporciona um ambiente de importação e adaptação de documentos descritos segundo o padrão HTML (HyperTexi Markup Language) para a representação interna do SASHE (Sistema de Autoria e Suporte Hipermiclia para Ensino), que se baseia na estruturação de objetos multimidia, segundo a hierarquia de classes proposta pelo MCA (Modelo de Contextos Aninhados). Além disso, este trabalho estendeu a capacidade do editor de nós de informação do tipo texto do protótipo anterior no que concerne ao processamento de arquivos-texto descritos pelo padrão RTF (Rich Text Formai). Dessa forma, o SASHE tornou-se capaz de processar e organizar materiais instrucionais preparados em seu próprio ambiente, no ambiente NX/NTAT/ (World-Wide Web), bem como em processadores de texto comuns. / This work presents a tool prototype, the Html2flip, that provides an importation and adaptation environment of documents described in HTML (HyperText Markup Language) standard for the internai representation of the SASHE (Hypermeclia System for Authorship and Supporting Educational Applications), that is based on the structural organization of multimeclia objects, proposed by MCA (Nested Contexts Model). Moreover, this work extended the capacity of the information text node editor of the previous prototype conceming the processing of text-files described in RTF (Rich Text Formar) standard. This way, the SASHE became capable to process and to organize instructional materiais prepared in its proper environment, in the WWW (World- Wide Web) environment, as well as in common word processors.

O armazenamento e a recuperação de imagens podem fazer-se pela indexação de características extraidas, automaticamente, por algum procedimento computacional. Estas caracteristicas são muitas vezes constituídas por valores numéricos sob a forma de vetores, representando coordenadas de pontos no espaço cuja dimensão é determinada pela quantidade destes valores. Diversos métodos de indexação voltados para este tipo de dados têm sido estudados e desenvolvidos no contexto de Sistema Gerenciadores de Banco de Dados. tidos como Métodos de Indexação Espacial, com o intuito de melhorar o desempenho do acesso às informações. O presente trabalho se inicia pela exposição de como o Modelo de Dados SIRIUS define \"Imagem- como tipo de dados abstrato, visando o desenvolvimento de aplicações na área médica. e como algoritmos de extração de características são associados a este tipo. Em seguida, fez-se o estudo sobre dados espaciais envolvendo: definições, propriedades, aplicações e métodos de indexação espacial, onde os métodos R-Tree e TV-Tree são descritos. Por fim, discutiu-se o resultado de testes feitos com esses métodos, utilizando conjuntos de pontos entre as dimensões 2 e 255, o que aponta o segundo (TV-Tree) como o mais adequado a aplicações que trabalham com pontos em dimensões distintas e elevadas. Dessa forma, pôde-se definir qual o método mais preferencial a ser incorporado ao Gerenciador de Objetos do SIRIUS, afim de efetuar a indexação do tipo de dados -Imagem\" nesse ambiente. / The retrieval of images from databases using features automatically extracted from the stored material takes advantage of ali information contained in the images, and it precludes human analysis. The features extracted are typically arrays of numbers that are used by index structures as points in an n-dimensional space, where n is the size of the feature array. Recently, many indexing methods for the image data type have been studied and developed on the context of Data Base Management Systems. Such methods are known as Spatial Data Structures or Multidimensional Access Methods. This work briefly introduces how \"Images\" are defined as an abstract data type in the SIRIUS Data Model, and how feature extraction algorithms can be associated to this data type. The approach is aimed toward a medical domain application context Therefore, the most important spatial data types are studied, describing their properties, common applications and indexing methods. The methods R-Tree and TV-Tree are described in detail. Finally, the results of the tests performed using these methods for point data sets within the dimensions 2 and 255 are presented. It was seen that the TV-Tree method is better suited for applications that need to work with point data in distinct and high dimensions. Thus, the TV-tree method can be used in the SIRIUS/GO Object Manager.

Este trabalho apresenta um estudo sobre as modificações necessárias no ASiA (Ambiente de Simulação Automático) para viabilizar a utilização de Redes de Petri para a representação de modelos. Esse estudo inicia-se com uma comparação entre Redes de Filas e Redes de Petri. utilizadas como técnicas para modelagem de sistemas computacionais, visando a avaliação desses sistemas através de simulação. O estudo da viabilidade analisa diversos aspectos tais como: possibilidade de utilização da linguagem SMPL; avaliação das modificações necessárias no Editor Gráfico; alterações necessárias no Gerador de Aplicações e no Gabarito utilizado pelo ASiA. / This work presents a study in respect to the modifications required in ASiA (Automatic Simulation Environment) to make possible the utilization of Petri Nets in models representation. The first step of this study is a comparison between Queue Nets and Petri Nets, when they are used as a techinique for computer system modeling, aiming the avaluation okf these systems using simulation. The viability study considers differents aspects, such as: the usage of SMPL in the simulation of systems represeted through Petri Nets; evaluation of the changes in the ASiA Graphic Editor, Aplication Generator and in the stencil used for the ASiA.

Este trabalho apresenta um estudo sobre problemas de dimensionamento de lotes monoestágios, que consistem em determinar as quantidades de itens a serem produzidos em diferentes períodos de tempo, de modo a minimizar a soma dos custos de produção, preparação e estoque. A quantidade produzida em cada período deve ser capaz de atender as demandas dos itens, sem exceder a capacidade de máquina. Para retratar o consumo de recursos, são incluídos tempos de preparação e produção. Inicialmente, são apresentados alguns métodos básicos para resolução de modelos simplificados e, em seguida, apresenta-se dois métodos para resolução de importantes modelos da literatura de problemas monoestágios. O primeiro, foi desenvolvido por Trigeiro et ai. (1989) e consiste num método heurístico baseado em relaxação Lagrangiana, no método de otimização do subgradiente e em uma heurística de factibilização. O segundo método, desenvolvido por Diaby et aL (1992a), é um método exato, baseado num procedimento de enumeração implícita, onde os limitantes inferiores são gerados por relaxação Lagrangiana tendo como opção a utilização do método de otimização do subgradiente. O primeiro método foi implementado assim como uma versão modificada. Finalmente, são apresentados alguns experimentos computacionais comparando as duas versões. / This work presents a study of the single product lot sizing problems. These problems consists of determining the quantities to be produced in different periods of time, minimizing the sum of costs of production, setup and inventory. The quantity to be produced in each period should be sufficient to attend the demands of items, without exceeding the capacity of the machine. To model the aspects of consumption of resources, setup and production times are included in the model. Initially, some basic methods for resolution of simplified models are presented, followed by two other methods for resolution of important models in the literature of single product problems. The first one, developed by Trigeiro et aL (1989), consists of a heuristic method based on Lagrangean relaxation, subgradient optimization and a feasibility heuristic. The second one, developed by Diaby et aL (1992a), is an branch and bound method, using lower bounds generated by Lagrangean relaxation, and the subgradient optimization method as an option. The first method was implemented together with a modified version. Finally, it is presented some computational experiments comparing both versions.

Este trabalho apresenta uma especialização do Método Primal Simplex para resolver o Problema de Aproximação Linear no L1 e o Problema de Regressão Quantil, os quais são casos particulares de Problema de Programação Linear por Partes. No Problema de Regressão Quantil a função objetivo linear por partes depende de um parâmetro θ e, com pequenas adaptações da pós otimização clássica da Programação Linear, pode-se determinar o intervalo para θ onde a solução do problema fica invariante. Assim, este trabalho apresenta também uma maneira simples para realizar esta análise pós otimização. Além disso, este trabalho apresenta alguns resultados computacionais, utilizando-se de exemplos da literatura. / This work presents a specialized of the Primal Simplex Method in order to solve the Least Absolute Approximation Problem as well as the Regression Quantile Problem, which are particular instances of Piecewise Linear Programming Problem. The piecewise linear objective function of the Regression Quanrile Problem is defmed using a parameter θ and slight modification in the classic post-optimality analyses of Linear Programming can be obtained in order to determine the interval for θ where the solution remains invariant. This work presents a simple manner to get this interval. Furthermore, this work illustrates some computational performance of the implemented method using examples from the literature.

O conceito de manufatura celular consiste em decompor um sistema de manufatura em subsistemas mais fáceis de gerenciar que o sistema global. As máquinas são agrupadas em células e as peças em famílias. Cada par família-célula constitui uma célula de manufatura. Nesta dissertação estudamos vários algoritmos e modelos para a obtenção de células de manufatura e propomos um método para resolver este problema baseado no algoritmo da máquina semente. Os resultados obtidos sobre vários exemplos da literatura são equivalentes ou melhores que aqueles existentes. / The concept of cellular manufacturing is to decompose a manufacturing systems into subsystems, which are easier to manage than the global manufacturing system. Machines are grouped into machines cells and parts are grouped into part families. Each family-cell pair constitutes a manufacturing cell. In this thesis we study several algorithms and models for cellular manufacturing design and we propose a method to solve this problem based on the seed machine algorithm. The results obtained with this method on several examples found in the literature are consistently equivalent to or even better than those hitherto proposed.