There are several approaches for creating double-ended heaps from the single-ended heaps. We build on one of them, the leaf correspondence heap, to create a generic double ended heap scheme called L-correspondence heap. This will broaden the class of eligible base single-ended heaps (e.g. by Fibonacci heap, Rank-pairing heap) and make the operations Decrease and Increase possible. We show this approach on specific examples for three different single-ended base heaps and give time complexity bounds for all operations. Another result is that for these three examples, the expected amortized time for Decrease and Increase operations in the L-correspondence heap is bounded by a constant.

Submitted by Roberto Fonseca (rcf2@icomp.ufam.edu.br) on 2018-11-18T00:36:14Z No. of bitstreams: 2 rcidadef-final-dissertacao-mestrado.pdf: 998750 bytes, checksum: 1738deb5326e881be7192f444ccedb86 (MD5) 315 ATA de Defesa - Roberto Cidade (Assinada).pdf: 531920 bytes, checksum: 51157459356b7ee8be9be278b4579378 (MD5) / Approved for entry into archive by Secretaria PPGI (secretariappgi@icomp.ufam.edu.br) on 2018-11-19T17:31:42Z (GMT) No. of bitstreams: 2 rcidadef-final-dissertacao-mestrado.pdf: 998750 bytes, checksum: 1738deb5326e881be7192f444ccedb86 (MD5) 315 ATA de Defesa - Roberto Cidade (Assinada).pdf: 531920 bytes, checksum: 51157459356b7ee8be9be278b4579378 (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2018-11-19T19:46:24Z (GMT) No. of bitstreams: 2 rcidadef-final-dissertacao-mestrado.pdf: 998750 bytes, checksum: 1738deb5326e881be7192f444ccedb86 (MD5) 315 ATA de Defesa - Roberto Cidade (Assinada).pdf: 531920 bytes, checksum: 51157459356b7ee8be9be278b4579378 (MD5) / Made available in DSpace on 2018-11-19T19:46:24Z (GMT). No. of bitstreams: 2 rcidadef-final-dissertacao-mestrado.pdf: 998750 bytes, checksum: 1738deb5326e881be7192f444ccedb86 (MD5) 315 ATA de Defesa - Roberto Cidade (Assinada).pdf: 531920 bytes, checksum: 51157459356b7ee8be9be278b4579378 (MD5) Previous issue date: 2018-08-28 / Machine learning (ML) based ranking functions generating methods have been broadly used on web search systems, such as the utilized by Google and Bing. Nonetheless, such methods have not been employed or studied in other contexts. It is the case, to cite an example, of electronic commerce (e-commerce), on which the user interaction with virtual stores produces data as: when an user landed on a page for the first time, queries submitted, products clicked and what she bought. In this work, we propose to leverage ML to learn ranking functions for the e-commerce context. We studied alternatives to estimate the relevance of a result for a given query and deployed experiments using data mined from e-commerce shops. We ran experiments in setups we denominated offline, where a dataset was created the traditional way by separating it in three subsets of training, validation and test, as well as in setups we denominated online, where distinct versions of the system were deployed to shops facing users in a real purchase situation. We present in the study our conclusions regarding the performed experiments. / Métodos que geram funções de ordenação de resultados baseadas em aprendizagem de máquina têm sido amplamente utilizados em sistemas de busca para a web, como as utilizadas em motores de busca como o Google e Bing. No entanto, esses recursos não têm sido muito empregados ou estudados em outros contextos. É o caso, por exemplo, do comércio eletrônico, no qual, a interação de usuários com lojas virtuais produz dados como: quando um usuário acessou a página de uma loja pela primeira vez, que consultas realizou, quais produtos clicou, e o que comprou. Neste trabalho, propomos a utilização de métodos de aprendizagem de máquina para aprender funções de ordenação de resultados no contexto de comércio eletrônico. Estudamos formas alternativas de estimar a relevância de um resultado para uma dada consulta e realizamos experimentos utilizando dados extraídos de lojas de comércio eletrônico. Realizamos experimentos tanto com ambientes que denominamos offline, onde uma base de dados é montada com a abordagem tradicional de separa-la em treino, validação e teste, quanto em ambientes que denominamos online, onde pusemos versões distintas dos sistemas para funcionar em lojas com usuários em situações reais de compra. Apresentamos no estudo nossas conclusões a respeito dos experimentos realizados. / Formulário longo, com várias fases e páginas.

Este trabalho avalia o desempenho do uso de árvores de decisão como função de ordenação para documentos e pessoas em ambientes empresariais. Para tanto, identificouse atributos relevantes das entidades a serem recuperadas a partir da análise de: (i) dinâmica de produção e consumo de informações em um ambiente empresarial; (ii) algoritmos existentes na literatura para a recuperação de documentos e pessoas; e (iii) conceitos utilizados em funções de ordenação para domínios genéricos. Montou-se um ambiente de avaliação, utilizando a coleção de referência CERC, para avaliar a aplicabilidade do algoritmo C4.5 na obtenção de funções de ordenação para o domínio empresarial. O uso do algoritmo C4.5 para a construção de funções de ordenação mostrou-se parcialmente efetivo. Para a tarefa de recuperação de documentos não trouxe resultados bons. Porém, constatou-se que é possível controlar a forma de construção da função de ordenação a fim de otimizar a precisão nas primeiras posições do ranking ou otimizar a média das precisões (MAP). Para a tarefa de recuperação de pessoas o algoritmo C4.5 obteve uma árvore de decisão que consegue resultados melhores que todas as outras funções de ordenação avaliadas. OMAP obtido pela árvore de decisão foi 0, 83, enquanto que a média do MAP das outras funções de ordenação foi de 0, 74. Percebeu-se que a árvore de decisão utilizada para representar a função de ordenação contribui para a compreensão da composição dos diversos atributos utilizados na caracterização dos documentos e pessoas. A partir da análise da árvore de decisão utilizada como função de ordenação para pessoas foi possível entender que uma pessoa é considerada especialista em algum tópico se ela aparecer em muitos documentos, aparecer muitas vezes nos documentos e os documentos onde aparece têm uma relevância alta para a consulta. / This work evaluates the performance of using decision trees as ranking functions for documents and people in enterprises. It was identified relevant attributes of the entities to be retrieved from the analysis of: (i) the production and consumption of information behavior in an enterprise, (ii) algorithms for documents and people retrieval at literature, and (iii) the concepts used in ranking functions for generic domains. It was set up an evaluation environment, using the CERC collection, to evaluate the applicability of the C4.5 algorithm to obtain a ranking function for the enterprise domain. The use of C4.5 algorithm for the construction of ranking function was proved to be partially effective. In the case of documents retrieval the C4.5 has not found good results. However, it was found that is possible to control the way of building the ranking function in order to optimize the precision in the first positions of the ranking or optimize the mean average precision (MAP). For the task of people retrieval the C4.5 algorithm developed a ranking function that obtain better results than all other ranking functions assessed. The value of MAP obtained by decision tree was 0, 83, while the average MAP of other ranking functions was 0, 74. The decision tree used to represent the ranking function contributes to understanding the attributes composition used in the characterization of documents and people. Through the analysis of the decision tree used as ranking function for people, we could realise that a person is considered expert in any topic if he/she appear in many documents, appear many times in same documents and documents where he/she appears have a high relevance to the query.

In this dissertation, we investigate four distinct and interrelated problems for high-dimensional inference of mean vectors in multi-groups. The first problem concerned is the profile analysis of high dimensional repeated measures. We introduce new test statistics and derive its asymptotic distribution under normality for equal as well as unequal covariance cases. Our derivations of the asymptotic distributions mimic that of Central Limit Theorem with some important peculiarities addressed with sufficient rigor. We also derive consistent and unbiased estimators of the asymptotic variances for equal and unequal covariance cases respectively. The second problem considered is the accurate inference for high-dimensional repeated measures in factorial designs as well as any comparisons among the cell means. We derive asymptotic expansion for the null distributions and the quantiles of a suitable test statistic under normality. We also derive the estimator of parameters contained in the approximate distribution with second-order consistency. The most important contribution is high accuracy of the methods, in the sense that p-values are accurate up to the second order in sample size as well as in dimension. The third problem pertains to the high-dimensional inference under non-normality. We relax the commonly imposed dependence conditions which has become a standard assumption in high dimensional inference. With the relaxed conditions, the scope of applicability of the results broadens. The fourth problem investigated pertains to a fully nonparametric rank-based comparison of high-dimensional populations. To develop the theory in this context, we prove a novel result for studying the asymptotic behavior of quadratic forms in ranks. The simulation studies provide evidence that our methods perform reasonably well in the high-dimensional situation. Real data from Electroencephalograph (EEG) study of alcoholic and control subjects is analyzed to illustrate the application of the results.

Coronary artery disease (CAD) is one of the leading causes of death in the world. In the United States alone, it is estimated that approximately every 25 seconds, a new CAD event will occur, and approximately every minute, someone will die of one. The detection of CAD during in its early stages is very critical to reduce the mortality rates. Magnetic resonance imaging of myocardial perfusion (MR-MPI) has been receiving significant attention over the last decade due to its ability to provide a unique view of the microcirculation blood flow in the myocardial tissue through the coronary vascular network. The ability of MR-MPI to detect changes in microcirculation during early stages of ischemic events makes it a useful tool in identifying myocardial tissues that are alive but at the risk of dying. However this technique is not yet fully established clinically due to fundamental limitations imposed by the MRI device physics. The limitations of current MRI schemes often make it challenging to simultaneously achieve high spatio-temporal resolution, sufficient spatial coverage, and good image quality in myocardial perfusion MRI. Furthermore, the acquisitions are typically set up to acquire images during breath holding. This often results in motion artifacts due to improper breath hold patterns. This dissertation deals with developing novel image reconstruction methods in conjunction with non-Cartesian sampling for the reconstruction of dynamic MRI data from highly accelerated / under-sampled Fourier measurements. The reconstruction methods are based on adaptive signal models to represent the dynamic data using few model coefficients. Three novel adaptive reconstruction methods are developed and validated: (a) low rank and sparsity based modeling, (b) blind compressed sensing, and (c) motion compensated compressed sensing. The developed methods are applicable to a wide range of dynamic imaging problems. In the context of MR-MPI, this dissertation show feasibilities that the developed methods can enable free breathing myocardial perfusion MRI acquisitions with high spatio-temporal resolutions ( < 2mm x 2mm, 1 heart beat) and slice coverage (upto 8 slices).

Efficient receiver designs for cooperative communication networks are becoming increasingly important. In previous work, cooperative networks communicated with the use of L relays. As the receiver is constrained, channel shortening and reduced-rank techniques were employed to design the preprocessing matrix that reduces the length of the received vector from L to U. In the first part of the work, a receiver structure is proposed which combines our proposed threshold selection criteria with the joint iterative optimization (JIO) algorithm that is based on the mean square error (MSE). Our receiver assists in determining the optimal U. Furthermore, this receiver provides the freedom to choose U for each frame depending on the tolerable difference allowed for MSE. Our study and simulation results show that by choosing an appropriate threshold, it is possible to gain in terms of complexity savings while having no or minimal effect on the BER performance of the system. Furthermore, the effect of channel estimation on the performance of the cooperative system is investigated. In the second part of the work, a joint preprocessor-based detector for cooperative communication networks is proposed for one-way and two-way relaying. This joint preprocessor-based detector operates on the principles of minimizing the symbol error rate (SER) instead of minimizing MSE. For a realistic assessment, pilot symbols are used to estimate the channel. From our simulations, it can be observed that our proposed detector achieves the same SER performance as that of the maximum likelihood (ML) detector with all participating relays. Additionally, our detector outperforms selection combining (SC), channel shortening (CS) scheme and reduced-rank techniques when using the same U. Finally, our proposed scheme has the lowest computational complexity.

S.Skryabin demonstrou que qualquer álgebra de Lie simples de dimensão finita sobre um corpo de característica 2 possui posto toroidal 2. Duas 2- álgebras de Lie de dimensão 31 foram estudadas. Neste trabalho, mostramos que a primeira delas contem uma base toroidal absoluta de dimensão três, assim como a segunda, que foi estudada por Grishkov e Guerreiro anteriormente. Utilizando uma decomposicão de Cartan, exibimos um isomorfismo entre as duas 2- álgebras de Lie de dimensão 31. Este resultado foi sugerido depois de encontrar uma sub álgebra de dimensão 12 n ao solúvel e 7 isomorfas 2-sub álgebras de Lie de dimensão 7 nas duas álgebras. Finalmente, exploramos uma 2- álgebra de Lie de dimensão 34 como o fim de encontrar base toroidal absoluta de dimensão 4. Apoiamos os cálculos com algumas códigos no linguajem de MATLAB que permitiram optimizar e acelerar a pesquisa. / S.Skryabin showed that any finite dimensional simple Lie algebra over a field of characteristic 2 has absolute toral rank 2. Two 31-dimensional 2-algebras were known. In this work, we show that the first of these algebras, contains a 3-dimensional maximal toral subalgebra, as the second one, which was studied by Grishkov e Guerreiro previously. Using a Cartan decomposition we establish an isomorphism between the two 31-dimensional 2-algebras. This result was suggested after finding a 12-dimensional not soluble subalgebra and seven 7-dimensional isomorphic 2-subalgebras in both algebras. Finally, a 34-dimensional 2-Lie algebra was studied in order to find 4-dimensional maximal toral subalgebras. Some computations in this work were performed with help of MATLAB.

Let G be an undirected graph on n vertices and let S(G) be the class of all real-valued symmetric n × n matrices whose nonzero off-diagonal entries occur in exactly the positions corresponding to the edges of G. Let V = {1, 2, . . . , n} be the vertex set of G. A scheme on G is a function f : V → {0, 1}. Given a scheme f on G, there is an associated class of matrices Sf (G) = {A ∈ S(G)|aii = 0 if and only if f(i) = 0}. A scheme f is said to be constructible if there exists a matrix A ∈ Sf (G) with rank A = min{rank M|M ∈ S(G)}. We explore properties of constructible schemes and give a complete classification of which schemes are constructible for paths and cycles. We also consider schemes on complete graphs and show the existence of a graph for which every possible scheme is constructible.

<p>In order to design robust controllers, H-infinity synthesis is a common tool to use. The controllers that result from these algorithms are typically of very high order, which complicates implementation. However, if a constraint on the maximum order of the controller is set, that is lower than the order of the plant, the problem is no longer convex and it is then relatively hard to solve. These problems become very complex, even when the order of the system to be controlled is low.</p><p>The approach used in the thesis is based on formulating the constraint on the maximum order of the plant as a polynomial equation. By using the fact that the polynomial is non-negative on the feasible set, the problem is reformulated as an optimization problem where the nonconvex polynomial function is to be minimized over a convex set defined by linear matrix inequalities.</p><p>To solve this optimization problem, two methods have been proposed. The first method is a barrier method and the second one is a method based on a primal-dual framework. These methods have been evaluated on several problems and compared with a well-known method found in the literature. To motivate this choice of method, we have made a brief survey of available methods available for solving the same or related problems.</p><p>The proposed methods emerged as the best methods among the three for finding lower order controllers with the same or similar performance as the full order controller. When the aim is to find the lowest order controller with no worse than +50% increase in the closed loop H-infinity norm, then the three compared methods perform equally well.</p>

<p>The Kappa coefficient is widely used in assessing categorical agreement between two raters or two methods. It can also be extended to more than two raters (methods).  When using Kappa, the shortcomings of this coefficient should be not neglected.  Bias and prevalence effects lead to paradoxes of Kappa. These problems can be avoided by using some other indexes together, but the solutions of the Kappa problems are not satisfactory. This paper gives a critical survey concerning the Kappa coefficient and gives a real life example. A useful alternative statistical approach, the Rank-invariant method is also introduced, and applied to analyze the disagreement between two raters.</p>