Um método para abordar todo o ciclo de desenvolvimento de aplicações tempo real

Neste trabalho apresenta-se um método de desenvolvimento integrado baseado no paradigma de orientação a objetos, que visa abordar todo o ciclo de desenvolvimento de uma aplicação tempo real. Na fase de especificação o método proposto baseia-se no uso de restrições temporais padronizadas pelo perfil da UML-TR, sendo que uma alternativa de mapeamento destas restrições para o nível de programação é apresentada. Este mapeamento serve para guiar a fase de projeto, onde utilizou-se como alvo a interface de programação orientada a objetos denominada TAFT-API, a qual foi projetada para atuar junto ao ambiente de execução desenvolvido no âmbito desta tese. Esta API é baseada na especificação padronizada para o Java-TR. Este trabalho também discute o ambiente de execução para aplicações tempo real desenvolvido. Este ambiente faz uso da política de escalonamento tolerante a falhas denominada TAFT (Time-Aware Fault- Tolerant). O presente trabalho apresenta uma estratégia eficiente para a implementação dos conceitos presentes no escalonador TAFT, que garante o atendimento a todos os deadlines mesmo em situações de sobrecarga transiente. A estratégia elaborada combina algoritmos baseados no Earliest Deadline, sendo que um escalonador de dois níveis é utilizado para suportar o escalonamento combinado das entidades envolvidas. Adicionalmente, também se apresenta uma alternativa de validação dos requisitos temporais especificados. Esta alternativa sugere o uso de uma ferramenta que permite uma análise qualitativa dos dados a partir de informações obtidas através de monitoração da aplicação. Um estudo de caso baseado em uma aplicação real é usado para demonstrar o uso da metodologia proposta.

Modelamento paramétrico e geração de malha em superfícies para aplicações em engenharia

Este trabalho apresenta um conjunto de técnicas para a modelagem paramétrica e geração de malhas de superfícies para uso em sistemas de análise e simulações numéricas pelo Método dos Elementos Finitos. Foram desenvolvidos algoritmos para a geração paramétrica de superfícies, para a determinação das curvas de interseções entre superfícies e para a geração de malhas em superfícies curvas e recortadas. Foram implementas linhas e curvas paramétricas básicas, a partir das quais são geradas superfícies paramétricas de vários tipos que proporcionam uma grande flexibilidade de modelamento geométrico. Curvas e superfícies são geradas e manipuladas de forma interativa. São apresentadas técnicas que simplificam a implementação de linhas e superfícies paramétricas. Foi desenvolvido um algoritmo para determinar as curvas de interseção entre superfícies paramétricas, que são utilizadas como linhas de recorte (trimming lines) para obter geometrias complexas e compostas de várias superfícies. O algoritmo desenvolvido emprega técnicas de subdivisão adaptativa, por quadtrees, em função da curvatura local das superfícies. Primeiramente, obtém-se uma aproximação das curvas de interseção no espaço 3D, através da aproximação por triângulos. Os resultados iniciais são refinados e projetados sobre as duas superfícies envolvidas com algoritmos que permitem obter grande precisão. As curvas de interseção finais são mapeadas nos espaços paramétricos das duas superfícies, porém com uma parametrização única, o que facilita a junção com superfícies adjacentes Um algoritmo de geração de malha foi desenvolvido para gerar malhas triangulares de qualidade sobre as superfícies curvas e recortadas. O algoritmo utiliza um processo de subdivisão adaptativa por quadtrees, similar ao utilizado no algoritmo de interseção, para definir tamanhos de elementos em função da curvatura local. Em seguida, aplica-se um algoritmo tipo advancing front para gerar a malha sobre a superfície. Os algoritmos foram implementados e testados em um ambiente gráfico interativo especialmente desenvolvido para este trabalho. São apresentados vários exemplos que comprovam a eficiência das técnicas e algoritmos propostos, incluindo exemplos de matrizes de conformação mecânica para uso com código de análise METAFOR, análise de sensibilidade para otimização de pré-formas e de modelagem de superfícies compostas recortadas com geração de malhas de qualidade, para uso em análise por Elementos Finitos ou como contorno para geração de elementos tridimensionais.

