Στην διπλωματική εργασία παρουσιάζεται μια νέα δομή δεδομένων ειδικά σχεδιασμένη για δίκτυα μεταφορών ευρείας κλίμακας τα οποία αλλάζουν δυναμικά. Η νέα δομή δεδομένων γραφημάτων μας παρέχει ταυτόχρονα τρία μοναδικά χαρακτηρισ τικά: 1. Σύμπτυξη(Compactness): ικανότητα να προσπελάσει αποδοτικά διαδοχικές κορυφές και ακμές, μια απαίτηση όλων των αλγορίθμων γραφημάτων). 2. Ευκινησία (Agility): ικανότητα να αλλάξει και να ρυθμίσει εξαρχής την εσωτερική της διάταξη με σκοπό να βελτιώσει την τοπικότητα των αναφορών των στοιχείων, σύμφωνα με έναν δεδομένο αλγόριθμο. 3. Δυναμικότητα (Dynamicity): ικανότητα να ενθέσει ή να διαγράψει αποδοτικά κορυφές και ακμές. Όλες οι προηγούμενες γνωστές δομές γραφημάτων δεν υποστήριζαν τουλάχιστον ένα από τα προηγούμενα χαρακτηριστικά ή/και δεν μπορούσαν να εφαρμοστούν σε δυναμικά δίκτυα μεταφορών ευρείας κλίμακας. Σε αυτή τη διπλωματική εργασία, παρουσιάζεται η πρακτικότητα της νέας δομής γραφημάτων εκτελώντας μια εκτενή πειραματική μελέτη για δρομολόγηση συντομότερων διαδρομών σε Ευρωπαϊκά οδικά δίκτυα ευρείας κλίμακας με μερικές δεκάδες εκατομμύρια κορυφές και ακμές. Χρησιμοποιώντας κλασικούς αλγόριθμους εύρεσης συντομότερων διαδρομών, επιτυγχάνονται εύκολα χρόνοι ερωτημάτων από μια αρχική κορυφή σε μια τελική κορυφή της τάξης των milliseconds, ενώ η νέα δομή γραφημάτων μας μπορεί να ενημερωθεί σε μόλις μερικά microseconds μετά από μια ένθεση ή διαγραφή μιας κορυφής ή ακμής. / We present a new graph data structure specifically suited for large scale transportation networks in dynamic scenario. Our graph data structure provides tree unique characteristics, namely compactness, agility and dynamicity. All previous data structures were lacking support in at least one of the aforementioned characteristics. We demonstrate the practicality of the new graph data structure by conducting experiments on large scale European road networks, achieving query times of classical routing algorithms in the order of milliseconds and update times in the order of a few microseconds.

Ces dernières années, les techniques d'imagerie ont fait l'objet de beaucoup d'améliorations. Elles permettent de fournir des images numériques 2D ou 3D précises de zones parfois invisibles à l’œil nu. Ces techniques s'appliquent dans de nombreux domaines comme l'industrie cinématographique, la photographie ou l'imagerie médicale... Dans cette thèse, l'imagerie sera utilisée pour effectuer des simulations numériques en la couplant avec un solveur éléments finis. Nous présenterons, en premier lieu, la morphologie mathématique et la méthode d'immersion d'image. Elles permettront l'extraction d'informations permettant la transformation d'une image dans un maillage exploitable. Puis, une méthode itérative d'adaptation de maillage basée sur un estimateur d'erreur sera utilisée afin de construire un maillage optimal. Ainsi, un maillage sera construit uniquement avec les données d'une image. Nous proposerons également une nouvelle méthodologie pour construire une fonction régulière a l'aide d'une méthode de réinitialisation de la distance signée. Deux avantages sont à noter : l'utilisation de la fonction régularisée permet une bonne adaptation de maillage. De plus, elle est directement utilisable par le solveur éléments finis. Les simulations numériques sont donc réalisées en couplant éléments finis stabilisés, adaptation de maillage anisotrope et réinitialisation. L'objectif de cette thèse est donc de simplifier le calcul numérique à partir d'image, d'améliorer la précision numérique, la construction d'un maillage automatique et de réaliser des calculs numériques parallèles efficaces. Les applications envisagées peuvent être dans le domaine médical, de la physique des matériaux ou du design industriel. / Imaging techniques have well improved in the last decades. They may accurately provide numerical descriptions from 2D or 3D images, opening perspectives towards inner information, not seen otherwise, with applications in different fields, like medicine studies, material science or urban environments. In this work, a technique to build a numerical description under the mesh format has been implemented and used in numerical simulations when coupled to finite element solvers. Firstly, mathematical morphology techniques have been introduced to handle image information, providing the specific features of interest for the simulation. The immersed image method was then proposed to interpolate the image information on a mesh. Then, an iterative anisotropic mesh adaptation operator was developed to construct the optimal mesh, based on the estimated error concerning the image interpolation. The mesh is thus directly constructed from the image information. We have also proposed a new methodology to build a regularized phase function, corresponding to the objects we wish to distinguish from the image, using a redistancing method. Two main advantages of having such function are: the gradient of the regularized function performs better for mesh adaptation; the regularized function may be directly used for the finite element solver. Stabilized finite element flow and advection solvers were coupled to the constructed anisotropic mesh and the redistancing function, allowing its application to multiphase flow numerical simulations. All these developments have been extended in a massively parallel context. An important objective of this work is the simplification of the image based computations, through a modified way to segment the image and by coupling all to an automatic way to construct the mesh used in the finite element simulations.

