Este estudo foi motivado pela necessidade de se tratar o excesso de vazão afluente às estações de tratamento de esgoto, que ocorre em dias de chuvas intensas. A hipótese central deste estudo é a de que a adoção de processo físico-químico para o tratamento de esgoto excedente diluído, pode ser vantajosa em relação ao aumento da capacidade com a ampliação dos sistemas exclusivamente biológicos. A pesquisa foi desenvolvida na ETE Martim de Sá da SABESP, localizada em Caraguatatuba/SP, onde o esgoto é tratado por lodos ativados em bateladas sequenciais. Estudou-se a variação da vazão de esgoto afluente na época de chuvas, bem como o funcionamento das bateladas. Além disso, foi avaliado o emprego da coagulação, floculação e sedimentação em decantador laminar para tratar o excesso de vazão com aplicação de sulfato de alumínio, cloreto férrico e polímero catiônico em uma estação piloto, após a realização de ensaios em escala de bancada em aparelho de Jar Test. O monitoramento da vazão afluente mostrou que em dias de chuvas e com ocorrência de desvios, a vazão máxima foi 220 L/s, ou seja, até 6 vezes maior que a vazão média de tempo seco. Para esta situação, o processo físico-químico pode tornar-se uma alternativa promissora, devido à sua capacidade de trabalho sob altas vazões em instalações de menor porte. Nos ensaios para se avaliar o tratamento físico-químico utilizou-se esgoto bruto pertencente a duas faixas de DBO: 50 e 100 mg/L e taxa de aplicação superficial no decantador de 76,82 m³ / m² / dia. A melhor dosagem de produto químico utilizada para tratar o esgoto bruto da faixa de DBO igual a 50 mg/L foi 40mg/L de cloreto férrico mais 0,5mg/L de polímero catiônico resultando em efluentes com DBO média de 26mg/L. Para o esgoto bruto da faixa de DBO igual a 100 mg/L a melhor dosagem foi a de 60mg/L de cloreto férrico, com DBO média dos efluentes igual a 44mg/L. Para esta faixa de trabalho é recomendável prever a aplicação de polímero. Por esta pesquisa concluiu-se que é possível atender aos limites legais de qualidade do esgoto tratado com o emprego do tratamento físico-químico, além disso produziu elementos importantes para subsidiar a avaliação econômica para a implantação desta tecnologia em paralelo ao sistema de lodo ativado nas situações de sobrecarga hidráulica. No entanto, a análise do fluxograma do funcionamento da estação com o processo de lodos ativado em bateladas, indicou que é possível efetuar o tratamento da vazão de 220 L/s pelo processo biológico. Assim, é recomendável a implantação do tratamento físico-químico somente se, após a realização do teste em escala real do funcionamento das bateladas com a vazão de 220 L/s, o tratamento biológico não atender aos padrões estabelecidos. / This study was motivated by the need to treat high wastewater influent exceeding in sewage treatment plants, which occurs on days of heavy rain. The central hypothesis of this study is that the physical-chemical process to treat dilute sewage overflow, it can be advantageous with respect to increased capacity and expansion of biological systems. The research was conducted in ETE Martim de Sá (SABESP), located in Caraguatatuba / SP, where the sewage is treated by sequencing batch reactor. It was studied the variation of the flow of wastewater during the rainy season, and the operation of the batch. Furthermore, it was evaluated the use of coagulation, flocculation and sedimentation in plate settler with application of aluminium sulfate, ferric chloride and cationic polymer in a pilot plant, after the testing of bench scale apparatus in Jar Test. Monitoring the inflow showed that on days of rainfall and bypass, the maximum flow was 220 L/s, up to 6 times the dry weather average flow. For this situation, the physico-chemical process may become a promising alternative, due to its ability to work under high flow rates in smaller facilities. In tests to evaluate the physical-chemical treatment was used two kinds of raw sewage: 50 and 100 mg/L BOD, overflow rate used in the plated settling tank was 76.82 m³/m² / day. The best dosage of chemical used to treat the raw sewage BOD of 50 mg/L was 40 mg/L ferric chloride plus 0.5 mg/L of cationic polymer, resulting in average effluent with BOD of 26 mg/L. For the raw sewage of the range BOD of 100 mg/L, 60 mg/L ferric chloride was the best dosage with an average BOD of effluent equal to 44 mg/L. For this range of work is recommended to provide for the application of polymer. This research concluded that it is possible to comply with the legal standard of treated sewage with physical-chemical treatment, also produced evidence that can help in the economic evaluation for the implementation of this technology in parallel with the activated sludge system in hydraulic overload situations. However, analysis of the flow diagram of operation of the station with the sequencing batch reactor, indicated that it is possible to make the treatment of flow of 220 L/s by the biological process. Therefore, is recommend the implementation of physical-chemical treatment only if after the test-scale operation of the batches with the flow rate of 220 L/s, the biological treatment doesn\'t meet the established standards.