Estudo teórico e experimental de um edifício alto submetido à ação dinâmica do vento

A crescente valorização dos imóveis nos centros de grandes cidades, com o custo do metro quadrado cada vez mais elevado, assim como o aprimoramento de técnicas e materiais construtivos, levaram a uma tendência mundial da construção de edificações altas. Contudo essas edificações altas, leves e esbeltas são suscetíveis a problemas dinâmicos, que podem levar a um comprometimento de confiabilidade das mesmas ou ao desconforto de seus usuários. Dentre as ações dinâmicas o vento trata-se de uma das mais importantes. A previsão da resposta induzida pela ação dinâmica do vento por métodos analíticos é complexa e de difícil resolução, principalmente para os efeitos transversais ao sentido da velocidade média do vento. Assim a construção de modelos aeroelásticos para a análise do comportamento dinâmico de edifícios altos em túnel de vento é, ainda hoje, a maneira mais confiável e precisa para chegar-se na resposta. Na presente dissertação é apresentado um estudo teórico e experimental de um edifício alto submetido a ação dinâmica do vento. As respostas obtidas em túnel de vento, através de um modelo aeroelástico equivalente de dois graus fundamentais de liberdade, são comparadas com as formulações da Norma Brasileira NBR - 6123, para a resposta longitudinal ao vento, e da Norma Canadense NBCC - 1985, para as respostas longitudinal e transversal ao vento.

Uma fundamentação teórica para a complexidade estrutural de problemas de otimização

Com o objetivo de desenvolver uma fundamentação teórica para o estudo formal de problemas de otimização NP-difíceis, focalizando sobre as propriedades estruturais desses problemas relacionadas à questão da aproximabilidade, este trabalho apresenta uma abordagem semântica para tratar algumas questões originalmente estudadas dentro da Teoria da Complexidade Computacional, especificamente no contexto da Complexidade Estrutural. Procede-se a uma investigação de interesse essencialmente teórico, buscando obter uma formalização para a teoria dos algoritmos aproximativos em dois sentidos. Por um lado, considera-se um algoritmo aproximativo para um problema de otimização genérico como o principal objeto de estudo, estruturando-se matematicamente o conjunto de algoritmos aproximativos para tal problema como uma ordem parcial, no enfoque da Teoria dos Domínios de Scott. Por outro lado, focaliza-se sobre as reduções entre problemas de otimização, consideradas como morfismos numa abordagem dentro da Teoria das Categorias, onde problemas de otimização e problemas aproximáveis são os objetos das novas categorias introduzidas. Dentro de cada abordagem, procura-se identificar aqueles elementos universais, tais como elementos finitos, objetos totais, problemas completos para uma classe, apresentando ainda um sistema que modela a hierarquia de aproximação para um problema de otimização NP-difícil, com base na teoria categorial da forma. Cada uma destas estruturas matemáticas fornecem fundamentação teórica em aspectos que se complementam. A primeira providencia uma estruturação interna para os objetos, caracterizando as classes de problemas em relação às propriedades de aproximabilidade de seus membros, no sentido da Teoria dos Domínios, enquanto que a segunda caracteriza-se por relacionar os objetos entre si, em termos de reduções preservando aproximação entre problemas, num ponto de vista externo, essencialmente categorial.

Contribuição à implementação da coordenação modular da construção no Brasil

