Cette thèse porte sur deux sujets d’algorithmique des graphes. Le premier sujet est l’inférence de réseaux. Quelle est la complexité pour déterminer un graphe inconnu à partir de requêtes de plus court chemin entre ses sommets ? Nous supposons que le graphe est de degré borné. Dans le problème de reconstruction, le but est de reconstruire le graphe ; tandis que dans le problème de vérification, le but est de vérifier qu’un graphe donné est correct. Nous développons des algorithmes probabilistes utilisant une décomposition en cellules de Voronoi. Ensuite, nous analysons des algorithmes de type glouton, et montrons qu’ils sont quasi-optimaux. Nous étudions aussi ces problèmes sur des familles particulières de graphes, démontrons des bornes inférieures, et étudions la reconstruction approximative. Le deuxième sujet est l’étude de deux problèmes d’optimisation sur les graphes planaires. Dans le problème de classification par corrélations, l’entrée est un graphe pondéré, où chaque arête a une étiquette h+i ou h-i, indiquant si ses extrémités sont ou non dans la même catégorie. Le but est de trouver une partition des sommets en catégories qui respecte au mieux les étiquettes. Dans le problème d’augmentation 2-arête-connexe, l’entrée est un graphe pondéré et un sous-ensemble R des arêtes. Le but est de trouver un sous-ensemble S des arêtes de poids minimum, tel que pour chaque arête de R, ses extrémités sont dans une composante 2-arête-connexe de l’union de R et S. Pour les graphes planaires, nous réduisons le premier problème au deuxième et montrons que les deux problèmes, bien que NP-durs, ont un schéma d’approximation en temps polynomial. Nous utilisons la technique récente de décomposition en briques. / This thesis focuses on two topics of graph algorithms. The first topic is network inference. How efficiently can we find an unknown graph using shortest path queries between its vertices? We assume that the graph has bounded degree. In the reconstruction problem, the goal is to find the graph; and in the verification problem, the goal is to check whether a given graph is correct. We provide randomized algorithms based on a Voronoi cell decomposition. Next, we analyze greedy algorithms, and show that they are near-optimal. We also study the problems on special graph classes, prove lower bounds, and study the approximate reconstruction. The second topic is optimization in planar graphs. We study two problems. In the correlation clustering problem, the input is a weighted graph, where every edge has a label of h+i or h−i, indicating whether its endpoints are in the same category or in different categories. The goal is to find a partition of the vertices into categories that tries to respect the labels. In the two-edge-connected augmentation problem, the input is a weighted graph and a subset R of edges. The goal is to produce a minimum-weight subset S of edges, such that for every edge in R, its endpoints are two-edge-connected in the union of R and S. For planar graphs, we reduce correlation clustering to two-edge-connected augmentation, and show that both problems, although they are NP-hard, have a polynomial-time approximation scheme. We build on the brick decomposition technique developed recently.

