Search

At first, we were interested in TimSort, a sorting algorithm which was designed in 2002, at a time where it was hard to imagine new results on sorting. Although it is used in many programming languages, the efficiency of this algorithm has not been studied formally before our work. The fine-grain study of TimSort leads us to take into account, in our theoretical models, some modern features of computer architecture. In particular, we propose a study of the mechanisms of branch prediction. This theoretical analysis allows us to design variants of some elementary algorithms (like binary search or exponentiation by squaring) that rely on this feature to achieve better performance on recent computers. Even if uniform distributions are usually considered for the average case analysis of algorithms, it may not be the best framework for studying sorting algorithms. The choice of using TimSort in many programming languages as Java and Python is probably driven by its efficiency on almost-sorted input. To conclude this dissertation, we propose a mathematical model of non-uniform distribution on permutations, for which permutations that are almost sorted are more likely, and provide a detailed probabilistic analysis, À l'origine de cette thèse, nous nous sommes intéressés à l'algorithme de tri TimSort qui est apparu en 2002, alors que la littérature sur le problème du tri était déjà bien dense. Bien qu'il soit utilisé dans de nombreux langages de programmation, les performances de cet algorithme n'avaient jamais été formellement analysées avant nos travaux. L'étude fine de TimSort nous a conduits à enrichir nos modèles théoriques, en y incorporant des caractéristiques modernes de l'architecture des ordinateurs. Nous avons, en particulier, étudié le mécanisme de prédiction de branchement. Grâce à cette analyse théorique, nous avons pu proposer des modifications de certains algorithmes élémentaires (comme l'exponentiation rapide ou la dichotomie) qui utilisent ce principe à leur avantage, améliorant significativement leurs performances lorsqu'ils sont exécutés sur des machines récentes. Enfin, même s'il est courant dans le cadre de l'analyse en moyenne de considérer que les entrées sont uniformément distribuées, cela ne semble pas toujours refléter les distributions auxquelles nous sommes confrontés dans la réalité. Ainsi, une des raisons du choix d'implanter TimSort dans des bibliothèques standard de Java et Python est probablement sa capacité à s'adapter à des entrées partiellement triées. Nous proposons, pour conclure cette thèse, un modèle mathématique de distribution non-uniforme sur les permutations qui favorise l'apparition d'entrées partiellement triées, et nous en donnons une analyse probabiliste détaillée

This Phd thesis is divided into two independent parts. In the first part, we provide an asymptotic analysis of some statistics on the binary search tree. In the second part, we study the coupon collector problem with a constraint. In the first part, following the model introduced by Aguech, Lasmar and Mahmoud [Probab. Engrg. Inform. Sci. 21 (2007) 133—141], the weighted depth of a node in a labelled rooted tree is the sum of all labels on the path connecting the node to the root. We analyze the following statistics : the weighted depths of nodes with given labels, the last inserted node, nodes ordered as visited by the depth first search procees, the weighted path length, the weighted Wiener index and the weighted depths of nodes with at most one child in a random binary search tree. In the second part, we study the asymptotic shape of the completion curve of the collection conditioned to T_n≤ (1+Λ), Λ>0, where T_n≃n ln⁡n is the time needed to complete accessible automata, we provide a new derivation of a formula due to Korsunov [Kor78, Kor86], Cette thèse comporte deux parties indépendantes. Dans la première partie, nous nous intéressons à l’analyse asymptotique de quelques statistiques sur les arbres binaires de recherche (ABR). Dans la deuxième partie, nous nous intéressons à l’étude du problème du collectionneur de coupons impatient. Dans la première partie, en suivant le modèle introduit par Aguech, Lasmar et Mahmoud [Probab. Engrg. Inform. Sci. 21 (2007) 133—141], on définit la profondeur pondérée d’un nœud dans un arbre binaire enraciné étiqueté comme la somme de toutes les clés sur le chemin qui relie ce nœud à la racine. Nous analysons alors dans ABR, les profondeurs pondérées des nœuds avec des clés données, le dernier nœud inséré, les nœuds ordonnés selon le processus de recherche en profondeur, la profondeur pondérée des trajets, l’indice de Wiener pondéré et les profondeurs pondérées des nœuds avec au plus un enfant. Dans la deuxième partie, nous étudions la forme asymptotique de la courbe de la complétion de la collection conditionnée à T_n≤ (1+Λ), Λ>0, où T_n≃n ln⁡n désigne le temps nécessaire pour compléter la collection. Puis, en tant qu’application, nous étudions les automates déterministes et accessibles et nous fournissons une nouvelle dérivation d’une formule due à Korsunov [Kor78, Kor86]

The first complete running time analysis of a stochastic divide and conquer algorithm was given for Quicksort, a sorting algorithm invented 1961 by Hoare. We analyse here the variant Random Median Quicksort. The analysis includes the expectation, the asymptotic distribution, the moments and exponential moments. The asymptotic distribution is characterized by a stochastic fixed point equation. The basic technic will be generating functions and the contraction method.

We study a variation of the classical Shortest Common Superstring (SCS) problem in which a shortest superstring of a finite set of strings $S$ is sought containing as a factor every string of $S$ or its reversal. We call this problem Shortest Common Superstring with Reversals (SCS-R). This problem has been introduced by Jiang et al., who designed a greedy-like algorithm with length approximation ratio $4$. In this paper, we show that a natural adaptation of the classical greedy algorithm for SCS has (optimal) compression ratio $\frac12$, i.e., the sum of the overlaps in the output string is at least half the sum of the overlaps in an optimal solution. We also provide a linear-time implementation of our algorithm., Published in Information Processing Letters

A connection is made between certain multiple-sequence alignment problems and facility-location problems, and the existence of a PTAS (polynomial-time approximation scheme) for these problems is shown. Moreover, it is shown that multiple sequence alignment with SP-score and fixed gap penalties is MAX SNP-hard.

We study the convergence of the density of states and thermodynamic properties in three flat-histogram simulation methods, the Wang-Landau (WL) algorithm, the 1/t algorithm, and tomographic sampling (TS). In the first case the refinement parameter f is rescaled (f -> f/2) each time the flat-histogram condition is satisfied, in the second f ~ 1/t after a suitable initial phase, while in the third f is constant (t corresponds to Monte Carlo time). To examine the intrinsic convergence properties of these methods, free of any complications associated with a specific model, we study a featureless entropy landscape, such that for each allowed energy E = 1,...,L, there is exactly one state, that is, g(E) = 1 for all E. Convergence of sampling corresponds to g(E,t) -> const. as t -> infinity, so that the standard deviation sigma_g of g over energy values is a measure of the overall sampling error. Neither the WL algorithm nor TS converge: in both cases sigma_g saturates at long times. In the 1/t algorithm, by contrast, sigma_g decays \propto 1/\sqrt{t}. Modified TS and 1/t procedures, in which f \propto 1/t^alpha, converge for alpha values between 0 and 1. There are two essential facets to convergence of flat-histogram methods: elimination of initial errors in g(E), and correction of the sampling noise accumulated during the process. For a simple example, we demonstrate analytically, using a Langevin equation, that both kinds of errors can be eliminated, asymptotically, if f ~ 1/t^alpha with 0 < ��\leq 1. Convergence is optimal for alpha = 1. For alpha \leq 0 the sampling noise never decays, while for alpha > 1 the initial error is never completely eliminated., 17 pages, 6 figures

This paper investigates on-line parallel machine scheduling problems. We show the optimality of the classical LS algorithm.

We study the online version of the Prize-Collecting Traveling Salesman Problem (PCTSP), a generalization of the Traveling Salesman Problem (TSP). In the TSP, the salesman has to visit a set of cities while minimizing the length of the overall tour. In the PCTSP, each city has a given weight and penalty, and the goal is to collect a given quota of the weights of the cities while minimizing the length of the tour plus the penalties of the cities not in the tour. In the online version, cities are disclosed over time. We give a 7/3-competitive algorithm for the problem, which compares with a lower bound of 2 on the competitive ratio of any deterministic algorithm. We also show how our approach can be combined with an approximation algorithm in order to obtain an O (1)-competitive algorithm that runs in polynomial time. © 2008 Elsevier B.V. All rights reserved.

International audience; In this paper, we investigate the computational and approximation complexity of the Exemplar Longest Common Subsequence of a set of sequences (ELCS problem), a generalization of the Longest Common Subsequence problem, where the input sequences are over the union of two disjoint sets of symbols, a set of mandatory symbols and a set of optional symbols. We show that different versions of the problem are APX-hard even for instances with two sequences. Moreover, we show that the related problem of determining the existence of a feasible solution of the Exemplar Longest Common Subsequence of two sequences is NP-hard. On the positive side, we first present an efficient algorithm for the ELCS problem over instances of two sequences where each mandatory symbol can appear in total at most three times in the sequences. Furthermore, we present two fixed parameter algorithms for the ELCS problem over instances of two sequences where the parameter is the number of mandatory symbols.

International audience; String matching is the problem of finding all the occurrences of a pattern in a text. We present a new method to compute the combinatorial shift function ("matching shift") of the well-known Boyer-Moore string matching algorithm. This method implies the computation of the length of the longest suffixes of the pattern ending at each position in this pattern. These values constituted an extra-preprocessing for a variant of the Boyer-Moore algorithm designed by Apostolico and Giancarlo. We give here a new presentation of this algorithm that avoids extra preprocessing together with a tight bound of 1.5n character comparisons (where n is the length of the text).

The purpose of this thesis is to study a class of power series, which we call Mahlerian, solutions to certain functional equations. These series arise in combinatorial theory, for problems involving counting words, and in the analysis of algorithms, where they are related to divide and conquer recurrences. Methods of solution of Mahlerian equations are based on the properties of rational functions with respect to the fundamental operation, analogue of the derivative for differential equations, and on the arithmetic of operators implicit in these equations. The methods we describe furnish efficient procedures for calculation, qualitative results concerning the closure of this class, and, in the complex case, analytic properties of the solutions. An important subclass of Mahlerian series is provided by B-regular series, a generalization of B-automatic series. They are the translation, via base B arithmetic, of rational series in non- commutative variables, inheriting their properties, familiar in the theory of formal languages. One can define, for example, notions of linear representation, of rank, and of Hankel matrix. Under certain simple conditions, a Mahlerian series is B-regular; in particular most divide and conquer recurrences provide B-regular series. The asymptotic analysis of coefficients of complex Mahlerian series relies on a classification which reveals the significance of B-regular series, on methods from linear algebra, and on methods from the analytic theory of numbers. The results here obtained permit us to handle a number of frequently encountered practical examples. They show, for B-regular series, a connection between the asymptotic behavior of coefficients and the spectra of linear representations. In many cases we exhibit a phenomenon of logarithmic periodicity.; L'objet de cette thèse est l'étude d'une classe de séries entières solutions de certaines équations fonctionnelles, dites mahlériennes. Ces séries interviennent en combinatoire avec des problèmes de comptage de mots et en analyse d'algorithmes où elles sont liées aux récurrences diviser pour régner. La résolution des équations mahlériennes est fondée sur les propriétés des fractions rationnelles vis à vis de l'opérateur fondamental, analogue de la dérivation pour les équations différentielles, et sur l'arithmétique des opérateurs sous-jacents à ces équations. Les méthodes décrites fournissent à la fois des procédés effectifs de calcul et des résultats qualitatifs sur les propriétés de clôture de cette classe et, dans le cas complexe, sur les propriétés analytiques des solutions. Une sous-classe importante de séries mahlériennes est fournie par les séries B-régulières, généralisation des séries B-automatiques. Elles sont la traduction, via la numération en base B, des séries rationnelles en indéterminées non commutatives de la théorie des langages formels et héritent de leurs propriétés. On peut par exemple définir les notions de représentation linéaire, de rang et de matrice de Hankel. Sous certaines conditions simples, une série mahlérienne est B-régulière ; en particulier la plupart des récurrences diviser pour régner fournissent des séries B-régulières. L'analyse asymptotique des coefficients des séries mahlériennes complexes sàppuie sur une classification qui met en valeur l'importance des séries B-régulières, sur des techniques d'algèbre linéaire et sur des méthodes de théorie analytique des nombres. Les résultats obtenus permettent de traiter les exemples rencontrés dans la pratique. Ils montrent pour les séries B-régulières un lien entre le comportement asymptotique des coefficients et le spectre des représentations linéaires et dans beaucoup de cas un phénomène de périodicité en échelle logarithmique.

The purpose of this thesis is to study a class of power series, which we call Mahlerian, solutions to certain functional equations. These series arise in combinatorial theory, for problems involving counting words, and in the analysis of algorithms, where they are related to divide and conquer recurrences. Methods of solution of Mahlerian equations are based on the properties of rational functions with respect to the fundamental operation, analogue of the derivative for differential equations, and on the arithmetic of operators implicit in these equations. The methods we describe furnish efficient procedures for calculation, qualitative results concerning the closure of this class, and, in the complex case, analytic properties of the solutions. An important subclass of Mahlerian series is provided by B-regular series, a generalization of B-automatic series. They are the translation, via base B arithmetic, of rational series in non- commutative variables, inheriting their properties, familiar in the theory of formal languages. One can define, for example, notions of linear representation, of rank, and of Hankel matrix. Under certain simple conditions, a Mahlerian series is B-regular; in particular most divide and conquer recurrences provide B-regular series. The asymptotic analysis of coefficients of complex Mahlerian series relies on a classification which reveals the significance of B-regular series, on methods from linear algebra, and on methods from the analytic theory of numbers. The results here obtained permit us to handle a number of frequently encountered practical examples. They show, for B-regular series, a connection between the asymptotic behavior of coefficients and the spectra of linear representations. In many cases we exhibit a phenomenon of logarithmic periodicity.; L'objet de cette thèse est l'étude d'une classe de séries entières solutions de certaines équations fonctionnelles, dites mahlériennes. Ces séries interviennent en combinatoire avec des problèmes de comptage de mots et en analyse d'algorithmes où elles sont liées aux récurrences diviser pour régner. La résolution des équations mahlériennes est fondée sur les propriétés des fractions rationnelles vis à vis de l'opérateur fondamental, analogue de la dérivation pour les équations différentielles, et sur l'arithmétique des opérateurs sous-jacents à ces équations. Les méthodes décrites fournissent à la fois des procédés effectifs de calcul et des résultats qualitatifs sur les propriétés de clôture de cette classe et, dans le cas complexe, sur les propriétés analytiques des solutions. Une sous-classe importante de séries mahlériennes est fournie par les séries B-régulières, généralisation des séries B-automatiques. Elles sont la traduction, via la numération en base B, des séries rationnelles en indéterminées non commutatives de la théorie des langages formels et héritent de leurs propriétés. On peut par exemple définir les notions de représentation linéaire, de rang et de matrice de Hankel. Sous certaines conditions simples, une série mahlérienne est B-régulière ; en particulier la plupart des récurrences diviser pour régner fournissent des séries B-régulières. L'analyse asymptotique des coefficients des séries mahlériennes complexes sàppuie sur une classification qui met en valeur l'importance des séries B-régulières, sur des techniques d'algèbre linéaire et sur des méthodes de théorie analytique des nombres. Les résultats obtenus permettent de traiter les exemples rencontrés dans la pratique. Ils montrent pour les séries B-régulières un lien entre le comportement asymptotique des coefficients et le spectre des représentations linéaires et dans beaucoup de cas un phénomène de périodicité en échelle logarithmique.