A Coordenação Modular pode ser entendida como a ordenação dos espaços na construção civil. Surgiu entre a Primeira (1914-1918) e a Segunda (1939-1945) Guerras Mundiais e contribuiu de forma fundamental na reconstrução de edificações residenciais nos países destruídos pela guerra, principalmente na Alemanha, em função da rapidez e da redução de custos proporcionadas pela sua utilização. A partir de então, muitos estudos surgiram, aprofundando o assunto e mostrando os imensos benefícios que a Coordenação Modular trouxe para a racionalização e a industrialização na construção civil em um grande número de países, sendo amplamente difundida e, hoje se sabe, utilizada. O Brasil foi um dos pioneiros, em nível mundial, a aprovar uma norma de Coordenação Modular, a NB-25R, em 1950, tendo os anos 70 e início dos 80 tomados por seus conceitos e estudos a respeito. Apesar disso, poucos objetivos foram alcançados mesmo com toda a promoção para a racionalização da construção. As atuais preocupações com as questões ambientais, de produtividade e de redução de custos no setor são aliados para uma retomada dos estudos de Coordenação Modular, que se mostra como um fator fundamental para que se traga à construção civil os benefícios que a industrialização trouxe a outros setores industriais. Foi realizado um levantamento histórico, em que são abordadas as questões relativas ao uso do módulo na arquitetura e sua evolução até a Coordenação Modular, os princípios e conceitos mais importantes de sua teoria e as ações realizadas em favor de sua implantação no Brasil As últimas ações identificadas foram as normas publicadas em 1982, pouco antes do fechamento do Banco Nacional da Habitação, até então o principal incentivador da Coordenação Modular. Em seguida a esse hiato de duas décadas em que ficou praticamente esquecida, estudou-se a situação atual da indústria da construção civil sob alguns aspectos e partiu-se em busca do que pode ser feito para a implementação da Coordenação Modular no país. Chegou-se à conclusão de que, apesar dos entraves existentes, o Programa Brasileiro de Produtividade e Qualidade no Habitat (PBQP-H) mostra-se como um instrumento propício para essa implementação, pois, além de contar com o suporte estatal, tem influência sobre todos os intervenientes da cadeia produtiva.

Modelos para o mapeamento de aplicações em infra-estruturas de comunicação intrachip

O projeto de sistemas intrachip (SoCs) é uma atividade de alto grau de complexidade, dados a dimensão de SoCs, na ordem do bilhão de transistores, os requisitos de tempo de desenvolvimento e de consumo de energia, entre outros fatores. A forma de dominar a complexidade de projeto de SoCs inclui dividir a funcionalidade do sistema em módulos de menor complexidade, denominados de núcleos de propriedade intelectual (núcleos IP), interligados por uma infra-estrutura de comunicação. Enquanto núcleos IP podem ser reusados de outros projetos ou adquiridos de terceiros, a infra-estrutura de comunicação deve sempre ser desenvolvida de forma personalizada para cada SoC. O presente trabalho volta-se para o projeto de infraestruturas de comunicação eficientes. Questões importantes neste contexto são a eficiência da comunicação, refletida e.g. em medidas de vazão e latência, a redução de área de silício para implementar a comunicação, e a redução da energia consumida na comunicação. Estas questões dependem da escolha da infra-estrutura de comunicação. Barramentos são as infra-estruturas mais usadas nas comunicações intrachip, mas têm sido consideradas como pouco adequadas para servir a necessidade de comunicação de SoCs futuros. Redes intrachip vêm emergindo como um possível melhor candidato. Nesta infra-estrutura de comunicação, um problema a ser resolvido é o posicionamento relativo de núcleos IP dentro da rede, visando otimizar desempenho e reduzir o consumo de energia, no que se denomina aqui problema de mapeamento. Dada a complexidade deste problema, considera-se fundamental dispor de modelos para capturar as características da infra-estrutura de comunicação, bem como da aplicação que a emprega A principal contribuição deste trabalho é propor e avaliar um conjunto de modelos de computação voltados para a solução do problema de mapeamento de núcleos de propriedade intelectual sobre uma infra-estrutura de comunicação. Três modelos são propostos (CDM, CDCM e ECWM) e comparados, entre si e com três outros disponíveis na literatura (CWM, CTM e ACPM). Embora os modelos sejam genéricos, os estudos de caso restringem-se aqui a infra-estruturas de comunicação do tipo rede intrachip. Dada a diversidade de modelos de mapeamento, propõe-se uma segunda contribuição, o metamodelo Quantidade, Ordem, Dependência (QOD), que relaciona modelos de mapeamento usando os critérios expressos na denominação QOD. Considerando o alto grau de abstração dos modelos empregados, julga-se necessário prover uma conexão com níveis inferiores da hierarquia de projeto. Neste sentido, uma terceira contribuição original do presente trabalho é a proposta de modelos de consumo de energia e tempo de comunicação para redes intrachip. Visando demonstrar a validade de todos os modelos propostos, foram desenvolvidos métodos de uso destes na solução do problema de mapeamento, o que constitui uma quarta contribuição. Estes métodos incluem algoritmos de mapeamento, estimativas de tempo de execução, consumo de energia e caminhos críticos em infra-estruturas de comunicação. Como quinta contribuição, propõe-se o framework CAFES, que integra os métodos desenvolvidos e os modelos de mapeamento em algoritmos computacionais. Uma última contribuição do presente trabalho é um método habilitando a estimativa de consumo de energia para infra-estruturas de comunicação e sua implementação como uma ferramenta computacional.