Malgré des décennies d’incontestables progrès dans le domaine des sciences informatiques, un certain nombre de problèmes restent difficiles à traiter en raison, soit de leur complexité numérique (problème d’optimisation, …), soit de contraintes spécifiques telle que la nécessité de traitement en temps réel (réalité virtuelle, augmentée, …). Dans ce contexte, il existe des méthodes de réduction de modèle qui permettent de réduire les temps de calcul de simulations multi-champs et/ou multi-échelles complexes. Le processus de réduction de modèle consiste à paramétrer un métamodèle qui requiert moins de ressources pour être évalué que le modèle complexe duquel il a été obtenu, tout en garantissant une certaine précision. Les méthodes actuelles nécessitent, en général, soit une expertise de l’utilisateur, soit un grand nombre de choix arbitraires de sa part. De plus, elles sont bien souvent adaptées à une application spécifique mais difficilement transposable à d’autres domaines. L’objectif de notre approche est donc d’obtenir, s'il n'est pas le meilleur, un bon métamodèle quel que soit le problème considéré. La stratégie développée s’appuie sur l’utilisation des hypersurfaces NURBS et se démarque des approches existantes par l’absence d’hypothèses simplificatrices sur les paramètres de celles-ci. Pour ce faire, une méta heuristique (de type algorithme génétique), capable de traiter des problèmes d’optimisation dont le nombre de variables n’est pas constant, permet de déterminer automatiquement l’ensemble des paramètres de l’hypersurface sans transférer la complexité des choix à l’utilisateur. / Despite undeniable progress achieved in computer sciences over the last decades, some problems remain intractable either by their numerical complexity (optimisation problems, …) or because they are subject to specific constraints such as real-time processing (virtual and augmented reality, …). In this context, metamodeling techniques can minimise the computational effort to realize complex multi-field and/or multi-scale simulations. The metamodeling process consists of setting up a metamodel that needs less resources to be evaluated than the complex one that is extracted from by guaranteeing, meanwhile, a minimal accuracy. Current methods generally require either the user’s expertise or arbitrary choices. Moreover, they are often tailored for a specific application, but they can be hardly transposed to other fields. Thus, even if it is not the best, our approach aims at obtaining a metamodel that remains a good one for whatever problem at hand. The developed strategy relies on NURBS hypersurfaces and stands out from existing ones by avoiding the use of empiric criteria to set its parameters. To do so, a metaheuristic (a genetic algorithm) able to deal with optimisation problems defined over a variable number of optimisation variables sets automatically all the hypersurface parameters so that the complexity is not transferred to the user.

