Neste trabalho, desenvolve-se um algoritmo detector de PCDs - Plataformas de Coleta de Dados, primeira etapa do processo de regeneração a bordo, que possa ser utilizado nos satélites de coleta de dados da Missão Espacial Completa Brasileira - MECB. Os sistemas atuais utilizam busca no tempo dos vários sinais que chegam aleatoriamente ao receptor. A proposta é utilizar processamento digital de sinais para identificar, no domínio da freqüência, os sinais das PCDs e direcioná-los para os estágios seguintes de demodulação. Para isso, técnicas de estimação espectral foram estudas para se decidir quanto ao método de deteção mais adequado à aplicação. Foram levados em conta, nessa análise, não apenas o desempenho das técnicas de estimação, mas também a complexidade computacional e a capacidade de tratar, em tempo real, sinais com um número de PCDs desconhecido a priori; optando-se pela utilização do estimador direto constituído pelo periodograma com janela de dados temporal prolata de ordem zero. Em paralelo, foi desenvolvido um programa simulador e analisador de sinais, utilizado para avaliar o algoritmo de detecção desenvolvido. Finalmente, o algoritmo de detecção, com aplicação também nos detectores terrenos de PCDs, foi avaliado com sinais simulados e com sinais reais de PCDs,| recolhidos na estação de recepção de sinais de satélites do INPE, em Cuiabá.

Since the introduction of Data Warehouse (DW) and Online Analytical Processing (OLAP) technologies, efficient computation of data cubes has become one of the most relevant and pervasive problems in the DW area. The data cube operator has exponential complexity; therefore, the materialization of a data cube involves both huge amount of memory and substantial amount of time for its generation. Reducing the size of data cubes, without loss of generality, thus becomes one of the essential aspects for achieving effective OLAP services. Previous approaches reduce substantially the cube size using graph representations. A data cube can be viewed as a set of sub-graphs. In general, the approaches eliminate prefix redundancy and part of suffix redundancy of a data cube. In this work, we propose three major contributions to reduce the data cube size: MDAG, MCG and p-Cube Approaches. The MDAG approach eliminates the wildcard all (*), which represents an entire aggregation, from the cube representation, using the dimensional ID. It also uses the internal nodes to reduce the cube representation height, number of branches and number of common suffixed nodes. Unfortunately, the MDAG approach just reduces the data cube suffix redundancy, so in order to complete eliminate prefix/suffix redundancies we propose the MCG approach. The MCG approach produces a full cube with a reduction ratio of 70-90% when compared to a Star full cube representation. In the same scenarios, the new Star approach, proposed in 2007, reduces only 10-30%, Dwarf 30-50% and MDAG 40-60% of memory consumption when compared to Star approach. Our approaches are, on average, 20-50% faster than Dwarf and Star approaches. In this work, we also propose a parallel cube approach, named p-Cube. The p-Cube approach improves the runtime of Star, MDAG and MCG approaches, while keeping their low memory consumption benefits. The p-Cube approach uses an attribute-based data cube decomposition strategy which combines both task and data parallelism. It uses the dimensions attribute values to partition the data cube into a set of disjoint sub-cubes with similar size. The p-Cube approach provides similar memory consumption among its threads. Its logical design can be implemented in shared-memory, distributed-memory and hybrid architectures with minimal adaptation.

O problema de tratamento de valores ausentes em Mineração de Dados tem sido um desafio de pesquisa. O tratamento incorreto das ausências pode implicar prejuízo à qualidade e à validação dos resultados gerados no processo de Mineração. Uma forma de tratar esses dados é utilizar métodos de imputação, ou seja, o preenchimento dos dados através de dados estimados a partir das relações conhecidas dos dados reais. Assim, este trabalho propõe realizar vários experimentos de imputação de valores ausentes com a integração dos conceitos de imputação múltipla e composta com o objetivo de melhorar o desempenho baseado nos valores estimados para preenchimento. A abordagem desta pesquisa levou em consideração o tipo do conjunto de dados, características de distribuição destes dados, tipos e quantidade de atributos univariados e multivariados com valores ausentes, além de diferentes taxas de porcentagens e mecanismos de ausência de dados. O objetivo de inserir valores ausentes artificialmente em um conjunto completo foi permitir a avaliação da qualidade dos métodos de imputação a partir da relação dos valores imputados e dos valores originais eliminados. Aplicou-se o conceito de imputação composta para dinamizar e aperfeiçoar o processo de imputação. Para tanto foram usados dois métodos em conjunto: método de procedimentos baseados em imputação única, Hot Deck (visão estocástica) e Média (visão determinística); e método com procedimentos baseados em modelos, Estimativa de Densidade de Probabilidade, através do método do K-Vizinhos Mais Próximos (KNN). Comparou-se, conseqüentemente, com a imputação por Média e Máxima Verossimilhança, além do método de eliminação ListWise. Posteriormente, análises das qualidades das imputações realizadas são avaliadas através de medidas estatísticas, mostrando bom comportamento do método KNN no contexto geral de imputações.