Made available in DSpace on 2017-07-10T19:24:51Z (GMT). No. of bitstreams: 1 Carla Limberger Lopes_protegido.pdf: 1510356 bytes, checksum: 558cae02592904f9e836e71f9aa4036f (MD5) Previous issue date: 2011-07-01 / This study aimed to evaluate the influence of air flow (0.25, 0.50 and 0.75 L.min-1.Lreator-1) and cycle time (11.35 h, 15.15 h and 18.25 h) in the performance of a sequencing batch reactor (SBR) to promote nitrification and denitrification of wastewater from slaughterhouse's poultry and refrigerator. The operation included the steps of feeding, aerobic and anoxic reaction, sedimentation, discharge and rest. SBR was operated on a laboratory scale with a working volume of 4 L, keeping 25% of biomass retained in the reactor as an inoculum for the next batch. The "manipueira" was added as a carbon source at the beginning of anoxic phase in order to keep the C: N ratio between 5 and 6. During this process, parameters monitored included: pH, alkalinity, dissolved oxygen and temperature. It was developed a factorial design (22) with five repetitions at the central point to check the influence of the response variable removal of total inorganic nitrogen (NH4+-N + NO2--N + NO3--N) in the whole process (%). Data were analyzed with 95% confidence, and experimentally, a higher removal of total inorganic nitrogen (85.75%) on average was observed when using air flow of 0.50 L.min-1.Lreator-1 in time cycle of 15.15 h. However, there was no statistically significant factor for the air flow, and during the progress of study, this variable was kept stable at 0.25 L.min-1.Lreator-1 while the cycle time was gradually increased until efficiency in the removal of constant nitrogen could be observed, which occurred at time 15.1 h with 92.78% in removal efficiency of total inorganic nitrogen. / Esta pesquisa teve por objetivo avaliar a influência da vazão de ar (0,25, 0,50 e 0,75 L.min-1.Lreator-1) e do tempo de ciclo (11,35 h, 15,15 h e 18,25 h) no desempenho de um reator em bateladas sequenciais (RBS), em promover a nitrificação e a desnitrificação de água residuária de abatedouro e frigorífico de aves. A operação contemplou as etapas de alimentação, reação aerada e anóxica, sedimentação, descarte e repouso. O RBS foi operado em escala de laboratório com volume útil de 4 L, mantendo-se 25% da biomassa no reator, como inóculo para a próxima batelada. A manipueira foi adicionada como fonte de carbono no início da fase anóxica, de modo a manter a relação C:N entre 5 e 6. Durante o processo foram monitorados os parâmetros pH, alcalinidade, oxigênio dissolvido e temperatura. Elaborou-se um planejamento fatorial (22) com cinco repetições no ponto central para verificar a influência dos fatores na variável resposta remoção de nitrogênio inorgânico total (N-NH4++N-NO2-+N-NO3-) no processo completo (%). Os dados foram analisados com 95% de confiança e, experimentalmente, a maior remoção de nitrogênio inorgânico total (85,75%) em média foi observada quando se utilizou vazão ar de 0,50 L.min-1.Lreator-1, no tempo de ciclo de 15,15 h. Entretanto, não foi verificada significância estatística para o fator vazão de ar e, na continuidade do estudo, esta variável foi mantida estável em 0,25 L.min-1.Lreator-1, enquanto o tempo de ciclo foi gradativamente elevado até ser observada eficiência de remoção de nitrogênio constante, o que foi verificado a partir do tempo de 15,1 h com 92,78% na eficiência de remoção de nitrogênio inorgânico total.

