Cálculo da complexidade exata de algoritmos do tipo divisão-e-conquista através das equações características

A equação de complexidade de um algoritmo pode ser expressa em termos de uma equação de recorrência. A partir destas equações obtém-se uma expressão assintótica para a complexidade, provada por indução. Neste trabalho, propõem-se um esquema de solução de equações de recorrência usando equações características que são resolvidas através de um "software" de computação simbólica, resultando em uma expressão algébrica exata para a complexidade. O objetivo é obter uma forma geral de calcular a complexidade de um algoritmo desenvolvido pelo método Divisão-e-Conquista.

Novos algoritmos para roteamento de circuitos VLSI

Este trabalho apresenta novos algoritmos para o roteamento de circuitos integrados, e discute sua aplicação em sistemas de síntese de leiaute. As interconexões têm grande impacto no desempenho de circuitos em tecnologias recentes, e os algoritmos propostos visam conferir maior controle sobre sua qualidade, e maior convergência na tarefa de encontrar uma solução aceitável. De todos os problemas de roteamento, dois são de especial importância: roteamento de redes uma a uma com algoritmos de pesquisa de caminhos, e o chamado roteamento de área. Para o primeiro, procura-se desenvolver um algoritmo de pesquisa de caminhos bidirecional e heurístico mais eficiente, LCS*, cuja aplicação em roteamento explora situações específicas que ocorrem neste domínio. Demonstra-se que o modelo de custo influencia fortemente o esforço de pesquisa, além de controlar a qualidade das rotas encontradas, e por esta razão um modelo mais preciso é proposto. Para roteamento de área, se estuda o desenvolvimento de uma nova classe de algoritmos sugerida em [JOH 94], denominados LEGAL. A viabilidade e a eficiência de tais algoritmos são demonstradas com três diferentes implementações. Devem ser também estudados mecanismos alternativos para gerenciar espaços e tratar modelos de grade não uniforme, avaliando-se suas vantagens e sua aplicabilidade em outros diferentes contextos.

Algoritmos para o posicionamento de células em circuitos VLSI

Este trabalho faz uma análise ampla sobre os algoritmos de posicionamento. Diversos são extraídos da literatura e de publicações recentes de posicionamento. Eles foram implementados para uma comparação mais precisa. Novos métodos são propostos, com resultados promissores. A maior parte dos algoritmos, ao contrário do que costuma encontrar-se na literatura, é explicada com detalhes de implementação, de forma que não fiquem questões em aberto. Isto só possível pela forte base de implementação por trás deste texto. O algorítmo de Fidduccia Mateyeses, por exemplo, é um algorítmo complexo e por isto foi explicado com detalhes de implementação. Assim como uma revisão de técnicas conhecidas e publicadas, este trabalho oferece algumas inovações no fluxo de posicionamento. Propõe-se um novo algorítimo para posicionamento inicial, bem como uma variação inédita do Cluster Growth que mostrta ótimos resultados. É apresentada uma série de evoluções ao algorítmo de Simulated Annealling: cálculo automático de temperatura inicial, funções de perturbação gulosas (direcionadas a força), combinação de funções de perturbação atingindo melhores resultados (em torno de 20%), otimização no cálculo de tamanho dos fios (avaliação das redes modificadas e aproveitamento de cálculos anteriores, com ganhos em torno de 45%). Todas estas modificações propiciam uma maior velocidade e convergência do método de Simulated Annealling. É mostrado que os algorítmos construtivos (incluindo o posicionador do Tropic, baseado em quadratura com Terminal Propagation) apresentam um resultado pior que o Simulated Annealling em termos de qualidade de posicionamento às custas de um longo tempo de CPD. Porém, o uso de técnicas propostas neste trabalho, em conjunto com outras técnicas propostas em outros trabalhos (como o trabalho de Lixin Su) podem acelerar o SA, de forma que a relação qualidade/tempo aumente.

ANAC : uma ferramenta para a automatização da análise da complexidade de algoritmos

