This document is a long abstract of my research work, concerning graph theory and algorithms on graphs. It summarizes some results, gives ideas of the proof for some of them and presents the context of the different topics together with some interesting open questions connected to them The first part precises the notations used in the rest of the paper; the second part deals with some problems on cycles in digraphs; the third part is an overview of two graph coloring problems and one problem on structures in colored graphs; finally the fourth part focus on some results in algorithmic graph theory, mainly in parametrized complexity.

Cette thèse traite de l'étude des spanneurs multichemins, comme extension des spanneurs de graphes classiques. Un spanneur H d'un graphe G est un sous-graphe couvrant tel que pour toute paire de sommets du graphe a, b ∈ V (G) la distance dans le spanneur dH (a, b) n'est pas trop étirée par rapport à la distance dans le graphe d'origine dG(a, b). Ainsi il existe un facteur d'étirement (α, β) tel que pour tout a, b ∈ V(G), d_h(a, b) <= α*d_G(a, b) + β. Motivés par des considérations de routage à plusieurs chemins et après la remarque que le concept de spanneur peut être étendu à toute métrique " non décroissante ", nous introduisons la notion de spanneur multichemins. Après une introduction au domaine, nous parlerons des résultats obtenus concernant d'une part les spanneurs multichemins arêtes disjoints et d'autre part les spanneurs multichemins sommets disjoints.

Digitalisering har haft allt större inverkan på samhället sedan millennieskiftet vilket har lett till omformning av metoder och vanor inom olika områden där utbildning inte är ett undantag. Den nya generationen studenters sätt att lära har påverkats av digitalisering vilket har lett till nya trender i forskning som fokuserar på användning av spel som en alternativ undervisningsmetod. Detta arbete syftar till att utforska hur ett mobilt spel med fokus på datastrukturer och algoritmer emottas av studenter på datavetenskapliga program. Studien genomfördes med forskningsstrategin Design Science med fokus på utveckling och utvärdering av en spelprototyp. Spelprototypen utvecklades med spelmotorn Unity och integrerar animering av algoritmer, interaktion med datastrukturer, återkoppling och metafor för att göra abstrakta begrepp lättare att förstå. Hur dessa integrationer påverkar studenternas attityder till inlärning analyserades genom en enkätundersökning med öppna frågor och tillämpning av en tematisk analys. Resultatet visar positiva trender i studenternas attityder till inlärning via spelet med animerad demonstration, interaktion och återkoppling. Dock är deras inställning till metaforiska spel för inlärning något skeptisk, vilket pekar på vidare undersökning av denna aspekt. Baserat på insikterna från respondenternas svar erbjuder resultatet potentialen att utveckla en förbättrad prototyp i flera iterativa cykler. Studien avslutas med att lägga fram förslag på fokus i framtida iterationer för att förfina prototypen. / Digitalization has increasingly been impacting society since the turn of the millennium, reshaping methods, and habits in various fields, including education. The learning methods of the new generation’s students have been influenced by digitalization, leading to new research trends that focus on using games as alternative teaching methods. This study aims to explore how students in computer science programs engage with a mobile game focusing on data structures and algorithms. The study was conducted using a Design Science approach focusing on the development and evaluation of a game prototype. The prototype was developed using the Unity game engine and integrates animation of algorithms, interaction with datastructures, feedback, and a metaphor to make abstract concepts easier to understand. The impact of these integrations on students' attitudes to learning was analyzed with an open-ended survey using thematic analysis. The results of the study show positive trends in students' attitudes towards learning through the game with animated demonstration, interaction, and feedback. However, their attitudes towards metaphorical games for learning are somewhat skeptical, which suggests further investigation of this aspect. Based on the insights from the respondents' answers, the result offers the potential to develop an improved prototype in several iterative cycles. The study concludes with suggestions for future iterations to refine the prototype.

<p dir="ltr">Machine learning has revolutionized the field of computer science in the recent years, yet its lack of rigorous, worst-case guarantees has raised various theoretical and practical concerns. The computer science community have thus shifted focus to <i>data-dependent</i> algorithm design and analysis, approaching the given algorithm problem with the specific instance in perspective, that can often times provide more fine-grained guarantees that better capture the non-worst-case patterns in real-world input that machine learning relies on. This thesis examines two classical problems from a data-dependent perspective: (1) Online optimization of covering and packing programs, augmented with untrusted predictions, and (2) instance-by-instance bounds on the hardness of mean estimation on the real line, accompanied by a novel beyond worst-case definition of optimality.</p><p dir="ltr">In the first part, we study <i>learning-augmented algorithms</i> in the context of online convex covering and concave packing optimization, utilizing untrusted data-dependent advice prudently to outperform classical counterparts reliably. We propose general-purpose frameworks for linear covering and concave packing, based on the simple idea of switching between candidate solutions from either the prediction or any classical online algorithm as a black-box subroutine. For convex covering where the switching strategy does not work, we extend the celebrated primal-dual framework, fine-tuning it to incorporate the external predictions. We show that our algorithmic frameworks beat classical impossibility results when the advice is accurate, while able to maintain robustness even if the advice is arbitrarily misleading.</p><p dir="ltr">In the second part, we examine the classical one-dimensional mean estimation problem, investigating whether it is possible to further our understanding of the estimation error landscape, beyond the worst-case sub-Gaussian rate. Our analyses show that in general the sub-Gaussian rate is in fact optimal on an instance-by-instance basis, and can only be outperformed if we make additional assumptions about the underlying distribution, such as symmetry. We formalize this notion of data-dependent optimality as <i>neighborhood optimality</i>, and provide tools to analyze estimators under this novel framework, establishing connections to robust mean estimation.</p>