Made available in DSpace on 2017-05-12T14:48:14Z (GMT). No. of bitstreams: 1 Carla Limberger Lopes_protegido.pdf: 1510356 bytes, checksum: 558cae02592904f9e836e71f9aa4036f (MD5) Previous issue date: 2011-07-01 / This study aimed to evaluate the influence of air flow (0.25, 0.50 and 0.75 L.min-1.Lreator-1) and cycle time (11.35 h, 15.15 h and 18.25 h) in the performance of a sequencing batch reactor (SBR) to promote nitrification and denitrification of wastewater from slaughterhouse's poultry and refrigerator. The operation included the steps of feeding, aerobic and anoxic reaction, sedimentation, discharge and rest. SBR was operated on a laboratory scale with a working volume of 4 L, keeping 25% of biomass retained in the reactor as an inoculum for the next batch. The "manipueira" was added as a carbon source at the beginning of anoxic phase in order to keep the C: N ratio between 5 and 6. During this process, parameters monitored included: pH, alkalinity, dissolved oxygen and temperature. It was developed a factorial design (22) with five repetitions at the central point to check the influence of the response variable removal of total inorganic nitrogen (NH4+-N + NO2--N + NO3--N) in the whole process (%). Data were analyzed with 95% confidence, and experimentally, a higher removal of total inorganic nitrogen (85.75%) on average was observed when using air flow of 0.50 L.min-1.Lreator-1 in time cycle of 15.15 h. However, there was no statistically significant factor for the air flow, and during the progress of study, this variable was kept stable at 0.25 L.min-1.Lreator-1 while the cycle time was gradually increased until efficiency in the removal of constant nitrogen could be observed, which occurred at time 15.1 h with 92.78% in removal efficiency of total inorganic nitrogen. / Esta pesquisa teve por objetivo avaliar a influência da vazão de ar (0,25, 0,50 e 0,75 L.min-1.Lreator-1) e do tempo de ciclo (11,35 h, 15,15 h e 18,25 h) no desempenho de um reator em bateladas sequenciais (RBS), em promover a nitrificação e a desnitrificação de água residuária de abatedouro e frigorífico de aves. A operação contemplou as etapas de alimentação, reação aerada e anóxica, sedimentação, descarte e repouso. O RBS foi operado em escala de laboratório com volume útil de 4 L, mantendo-se 25% da biomassa no reator, como inóculo para a próxima batelada. A manipueira foi adicionada como fonte de carbono no início da fase anóxica, de modo a manter a relação C:N entre 5 e 6. Durante o processo foram monitorados os parâmetros pH, alcalinidade, oxigênio dissolvido e temperatura. Elaborou-se um planejamento fatorial (22) com cinco repetições no ponto central para verificar a influência dos fatores na variável resposta remoção de nitrogênio inorgânico total (N-NH4++N-NO2-+N-NO3-) no processo completo (%). Os dados foram analisados com 95% de confiança e, experimentalmente, a maior remoção de nitrogênio inorgânico total (85,75%) em média foi observada quando se utilizou vazão ar de 0,50 L.min-1.Lreator-1, no tempo de ciclo de 15,15 h. Entretanto, não foi verificada significância estatística para o fator vazão de ar e, na continuidade do estudo, esta variável foi mantida estável em 0,25 L.min-1.Lreator-1, enquanto o tempo de ciclo foi gradativamente elevado até ser observada eficiência de remoção de nitrogênio constante, o que foi verificado a partir do tempo de 15,1 h com 92,78% na eficiência de remoção de nitrogênio inorgânico total.

Made available in DSpace on 2016-06-02T19:06:12Z (GMT). No. of bitstreams: 1 5971.pdf: 5628502 bytes, checksum: 38bfe45912e4f91f4ad8c7fb5fb815db (MD5) Previous issue date: 2012-08-03 / Universidade Federal de Minas Gerais / Technological development brought improvements in the technology of climate sensors and Earth's surface image acquisition, gathering increasing amounts of data. Generally, when these data are submitted to mining algorithms, the output is the production of hundreds or even thousands of textual patterns, making the task of data analysis by the domain expert even harder. Hence, it is crucial, to support experts, the development of a tool that helps to identify and display patterns of interest. In this context, this research project at Master Science level aims to develop a technique for mining association rules in time series allowing agrometeorological data analysis over time. / O avanço tecnológico tem propiciado melhorias nos diversos sensores utilizados para medições dos dados climáticos e de imageamento da superfície terrestre, coletando quantidades cada vez maiores de dados. Quando esses dados são submetidos aos algoritmos de mineração para serem explorados ocorre, em geral, a produção de centenas ou ate mesmo milhares de padrões textuais, dificultando ainda mais a tarefa de analise dos dados pelo especialista de domínio. Assim, e crucial, para apoiar os especialistas, o desenvolvimento de um ferramental que auxilia na identificação e visualização dos padrões de interesse. Neste contexto, este projeto de pesquisa em nível de mestrado visa desenvolver uma técnica de mineração de regras de associação em series temporais permitindo a analise de dados agrometeorológicos ao longo do tempo.

