Le test boîte blanche basé sur les chemins est largement utilisé pour la validation de programmes. A partir du graphe de flot de contrôle (CFG) du programme sous test, les cas de test sont générés en sélectionnant des chemins d'intérêt, puis en essayant de fournir, pour chaque chemin, des valeurs d'entrées concrètes qui déclencheront l'exécution du programme le long de ce chemin.Il existe de nombreuses manières de définir les chemins d'intérêt: les méthodes de test structurel sélectionnent des chemins remplissant un critère de couverture concernant les éléments du graphe; dans l'approche aléatoire, les chemins sont tirés selon une distribution de probabilité sur ces éléments. Ces méthodes aléatoires ont l'avantage de fournir un moyen d'évaluer la qualité d'un jeu de test à travers la probabilité minimale de couvrir un élément du critère.Fournir des valeurs concrètes d'entrées nécessite de construire le prédicat de cheminement chaque chemin, i.e. la conjonction des contraintes sur les entrées devant être vérifiée pour que le système s'exécute le long de ce chemin. Cette construction se fait par exécution symbolique. Les données de test sont ensuite déterminées par résolution de contraintes. Si le prédicat d'un chemin est insatisfiable, le chemin est dit infaisable. Il est très courant qu'un programme présente de tels chemins, leur nombre surpassent généralement de loin celui des faisables. Les chemins infaisables sélectionnés lors la première étape ne contribuent pas au jeu de test final, et doivent être tirés à nouveau. La présence de ces chemins pose un sérieux problème aux méthodes structurelles et à toutes les méthodes d'analyse statique, la qualité des approximations qu'elles fournissent étant réduite par les données calculées le long de chemins infaisables.De nombreuses méthodes ont été proposées pour résoudre ce problème, telles que le test concolique ou le test aléatoire basé sur les domaines d'entrée. Nous présentons un algorithme qui construit de meilleures approximations du comportement d'un programme que son CFG, produisant un nouveau CFG qui sur-approxime l'ensemble des chemins faisables mais présentant moins de chemins infaisables. C'est dans ce nouveau graphe que sont tirés les chemins.Nous avons modélisé notre approche et prouvé formellement, à l'aide de l'assistant de preuve interactif Isabelle/HOL, les propriétés principales établissant sa correction.Notre algorithme se base sur l'exécution symbolique et la résolution de contraintes, permettant de détecter si certains chemins sont infaisables ou non. Nos programmes peuvent contenir des boucles, et leurs graphes des cycles. Afin d'éviter de suivre infiniment les chemins cycliques, nous étendons l'exécution symbolique avec la détection de subsomptions. Une subsomption peut être vue comme le fait qu'un certain point atteint durant l'analyse est un cas particulier d'un autre atteint précédemment: il n'est pas nécessaire d'explorer les successeurs d'un point subsumé, ils sont subsumés par les successeurs du subsumeur. Notre algorithme a été implémenté par un prototype, dont la conception suit fidèlement la formalisation, offrant un haut niveau de confiance dans sa correction.Dans cette thèse, nous présentons les concepts théoriques sur lesquels notre approche se base, sa formalisation à l'aide d'Isabelle/HOL, les algorithmes implémentés par notre prototype et les diverses expériences menées et résultats obtenus à l'aide de ce prototype. / White-box, path-based, testing is largely used for the validation of programs. Given the control-flow graph (CFG) of the program under test, a test suit is generated by selecting a collection of paths of interest, then trying to provide, for each path, some concrete input values that will make the program follow that path during a run.For the first step, there are various ways to define paths of interest: structural testing methods select some set of paths that fulfills coverage criteria related to elements of the graph; in random-based techniques, paths are selected according to a given distribution of probability over these elements (for instance, uniform probability over all paths of length less than a given bound). Both approaches can be combined as in structural statistical testing. The random-based methods above have the advantage of providing a way to assess the quality of a test set as the minimal probability of covering an element of a criterion.The second step requires to produce for each path its path predicate, i.e. the conjunction of the constraints over the input parameters that must hold for the system to run along that path. This is done using symbolic execution. Then, constraint-solving is used to compute test data. If there is no input values such that the path predicate evaluates to true, the path is infeasible. It is very common for a program to have infeasible paths and such paths can largely outnumber feasible paths. Infeasible paths selected during the first step will not contribute to the final test suite, and there is no better choice than to select another path, hoping for its feasibility. Handling infeasible paths is the serious limitation of structural methods since most of the time is spent selecting useless paths. It is also a major challenge for all techniques in static analysis of programs, since the quality of the approximations they provide is lowered by data computed for paths that do not correspond to actual program runs.To overcome this problem, different methods have been proposed, like concolic testing or random testing based on the input domain. In path-biased random testing, paths are drawn according to a given distribution and their feasibility is checked in a second step. We present an algorithm that builds better approximations of the behavior of a program than its CFG, providing a transformed CFG, which still over-approximates the set of feasible paths but with fewer infeasible paths. This transformed graph is used for drawing paths at random.We modeled our graph transformations and formally proved, using the interactive theorem proving environment Isabelle/HOL, the key properties that establish the correctness of our approach.Our algorithm uses symbolic execution and constraint solving, which allows to detect whether some paths are infeasible. Since programs can contain loops, their graphs can contain cycles. In order to avoid to follow infinitely a cyclic path, we enrich symbolic execution with the detection of subsumptions. A subsumption can be interpreted as the fact that some node met during the analysis is a particular case of another node met previously: there is no need to explore the successors of the subsumed node: they are subsumed by the successors of the subsumer. Our algorithm has been implemented by a prototype, whose design closely follows said formalization, giving a good level of confidence in its correctness.In this thesis, we introduce the theoretical concepts on which our approach relies, its formalization in Isabelle/HOL, the algorithms our prototype implements and the various experiments done and results obtained using it.

