Les capteurs multi- et hyper-spectraux génèrent un énorme flot de données. Un moyende contourner cette difficulté est de pratiquer une acquisition compressée de l'objet multi- ethyper-spectral. Les données sont alors directement compressées et l'objet est reconstruitlorsqu'on en a besoin. L'étape suivante consiste à éviter cette reconstruction et à travaillerdirectement avec les données compressées pour réaliser un traitement classique sur un objetde cette nature. Après avoir introduit une première approche qui utilise des outils riemannienspour effectuer une détection de contours dans une image multispectrale, nous présentonsles principes de l'acquisition compressée et différents algorithmes utilisés pour résoudre lesproblèmes qu'elle pose. Ensuite, nous consacrons un chapitre entier à l'étude détaillée de l'und'entre eux, les algorithmes de type Bregman qui, par leur flexibilité et leur efficacité vontnous permettre de résoudre les minimisations rencontrées plus tard. On s'intéresse ensuiteà la détection de signatures dans une image multispectrale et plus particulièrement à unalgorithme original du Guo et Osher reposant sur une minimisation L1. Cet algorithme estgénéralisé dans le cadre de l'acquisition compressée. Une seconde généralisation va permettrede réaliser de la détection de motifs dans une image multispectrale. Et enfin, nous introduironsde nouvelles matrices de mesures qui simplifie énormément les calculs tout en gardant debonnes qualités de mesures. / Multi- and hyper-spectral sensors generate a huge stream of data. A way around thisproblem is to use a compressive acquisition of the multi- and hyper-spectral object. Theobject is then reconstructed when needed. The next step is to avoid this reconstruction and towork directly with compressed data to achieve a conventional treatment on an object of thisnature. After introducing a first approach using Riemannian tools to perform edge detectionin multispectral image, we present the principles of the compressive sensing and algorithmsused to solve its problems. Then we devote an entire chapter to the detailed study of one ofthem, Bregman type algorithms which by their flexibility and efficiency will allow us to solvethe minimization encountered later. We then focuses on the detection of signatures in amultispectral image relying on an original algorithm of Guo and Osher based on minimizingL1. This algorithm is generalized in connection with the acquisition compressed. A secondgeneralization will help us to achieve the pattern detection in a multispectral image. Andfinally, we introduce new matrices of measures that greatly simplifies calculations whilemaintaining a good quality of measurements.