[pt] Nesse trabalho, estudamos online packing integer programs, cujas colunas são reveladas uma a uma. Já que algoritmos ótimos foram encontrados para o modelo RANDOMORDER– onde a ordem na qual as colunas são reveladas para o algoritmo é aleatória – o foco da área se voltou para modelo menos otimistas. Um desses modelos é o modelo MIXED, no qual algumas colunas são ordenadas de forma adversária, enquanto outras chegam em ordem aleatória. Pouquíssimos resultados são conhecidos para online packing IPs no modelo MIXED, que é o objeto do nosso estudo. Consideramos problemas de online packing com d dimensões de ocupação (d restrições de empacotamento), cada uma com capacidade B. Assumimos que todas as recompensas e ocupações dos itens estão no intervalo [0, 1]. O objetivo do estudo é projetar um algoritmo no qual a presença de alguns itens adversários tenha um efeito limitado na competitividade do algoritmo relativa às colunas de ordem aleatória. Portanto, usamos como benchmark OPTStoch, que é o valor da solução ótima offline que considera apenas a parte aleatória da instância. Apresentamos um algoritmo que obtém recompensas de pelo menos (1 − 5lambda − Ó de epsilon)OPTStoch com alta probabilidade, onde lambda é a fração de colunas em ordem adversária. Para conseguir tal garantia, projetamos um algoritmo primal-dual onde as decisões são tomadas pelo algoritmo pela avaliação da recompensa e ocupação de cada item, de acordo com as variáveis duais do programa inteiro. Entretanto, diferentemente dos algoritmos primais-duais para o modelo RANDOMORDER, não podemos estimar as variáveis duais pela resolução de um problema reduzido. A causa disso é que, no modelo MIXED, um adversário pode facilmente manipular algumas colunas, para atrapalhar nossa estimação. Para contornar isso, propomos o uso de tecnicas conhecidas de online learning para aprender as variáveis duais do problema de forma online, conforme o problema progride. / [en] We study online packing integer programs, where the columns arrive one by one. Since optimal algorithms were found for the RANDOMORDER model – where columns arrive in random order – much focus of the area has been on less optimistic models. One of those models is the MIXED model, where some columns are adversarially ordered, while others come in random-order. Very few results are known for packing IPs in the MIXED model, which is the object of our study. We consider online IPs with d occupation dimensions (d packing constraints), each one with capacity (or right-hand side) B. We also assume all items rewards and occupations to be less or equal to 1. Our goal is to design an algorithm where the presence of adversarial columns has a limited effect on the algorithm s competitiveness relative to the random-order columns. Thus, we use OPTStoch – the offline optimal solution considering only the random-order part of the input – as a benchmark.We present an algorithm that, relative to OPTStoch, is (1−5 lambda− OBig O of epsilon)-competitive with high probability, where lambda is the fraction of adversarial columns. In order to achieve such a guarantee, we make use of a primal-dual algorithm where the decision variables are set by evaluating each item s reward and occupation according to the dual variables of the IP, like other algorithms for the RANDOMORDER model do. However, we can t hope to estimate those dual variables by solving a scaled version of problem, because they could easily be manipulated by an adversary in the MIXED model. Our solution was to use online learning techniques to learn all aspects of the dual variables in an online fashion, as the problem progresses.