A análise de um algoritmo tem por finalidade melhorar, quando possível, seu desempenho e dar condições de poder optar pelo melhor, dentre os algoritmos existentes, para resolver o mesmo problema. O cálculo da complexidade de algoritmos é muito dependente da classe dos algoritmos analisados. O cálculo depende da função tamanho e das operações fundamentais. Alguns aspectos do cálculo da complexidade, entretanto, não dependem do tipo de problema que o algoritmo resolve, mas somente das estruturas que o compõem, podendo, desta maneira, ser generalizados. Com base neste princípio, surgiu um método para o cálculo da complexidade de algoritmos no pior caso. Neste método foi definido que cada estrutura algorítmica possui uma equação de complexidade associada. Esse método propiciou a análise automática da complexidade de algoritmos. A análise automática de algoritmos tem como principal objetivo tornar o processo de cálculo da complexidade mais acessível. A união da metodologia para o pior caso, associada com a idéia da análise automática de programas, serviu de motivação para o desenvolvimento do protótipo de sistema ANAC, que é uma ferramenta para análise automática da complexidade de algoritmos não recursivos. O objetivo deste trabalho é implementar esta metodologia de cálculo de complexidade de algoritmos no pior caso, com a utilização de técnicas de construção de compiladores para que este sistema possa analisar algoritmos gerando como resultado final a complexidade do algoritmo dada em ordens assintóticas.

Algoritmos adaptativos para o método GMRES(m)

Nesse trabalho apresentamos algoritmos adaptativos do M´etodo do Res´ıduo M´ınimo Generalizado (GMRES) [Saad e Schultz, 1986], um m´etodo iterativo para resolver sistemas de equa¸c˜oes lineares com matrizes n˜ao sim´etricas e esparsas, o qual baseia-se nos m´etodos de proje¸c˜ao ortogonal sobre um subespa¸co de Krylov. O GMRES apresenta uma vers˜ao reinicializada, denotada por GMRES(m), tamb´em proposta por [Saad e Schultz, 1986], com o intuito de permitir a utiliza¸c˜ao do m´etodo para resolver grandes sistemas de n equa¸c˜oes, sendo n a dimens˜ao da matriz dos coeficientes do sistema, j´a que a vers˜ao n˜ao-reinicializada (“Full-GMRES”) apresenta um gasto de mem´oria proporcional a n2 e de n´umero de opera¸c˜oes de ponto-flutuante proporcional a n3, no pior caso. No entanto, escolher um valor apropriado para m ´e dif´ıcil, sendo m a dimens˜ao da base do subespa¸co de Krylov, visto que dependendo do valor do m podemos obter a estagna¸c˜ao ou uma r´apida convergˆencia. Dessa forma, nesse trabalho, acrescentamos ao GMRES(m) e algumas de suas variantes um crit´erio que tem por objetivo escolher, adequadamente, a dimens˜ao, m da base do subespa¸co de Krylov para o problema o qual deseja-se resolver, visando assim uma mais r´apida, e poss´ıvel, convergˆencia. Aproximadamente duas centenas de experimentos foram realizados utilizando as matrizes da Cole¸c˜ao Harwell-Boeing [MCSD/ITL/NIST, 2003], que foram utilizados para mostrar o comportamento dos algoritmos adaptativos. Foram obtidos resultados muito bons; isso poder´a ser constatado atrav´es da an´alise das tabelas e tamb´em da observa ¸c˜ao dos gr´aficos expostos ao longo desse trabalho.

Um Estudo de técnicas de aceleração para algoritmos de análise de timing funcional baseados em geração automática de teste

Este trabalho tem como objetivo estudar e avaliar técnicas para a aceleração de algoritmos de análise de timing funcional (FTA - Functional Timing Analysis) baseados em geração automática de testes (ATPG – Automatic Test Generation). Para tanto, são abordados três algoritmos conhecidos : algoritmo-D, o PODEM e o FAN. Após a análise dos algoritmos e o estudo de algumas técnicas de aceleração, é proposto o algoritmo DETA (Delay Enumeration-Based Timing Analysis) que determina o atraso crítico de circuitos que contêm portas complexas. O DETA está definido como um algoritmo baseado em ATPG com sensibilização concorrente de caminhos. Na implementação do algoritmo, foi possível validar o modelo de computação de atrasos para circuitos que contêm portas complexas utilizando a abordagem de macro-expansão implícita. Além disso, alguns resultados parciais demonstram que, para alguns circuitos, o DETA apresenta uma pequena dependência do número de entradas quando comparado com a dependência no procedimento de simulação. Desta forma, é possível evitar uma pesquisa extensa antes de se encontrar o teste e assim, obter sucesso na aplicação de métodos para aceleração do algoritmo.