Une tâche importante qui a été étudiée dans le contexte de données à forte dimensionnalité est la tâche connue sous le nom de subspace clustering. Le subspace clustering est généralement reconnu comme étant plus compliqué que le clustering standard, étant donné que cette tâche vise à détecter des groupes d’objets similaires entre eux (clusters), et qu’en même temps elle vise à trouver les sous-espaces où apparaissent ces similitudes. Le subspace clustering, ainsi que le clustering traditionnel ont été récemment étendus au traitement de flux de données en mettant à jour les modèles de clustering de façon incrémentale. Les différents algorithmes qui ont été proposés dans la littérature, reposent sur des bases algorithmiques très différentes. Parmi ces approches, les algorithmes évolutifs ont été sous-explorés, même si ces techniques se sont avérées très utiles pour traiter d’autres problèmes NP-difficiles. L’objectif de cette thèse a été de tirer parti des nouvelles connaissances issues de l’évolution afin de concevoir des algorithmes évolutifs qui traitent le problème du subspace clustering sur des jeux de données statiques ainsi que sur des flux de données dynamiques. Chameleoclust, le premier algorithme développé au cours de ce projet, tire partie du grand degré de liberté fourni par des éléments bio-inspirés tels qu’un génome de longueur variable, l’existence d’éléments fonctionnels et non fonctionnels et des opérateurs de mutation incluant des réarrangements chromosomiques. KymeroClust, le deuxième algorithme conçu dans cette thèse, est un algorithme de k-medianes qui repose sur un mécanisme évolutif important: la duplication et la divergence des gènes. SubMorphoStream, le dernier algorithme développé ici, aborde le problème du subspace clustering sur des flux de données dynamiques. Cet algorithme repose sur deux mécanismes qui jouent un rôle clef dans l’adaptation rapide des bactéries à des environnements changeants: l’amplification de gènes et l’absorption de matériel génétique externe. Ces algorithmes ont été comparés aux principales techniques de l’état de l’art, et ont obtenu des résultats compétitifs. En outre, deux applications appelées EvoWave et EvoMove ont été développés pour évaluer la capacité de ces algorithmes à résoudre des problèmes réels. EvoWave est une application d’analyse de signaux Wi-Fi pour détecter des contextes différents. EvoMove est un compagnon musical artificiel qui produit des sons basés sur le clustering des mouvements d’un danseur, décrits par des données provenant de capteurs de déplacements. / An important task that has been investigated in the context of high dimensional data is subspace clustering. This data mining task is recognized as more general and complicated than standard clustering, since it aims to detect groups of similar objects called clusters, and at the same time to find the subspaces where these similarities appear. Furthermore, subspace clustering approaches as well as traditional clustering ones have recently been extended to deal with data streams by updating clustering models in an incremental way. The different algorithms that have been proposed in the literature, rely on very different algorithmic foundations. Among these approaches, evolutionary algorithms have been under-explored, even if these techniques have proven to be valuable addressing other NP-hard problems. The aim of this thesis was to take advantage of new knowledge from evolutionary biology in order to conceive evolutionary subspace clustering algorithms for static datasets and dynamic data streams. Chameleoclust, the first algorithm developed in this work, takes advantage of the large degree of freedom provided by bio-like features such as a variable genome length, the existence of functional and non-functional elements and mutation operators including chromosomal rearrangements. KymeroClust, our second algorithm, is a k-medians based approach that relies on the duplication and the divergence of genes, a cornerstone evolutionary mechanism. SubMorphoStream, the last one, tackles the subspace clustering task over dynamic data streams. It relies on two important mechanisms that favor fast adaptation of bacteria to changing environments, namely gene amplification and foreign genetic material uptake. All these algorithms were compared to the main state-of-the-art techniques, obtaining competitive results. Results suggest that these algorithms are useful complementary tools in the analyst toolbox. In addition, two applications called EvoWave and EvoMove have been developed to assess the capacity of these algorithms to address real world problems. EvoWave is an application that handles the analysis of Wi-Fi signals to detect different contexts. EvoMove, the second one, is a musical companion that produces sounds based on the clustering of dancer moves captured using motion sensors.