La modulation codée est une technique de transmission efficace en largeur de bande qui intègre le codage de canal et la modulation en une seule entité et ce, afin d'améliorer les performances tout en conservant la même efficacité spectrale comparé à la modulation non codée. Les codes de parité à faible densité (low-density parity-check codes, LDPC) sont les codes correcteurs d'erreurs les plus puissants et approchent la limite de Shannon, tout en ayant une complexité de décodage relativement faible. L'idée de combiner les codes LDPC et la modulation efficace en largeur de bande a donc été considérée par de nombreux chercheurs. Dans ce mémoire, nous étudions une méthode de modulation codée à la fois puissante et efficace en largeur de bande, ayant d'excellentes performances de taux d'erreur binaire et une complexité d'implantation faible. Ceci est réalisé en utilisant un encodeur rapide, un décoder de faible complexité et aucun entrelaceur. Les performances du système proposé pour des transmissions sur un canal additif gaussien blanc et un canal à évanouissements plats de Rayleigh sont évaluées au moyen de simulations. Les résultats numériques montrent que la méthode de modulation codée utilisant la modulation d'amplitude en quadrature à M niveaux (M-QAM) peut atteindre d'excellentes performances pour toute une gamme d'efficacité spectrale. Une autre contribution de ce mémoire est une méthode simple pour réaliser une modulation codée adaptative avec les codes LDPC pour la transmission sur des canaux à évanouissements plats et lents de Rayleigh. Dans cette méthode, six combinaisons de paires encodeur modulateur sont employées pour une adaptation trame par trame. L'efficacité spectrale moyenne varie entre 0.5 et 5 bits/s/Hz lors de la transmission. Les résultats de simulation montrent que la modulation codée adaptative avec les codes LDPC offre une meilleure efficacité spectrale tout en maintenant une performance d'erreur acceptable.