Alors que la complexité des fonctions d'ordre 1 est bien définie et étudiée, il n'existe pas de notion satisfaisante à tout ordre. Une telle théorie existe déjà à l'ordre 2 et permet de définir une classe analogue aux fonctions calculables en temps polynomial usuelles. Cela est tout particulièrement intéressant dans le domaine de l'analyse récursive où l'on peut représenter, entre autres, les nombres et les fonctions réelles par des fonctions d'ordre 1. On peut alors remarquer un lien fort entre calculabilité et continuité, et aussi rapprocher la complexité avec certaines propriétés analytiques, ce que nous illustrons dans le cas des opérateurs réels. Nous prouvons cependant que, du point de vue de la complexité, les fonctions d'ordre 1 ne permettent pas de représenter fidèlement certains espaces mathématiques. Ce résultat appuie tout particulièrement la nécessité d'une théorie de la complexité d'ordre supérieur. Nous développons alors un modèle de calcul basé sur la sémantique des jeux, où l'application de deux fonctions est représentée par la confrontation de deux stratégies dans un jeu. En définissant la taille de telles stratégies, nous pouvons déduire une notion robuste et pertinente de complexité pour ces stratégies et donc pour les fonctions d'ordre supérieur. Nous définissons aussi une classe de fonctions calculables en temps polynomial qui paraît être un bon candidat pour définir une classe de complexité raisonnable à tout ordre / While first order complexity is well defined and studied, higher order lacks a satisfactory notion of complexity. Such a theory already exists at order 2 and provides a complexity class analogue to usual polynomial time computable functions. This is already especially interesting in the domain of computable analysis, where real numbers or real functions for example can be represented by first order functions. In particular, there is a clear link between computability and continuity, and we also illustrate in the case of real operators that complexity can be related to some analytical properties. However, we prove that, from a complexity point of view, some mathematical spaces can not be faithfully represented by order 1 functions and require higher order ones. This result underlines that there is a need to develop a notion of complexity at higher types which will be, in particular but not only, useful to computable analysis. We have developed a computational model for higher type sequential computations based on a game semantics approach, where the application of two functions is represented by the game opposing two strategies. By defining the size of such strategies, we are able to define a robust and meaningful notion of complexity at all types, together with a class of polynomial time computable higher order functionals which seems to be a good candidate for a class of feasible functionals at higher types