Dans les dernières années, plusieurs problèmes ont été étudiés à l'interface entre la physique statistique et l'informatique. La raison étant que, souvent, ces problèmes peuvent être réinterprétés dans le langage de la physique des systèmes désordonnés, où un grand nombre de variables interagit à travers champs locales qui dépendent de l'état du quartier environnant. Parmi les nombreuses applications de l'optimisation combinatoire le routage optimal sur les réseaux de communication est l'objet de la première partie de la thèse. Nous allons exploiter la méthode de la cavité pour formuler des algorithmes efficaces de type ‘’message-passing’’ et donc résoudre plusieurs variantes du problème grâce à sa mise en œuvre numérique. Dans un deuxième temps, nous allons décrire un modèle pour approcher la version dynamique de la méthode de la cavité, ce qui permet de diminuer la complexité du problème de l'exponentielle de polynôme dans le temps. Ceci sera obtenu en utilisant le formalisme de ‘’Matrix Product State’’ de la mécanique quantique.Un autre sujet qui a suscité beaucoup d'intérêt en physique statistique de processus dynamiques est la marche aléatoire sur les réseaux. La théorie a été développée depuis de nombreuses années dans le cas que la topologie dessous est un réseau de dimension d. Au contraire le cas des réseaux aléatoires a été abordé que dans la dernière décennie, laissant de nombreuses questions encore ouvertes pour obtenir des réponses. Démêler plusieurs aspects de ce thème fera l'objet de la deuxième partie de la thèse. En particulier, nous allons étudier le nombre moyen de sites distincts visités au cours d'une marche aléatoire et caractériser son comportement en fonction de la topologie du graphe. Enfin, nous allons aborder les événements rares statistiques associées aux marches aléatoires sur les réseaux en utilisant le ‘’Large deviations formalism’’. Deux types de transitions de phase dynamiques vont se poser à partir de simulations numériques. Nous allons conclure décrivant les principaux résultats d'une œuvre indépendante développée dans le cadre de la physique hors de l'équilibre. Un système résoluble en deux particules browniens entouré par un bain thermique sera étudiée fournissant des détails sur une interaction à médiation par du bain résultant de la présence du bain. / In the last years several problems been studied at the interface between statistical physics and computer science. The reason being that often these problems can be reinterpreted in the language of physics of disordered systems, where a big number of variables interacts through local fields dependent on the state of the surrounding neighborhood. Among the numerous applications of combinatorial optimisation the optimal routing on communication networks is the subject of the first part of the thesis. We will exploit the cavity method to formulate efficient algorithms of type message-passing and thus solve several variants of the problem through its numerical implementation. At a second stage, we will describe a model to approximate the dynamic version of the cavity method, which allows to decrease the complexity of the problem from exponential to polynomial in time. This will be obtained by using the Matrix Product State formalism of quantum mechanics. Another topic that has attracted much interest in statistical physics of dynamic processes is the random walk on networks. The theory has been developed since many years in the case the underneath topology is a d-dimensional lattice. On the contrary the case of random networks has been tackled only in the past decade, leaving many questions still open for answers. Unravelling several aspects of this topic will be the subject of the second part of the thesis. In particular we will study the average number of distinct sites visited during a random walk and characterize its behaviour as a function of the graph topology. Finally, we will address the rare events statistics associated to random walks on networks by using the large-deviations formalism. Two types of dynamic phase transitions will arise from numerical simulations, unveiling important aspects of these problems. We will conclude outlining the main results of an independent work developed in the context of out-of-equilibrium physics. A solvable system made of two Brownian particles surrounded by a thermal bath will be studied providing details about a bath-mediated interaction arising for the presence of the bath.

La présente étude concerne l’étude d’optimisation thermique d’une machine électrique. Un modèle nodal est utilisé pour la simulation du champ de température. Ce modèle résout l’équation de la chaleur en trois dimensions, en coordonnées cylindriques et en régime transitoire ou permanent. On prend en compte les deux mécanismes de transport les plus importants : La conduction et la convection. L’évaluation de ce modèle est effectuée par l’intermédiaire de 13 valeurs de débits de référence. C’est en faisant varier ces variables qu’on évalue la performance du refroidissement dans la machine. Avant de partir sur l’étude d’optimisation de cettegéométrie, on a lancé une étude d’optimisation d’un cas plus simple afin de mieux comprendre les différents outils d’optimisation disponibles. L’expérience acquise avec les cas simples est utilisée dans l’optimisation thermique de la machine. La machine est thermiquement évaluée sur la combinaison de deux critères : la température maximale et la température moyenne. Des contraintes ont été additionnées afin d’obtenir des résultats physiquement acceptables. Le problème est résolu à l’aide des méthodes de gradient (Active-set et Point-Intérieur) et des Algorithmes Génétiques. / This work relates the thermal optimization of an electrical machine. The lumped method is used to simulate the temperature field. This model solves the heat equation in three dimensions, in cylindrical coordinates and in transient or steady state. We consider two transport mechanisms: conduction and convection. The evaluation of this model is performed by means of 13 design variables that correspond to the main flow rates of the equipment. We analyse the machine cooling performance by varying these 13 flow rates. Before starting the study of such a complicated geometry, we picked a simpler case in order to better understand the variety of the available optimization tools. The experience obtained in the simpler case is applyed in the resolution of the thermal optimization problem of the electrical machine. This machine is evaluated from the thermal point of view by combining two criteria : the maximum and the mean temperature. Constraints are used to keep the problem consistent. We solved the problem using the gradient based methods (Active-set and Interior-Point) and the Genetic Algorithms.