Detecção de dano estrutural por algoritmos genéticos e sensibilidade modal

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

Formação de grupos colaborativos em um ambiente multiagente interativo de aprendizagem na internet : um estudo de caso utilizando sistemas multiagentes e algoritmos genéticos

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

Proposta de uma arquitetura especial para simulação lógica

O objetivo deste trabalho é a proposta de uma arquitetura especial para simulação lógica (AESL). As técnicas e modelos utilizados no processo de simulação lógica são brevemente revistos. É definida uma taxonomia para AESL sob a qual são analisadas diversas propostas de AESL relatadas na literatura. Uma taxonomia já existente é comparada com a proposta. A AESL definida é programável para diferentes algoritmos de simulação lógica. O detalhamento da AESL é, então, incrementado pela implementação de um algoritmo particular. Uma linguagem de simulação discreta é utilizada na construção de um modelo da arquitetura. Os resultados da simulação deste modelo permitem avaliar o desempenho da AESL e otimizar sua estrutura. Uma comparação com outras arquiteturas conclui a análise.

Dimensionamento de pilares esbeltos de concreto armado

O objetivo deste trabalho é o dimensionamento de pilares esbeltos de concreto armado, sob cargas de curta e longa duração, baseado numa análise realística das deformações do mesmo. Apresenta-se três algoritmos numéricos para a obtencão das relações momento fletor-esforço normal-curvatura de uma seção arbitrária de concreto armado, sob flexo-compressão normal. Inclue-se as deformações específicas de fluência e retração do concreto na análise, através de uma alteração nas referidas relações. Apresenta-se alguns critérios de normas, relativos ao dimensionamento de pilares esbeltos de concreto armado e uma comparação dos mesmos, entre si e com o algoritmo numérico desenvolvido. Considerações da NB-1/78 relativas ao projeto de pilares são analisadas, verificando o nivel da precisão obtida. Um procedimento simplificado para a inclusão da fluência do concreto no dimensionamento, proposto pelo CEB, é testado e uma solução para pilares de concreto armado com engastamento elástico simétrico é apresentada, para verificar o nível: do erro cometido ao se estender o conceito de comprimento de flambagem a pilares de concreto armado. Uma série de exemplos experimentais são apresentados, onde a solução numérica para o dimensionamento tem sua precisão verificada. Diversas tabelas foram desenvolvidas para o dimensionamento de pilares esbeltos com secão transversal retangular e armadura simétrica. Todo o estudo é restrito ao caso de flexo-compressão normal.

Paralelização de métodos de resolução de sistemas lineares esparsos com o DECK em um Cluster de PCs

O objetivo desta dissertação é a paralelização e a avaliação do desempenho de alguns métodos de resolução de sistemas lineares esparsos. O DECK foi utilizado para implementação dos métodos em um cluster de PCs. A presente pesquisa é motivada pela vasta utilização de Sistemas de Equações Lineares em várias áreas científicas, especialmente, na modelagem de fenômenos físicos através de Equações Diferenciais Parciais (EDPs). Nessa área, têm sido desenvolvidas pesquisas pelo GMC-PAD – Grupo de Matemática da Computação e Processamento de Alto Desempenho da UFRGS, para as quais esse trabalho vem contribuindo. Outro fator de motivação para a realização dessa pesquisa é a disponibilidade de um cluster de PCs no Instituto de Informática e do ambiente de programação paralela DECK – Distributed Execution and Communication Kernel. O DECK possibilita a programação em ambientes paralelos com memória distribuída e/ou compartilhada. Ele está sendo desenvolvido pelo grupo de pesquisas GPPD – Grupo de Processamento Paralelo e Distribuído e com a paralelização dos métodos, nesse ambiente, objetiva-se também validar seu funcionamento e avaliar seu potencial e seu desempenho. Os sistemas lineares originados pela discretização de EDPs têm, em geral, como características a esparsidade e a numerosa quantidade de incógnitas. Devido ao porte dos sistemas, para a resolução é necessária grande quantidade de memória e velocidade de processamento, característicos de computações de alto desempenho. Dois métodos de resolução foram estudados e paralelizados, um da classe dos métodos diretos, o Algoritmo de Thomas e outro da classe dos iterativos, o Gradiente Conjugado. A forma de paralelizar um método é completamente diferente do outro. Isso porque o método iterativo é formado por operações básicas de álgebra linear, e o método direto é formado por operações elementares entre linhas e colunas da matriz dos coeficientes do sistema linear. Isso permitiu a investigação e experimentação de formas distintas de paralelismo. Do método do Gradiente Conjugado, foram feitas a versão sem précondicionamento e versões pré-condicionadas com o pré-condicionador Diagonal e com o pré-condicionador Polinomial. Do Algoritmo de Thomas, devido a sua formulação, somente a versão básica foi feita. Após a paralelização dos métodos de resolução, avaliou-se o desempenho dos algoritmos paralelos no cluster, através da realização de medidas do tempo de execução e foram calculados o speedup e a eficiência. As medidas empíricas foram realizadas com variações na ordem dos sistemas resolvidos e no número de nodos utilizados do cluster. Essa avaliação também envolveu a comparação entre as complexidades dos algoritmos seqüenciais e a complexidade dos algoritmos paralelos dos métodos. Esta pesquisa demonstra o desempenho de métodos de resolução de sistemas lineares esparsos em um ambiente de alto desempenho, bem como as potencialidades do DECK. Aplicações que envolvam a resolução desses sistemas podem ser realizadas no cluster, a partir do que já foi desenvolvido, bem como, a investigação de précondicionadores, comparação do desempenho com outros métodos de resolução e paralelização dos métodos com outras ferramentas possibilitando uma melhor avaliação do DECK.

