Stimulé par des applications comme l’annotation de documents ou d’images, l’apprentissage multi-label a connu un fort développement cette dernière décennie. Mais les algorithmes classiques se heurtent aux nouveaux volumes des données multi-label extrême (XML) où le nombre de labels peut atteindre le million. Cette thèse explore trois directions pour aborder la complexité en temps et en mémoire du problème : la réduction de dimension multi-label, les astuces d’optimisation et d’implémentation et le découpage arborescent. Elle propose d’unifier les approches de réduction à travers une typologie et deux formulations génériques et d’identifier des plus performantes avec une méta-analyse originale des résultats de la littérature. Une nouvelle approche est développée pour analyser l’apport du couplage entre le problème de réduction et celui de classification. Pour réduire la complexité mémoire en maintenant les capacités prédictives, nous proposons également un algorithme d’estimation des plus grands paramètres utiles d’un modèle classique de régression one-vs-rest qui suit une stratégie inspirée de l’analyse de données en flux. Enfin, nous présentons un nouvel algorithme CRAFTML qui apprend un ensemble d’arbres de décision diversifiés. Chaque arbre effectue une réduction aléatoire conjointe des espaces d’attributs et de labels et implémente un partitionnement récursif très rapide. CRAFTML est plus performant que les autres méthodes arborescentes XML et compétitif avec les meilleures méthodes qui nécessitent des supercalculateurs. Les apports de la thèse sont complétés par la présentation d’un outil logiciel VIPE développé avec Orange Labs pour l’analyse d’opinions multi-label. / Stimulated by many applications such as documents or images annotation, multilabel learning have gained a strong interest during the last decade. But, standard algorithms cannot cope with the volumes of the recent extreme multi-label data (XML) where the number of labels can reach millions. This thesis explores three directions to address the complexity in time and memory of the problem: multi-label dimension reduction, optimization and implementation tricks, and tree-based methods. It proposes to unify the reduction approaches through a typology and two generic formulations and to identify the most efficient ones with an original meta-analysis of the results of the literature. A new approach is developed to analyze the interest of coupling the reduction problem and the classification problem. To reduce the memory complexity of a classical one-vs-rest regression model while maintaining its predictive performances, we also propose an algorithm for estimating the largest useful parameters that follows a strategy inspired by data stream analysis. Finally, we present a new algorithm called CRAFTML that learns an ensemble of diversified decision trees. Each tree performs a joint random reduction of the feature and the label spaces and implements a very fast recursive partitioning strategy. CRAFTML performs better than other XML tree-based methods and is competitive with the most accurate methods that require supercomputers. The contributions of the thesis are completed by the presentation of a software called VIPE that is developed with Orange Labs for multilabel opinion analysis.

Cette thèse propose une extension multi-dimensionnelle des liens entre mots sturmiens, fractions continues et reconnaissance de droite discrète. Les notions principales sont celles de substitution généralisée (ou application duale), de flip (une transformation élémentaire courante en mécanique statistique) et de fractions continues multi-dimensionnelles (algorithme de Brun). On montre notamment comment définir et calculer des développements en fractions continues de plans ou de surfaces discrets.

Th. doct.-ing.--Autom.--Toulouse 3, 1977. N°: 584.

Le présent travail traite de problèmes particuliers en traitement de signal soulevés par l'holographie digitale. Le premier chapitre présente l'holographie et l'holographie digitale. Le deuxième chapitre aborde le problème des artéfacts apparaissant sur le bord des hologrammes lorsque ceux-ci sont propagés numériquement. Le troisième chapitre propose une méthode automatique pour éliminer la phase de fond d'un hologramme. Le quatrième chapitre montre comment améliorer la visibilité des hologrammes en supprimant les objets diffractants. Le cinquième chapitre expose un logiciel d'aide à l'analyse des hologrammes enregistrés dans le temps. On montre la capacité du logiciel à effectuer du tracking d'objets en trois dimensions à posteriori. Le sixième chapitre traite de la reconnaissance de forme dans les hologrammes, le problème de la reconnaissance de particules micrométriques est abordé. Des conclusions et perspectives terminent le travail.