Neste trabalho de doutorado utilizou-se um reator anaeróbio em batelada seqüencial contendo biomassa imobilizada em matrizes cúbicas de espuma de poliuretano e agitação mecânica, com volume total de 5.5 L e volume útil de 4.5 L. A agitação do meio líquido foi realizada com quatro tipos de impelidores (turbina tipo hélice, lâminas planas, lâminas planas inclinadas e lâminas curvas, testados individualmente, sempre em número de 3), com 6 cm de diâmetro. A pesquisa foi realizada em quatro etapas experimentais. A etapa 1 objetivou determinar o tempo de mistura no reator para cada tipo de impelidor, ou seja, o tempo necessário para que o meio líquido ficasse totalmente homogêneo. A etapa 2 objetivou selecionar o tipo de impelidor e a respectiva intensidade de agitação que garantisse a minimização da resistência à transferência de massa externa no sistema. As intensidades de agitação testadas variaram de 200 a 1100 rpm, dependendo do tipo de impelidor. A etapa 3 foi realizada com tipo de impelidor e intensidade de agitação definidos na etapa 2, mas variando-se o tamanho da biopartícula (0,5, 1,0, 2,0 e 3,0 cm de aresta). O objetivo desta etapa foi selecionar o tamanho de biopartícula que minimizasse a resistência à transferência de massa interna. De posse das condições operacionais otimizadas (tipo de impelidor, intensidade de agitação e tamanho de partícula de suporte), a etapa 4 constituiu na aplicação das mesmas para o tratamento de um resíduo real, sendo escolhida água residuária de suinocultura. Na etapa 1, os resultados mostraram que os tempos de mistura para todos os tipos de impelidores foram desprezíveis em relação ao tempo total de ciclo. A etapa 2 revelou tempos de partida muito curtos (cerca de 20 dias), em todas as condições testadas, sendo atingidas remoções de DQO próximas de 70%. Além disso, o tipo de impelidor exerceu grande influência na qualidade final do efluente, fato este claramente constatado quando as frações de DQO foram consideradas separadamente (filtrada e suspensa). De acordo com os resultados obtidos na etapa 3, o tamanho da biopartícula teve influência decisiva no desempenho do sistema, nas condições testadas. As velocidades de dissolução foram aparentemente influenciadas pelo empacotamento do leito de espuma, enquanto que o consumo da fração de DQO correspondente às amostras filtradas foi provavelmente influenciado por fatores mais complexos. Finalmente, o teste realizado com resíduo diluído de suinocultura demonstrou que a operação do reator em estudo para o tratamento deste tipo de água residuária é possível. Os dados operacionais mostraram que o reator permaneceu estável durante o período testado. A agitação mecânica provou ser eficiente para melhorar a degradação da DQO suspensa, um dos maiores problemas no tratamento deste tipo de água residuária. Sendo assim, de acordo com os dados experimentais obtidos ao longo do trabalho, pode-se afirmar que a agitação em reatores em batelada mostrou-se importante não somente para proporcionar boas condições de mistura ou melhorar a transferência de massa na fase líquida, mas também para melhorar a solubilização da matéria orgânica particulada, melhorando as velocidades de consumo de matéria orgânica. / The bench-scale anaerobic sequencing batch reactor containing immobilized biomass and provided with mechanical stirring employed in this work had total and useful volumes of 5.5 and 4.5 L, respectively. The biomass was immobilized on cubic polyurethane foam matrices, and the agitation of the liquid medium was provided by four types of impellers (propeller, flat-blade, pitched-blade and curved-blade turbines, individually tested, always in a set of three), with 6 cm of diameter. The research was divided into 4 experimental steps. The first one aimed at determining the mixing time in the reactor for each sort of impeller, i.e., the time necessary for the system to be completely homogeneized. As for the second step, its objective was to choose the sort of impeller and the agitation rate suitable for minimizing the external mass-transfer resistance. The agitation rates tests ranged from 200 to 1100 rpm, depending on the impeller type. The step 3 was carried out utilizing the chosen impeller and agitation rate, but varying the bioparticle size (0.5, 1.0, 2.0 and 3.0 cm of side). The aim of these experiments was to determine the bioparticle size that minimized the solid-phase mass transfer. Using these optimized operational conditions (type of impeller and bioparticle size), the step 4 consisted of the utilization of them in the treatment of a real wastewater (diluted swine manure). As for the results, step 1 showed the mixing times were very low compared to the total cycle times employed in the experiments (8 and 24 h). Very short start-up periods were revealed by the second experimental part (about 20 days in average) for all conditions tested, and the removal efficiencies reached approximately 70%. Besides that, the impeller type exerted great influence on the final quality of the effluent, fact clearly observed when the COD fractions were analyzed separately (filtered and suspended). According to the data obtained in the step 3, the bioparticle size influenced decisively on the performance of the system, in the conditions tested. The bed packing apparently influenced the dissolution rates, whereas the consumption of the COD correspondent to the filtered samples was defined by more complex factors. Finally, the test with the diluted swine manure demonstrated that the operation of this reactor with this type of wastewater is feasible, as the operational data showed the reactor remained stable during all the period tested. The mechanical stirring proved to be efficient to improve the degradation of the suspended COD, one of the major problems in the treatment of this type of wastewater. In this sense, according to the experimental data obtained in this work, it can be affirmed the mechanical stirring in anaerobic sequencing batch reactors showed to be not only important to provide good mixing conditions and improve the liquid phase mass transfer, but also to improve the solubilization of the particulate organic matter and increase the overall organic matter consumption rates.

