Etude des résolutions de problèmes mathématiques par des personnes parvenues au stade hypothético-déductif exprimées par un discours. Présentation d'un outil pour l'étude des raisonnements naturels.

Ce travail s'insère dans un projet global de modélisation de scènes urbaines à partir d'images satellitaires très haute résolution. Le projet a été proposé dans le cadre d'une collaboration entre l'IGN et le CNES et l'université de Paris 5. L'objectif final du projet sera de fournir un système automatique permettant de classifier la scène en deux thèmes ; bâti et routes et de reconstruire les bâtiments en 3D. Dans le cadre de cette thèse, on s'intéresse uniquement à la modélisation des bâtiments. <br />On dispose en entrée de couples stéréoscopiques panchromatiques à [50-70 cm] de résolution et de faible rapport Base sur Hauteur B/H [0.05-0.2]. On exclut la multiscopie.<br />Étant donnée la complexité d'une extraction fine et détaillée des toits en contexte satellitaire, on propose de modéliser la scène urbaine par une surface 3D hybride fournissant différents niveaux de description en fonction de la fiabilité des primitives extraites : points 3D, segments 3D et surfaces planes. <br />Une stratégie mixte a été adoptée. Tout d'abord, une stratégie ascendante basée sur les images permet d'extraire les primitives 3D (segments 3D et facettes 3D). Deux stratégies complémentaires d'extractions de primitives seront détaillées. Une description multi-échelles est utilisée pour la segmentation des images. Notre apport consiste essentiellement dans l'appariement global de deux segmentations multi-échelles du couple stéréoscopique.<br /><br />L'ensemble des primitives sera validé par une approche descendante et permettra de contraindre la modélisation de la surface 3D.<br />Le problème de modélisation de surface 3D peut être formulé comme un problème de minimisation d'énergie. Il sera résolu par optimisation à base de flots de graphes, contrainte par les primitives 3D. Le graphe 3D hybride sera construit à partir d'un volume de corrélation sur la scène 3D et des primitives 3D extraites. La surface finale est obtenue par recherche de la coupe de capacité minimale dans ce graphe 3D.<br /> La majeure contribution de notre approche consiste à utiliser des primitives 3D extraites et des données externes telles que le réseau routier ou les plans cadastraux pour contraindre le problème d'optimisation et modéliser de manière explicite les occultations et les discontinuités.<br />Le produit final, sera un Modèle Numérique d'Élévation hybride « raster/vecteur », permettant d'exploiter à chaque endroit de la scène, les primitives du niveau le plus élevé que l'on a pu reconstruire de manière fiable.<br /><br />Mots-clés : images satellitaires haute résolution, stéréoscopie, Modèle Numérique d'Élévation, primitives 3D, mise en correspondance de régions, appariement multi-échelles, optimisation à base de flots de graphes.

Les problèmes d'optimisation combinatoires définis sur graphes aléatoires sont au coeur de la théorie de la complexité algorithmique. Ils sont également étroitement liés à une formulation champ moyen, dite approximation de Bethe, de modèles sur réseau de verres de spins et verres structuraux. Cette thèse s'appuie sur ce parallèle pour appliquer à des problèmes d'optimisation une approche issue de la physique statistique des systèmes désordonnés, la méthode de la cavité. Etant donné un ensemble d'entrées (instances) d'un problème d'optimisation, cette méthode permet de déterminer les propriétés des solutions des instances typiques, ainsi que celles des instances atypiques, dont les probabilités sont exponentiellement petites (grandes déviations sur la structure externe). Pour une instance donnée, la méthode de la cavité donne également accès à la thermodynamique des différentes solutions admissibles (grandes déviations sur la structure interne). D'un point de vue physique, de nombreux problèmes algorithmiquement difficiles se révèlent ainsi posséder une phase de type verre. Cette thèse est composée de trois parties destinées à exposer les principes, applications et limitations de la méthode de la cavité. La première partie rappelle, dans la perspective des grandes déviations, les liens entre physique statistique et optimisation combinatoire. La deuxième partie aborde les modèles définis sur graphes aléatoires et, pour différents ensembles de graphes, analyse les propriétés typiques et atypiques de ces modèles. La troisième partie est consacrée aux grandes déviations sur le "désordre interne", constitué par les solutions et quasi-solutions d'une instance donnée. Une attention particulière est dévolue au traitement des phases vitreuses où l'ensemble des solutions est fragmenté en un nombre exponentiel d'amas disjoints (structure dite à un pas de brisure de symétrie des répliques); il est montré comment la méthode de la cavité fournit dans de tels cas une description fine des propriétés géométriques de l'espace des solutions.