Inicialmente este problema é enquadrado no contexto mais amplo de Corte e Empacotamento e uma forma exata de resolver o problema é apresentada. O problema é NP-'Arduo no sentido forte e extremamente difícil de ser resolvido na prática, por isso uma atenção especial aos algoritmos aproximativos e seus desempenhos, não poderia ser omitida. Como resultado, uma classe de algoritmos aproximativos (heurísticas e meta-heurísticas) foi desenvolvida e seus desempenhos avaliados com relação às heurísticas famosas. O procedimento para o preenchimento dos itens dentro dos bins utiliza o bem conhecido princípio da alocação em pontos de cantos. Os critérios para a estabilidade estática dos itens dentro dos bins são apresentados com detalhes. Uma abordagem distribuída também foi usada como forma de resolver o problema, com o intuito de diminuir o tempo de execução computacional dos algoritmos aproximativos que levam em conta a estabilidade estática dos itens dentro dos bins. Grande quantidade de experimentos computacionais são apresentados para problemas com até 90 itens (com e sem estabilidade estática) e os resultados são comparados com aqueles obtidos da literatura. Por último, foi sugerida algumas idéias para o direcionamento das futuras pesquisas sobre o problema.

Abordagens para computação de cubos de dados utilizando a estratégia de índices invertidos, tais como Frag-Cubing, são alternativas eficientes em relação às tradicionais abordagens para computação de cubos de dados com alta dimensionalidade, entretanto tais abordagens são limitadas pela memória principal (RAM) disponível. Neste trabalho, é apresentadado duas abordgens iniciais: qCube e H-Frag. qCube é uma extensão da abordagem Frag-Cubing que possibilita consultas de intervalo e H-Frag é uma abordagem que utiliza memória principal e memória externa a partir de definições do usuário. Com base nas abordagens iniciais, propomos duas outras que utilizam o sistema de memória composto por memória principal e memória externa, o qual chamamos de sistema híbrido de memória, para computar e manter atualizado cubos com alta dimensionalidade e elevado número de tuplas: HIC e bCubing. Em HIC, partições de cubos são armazenados em RAM e na memória externa utilizando a mesma representação de Frag-Cubing, contudo valores de atributos frequentes são armazenados em memória principal e valores de atributos pouco frequentes são armazenados em memória externa. HIC utiliza um parâmetro, chamado frequência acumulada crítica, para definir quais os valores de atributo são armazenados em memória principal ou em memória externa. bCubing particiona uma lista de identificadores de tuplas (TIDs) implementando a inversão de tuplas em dois níveis: um nível onde o identificador é o índice de bloco (BID) e o segundo nível onde o identificador é o índice da tupla (TID). As listas de TIDs dos valores de atributos são armazenadas em memória externa. As listas de BIDs são mantidas em memória principal e indexadas pelos valores de atributos. bCubing é capaz de calcular e manter atualizadas medidas holísticas de forma exata em cubos com alta dimensionalidade e elevado número de tuplas. Experimentos utilizando uma relação com 480 dimensões e 107 tuplas mostram que a abordagem bCubing é apenas 30% mais lenta do que Frag-Cubing para computação de cubos e aproximadamente 3 vezes mais rápida para responder consultas multidimensionais complexas a partir de tais relações. Um cubo massivo com 60 dimensões e 109 tuplas foi computado por bCubing usando 84 GB de RAM, enquanto o Frag-Cubing não computou tal cubo em uma máquina com 128 GB de RAM sem realizar operações de swap do sistema operacional. O impacto do cálculo de medidas holísticas em um cubo de dados com alta dimensionalidade também foi avaliado e os resultados demonstram que a abordagem bCubing gasta, em média, 10% mais tempo ao calcular medidas holísticas do que consultas com medidas COUNT. A abordagem bCubing respondeu consultas em um cubo de dados com 1.2 bilhões de tuplas em até 4 minutos, sendo uma destas consultas Q composta por dois operadores de subcubo e um operador EQUAL. A consulta Q calculou três medidas holísticas de forma exata: desvio padrão, mediana e moda.

