[pt] O uso cada vez mais corrente de métodos heurístico tem permitido contribuir para a automação e otimização de inúmeros processos industriais complexos. Um dos processos que vem sendo beneficiado é o corte de roupas na indústria do vestuário, onde o encaixe de moldes deve ser feito de forma a minimizar o desperdício de tecido. Este trabalho visa a dar uma contribuição ao problema geral de encaixe de figuras planas irregulares. Assim, busca-se resolver este problema através do uso de regras heurísticas implementadas num algoritmo computacional. Como ponto principal, o apresenta uma sistemática de construção de alternativas de encaixe, em forma de uma árvore, facilitando a busca de um encaixe solução, de alto rendimento, entre as praticamente infinitas possibilidades. A viabilização do algoritmo de encaixe é alcançada através de duas técnicas de posicionamento dos moldes que previnem sua superposição. As vantagens das duas técnicas são combinadas para melhor proveito do algoritmo. Nas conclusões são discutidas as dificuldades encontradas e formulados novos caminhos para a investigação. / [en] The increasing use of heuristical methods has advanced the frontier of application of optimization and automatization techniques in complex industrial processes. One emerging utilization for these methods in the pattern nesting process in the garment industry. The aim is to nest the pattern in such a way as to minimize the waste of fabric. The present work aims to contribute to the optimal nesting of general planes figures. The methods which will be discussed, employ heustical rules implemented thorough computacional algorithms. The focal point of the work is a methodology of obtaining a sequence of partial and complete nesting from which the best one can be selected. The computacional algorithm embodies two distinct methods for the placement of the figures on the nesting plane avoiding superposition. Both methods are used in such way that the resulting algorithm profits from their advantages. Present diffuclties and future trends are outlined in the conclusions.

[pt] Este trabalho aborda o problema de compactação de imagens, sem distorção, explorando o algoritmo M-LZA, proposto por Finamore e Nunes [2]. Nomcando de forma diferente os nós da árvore de codificação gerada pelo algoritmo M-LZA [2], o algoritmo V-LZA aqui introduzido busca ser uma alternativa mais eficiente do que seu antecessor com relação ao tamanho em bits, ocupado pela imagem codificada e/ou a rapidez de convergência para uma taxa de compactação mínima. / [en] This work focus on the problem of image compactation in the errorless sense, by means of exploring the M-LZA algorithm proposed by Finamore and Nunes [2]. Naming diferently the nodes of the coding tree fenerated by the M- LZA algorithm, the algorthm V-LZA introduced in this work, seek to became a more efficient alternative than its predecessor concerning the size of the coded image and/or its converging speed to a minimum compactation rate.

[pt] Este trabalho analisa algumas estratégias para decodificação de sinais TCM. Além disto, propõe-se uma nova estratégia que faz uso de um processamento por percurso sobrevivente na treliça de decodificação para gerar e atualizar, de acordo com um algoritmo do tipo PLL, um conjunto de estimativas de fase, cada uma associada a um estado da treliça, que são utilizadas simultaneamente no processo de decodificação. Expressões úteis para o direcionamento de parâmetros usados no algoritmo de estimação são apresentadas. Estas expressões foram baseadas em uma análise linear simplificada que considerou tanto o desempenho do estimador em estado estacionário quanto no período transiente. Resultados de desempenho obtidos, via simulação, com o uso do método proposto são comparados com resultados obtidos com outras estratégias para recuperação de portadora em sistemas TCM. Estes resultados mostram uma clara superioridade do método proposto para diversos tipos de erros de fase. / [en] This thesis analyses some coherent decoding schemes for TCM signals reception. In addition, a new scheme, which makes use of a per survivor processing, is propoed. In this scheme, each trellis state has an associated phase estimate which is generated by a data-aided PLL-like algorithm, based on the survivor sequence associated to that state. Some useful expressions are developed to help the parameters selection for use on the estimation algorthm. These expressions are based on a simplified linear analysis which are carried out on both transient and stationary cases. We compare the proposed scheme performance to others schemes by means of computer simulation. These results show that the new scheme has better performance in terms of bit-error-rate.