Les WMNs comportent des nœuds qui sont capables de recevoir et de transmettre des données vers de multiples destinations dans le réseau. De ce fait, les WMNs sont capables de s'auto-organiser et auto-configurer dynamiquement [5]. Chaque nœud crée et maintient la connectivité avec ses voisins. La disponibilité du mode ad-hoc basée sur la norme IEEE 802.11 permet une mise en œuvre de WMNs à faible coût. Les WMNs présentent cependant deux inconvénients majeurs liés aux interférences d'une part et à la scalabilité d'autre part [6]. (D1) Le problème des interférences (D2) Le problème de scalabilité. Les solutions existantes au niveau de la couche PHY ou de la couche MAC peuvent apporter des solutions au problème des interférences mentionné ci-dessus (cf. D1) . D'un autre côté, le problème de scalabilité dans les WMNs peut être résolu par les solutions de routage efficaces [11]. En effet, les algorithmes de routage dans les WMNs sont chargés de calculer des routes pour transporter des données de multiples sauts jusqu' à atteindre les destinations. Comme illustré dans [11], les routes les plus courtes, qui sont les solutions par défaut des algorithmes de routage classiques, ont généralement plus d'interférences. En conséquences, il faut trouver des routes qui ont moins d'interférences. Pour un objectif de routage donné et des paramètres donnés, ces routes peuvent être optimales ou sub-optimales. Les objectifs de routage peuvent être par exemple de maximiser la bande passante entre utilisateurs, ou de minimiser les pertes de paquets, etc. Les paramètres dans les problèmes de routage comprennent des métriques orientées réseau et des métriques orientées utilisateur. Les métriques orientées réseau, également appelées les métriques de la qualité de service (QoS), sont dérivées à partir des paramètres réseau comme la bande passante, le délai, la gigue, etc. En revanche, les métriques orientées vers l'utilisateur, également appelées les métriques de qualité d'expérience (QoE), sont basées sur l'expérience de l'utilisateur, tels que les notes MOS (Mean Opinion Score) qui indiquent le niveau de satisfaction de l'utilisateur. La perception de l'utilisateur est un objectif majeur des services de streaming vidéo. La plupart des algorithmes de routage existants prennent des décisions de routage en fonction d'une seule ou d'une combinaison des métriques orientées réseau. Ainsi, les algorithmes de routage dans [12, 13, 14] déterminent les routes basées sur la bande passante et la charge du réseau. Cependant, les métriques orientées réseau ne sont pas nécessairement corrélée à l'expérience de l'utilisateur [15, 16, 17, 18]. En d'autres termes, les utilisateurs peuvent ne pas être satisfaits même avec les routes optimales qui sont basées sur les métriques orientés réseau. En conséquences, il est nécessaire de développer les algorithmes de routage qui tiennent compte de métriques orientées utilisateur. Cette thèse traite d'algorithmes de routage dans les WMNs avec comme objectif d'améliorer la qualité pour les applications de streaming vidéo. Les algorithmes de routage proposés prendront des décisions de routage basées sur la perception de l'utilisateur. Dans ce contexte, toutes les solutions doivent faire face aux deux challenges suivants : (M1) l'estimation en temps réel de la perception utilisateur et (M2) découverte des routes optimales ou sous-optimales. / WMNs comprise nodes that are able to receive and forward the data to other destinations in the networks. Consequently, WMNs are able to dynamically self-organize and self-configure [5]. Each node itself creates and maintains the connectivity with its neighbors. The availability of ad-hoc mode on popular IEEE 802.11 allows low-cost implementation of WMNs. Nevertheless, WMNs have two major drawbacks: interference and scalability as discussed in [6]. (D1) Interference : The independent behaviour and arbitrary deployment of nodes in WMNs can create an extremely high interference environment, which leads to degradation in the quality of wireless connections. For instance, the Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA) mechanism of IEEE 802.11 (CSMA/CA) has long delays and low resource utilization in dense networks [7]. Recent advancements in physical (PHY) and medium control access (MAC) layers, such as multiple-input multiple-output (MIMO) and multiple channels MAC, can overcome this challenge. The deployment of some solutions are unable in practice because of specific requirements of hardware. Moreover, some implementations such as multiple channel MAC requires high synchronization, which is difficult in WMNs [8]. (D2) Scalability: Multi-hop communication are able to improve coverage and band-width availability in wireless networks [9]. However, it has scalability issues as discussed in [10, 11]. It means that the performance of networks deteriorates significantly when the size of networks grows. PHY layer may experience an extremely noisy medium, thus causing throughput degradation at MAC layer. Moreover, the noisy environment increases the packet loss rate, which impacts significantly to network and transport layers. The existing solutions at PHY or MAC layer can solve the interference problem mentioned in D1. Meanwhile, the scalability of WMNs could be tackled by routing solutions [11]. Routing algorithms are responsible for computing routes so as to convey data through multiple hops until reaching the destinations. As shown in [11], the shortest-path routes, which are the default solutions of conventional routing algorithms, usually have more interference. The solution, subsequently, is finding other routes that have less interference. These routes could be optimal or sub-optimal with given objectives and arguments. The arguments of routing problems comprise of network-oriented metrics and User-oriented metrics. Network-oriented metrics, also called as Quality of Service (QoS) metrics, are derived from the network directly such as bandwidth, delay, jitter, etc. Meanwhile, User-oriented metrics, also called as Quality of Experience (QoE) metrics, are based on users’ experience such as mean opinion score (MOS). They represent the level of satisfaction of a users. The good perception of users is the major objective of video streaming services. Most of existing routing algorithms give routing decisions based on single or combination of network-oriented metrics. For example, the routing algorithms in [12, 13, 14] determine routes based on the bandwidth and congestion. Nevertheless, network-oriented metrics may not be well-correlated to users’ experience [15, 16, 17, 18]. In other words, users may not be satisfied even with optimal network-oriented metric routes. As a result, it is necessary to develop routing algorithms that take user-oriented metrics into account. This thesis addresses the routing of video streaming over WMNs and proposes novel routing algorithms. These routing algorithms give routing decisions based on the perception of users. To do that, the proposed solution has to address two challenges as follows :(M1) estimate users’ perception in real-time and (M2) find optimal or sub-optimal routes efficiently.