Nesta tese apresentamos a abordagem da Mecânica Estatística para o clássico problema de otimização denominado problema da partição numérica (PPN), que é definido como: Dada uma seqüência de N números reais positivos {a1, a2, a3,....aN}, o problema consiste em particioná-los em dois conjuntos complementares, A e Ac, tais que o valor absoluto da diferença da soma dos ais nos dois conjuntos seja minimizada. No caso em que os aj\'s são variáveis aleatórias estatisticamente independentes distribuídas uniformemente no intervalo unitário, este problema NP-completo equivale ao problema de encontrar o estado fundamental de um modelo de Ising antiferromagnético aleatório de alcance infinito. Conseqüentemente, a análise probabilística do PPN pode ser realizada com as ferramentas da Mecânica Estatística de sistemas desordenados. Neste trabalho empregamos a aproximação recozida (annealed) para derivar uma expressão analítica para o limitante inferior do valor médio da diferença para partições tanto com vínculo de cardinalidade quanto sem vínculo para grandes valores de N. Além disso, calculamos analiticamente a fração de estados metaestáveis, isto é, estados que possuem a menor energia mediante todos os vizinhos (estados que diferem pela troca de um único spin). Concluímos a análise da abordagem direta, cujas instâncias . / In this thesis we present a statistical mechanics approach to a classical optimization problem called the number partitioning problem (NPP), which is stated as follows. Given a sequence of N positive real numbers , the number partitioning problem consists of partitioning them into two sets A and its complementary set Ac such that the absolute value of the difference of the sums of aj over the two sets is minimized. In each case in which the aj\'s are statistically independent random variables uniformly distributed in the unit interval, this NP-complete problem is equivalent to the problem of finding the ground state of an infinite range, random antiferromagnetic Ising model. Hence the probabilistic analysis of the NPP can be carried out within the framework of the standard statistical mechanics of disordered systems. In this vein we employ the annealed approximation to derive analytical lower bounds to the average value of the difference for the best-constrained and unconstrained partitions in the large N limit. Furthermore, we calculate analytically the fraction of metastable states, i.e. states that are stable against all single spin flips. We conclude the analysis of the so-called direct approach, in which the instances {ai} are fixed and the partitions are variable, with the analytical study of the linear programming relaxation of this NP-complete integer programming. In the second part of this thesis we propose and explore an inverse approach to the NPP, in which the optimal partitions are fixed and the instances are variable. Specifically, using the replica framework we study analytically the instance space of the number partitioning problem. We show that, regardless of the distribution of the instance entries, there is an upper bound &#945cN to the number of perfect random partitions (i.e. partitions for which that difference is zero). In particular, in the case where the two sets have the same cardinality (balanced partitions) we find &#945c =1/2. Moreover, in the case of unbalanced partitions, we show that perfect random partitions exist only if the difference between the cardinalities of the two sets scales like m N-1/2}.

A teoria dos grafos é uma ferramenta matemática muito utilizada na resolução de problemas algorítmicos e computacionais em que se quer modelar conjuntos de elementos e relações entre estes elementos. Sistemas naturais e tecnológicos de diversos domínios podem ser representados matematicamente por grafos que possuem propriedades estatísticas bem conhecidas, sendo uma destas propriedades a distribuição de graus dos vértices do grafo seguindo a lei de potência (power law). Exemplos destes grafos, conhecidos como grafos power law são a internet, World-Wide Web, as redes sociais, redes biológicas. No contexto de problemas algorítmicos em grafos, estamos interessados em problemas computacionalmente difíceis de serem resolvidos que pertencem à classe NP-Difícil (ou NP-Hard), mais especificamente no problema de cobertura por vértices. Neste trabalho será estudado experimentalmente o comportamento de um algoritmo baseado em uma estratégia gulosa para o problema de cobertura de vértices e compararemos com outro algoritmo de aproximação e com a solução exponencial ótima. Em particular esta solução será aplicada e analisada em redes complexas. / Graph theory is a mathematical tool used in solving many algorithmic and computational problems in that both sets of model elements and relationships between these elements. Most natural and technological systems can be mathematically modeled by graph having many well known properties, in particular the power law distribution of the vertex degree sequence. Examples of such graphs, called power law graphs are the Internet, World-Wide Web, social networks, biological networks. In the context of algorithmic problems on graphs, we are interested in problems in class NP-Hard, more specifically in the vertex cover problem. This work will be studied experimentally the behavior of an algorithm based on a greedy strategy for the vertex cover problem and compare with other approximation algorithms and with the exponential optimal solution. In particular this solution will be applied and analyzed in complex networks.

