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.

Racionalidade imperfeita e inércia inflacionária : uma nova estimação da Curva de Phillips para o Brasil

O presente trabalho estima uma nova relação entre emprego e inflação para o Brasil, tendo como pano de fundo hipóteses propostas pelo arcabouço neo-keynesiano. Quatro hipóteses são testadas e sustentadas ao longo de todo o trabalho: i) os agentes não possuem racionalidade perfeita; ii) a imperfeição no processo de formação das expectativas dos agentes pode ser um fator determinante no componente inercial da inflação brasileira; iii) a inflação possui um componente inercial autônomo, que não depende de choques verificados em mercados isolados; e, iv) relações não-lineares entre inflação e desemprego são capazes de fornecer melhores explicações para o comportamento da economia nos últimos 12 anos. Enquanto as duas primeiras hipóteses são verificadas através de um modelo com mudanças markovianas, as duas últimas são testadas a partir da estimação de uma Curva de Phillips convexa, estimadas pelo Filtro de Kalman. Entretanto, mesmo fazendo uso destas estimativas, as funções de resposta da política monetária apresentam as mesmas propriedades de estimativas tradicionais para o Brasil.

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.

Estimação em classes de processos estocásticos com decaimento hiperbólico da função de autocorrelação

Neste trabalho analisamos processos estocásticos com decaimento polinomial (também chamado hiperbólico) da função de autocorrelação. Nosso estudo tem enfoque nas classes dos Processos ARFIMA e dos Processos obtidos à partir de iterações da transformação de Manneville-Pomeau. Os objetivos principais são comparar diversos métodos de estimação para o parâmetro fracionário do processo ARFIMA, nas situações de estacionariedade e não estacionariedade e, além disso, obter resultados similares para o parâmetro do processo de Manneville-Pomeau. Entre os diversos métodos de estimação para os parâmetros destes dois processos destacamos aquele baseado na teoria de wavelets por ser aquele que teve o melhor desempenho.

Estimação e previsão em processos com longa dependência sazonais

Neste trabalho analisamos alguns processos com longa dependência sazonais, denotados por SARFIMA(0,D, 0)s, onde s é a sazonalidade. Os estudos de estimação e previsão estão baseados em simulações de Monte Carlo para diferentes tamanhos amostrais e diferentes sazonalidades. Para estimar o parâmetro D de diferenciação sazonal utilizamos os estimadores propostos por Geweke e Porter-Hudak (1983), Reisen (1994) e Fox e Taqqu (1986). Para os dois primeiros procedimentos de estimação consideramos seis diferentes maneiras de compor o número de regressores necessários na análise de regressão, com o intuito de melhor comparar seus desempenhos. Apresentamos um estudo sobre previsão h-passos à frente utilizando os processos SARFIMA(0,D, 0)s no qual analisamos o erro de previsão, as variâncias teórica e amostral, o vício, o pervício e o erro quadrático médio.

Uma Arquitetura de Hardware para estimação de movimento aplicada à compressão de vídeo digital

A tarefa de estimação de movimento, utilizada na compressão de vídeo digital, é normalmente realizada em hardware por processador dedicado, uma vez que demanda expressiva capacidade computacional. Este trabalho propõe e desenvolve uma arquitetura de hardware para realizar o cálculo dos vetores de movimento no contexto de compressão de vídeo digital. Essa arquitetura para estimação de movimento é composta pelos blocos: interface de entrada e saída (E/S), matriz de processamento com 64 elementos de processamento, unidade de comparação e unidade de controle. A arquitetura foi descrita em linguagem VHDL de maneira que o número de bits utilizados para representação da luminância dos pontos é configurável. A partir desta descrição, foi gerado um protótipo para dados representados em 4 bits utilizando um kit de desenvolvimento baseado no dispositivo FPGA XC2S150 da Xilinx. Para validação do algoritmo e da arquitetura implementada, além da simulação, foi desenvolvido um software para plataforma PC capaz de exercitar as funcionalidades do protótipo. O PC é utilizado como dispositivo controlador de E/S para esta validação, na qual uma implementação do algoritmo em software e outra em linguagem de descrição de hardware são comparadas. A máxima freqüência de trabalho do protótipo, estimada por simulação da arquitetura mapeada no FPGA XC2S150, é de 33 MHz. A esta freqüência o núcleo da arquitetura paralela de 64 elementos de processamento realiza cerca de 2,1 GOps (bilhões de operações inteiras por segundo). Esta arquitetura de hardware calcula os vetores de movimento para vídeo no formato 640x480 pontos à taxa de 107,32 quadros por segundo, ou um quadro a cada 9,3 ms. A arquitetura implementada para luminânica em 4 bits ocupa 16 pinos de E/S, 71,1% dos blocos lógicos do FPGA e 83,3% dos blocos de memória disponíveis no dispositivo XC2S150.

Estimação e simulação dinâmica de um modelo econométrico para o mercado de alumínio no Brasil

O presente estudo pretende analisar o mercado brasileiro de alumínio primário, através da elaboração e simulação dinâmica de um modelo econométrico, com capacidade de explicar satisfatoriamente as relações típicas das variáveis econômicas consideradas neste mercado, conforme são postuladas pela teoria da empresa em competição imperfeita.

Estimação dos parâmetros das curvas IS e de Phillips da economia brasileira: 1994/2001

