Notre travail porte sur le développement d'algorithmes performants d'application de grammaires locales, en prenant comme référence ceux des logiciels libres existants : l'analyseur syntaxique descendant d'Unitex et l'analyseur syntaxique à la Earley d'Outilex. Les grammaires locales sont un formalisme de représentation de la syntaxe des langues naturelles basé sur les automates finis. Les grammaires locales sont un modèle de construction de descriptions précises et à grande échelle de la syntaxe des langues naturelles par le biais de l'observation systématique et l'accumulation méthodique de données. L'adéquation des grammaires locales pour cette tâche a été testée à l'occasion de nombreux travaux. À cause de la nature ambiguë des langues naturelles et des propriétés des grammaires locales, les algorithmes classiques d'analyse syntaxique tels que LR, CYK et ne peuvent pas être utilisés dans le contexte de ce travail. Les analyseurs top-down et Earley sont des alternatives possibles ; cependant, ils ont des coûts asymptotiques exponentiels pour le cas des grammaires locales. Nous avons d'abord conçu un algorithme d'application de grammaires locales avec un coût polynomial dans le pire des cas. Ensuite, nous avons conçu des structures de donnés performantes pour la représentation d'ensembles d'éléments et de séquences. Elles ont permis d'améliorer la vitesse de notre algorithme dans le cas général. Nous avons mis en œuvre notre algorithme et ceux des systèmes Unitex et Outilex avec les mêmes outils afin de les tester dans les mêmes conditions. En outre, nous avons mis en œuvre différents versions de chaque algorithme en utilisant nos structures de données et algorithmes pour la représentation d'ensembles et ceux fournis par la Standard Template Library (STL) de GNU. Nous avons comparé les performances des différents algorithmes et de leurs variantes dans le cadre d'un projet industriel proposé par l'entreprise Telefónica I+D : augmenter la capacité de compréhension d'un agent conversationnel qui fournit des services en ligne, voire l'envoi de SMS à des téléphones portables ainsi que des jeux et d'autres contenus numériques. Les conversations avec l'agent sont en espagnol et passent par Windows Live Messenger. En dépit du domaine limité et de la simplicité des grammaires appliquées, les temps d'exécution de notre algorithme, couplé avec nos structures de données et algorithmes pour la représentation d'ensembles, ont été plus courts. Grâce au coût asymptotique amélioré, on peut s'attendre à des temps d'exécution significativement inférieurs par rapport aux algorithmes utilisés dans les systèmes Unitex et Outilex, pour le cas des grammaires complexes et à large couverture

Les travaux présentés dans le cadre de cette Habilitation à Diriger des Recherches s'inscrivent principalement dans la problématique dite d'" Adéquation Algorithme Architecture ". Ils ont pour objectif commun la mise en œuvre de systèmes matériels et logiciels dédiés à la vision artificielle à fortes contraintes temporelles. Ils se focalisent sur différents aspects cruciaux tels que l'acquisition d'images par des capteurs dédiés, le développement et la programmation d'architectures optimisées de traitement des images et l'implantation d'algorithmes de traitement du signal et d'images en temps réel sur ces architectures.

La première partie de cette thèse (articles 1 et 2) est consacrée à l'étude du comportement asymptotique des solutions de dynamiques du second ordre avec dissipation evanescente. La deuxième partie de cette thése (articles 3 à 6) est consacrée à l'étude de plusieurs algorithmes de type proximal. Nous montrons que ces algorithmes convergent vers des solutions de certains problèmes de minimisation. Dans chaque cas, une application est donnée dans le cadre de la décomposition de domaine pour les EDP.

Un des buts de l'infographie est de produire des images réalistes. Pour cela, des artistes créent des modèles géométriques complexes ornés de textures détaillées. Malheureusement, selon l'application visée et les ressources disponibles, il doivent souvent "prendre des raccourcis" en répétant des textures ou en utilisant des modèles simples dont les détails sont simulés par une série de couches d'apparence. Afin de créer des objets 3D réalistes, la meilleure source d'inspiration est le monde réel lui-même. Dans ce contexte, nous proposons d'aider l'artiste à créer ces couches d'apparence à partir de l'analyse d'exemples. Nous nous attaquons tout d'abord à la couche de texture couleur, et plus particulièrement aux textures structurées.<br />En effet, ces dernières sont difficilement reproductibles de manière automatique et leur répétition visuelle est gênante pour l'observateur. Afin de réussir à propager de telles textures à partir d'un exemplaire donné, nous proposons de découpler la structure de l'apparence.<br />Nous traitons le problème tout d'abord sous un aspect géométrique. Les textures structurées sont représentées par un maillage 2D qui est analysé afin d'en extraire une description statistique compacte menant à la création d'un générateur permettant de reproduire la structure originelle à volonté. L'utilisateur est pris en compte tout au long du processus et peut influencer le résultat grâce à des cartes de contraintes.<br />En parallèle, nous analysons l'apparence de la texture structurée afin d'extraire un ensemble réduit de textures représentant les matériaux utilisés pour l'intérieur des régions et leur contour. Ces informations nous permettent d'"habiller" de nouvelles structures de manière efficace. Dans un troisième temps, nous utilisons l'information de structure et de texture, ainsi que des informations usager afin de générer et propager des détails 3D sur des modèles. Nous proposons un système générique qui permettra d'alléger les artistes de tâches souvent répétitives et fastidieuses. Nous appliquons ce système à la génération de cartes de hauteurs et présentons plusieurs autres cas d'application.<br />L'ensemble des techniques proposées permet de synthétiser des textures structurées détaillées à partir d'exemples avec un coût mémoire réduit et permettant un rendu en temps-réel, tout en laissant du contrôle à l'utilisateur.