Many-core architectures are more promising hardware to design real-time systems than multi-core systems as they should enable an easier mastered integration of a higher number of applications, potentially of different level of criticalities. In embedded real-time systems, these architectures will be integrated within backbone Ethernet networks, as they mostly provide Ethernet controllers as Input/Output(I/O) interfaces. Thus, a number of applications of different level of criticalities could be allocated on the Network-on-Chip (NoC) and required to communicate with sensors and actuators. However, the worst-case behavior of NoC for both inter-core and core-to-I/O communications must be established. Several NoCs targeting hard real-time systems, made of specific hardware extensions, have been designed. However, none of these extensions are currently available in commercially available NoC-based many-core architectures, that instead rely on wormhole switching with round-robin arbitration. Using this switching strategy, interference patterns can occur between direct and indirect flows on many-cores. Besides, the mapping over the NoC of both critical and non-critical applications has an impact on the network contention these core-to-I/O communications exhibit. These core-to-I/O flows (coming from the Ethernet interface of the NoC) cross two networks of different speeds: NoC and Ethernet. On the NoC, the size of allowed packets is much smaller than the size of Ethernet frames. Thus, once an Ethernet frame is transmitted over the NoC, it will be divided into many packets. When all the data corresponding to this frame are received by the DDR-SDRAM memory on the NoC, the frame is removed from the buffer of the Ethernet interface. In addition, the congestion on the NoC, due to wormhole switching, can delay these flows. Besides, the buffer in the Ethernet interface has a limited capacity. Then, this behavior may lead to a problem of dropping Ethernet frames. The idea is therefore to analyze the worst case transmission delays on the NoC and reduce the delays of the core-to-I/O flows. In this thesis, we show that the pessimism of the existing Worst-Case Traversal Time (WCTT) computing methods and the existing mapping strategies lead to drop Ethernet frames due to an internal congestion in the NoC. Thus, we demonstrate properties of such NoC-based wormhole networks to reduce the pessimism when modeling flows in contentions. Then, we propose a mapping strategy that minimizes the contention of core-to-I/O flows in order to solve this problem. We show that the WCTT values can be reduced up to 50% compared to current state-of-the-art real-time packet schedulability analysis. These results are due to the modeling of the real impact of the flows in contention in our proposed computing method. Besides, experimental results on real avionics applications show significant improvements of core-to-I/O flows transmission delays, up to 94%, without significantly impacting transmission delays of core-to-core flows. These improvements are due to our mapping strategy that allocates the applications in such a way to reduce the impact of non-critical flows on critical flows. These reductions on the WCTT of the core-to-I/O flows avoid the drop of Ethernet frames.