Uma Proposta de especificação formal e fundamentação teórica para simulated annealing

Os algoritmos baseados no paradigma Simulated Annealing e suas variações são atualmente usados de forma ampla na resolução de problemas de otimização de larga escala. Esta popularidade é resultado da estrutura extremamente simples e aparentemente universal dos algoritmos, da aplicabilidade geral e da habilidade de fornecer soluções bastante próximas da ótima. No início da década de 80, Kirkpatrick e outros apresentaram uma proposta de utilização dos conceitos de annealing (resfriamento lento e controlado de sólidos) em otimização combinatória. Esta proposta considera a forte analogia entre o processo físico de annealing e a resolução de problemas grandes de otimização combinatória. Simulated Annealing (SA) é um denominação genérica para os algoritmos desenvolvidos com base nesta proposta. Estes algoritmos combinam técnicas de busca local e de randomização. O objetivo do presente trabalho é proporcionar um entendimento das características do Simulated Annealing e facilitar o desenvolvimento de algoritmos com estas características. Assim, é apresentado como Simulated Annealing e suas variações estão sendo utilizados na resolução de problemas de otimização combinatória, proposta uma formalização através de um método de desenvolvimento de algoritmos e analisados aspectos de complexidade. O método de desenvolvimento especifica um programa abstrato para um algoritmo Simulated Annealing seqüencial, identifica funções e predicados que constituem os procedimentos deste programa abstrato e estabelece axiomas que permitem a visualização das propriedades que estes procedimentos devem satisfazer. A complexidade do Simulated Annealing é analisada a partir do programa abstrato desenvolvido e de seus principais procedimentos, permitindo o estabelecimento de uma equação genérica para a complexidade. Esta equação genérica é aplicável aos algoritmos desenvolvidos com base no método proposto. Uma prova de correção é apresentada para o programa abstrato e um código exemplo é analisado com relação aos axiomas estabelecidos. O estabelecimento de axiomas tem como propósito definir uma semântica para o algoritmo, o que permite a um desenvolvedor analisar a correção do código especificado para um algoritmo levando em consideração estes axiomas. O trabalho foi realizado a partir de um estudo introdutório de otimização combinatória, de técnicas de resolução de problemas, de um levantamento histórico do uso do Simulated Annealing, das variações em torno do modelo e de embasamentos matemáticos documentados. Isto permitiu identificar as características essenciais dos algoritmos baseados no paradigma, analisar os aspectos relacionados com estas características, como as diferentes formas de realizar uma prescrição de resfriamento e percorrer um espaço de soluções, e construir a fundamentação teórica genérica proposta.

Geração de sombras em objetos modelados por geometria sólida construtiva