Dans cette thèse, nous avons étudié les problèmes de décisions séquentielles, avec comme application la gestion de stocks d'énergie. Traditionnellement, ces problèmes sont résolus par programmation dynamique stochastique. Mais la grande dimension, et la non convexité du problème, amènent à faire des simplifications sur le modèle pour pouvoir faire fonctionner ces méthodes. Nous avons donc étudié une méthode alternative, qui ne requiert pas de simplifications du modèle: Monte Carlo Tree Search (MCTS). Nous avons commencé par étendre le MCTS classique (qui s'applique aux domaines finis et déterministes) aux domaines continus et stochastiques. Pour cela, nous avons utilisé la méthode de Double Progressive Widening (DPW), qui permet de gérer le ratio entre largeur et profondeur de l'arbre, à l'aide de deux méta paramètres. Nous avons aussi proposé une heuristique nommée Blind Value (BV) pour améliorer la recherche de nouvelles actions, en utilisant l'information donnée par les simulations passées. D'autre part, nous avons étendu l'heuristique RAVE aux domaines continus. Enfin, nous avons proposé deux nouvelles méthodes pour faire remonter l'information dans l'arbre, qui ont beaucoup amélioré la vitesse de convergence sur deux cas tests. Une part importante de notre travail a été de proposer une façon de mêler MCTS avec des heuristiques rapides pré-existantes. C'est une idée particulièrement intéressante dans le cas de la gestion d'énergie, car ces problèmes sont pour le moment résolus de manière approchée. Nous avons montré comment utiliser Direct Policy Search (DPS) pour rechercher une politique par défaut efficace, qui est ensuite utilisée à l'intérieur de MCTS. Les résultats expérimentaux sont très encourageants. Nous avons aussi appliqué MCTS à des processus markoviens partiellement observables (POMDP), avec comme exemple le jeu de démineur. Dans ce cas, les algorithmes actuels ne sont pas optimaux, et notre approche l'est, en transformant le POMDP en MDP, par un changement de vecteur d'état. Enfin, nous avons utilisé MCTS dans un cadre de méta-bandit, pour résoudre des problèmes d'investissement. Le choix d'investissement est fait par des algorithmes de bandits à bras multiples, tandis que l'évaluation de chaque bras est faite par MCTS. Une des conclusions importantes de ces travaux est que MCTS en continu a besoin de très peu d'hypothèses (uniquement un modèle génératif du problème), converge vers l'optimum, et peut facilement améliorer des méthodes suboptimales existantes.