Les progrès dans le domaine de la robotique mobile nous permettent aujourd'hui d'ajouter la notion de mobilité dans plusieurs classes de réseaux de capteurs sans fil. Le déploiement de capteurs mobiles est possible et utile dans de nombreuses applications (la sécurité, la surveillance de l'environnement, l’industrie et dans la santé). Deux thèmes sont abordées dans cette thèse: la conception d'un intergiciel pour les réseaux de robots mobiles et un ensemble de techniques pour le déploiement du robot mobile dans le cadre de réseaux de capteurs sans fil. L'intergiciel proposé et décrit dans cette thèse permet à l'utilisateur de facilement mettre en œuvre les différents types d'algorithmes de déploiement pour les robots mobiles. Dans la deuxième partie de la thèse, trois problèmes principaux sont présentés et analysés. Le premier est le problème de l'amélioration de la qualité de service avec l'utilisation des réseaux robotiques. Ce problème est résolu par l'utilisation de l'algorithme de déploiement qui améliore les performances de la transmission multimédia. Notre solution utilise une méthode intrusive pour recueillir la métrique de la qualité de transmission. Le deuxième problème abordé est la couverture de points d'intérêt avec des robots mobiles. Une station de base fixe est placé à l'intérieur du domaine d'intérêt, tandis que les robots mobiles disponibles couvrent le point d'intérêt et relayent l'information vers la station de base de proche en proche. Le troisième problème est la découverte des points d'intérêt et la couverture par l'utilisation de robots mobiles qui suivent des trajectoires circulaires concentriques afin de couvrir le domaine d'intérêt. En ajustant la vitesse de déplacement, ils répondent aux contraintes sur la couverture des points d'intérêt et la connectivité avec le station de base. / The advances in mobile robotics allow us today to add the mobility concept into many different classes of Wireless Sensor Networks. The deployment of mobile sensors is possible and useful in many application scenarios, ranging from the environmental monitoring and public safety applications, to the industry, healthcare and military applications. Two topics are elaborated in this thesis: networked robot middleware design and a set of approaches for mobile robot deployment in the context of wireless sensor networks. The middleware proposed and described in this thesis allows the user to easily implement different types of deployment algorithms for mobile robots. In the second part of the thesis, three main problems are presented and analyzed. The first is the problem of improving the quality of service with the use of mobile robotic networks, which is solved with the use of deployment algorithm that improves the performance of a multimedia communication by using an intrusive methods to gather the necessary transmission quality evaluation metrics. Second problem is the coverage of the point of interest with mobile robots, where the fixed base station is placed inside the field of interest, while the available mobile robots cover the point of interest and relay the information about it towards the base station in a multi-hop manner. The third problem is the point of interest discovery and coverage with the use of mobile robots which follow concentric circular paths to explore and cover the field of interest, and, by adjusting the movement velocity, they satisfy the constraints on PoI coverage and connectivity with the base station.

La correspondance de Robinson-Schensted envoie une permutation sur une paire de tableaux de Young standards de même forme. La forme de ces deux tableaux est aussi appelée forme de la permutation. Récemment, à l'aide de la théorie de Kazhdan-Lusztig, Hohlweg a caractérisé les permutations ayant le nombre d'inversions minimal et celles ayant le nombre d'inversions maximal dans un tapis qui est l'ensemble des permutations de forme fixée. Guo-Niu Han (2004) a montré, par un argument combinatoire, que la caractérisation de Hohlweg pour les permutations minimales dans un tapis est une conséquence de l'algorithme géométrique que Viennot (1976) avait construit pour la correspondance de Robinson-Schensted. Dans ce mémoire, on montre, par un argument combinatoire très similaire à celui de Guo-Niu Han, que la caractérisation de Hohlweg pour les permutations maximales est aussi une conséquence de l'algorithme géométrique de Viennot. Cette construction, qui est une variante de celle de Han, est originale. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Partages, Diagrammes de Ferrers, Tableaux de Young standards, Formule des équerres, Inversions et diagramme de Rothe d'une permutation, Représentations du groupe symétrique, Correspondance de Robinson-Schensted, Construction de Viennot, Cellules bilatères de Kazhdan-Lusztig dans le groupe symétrique, Sous-groupes de Young, Tableaux lisibles par colonnes, Permutations minimales, Permutations maximales.

Cette thèse s'intéresse à l'amélioration des performances pratiques de l'algorithme CDCL (Conftict-Driven Clause Learning) pour la résolution du problème de satisfaisabilité des formules propositionnelles, ou problème SAT. Plus particulièrement, nous cherchons à diminuer la destruction de l'instanciation courante lors des étapes de saut arrière, qui peuvent occasionner la désinstanciation de nombreuses variables n'ayant aucun rapport direct avec le conflit à résoudre. Dans ce but, nous proposons trois approches différentes. La première est une amélioration de l'utilisabilité de la méthode déjà existante de décomposition implicite d'une instance SAT. Notre but principal est de permettre son application à des instances de plus grande taille possible, après avoir montré les limitations des implémentations existantes. Nous développons également deux variations de l'algorithme CDCL, le CDCL sans saut arrière et le CDCL à ordre partiel. Si le premier supprime totalement la notion de saut arrière en permettant la propagation des clauses unitaires à des niveaux de décision quelconques, le second rend le saut arrière plus sélectif, en désinstanciant uniquement les niveaux de décision qui dépendent du niveau de retour du saut arrière. Notre analyse est à la fois théorique, notamment par une analyse détaillée des propriétés de différentes variations des CDCL sans saut arrière et à ordre partiel, et pratique, puisque l'efficacité de nos contributions est évaluée en les implémentant comme modifications de solveurs SAT de l'état de l'art et en se servant de ces implémentations sur des instances SAT difficiles utilisées lors de compétitions internationales de solveurs. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : problème SAT, satisfaisabilité, formules propositionnelles, CDCL, décomposition arborescente, retour arrière, ordre partiel.

L'augmentation des charges transportées par essieu, des vitesses de circulation et l’état des voies peuvent conduire à des endommagements des roues en surface ou sous-surface, généralement appelés écaillage. L’objectif de cette thèse est de développer une approche complète de dimensionnement des roues ferroviaires en fatigue de roulement permettant de prendre en compte les sollicitations locales via la géométrie réelle du contact roue/rail, le comportement inélastique du matériau de la roue (acier) et les conditions d'exploitation. A l’heure actuelle, les méthodes de dimensionnement des roues ne permettent pas de prendre en tous ces éléments au travers d’une même simulation. L’algorithme stationnaire fondé sur la formulation eulérienne est utilisé pour déterminer l’état stabilisé de la structure. L’influence du glissement, du mésalignement, de la position du chargement, et de la nuance d’aciers sur la réponse mécanique, les trajets de chargement en fatigue et la limite d’adaptation a été étudiée. Les critères de fatigue de Dang Van et de Manson-Coffin sont principalement utilisés pour l’analyse en fatigue. Les résultats obtenus permettent la construction de cartes d’adaptation numérique et celles-ci sont alors discutées. D'autre part, l’influence des contraintes résiduelles introduites par le traitement thermique de la bande de roulement est analysée. Il est montré qu’elles modifient les contraintes hydrostatiques comme c'est généralement le cas en fatigue, mais aussi le cisaillement mésoscopique, qui constitue un résultat nouveau. / The increasing of the railways axles loads; the traffic speeds and track conditions can lead to surface and sub-surface damage of wheel, usually called scaling. The aim of this thesis is to develop a numerical approach of railways wheel design in rolling contact fatigue which takes into account the local solicitations via the real geometric of rail/wheel contact, the inelastic behavior of the wheel material (steel) and the operating conditions. At present, the simplified methods for the wheel design are not possible to take all these elements through a single simulation. The stationary algorithm based on the Eulerian formulation is used to determine the steady state of the structure. The influence of the slip, the slip angle, the position of the load and the steel grades on the mechanical response, the fatigue loading paths and the shakedown are investigated. For the fatigue analysis, the criteria of Dang Van and Manson-Coffin are used. The results allow the establishment of the numerical shakedown maps and these are then discussed. Furthermore, the influence of residual stresses introduced by the heat treatment of the tread is analysed. It is shown that they modify the hydrostatic pressure as it is usually the case in fatigue, but also the mesoscopic shear stress, which is a new result.

Le sujet central de cette thèse est le développement d'une méthode dédiée à la preuve de structures de données sans verrou. La motivation première vient du constat que les programmes concurrents sont devenu monnaie courante. Ceci a été possible par l'apparition de nouvelles primitives de synchronisation dans les nouvelles architectures matérielles. La seconde motivation est la quête de logiciel prouvé et donc correct. La sûreté des logiciels est en effet devenue primordiale de par la diffusion des systèmes embarqués et enfouis. La méthode proposée est basée sur le raffinement et dédiée à la conception et la vérification d'algorithme non-bloquant, en particulier ceux sans verrou. La méthode a été formalisée et sa correction prouvée en Isabelle/HOL. Un outil a par ailleurs été développé afin de générer des obligations de preuves à destination des solveurs SMT et des prouveurs de théorèmes du premier ordre. Nous l'avons utilisé afin de vérifier certains de ces algorithmes. / The central topic of this thesis is the proof-based development of lock-free data-structure algorithms. First motivation comes from new computer architectures that come with new synchronisation features. Those features enable concurrent algorithms that do not use locks and are thus more efficient. The second motivation is the search for proved correct program. Nowadays embedded software are used everywhere included in systems where safety is central. We propose a refinement-based method for designing and verifying non-blocking, and in particular lock-free, implementations of data structures. The entire method has been formalised in Isabelle/HOL. An associated prototype tool generates verification conditions that can be solved by SMT solvers or automatic theorem provers for first-order logic, and we have used this approach to verify a number of such algorithms.