O método do gradiente conjugado, na sua forma geral, pode ser aplicado a um sistema de equações lineares algébricas Ax = b, quando A é autoadjunta e positiva definida em relação a um produto interno qualquer. As formas de recorrência de dois termos ou três, que fornecem uma aproximação da solução do sistema, independem do produto interno fixado no espaço universo. A generalidade teórica envolvida em tal contexto encontra-se, nesse trabalho, devidamente justificada. O precondicionamento e a sua relação com o produto interno utilizado, e o método para SELAS singulares e quase singulares também fazem parte da exposição. / The conjugated gradient method, in its general form, can be applied on an algebraic linear system Ax = b , when A is selfadjoint and positive definite with respect to an arbitrary inner product. The three-term recurrence form and the two-term one that give an approximation to the solution of the system do not depend on the inner product in the environment space. The theoretical generality involved in that context is properly justified in this dissertation. The preconditioning and its relationship with the relevant inner product and the conjugate gradient method for the singular and nearly singular systems are also part of this work.

[pt] A dissertação apresenta detalhadamente o algoritmo de fatoração de Shor, tanto em termos de sua execução passo a passo como mediante sua representação em forma de circuito, abordando aspectos tanto de sua parte clássica como de sua parte quântica. Inicialmente são apresentados aspectos de teoria dos números indispensáveis para a compreensão do algoritmo e em seguida são desenvolvidos conceitos e propriedades de mecânica quântica e de informação quântica pertinentes. Em atenção ao caráter eminentemente estocástico do algoritmo realiza-se um estudo de sua fonte estocástica e demonstram-se os principais teoremas que embasam a avaliação de sua probabilidade de sucesso. Desenvolvem-se exemplos de simulação clássica do algoritmo. Finalmente, a eficiência do algoritmo de fatoração de Shor é comparada com a de algoritmos clássicos. / [en] The dissertation presents in detail Shor s factoring algorithm, including its execution step by step and its representation in the form of a circuit, addressing aspects of both its classical and its quantum parts. Aspects of number theory indispensable to understand the algorithm are presented, followed by a development of concepts and properties of quantum mechanics and quantum information. Considering the eminently stochastic character of the algorithm, a study of its stochastic source is carried out and the main theorems that support the evaluation of its probability of success are proved. Examples of classical simulation of the algorithm are developed. Finally, the efficiency of Shor s factoring algorithm is compared with that of classical algorithms.

[pt] Com o desenvolvimento tecnológico no setor de telecomunicações, o espectro radioelétrico está quase totalmente ocupado com um grande número de múltiplas atribuições para os muitos serviços sem fio de aplicação comercial e, também, não comercial, tais como defesa, controle de tráfego aéreo e exploração científica. O espectro eletromagnético é um recurso natural precioso e escasso, por isso, importantes esforços estão sendo direcionados para o desenvolvimento de rádios cognitivos, com capacidade de sensoriar o uso do espectro e utilizar frequências momentaneamente disponíveis de forma oportunista. O rastreamento e a utilização de intervalos espectrais, ou white spaces, através da tecnologia de rádios cognitivos, permitirá aumentar a eficiência de uso do espectro com a introdução de novos serviços de telecomunicações a serem explorados por usuários secundários, obrigados a não interferir ou a provocar interferência muito limitada nos usuários primários. O objetivo geral deste trabalho é avaliar os principais algoritmos de detecção dos intervalos espectrais (Detector de Energia, Detecção do Valor Absoluto de Covariância, Sensoriamento de Covariância Espectral) por meio de simulações com dados experimentais obtidos em campanhas de medições e testes em laboratório. Os algoritmos foram testados para avaliar o seu desempenho em termos de probabilidade de detecção dada uma probabilidade de falso alarme requerida, complexidade computacional e robustez quanto a relações sinal-a-ruído baixas. Os dados experimentais utilizados provêm de campanhas de medidas realizadas em ambiente urbano na faixa de 3.5 GHz. / [en] With the technological development of the telecommunications industry, the radio spectrum is almost fully occupied with a large number of multiple assignments for wireless services for both commercial and non-commercial applications, such as defense, air traffic control and scientific exploration. The electromagnetic spectrum is a precious and scarce natural resource. Therefore, a considerable effort is being directed at the development of cognitive radios, capable of sensoring the spectrum and using momentarily available frequency bands in an opportunistic way. The tracking and using of these spectral intervals, or white spaces, using cognitive radio technology will enhance the efficiency of the spectrum use and allow the introduction of new telecommunications services to be exploited by secondary users, obliged not to interfere or produce very limited interference to primary users. The aim of this study is to evaluate the main algorithms for detection of spectral intervals (Energy Detector, Detection of Covariance Absolute Value, Spectral Covariance Sensing) through simulations with experimental data obtained in field measurements campaigns. The algorithms were tested to evaluate their performance in terms of detection probability given a required false alarm probability, computational complexity and robustness in low signal-to-noise conditions. The experimental data used comes from the measurements campaigns in urban environments at the 3.5 GHz band.