[pt] Em algumas aplicações, como por exemplo sinais de dados, a variância do sinal pode ser desconhecida, porém constante. Nesses casos, quantizadores adaptivos que utilizam algoritmos de estimação local da variância não são apropriados para a discretização do sinal. Algoritmos mais adequados para essa situação são aqueles que se preocupam em aprender a variância do sinal de entrada. Neste trabalho são examinados quatro algoritmos de aprendizagem de variância, com vistas ao seu emprego em quatização adaptiva. Um destes algoritmos, proposto por A. Gersho e D. J. Goodman, é um algoritmo de aproximação estocástica que converge com probabilidade 1. É mostrado que um outro algoritmo, também de aproximação estocástica, converge com probabilidade 1 para a aplicação em um quantizador adaptivo com entradas independentes. Os outros dois algoritmos consistem de modificações introduzidas sobre dois primeiros, com a finalidade de obter uma maior velocidade de convergência. Finalmente, é analisado, através de simulações em computador, o desempenho desses quatro quantizadores adaptivos quando usados em sistemas DPCM. / [en] In some applications, such as data transmission, signal variance is unknown but constant. In such cases, adaptive quantizers using local variance estimation algorithms are not appropriate for the signal quantizations. The most suitable algorithms for this situation are those which learn the input signal variance. This work examines four variance learning algorithms for application in adaptive quantization. One of them, proposed by A. Gersho and D. J. Goodman, is a stochastic approximation algorithm which converges with probability one, when applied to adaptive quantization. The remaining two algorithms are modified versions of the first two, in order to obtain greater convergence speed. Finally, performance of these four adaptive quantizers, when used in DPCM systems, is analyzed through computer simulations.

[pt] O trabalho consiste de um algoritmo, programado na linguagem LISP/360, que sintetiza uma máquina seqüencial por registros de deslocamento utilizando processos heurísticos. É feita a designação dos estados da máquina e os registros são de mesmo comprimento. Uma parte deste algoritmo consiste de um processo de adição de estados transitórios, tornando qualquer máquina realizável por registros de comprimento - 2. / [en] This paper is concerned with the equal-length shift- register realization of sequential machines. The state assignement is restricted to one code per state. An algorithm programed in LISP/360 is used, which synthesizes a given sequantial machine by shift registers. A part of this algorithm does an addition of transitory states, making possible the synthesis of every sequential machine by shift-registers of length 2.