L’objet de cette thèse est d’étudier plusieurs modèles probabilistes reliant les marches aléatoires et les arbres aléatoires issus de processus de branchement critiques.Dans la première partie, nous nous intéressons au modèle de marche aléatoire à valeurs dans un réseau euclidien et indexée par un arbre de Galton–Watson critique conditionné par la taille. Sous certaines hypothèses sur la loi de reproduction critique et la loi de saut centrée, nous obtenons, dans toutes les dimensions, la vitesse de croissance asymptotique du nombre de points visités par cette marche, lorsque la taille de l’arbre tend vers l’infini. Ces résultats nous permettent aussi de décrire le comportement asymptotique du nombre de points visités par une marche aléatoire branchante, quand la taille de la population initiale tend vers l’infini. Nous traitons également en parallèle certains cas où la marche aléatoire possède une dérive constante non nulle.Dans la deuxième partie, nous nous concentrons sur les propriétés fractales de la mesure harmonique des grands arbres de Galton–Watson critiques. On comprend par mesure harmonique la distribution de sortie, hors d’une boule centrée à la racine de l’arbre, d’une marche aléatoire simple sur cet arbre. Lorsque la loi de reproduction critique appartient au domaine d’attraction d’une loi stable, nous prouvons que la masse de la mesure harmonique est asymptotiquement concentrée sur une partie de la frontière, cette partie ayant une taille négligeable par rapport à celle de la frontière. En supposant que la loi de reproduction critique a une variance finie, nous arrivons à évaluer la masse de la mesure harmonique portée par un sommet de la frontière choisi uniformément au hasard. / The aim of this Ph. D. thesis is to study several probabilistic models linking the random walks and the random trees arising from critical branching processes.In the first part, we consider the model of random walk taking values in a Euclidean lattice and indexed by a critical Galton–Watson tree conditioned by the total progeny. Under some assumptions on the critical offspring distribution and the centered jump distribution, we obtain, in all dimensions, the asymptotic growth rate of the range of this random walk, when the size of the tree tends to infinity. These results also allow us to describe the asymptotic behavior of the range of a branching random walk, when the size of the initial population goes to infinity. In parallel, we treat likewise some cases where the random walk has a non-zero constant drift.In the second part, we focus on the fractal properties of the harmonic measure on large critical Galton–Watson trees. By harmonic measure, we mean the exit distribution from a ball centered at the root of the tree by simple random walk on this tree. If the critical offspring distribution is in the domain of attraction of a stable distribution, we prove that the mass of the harmonic measure is asymptotically concentrated on a boundary subset of negligible size with respect to that of the boundary. Assuming that the critical offspring distribution has a finite variance, we are able to calculate the mass of the harmonic measure carried by a random vertex uniformly chosen from the boundary.

La mise en évidence des mécanismes de sélection agissant sur les données génomiques structurées (ARN, Protéines, ADN...) nécessite l'élaboration de modèles de séquences. Une fois un tel modèle élaboré, il est possible, au prix d'une analyse mathématique parfois complexe ou par le biais de la<br />génération aléatoire, d'évaluer la significativité d'un phénomène observé. Tout d'abord, nous nous intéressons aux propriétés des grammaires pondérées, un formalisme particulièrement adapté à la modélisation de la structure des ARN, dérivant des algorithmes de génération aléatoire efficaces implémentés au sein du prototype GenRGenS. Nous abordons le calcul automatique des pondérations réalisant des valeurs observées pour les paramètres du modèle, ainsi qu'une implémentation basée sur une approche optimisation. Dans un second temps, nous abordons la modélisation de la structure secondaire d'ARN. Après quelques rappels de biologie moléculaire, nous proposons plusieurs modèles basés sur des grammaires pondérées permettant la génération de structures d'ARN réalistes. L'utilisation d'un algorithme d'optimisation permet le calculer des pondérations correspondant à certaines familles d'ARN. Nous proposons enfin un algorithme d'extraction de structure secondaire maximale dans une structure générale, qui permet de profiter des données récentes issues de la cristallographie. Le dernier chapitre de cette thèse s'intéresse à l'analyse d'un algorithme de recherche de similarité heuristique, dont la sensibilité s'avère étroitement liée à la probabilité de présence d'un motif au sein de marches aléatoires particulières, les chemins culminants. Ces marches restent positives, et atteignent une altitude maximale en leur dernier pas. Nous proposons un algorithme récursif de génération aléatoire pour ces chemins. En combinant des techniques issues de la combinatoire énumérative, l'analyse asymptotique et la théorie des langages, nous dérivons des algorithmes de génération aléatoire par rejet linéaires dans de nombreux cas.

La mésentéricine Y105 est une bactériocine de sous-classe IIa produite par Leuconostoc mesenteroides Y105. Pour comprendre le mécanisme de l'activité anti-Listeria de ce peptide et plus généralement des bactériocines de classe IIa, l'étude des relations existant entre la structure et la fonction de ce peptide a été envisagée. Dans ce but, une collection de mésentéricines Y105 modifiées au niveau d'un résidu a été produite. Afin d'obtenir ces dérivés de bactériocine, une méthode de mutagenèse aléatoire par PCR a été mise en place pour générer des séquences d'ADN, codant la bactériocine mature, modifiées sur un seul codon. Dans un deuxième temps, une méthode de production hétérologue de ces peptides mutés a été développée en utilisant d'une part un vecteur portant les gènes de structure des bactériocines, et d'autre part, un vecteur permettant l'expression de l'immunité et du transport de ces peptides. Un outil de production universelle de peptide a été élaboré. L'étude de l'impact des mutations sur l'activité antagoniste, la structure secondaire (analysée par dichroïsme circulaire en présence de trifluoroéthanol ou de micelles de lysophosphatidylcholine), la structure tridimensionnelle (prédite) et l'interaction de la mésentéricine Y105 avec des environnements mimant les membranes cibles (méthode d'extinction de la fluorescence intrinsèque du tryptophane) a été réalisée. Enfin, une analyse par résonance magnétique nucléaire (RMN) a été effectuée sur la bactériocine sauvage pour déterminer sa structure tridimensionnelle. De l'ensemble de ces données, un modèle d'action est proposé pour la mésentéricine Y105, ce modèle peut être étendu aux bactériocines de structure proche.