Atualmente os sistemas computacionais mais sofisticados são aqueles que apresentam imagens gráficas. Devido às características de alta velocidade de processamento e excelente resultado na geração de imagens o uso da Computação Gráfica se dá em diversas áreas como a indústria, pesquisa, publicidade, entretenimento, medicina, treinamento, dentre outras. Este trabalho aborda dois assuntos clássicos na Computação Gráfica, Geometria Sólida Construtiva (CSG) e Sombras Projetadas. Ambos são muito importantes para esta linha de pesquisa da Ciência da Computação. A Geometria Sólida Construtiva é utilizada na modelagem de objetos e as sombras projetadas são necessárias para aumentar o realismo das imagens. Geometria sólida construtiva (CSG) é uma técnica para a modelagem de sólidos, que define sólidos complexos pela composição de sólidos simples (primitivas). Isso inclui também a composição de objetos já combinados, até que se chegue a um objeto mais complexo. Um fator muito importante e necessário na obtenção de imagens realistas e que deve ser considerado é a utilização de sombras, pois estas são eficazes no realismo e impressão espacial de objetos tridimensionais. As sombras estabelecem diversos níveis de profundidade na imagem, fazem uma pontuação geométrica na cena de modo a evitar que os objetos não pareçam estar flutuando no ar. Este trabalho consiste em apresentar uma proposta para a geração de sombras em objetos modelados pela Geometria Sólida Construtiva. Para tanto foram estudados os assuntos referentes à modelagem de objetos por CSG, algoritmos para a geração de sombras “bem delimitadas” e formas de gerar sombras na Geometria Sólida Construtiva. O processo de geração de sombras em cenas modeladas por CSG, através da aplicação das mesmas operações booleanas envolvidas na modelagem dos objetos, sobre as sombras nem sempre apresenta resultados corretos. Diante disso, foram investigadas outras formas de solucionar o problema. Dentre estas, uma alternativa é a realização de transformações na árvore binária CSG, através de outras operações, envolvendo o uso de complemento com operações de união e interseção, para a modelagem do objeto e geração da sombra correspondente. Com base nos estudos realizados foram implementados dois protótipos que exibem a sombra projetada de objetos modelados por CSG. Na implementação do protótipo A utilizaram-se as técnicas tradicionais de modelagem de sólidos e sombra projetada. Os resultados obtidos com este protótipo serviram de referência. No protótipo B os resultados foram obtidos através da aplicação da zona ativa das primitivas na modelagem dos objetos e a sombra é projetada durante o processo de avaliação de contornos do sólido. Os resultados obtidos com este protótipo são comparados com os resultados do protótipo A e são apresentados como forma de exibir a aplicação do método proposto.

Representação na forma normal disjuntiva para a flexibilidade de seqüência na manufatura

A crescente demanda por produtos de melhor qualidade, diferenciados e com custos competitivos tem forçado as manufaturas a se tornarem flexíveis, capacitando-as a responder às mudanças impostas pelo mercado. A flexibilidade permite que as empresas alcancem a customização desejada através da capacitação do sistema de responder e atuar em tempo real, mesmo em um ambiente de incertezas. Para atuar em tempo real, os sistemas de manufatura precisam de representações eficientes dos planos de produção. Muitas vezes, a atuação em tempo real torna-se inviável devido ao crescimento exponencial no número de planos de produção para cada máquina ou operação adicionada ao sistema. Uma possível solução para este problema é uso de representações adequadas para o espaço de estados. A escolha de uma representação adequada para o espaço de estados influencia na capacidade de reposta em tempo real, pois determina o desempenho computacional do sistema através da utilidade e eficiência dos algoritmos desenvolvidos, tornando possível explorar problemas clássicos de flexibilidade, tais como, seqüenciamento, otimização, etc. Entretanto, a geração de uma representação que trabalhe com o espaço de estados completo de uma manufatura é considerada um problema não polinomial (NP). Esta particularidade dificulta o desenvolvimento de algoritmos que trabalhem com uma manufatura flexível. Assim, a geração de uma representação, que trabalhe com pouca memória computacional e permita o desenvolvimento de heurísticas eficientes, é um importante desafio para uma avaliação efetiva da flexibilidade. Este trabalho objetiva o desenvolvimento de uma representação para o espaço de estados de uma manufatura com flexibilidade de seqüência. Na construção desta representação são aplicadas técnicas de modelagem baseadas na teoria dos grafos e nos princípios de álgebra booleana. Inicialmente, os grafos são utilizados para representar todas as seqüências de operações de uma manufatura, posteriormente estas seqüências são convertidas em formas normais disjuntivas (FND). Por fim, é apresentada uma possível aplicação da representação na FND em modelos de programação linear.