Comment l'accès au savoir peut-il être impacté par la technologie ? Il suffit d'observer le virage intenté par les outils de communication au début des années 2000 pour se rendre compte : convergence des médias, pratiques participatives et numérisation massive des données. Dans ce contexte, on imagine que l'accès au savoir tend à se démocratiser. En effet, les individus semblent se réapproprier les espaces de vie, en inversant le modèle de transmission top-down, qui va du producteur vers le consommateur, au profit de processus de transfert basés sur l'intelligence collective. Pourtant, on aurait tort de réduire cette réorganisation à un simple renversement du modèle. Car l'intelligence collective est encline à divers biais cognitifs et socio-cognitifs, amenant parfois vers des situations irrationnelles. Autrefois, on s’accommodait de ces mécaniques sociales aux conséquences limitées, aujourd'hui les savoirs numérisés constituent des ensembles massivement communiquant, donnant naissance à de nouvelles voies d'accès et à de nouveaux clivages. Pourquoi ce savoir qui n'a jamais été aussi massif et ouvert, se révèle-t-il si sélectif ? Je propose d'explorer ce paradoxe. L'enregistrement massif et constant de nos traces numériques et l'hyper-connexion des individus, participent à la construction de structures organisationnelles, où se retrouvent numérisées de manière complexe, une partie des dynamiques sociales. En formalisant de la sorte les voies navigables, ces structures organisationnelles façonnent nos trajectoires. Sur cette base, les informaticiens ont mis au point des algorithmes de parcours individualisés, ayant pour objectifs de prédire et de recommander. Ainsi, on propose d'automatiser l'accès au savoir. Se pose alors la question de la gouvernance des individus, dans un contexte où l'intelligence collective est soumise à l'infrastructure : enregistrement des traces, composition des structures organisationnelles et algorithmes de parcours. / How access to knowledge can be impacted by Information Technology? In the earlier 2000s, communication tools caused a significant turn : media convergence, participative practices and massive data. In this way, free access to knowledge might tend to be democratized. People seem to regain spaces, reversing traditional top-down model, going from producer to consumer, for the benefit of an horizontal model based on collective intelligence. However, it should not automatically be assumed that this leads to a simple model reversing. Collective intelligence is subject to cognitive biases, leading to potential irrational situations. Formerly, those social mechanisms had limited consequences. Nowadays, digital knowledge are massive communicating spaces, giving birth to new access paths and new cleavages. Why this massive and open knowledge, is actually so selective? I propose to explore this paradox. Massive and constant tracking of traces and individuals hyper-connection, these two facts help organizational structures design, where social dynamics are digitalized in a complex way. These structures formalize human trajectories. On this basis, computer scientists set up prediction algorithms and recommender engines. This way, knowledge access is automatized. It can then be asked about people governance, in this context of infrastructure submission: recording traces, designing knowledge structure and automating algorithms.