Cette thèse traite de la survie et des généalogies de populations en présence de sélection dans quelques modèles simples de physique statistique inspirés de la biologie.<br /><br />La première partie étudie l'évolution de marches aléatoires avec branchements unidimensionnelles en présence d'un seuil de survie qui croît linéairement au cours du temps. En reliant les propriétés de ces marches aléatoires à une équation de propagation de fronts, nous étudions la transition vers l'extinction de ces marches lorsque la vitesse du seuil croît et obtenons les comportements critiques de la probabilité de survie. Nous construisons également un processus biaisé décrivant une population de telles marches conditionnée sur sa taille à un instant final. Cette construction permet d'étudier le régime quasi-stationnaire près de la vitesse critique. Enfin, nous présentons un modèle exactement soluble sur lequel plusieurs conjectures peuvent être vérifiées.<br /><br />Dans une seconde partie, nous étudions des populations de taille constante du point de vue des généalogies et des temps de coalescence. Nous expliquons dans quelle mesure certains modèles d'évolution avec sélection se rapprochent des modèles de polymères dirigés et montrons plusieurs résultats numériques qui mettent en évidence l'existence de classes d'universalité dans les généalogies. En absence de sélection, nous étudions la dynamique des temps de coalescence et de l'âge de l'ancêtre commun d'une population, ainsi que les corrélations de ce dernier avec la diversité génétique dans un cas simple.

Cette thèse s'inscrit dans la problématique de la comparaison de graphes. Nous proposons dans la première partie de ce manuscrit plusieurs algorithmes de recherche de motifs similaires dans de grands graphes. La seconde partie de cette thèse traite de l'étude des arborescences de fichiers, structure de données pour laquelle la méthode initiale de reconnaissance de motifs a été développée. Nous présentons un modèle stochastique pour la génération aléatoire de structure arborescentes, basé sur les observations de l'étude statistique des données réelles. Enfin, nous détaillons deux adaptations de l'algorithme de reconnaissance de motifs similaires à des applications particulières. La première concerne la reconnaissance d'objets extraits de la video basse résolution pour l'indexation grossière. La deuxième application a été développée pour la visualisation de l'évolution de projets logiciels.

Le phénomène d'incertitude, dont les sources sont variées, est rencontré dans plusieurs domaines et on devrait y faire face. Cette incertitude est due essentiellement à notre incapacité à prédire avec exactitude le comportement futur d'une partie ou de la totalité d'un système. Dans les dernières décades, plusieurs techniques mathématiques ont été développées pour maitriser cette incertitude, afin de réduire son impact négatif, et par conséquent, l'impact négatif de notre méconnaissance. <br />Dans le domaine du « Supply Chain Management » la source principale d'incertitude est la demande future. Cette demande est, en général, modélisé par des lois de probabilité paramétrées en utilisant des techniques de prévision. L'impact de l'incertitude de la demande sur les performances de la « Supply Chain » est important: par exemple, le taux mondial de rupture de stock, dans l'industrie de distribution était en 2007 de 8.3%. De l'autre côté, le taux mondial de produits invendus, dans la grande distribution, était en 2003 de 1%. Ces deux types de coûts, qui sont dus essentiellement à l'incertitude de la demande, représentent des pertes significatives pour les différents acteurs de la « Supply Chain ».<br />Dans cette thèse, on s'intéresse au développement de modèles mathématiques de planification de production et de gestion de stock, qui prennent en compte ce phénomène d'incertitude sur la demande, essentiellement pour de produits à courte durée de vie. On propose plusieurs modèles de planification de production, à petit horizon de planification, qui prennent en compte les différents aspects de notre problématique, tels que les capacités de production, la remise à jour des prévisions de la demande, les options de réservation de capacité, et les options de retour « Payback » des produits. On souligne, dans ces modèles, un aspect important qui prend de l'ampleur à cause de la mondialisation, et qui est lié à la différence entre les coûts de production des différents fournisseurs. On propose à la fin de la thèse, un modèle généralisé qui pourrait être appliqué à des produits à longue durée de vie, et qui exploite quelques résultats obtenus pour les produits à courte durée de vie. Tous ces modèles sont résolus analytiquement ou bien numériquement en utilisant la programmation dynamique stochastique.