As estruturas de dados concretas (cds) são quaternas (C, V, E, l-) que contêm um conjunto C de células, um conjunto V de valores, um conjunto E de eventos e uma relação de habilitação l-. O conjunto de estados de uma cds é um domínio concreto que pode ser considerada a parte "abstrata" das cds. Da mesma maneira tem-se que os domínios de eventos (que são generalizações dos domínios concretos) são a parte abstrata das estruturas de eventos. Mostra-se a relação dos domínios concretos e domínios de eventos com os espaços coerentes, assim como também das teias de espaços coerentes com as cds e estruturas de eventos. Intuitivamente, uma cds é uma teia de um espaço coerente se toda célula c de C não é habilitada por nenhum evento (ou equivalentemente, é habilitada pelo conjunto vazio), isto é, V C E C, 0 F c. Outra forma de expressar isto é dizer que uma cds e uma teia de um espaço coerente se o conjunto de estados da cds é um espaço coerente. Definem-se os algoritmos lineares como sendo estados de uma cds no estilo dos algoritmos seqüenciais do Curien ([CUR 86]). Em particular as cds consideradas são teias de espaços coerentes. Mostra-se como obter a cds !A—>B, a partir de uma função estável f. A —> B. O algoritmo linear desta cds possui todas as estratégias de computação (seqüenciais e paralelas) que computam a função subjacente f, o que implica que os algoritmos lineares podem ser considerados meta-algoritmos. Mostra-se que para toda estratégia de computação seqüencial de um algoritmo linear, existe um algoritmo seqüencial de Curien que computa a mesma função, e vice-versa. A definição de estratégia de computação é dada de maneira tal que permite se dar semântica a segmentos de programas. Define-se uma operação de composição de estratégias, de forma tal que se pode obter uma estratégia de computação de um programa, a partir da composição das estratégias dos segmentos. / The concrete data structures, or cds, (C, V, E, l-) consists of a set C of cells, a set V of values. a set E of events and an enabling relation l-. The set of states of a cds is a concrete domain, that can be considered the "abstract" counterpart of the cds. In the same way we have that the events domains (that are more general that the concretes domains) are the abstract counterpart of the events structures. We show the relation between the concretes domains and events domains with the coherence spaces, as just as the relation between the cds and events structures with webs of coherence spaces. Intuitivelly, a cds is a web of a coherence space if any cell c is not enabled for any event, i.e. Vce C, 0 F c. We can say that a cds is a web of a coherence space if the set of states of the cds is a coherence space. We define the linear algorithms as states of a cds following the Curien's sequential algorithms ([CUR 86]). In particular the cds considered are webs of coherence spaces. We show how to obtain a cds !A—>B from a stable function f. A —> B. The linear algorithm of this cds contain all the computational strategies (sequentials and parallels) that compute the subjacent function f; this implies that the linear algorithms can be considered a kind of meta-algorithms. We show that for all sequential computational strategy of a linear al gorithm exists a Curien's sequential algorithm that compute the same function and conversely. We define the computational strategies in such a way that we can give semantic of segments of programs. We define a composition operation for strategies. This operation has the advantage that we can obtain the computational strategy of a program as the composition of the segments of it.

Esta dissertação investiga a aplicação dos algoritmos evolucionários inspirados na computação quântica na síntese de circuitos sequenciais. Os sistemas digitais sequenciais representam uma classe de circuitos que é capaz de executar operações em uma determinada sequência. Nos circuitos sequenciais, os valores dos sinais de saída dependem não só dos valores dos sinais de entrada como também do estado atual do sistema. Os requisitos cada vez mais exigentes quanto à funcionalidade e ao desempenho dos sistemas digitais exigem projetos cada vez mais eficientes. O projeto destes circuitos, quando executado de forma manual, se tornou demorado e, com isso, a importância das ferramentas para a síntese automática de circuitos cresceu rapidamente. Estas ferramentas conhecidas como ECAD (Electronic Computer-Aided Design) são programas de computador normalmente baseados em heurísticas. Recentemente, os algoritmos evolucionários também começaram a ser utilizados como base para as ferramentas ECAD. Estas aplicações são referenciadas na literatura como eletrônica evolucionária. Os algoritmos mais comumente utilizados na eletrônica evolucionária são os algoritmos genéticos e a programação genética. Este trabalho apresenta um estudo da aplicação dos algoritmos evolucionários inspirados na computação quântica como uma ferramenta para a síntese automática de circuitos sequenciais. Esta classe de algoritmos utiliza os princípios da computação quântica para melhorar o desempenho dos algoritmos evolucionários. Tradicionalmente, o projeto dos circuitos sequenciais é dividido em cinco etapas principais: (i) Especificação da máquina de estados; (ii) Redução de estados; (iii) Atribuição de estados; (iv) Síntese da lógica de controle e (v) Implementação da máquina de estados. O Algoritmo Evolucionário Inspirado na Computação Quântica (AEICQ) proposto neste trabalho é utilizado na etapa de atribuição de estados. A escolha de uma atribuição de estados ótima é tratada na literatura como um problema ainda sem solução. A atribuição de estados escolhida para uma determinada máquina de estados tem um impacto direto na complexidade da sua lógica de controle. Os resultados mostram que as atribuições de estados obtidas pelo AEICQ de fato conduzem à implementação de circuitos de menor complexidade quando comparados com os circuitos gerados a partir de atribuições obtidas por outros métodos. O AEICQ e utilizado também na etapa de síntese da lógica de controle das máquinas de estados. Os circuitos evoluídos pelo AEICQ são otimizados segundo a área ocupada e o atraso de propagação. Estes circuitos são compatíveis com os circuitos obtidos por outros métodos e em alguns casos até mesmo superior em termos de área e de desempenho, sugerindo que existe um potencial de aplicação desta classe de algoritmos no projeto de circuitos eletrônicos. / This thesis investigates the application of quantum inspired evolutionary algorithms in the synthesis of sequential circuits. Sequential digital systems represent a class of circuit that is able to execute operations in a particular sequence. In sequential circuits, the values of output signals not only depend on the values of input signals but also on the current state of the system. The increasingly high requirements regarding the functionality and performance of digital systems demand more efficient designs. The design of these circuits, when implemented manually, became slow and thus the importance of tools for automatic synthesis of circuits grew rapidly. These tools known as ECAD (Electronic Computer-Aided Design) are computer programs usually based on heuristics. Recently, evolutionary algorithms also began to be used as a basis in ECAD tools developing. These applications are referenced in literature as evolutionary electronics. The algorithms most commonly used in evolutionary electronics are genetic algorithms and genetic programming. This work presents a study of the application of quantum inspired evolutionary algorithms as a tool for automatic synthesis of sequential circuits. This class of algorithms uses the principles of quantum computing to improve the performance of evolutionary algorithms. Traditionally, the design of sequential circuits is divided into five main steps: (i) State machine specification; (ii) Reduction of states; (iii) State assignment; (iv) Control logic synthesis and (v) Implementation of the state machine. The proposed algorithm AEICQ is used in the state assignment design step. The choice of an optimal state assignment is treated in the literature as an issue still unresolved. The state assignment chosen for a particular state machine has a direct impact on the complexity of its control logic. The results show that the state assignment obtained by AEICQ in fact leads to the implementation of circuits of less complexity when compared with the ones generated from assignments obtained by other methods. The AEICQ is also used in the control logic synthesis of the state machine. The circuits evolved by AEICQ are optimized according to the area occupied and the propagation delay. These circuits are compatible with the circuits obtained by other methods and in some cases even higher in terms of area and performance, suggesting that there is a potential for application of this class of algorithms in the design of electronic circuits.