En informatique, la notion de ressource est une notion centrale. Nous considérons comme ressource toute entité pouvant être composée ou décomposée en sous-entités. Plusieurs logiques ont été proposées afin de modéliser et d’exprimer des propriétés sur celles-ci, comme la logique BI exprimant des propriétés de partage et de séparation. Puisque les systèmes informatiques manipulent des ressources, la proposition de nouveaux modèles capturant la dynamique de ces ressources, ainsi que la vérification et la preuve de propriétés sur ces modèles, sont des enjeux cruciaux. Dans ce contexte, nous définissons de nouvelles logiques permettant la modélisation logique de la dynamique des ressources, proposant de nouveaux modèles et permettant l’expression de nouvelles propriétés sur cette dynamique. De plus, pour ces logiques, nous proposons des méthodes des tableaux et d’extraction de contre-modèles. Dans un premier temps, nous définissons de nouveaux réseaux de Petri, nommés ß-PN, et proposons une nouvelle sémantique à base de ß-PN pour BI. Puis nous proposons une première extension modale de BI, nommée DBI, permettant la modélisation de ressources ayant des propriétés dynamiques, c’est-à-dire évoluant en fonction de l’état courant d’un système. Ensuite, nous proposons une logique, nommée DMBI, modélisant des systèmes manipulant/produisant/consommant des ressources. Par ailleurs, nous proposons une nouvelle logique (LSM) possédant de nouvelles modalités multiplicatives (en lien avec les ressources). Pour finir, nous introduisons la séparation au sein des logiques épistémiques, obtenant ainsi une nouvelle logique ESL, exprimant de nouvelles propriétés épistémiques / In computer science, the notion of resource is a central concern. We consider as a resource, any entity that can be composed or decomposed into sub-entities. Many logics were proposed to model and express properties on these resources, like BI logic, a logic about sharing and separation of resources. As the computer systems manipulate resources, a crucial issue consists in providing new models that capture the dynamics of resources, and also in verifying and proving properties on these models. In this context, we define new logics with new models and new languages allowing to respectively capture and express new properties on the dynamics of resources. Moreover, for all these logics, we also study the foundations of proof search and provide tableau methods and counter-model extraction methods. After defining new Petri nets, called ß-PN, we propose a new semantics based on ß-PN for BI logic, that allows us to show that BI is able to capture a kind of dynamics of resources. After observing that it is necessary to introduce new modalities in BI logic, we study successively different modal extensions of BI. We define a logic, called DBI, that allows us to model resources having dynamic properties, meaning that they evolve during the iterations of a system. Then, we define a logic, called DMBI, that allows us to model systems that manipulate/produce/consume resources. Moreover, we define a new modal logic, called LSM, having new multiplicative modalities, that deals with resources. Finally, we introduce the notion of separation in Epistemic Logic, obtaining a new logic, called ESL, that models and expresses new properties on agent knowledge

Cette thèse de doctorat est une investigation des logiques de la connaissance, de la croyance et de la dynamique d'information, en utilisant des outils de topologie et logique épistémique (dynamique). La partie I concerne les interprétations fondées sur des preuves de croyances justifiées et connaissance. Commencer par une interprétation topologique des connaissances désormais standard en tant qu'opérateur intérieur, nous développons, de manière progressive, un cadre qui (1) peut parler de preuves non seulement sémantiquement, mais aussi le niveau syntaxique, rendant ainsi la notion de preuve plus explicite; (2) prend la preuve comme la notion la plus primitive, et définit la croyance et la connaissance purement basé sur elle. Dans la partie II de cette dissertation, nous nous concentrons sur notions de connaissances ainsi que divers types de dynamique de l'information comprenant apprendre de nouvelles preuves. Plus précisément, cette partie est centrée autour des notions de certaines connaissances et savoir-faire en tant que «connaissances potentielles», ainsi que les liens entre la notion abstraite d'effort épistémique englobant toute méthode l'acquisition de preuves et les attitudes dynamiques bien étudiées telles que les annonces publiques arbitraires. Pour résumer, cette thèse réinterprète d'une part certaines logiques épistémiques et doxastiques existantes et leurs extensions dynamiques d'un point de vue topologique, fournissant une interprétation fondée sur des preuves. D'un autre côté, elle utilise des outils topologiques pour affiner et étendre les analyses antérieures, conduisant à de nouvelles logiques de la dynamique des preuves et de l'information / This dissertation brings together epistemic logic and topology. It studies formal representations of the notion of evidence and its link to justification, justified belief, knowledge, and evidence-based information dynamics, by using tools from topology and (dynamic) epistemic logic. Part I is concerned with evidence-based interpretations of justified belief and knowledge. Starting with a by-now-standard topological interpretation of knowledge as the interior operator, we develop, in a gradual manner, a topological framework that (1) can talk about evidence not only semantically, but also at the syntactic level, thereby making the notion of evidence more explicit; (2) takes evidence as the most primitive notion, and defines belief and knowledge purely based on it, thereby linking these two crucial notions of epistemology at a deeper, more basic level. In Part II of this dissertation, we focus on notions of knowledge as well as various types of information dynamics comprising learning new evidence. More precisely, this part is centered around the notions of absolutely certain knowledge and know ability as "potential knowledge", as well as the connections between the abstract notion of epistemic effort encompassing any method of evidence acquisition and the well-studied dynamic attitudes such as public and arbitrary public announcements. To sum up, this dissertation on one hand re-interprets some existing epistemic and doxastic logics and their dynamic extensions from a topological perspective, providing an evidence-based interpretation. On the other hand, it uses topological tools to refine and extend earlier analysis, leading to novel logics of evidence and information dynamics

