À 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 / 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

Cette thèse traite d'algorithmique des ensembles de données en adoptant le point de vue de la combinatoire analytique. On traite ici de trois problèmes qui illustrent cette approche: les listes à sauts associées à de l'analyse asymptotique bivariée, le hachage à essai aléatoire avec pagination et le comptage probabiliste. Les listes à sauts sont une structure de données intermédiaire entre les skiplists et les arbres binaires de recherche. L'étude de cette structure a donné lieu à un problème d'asymptotique bivariée avec coalescence de singularités. Le hachage avec essai aléatoire est un algorithme qui gère les collisions d'une table de hachage. Dans le contexte étudié qui est celui de la pagination, on obtient la moyenne, ainsi que tous les moments successifs du coût de construction. Les algorithmes de comptage probabilistes originaux Loglog et Super Loglog permettent d'estimer le cardinal d'un ensemble en utilisant un kilooctet de mémoire avec une précision d'environ 3%.

Beaucoup de programmes de visualisation, de planification de trajectoire, etc., utilisent intensivement des calculs de visibilité. Si ces calculs de visibilité ne constituent qu'une petite partie de ces programmes, ils sont en revanche responsables d'une grande partie du temps d'exécution de ces programmes: leur efficacité est donc cruciale. Les algorithmes traditionnels de calculs de visibilité ont deux défauts: ils effectuent - inutilement - des calculs sur des objets non visibles et refont tous ces calculs à chaque nouvelle requête, même si les changements avec la requête précédente sont minimes. Pour remédier à ces inconvénients dans le cadre de scènes polygonales bidimensionnelles, nous nous servons d'une structure de données - le complexe de visibilité - qui code toutes les relations de visibilité entre objets d'une scène. Après avoir montré comment construire de façon optimale le complexe de visibilité, nous montrons comment il permet d'utiliser la cohérence spatiale de la scène dans les calculs de polygones de visibilité. Nous montrons aussi comment il permet d'utiliser la cohérence temporelle dans le maintien d'une vue autour d'un point se déplaçant dans la scène. Nous étudions ces algorithmes non seulement d'un point de vue théorique mais aussi d'un point de vue pratique. Nous avons programmé ces algorithmes et effectué des comparaisons expérimentales entre algorithmes. Nous nous sommes aussi intéressés aux problèmes de dégénérescences et d'imprécisions des calculs numériques qui se posent dès que les programmes sont exécutés sur des données «réelles»

Dans ce mémoire, j'examine différents aspects d'un objet simple mais omniprésent en informatique: la séquence de symboles (appelée selon le contexte mot ou chaîne de caractères). La notion de mot est au carrefour de domaines comme la théorie de l'information et la théorie des langages. S'il est simple, il reste fondamental: nous n'avons, au plus bas niveau, que cela à disposition puisqu'il arrive toujours un moment où une donnée doit être encodée en symboles stockables en mémoire. La quantité d'information croissante de données mise à disposition et qu'on peut stocker, par exemple des génomes d'individus ou des documents numérisés, justifie que les algorithmes et les structures de données qui les manipulent soient optimisés. En conséquence, les besoins d'analyse se font sentir pour guider le choix et la conception des programmes qui manipulent ces données. L'analyse en moyenne est ici particulièrement adaptée puisque les données atteignent une variété et des volumes tellement importants que c'est le cas typique qui traduit le mieux la complexité et non pas le cas le pire. Cela évidemment pose le problème de la modélisation de données qui reste encore très épineux. En effet on souhaite deux choses contradictoires: un modèle au plus près des données, qui traduise vraiment leurs spécificités, mais aussi un modèle permettant de donner des résultats, c'est-à-dire de prédire les performances (et on comprend vite que le modèle doit donc rester relativement simple pour qu'il subsiste un espoir de le traiter!). Les méthodes sont le plus souvent celles de la combinatoire analytique et font appel à un objet mathématique, les séries génératrices, pour mener les analyses à bien.

Nous présentons ici plusieurs améliorations d'un algorithme de modélisation de l'éclairage, la méthode de radiosité. Pour commencer, une analyse détaillée de la méthode de radiosité hiérarchique permet de souligner ses points faibles et de mettre en évidence deux améliorations simples : une évaluation paresseuse des interactions entre les objets, et un nouveau critère de raffinement qui élimine en grande partie les raffinements inutiles. Un bref rappel des propriétés des fonctions de plusieurs variables et de leurs dérivées suit, qui permet d'abord de déduire une réécriture de l'expression de la radiosité, d'où un calcul numérique plus précis. Les méthodes d'estimation de l'erreur produite au cours du processus de modélisation de la lumière sont introduites. Nous voyons alors comment les propriétés de concavité de la fonction de radiosité permettent -- grâce au calcul des dérivées successives de la radiosité -- un contrôle complet de l'erreur commise dans la modélisation des interactions entre les objets, et donc un encadrement précis de la radiosité. Nous présentons un critère de raffinement basé sur cette modélisation des interactions, et un algorithme complet de radiosité hiérarchique intégrant ce critère de raffinement, et donc permettant un contrôle de l'erreur commise sur la radiosité au cours de la résolution. Finalement, nous présentons les méthodes de calcul pratique des dérivées successives de la radiosité (gradient et Hessien) dans le cas d'un émetteur constant sans obstacles tout d'abord, puis dans le cas d'un émetteur constant en présence d'obstacles et dans le cas d'un émetteur sur lequel la radiosité varie de façon linéaire.

Cette thèse étudie la distribution limite de paramètres définis récursivement sur des arbres (graphes enracinés). Un premier paramètre étudié est le résultat d'expressions arithmétiques tirées aléatoirement. Une application est l'amélioration heuristique d'un algorithme de recherche de structures secondaires d'ARN. Un autre paramètre étudié est la taille d'expressions logiques ou arithmétiques réduites selon des lois idempotentes, nilpotentes ou d'absorption. J'étudie des fonctionnelles polynomiales du mouvement brownien standard, du pont, du méandre, et de l'excursion browniens en utilisant la méthode des moments à base de séries génératrices et d'analyse de singularité. J'obtiens la limite gaussienne de la loi jointe de la taille et de la longueur de cheminement interne des tries avec source de Bernoulli en utilisant des méthodes de point fixe.

Les réseaux Euclidiens sont un riche objet algébrique qui apparaît dans des contextes variés en mathématiques et en informatique. Cette thèse considère plusieurs aspects algorithmiques des réseaux. Le concept de réduction d'une base d'un réseau est étudié minutieusement : nous couvrons en particulier le spectre complet des compromis qualité-temps des algorithmes de réduction. D'une part, nous présentons et analysons des algorithmes rapides pour trouver une base assez courte (base LLL-réduite) d'un réseau donné arbitraire. D'autre part, nous proposons de nouvelles analyses pour des algorithmes (plus lents) permettant de calculer des bases très courtes (bases HKZ et BKZ-réduites). Cette étude des algorithmes de résolution efficace de problèmes portant sur les réseaux est complétée par une application constructive exploitant leur difficulté apparente. Nous proposons et analysons des schémas cryptographiques, dont la fonction de chiffrement NTRU, et les prouvons au moins aussi difficiles à casser que de résoudre des problèmes pires-cas bien spécifiés portant sur les réseaux.