[pt] Esta dissertação investiga a convergência e o desempenho de Algoritmos Genéticos: os problemas, soluções e medidas propostas. O trabalho consiste de cinco partes principais: uma discussão sobre os fundamentos matemáticos que buscam explicar o funcionamento de um Algoritmo genético; um estudo dos principais problemas associados à  convergência e ao desempenho de Algoritmos genéticos; uma análise das técnicas e algoritmos alternativos para a melhoria da convergência; um estudo de medidas para estimar o grau de dificuldade esperado para a convergência de Algoritmos Genéticos; e estudo de casos. Os fundamentos matemáticos de Algoritmos Genéticos têm por base os conceitos de schema e blocos construtores, desenvolvidos por Holland (apud Goldberb, 1989a). Embora estes conceitos constituam a teoria fundamental sobre a qual a convergência se baseia, há, no entanto, questões importantes sobre o processo através do qual schemata interagem durante a evolução de um Algoritmo genético (Forrest et al, 1993b). Este trabalho apresenta uma discussão sobre os principais questionamentos que têm sido levantados sobre a validade destes fundamentos. São discutidas as controvérsias geradas pela necessidade de uma visão dinâmica dos Algoritmos Genéticos, onde a amostra da população e os resultados obtidos pela recombinação sejam considerados. Em especial, as objeções apontadas pro Thornton (1995) quanto à  coerência da associação dos conceitos de schema e blocos construtores, a contradição entre os Teoremas schema e Price vista por Altemberg (1994), e as idéias de adequação do Teorema Fundamental de Algoritmos Genéticos ao conceito de variância dentro de uma população. Os principais problemas de convergência e desempenho de um Algoritmo Genético foram discutidos: a Decepção e a Epistasia. É apresentada a idéia de que a Decepção, embora esteja fortemente ligada à  dificuldade de convergência de Algoritmos Genéticos, não constitui fator suficiente para que um problema seja considerado difí­cil para um Algoritmo genético (GA-hard problems) (Grefenstette, 1993). São também apresentados os coeficientes de Walsh (Goldberg, 1989b) e demonstrada a sua relação com as idéias de schema e epistasia, e sua utilização em funções decepcionantes. São analisadas diversas funções decepcionantes. São analisadas diversas funções, associadas aos conceitos de Decepção e Epistasia: as funções fully-deceptive e fully easy com 6 bits, propostas por Deb e Goldberg (1994); as funções deceptive but easy e non-deceptive but hard de Grefenstette (op. Cit.); as funções F2 e F3 de Whitley (1992), e ainda, as funções NK (apud Harvey, 1993) e Royal Road (Forrest et al, op. Cit.) Técnicas alternativas para melhorar a convergência incluem basicamente algoritmos evolucionários com características especí­ficas a determinado tipo de problema. São analisados alguns algoritmos alternativos, como o Messy de Goldberg et alli (1989), o Estruturado de Dasgupta et al (s.d.), o aumentado de Grefenstette (ibidem) e os algoritmos propostos por Paredis (1996b). É ainda discutida e exemplificada a importância da escolha adequada de parâmetros e da representação de cromossomas, para que a convergência seja mais facilmente alcançada. O estudo de medidas de convergêcia de Algoritmos Genéticos fornece uma classificação: medidas probabilísticas e medidas baseadas em landscapes. São apresentadas também as colocações de Koza (1994) e Altemberg (op. Cit.) sobre a convergência de Algoritmos Evolucionários. É dado destaque para medida da dificuldade esperada para convergência baseada no Coeficiente de Correlação entre a Aptidão e a Distância (FDC - Fitness Distance Correlation), como proposto por Jones e Forrest (1995b). O estudo de casos consiste da análise do comportamento de Algoritmos Genéticos pela medida FDC, quando aplicados a um conjunto de funções matemáticas, incluindo as já citadas, e ainda as funções de teste propostas por De Jong (apud Goldberg, op. cit) e a função decepcionante de Liepins e Vose (apud Deb et al, 1994). Também é realizada uma extensão da medida de dificuldade FDC estudada, buscando adequá-la a uma visão mais dinâmica de Algoritmos Genéticos. Para executar estes testes, o ambiente GENEsYs 1.0, desenvolvido por Thomas Bäck (1992) (a partir de seu precursor Genesis de JOhn Grefenstette (apud Ribeiro et alli, 1994), foi adaptado e extendido. / [en] This wok investigates the convergence and the performance of Genetic Algorithms: the problems, solutions and proposed measures. It is divided into five topics: a discussion on the mathematical foundations that explains how Genetic Algorithms work: a study of the most important problems associated to their convergence and performance; an analysis of techniques and alternative Genetic Algorithms to achieve better convergence; a study of measures trying to estimate the level of difficulty for the convergence of GA s; and case study. The mathematical foundations are based in conceps of schema and building blocks, developed by Holland (apud Goldberg, 1989a). Although they constitute the fundamental theory about Genetic Algorithms convergence, there has been a lot of questions about the process in which schemata interact during the evolution of GA s (Forrest et al, 1993b). This work presents a discussion on the most important questions that have been raised about the validity of these foundations. Specifically the objections pointed out by Thorton (1995) about the conference of the association between schema and building blocks; the contradiction between schema theorem and Price theorem, mentioned by Altenberg (1994); and the new ideas raised by the variance of fitness concept. The most important problems related to the convergence and performance of GA s are discussed, i.e. the Deception and the Epistasis. Even though Deception can difficult the convergence, the former does not constitute a sufficient factor for the late (Grefenstette, 1993). The Walsh coefficients (Goldberg, 1989b0 and their relation with schema are presented, and also their utilization in deceptive fuctions. Some functions are analised, based on the concepts of Deception and Epistasis: the 6-bits fully- deceptive function by Deb et all (1994): the 3-bits fully- deceptive functions, by Deb et alli (1989); the functions deceptive but easy and non-deceptive but hard of Grefenstette (op. cit.) the F2 and F3 functions of Whitley (1992) as well as the NK functions (apud Harvey, 1993) and the Royal Road functions (Forrest et al, op. cit.). The techniques included the alternative GA s, with special carachteristics. The Messy GA of Goldberg (1989), the Structured GA of Dasgupta (s.d.), the Augmenated GA of Grefenstette (ibidem) and GA s fo Paredis (1996b). The importance of a correct choice of parameters is also discussed. The study of measures classifies those Ga´s into two types: probabilistics and based on landscapes. The considerations of Koza (1994) and Altenberg (op. cit.) are also discussed. It is given special enfasis to the FDC ( Fitness Distance Correlacion) measure, proposed by Jones and Forrest (1995b). The case study consists of the analysis of the behavior of GA by the measure FDC, applied to a set of mathematical functions. The environment used is GENEsYs 1.0, developed by Thomas Bäck (1992) over the Genesis of Grefenstette. The GENEsys 1.0 was adapted and expanded to fullfil the requirements of this work.

[pt] No presente trabalho é examinada a decodificação de esquemas CPM (Continuous Phase Modulation) filtrados severamente (filtragem com resposta impulsional infinita) utilizando-se algoritmo M, um algoritmo de busca limitada. A estrutura formada pelo modulador CPM seguido do filtro é tratada como um esquema que realiza modulação codificada com utilização eficiente de faixa. A caracterização da modulação através de estados requer um número infinito de estados. O esquema é analisado através de simulação de sistema modulado em tempo discreto com processamento digital. A utilização de filtro digital permite uma caracterização de estados simplificada em relação a trabalhos anteriores. Uma versão simplificada do algoritmo M é analisada neste trabalho. Através de simulação realiza-se a análise do desempenho do sistema assim como do comportamento do algoritmo M na sua versão simplificada. / [en] Decoding of severely filtered CPM schemes with infinite impulse response filters using a limited search algorith (M-Algorithm ) is examined in this thesis. The structure composed by the CPM modulator followed by the filter is treated as a bandwidth efficient coded modulation scheme. The modulation requires a infinite state description. Analysis of the system is done by computer simulation. The analysed system is discret time modeled and uses digital signal processing techniques. This allows a simplified state description of the modulation scheme. A simplified version of the M-algorithm is analysed in the thesis. Analysis of the system performance as well as the M-algorithm (simplified version) behavior is done by simulation.

[pt] Neste trabalho, um método de compressão de dados com perdas, baseado no algoritmo de compressão sem perdas de Lempel-Ziv é proposto. Simulações são usadas para caracterizar o desempenho do método, chamado LLZ. É também aplicado à compressão de imagens e os resultados obtidos são analisados. / [en] In this work, a lossy data compression method, base don the Lempel-Ziv lossles compression scheme is proposed. Simulations are used to study the performance of the method, called LLZ. The lLZ is also used to compress digital image data and the results obtained is analized.

[pt] A tese de mestrado, aqui resumida, tem a meta de propor novos algoritmos para a compressão de dados, em especial imagens, apresentando aplicações e resultados teóricos. Como o título sugere, estes dados serão originados de fontes com alfabeto contínuo, podendo ser particularizado para os casos discretos. O algoritmo a ser proposto (LLZ para o caso contínuo) é baseado no codificador universal Lempel-Ziv, apresentando a característica de admitir a introdução de perdas, mas que conduza a um maior aproveitamento do poder de compressão deste algoritmo. Desta forma, o LLZ se mostra vantajoso em dois pontos: integrar compactador e quantizador, e ser um quantizador universal. / [en] This dissertation introduces new data compression algorithms, specially for images, and presents some applications and theoretical results related to these algorithms. The data to be compressed will be originated from sources with continuos alphabet, and can be stated for discrete sources. The proposed algorithms (LLZ for continuos case), which is based on the universal Lempel-Ziv coder (LZ), accepts losses, taking advantage of LZ s compression power. As such, the LIZ is an innovating proposal in two ways: first, it couples compaction and quantization in one step; and second, it can be seeing as an universal quantizer.

[pt] O problema da classificação de dados remonta à criação de taxonomias visando cobrir áreas do conhecimento. Com o surgimento da Web, o volume de dados disponíveis aumentou várias ordens de magnitude, tornando praticamente impossível a organização de dados manualmente. Esta dissertação tem por objetivo organizar dados semi-estruturados, representados por frames, sem uma estrutura de classes prévia. A dissertação apresenta um algoritmo, baseado no K-Medóide, capaz de organizar um conjunto de frames em classes, estruturadas sob forma de uma hierarquia estrita. A classificação dos frames é feita a partir de um critério de proximidade que leva em conta os atributos e valores que cada frame possui. / [en] The problem of data classification goes back to the definition of taxonomies covering knowledge areas. With the advent of the Web, the amount of data available has increased several orders of magnitude, making manual data classification impossible. This dissertation proposes a method to automatically classify semi-structured data, represented by frames, without any previous knowledge about structured classes. The dissertation introduces an algorithm, based on K-Medoid, capable of organizing a set of frames into classes, structured as a strict hierarchy. The classification of the frames is based on a closeness criterion that takes into account the attributes and their values in each frame.