As estruturas de dados concretas (cds) são quaternas (C, V, E, l-) que contêm um conjunto C de células, um conjunto V de valores, um conjunto E de eventos e uma relação de habilitação l-. O conjunto de estados de uma cds é um domínio concreto que pode ser considerada a parte "abstrata" das cds. Da mesma maneira tem-se que os domínios de eventos (que são generalizações dos domínios concretos) são a parte abstrata das estruturas de eventos. Mostra-se a relação dos domínios concretos e domínios de eventos com os espaços coerentes, assim como também das teias de espaços coerentes com as cds e estruturas de eventos. Intuitivamente, uma cds é uma teia de um espaço coerente se toda célula c de C não é habilitada por nenhum evento (ou equivalentemente, é habilitada pelo conjunto vazio), isto é, V C E C, 0 F c. Outra forma de expressar isto é dizer que uma cds e uma teia de um espaço coerente se o conjunto de estados da cds é um espaço coerente. Definem-se os algoritmos lineares como sendo estados de uma cds no estilo dos algoritmos seqüenciais do Curien ([CUR 86]). Em particular as cds consideradas são teias de espaços coerentes. Mostra-se como obter a cds !A—>B, a partir de uma função estável f. A —> B. O algoritmo linear desta cds possui todas as estratégias de computação (seqüenciais e paralelas) que computam a função subjacente f, o que implica que os algoritmos lineares podem ser considerados meta-algoritmos. Mostra-se que para toda estratégia de computação seqüencial de um algoritmo linear, existe um algoritmo seqüencial de Curien que computa a mesma função, e vice-versa. A definição de estratégia de computação é dada de maneira tal que permite se dar semântica a segmentos de programas. Define-se uma operação de composição de estratégias, de forma tal que se pode obter uma estratégia de computação de um programa, a partir da composição das estratégias dos segmentos. / The concrete data structures, or cds, (C, V, E, l-) consists of a set C of cells, a set V of values. a set E of events and an enabling relation l-. The set of states of a cds is a concrete domain, that can be considered the "abstract" counterpart of the cds. In the same way we have that the events domains (that are more general that the concretes domains) are the abstract counterpart of the events structures. We show the relation between the concretes domains and events domains with the coherence spaces, as just as the relation between the cds and events structures with webs of coherence spaces. Intuitivelly, a cds is a web of a coherence space if any cell c is not enabled for any event, i.e. Vce C, 0 F c. We can say that a cds is a web of a coherence space if the set of states of the cds is a coherence space. We define the linear algorithms as states of a cds following the Curien's sequential algorithms ([CUR 86]). In particular the cds considered are webs of coherence spaces. We show how to obtain a cds !A—>B from a stable function f. A —> B. The linear algorithm of this cds contain all the computational strategies (sequentials and parallels) that compute the subjacent function f; this implies that the linear algorithms can be considered a kind of meta-algorithms. We show that for all sequential computational strategy of a linear al gorithm exists a Curien's sequential algorithm that compute the same function and conversely. We define the computational strategies in such a way that we can give semantic of segments of programs. We define a composition operation for strategies. This operation has the advantage that we can obtain the computational strategy of a program as the composition of the segments of it.

