Malgré le franc succès des techniques de planification de mouvement au cours de ces deux dernières décennies, leur adaptation à des scènes comprenant à la fois des obstacles statiques et des obstacles mobiles s'est avérée limitée jusqu'ici. Une des raisons en est le coût associé à la mise à jour des structures de données précalculées afin de capturer la connexité de l'espace libre. Notre contribution principale concerne la proposition d'un nouveau planificateur capable de traiter ces problèmes d'environnements partiellement dynamiques composés à la fois d'obstacles statiques et d'obstacles mobiles.

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.

Context. In newer database solutions designed for large-scale, cloud-based services, database performance is of particular concern as these services face scalability challenges due to I/O bottlenecks. These issues can be alleviated through various data model optimizations that reduce I/O loads. Object serialization is one such approach. Objectives. This study investigates the performance of serialization using the Apache Avro library in the Cassandra database. Two different serialized data models are compared with a traditional relational database model. Methods. This study uses an experimental approach that compares read and write latency using Twitter data in JSON format. Results. Avro serialization is found to improve performance. However, the extent of the performance benefit is found to be highly dependent on the serialization granularity defined by the data model. Conclusions. The study concludes that developers seeking to improve database throughput in Cassandra through serialization should prioritize data model optimization as serialization by itself will not outperform relational modelling in all use cases. The study also recommends that further work is done to investigate additional use cases, as there are potential performance issues with serialization that are not covered in this study.

<p dir="ltr">The twenty-first century is a data-driven era where human activities and behavior, physical phenomena, scientific discoveries, technology advancements, and almost everything that happens in the world resulting in massive generation, collection, and utilization of data. </p><p dir="ltr">Connectivity in data is a crucial property. A straightforward example is the World Wide Web, where every webpage is connected to other web pages through hyperlinks, providing a form of directed connectivity. Combinatorial data refers to combinations of data items based on certain connectivity rules. Other forms of combinatorial data include social networks, meshes, community clusters, set systems, and molecules.</p><p dir="ltr">This Ph.D. dissertation focuses on learning and computing with combinatorial data. We study and examine topological and connectivity features within and across connected data to improve the performance of learning and achieve high algorithmic efficiency.</p>

Mutation testing (MT) is a powerful technique for evaluating the quality of software test suites by introducing small faults, called ``mutations,'' into code to assess if tests can detect them. While MT has been extensively applied in the software industry, its use in programming courses faces both computational and pedagogical barriers. My research investigates the successful integration of MT in a post-CS2 Data Structures and Algorithms (DSA) course with 3-4 week long programming projects. Through a comprehensive study across multiple semesters, I investigated three key aspects: the computational demands of MT in an educational auto-grading system, the effect of MT on student test suite quality and coding practices, and the development of a framework for effectively integrating MT in programming courses. Initially, the implementation of standard MT showed mixed results due to inadequate stock feedback. This prompted me to develop a tailored approach that modified MT feedback, while also incorporating additional documentation and training materials. I also observed a noticeable increase (30-50 seconds per submission) in the auto-grader's processing time and feedback turnaround time when using MT, raising concerns about potential server overload. At the same time, the collection of changes made to the environment and requirements as part of this intervention led to an overall reduction in the number of submissions per student needed to complete the projects. My findings suggest that students using modified MT, as a group, demonstrated higher quality test suites and wrote better solution code compared to students whose test suites were graded on code coverage. This version of MT with modified feedback also showed positive results in student understanding and application of MT principles compared to MT with stock feedback. Analysis of IDE activity data, code submissions, and 38 semi-structured student interviews led me to provide a framework for introducing MT as an effective intervention. Thus, my research provides a framework for effectively integrating MT in programming courses, contributing to improved student test suite development and offering practical guidelines for instructors introducing MT in undergraduate Computer Science courses. / Doctor of Philosophy / Software plays a crucial role in our daily lives, from the apps on our smartphones to the systems that control our cars and homes. Ensuring that software works correctly and reliably is essential to prevent potential harm or inconvenience caused by malfunctions. One way to ensure software quality is through thorough testing, which involves writing test cases that check whether the software behaves as expected under various conditions. One advanced testing technique used in the software industry is mutation testing (MT), which deliberately introduces small changes (or ``mutations'') into working code to see if existing tests can catch these artificial mistakes. While this technique is powerful, its adoption in programming courses has been challenging due to technical limitations and teaching difficulties. My research focused on successfully introducing MT in a college-level computer programming course. I studied how MT could be effectively taught to students while managing the additional computational demands it places on the course's automated grading system. Over multiple semesters, I developed and refined an approach that made MT more accessible and beneficial for students. Initially, using standard MT tools proved problematic because students found the stock feedback difficult to understand. In response, I modified a more student-friendly version with clear explanations, documentations, and training materials. While this improved version did require more processing time from the grading system, I also applied solutions to alleviate computational overload on the course's automated grading system, such as allowing students to run MT on their own computers. The results were encouraging: students who used modified MT wrote better tests and produced higher quality code compared to students graded using the previous test suite quality measure (code coverage). Following interviews with students and analysis of their coding patterns, I developed a comprehensive framework for successfully introducing MT in programming courses. Finally, my research provides practical guidelines for instructors who want to incorporate this industry-standard testing technique into their teaching, ultimately helping students become better programmers. My research contributes to the field of Computer Science education by improving training in testing, helping students create more robust software tests, and providing instructors with insights into effectively teaching this influential yet complex topic.