Les FPGA (Field Programmable Gate Arrays) constituent un type de circuit reprogrammable qui, sous certaines conditions, peuvent avoir de meilleures performances que les microprocesseurs classiques. Les FPGA utilisent le circuit comme paradigme de programmation, ce qui permet d'effectuer des calculs parallèles propres à l'application visée. Ils permettent aussi d’atteindre l’efficacité arithmétique: un bit ne doit être calculé que s'il est utile dans le résultat final. Pour ce faire, l’arithmétique utilisée par les FPGA ne peut se limiter qu’à des fonctions conçues pour les microprocesseurs. Cette thèse se propose d’étudier les méthodes pour l’implémentation des fonctions gros-grain pour les FPGA à travers trois voies. De nouvelles méthodes pour évaluer des fonctions trigonométriques, telles que le sinus, cosinus et arc tangente ont été développés dans cette thèse. Chaque méthode est optimisée dans son contexte, de la manière la plus flexible et la plus souple possible. Pour que les méthodes aboutissent à leur efficacité arithmétique, il est nécessaire de procéder à une analyse d'erreurs, ainsi qu’à un choix attentif des paramétrés de la méthode et à une fine compréhension des algorithmes utilisés. Les filtres numériques constituent une famille importante d’opérateurs arithmétiques qui rassemble des fonctions élémentaires. Ils peuvent être spécifiés à un niveau élevé d'abstraction, à travers une fonction de transfert avec des contraintes sur le rapport signal/bruit. Ils peuvent être ensuite implémentés comme des chemins de données basés sur des additions et des multiplications. Le principal résultat est donc une méthode qui transforme une spécification de haut niveau en une implémentation d’une façon automatique. La première étape se rapporte au développement d'une méthode pour le calcul des produits par des constantes. Des filtres FIR et IIR peuvent être construits à l'aide de cette brique de base. Pour que les opérateurs arithmétiques atteignent leur performance maximale, on a besoin d’un pipeline correspondant au contexte donné. Même si les connaissances du développeur s’avèrent d’un grand avantage pendant le processus de création d'un pipeline d'un chemin de données, cette étape demeure complexe et facilement susceptible à des erreurs. Une méthode automatique, contrôlée par le développeur a dont été développée. Cette thèse fournit un générateur des opérateurs arithmétiques de haute qualité près à l'emploi, et qui propagent le domaine des calculs sur des FPGA à un pas plus proche de l’adoption générale. Les cœurs arithmétiques font partie d'un générateur open-source, où les fonctions peuvent être décrites par une spécification de haut niveau, comme par exemple une formule mathématique. / Field-Programmable Gate Arrays (FPGAs) have been shown to sometimes outperform mainstream microprocessors. The circuit paradigm enables efficient application-specific parallel computations. FPGAs also enable arithmetic efficiency: a bit is only computed if it is useful to the final result. To achieve this, FPGA arithmetic shouldn’t be limited to basic arithmetic operations offered by microprocessors. This thesis studies the implementation of coarser operations on FPGAs, in three main directions: New FPGA-specific approaches for evaluating the sine, cosine and the arctangent have been developed. Each function is tuned for its context and is as versatile and flexible as possible. Arithmetic efficiency requires error analysis and parameter tuning, and a fine understanding of the algorithms used. Digital filters are an important family of coarse operators resembling elementary functions: they can be specified at a high level as a transfer function with constraints on the signal/noise ratio, and then be implemented as an arithmetic datapath based on additions and multiplications. The main result is a method which transforms a high-level specification into a filter in an automated way. The first step is building an efficient method for computing sums of products by constants. Based on this, FIR and IIR filter generators are constructed. For arithmetic operators to achieve maximum performance, context-specific pipelining is required. Even if the designer’s knowledge is of great help when building and pipelining an arithmetic datapath, this remains complex and error-prone. A user-directed, automated method for pipelining has been developed. This thesis provides a generator of high-quality, ready-made operators for coarse computing cores, which brings FPGA-based computing a step closer to mainstream adoption. The cores are part of an open-ended generator, where functions are described as high-level objects such as mathematical expressions.