La créativité est considérée comme une compétence cruciale pour le monde contemporain. La recherche décrite dans cette thèse a eu comme contexte principal le projet MC Squared. Réalisé entre octobre 2013 et septembre 2016. L'objectif du projet était de développer une plate-forme numérique pour le développement de C-books destinés à l'enseignement des mathématiques de manière à développer la pensée mathématique créative chez les étudiants et les auteurs. Cette thèse propose une analyse de la conception, du développement, de la mise en oeuvre et du test des activités numériques et non numériques dans le but d'améliorer et d'encourager la pensée mathématique créative ayant des fonctions et des algorithmes comme objets mathématiques à analyser. Les questions de recherche suivantes ont été soulevées à partir du problème: -Comment opérationnaliser et réviser les définitions existantes de la pensée mathématique créative? -Quels sont les composants nécessaires d'une situation ou d'un artefact permettant un processus de pensée mathématique créative? -Comment pouvons-nous évaluer l'avancement d'un processus impliquant la pensée mathématique créative?-Le modèle "Diamant de la créativité" est-il un outil d'analyse utile pour cartographier le cheminement du processus créatif? Pour répondre à ces questions, la recherche a suivi une méthodologie basée sur une recherche agile basée sur le design. Quatre activités ont été développées de manière cyclique. Le premier, appelé Function Hero, est un jeu numérique qui utilise les mouvements du corps du joueur pour évaluer la capacité de reconnaissance des fonctions. Trois autres activités appelées Binary Code, Fake Binary Code et Op'Art, visant au développement de la pensée computationnelle. Le modèle principal de cette thèse est le modèle "Diamond de créativité" pour cartographier le processus de résolution des problèmes rencontrés dans chaque activité, en évaluant le processus et les produits dérivés du travail des étudiants.Pour valider les hypothèses de recherche, nous avons collecté des données pour chaque activité et les avons analysées quantitativement et qualitativement. Les résultats montrent que les activités développées ont éveillé et engagé les étudiants dans la résolution de problèmes et que le modèle "Diamond of Creativity" peut aider à identifier et à identifier des points spécifiques du processus de création / Creativity is considered as a crucial skill for the contemporary world. The research described in this thesis had the Project MC Squared as the main context. Carried out between October 2013 and September 2016. The objective of the project was to develop a digital platform for the development of C-books for teaching mathematics in a way that develops Creative Mathematical Thinking both in the students and the authors. This thesis, entitled: Didactic Situations for the Development of Creative Mathematical Thinking proposes an analysis of the design, development, implementation, and testing of digital and non-digital activities with the aim of improving and fostering Creative Mathematical Thinking having Functions and Algorithms as mathematical objects to analyze. The following research questions raised from the problem: • How to operationalize and revise existing definitions of Creative Mathematical Thinking? • How can we assess the progress of a process involving Creative Mathematical Thinking? • How the "Diamond of Creativity" model is an useful analytic tool to map the Creative Process path? To answer such questions, the research followed a methodology based on an agile Design-Based Research. Four activities were cyclically developed. The first one, called: "Function Hero," is a digital game that uses body movements of the player to evaluate recognizability of functions. Three other activities called "Binary Code," "FakeBinary Code" and "Op’Art", aimed at the development of Computational Thinking. The main constructs of this thesis are: (a) the "Diamond of Creativity" model to map the process of solving problems found in each activity, evaluating the process and the products derived from the students’ work. (b) The digital game: "Function Hero". To validate the research hypotheses, we collected data from each activity and analyzed them quantitatively and qualitatively. The results show that developed activities have awakened and engaged students into problem-solving and that the "Diamond of Creativity" model can help in identifying and labeling specific points in the creative process

La conception d'algorithmes pour les systèmes concurrents et répartis est subtile et difficile. Ces systèmes sont enclins à des blocages et à des conditions de course et sont par conséquent difficiles à reproduire La vérification formelle est une technique essentielle pour modéliser le système et ses propriétés et s'assurer de sa correction au moyen du model checking. Des langages formels tels TLA+ permettent de décrire des algorithmes compliqués de manière assez concise, mais les concepteurs d'algorithmes trouvent souvent difficile de modéliser un algorithme par un ensemble de formules. Dans ce mémoire nous présentons le langage PlusCal-2 qui vise à allier la simplicité de pseudo-code à la capacité d'être vérifié formellement. PlusCal-2 améliore le langage algorithmique PlusCal conçu par Lamport en levant certaines restrictions de ce langage et en y ajoutant de nouvelles constructions. Notre langage est destiné à la description d'algorithmes à un niveau élevé d'abstraction. Sa syntaxe ressemble à du pseudo-code mais il est tout à fait expressif et doté d'une sémantique formelle. Pour calculer la dépendance conditionnelle pour les algorithmes en PlusCal-2 nous exploitons des informations sur la localité des actions et nous générons des prédicats d'indépendance. Nous proposons également une adaptation d'un algorithme de réduction par ordre partiel dynamique pour une variante du model checker TLC. Enfin, nous proposons une variante d'un algorithme de réduction par ordre partiel statique s'appuyant sur une relation de dépendance constante, et son implantation au sein de TLC. Nous présentons nos résultats expérimentaux et une preuve de correction / Designing sound algorithms for concurrent and distributed systems is subtle and challenging. These systems are prone to deadlocks and race conditions, and are therefore hard to reproduce. Formal verification is a key technique to model the system and its properties and then perform verification by means of model checking. Formal languages like TLA+ have the ability to describe complicated algorithms quite concisely, but algorithm designers often find it difficult to model an algorithm in the form of formulas. In this thesis, we present PlusCal-2 that aims at being similar to pseudo-code while being formally verifiable. PlusCal-2 improves upon Lamport?s PlusCal algorithm language by lifting some of its restrictions and adding new constructs. Our language is intended for describing algorithms at a high level of abstraction. Finite instances of algorithms described in PlusCal-2 can be verified through the TLC model checker. The second contribution presented in this thesis is a study of partial-order reduction methods using conditional and constant dependency relation. To compute conditional dependency for PlusCal-2 algorithms, we exploit their locality information and present them in the form of independence predicates. We also propose an adaptation of a dynamic partial-order reduction algorithm for a variant of the tlc model checker. As an alternative to partial order reduction based on conditional dependency, we also describe a variant of a static partial-order reduction algorithm for the tlc model checker that relies on constant dependency relation. We also present our results for the experiments along with the proof of correctness