Implementação de recuperação por retorno de aplicações distribuídas baseada em checkpoints coordenados

A recuperação por retorno baseada em checkpointing é largamente usada como técnica de tolerância a falhas. O modelo complexo de sistemas distribuídos tem motivado o desenvolvimento de diversos algoritmos na tentativa de encontrar soluções mais simples e eficientes. Os processos que formam o sistema distribuído podem coordenar suas operações para garantir que o conjunto de checkpoints locais componha um estado global consistente (linha de recuperação). A partir desse estado, no caso de ocorrência de falhas, o sistema pode ser recuperado e a computação retomada a partir de um momento anterior ao da manifestação da falha, evitando o retrocesso para o estado inicial da computação e prevenindo a ocorrência de prejuízos com a perda de todo processamento até então realizado. No Grupo de Tolerância a Falhas da UFRGS foi proposto recentemente um algoritmo que é voltado para aplicações que executam em sistemas distribuídos assíncronos que se comunicam exclusivamente pela troca de mensagens. Ele opera com salvamento coordenado de checkpoints (não bloqueando as aplicações) e prevê o tratamento de mensagens órfãs e perdidas. Os mecanismos do algoritmo sugerem que nenhuma alteração deveria ser realizada no código das aplicações, criando a possibilidade de implementação transparente sob o ponto de vista dos usuários e dos programadores das aplicações. Como o algoritmo não requer o bloqueio das aplicações, a sobrecarga imposta pelos mecanismos à execução livre de falhas é pequena. Além disso, o processo de recuperação tende a ser efetuado rapidamente, uma vez que é garantida a existência de uma linha de recuperação consistente, facilmente identificada Este trabalho apresenta as decisões de projeto, a implementação, os resultados e a avaliação de desempenho desse algoritmo. A avaliação das alternativas de implementação resultou na decisão de uma implementação então realizada diretamente sobre o sistema operacional Linux, sem recorrer a protocolos auxiliares para garantir a execução dos serviços e sem a necessidade de adaptações no código das aplicações nem no código do sistema operacional. Adicionalmente, os resultados comprovaram a expectativa inicial de que o algoritmo causaria pouca sobrecarga no sistema (menos de 2%), embora ele ainda apresente alta dependência do tamanho dos checkpoints salvos.

Avaliação do uso de guias sonoras como medida de redução de acidentes nas rodovias do Rio Grande do Sul