Le principal but de notre recherche a été de caractériser les individus connectés dans un réseau social en analysant la structure locale du réseau. Pour cela, nous avons proposé une méthode qui décrit la façon dont un noeud (correspondant à un individu) est intégré dans le réseau. Notre méthode est liée à l'analyse de réseaux égocentrés en sociologie et à l'approche locale dans l'étude des grands graphes de terrain. Elle peut être appliquée à des petits réseaux, à des fractions de réseaux et aussi à des grands réseaux, grâce à sa petite complexité. Nous avons appliqué la méthode proposée à deux grands réseaux sociaux, un modélisant des activités enligne sur MySpace, l'autre modélisant des communications par téléphone mobile. Dans le premier cas nous nous sommes intéressés à l'analyse de la popularité enligne des artistes sur MySpace. Dans le deuxième cas, nous avons proposé et avons utilisé une méthode pour regrouper les noeuds qui sont connectés au réseau de façon similaire. Nous avons constaté que la distribution des utilisateurs de téléphone mobile dans des groupes était corrélée à d'autres caractéristiques des individus (intensité de communication et 'âge). Bien que dans cette thèse nous ayons appliqué les deux méthodes seulement aux réseaux sociaux, elles peuvent être appliquées de la même manière à tout autre graphe, peu importe son origine.

Les éditeurs collaboratifs permettent à des utilisateurs éloignés de collaborer à une tâche commune qui va de l'utilisation d'un agenda partagé à la réalisation de logiciels. Ce concept est né avec SCCS en 1972 et connait un engouement récent (ex: Wikipedia). L'absence de centralisation et l'asynchronisme sont des aspects essentiels de cette approche qui relève d'un modèle pair-à-pair (P2P). D'un autre côté, le format XML est devenu une référence pour la manipulation et l'échange de documents. Notre travail vise à la réalisation d'un éditeur collaboratif P2P pour l'édition de documents semi-structurés qui sont une abstraction du format XML. Le problème est difficile et de nombreuses propositions se sont révélées erronées ou ne passant pas à l'échelle. Nous rappelons les concepts et l'état de l'art sur l'édition collaborative, les modèles centralisés et le P2P. Ensuite, nous explorons deux approches différentes : les transformées opérationnelles et le CRDT (Commutative Replicated Data Type) avec différentes structures de données arborescentes. L'objectif est de réaliser les opérations de base (ajout, suppression et ré-étiquetage) tout en garantissant la convergence du processus d'édition. Nous proposons un algorithme générique pour l'approche CRDT basée sur une notion d'indépendance dans la structure de données. Nous avons étendu nos travaux afin de réaliser l'opération de déplacement d'un sous-arbre et de prendre en compte le typage XML. Peu de travaux abordent ces deux points qui sont très utiles pour l'édition de documents. Finalement, nous donnons les résultats expérimentaux obtenus avec un prototype permettant de valider notre approche.

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.

Le sujet de cette thèse est la conception et l'implantation d'algorithmes efficaces pour des opérations de base en calcul formel, ainsi que leurs applications à des domaines connexes, comme la théorie algorithmique des nombres et la cryptographie. Une première partie traite de l'algorithmique de base sur les polynômes à une variable. L'outil systématiquement mis en oeuvre est une version constructive du principe de transposition de Tellegen, qui permet d'obtenir de nouveaux algorithmes pour l'évaluation multipoint et l'interpolation (dans diverses bases polynomiales et pour diverses familles de points d'évaluation), ainsi qu'un théorème d'équivalence entre les complexités de ces deux problèmes. La deuxième partie est consacrée à l'algorithmique des nombres algébriques. Nous étudions d'abord certaines opérations élémentaires, comme la somme, le produit et leur généralisation, le produit diamant de Brawley et Carlitz. Leur calcul repose sur l'utilisation de l'opérateur de Newton formel et de la dualité algébrique, traduite algorithmiquement par l'emploi du principe de transposition et des méthodes de type pas de bébés / pas de géants. Ces méthodes sont ensuite généralisées au cadre des systèmes de polynômes de dimension zéro, pour le calcul de polynômes minimaux dans des algèbres quotient, ainsi que de paramétrisations rationnelles. Dans la troisième partie, nous étudions la question du calcul d'un terme d'une suite récurrente linéaire à coefficients polynomiaux. Comme application, nous obtenons des améliorations théoriques et pratiques des méthodes de comptage de points utilisées en cryptographie. Nous proposons ensuite une méthode de type évaluation-interpolation pour certaines opérations usuelles sur les opérateurs différentiels linéaires à coefficients polynomiaux.

Un graphe est un objet mathématique modélisant des relations sur un ensemble d' éléments. Il est utilisé dans de nombreux domaines a des fi ns de modélisation. La taille et la complexité des graphes manipulés de nos jours entraînent des besoins de visualisation a fin de mieux les analyser. Dans cette thèse, nous présentons différents travaux en visualisation interactive de graphes qui s'attachent a exploiter les architectures de calcul parallèle (CPU et GPU) disponibles sur les stations de travail contemporaines. Un premier ensemble de travaux s'intéresse a des problématiques de dessin de graphes. Dessiner un graphe consiste a le plonger visuellement dans un plan ou un espace. La première contribution dans cette thématique est un algorithme de regroupement d'arêtes en faisceaux appelé Winding Roads. Cet algorithme intuitif, facilement implémentable et parallélisable permet de reduire considérablement les problèmes d'occlusion dans un dessin de graphe dus aux nombreux croisements d'arêtes. La seconde contribution est une méthode permettant de dessiner un réseau métabolique complet. Ce type de reseau modélise l'ensemble des réactions biochimiques se produisant dans les cellules d'un organisme vivant. L'avantage de la méthode est de prendre en compte la décomposition du réseau en sous-ensembles fonctionnels ainsi que de respecter les conventions de dessin biologique. Un second ensemble de travaux porte sur des techniques d'infographie pour la visualisation interactive de graphes. La première contribution dans cette thématique est une technique de rendu de courbes paramétriques exploitant pleinement le processeur graphique. La seconde contribution est une méthode de rendu nommée Edge splatting permettant de visualiser la densité des faisceaux d'arêtes dans un dessin de graphe avec regroupement d'arêtes. La dernière contribution porte sur des techniques permettant de mettre en évidence des sous-graphes d'interêt dans le contexte global d'une visualisation de graphes.