Ce travail de thèse vise à décrire l'influence des connaissances mathématiques des enseignants primaires sur leur gestion didactique de tâches mathématiques. Il s'appuie sur une comparaison à ce sujet entre enseignants chinois et étatsuniens (Ma, 1999), sur les catégories de connaissances mathématiques pour l'enseignement (Ball, Thames & Phelps, 2008), sur la structuration du milieu et sa déclinaison en niveaux d'activité du professeur (Margolinas, 2002), et sur les critères de pertinence mathématique du professeur élaborés par Bloch (2009). Dans une première partie, des entretiens avec des enseignants vaudois ont permis de mettre en évidence certaines similitudes avec les enseignants interrogés par Ma. Dans une seconde partie, quatre enseignants ont été observés durant leur enseignement de l'algorithme de la multiplication par un nombre à plusieurs chiffres. Les résultats ont été considérés à plusieurs niveaux d'analyse allant jusqu'au grain très fin de la structuration du milieu. Ils font apparaître des liens entre connaissances mathématiques, pertinence et choix didactiques des enseignants.

Il existe aujourd'hui une demande croissante pour des modèles numériques de ville de plus en plus précis. Alors que les travaux récents ont permis la production robuste de modèles polyédriques de bâtiments, les superstructures de toits telles que les cheminées et les chiens assis ne sont pas modélisées, et les erreurs géométriques et topologiques peuvent être importantes. L'approche itérative proposée affine géométriquement et sémantiquement un modèle de bâtiment approché sans superstructures, à l'aide d'un Modèle Numérique de Surface (MNS). Elle alterne la reconstruction de superstructures et le recalage des pans de toit principaux. La détection et la reconstruction de superstructures sont basées sur une bibliothèque de modèles paramétriques de superstructures. Un ensemble de superstructures disjointes est recherché, en se réduisant au problème de recherche d'une clique pondérée maximale. La phase de recalage tire parti des superstructures précédemment détectées afin de mieux estimer les pans de toit principaux. Elle corrige des simplifications tant géométriques telles qu'une symétrie erronée des toits, que topologiques telles que la fusion de sommets proches. Nous utilisons une représentation géométrique des bâtiments par les plans porteurs de chaque facette polyédrique, plus intuitive dans ce contexte que la représentation habituelle par la position de ses sommets. Nous introduisons le problème de triédralisation qui scinde les sommets surcontraints en sommets bien définis à l'intersection de 3 plans seulement. Nous proposons une structure de donnée cinétique garantissant des facettes non auto-intersectantes au cours de la réestimation itérative de leurs plans porteurs.

Cette thése porte sur la reconnaissance de caractères imprimés et manuscrits par méthodes markoviennes et réseaux bayésiens. La première partie consiste à effectuer une modélisation stochastique markovienne en utilisant les HMMs classiques dans deux cas: semi-continu et discret. Un premier modèle HMM est obtenu à partir d'observations de type colonnes de pixels (HMM-vertical), le second à partir d'observations de type lignes (HMM-horizontal). Ensuite nous proposons deux types de modèles de fusion : modèle de fusion de scores qui consiste à combiner les deux vraisemblances résultantes des deux HMMs, et modèle de fusion de données qui regroupe simultanément les deux observations lignes et colonnes. Les résultats montrent l'importance du cas semi-continu et la performance des modèles de fusion. Dans la deuxième partie nous développons les réseaux bayésiens statiques et dynamiques, l'algorithme de Jensen Lauritzen Olesen (JLO) servant comme moteur d'inférence exacte, ainsi que l'apprentissage des paramètres avec des données complètes et incomplètes. Nous proposons une approche pour la reconnaissance de caractères (imprimés et manuscrits) en employant le formalisme des réseaux bayésiens dynamiques. Nous construisons certains types de modèles: HMM sous forme de réseau bayésien dynamique, modèle de trajectoire et modèles de couplages. Les résultats obtenus mettent en évidence la bonne performance des modèles couplés. En général nos applications nous permettent de conclure que l'utilisation des réseaux bayésiens est efficace et très prometteuse par le fait de modéliser les dépendances entre différentes observations dans les images de caractères.