Nos últimos anos, os profissionais que atuam na área da engenharia rodoviária têm se dedicado à busca de tratamentos e soluções de engenharia que conduzam a melhores condições de segurança na malha viária. Entre as soluções de engenharia capazes de contribuir de forma efetiva para a segurança viária, estão as Guias Sonoras. As Guias Sonoras são ranhuras ou saliências que marcam o pavimento das rodovias alertando motoristas desatentos. Este trabalho teve por objetivo sistematizar os conhecimentos existentes sobre o uso de Guias Sonoras no país e no mundo, afim de divulgar um dispositivo de baixo custo e de simples aplicação e manutenção. O estudo aborda questões referentes ao custo do dispositivo, aos seus aspectos construtivos e à sua durabilidade, bem como o seu potencial na redução de acidentes. Foi realizada um ampla pesquisa bibliográfica e um estudo de caso. No estudo de caso realizado, buscou-se (a) verificar a existência de locais com características geométricas que resultam em uma maior propensão à ocorrência de acidentes do tipo saída de pista, principal evento evitável pelo uso das Guias Sonoras,e (b) comparar os custos de implantação do dispositivo com os custos dos acidentes evitáveis pelas Guias Sonoras. O estudo de caso mostrou que acidentes do tipo saída de pista representam aproximadamente 30% do total de acidentes de uma rodovia típica. Esse percentual é compatível com o verificado na revisão bibliográfica. A análise dos segmentos nos quais este tipo de acidente ocorria de forma mais freqüente revelou uma tendência à sua ocorrência em aclives/declives e/ou curvas. De acordo com o comparativo feito entre custos dos acidentes e custos de implantação de Guias Sonoras, o custo de um acidente apenas com feridos equivale à execução de 3,8 quilômetros de Guias Sonoras nos acostamentos da rodovia. Já, o custo de um acidente com vítima fatal equivale à execução de 31 quilômetros de Guias Sonoras. Adicionalmente, constatou-se que o investimento necessário para a implantação do dispositivo nos acostamentos do trecho analisado seria menor do que os custos de acidentes de saída de pista ocorridos no trecho no período de 3 anos.

As casas de Oscar Niemeyer - 1935-1955

A presente dissertação trata das casas projetadas pelo arquiteto Oscar Niemeyer, no período que compreende o início da sua carreira, em 1935, até a revisão autocrítica de 1955 – entre a Emergência e o final da Hegemonia da Arquitetura Moderna Brasileira. As 24 casas do período são apresentadas em ordem cronológica estudadas e analisadas individualmente, em paralelo ao conjunto de sua obra e considerando o contexto arquitetônico local e internacional. Contexto este especificamente representado pelos seus mestres confessos: Lucio Costa e Le Corbusier. As análises específicas de cada casa abordam: a sua motivação, o contexto histórico-cultural, os seus clientes, o lugar onde estão (ou estariam) e os seus aspectos compositivos, formais, funcionais e técnico-construtivos. O conjunto e contexto aparecem como suporte para a comparação, verificação de precedência, de influência, de renovação ou realimentação. Os resultados foram classificados, listados e quantificados afim de permitir futuros estudos sobre o tema. O trabalho procura também contribuir como meio de compilação, preservação e registro iconográfico desta parcela da obra de Niemeyer.

Desenvolvimento de um simulador genérico de processos dinâmicos

Simulador de processos é uma ferramenta valiosa, pois possibilita desde a validação de projetos e sua operabilidade prática até aumentos de produção e redução de custos. Devido a estes e outros fatores, o interesse industrial em técnicas e pacotes computacionais para a modelagem, simulação e otimização de processos tem crescido muito nos últimos anos. Juntamente com este interesse cresce a qualidade das ferramentas disponíveis no mercado para tal, mas estas ainda não satisfazem totalmente as expectativas de seus usuários. Este trabalho consiste no projeto de um novo simulador genérico para processos dinâmicos que satisfaça os usuários de forma mais completa do que os disponíveis atualmente no mercado. Para tanto, foram reunidas e, quando necessário, desenvolvidas novas técnicas relativas à descrição, análise e solução de problemas dinâmicos. Uma nova linguagem de modelagem orientada a objetos e um sistema de tradução da representação nesta linguagem para sistemas de equações foram propostos. Métodos de análise dos sistemas de equações provenientes da modelagem foram desenvolvidos com o intuito de auxiliar o usuário na detecção de erros de modelagem. Algoritmos para solução de sistemas dinâmicos e estacionários foram reunidos e uma arquitetura interna foi proposta. Por fim, o sistema como um todo foi testado através de sua aplicação em problemas típicos e outros que não podem ser resolvidos diretamente com os pacotes computacionais disponíveis no mercado. O teste com os problemas práticos provou que a estrutura proposta é adequada e apresenta uma série de vantagens quando comparada com softwares largamente utilizados na simulação de processos.

Aprendizado de máquina em sistemas complexos multiagentes : estudo de caso em um ambiente sob racionalidade limitada