La mémoire est considérée comme étant gloutonne en consommation d'énergie, un problème sensible, particulièrement dans les systèmes embarqués. L'optimisation globale de fonctions multimodales est également un problème délicat à résoudre du fait de la grande quantité d'optima locaux de ces fonctions. Dans ce mémoire, je présente différents nouveaux algorithmes hybrides et distribués afin de résoudre ces deux problèmes d'optimisation. Ces algorithmes sont comparés avec les méthodes classiques utilisées dans la littérature et les résultats obtenus sont encourageants. En effet, ces résultats montrent une réduction de la consommation d'énergie en mémoire d'environ 76% jusqu'à plus de 98% sur nos programmes tests, d'une part. D'autre part, dans le cas de l'optimisation globale de fonctions multimodales, nos algorithmes hybrides convergent plus souvent vers la solution optimale globale. Des versions distribuées et coopératives de ces nouveaux algorithmes hybrides sont également proposées. Elles sont, par ailleurs, plus rapides que leurs versions séquentielles respectives. / Résumé en anglais : Memory is considered to be greedy in energy consumption, a sensitive issue, especially in embedded systems. The global optimization of multimodal functions is also a difficult problem because of the large number of local optima of these functions. In this thesis report, I present various new hybrid and distributed algorithms to solve these two optimization problems. These algorithms are compared with conventional methods used in the literature and the results obtained are encouraging. Indeed, these results show a reduction in memory energy consumption by about 76% to more than 98% on our benchmarks on one hand. On the other hand, in the case of global optimization of multimodal functions, our hybrid algorithms converge more often to the global optimum solution. Distributed and cooperative versions of these new hybrid algorithms are also proposed. They are more faster than their respective sequential versions.