Inventer des circuits de l'électronique de puissance est une activité intellectuelle qui met en jeu de nombreuses connaissances, requiert du savoir-faire et de la créativité. L'objectif de cette thèse est de concevoir un système informatique simulant cette activité. A cet effet, un système constitué de deux modules a été implanté. Le premier propose les circuits qui ne présentent pas de grossier défaut de conception, au terme d'une recherche heuristique dans un espace organisé en hiérarchie d'abstractions. Cette organisation particulière des connaissances permet de focaliser, aussi tôt que possible, la recherche sur les circuits potentiellement intéressants. Pour éviter que ce module engendre des doublons, la représentation par graphes de liens a été utilisée. Cette mise en (\oe)uvre a donné lieu à un algorithme qui, contrairement à ceux qui ont été décrits dans la littérature, transforme un circuit en un graphe de liens parfaitement adapté au formalisme. Le second module analyse qualitativement le fonctionnement des circuits ainsi engendrés. Il décrit notamment leur fonctionnement dans des termes identiques à ceux employés par les ingénieurs. Il permet ainsi d'exprimer intuitivement les critères imposés par un cahier des charges et de sélectionner les circuits qui le vérifient. L'approche proposée est viable car le système a redécouvert les principaux représentants de classes importantes de circuits. Il a également proposé de circuits nouveaux aux performances a priori comparables à celles des circuits connus. Le système présenté dans cette thèse permet ainsi d'envisager une étude rationnelle des dispositifs de l'électronique de puissance. Plus généralement, il prouve l'efficacité des techniques d'intelligence artificielle sur un domaine concret et met en évidence l'intérêt de l'utilisation des abstractions pour la résolution de problème.

Selon les domaines d'applications, différentes façons de modéliser le partage de ressources ont été envisagées. Un des premiers modèles apparus est issu du "Dining Philosophers Problem" de Dijkstra, généralisé par la suite par Chandy et Misra à travers le "Drinking Philosophers Problem". Nous nous intéressons à des versions markoviennes de ces situations, dans lesquelles les durées pour la prise et l'utilisation des ressources sont aléatoires. L'évaluation puis l'optimisation des performances des systèmes de ressources partagées nous conduit à étudier l'équilibre de ces modèles. Cette étude s'inscrit dans le contexte des propriétés de Markov des champs aléatoires sur les graphes dont nous présentons quelques résultats généraux. Nous utilisons également le formalisme des systèmes de particules. Nous introduisons une nouvelle classe de modèles markoviens de ressources partagées pour lesquels nous généralisons des outils classiques. Nous présentons des résultats de réversibilité et envisageons des techniques de comparaison stochastique. Pour des systèmes finis, nous donnons quelques calculs explicites de mesures d'équilibre. Des systèmes qui augmentent en taille et en complexité peuvent être approchés par des systèmes infinis. Pour des systèmes sur des graphes infinis construits à partir d'un arbre, nous mettons en évidence des phénomenes de transition de phase.

Considérons les systèmes à évènements discrets qui sont modélisables par des réseaux de Pétri du type "graphes d'évènements temporisés", Ils ont un comportement optimal (fonctionnement au plus tôt) qui peut-être calculé sans simulation par un système dynamique qui est linéaire dans l'algèbre des dïodes (max,+) ou (min,+). Le comportement asymptotique d'un tel système à évènements discrets est cyclique et les caractéristiques de ce cycle (période, délai, motif) sont analysables par un calcul de valeur propre sur la matrice de dynamique. À partir de cette formulation linéaire, une représentation externe (fonction de transfert) peut-être obtenue grâce à un calcul formel sur des séries à coefficients dans les dïodes, la fonction de transfert d'un tel système est rationnelle au sens des dïoides et est factorisable en une expression finie de polynômes.

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