Le courant d'alimentation d'une carte à puce présente des corrélations significatives avec les données traitées par son microcontrôleur. Les techniques de cryptanalyse dites « par analyse en courant » exploitent ces corrélations pour déterminer les clés secrètes des cryptosystèmes embarqués. Cette étude traite de la conception d'un système d'alimentation sur puce destiné à protéger les microcontrôleurs encartables contre les attaques par analyse en courant. Le nouveau système proposé permet de réguler la tension d'alimentation interne du microcontrôleur à partir de la tension d'alimentation externe fournie par le lecteur, tout en décorrélant le courant d'alimentation externe du courant d'alimentation interne. Sa surface et son rendement respectent les contraintes imposées par le support. De plus, son architecture inclut un nouveau générateur d'horloge aléatoire basé, entre autres, sur un attracteur chaotique de type « double-scroll ». Le système a été simulé avec Eldo et les paramètres MM9 d'un procédé CMOS 0.18 µm standard de la société STMicroelectronics; les résultats des simulations témoignent de son efficacité. Par ailleurs, l'oscillateur chaotique a été fabriqué suivant le procédé CMOS 0.35 µm 2P/4M du fondeur AMS; les mesures expérimentales confirment les résultats théoriques.

Les voies de signalisation cellulaires permettent aux cellules de percevoir et d'échanger de l'information sous la forme de signaux chimiques. Un tel signal génère une réponse de la cellule au travers des étapes cruciales de réception et transduction. Différents types de protéines sont organisés dans une cascade de réactions de proche en proche qui relaient le signal de l'extérieur vers l'intérieur de la cellule, notamment au travers de la membrane. Les protéines de signalisation sont restreintes à des compartiments avec des degrés de liberté différents, et diffusent soit dans la membrane cellulaire qui est bidimensionnelle, soit dans le cytoplasme qui est en trois dimensions. De plus, au sein même de ces espaces, leurs distributions respectives sont hétérogènes. Or l'étude de la dynamique des voies de signalisation repose classiquement sur des modèles mathématiques supposant une homogénéité de distribution spatiale. Nous avons développé des modèles de réactions biochimiques entre populitions de molécules oú l'état et la position de chaque molécule sont caractérisés. La diffusion et les interactions entre molécules simulées sont reproduites sur la base de processus stochastiques issus de la biophysique. Ceci permet de recréer des distributions spatiales et des modes de diffusion hétérogènes tels qu'observés en biologie et d'étudier leur effet sur la dynamique de la signalisation en simulation. L'exploitation des modèles a été menée sur les différentes étapes de signalisation. Premièrement, l'étude a porté sur l'interaction entre un ligand dans le milieu extracellulaire et des récepteurs membranaires fixes. Lorsque les récepteurs forment des grappes au lieu d'être répartis uniformément, cela provoque une perte de sensibilité globale de l'étage de réception. Deuxièmement, l'analyse a été poursuivie au niveau de l'étage de transduction entre les récepteurs et un effecteur au niveau de la membrane. Là aussi, une distribution en grappe plutôt qu'uniforme des récepteurs provoque une perte de sensibilité. Enfin, l'étude s'est portée sur un modèle intégrant un mécanisme de diffusion non-homogène en mettant en interaction des récepteurs mobiles et leur substrat membranaire. Lorsque des zones restreintes de diffusion ralentie sont définies sur la membrane, deux effets opposés apparaissent sur la dynamique de transduction : un phénomène d'amplification si le ralentissement affecte les deux protéines, et un phénomène de perte de sensibilité si seuls les récepteurs sont ralentis. Globalement, les résultats illustrent comment les hétérogénéités spatiales modifient les distributions de collision et d'évènements de réaction dans le temps et l'espace à l'échelle microscopique, et comment cela se traduit par un effet sur la dynamique globale de la voie de signalisation à l'échelle macroscopique.