La sécurité des systèmes cryptographiques à clef publique repose sur la difficulté de résoudre certains problèmes mathématiques, parmi lesquels se trouve le problème du logarithme discret sur les corps finis GF(p^n). Dans cette thèse, nous étudions les variantes de l’algorithme de crible algébrique, number field sieve (NFS) en anglais, qui résolvent le plus rapidement ce problème, dans le cas où la caractéristique du corps est dite moyenne. NFS peut être divisé en quatre étapes principales : la sélection polynomiale, la recherche de relations, l’algèbre linéaire et le calcul d’un logarithme individuel. Nous décrivons ces étapes, en insistant sur la recherche de relations, une des étapes les plus coûteuses. Une des manières efficaces de réaliser cette étape est d’utiliser des algorithmes de crible. Contrairement au cas classique où la recherche de relations est réalisée dans un espace à deux dimensions, les corps finis que nous ciblons requièrent une énumération d’éléments dans un espace de plus grande dimension pour atteindre la meilleure complexité théorique. Il existe des algorithmes de crible efficaces en deux dimensions, mais peu pour de plus grandes dimensions. Nous proposons et analysons deux nouveaux algorithmes de crible permettant de traiter n’importe quelle dimension, en insistant particulièrement sur la dimension trois. Nous avons réalisé une implémentation complète de la recherche de relations pour plusieurs variantes de NFS en dimensions trois. Cette implémentation, qui s'appuie sur nos nouveaux algorithmes de crible, est diffusée au sein du logiciel CADO-NFS. Nous avons pu valider ses performances en nous comparant à des exemples de la littérature. Nous avons également été en mesure d’établir deux nouveaux records de calcul de logarithmes discrets, l'un dans un corps GF(p^5) de taille 324 bits et l'autre dans un corps GF(p^6) de taille 422 bits / The security of public-key cryptography relies mainly on the difficulty to solve some mathematical problems, among which the discrete logarithm problem on finite fields GF(p^n). In this thesis, we study the variants of the number field sieve (NFS) algorithm, which solve the most efficiently this problem, in the case where the characteristic of the field is medium. The NFS algorithm can be divided into four main steps: the polynomial selection, the relation collection, the linear algebra and the computation of an individual logarithm. We describe these steps and focus on the relation collection, one of the most costly steps. A way to perform it efficiently is to make use of sieve algorithms. Contrary to the classical case for which the relation collection takes place in a two-dimensional space, the finite fields we target require the enumeration of elements in a higher-dimensional space to reach the best theoretical complexity. There exist efficient sieve algorithms in two dimensions, but only a few in higher dimensions. We propose and study two new sieve algorithms allowing us to treat any dimensions, with an emphasis on the three-dimensional case. We have provided a complete implementation of the relation collection for some variants of the NFS in three dimensions. This implementation relies on our new sieve algorithms and is distributed in the CADO-NFS software. We validated its performances by comparing with examples from the literature. We also establish two new discrete logarithm record computations, one in a 324-bit GF(p^5) and one in a 422-bit GF(p^6)

L’objectif de ce projet de trois ans est de proposer des avancées conceptuelles et technologiques dans la résolution de problèmes d’ordonnancement du personnel. L’atteinte de cet objectif passe par la proposition de nouveaux algorithmes basés sur les métaheuristiques et leur implémentation sur les architectures de calcul haute performance. Ce projet s’inscrit en complémentarité du projet HORUS qui bénéficie d’une subvention ANR et qui réunit les expertises scientifiques de deux laboratoires universitaires spécialisés en optimisation et en calcul parallèle : l’équipe SysCom du laboratoire CReSTIC de l’URCA et l’équipe CaRO du laboratoire PRiSM de l’UVSQ. Les avancées technologiques proposées s’appuient également sur les moyens de calcul haute performance offerts par le Centre de Calcul Régional Champagne-Ardenne. / .Many academic and industrial optimization problems are multi-objective and have been of particular interest to researchers in recent years. These problems usually do not have a single optimal solution but a set of best trade-off solutions which form the so-called Pareto front in the objective space. In order to approximate the Pareto front, multi-objective evolutionary algorithms (MOEAs) have been largely investigated in the fields of continuous and combinatorial optimization. Contrary to some classical algorithms, MOEAs have the ability to provide a number of solutions in one single run and are less sensitive to the shape of the Pareto front.As they often require a high amount of computing resources to explore large portions of the search space and handle complex real-life constraints, MOEAs could greatly benefit from today's high-performance computing architectures. Although significant progress has been made in recent years in the design and improvement of parallel models for evolutionary algorithms, most of these models have limited scalability and ability to solve various problems. In fact, solving multi-objective combinatorial optimization problems efficiently on a large number of processors remains a challenge today.This thesis aims to propose an island model which is based on objective space division. The main features of the proposed model are the following (i) An organizer has a global view of the current search via a global archive (ii) Asynchronous cooperation between islands, especially for the exchange of local archives with the organizer to limit model overheads (iii)Control islands to guide the exploration of the search space and improve diversity (iv) A periodic use of a specific local search procedure to improve convergence. Extensive experiments have been conducted to evaluate the performance of the approach and more particularly of each component in the resolution of two classical combinatorial problems, the travelling salesman problem and quadratic assignment problem. Extensibility and quality of the solutions are analyzed compared to state-of-the-art parallel models.