Neste trabalho comparamos as Curvas IS e de Phillips, derivadas a partir de modelos “tradicionais” e micro-fundamentados. Além disso, estimamos essas curvas para dados trimestrais brasileiros no período de 1994 a 2001. Na estimativa da IS foi usada a técnica de vetores de co-integração, já que esta curva é não balanceada – o hiato do produto é integrado de ordem zero e os regressandos são integrados de ordem um.

Estimação da volatilidade para hedge de carteiras de opções: um teste de eficiência

Neste trabalho compara-se diversos métodos de determinação da volatilidade de uma ação, quando a finalidade é tornar um dado spread de opções delta-neutro, usando o modelo de Black-Scholes. Os spreads são formados com o objetivo de gerar lucros de arbitragem, através de uma estratégia de exploração sistemática de distorções de volatilidades implícitas das opções de compra da Telebrás na BOVESPA, no período de Abril de 93 a Maio de 95. A comparação dos métodos é feita através de medidas da eficiência dos mesmos em hedgear os spreads formados. Nessas condições, conclui-se que a melhor maneira de tomar a carteira delta-neutra é usando para cada opção a sua respectiva volatilidade implícita. Além disso, verifica-se que teria sido possível, para um agente com baixos custos de transação, obter lucros substanciais com a estratégia de trading utilizada.

Estimação do preço hedônico: uma aplicação para o mercado imobiliário da cidade do Rio de Janeiro

O objetivo da dissertação foi obter um modelo de previsão para os preços dos imóveis, praticados no mercado imobiliário da cidade do Rio de Janeiro no ano 2000, utilizando a Metodologia do Preço Hedônico (HPM), que deve reponder a duas questões: a) Quais são as características relevantes; b) Qual é a forma de relacionamento entre os preços e as características. O modelo de previsão foi obtido, com base em procedimentos econométricos, e teve duas etapas distintas. Na primeira etapa, de formulação do modelo, foram realizadas regressões paras as formas funcionais mais utilizadas pelos estudos na área, a saber, a forma funcional linear, dupla logarítmica e semilogarítmica. Em seguida foi utilizado o procedimento de seleção de modelos “geral para específico”. A segunda etapa consistiu na previsão fora da amostra. Isto é, a partir das formas funcionais reduzidas e utilizando-se dos coeficientes das variáveis significativas, obteve-se os preços estimados e em seguida foram comparados com os preços efetivamente praticados pelo mercado. Calculou-se, então, os Erro Quadrático Médio (EQM) e o Erro Absoluto Médio (EAM) e com o auxílio dos testes de diagnósticos e igualdade de variância, escolheu-se a forma funcional que melhor se adequou aos dados Desta forma, para um nível de significância de 5%, a forma funcional que melhor se adequou aos critérios estabelecidos foi a dupla logarítmica e apresentou como resultado da estimação um R2=92,63% e dentre as características mais relevantes para estimação do preço do imóvel pode-se destacar, entre outras, o tamanho do imóvel como características físicas; a ocorrência de roubos como características de segurança, a quantidade disponível de bens e serviços destinados ao lazer como características de vizinhança e a disponibilidade ou não de serviços de hotelaria como características dummies.

Estimação da razão ótima de Hedge para o IBOVESPA futuro: uma aplicação do modelo Garch bivariado

Este estudo tem o objetivo de comparar várias técnicas que podem ser empregadas para proteger posições à vista usando mercados futuros. Partindo de uma posição na qual o investidor está à mercê do mercado, adota-se as técnicas mais simples de proteção até chegar a estimação da razão ótima de hedge ou de risco mínimo utilizando o modelo condicional, modelo no qual a variância é dependente do tempo. Para justificar a utilização da razão ótima de hedge dinâmica é introduzida a possibilidade de haver custo de transação. Os dados utilizados neste estudo são o preço à vista e preço de ajuste futuro do IBOVESPA do período 13/07/90 à 14/12/95.

Estimação de regressões aditivas via backfitting e integração marginal: performance em pequenas amostras

Nesta dissertação realizou-se um experimento de Monte Carlo para re- velar algumas características das distribuições em amostras finitas dos estimadores Backfitting (B) e de Integração Marginal(MI) para uma regressão aditiva bivariada. Está-se particularmente interessado em fornecer alguma evidência de como os diferentes métodos de seleção da janela hn, tais co- mo os métodos plug-in, impactam as propriedades em pequenas amostras dos estimadores. Está-se interessado, também, em fornecer evidência do comportamento de diferentes estimadores de hn relativamente a seqüência ótima de hn que minimiza uma função perda escolhida. O impacto de ignorar a dependência entre os regressores na estimação da janela é tam- bém investigado. Esta é uma prática comum e deve ter impacto sobre o desempenho dos estimadores. Além disso, não há nenhuma rotina atual- mente disponível nos pacotes estatísticos/econométricos para a estimação de regressões aditivas via os métodos de Backfitting e Integração Marginal. É um dos objetivos a criação de rotinas em Gauss para a implementação prática destes estimadores. Por fim, diferentemente do que ocorre atual- mente, quando a utilização dos estimadores-B e MI é feita de maneira completamente ad-hoc, há o objetivo de fornecer a usuários informação que permita uma escolha mais objetiva de qual estimador usar quando se está trabalhando com uma amostra finita.