Nous considérons la résolution de très grands systèmes linéaires creux à l'aide d'une méthode de factorisation directe appelée méthode multifrontale. Bien que numériquement robustes et faciles à utiliser (elles ne nécessitent que des informations algébriques : la matrice d'entrée A et le second membre b, même si elles peuvent exploiter des stratégies de prétraitement basées sur des informations géométriques), les méthodes directes sont très coûteuses en termes de mémoire et d'opérations, ce qui limite leur applicabilité à des problèmes de taille raisonnable (quelques millions d'équations). Cette étude se concentre sur l'exploitation des approximations de rang-faible dans la méthode multifrontale, pour réduire sa consommation mémoire et son volume d'opérations, dans des environnements séquentiel et à mémoire distribuée, sur une large classe de problèmes. D'abord, nous examinons les formats rang-faible qui ont déjà été développé pour représenter efficacement les matrices denses et qui ont été utilisées pour concevoir des solveur rapides pour les équations aux dérivées partielles, les équations intégrales et les problèmes aux valeurs propres. Ces formats sont hiérarchiques (les formats H et HSS sont les plus répandus) et il a été prouvé, en théorie et en pratique, qu'ils permettent de réduire substantiellement les besoins en mémoire et opération des calculs d'algèbre linéaire. Cependant, de nombreuses contraintes structurelles sont imposées sur les problèmes visés, ce qui peut limiter leur efficacité et leur applicabilité aux solveurs multifrontaux généraux. Nous proposons un format plat appelé Block Rang-Faible (BRF) basé sur un découpage naturel de la matrice en blocs et expliquons pourquoi il fournit toute la flexibilité nécéssaire à son utilisation dans un solveur multifrontal général, en terme de pivotage numérique et de parallélisme. Nous comparons le format BRF avec les autres et montrons que le format BRF ne compromet que peu les améliorations en mémoire et opération obtenues grâce aux approximations rang-faible. Une étude de stabilité montre que les approximations sont bien contrôlées par un paramètre numérique explicite appelé le seuil rang-faible, ce qui est critique dans l'optique de résoudre des systèmes linéaires creux avec précision. Ensuite, nous expliquons comment les factorisations exploitant le format BRF peuvent être efficacement implémentées dans les solveurs multifrontaux. Nous proposons plusieurs algorithmes de factorisation BRF, ce qui permet d'atteindre différents objectifs. Les algorithmes proposés ont été implémentés dans le solveur multifrontal MUMPS. Nous présentons tout d'abord des expériences effectuées avec des équations aux dérivées partielles standardes pour analyser les principales propriétés des algorithms BRF et montrer le potentiel et la flexibilité de l'approche ; une comparaison avec un code basé sur le format HSS est également fournie. Ensuite, nous expérimentons le format BRF sur des problèmes variés et de grande taille (jusqu'à une centaine de millions d'inconnues), provenant de nombreuses applications industrielles. Pour finir, nous illustrons l'utilisation de notre approche en tant que préconditionneur pour la méthode du Gradient Conjugué.

Cette thése étudie le problème NP-difficile de optimization quadratique en variables binaires (BQO), à savoir le problème de la maximisation d'une fonction quadratique en variables binaires. BQO peut représenter de nombreux problèmes importants de différents domaines et servir de modèle unifié pour un grand nombre de problèmes d'optimisation combinatoire portant sur les graphes. Cette thèse est consacrée au développement d'algorithmes métaheuristiques efficaces pour résoudre le BQO et ses applications. Premièrement, nous proposons algorithmes de "backbone guided" recherche tabou et d'un algorithme mémétique multi-niveaux sur la base de la technique de la fixation de variables. Ces techniques sont toutes deux basées sur l'idée de la réduction du problème afin de mener à bien une exploitation exhaustive d'une petite région de recherche. Ensuite, nous nous concentrons sur des procédés avancés de génération des solutions initiales préférables et développons des algorithmes combinant GRASP avec la recherche tabou et les algorithmes de path-relinking. En outre, nous résolvons des problèmes, y compris le problème de coupe maximum, de clique maximum, de clique maximale de sommets pondérés et la somme coloration minimum, soit en appliquant directement ou avec une légère adaptation de nos algorithmes développés pour BQO, avec l'hypothèse que ces problèmes sont reformulés en BQO. Enfin, nous présentons un algorithme mémétique basé sur la recherche tabou qui s'attaque efficacement au BQO avec contrainte de cardinalité.

Ce travail de thèse concerne la fouille de données sur des graphes attribués. Il s'agit de graphes dans lesquels des propriétés, encodées sous forme d'attributs, sont associées à chaque sommet. Notre objectif est la découverte, dans ce type de données, de sous-graphes organisés en plusieurs groupes de sommets fortement connectés et homogènes au regard des attributs. Plus précisément, nous définissons l'extraction sous contraintes d'ensembles de sous-graphes densément connectés et tels que les sommets partagent suffisamment d'attributs. Pour cela nous proposons deux familles de motifs originales ainsi que les algorithmes justes et complets permettant leur extraction efficace sous contraintes. La première famille, nommée Ensembles Maximaux de Cliques Homogènes, correspond à des motifs satisfaisant des contraintes concernant le nombre de sous-graphes denses, la taille de ces sous-graphes et le nombre d'attributs partagés. La seconde famille, nommée Collections Homogènes de k-cliques Percolées emploie quant à elle une notion de densité plus relaxée permettant d'adapter la méthode aux données avec des valeurs manquantes. Ces deux méthodes sont appliquées à l'analyse de deux types de réseaux, les réseaux de coopérations entre chercheurs et les réseaux d'interactions de protéines. Les motifs obtenus mettent en évidence des structures utiles dans un processus de prise de décision. Ainsi, dans un réseau de coopérations entre chercheurs, l'analyse de ces structures peut aider à la mise en place de collaborations scientifiques entre des groupes travaillant sur un même domaine. Dans le contexte d'un graphe de protéines, les structures exhibées permettent d'étudier les relations entre des modules de protéines intervenant dans des situations biologiques similaires. L'étude des performances en fonction de différentes caractéristiques de graphes attribués réels et synthétiques montre que les approches proposées sont utilisables sur de grands jeux de données.

Ce mémoire résume une quinzaine d'années de recherche dans le monde industriel et universitaire. Il est divisé en trois parties, traitant respectivement de la théorie de la morphologie mathématique, des systèmes dynamiques et enfin des applications au traitement des images. En morphologie mathématique, nos travaux ont porté principalement sur le filtrage et la segmentation d'images. En ce qui concerne le filtrage, nous avons proposé un algorithme quasi-linéaire pour calculer l'arbre des composantes, une des structures d'organisation naturelles des ensembles de niveaux d'une image. En segmentation, nous nous sommes principalement intéressé à la ligne de partage des eaux. Nous en avons proposé une définition continue. En nous servant du formalisme récemment introduit par Gilles Bertrand, nous avons comparé les propriétés de plusieurs définitions discrètes et nous avons proposé un algorithme quasi-linéaire permettant de calculer la ligne de partage des eaux topologique. Notre algorithme repose en partie sur celui de l'arbre des composantes. Enfin, nous avons proposé des schémas hiérarchiques pour utiliser la ligne de partage des eaux, et en particulier, nous avons proposé de valuer les contours produits par un critère de saillance donnant l'importance du contour dans la hiérarchie. Ces études nous ont conduit à proposer des classes de graphes adaptés pour la fusion de région, mettant en particulier en évidence l'équivalence existant entre une de ces classes de graphes et la classe des graphes pour lesquels toute ligne de partage des eaux binaire est mince. En ce qui concerne les systèmes dynamiques, nous avons utilisé les outils issus du cadre de l'analyse multivoque et de la théorie de la viabilité pour proposer un algorithme (dit des "Montagnes Russes") qui permet de converger vers le minimum global d'une fonction dont on connaît l'infimum. L'association du cadre algébrique des treillis complets, de l'algèbre et de la théorie des inclusions différentielles nous a permis de donner des propriétés algébriques et de continuité d'applications agissant sur des ensembles fermés, comme l'ensemble atteignable ou le noyau de viabilité. Nous avons utilisé le cadre des équations mutationnelles, permettant de dériver des tubes de déformations de formes dans des espaces métriques, pour prouver de manière rigoureuse et sans hypothèse de régularité sur la forme, l'intuition selon laquelle la dilatation transforme la forme dans la direction des normales à celle-ci en chacun de ses points. Nous avons adapté au cadre des équations mutationnelles le théorème d'Euler, qui permet d'approcher une solution à une équation mutationnelle par une s'equence de points dans un espace métrique. Enfin, nous avons proposé une approche générique de simulation, fondée sur les systèmes de particules, qui a prouvé son efficacité par sa mise en œuvre en milieu industriel, en particulier, pour la simulation de foules, pour la synthèse d'images, ou encore pour la simulation du déploiement d'airbags. Nous pensons que de bonnes études théoriques aident à réaliser des applications de qualité. Inversement, de bons problèmes théoriques peuvent trouver une source dans de bons problèmes applicatifs. On trouvera dans ce mémoire le résumé d'un certain nombre de travaux dont l'intérêt industriel a été prouvé par des brevets ou des logiciels. Citons par exemple un outil de segmentation 4D (3D+temps) en imagerie cardiaque utilisé par des médecins dans le cadre de leur pratique. Nous avons travaillé pendant plusieurs années dans le domaine du traitement d'images de documents. Nous avons proposé un outil basé sur la morphologie mathématique permettant d'estimer l'angle d'inclinaison d'un document scanné. Plus particulièrement, nous avons étudié des problèmes liés à l'indexation et à la reconnaissance de dessins techniques.

Cette thèse présente l'ensemble des concepts mathématiques et de Génie Logiciel ayant servi à la réalisation d'un cahier de brouillon interactif pour la théorie des graphes : Cabri-graphes.