Esta dissertação investiga a aplicação dos algoritmos evolucionários inspirados na computação quântica na síntese de circuitos sequenciais. Os sistemas digitais sequenciais representam uma classe de circuitos que é capaz de executar operações em uma determinada sequência. Nos circuitos sequenciais, os valores dos sinais de saída dependem não só dos valores dos sinais de entrada como também do estado atual do sistema. Os requisitos cada vez mais exigentes quanto à funcionalidade e ao desempenho dos sistemas digitais exigem projetos cada vez mais eficientes. O projeto destes circuitos, quando executado de forma manual, se tornou demorado e, com isso, a importância das ferramentas para a síntese automática de circuitos cresceu rapidamente. Estas ferramentas conhecidas como ECAD (Electronic Computer-Aided Design) são programas de computador normalmente baseados em heurísticas. Recentemente, os algoritmos evolucionários também começaram a ser utilizados como base para as ferramentas ECAD. Estas aplicações são referenciadas na literatura como eletrônica evolucionária. Os algoritmos mais comumente utilizados na eletrônica evolucionária são os algoritmos genéticos e a programação genética. Este trabalho apresenta um estudo da aplicação dos algoritmos evolucionários inspirados na computação quântica como uma ferramenta para a síntese automática de circuitos sequenciais. Esta classe de algoritmos utiliza os princípios da computação quântica para melhorar o desempenho dos algoritmos evolucionários. Tradicionalmente, o projeto dos circuitos sequenciais é dividido em cinco etapas principais: (i) Especificação da máquina de estados; (ii) Redução de estados; (iii) Atribuição de estados; (iv) Síntese da lógica de controle e (v) Implementação da máquina de estados. O Algoritmo Evolucionário Inspirado na Computação Quântica (AEICQ) proposto neste trabalho é utilizado na etapa de atribuição de estados. A escolha de uma atribuição de estados ótima é tratada na literatura como um problema ainda sem solução. A atribuição de estados escolhida para uma determinada máquina de estados tem um impacto direto na complexidade da sua lógica de controle. Os resultados mostram que as atribuições de estados obtidas pelo AEICQ de fato conduzem à implementação de circuitos de menor complexidade quando comparados com os circuitos gerados a partir de atribuições obtidas por outros métodos. O AEICQ e utilizado também na etapa de síntese da lógica de controle das máquinas de estados. Os circuitos evoluídos pelo AEICQ são otimizados segundo a área ocupada e o atraso de propagação. Estes circuitos são compatíveis com os circuitos obtidos por outros métodos e em alguns casos até mesmo superior em termos de área e de desempenho, sugerindo que existe um potencial de aplicação desta classe de algoritmos no projeto de circuitos eletrônicos. / This thesis investigates the application of quantum inspired evolutionary algorithms in the synthesis of sequential circuits. Sequential digital systems represent a class of circuit that is able to execute operations in a particular sequence. In sequential circuits, the values of output signals not only depend on the values of input signals but also on the current state of the system. The increasingly high requirements regarding the functionality and performance of digital systems demand more efficient designs. The design of these circuits, when implemented manually, became slow and thus the importance of tools for automatic synthesis of circuits grew rapidly. These tools known as ECAD (Electronic Computer-Aided Design) are computer programs usually based on heuristics. Recently, evolutionary algorithms also began to be used as a basis in ECAD tools developing. These applications are referenced in literature as evolutionary electronics. The algorithms most commonly used in evolutionary electronics are genetic algorithms and genetic programming. This work presents a study of the application of quantum inspired evolutionary algorithms as a tool for automatic synthesis of sequential circuits. This class of algorithms uses the principles of quantum computing to improve the performance of evolutionary algorithms. Traditionally, the design of sequential circuits is divided into five main steps: (i) State machine specification; (ii) Reduction of states; (iii) State assignment; (iv) Control logic synthesis and (v) Implementation of the state machine. The proposed algorithm AEICQ is used in the state assignment design step. The choice of an optimal state assignment is treated in the literature as an issue still unresolved. The state assignment chosen for a particular state machine has a direct impact on the complexity of its control logic. The results show that the state assignment obtained by AEICQ in fact leads to the implementation of circuits of less complexity when compared with the ones generated from assignments obtained by other methods. The AEICQ is also used in the control logic synthesis of the state machine. The circuits evolved by AEICQ are optimized according to the area occupied and the propagation delay. These circuits are compatible with the circuits obtained by other methods and in some cases even higher in terms of area and performance, suggesting that there is a potential for application of this class of algorithms in the design of electronic circuits.