Lorsqu'une erreur survient dans le noyau Linux, celui-ci émet un rapport d’erreur appelé "kernel oops" contenant le contexte d’exécution de cette erreur. Les kernel oops décrivent des erreurs réelles de Linux, permettent de classer les efforts de débogage par ordre de priorité et de motiver la conception d’outils permettant d'améliorer la fiabilité du code de Linux. Néanmoins, les informations contenues dans un kernel oops n’ont de sens que si elles sont représentatives et qu'elles peuvent être interprétées correctement. Dans cette thèse, nous étudions une collection de kernel oops provenant d'un dépôt maintenu par Red Hat sur une période de huit mois. Nous considérons l’ensemble des caractéristiques de ces données, dans quelle mesure ces données reflètent d’autres informations à propos de Linux et l’interprétation des caractéristiques pouvant être pertinentes pour la fiabilité de Linux. Nous constatons que ces données sont bien corrélées à d’autres informations à propos de Linux, cependant, elles souffrent parfois de problèmes de duplication et de manque d’informations. Nous identifions également quelques pièges potentiels lors de l'étude des fonctionnalités, telles que les causes d'erreurs fréquentes et les causes d'applications défaillant fréquemment. En outre, un kernel oops fournit des informations précieuses et de première main pour un mainteneur du noyau Linux lui permettant d'effectuer le débogage post-mortem car il enregistre l’état du noyau Linux au moment du crash. Cependant, le débogage sur la seule base des informations contenues dans un kernel oops est difficile. Pour aider les développeurs avec le débogage, nous avons conçu une solution afin d'obtenir la ligne fautive à partir d’un kernel oops, i.e., la ligne du code source qui provoque l'erreur. Pour cela, nous proposons un nouvel algorithme basé sur la correspondance de séquences approximative utilisé dans le domaine de bioinformatique. Cet algorithme permet de localiser automatiquement la ligne fautive en se basant sur le code machine à proximité de celle-ci et inclus dans un kernel oops. Notre algorithme atteint 92% de précision comparé à 26 % pour l’approche traditionnelle utilisant le débogueur gdb. Nous avons intégré notre solution dans un outil nommé OOPSA qui peut ainsi alléger le fardeau pour les développeurs lors du débogage de kernel oops. / When a failure occurs in the Linux kernel, the kernel emits an error report called “kernel oops”, summarizing the execution context of the failure. Kernel oopses describe real Linux errors, and thus can help prioritize debugging efforts and motivate the design of tools to improve the reliability of Linux code. Nevertheless, the information is only meaningful if it is representative and can be interpreted correctly. In this thesis, we study a collection of kernel oopses over a period of 8 months from a repository that is maintained by Red Hat. We consider the overall features of the data, the degree to which the data reflects other information about Linux, and the interpretation of features that may be relevant to reliability. We find that the data correlates well with other information about Linux, but that it suffers from duplicate and missing information. We furthermore identify some potential pitfalls in studying features such as the sources of common faults and common failing applications. Furthermore, a kernel oops provides valuable first-hand information for a Linux kernel maintainer to conduct postmortem debugging, since it logs the status of the Linux kernel at the time of a crash. However, debugging based on only the information in a kernel oops is difficult. To help developers with debugging, we devised a solution to derive the offending line from a kernel oops, i.e., the line of source code that incurs the crash. For this, we propose a novel algorithm based on approximate sequence matching, as used in bioinformatics, to automatically pinpoint the offending line based on information about nearby machine-code instructions, as found in a kernel oops. Our algorithm achieves 92% accuracy compared to 26% for the traditional approach of using only the oops instruction pointer. We integrated the solution into a tool named OOPSA, which would relieve some burden for the developers with the kernel oops debugging.

L’adaptation et l’application des méthodes formelles de vérification et de développement à des systèmes et algorithmes distribués est un domaine de recherche très actif. Un des défis principaux réside dans la variété des modèles calculatoires qui existent en algorithmique répartie : des encodages naïfs conduisent à des espaces d’états dont la taille dépasse les capacités des outils les plus puissants de vérification. D’autre part, la complexité intrinsèque de ces algorithmes fait que leur correction n’est pas évidente même pour leurs concepteurs. Dans cette thèse on s’intéresse à l’analyse formelle de protocoles de robots mobiles, un modèle de calcul particulièrement original car les agents ne disposent ni de mémoire (locale ou partagée) ni de la capacité de communiquer par échange de messages. Un cadre général permettant d'exprimer les modèles robotiques est présenté dans cette thèse. Ce modèle a permit d'utiliser à la fois la vérification par model checking d’algorithmes proposés dans la littérature et la synthèse formelle d’algorithmes (optimaux) pour un problème donné, quelque soit le niveau d'asynchronisme du modèle robotique étudié. / The topic of autonomous mobile robots continues to generate a lot of interest in the algorithmic community, both from a purely theoretical perspective and from a more applicative one. The model is now well understood, and the problems under investigation are becoming more and more complex. Correctness proofs are usually very intricate and elaborate, often leaving margin of doubts. This thesis focuses on a new approach to formally study correctness in robots systems and to automatically generate algorithmic solutions. In fact, we propose a general framework to express robot models, and where automated technics like model checking and algorithm synthesis can be used, moreover we show their applicability in robots models under all possible synchronicity levels (from fully synchronous to fully asynchronous).