L'étude non destructive du bois à partir de scanners à rayons X nécessite d’imaginer de nouvelles solutions adaptées à l'analyse des images. Préoccupation à la fois de la recherche agronomique et du milieu industriel des scieries, la segmentation des nœuds de bois est un défi majeur en termes de robustesse aux spécificités de chaque espèce et aux conditions d'acquisition des images. Les travaux menés dans cette thèse permettent de proposer un processus de segmentation en deux phases. Il isole d'abord chaque nœud dans une zone réduite puis segmente le nœud unique de chaque zone. Les solutions proposées pour chaque phase permettent d'intégrer les connaissances sur l'organisation interne du tronc et les mécanismes inhérents à sa croissance, à travers des outils classiques du traitement et de l'analyse d'image. La première phase repose en grande partie sur un principe de détection du mouvement emprunté à l'analyse vidéo et revisité. Deux approches de segmentation sont ensuite proposées, considérant pour l'une les coupes tomographiques initiales, et pour l'autre de nouvelles coupes ré-échantillonnées pour chaque nœud, orthogonalement à sa trajectoire. L'intégralité du processus a été implémenté dans un logiciel dédié aussi bien à l'expérimentation et la validation de l'approche qu'aux échanges interdisciplinaires. Le support applicatif du bois souligne la capacité de spécialisation des algorithmes génériques du traitement et de l'analyse d'image, et la pertinence de l'intégration de connaissances a priori dans cette optique / The non-destructive study of wood from X-Ray CT scanners requires to imagine new solutions adapted to analysis of images. Relating both agronomic research and industrial sector of sawmills, segmentation of wood knots is a major challenge in terms of robustness to specificities of each species and to image acquisition conditions. The works carried out in this thesis allow to propose a segmentation process in two phases. It first isolates each knot in a reduced area then it segments the unique knot of each area. Proposed solutions for each phase allow to integrate knowledges about internal organization of trunk and mechanisms inherent to its growth, through classical tools of image analysis and processing. The first phase is essentially based on a movement detection principle borrowed from video analysis and revisited. Two segmentation approaches are then proposed, considering for one the initial CT slices and for the other news slices resampled for each knot orthogonally to its trajectory. The complete process has been implemented in a software dedicated both for experimentation and validation of approach, and to interdisciplinary dialogs. The applicative support of wood emphasizes the specialization abilities of generic image analysis and processing algorithms, and the relevance to integrate priori knowledges in this perspective