O presente trabalho investiga a relação entre aprendizado e dinâmica em sistemas complexos multiagentes. Fazemos isso através de estudos experimentais em um cenário de racionalidade limitada que situa-se na interesecção entre Inteligência Artificial, Economia e Física Estatística, conhecido como “Minority Game”. Apresentamos resultados experimentais sobre o jogo focando o estudo do cenário sob uma perspectiva de Aprendizado de Máquina. Introduzimos um novo algoritmo de aprendizado para os agentes no jogo, que chamamos de aprendizado criativo, e mostramos que este algoritmo induz uma distribuição mais eficiente de recursos entre os agentes. Este aumento de eficiência mostra-se resultante de uma busca irrestrita no espaço de estratégias que permitem uma maximização mais eficiente das distâncias entre estratégias. Analisamos então os efeitos dos parâmetros deste algoritmo no desempenho de um agente, comparando os resultados com o algoritmo tradicional de aprendizado e mostramos que o algoritmo proposto é mais eficiente que o tradicional na maioria das situações. Finalmente, investigamos como o tamanho de memória afeta o desempenho de agentes utilizando ambos algoritmos e concluímos que agentes individuais com tamanhos de memória maiores apenas obtém um aumento no desempenho se o sistema se encontrar em uma região ineficiente, enquanto que nas demais fases tais aumentos são irrelevantes - e mesmo danosos - à performance desses agentes.

Automatic layout generation of static CMOS circuits targeting delay and power

The evolution of integrated circuits technologies demands the development of new CAD tools. The traditional development of digital circuits at physical level is based in library of cells. These libraries of cells offer certain predictability of the electrical behavior of the design due to the previous characterization of the cells. Besides, different versions of each cell are required in such a way that delay and power consumption characteristics are taken into account, increasing the number of cells in a library. The automatic full custom layout generation is an alternative each time more important to cell based generation approaches. This strategy implements transistors and connections according patterns defined by algorithms. So, it is possible to implement any logic function avoiding the limitations of the library of cells. Tools of analysis and estimate must offer the predictability in automatic full custom layouts. These tools must be able to work with layout estimates and to generate information related to delay, power consumption and area occupation. This work includes the research of new methods of physical synthesis and the implementation of an automatic layout generation in which the cells are generated at the moment of the layout synthesis. The research investigates different strategies of elements disposition (transistors, contacts and connections) in a layout and their effects in the area occupation and circuit delay. The presented layout strategy applies delay optimization by the integration with a gate sizing technique. This is performed in such a way the folding method allows individual discrete sizing to transistors. The main characteristics of the proposed strategy are: power supply lines between rows, over the layout routing (channel routing is not used), circuit routing performed before layout generation and layout generation targeting delay reduction by the application of the sizing technique. The possibility to implement any logic function, without restrictions imposed by a library of cells, allows the circuit synthesis with optimization in the number of the transistors. This reduction in the number of transistors decreases the delay and power consumption, mainly the static power consumption in submicrometer circuits. Comparisons between the proposed strategy and other well-known methods are presented in such a way the proposed method is validated.

Sistema para projeto de célula de manufatura : definição de agrupamentos