Cette thèse s'inscrit dans le domaine de l'optimisation combinatoire. Elle utilise l'approche polyèdrale pour résoudre des problèmes combinatoires qui se posent dans le contexte des réseaux de télécommunications. Nous introduisons et étudions le problème de synthèse de réseaux à composantes connexes unicycliques. Après avoir rappelé que le problème est facile à résoudre en absence d'autres contraintes, nous étudions de nouvelles variantes en intégrant de nouvelles contraintes techniques. Nous commençons par une contrainte portant sur la taille des cycles. Nous souhaitons interdire tous les cycles contenant au plus $p$ sommets. Le problème est alors NP-Difficile. Des inégalités valides sont alors proposées pour ce problème. On montre sous des conditions bien précises que ces inégalités peuvent être des facettes. Plusieurs algorithmes polynomiaux ont été proposés pour la séparation des inégalités valides. Ces algorithme sont mis en oeuvre et des résultats numériques sont donnés. Nous nous focalisons par la suite sur un nouveau problème dit de Steiner consistant à partitionner un réseau en composantes unicycliques tout en imposant que certains sommets soient sur les cycles. On montre alors que ce problème est facile au sens de la complexité algorithmique en proposant un algorithme polynomial et une formulation étendue du problème. On présente également une description partielle de l'enveloppe convexe des vecteurs d'incidence de ces réseaux. La séparation des inégalités est également étudiée. Nous proposons notamment une généralisation de l'algorithme de Padberg-Rao pour séparer les inégalités Blossom. D'autres contraintes techniques sont prises en compte : contraintes de degrés, contrainte sur le nombre de composantes connexes, appartenance de certains sommets à une même composante connexe et enfin la séparation de certains sommets qui doivent être sur des composantes différentes. Enfin, nous faisons une étude spectrale de deux classes spécifiques de graphes unicycliques. / In this thesis, we use the polyhedral approach to solve combinatorial problems in telecommunications context. First, we introduce the problem of network design with unicyclic connected components. We recall that without other constraints, our problem is easy to solve, and we propose a study with new technical constraints. We start our study by adding constraints on the size of cycles. We aim to obtain unicyclic components such that the size of each cycle is not lower than a certain p. This problem is NP-Hard. We describe some valid inequalities for the design of unicyclic graphs with girth constraints. The faces induced by these valid inequalities are also studied. Some of them can be separated in polynomial time. A cutting plane algorithm based on these inequalities is implemented to solve the problem. Furthermore, we focus on a Steiner type problem, which consists in partitioning the graph to unicyclic components, such that some given vertices belong to a cycle. We prove then that our problem is easy to solve, and we propose an exact extended formulation and a partial description of the convex hull of the incidence vectors of our Steiner network problem. Polynomial time separation algorithms are described. One of them is a generalization of the Padberg&Rao algorithm to separate blossom inequalities. Other technical constraints are proposed such as degree constraints, a bound of the number of unicyclic components, constraints related to whether some given pairs of vertices belong to the same component or to different components. Finally, we study the spectra of two specified classes of unicyclic graphs.