Dans cette thèse, nous nous concentrons sur le développement des méthodes d'optimisation pour résoudre certaines classes de problèmes d'apprentissage avec la parcimonie et/ou avec l'incertitude des données. Nos méthodes sont basées sur la programmation DC (Difference of Convex functions) et DCA (DC Algorithms) étant reconnues comme des outils puissants d'optimisation. La thèse se compose de deux parties : La première partie concerne la parcimonie tandis que la deuxième partie traite l'incertitude des données. Dans la première partie, une étude approfondie pour la minimisation de la norme zéro a été réalisée tant sur le plan théorique qu'algorithmique. Nous considérons une approximation DC commune de la norme zéro et développons quatre algorithmes basées sur la programmation DC et DCA pour résoudre le problème approché. Nous prouvons que nos algorithmes couvrent tous les algorithmes standards existants dans le domaine. Ensuite, nous étudions le problème de la factorisation en matrices non-négatives (NMF) et fournissons des algorithmes appropriés basés sur la programmation DC et DCA. Nous étudions également le problème de NMF parcimonieuse. Poursuivant cette étude, nous étudions le problème d'apprentissage de dictionnaire où la représentation parcimonieuse joue un rôle crucial. Dans la deuxième partie, nous exploitons la technique d'optimisation robuste pour traiter l'incertitude des données pour les deux problèmes importants dans l'apprentissage : la sélection de variables dans SVM (Support Vector Machines) et le clustering. Différents modèles d'incertitude sont étudiés. Les algorithmes basés sur DCA sont développés pour résoudre ces problèmes. / In this thesis, we focus on developing optimization approaches for solving some classes of optimization problems in sparsity and robust optimization for data uncertainty. Our methods are based on DC (Difference of Convex functions) programming and DCA (DC Algorithms) which are well-known as powerful tools in optimization. This thesis is composed of two parts: the first part concerns with sparsity while the second part deals with uncertainty. In the first part, a unified DC approximation approach to optimization problem involving the zero-norm in objective is thoroughly studied on both theoretical and computational aspects. We consider a common DC approximation of zero-norm that includes all standard sparse inducing penalty functions, and develop general DCA schemes that cover all standard algorithms in the field. Next, the thesis turns to the nonnegative matrix factorization (NMF) problem. We investigate the structure of the considered problem and provide appropriate DCA based algorithms. To enhance the performance of NMF, the sparse NMF formulations are proposed. Continuing this topic, we study the dictionary learning problem where sparse representation plays a crucial role. In the second part, we exploit robust optimization technique to deal with data uncertainty for two important problems in machine learning: feature selection in linear Support Vector Machines and clustering. In this context, individual data point is uncertain but varies in a bounded uncertainty set. Different models (box/spherical/ellipsoidal) related to uncertain data are studied. DCA based algorithms are developed to solve the robust problems

Dans la société moderne, le stress s’avère un problème omniprésent. Un stress permanent peut entraîner divers problèmes mentaux et physiques notamment pour des personnes confrontées à des situations d'urgence comme par exemple des pompiers en intervention: il peut modifier leurs actions et les mettre en danger. Par conséquent, dans ce contexte, il est pertinent de chercher à évaluer le stress de la personne. Sur la base de cette idée, a été proposé le projet Psypocket qui vise à concevoir un système portable capable d'analyser précisément l'état de stress d'une personne en fonction de ses modifications physiologiques, psychologiques et comportementales, puis de proposer des solutions de rétroaction pour réguler cet état. Cette thèse s’inscrit dans le cadre du projet Psypocket. Nous y discutons de la faisabilité et de l'intérêt de la reconnaissance du stress à partir de données hétérogènes. Non seulement les signaux physiologiques, tels que l'électrocardiographie (ECG), l'élecchtromyographie (EMG) et l'activité électrodermale (EDA), mais aussi le temps de réaction (RT) sont adoptés pour discriminer différents états de stress d'une personne. Pour cela nous proposons une approche basée sur un classifieur SVM (Machine à Vecteurs de Support). Les résultats obtenus montrent que le temps de réaction peut-être un moyen d’estimation du niveau de stress de l’individu en complément ou non des signaux physiologiques. En outre, nous discutons de la faisabilité d'un système embarqué à même de réaliser la chaîne globale de traitement des signaux. Cette thèse contribue donc à la conception d’un système portable de reconnaissance du stress d'une personne en temps réel en adoptant des données hétérogènes, en l’occurrence les signaux physiologiques et le temps de réaction / In modern society, the stress of an individual has been found to be a common problem. Continuous stress can lead to various mental and physical problems and especially for the people who always face emergency situations (e.g., fireman): it may alter their actions and put them in danger. Therefore, it is meaningful to provide the assessment of the stress of an individual. Based on this idea, the Psypocket project is proposed which is aimed at making a portable system able to analyze accurately the stress state of an individual based on his physiological, psychological and behavioural modifications. It should then offer solutions for feedback to regulate this state.The research of this thesis is an essential part of the Psypocket project. In this thesis, we discuss the feasibility and the interest of stress recognition from heterogeneous data. Not only physiological signals, such as Electrocardiography (ECG), Electromyography (EMG) and Electrodermal activity (EDA), but also reaction time (RT) are adopted to recognize different stress states of an individual. For the stress recognition, we propose an approach based on a SVM classifier (Support Vector Machine). The results obtained show that the reaction time can be used to estimate the level of stress of an individual in addition or not to the physiological signals. Besides, we discuss the feasibility of an embedded system which would realize the complete data processing. Therefore, the study of this thesis can contribute to make a portable system to recognize the stress of an individual in real time by adopting heterogeneous data like physiological signals and RT