Dans cette thèse, nous étudions des modèles d'agrégation limitée, qui modélisent la coalescence de particules ayant des "bras", c'est-à-dire un nombre fixé de liens potentiels. Une particule ne peut donc créer plus de liens que son nombre de bras. On s'intéresse en particulier à une variante de l'équation de Smoluchowski introduite par Jean Bertoin. Ce document comprend, outre l'introduction, trois chapitres. Le premier est dévolu à l'étude d'un modèle sexué de coagulation, où les particules ont des bras mâles et femelles et seuls des bras de sexes opposés peuvent se joindre. Ce modèle généralise et unifie ceux de Bertoin, dont on peut en particulier retrouver les résultats. Le second chapitre comprend un travail en collaboration avec Lorenzo Zambotti. On s'y intéresse à l'unicité des solutions d'équations de coagulation après gélification, en particulier l'équation de Smoluchowski avec noyau multiplicatif et l'équation d'agrégation limitée. En particulier, on donne des preuves rigoureuses de certaines heuristiques de la littérature physique, par exemple en calculant précisément le temps de gélification. Dans le cas d'agrégation limitée, on obtient aussi des formules particulièrement simples pour les concentrations limites. Pour expliquer celles-ci, on étudie dans le dernier chapitre un modèle microscopique pour l'équation de Smoluchowski d'agrégation limitée. Ceci est un travail commun avec Mathieu Merle. On parvient à décrire précisément l'état microscopique du système à tout temps et ainsi à retrouver les formules du second chapitre. Une caractéristique frappante de ce modèle est qu'il possède une propriété de criticalité auto-organisée.

Dans cette thèse, nous nous intéressons à la caractérisation de grandes collections de documents (en utilisant les liens entre ces derniers) afin de faciliter leur utilisation et leur exploitation par des humains ou par des outils informatiques. Dans un premier temps, nous avons abordé la problématique du calcul de centralité dans les graphes de documents. Nous avons décrit les principaux algorithmes de calcul de centralité existants en mettant l'accent sur le problème TKC (Tightly Knit Community) dont souffre la plupart des mesures de centralité récentes. Ensuite, nous avons proposé trois nouveaux algorithmes de calcul de centralité (MHITS, NHITS et DocRank) permettant d'affronter le phénomène TKC. Les différents algorithmes proposés ont été évalués et comparés aux approches existantes. Des critères d'évaluation ont notamment été proposés pour mesurer l'effet TKC. Dans un deuxième temps, nous nous sommes intéressés au problème de la classification non supervisée de documents. Plus précisément, nous avons envisagé ce regroupement comme une tâche d'identification de structures de communautés (ISC) dans les graphes de documents. Nous avons décrit les principales approches d'ISC existantes en distinguant les approches basées sur un modèle génératif des approches algorithmiques ou classiques. Puis, nous avons proposé un modèle génératif (SPCE) basé sur le lissage et sur une initialisation appropriée pour l'ISC dans des graphes de faible densité. Le modèle SPCE a été évalué et validé en le comparant à d'autres approches d'ISC. Enfin, nous avons montré que le modèle SPCE pouvait être étendu pour prendre en compte simultanément les liens et les contenus des documents.

Des millions de réactions chimiques sont décrites dans des bases de données sous la forme de transformations de graphes moléculaires. Cette thèse propose différentes méthodes de fouille de donnés pour extraire des motifs pertinents contenus dans ces graphes et ainsi aider les chimistes à améliorer leurs connaissances des réactions chimiques et des molécules. Ainsi on commence par montrer comment le problème central de la recherche des schémas de réactions fréquents peut se résoudre à l'aide de méthodes existantes de recherche de sous-graphes fréquents. L'introduction du modèle général des motifs les plus informatifs permet ensuite de restreindre l'analyse de ces motifs fréquents à un nombre réduit de motifs peu redondants et représentatifs des données. Si l'application du modèle aux bases de réactions permet d'identifier de grandes familles de réactions, le modèle est inadapté pour extraire les schémas caractéristiques de méthodes de synthèse (schémas CMS) dont la fréquence est trop faible. Afin de surmonter cet obstacle, est ensuite introduite une méthode de recherche heuristique fondée sur une contrainte d'intervalle entre graphes et adaptée à l'extraction de motifs de très faible fréquence. Cette méthode permet ainsi de déterminer à partir d'exemples de réactions et sous certaines conditions le schéma CMS sous-jacent à une réaction donnée. La même approche est ensuite utilisée pour traiter le problème de la classification supervisée de sommets ou d'arêtes fondée sur leurs environnements puis exploitée pour évaluer la formabilité des liaisons d'une molécule. Les résultats produits ont pu être analysés par des experts de la synthèse organique et sont très encourageants.