L’évolution des supercalculateurs, de leur origine dans les années 60 jusqu’à nos jours, a fait face à 3 révolutions : (i) l’arrivée des transistors pour remplacer les triodes, (ii) l’apparition des calculs vectoriels, et (iii) l’organisation en grappe (clusters). Ces derniers se composent actuellement de processeurs standards qui ont profité de l’accroissement de leur puissance de calcul via une augmentation de la fréquence, la multiplication des cœurs sur la puce et l’élargissement des unités de calcul (jeu d’instructions SIMD). Un exemple récent comportant un grand nombre de cœurs et des unités vectorielles larges (512 bits) est le co-proceseur Intel Xeon Phi. Pour maximiser les performances de calcul sur ces puces en exploitant aux mieux ces instructions SIMD, il est nécessaire de réorganiser le corps des nids de boucles en tenant compte des aspects irréguliers (flot de contrôle et flot de données). Dans ce but, cette thèse propose d’étendre la transformation nommée Deep Jam pour extraire de la régularité d’un code irrégulier et ainsi faciliter la vectorisation. Ce document présente notre extension et son application sur une mini-application d’hydrodynamique multi-matériaux HydroMM. Ces travaux montrent ainsi qu’il est possible d’obtenir un gain de performances significatif sur des codes irréguliers. / Since the 60s to the present, the evolution of supercomputers faced three revolutions : (i) the arrival of the transistors to replace triodes, (ii) the appearance of the vector calculations, and (iii) the clusters. These currently consist of standards processors that have benefited of increased computing power via an increase in the frequency, the proliferation of cores on the chip and expansion of computing units (SIMD instruction set). A recent example involving a large number of cores and vector units wide (512-bit) is the co-proceseur Intel Xeon Phi. To maximize computing performance on these chips by better exploiting these SIMD instructions, it is necessary to reorganize the body of the loop nests taking into account irregular aspects (control flow and data flow). To this end, this thesis proposes to extend the transformation named Deep Jam to extract the regularity of an irregular code and facilitate vectorization. This thesis presents our extension and application of a multi-material hydrodynamic mini-application, HydroMM. Thus, these studies show that it is possible to achieve a significant performance gain on uneven codes.

