De nombreuses applications informatiques nécessitent l'utilisation de distances. Dans le cadre de données structurées, chaînes ou arbres, nous utilisons majoritairement la distance d'édition. Celle-ci correspond au nombre minimal d'opérations d'édition (insertion, délétion et substitution) nécessaire pour transformer la première donnée en la seconde. Suivant l'application traitée, il est possible de paramétrer la distance d'édition en associant à chaque opération d'édition un poids. Dans le cadre de ce manuscrit, nous proposons une technique d'apprentissage automatique supervisée pour apprendre les poids de la distance décrite précédemment. L'algorithme utilisé, appelé Expectation-Maximisation, maximise la vraisemblance des paramètres du modèle à l'aide d'un échantillon d'apprentissage composé de paires d'exemples considérés comme similaires. La première contribution de ce manuscrit est une extension de précédents travaux sur les chaînes aux arbres sous la forme de transducteur à un unique état. Nous montrons sur une tâche de reconnaissance de caractères manuscrits, l'efficacité de l'apprentissage par rapport à l'utilisation de poids non appris. La seconde est une approche sur les chaînes sous contraintes. Le modèle est représenté par un ensemble fini d'états dans lequel les transitions sont contraintes. Une contrainte est représentée par un ensemble fini de fonctions booléennes définies sur la chaîne d'entrée et une de ses positions. Nous utilisons notre modèle pour aborder une application de recherche de sites de facteur de transcription dans des séquences génomiques

Cette thèse propose une nouvelle approche pour la synthèse de valeurs temporelles dans les systèmes temporisés. Notre approche est basée sur la méthode inverse suivante : à partir d’une instance de référence des paramètres, nous synthétisons une contrainte sur les paramètres, garantissant le même comportement que pour l’instance de référence, abstraction faite du temps. Il en résulte un critère de robustesse pour le système. En itérant cette méthode sur des points dans un domaine paramétrique borné, nous sommes alors à même de partitionner l’espace des paramètres en bonnes et mauvaises zones par rapport à une propriété à vérifier. Ceci nous donne une cartographie comportementale du système. Cette méthode s’étend aisément aux systèmes probabilistes. Nous présentons également des variantes de la méthode inverse pour les graphes orientés valués et les processus de décision markoviens. Parmi les prototypes implémentés, IMITATOR II implémente la méthode inverse et la cartographie pour les automates temporisés. Ce prototype nous a permis de synthétiser de bonnes valeurs pour les paramètres temporels de plusieurs études de cas, dont un modèle abstrait d’une mémoire commercialisée par le fabricant de puces STMicroelectronics, ainsi que plusieurs protocoles de communication. / This thesis proposes a novel approach for the synthesis of delays for timed systems, in particular in the framework oftimed automata, a model for verifying real-time systems. Our approach relies on the following inverse method: given a reference valuation of the parameters, we synthesize a constraint on the parameters, guaranteeing the same timeabstract linear behavior as for the reference valuation. This gives a criterion of robustness to the system. By iterating this inverse method on various points of a bounded parameter domain, we are then able to partition the parametric space into good and bad zones, with respect to a given property one wants to verify. This gives a behavioral cartography of the system. This method extended to probabilistic systems allows to preserve minimum and maximum probabilities of reachability properties. We also present variants of the inverse method for directed weighted graphs and Markov Decision Processes. Several prototypes have been implemented; in particular, IMITATOR II implements the inverse method and the cartography for timed automata. It allowed us to synthesize parameter values for several case studies such as an abstract model of a memory circuit sold by the chipset manufacturer ST-Microelectronics, and various communication protocols.

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