Une Fonction Latticielle Polynômiale (FLP) sur un treillis L est une fonction p : Ln → L, qui peut être exprimée à partir de variables, de constantes et des opérateurs de treillis ∧ et ∨ . Dans les cas où L est distributif et borné, les FLP incluent les intégrales de Sugeno. Celles-ci sont des fonctions d'agrégation qui permettent de fusionner des valeurs sur des échelles ordinales non numériques, et qui sont utilisées notamment dans l'approche qualitative de l'Aide à la Décision Multi Critères en tant qu'alternatives ordinales aux intégrales de Choquet. Dans une première partie, nous traitons la tâche d'interpolation par des FLP, c'est à dire : pour un treillis L, un sous-ensemble fini D de Ln et une fonction f : D → L, retourner une FLP p : Ln → L telle que p(x) = f(x) pour tout x ∊ D (si une telle FLP existe). Nous traitons successivement le cas où L est un treillis fini et le cas où L est une treillis distributif borné. Dans les deux cas, nous donnons des algorithmes qui résolvent ce problème en temps polynomial. Dans une seconde partie, nous abordons les généralisations des intégrales de Sugeno appelées Fonctions d'Utilité de Sugeno (FUS), qui permettent la fusion de valeurs appartenant à des échelles ordinales différentes, ainsi que leur application à la tâche de classification monotone. Nous introduisons un modèle composé de plusieurs FUS, ainsi qu'un algorithme d'apprentissage d'un tel modèle. Nous comparons ce modèle aux ensembles de règles de décision appris par VC-DomLEM, et étudions le nombre de FUS nécessaires afin de modéliser des données empiriques / A Lattice Polynomial Function (LPF) over a lattice L is a map p : Ln → L that can be defined by an expression involving variables, constants and the lattice operators ∧ and ∨. If L is a distributive lattice, these maps include the so-called Sugeno integrals that are aggregation functions capable of merging ordinal values, not necessarily numerical. They are widely used in the qualitative approach to Multiple Criteria Decision Aiding (MCDA), and they can be thought of as the ordinal counterparts of Choquet integrals. In the first part of this thesis, we tackle the task of interpolating a partial function by an LPF, stated as follows: for a lattice L, a finite subset D of Ln, and a function f : D → L, return an LPF p : Ln → L such that p(x) = f(x) for all x ∊ D (if such an LPF exists). We treat the cases where L is a finite lattice, and then the cases where L is a bounded distributive lattice. In both cases, we provide algorithms that solve this problem in polynomial time. In the second part, we consider generalizations of Sugeno integrals in the multi-attribute setting, in particular, the Sugeno Utility Functions (SUFs), that are able to merge values coming from different ordinal scales. We consider the their use in monotonic classification tasks. We present a model based on a set of SUFs and an algorithm for learning such model from data. We compare this model to the sets of monotonic decision rules learned by VC-DomLEM, and study the number of SUFs that are required in order to model empirical data