O entendimento da manufatura celular passa pelo estudo das rotas de fabricação e pelos métodos de agrupamento de máquinas e de peças. Neste contexto, o objetivo principal deste trabalho é a implemetação de uma ferramenta de auxílio ao projeto de células de manufatura, abordando uma metodologia fundamentada na Tecnologia de Grupo para agrupamento de máquinas em células de manufatura com as respectivas famílias de peças. A base de dados com as informações das peças, das máquinas e das rotas que compõe o fluxo de produção é implementada em um banco de dados relacional. A matriz incidência peça-máquina é montada a partir das rotas armazenadas no banco de dados através de um aplicativo desenvolvido em Visual Basic. Os agrupamentos em famílias de peças e células de manufatura são gerados por três diferentes algoritmos: o Rank Order Clustering (ROC), o Close Neighbor Algorithm (CNA) e um algoritmo heurístico (HEU). São aplicadas restrições referentes a limite de carregamento, tamanho de célula e resolução de situações de “gargalo”. Processados os algoritmos de agrupamento, são analisados os resultados em função da densidade e da eficiência do agrupamento. O sistema apresenta o resultado final em planilhas no formato MS Excel. A primeira planilha, chamada resultados, exibe os valores das restrições de projeto das células (número de máquinas por célula, tempo limite de carregamento e tempo limite para duplicação da máquina), o número de peças (colunas) e de máquinas (linhas) da matriz incidência, os valores de eficiência do agrupamento de peças, do agrupamento de máquinas e do aproveitamento dos recursos, bem como o número de células independentes e a quantidade de máquinas duplicadas, obtidos por cada algoritmo no sistema, destacando os melhores resultados. A segunda planilha mostra a matriz incidência peça-máquina. As demais planilhas apresentam, respectivamente, a matriz diagonalizada com o algoritmo original (ROC e CNA), a matriz diagonalizada levando-se em consideração as restrições de projeto das células (análise ROC, análise CNA e HEU) e por fim, uma planilha relatório. A planilha relatório tabula os mesmos valores citados na primeira planilha e lista as peças associadas a cada família, as máquinas associadas a cada célula, as peças rejeitadas, por não se enquadrarem nos agrupamentos, e que devem ser tratadas fora do ambiente celular e as máquinas duplicadas. A comparação dos resultados é efetuada considerando as características adicionadas aos algoritmos originais. Dos três estudados, as restrições de projeto são tratadas na implementação do HEU. Os demais, ROC e CNA, têm incorporado um pós processamento. Em análises comparativas observa-se a superioridade dos algoritmos ROC e HEU em relação ao CNA e os resultados do ROC são melhores ou iguais aos demais, dificilmente inferiores.

Análise da complexidade computacional de problemas de estatística descritiva com entradas intervalares

A Estatística é uma ferramenta indispensável em todos os campos científicos. A Estatística descritiva é usada para sintetizar dados. O principal problema desta área está relacionado aos valores de uma amostra, os quais geralmente possuem erros que ocorrem durante a obtenção dos dados. Um dos objetivos deste trabalho é apresentar uma forma de representação para os valores amostrais que considera os erros contidos nestes valores. Esta representação é realizada através de intervalos. A literatura mostra que foram realizadas pesquisas somente em problemas de calcular os valores intervalares das medidas de dispersão variância, covariância e coeficiente de correlação, que a utilização da computação intervalar na solução de problemas de medidas de dispersão intervalar sempre fornece solução com intervalos superestimados (intervalos com amplitude grande), e que ao procurar uma solução com intervalos de amplitude pequena (através da computação da imagem intervalar), o problema passa a pertencer a classe de problemas NP-Difícil. Com o objetivo principal de analisar a complexidade computacional dos problemas de computar os valores dos indicadores estatísticos descritivos com entradas intervalares, e realizar uma classificação quanto a classe de complexidade, a presente tese apresenta: i) definições intervalares de medidas de tendência central, medidas de dispersão e separatrizes; ii) investigação da complexidade de problemas das medidas de tendência central média, mediana e moda, das medidas de dispersão amplitude, variância, desvio padrão, coeficiente de variação, covariância, coeficiente de correlação e das separatrizes e iii) representação intervalar dos valores reais, de tal modo que garante a qualidade de aproximação nos intervalos solução calculado através da extensão intervalar Primeiramente, apresentamos uma abordagem intervalar para os indicadores estatísticos e propomos algoritmos para a solução dos problemas de computar os intervalos de medidas de tendência central intervalar, dispersão intervalar e separatrizes intervalares. Tais algoritmos utilizam a aritmética intervalar definida por Moore, a extensão intervalar e foram projetados para serem executados em ambientes intervalares como IntLab e Maple Intervalar. Por meio da análise da complexidade computacional verificamos que os problemas de medidas de tendência central, dispersão e separatrizes, com entradas intervalares, pertencem à classe de problemas P. Este trabalho apresenta, portanto, algoritmos de tempo polinomial que calculam os intervalos dos indicadores estatísticos com entradas intervalares, e que retornam como solução intervalos com qualidade de aproximação. Os resultados obtidos no desenvolvimento do trabalho tornaram viável a computação da Estatística Descritiva Intervalar.