On présente une Logique Probabiliste avec des opérateurs Conditionnels - LPCP, sa syntaxe, sémantique, axiomatisation correcte et fortement complète, comprenant une règle de déduction infinitaire. On prouve que LPCP est décidable, et on l'étend pour qu’il puisse représenter l'évidence, en créant ainsi la première axiomatisation propositionnelle du raisonnement basé sur l'évidence. On codifie les Logiques Probabilistes LPP1Q et LPPQ2 dans l'Assistant de Preuve Coq, et on vérifie formellement leurs propriétés principales: correction, complétude fort et non-compacité. Les deux logiques étendent la Logique Classique avec des opérateurs de probabilité, et présentent une règle de déduction infinitaire. LPPQ1 permet des itérations des opérateurs de probabilité, lorsque LPPQ2 ne le permet pas. On a formellement justifié l'utilisation des solveurs SAT probabilistes pour vérifier les questions liées à la cohérence. On présente LFP, un Cadre Logique avec Prédicats Externes, en introduisant un mécanisme pour bloquer et débloquer types et termes dans LF, en permettant l'utilisation d’oracles externes. On démontre que LFP satisfait tous les principales propriétés et on développe un cadre canonique correspondant, qui permet de prouver l’adéquation. On fournit diverses encodages - le λ-calcul non-typé avec la stratégie de réduction CBV, Programmation-par-Contrats, un langage impératif avec la Logique de Hoare, des Logiques Modales et la Logique Linéaire Non-Commutative, en montrant que en LFP on peut codifier aisément des side-conditions dans l'application des règles de typage et atteindre une séparation entre vérification et computation, en obtenant des preuves plus claires et lisibles. / We introduce a Probability Logic with Conditional Operators - LPCP, its syntax, semantics, and a sound and strongly-complete axiomatic system, featuring an infinitary inference rule. We prove the obtained formalism decidable, and extend it so as to represent evidence, making it the first propositional axiomatisation of reasoning about evidence. We encode Probability Logics LPP1Q and LPP2Q in the Proof Assistant Coq and formally verify their key properties - soundness, strong completeness, and non-compactness. Both logics extend Classical Logic with modal-like probability operators, and both feature an infinitary inference rule. LPP1Q allows iterations of probability operators, while LPP2Q does not. In this way, we have formally justified the use of Probabilistic SAT-solvers for the checking of consistency-related questions. We present LFP - a Logical Framework with External Predicates, by introducing a mechanism for locking and unlocking types and terms into LF, allowing the use of external oracles. We prove that LFP satisfies all the main meta-theoretic properties and develop a corresponding canonical framework, allowing for easy proofs of adequacy. We provide a number of encodings - the simple untyped λ-calculus with a Call-by-Value reduction strategy, the Design-by-Contract paradigm, a small imperative language with Hoare Logic, Modal Logics in Hilbert and Natural Deduction style, and Non-Commutative Linear Logic (encoded for the first time in an LF-like framework), illustrating that in LFP we can encode side-conditions on the application of rules elegantly, and achieve a separation between verification and computation, resulting in cleaner and more readable proofs.

Le contrôle de l'information émise par un système a vu son utilité grandir avec la multiplication des systèmes communicants. Ce contrôle peut être réalisé par exemple pour révéler une information du système, ou au contraire pour en dissimuler une. Le diagnostic notamment cherche à déterminer, grâce à l'observation du système, si une faute a eu lieu au sein de celui-ci. Dans cette thèse, nous établissons des bases formelles à l'analyse des problèmes du diagnostic pour des modèles stochastiques. Nous étudions ensuite ces problèmes dans plusieurs cadres (fini/infini, passif/actif). / The control of the information given by a system has seen increasing importance recently with the multiplication of communicating systems. This control can be used in order to disclose an information of the system, or, oppositely, to hide one. Diagnosis for instance tries to determine from the observation produced by the system whether a fault occurred within it or not. In this PhD, we establish formal foundations to the analysis of the diagnosis problems for stochastic models. We then study these problems in multiple framework (finite/infinite, passive/active).