La superposition de topologies virtuelles à la topologie physique d'un réseau est un des principaux mécanismes de l'ingénierie de trafic. Soit un réseau physique d'une certaine topologie et capacité fixées et une matrice de trafic à véhiculer, il s'agit trouver une topologie logique permettant de mapper de manière optimale la matrice de trafic sur le réseau physique. Lors de l'évolution de la matrice de trafic sur des échelles de temps longues, il faudra agir sur le layout. La première contribution concerne la définition de fonctions de coût mieux adaptées à la réalité d'un opérateur, la deuxième contribution concerne la prise en compte du coût de changement du layout. Il s'avère intéressant d'un point de vue opérateur de réduire la complexité du layout, mesurée comme une fonction du nombre de chemins virtuels. Nous avons donc formulé divers problèmes de minimisation de la complexité du layout sous des contraintes de QoS. Il s'agit d'une modélisation réaliste mais qui engendre des modèles difficiles à résoudre. Nous avons développés des heuristiques qui permet de trouver des solutions approchées pour des réseaux de grande taille. Nous avons montré que la complexité des layouts peut être significativement réduite en comparaison avec celle obtenue suite à l'optimisation des fonctions de coût classiques. Le changement du layout implique d'une part un coût d'opération et d'autre part peut engendrer des coupures de service qui affecteront directement le coût d'opération. Nous avons formulé une famille de problèmes prenant en compte le coût de reconfiguration du layout. L'une des heuristiques citées a été adaptée pour analyser ces nouveaux problèmes.

Dans cette thèse, nous étudions les triangulations définies par un ensemble de points dans des espaces de topologies différentes. Nous proposons une définition générale de la triangulation de Delaunay, valide pour plusieurs classes d'espaces, ainsi qu'un algorithme de construction. Nous fournissons une implantation pour le cas particulier du tore plat tridimensionnel. Ce travail est motivé à l'origine par le besoin de logiciels calculant des triangulations de Delaunay périodiques, dans de nombreux domaines dont l'astronomie, l'ingénierie des matériaux, le calcul biomédical, la dynamique des fluides, etc. Les triangulations périodiques peuvent être vues comme des triangulations du tore plat. Nous fournissons une définition et nous développons un algorithme incrémentiel efficace pour calculer la triangulation de Delaunay dans le tore plat. L'algorithme est adapté de l'algorithme incrémentiel usuel dans R^d. Au contraire des travaux antérieurs sur les triangulations périodiques, nous évitons de maintenir plusieurs copies périodiques des points, lorsque cela est possible. Le résultat fourni par l'algorithme est toujours une triangulation du tore plat. Nous présentons une implantation de notre algorithme, à présent disponible publiquement comme un module de la bibliothèque d'algorithmes géométriques CGAL. Nous généralisons les résultats à une classe plus générale d'espaces quotients plats, ainsi qu'à des espaces quotients de courbure constante positive. Enfin, nous considérons le cas du tore double, qui est un exemple de la classe beaucoup plus riche des espaces quotients de courbure négative constante.

Cette thèse en informatique se place dans le cadre de l'Analyse de Concepts Formels (ACF) ou les treillis de Galois. Ce sont des outils basés sur des opérateurs mathématiques appelés fermetures de Galois permettant de calculer des concepts. Un concept est formé d'un ensemble d'objets partageant tous un ensemble d'attributs communs. Ces concepts sont extraits à partir d'un contexte qui est une table de relation binaire entre ces objets et ces attributs. Nous nous intéressons à des contextes complexes dont la complexité repose sur deux axes. D'une part, les contextes multi-valués dont les attributs se divisent en plusieurs modalités. D'autre part, les contextes flous dont la relation entre objets et attributs n'est pas binaire. Nous définissons les contextes multi-valués flous qui héritent de ces deux complexités et présentons deux conversions des données multi-valuées floues. La première conversion est une binarisation par une disjonction totale des attributs permettant d'une part l'exploitation d'outils comme des implications et d'autre part de comparer et combiner les treillis avec des méthodes statistiques telles que l'analyse factorielle. La seconde conversion est issue de l'échelonnage histogramme que nous définissons et qui permet de convertir les attributs en histogrammes. Afin de générer les concepts à partir des histogrammes, nous proposons une nouvelle fermeture de Galois basée sur une mesure de similarité entre ces histogrammes. Cette fermeture permet d'obtenir des concepts pour lesquels les objets possèdent des attributs non plus égaux mais similaires compris entre un minimum et un maximum communs. Nous proposons également des mesures de seuillage pour limiter le nombre de concepts générés et diminuer les temps de calculs. Enfin, deux algorithmes ont été testés pour implémenter cette fermeture : MinMaxNC et MinMaxC, dont nous comparons les performances. Cette thèse trouve son application notamment dans le domaine hydrobiologique dont une problématique est la sélection de traits écologiques de taxons permettant de caractériser l'état écologique des cours d'eau par le comportement des espèces au sein de leur environnement. La sélection de ces traits s'appuie sur la recherche de groupes de taxons possédant des caractéristiques morphologiques et physiologiques (appelés traits biologiques) communes. Ces groupes correspondent à des concepts au sens de l'ACF et les données biologiques se présentent sous la forme d'un contexte multi-valué flou pour lequel nous montrons l'efficacité de notre approche.