L'objectif principal de cette thèse est de développer un algorithme dynamique de partitionnement de données (classification non supervisée ou " clustering " en anglais) qui ne se limite pas à des concepts statiques et qui peut gérer des distributions qui évoluent au fil du temps. Cet algorithme peut être utilisé dans les systèmes de surveillance du processus, mais son application ne se limite pas à ceux-ci. Les contributions de cette thèse peuvent être présentées en trois groupes: 1. Contributions au partitionnement dynamique de données en utilisant : un algorithme de partitionnement dynamique basé à la fois sur la distance et la densité des échantillons est présenté. Cet algorithme ne fait aucune hypothèse sur la linéarité ni la convexité des groupes qu'il analyse. Ces clusters, qui peuvent avoir des densités différentes, peuvent également se chevaucher. L'algorithme développé fonctionne en ligne et fusionne les étapes d'apprentissage et de reconnaissance, ce qui permet de détecter et de caractériser de nouveaux comportements en continu tout en reconnaissant l'état courant du système. 2. Contributions à l'extraction de caractéristiques : une nouvelle approche permettant d'extraire des caractéristiques dynamiques est présentée. Cette approche, basée sur une approximation polynomiale par morceaux, permet de représenter des comportements dynamiques sans perdre les informations relatives à la magnitude et en réduisant simultanément la sensibilité de l'algorithme au bruit dans les signaux analysés. 3. Contributions à la modélisation de systèmes à événements discrets évolutifs a partir des résultats du clustering : les résultats de l'algorithme de partitionnement sont utilisés comme base pour l'élaboration d'un modèle à événements discrets du processus. Ce modèle adaptatif offre une représentation du comportement du processus de haut niveau sous la forme d'un automate dont les états représentent les états du processus appris par le partitionnement jusqu'à l'instant courant et les transitions expriment l'atteignabilité des états. / The main objective of this thesis is to propose a dynamic clustering algorithm that can handle not only dynamic data but also evolving distributions. This algorithm is particularly fitted for the monitoring of processes generating massive data streams, but its application is not limited to this domain. The main contributions of this thesis are: 1. Contribution to dynamic clustering by the proposal of an approach that uses distance- and density-based analyses to cluster non-linear, non-convex, overlapped data distributions with varied densities. This algorithm, that works in an online fashion, fusions the learning and lassification stages allowing to continuously detect and characterize new concepts and at the same time classifying the input samples, i.e. which means recognizing the current state of the system in a supervision application. 2. Contribution to feature extraction by the proposal of a novel approach to extract dynamic features. This approach ,based on piece-polynomial approximation, allows to represent dynamic behaviors without losing magnitude related information and to reduce at the same time the algorithm sensitivity to noise corrupting the signals. 3. Contribution to automatic discrete event modeling for evolving systems by exploiting informations brought by the clustering. The generated model is presented as a timed automaton that provides a high-level representation of the behavior of the process. The latter is adaptive in the sense that its construction is elaborated following the discovery of new concepts by the clustering algorithm.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Un défi majeur pour les programmeurs, en particulier pour les novices, est de comprendre les messages d'erreurs émis par le compilateur. Nous nous intéresserons au problème d'affichage de bon message d'erreur de compilation. Dans certains langages, tels que Typer, la vérification du type des expressions est faite lors de la compilation; ce qui oblige le compilateur à déduire les types de certaines ou de toutes les expressions; mais aussi d'envisager la meilleure manière d'écrire le type (dans le langage source) dans un message d'erreur (ce qui est infaisable pour le moment dans Typer). Cependant l'interprétation du type des expressions faite par le compilateur est toujours différente de ce que l'utilisateur aimerait voir en cas d'erreur de compilation. En effet, lorsque le code source est converti en une représentation interne via une fonction complexe (appelée \Code{elaborate}), il peut être difficile de trouver une correspondance entre le type "t\_source" (type du code source) et le type "t\_interne" (type de la représentation interne du code source) en cas d'erreur. Parfois, "t\_source" peut ne pas être disponible ou même n'avoir jamais existé car "t\_interne" a été créé de toute pièce par inférence de type. Il peut donc être difficile de trouver un "t\_source" correspondant, d'autant plus qu'il doit être clair et compréhensible pour le programmeur. En d'autres termes, il n'existe pas d'algorithme déterministe permettant de trouver une représentation naturelle dans le code source correspondant à la représentation interne d'un type. D'où l'importance d'implémenter un système heuristique tel que les algorithmes génétiques ou les réseaux de neurones qui nous donne cette information, permettant ainsi une meilleure affichage du texte des messages d'erreurs. Nous avons donc décidé de travailler sur l'amélioration des messages d'erreur du compilateur Typer, dans sa phase de traduction du langage (interprétation et représentation des différentes expressions dans le langage source) en proposant une approche basée sur les algorithmes génétiques. \\ / A major challenge for programmers, especially for novices, is to understand the error messages issued by the compiler. We are interested in the problem of displaying correct compiler error messages. In some languages, such as Typer, the type checking of expressions is done at compile time; this forces the compiler to deduce the types of some or all expressions; but also to consider the best way to write the type (in the source language) in an error message (which is unfeasible for the moment in Typer). However, the interpretation of the type of expressions made by the compiler is always different from what the user would like to see in case of a compilation error. Indeed, when the source code is converted into an internal representation via a complex function (called ‘elaborate’), it can be difficult to find a correspondence between the type "t_source" (type of the source code) and the type "t_interne" (type of the internal representation of the source code) in case of error. Sometimes, "t_source" may not be available or even have never existed because "t_interne" was created from scratch by type inference. It can therefore be difficult to find a corresponding "source_t", especially since it must be clear and understandable for the programmer. In other words, there is no deterministic algorithm to find a natural representation in the source code corresponding to the internal representation of a type. Hence the importance of implementing a heuristic system such as genetic algorithms or neural networks that gives us this information; thus allowing a better display of the text of error messages. We therefore decided to work on the improvement of the error messages of the Typer compiler, in its language translation phase (interpretation and representation of the different expressions in the source language) by proposing an approach based on genetic algorithms.