La production renouvelable (l'éolien, solaire photovoltaïque) a la particularité d'être variable et surtout non contrôlable du fait de la variabilité des sources. Compte tenu de ces particularités, les études d'impact des EnR sur les systèmes électriques, basées sur les méthodes déterministes s'avèrent inadaptées. L'objectif de ce travail est d'étudier l'apport des méthodes probabilistes dans les études d'intégration des EnR aux systèmes électriques. Les variations des paramètres du système imposent aux gestionnaires de réseaux des défis dont un des plus importants est la maîtrise de l'impact lié à ces variations. Cela passe par une caractérisation probabiliste du système électrique qui a été développée dans ce travail. Des méthodes probabilistes ont été développées pour réaliser les différentes analyses (transits, tensions, stabilité...) d'impact des EnR. De même pour les études d'intégration du type calcul du taux de pénétration en EnR dans un système donné, une méthode probabiliste a été proposée. Le principe de ces études est d'effectuer les analyses classiques sur grand nombre de points de fonctionnement représentatifs du comportement du système sur la période d'étude. Ces points de fonctionnement sont obtenus par tirage Monte Carlo sur les lois de probabilités des différents paramètres du système. A l'issue de ces analyses, l'impact des EnR est défini par un risque de défaillance. Il s'agit donc d'une étude du « risque de défaillance » à la différence d'une étude déterministe qui est du type « défaillance /pas défaillance ». Les méthodes déterministe et probabiliste ont été comparées pour deux cas : le raccordement d'une unité de production renouvelable à un réseau de distribution et l'étude du taux de pénétration d'un parc d'EnR dans un réseau de type insulaire.

Selon des travaux récents, les locuteurs seraient capables de recourir à des connaissances sur les régularités phonotactiques ou syllabiques de leur langue pour segmenter le signal de parole en mots. Une analyse distributionnelle de la fréquence des groupes de consonnes dans un lexique informatisé de la langue française révèle cependant l'existence d'un lien étroit entre la structure phonologique des groupes de consonnes et leur probabilité d'occurrence dans la langue. Les séquences de phonèmes tautosyllabiques ou légales sont en moyenne beaucoup plus fréquentes que les séquences hétérosyllabiques ou illégales. Trois modèles des processus de segmentation lexicale sont présentés qui pourraient rendre compte des effets observés sans recourir à des processus de segmentation fondés sur les régularités phonologiques de la langue. Les expériences conduites ont pour objectif de dissocier ces diverses interprétations d'un modèle de segmentation fondé sur les régularités phonologiques. Les résultats obtenus confirment en partie l'influence des contraintes phonologiques sur les processus de segmentation de la parole en mots. Ils incitent cependant à développer une réflexion sur le niveau d'implémentation de ces connaissances (prélexical vs. post-lexical) et sur leur mode d'intégration dans un modèle du traitement de la parole. Un modèle est proposé dans lequel ces procédures de segmentation constitueraient des routines générales d'organisation perceptive qui ne seraient pas spécifiques des processus de traitement du langage parlé et n'influenceraient pas directement les niveaux de représentation lexicaux. Ces deux catégories de traitements seraient indépendantes et intégrées au cours d'une étape ultérieure.

Le sujet global de cette thèse est l'étude d'automates cellulaires probabilistes. Elle est divisée en deux grandes parties.<br /><br />Au cours de la première, nous définissons la notion de chaîne partiellement ordonnée qui généralise celle d'automate cellulaire probabiliste. Cette définition se fait par l'intermédiaire de spécification partiellement ordonnée de la même façon que les mesures de Gibbs sont définies à l'aide de spécifications. Nous obtenons des résultats analogues sur l'espace des phases : caractérisation des mesures extrêmes, construction/reconstruction en partant des noyaux sur un seul site, critères d'unicité. Les résultats sont appliqués tout au long du texte à des automates déjà connus.<br /><br />La deuxième partie est essentiellement vouée à l'étude d'automates cellulaires unidimensionnels à deux voisins et deux états. Nous donnons deux décompositions des configurations spatio-temporelles en flot d'information. Ces flots ont une signification géométrique. De cela nous tirons deux critères d'unicité.<br /><br />En annexe, nous donnons une démonstration de transition de phase d'un automate cellulaire défini par A. Toom, le modèle NEC. Tout au long du texte, des simulations sont présentées.

Cette thèse est consacrée à la prise en compte de données incertaines dans les problèmes d'optimisation. On se concentre sur la programmation mathématique sous contraintes probabilistes, dont le but est de trouver la meilleure solution qui sera réalisable avec une probabilité minimale garantie. Par ailleurs, on s'intéresse à la prise en compte de variables de décisions entières, qui sont souvent requises en pratique.<br /><br />Pour résoudre de tels problèmes combinatoires sous contraintes probabilistes, on s'appuie d'abord sur l'optimisation robuste. Les liens théoriques entre ces deux familles de méthodes sont mis en évidence. A partir de modèles robustes appropriés, des algorithmes de résolution heuristique sont définis. On s'intéresse ensuite à la résolution optimale de problèmes combinatoires sous contraintes probabilistes. Des tests numériques illustrent les méthodes présentées et montrent leur efficacité pratique. Enfin, deux applications au domaine des télécommunications sont développées. Elles concernent toutes deux la localisation de fonctions dans un réseau.

L'étude de la démographie dans une perspective historique participe à la compréhension des processus évolutifs. Les données de diversité génétique sont potentiellement informatives quant au passé démographique des populations: en effet, ce passé est enregistré avec perte d'information par les marqueurs moléculaires, par l'intermédiaire de leur histoire généalogique et mutationnelle. L'acquisition de données de diversité génétique est de plus en plus rapide et aisée, et concerne potentiellement n'importe quel organisme d'intérêt. D'où un effort dans la dernière décennie pour développer les outils statistiques permettant d'extraire l'information démographique des données de typage génétique.<br />La présente thèse propose une extension de la méthode d'inférence bayésienne développée en 1999 par M. Beaumont. Comme la méthode originale, (i) elle est basée sur le coalescent de Kingman avec variations d'effectif, (ii) elle utilise l'algorithme de Metropolis-Hastings pour échantillonner selon la loi a posteriori des paramètres d'intérêt et (iii) elle permet de traiter des données de typage à un ou plusieurs microsatellites indépendants. La version étendue généralise les modèles démographique et mutationnel supposés dans la méthode initiale: elle permet d'inférer les paramètres d'un modèle de fondation-explosion pour la population échantillonnée et d'un modèle mutationnel à deux phases, pour les marqueurs microsatellites typés. C'est la première fois qu'une méthode probabiliste exacte incorpore pour les microsatellites un modèle mutationnel autorisant des sauts.<br />Le modèle démographique et mutationnel est exploré. L'analyse de jeux de données simulés permet d'illustrer et de comparer la loi a posteriori des paramètres pour des scénarios historiques: par exemple une stabilité démographique, une croissance exponentielle et une fondation-explosion. Une typologie des lois a posteriori est proposée. Des recommandations sur l'effort de typage dans les études empiriques sont données: un unique marqueur microsatellite peut conduire à une loi a posteriori très structurée. Toutefois, les zones de forte densité a posteriori représentent des scénarios de différents types. 50 génomes haploides typés à 5 marqueurs microsatellites suffisent en revanche à détecter avec certitude (99% de la probabilité a posteriori) une histoire de fondation-explosion tranchée. Les conséquences de la violation des hypothèses du modèle démographique sont discutées, ainsi que les interactions entre processus et modèle mutationnel. En particulier, il est établi que le fait de supposer un processus mutationnel conforme au modèle SMM, alors que ce processus est de type TPM, peut générer un faux signal de déséquilibre génétique. La modélisation des sauts mutationnels permet de supprimer ce faux signal.<br />La méthode est succinctement appliquée à l'étude de deux histoires de fondation-explosion: l'introduction du chat Felis catus sur les îles Kerguelen et celle du surmulot Rattus norvegicus sur les îles du large de la Bretagne. Il est d'abord montré que la méthode fréquentiste développée par Cornuet et Luikart (1996) ne permet pas de détecter les fondations récentes et drastiques qu'ont connu ces populations. Cela est vraisemblablement dû à des effets contraires de la fondation et de l'explosion, sur les statistiques utilisées dans cette méthode.<br />La méthode bayésienne ne détecte pas non plus la fondation si l'on force une histoire démographique en marche d'escalier, pour la même raison. La fondation et l'explosion deviennent détectables si le modèle démographique les autorise. Toutefois, les dépendances entre les paramètres du modèle empêchent de les inférer marginalement avec précision. Toute information a priori sur un paramètre contraint fortement les valeurs des autres paramètres. Ce constat confirme le potentiel de populations d'histoire documentée pour l'estimation indirecte des paramètres d'un modèle de mutation des marqueurs.