In this thesis, we consider three fundamental problems of transducers theory. The containment problem asks, given two transducers,whether the relation defined by the first is included into the relation defined by the second. The equivalence problem asks, given two transducers,whether they define the same relation. Finally, the sequential uniformisation problem,corresponding to the synthesis problem in the setting of transducers,asks, given a transducer, whether it is possible to deterministically pick an output correspondingto each input of its domain. These three decision problems are undecidable in general. As a first step, we consider different manners of recovering the decidability of the three problems considered.First, we characterise a family of classes of transducers, called controlled by effective languages, for which the containment and equivalence problems are decidable. Second, we add structural constraints to the problems considered: for instance, instead of only asking that two transducers define the same relation, we require that this relation is defined by both transducers in a similar way. This `similarity' is formalised through the notion of delay,used to measure the difference between the output production of two transducers. This allows us to introduce stronger decidable versions of our three decision problems, which we use to prove the decidability of the original problems in the setting of finite-valued transducers. In the second part, we study extensions of the automaton model,together with the adaptation of the sequential uniformisation problems to these new settings.Weighted automata are automata which,along each transition, output a weight in Z. Then, whereas a transducer preserves all the output mapped to a given input, weighted automata only preserve the maximal weight. In this setting, the sequential uniformisation problem turns into the determinisation problem: given a weighted automaton, is it possible to deterministically pick the maximal output mapped to each input? The decidability of this problem is open.The notion of delay allows us to devise a complete semi-algorithm deciding it. Finally, we consider two-way transducers, that are allowed to move back and forth over the input tape. These transducers enjoy good properties with respect to the sequential uniformisation problem: every transducer admits a sequential two-way uniformiser. We strengthen this result by showing that every transducer admits a reversible two-way uniformiser, i.e. a uniformiser that is both sequential and cosequential (backward sequential). / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

In this thesis, we are concerned with multi-player games played on finite graphs. They are games in which the players interact trying to fulfil their own objectives which are not necessarily antagonistic to the others’. More particularly, we are interested in the study of dynamics which model the behaviour of the players when they repeatedly update their strategy in order to achieve a better outcome. A dynamics terminates when these updates converge to a state in which the players have no incentive to further update their respective strategies. We define several dynamics characterised by the type of updates made by the players.There are two types of contributions in this thesis. The first one is to draw a general framework to reason about the termination of dynamics in order to show its applicability to particular problems. In this abstract framework, we present several meta-theorems that make the links between games and dynamics explicit. For example, we introduce a notion of game minor that allows to induce simulations between the associated dynamics. The second type of contribution is the application of dynamics to a particular context, characterised by three parameters: the arena of the game, the conditions over the dynamics, and the payoff functions of the players. The first arena we deal with are sequential games (or games played on trees). Among other results, we prove that the acyclicity of the preferences is a necessary and sufficient condition to ensure the termination of dynamics that respect the Subgame Improvement Property (i.e. every update has to improve the payoff in the subgame of the change).Another studied arena is the so called One-player Games. We model BGP (Border Gateway Protocol, which is a standard interdomain routing protocol) into dynamics on graphs. We firstly revisit some classical results of network theory in our context, then we identify a theoretical and relevant framework regarding to the termination of the dynamics. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

Cette thèse a pour but d'illustrer et de faire avancer l'état des connaissances sur certaines problématiques liées à l'utilisation de la cryptographie résistante à un adversaire muni d'un ordinateur quantique. L'intérêt suscité par le développement d'algorithmes dit "post-quantiques" a pris une ampleur majeure dans les dernières années suite aux progrès techniques de l'informatique quantique et la décision du NIST (National Institute of Standards and Technology) d'organiser un projet de standardisation. En particulier, nous nous intéressons aux algorithmes basant leur sécurité sur la difficulté de résoudre certains problèmes liés a un object mathématique appelé emph{réseau euclidien}. Ce type de cryptographie ayant déjà été étudiée de manière soutenue en théorie, une partie la communauté scientifique s'est maintenant tournée vers les aspects pratiques. Nous présentons dans la thèse trois sujets majeurs relatifs à ces aspects pratiques, chacun discuté dans un chapitre soutenu par une publication scientifique. Le premier sujet est celui des implémentations efficaces. L'utilisation de la cryptographie dans la société moderne implique de programmer du matériel informatique sécurisant des données. Trouver la manière la plus efficace d'implémenter les fonctions mathématiques décrites dans les spécifications de l'algorithme n'est pas toujours simple. Dans le chapitre correspondant à ce premier sujet, nous allons présenter un papier établissant la façon la plus rapide connue actuellement d'implémenter certains algorithmes participant au projet du NIST. Le deuxième sujet est celui des attaques par canaux auxiliaires. Une fois l'algorithme implémenté, son utilisation dans le monde physique donne une surface d'attaque étendue à l'adversaire. Certaines techniques sont connues pour mitiger les nouvelles attaques pouvant survenir. Dans ce chapitre, nous étudierons l'application d'une technique appelée emph{masquage} qui a été appliquée à un algorithme de signature post-quantique, lui aussi candidat au projet du NIST. Finalement, le dernier chapitre de contributions s'intéresse à la possibilité de fusionner deux algorithmes afin de créer un outil spécialisé plus efficace que l'utilisation des deux algorithmes de base. Cette technique de fusion était déjà connue par le passé mais n'avait été beaucoup étudiée dans le cadre de la cryptographie post-quantique. Ce dernier aspect est donc légèrement plus orienté design que purement pratique, mais la possibilité de fusionner à moindre coup des fonctionnalités permet d'avoir un gain concret lors de l'utilisation. / Option Informatique du Doctorat en Sciences / info:eu-repo/semantics/nonPublished

Dans cette thèse nous nous intéressons à la mesure de dépendance sous des modèles de copules. Nous y traitons trois problèmes : la mesure d’association dans le cas bidimensionnel en présence de seuils de détection, la mesure d’association pour des données en grappes et la mesure d’association pour des données hiérarchiques. Le premier problème, indépendant des deux autres, concerne la mesure d’association entre deux variables sujettes à une censure à gauche fixe due à l’existence de seuils de détection. Nous définissons une version conditionnelle du tau de Kendall permettant de mesurer l’association entre de telles variables. Nous en proposons un estimateur non paramétrique et en étudions les propriétés asymptotiques. Nous supposons, ensuite, un modèle de copule Archimédienne et en déduisons un estimateur pour le tau de Kendall global. Un test d’ajustement de copules à ce type de données est développé. Le deuxième problème traite de la mesure d’association dans un cadre multidimensionnel pour des données en grappes telles que les observations à l’intérieur de chaque groupe sont échangeables. Pour cela, nous introduisons le tau de Kendall échangeable comme une mesure d’association intra-classe et présentons un estimateur non paramétrique pour cette mesure. Ses propriétés asymptotiques sont étudiées sous un modèle de copules multidimensionnelles caractérisées par une propriété appelée échangeabilité. Nous en déduisons un estimateur du coefficient de corrélation intra-classe pour des données provenant d’une distribution elliptique. Nous dérivons ses propriétés asymptotiques sous un modèle ANOVA généralisé à un facteur. Enfin, nous développons un test d’indépendence basé sur le tau de Kendall. Le troisième problème est une extension du deuxième au cas de données hiérarchiques avec des sous-groupes imbriqués dans des groupes, dans le cas où les unités à l’intérieur de chaque sous-groupe sont échangeables et où les sous-groupes appartenant à un même groupe sont, eux mêmes, échangeables. Nous définissons alors deux mesures d’association basées sur le tau de Kendall échangeable et en proposons des estimateurs non paramétriques. Nous étudions les propriétés asymptotiques de ces estimateurs sous des modèles de copules hiérarchiques vérifiant certaines propriétés d’échangeabilité partielle. Pour les données provenant de copules meta-elliptiques hiérarchiques, nous déduisons des estimateurs pour les coefficients de corrélation intra-classe associés aux groupes et aux sous-groupes respectivement. Nous développons, enfin, des procédures de tests pour les effets de groupes et de sous-groupes. / In this thesis we are interested in measuring the dependence under copula models. We deal with three problems: the measure of association in the bivariate case in the presence of lower detection limits, the measure of association for clustered data and the measure of association for two-level hierarchical data. The first problem, independent of the other two, deals with the measure of association between two variables subject to fixed left censoring due to the presence of lower detection limits. We define a conditional version of Kendall’s tau to measure the association between such variables. We provide a nonparametric estimator of this measure and study its asymptotic properties. We then assume an Archimedean copula model and deduce an estimator for the copula’s Kendall’s tau. A goodness-of-fit test for the assumed copula is developed. The second problem deals with the measure of intra-class association for clustered data such that observations within each group are exchangeable. For this, we introduce an exchangeable version of Kendall’s tau as a measure of intra-class dependance and provide a nonparametric estimator for this measure. Its asymptotic properties are investigated under a multivariate exchangeable copula model. We derive an estimator of the intra-class correlation coefficient for data drawn from an elliptical distribution. The asymptotic properties of this estimator are investigated under a generalized oneway ANOVA model. Finally, we develop an intra-class independence test based on Kendall’s tau. The third problem is an extension of the second to the case of hierarchical data with a set of subgroups nested into groups, such that the units within each subgroup are exchangeable and the subgroups belonging to the same group are themselves exchangeable. We define two association measures based on the exchangeable Kendall’s tau and propose nonparametric estimators for these measures. We investigate their asymptotic properties under hierarchical copula models satisfying some properties of partial exchangeability. For data drawn from meta-elliptical hierarchical copulas we deduce estimators for the intra-class correlation coefficients associated to groups and subgroups respectively. We also develop procedures for testing the effects of groups and subgroups.

Les problèmes d’optimisation apparaissent dans presque tous les domaines scientifiques. Cependant, le processus laborieux de conception d’un optimiseur approprié peut demeurer infructueux. La question la plus ambitieuse de l’optimisation est peut-être de savoir comment concevoir des optimiseurs suffisamment flexibles pour s’adapter à un grand nombre de scénarios, tout en atteignant des performances de pointe. Dans ce travail, nous visons donner une réponse potentielle à cette question en étudiant comment faire un méta-apprentissage d’optimiseurs à base de population. Nous motivons et décrivons une modélisation commune pour la plupart des algorithmes basés sur la population, qui présentent des principes d’adaptation générale. Cette structure permet de dériver un cadre de méta-apprentissage basé sur un processus de décision de Markov partiellement observable (POMDP). Notre formulation conceptuelle fournit une méthodologie générale pour apprendre l’algorithme d’optimisation lui-même, présenté comme un problème de méta-apprentissage ou d’apprentissage pour optimiser à l’aide d’ensembles de données d’analyse comparative en boîte noire, pour former des optimiseurs polyvalents efficaces. Nous estimons une fonction d’apprentissage de méta-perte basée sur les performances d’algorithmes stochastiques. Notre analyse expérimentale indique que cette nouvelle fonction de méta-perte encourage l’algorithme appris à être efficace et robuste à une convergence prématurée. En outre, nous montrons que notre approche peut modifier le comportement de recherche d’un algorithme pour s’adapter facilement à un nouveau contexte et être efficace par rapport aux algorithmes de pointe, tels que CMA-ES. / Optimization problems appear in almost any scientific field. However, the laborious process to design a suitable optimizer may lead to an unsuccessful outcome. Perhaps the most ambitious question in optimization is how we can design optimizers that can be flexible enough to adapt to a vast number of scenarios while at the same time reaching state-of-the-art performance. In this work, we aim to give a potential answer to this question by investigating how to metalearn population-based optimizers. We motivate and describe a common structure for most population-based algorithms, which present principles for general adaptation. This structure can derive a meta-learning framework based on a Partially observable Markov decision process (POMDP). Our conceptual formulation provides a general methodology to learn the optimizer algorithm itself, framed as a meta-learning or learning-to-optimize problem using black-box benchmarking datasets to train efficient general-purpose optimizers. We estimate a meta-loss training function based on stochastic algorithms’ performance. Our experimental analysis indicates that this new meta-loss function encourages the learned algorithm to be sample efficient and robust to premature convergence. Besides, we show that our approach can alter an algorithm’s search behavior to fit easily in a new context and be sample efficient compared to state-of-the-art algorithms, such as CMA-ES.

Dans la première partie de ce manuscrit nous étudions les fonctions rationnelles, c'est-à-dire définies par des transducteurs unidirectionnels. Notre objectif est d'étendre aux transductions les nombreuses correspondances logique-algèbre qui ont été établies concernant les langages, notamment le célèbre théorème de Schützenberger-McNaughton-Papert. Dans le cadre des fonctions rationnelles sur les mots finis, nous obtenons une caractérisation à la Myhill-Nerode en termes de congruences d'indice fini. Cette caractérisation nous permet d'obtenir un résultat de transfert, à partir d'équivalences logique-algèbre pour les langages vers des équivalences pour les transductions. En particulier nous montrons comment décider si une fonction rationnelle est définissable en logique du premier ordre. Sur les mots infinis, nous pouvons également décider la définissabilité en logique du premier ordre, mais avec des résultats moins généraux.Les fonctions rationnelles sur les mots infinis sont plus difficiles à caractériser et nous obtenons un résultat plus faible: étant donné un transducteur nous montrons comment calculer un transducteur canonique, c'est-à-dire indépendant du transducteur initial, réalisant la même fonction.Cependant cette machine canonique nous permet tout de même de décider si une fonction est définissable en logique du premier ordre.Dans la seconde partie nous introduisons une logique pour les transductions et nous résolvons le problème de synthèse régulière: étant donnée une formule de la logique, peut-on obtenir un transducteur bidirectionnel déterministe satisfaisant la formule ?Dans la seconde partie nous considérons un problème de synthèse: étant donné une relation (spécification) peut-on obtenir une fonction (un programme) qui est inclus dans (qui satisfait) la relation. Les fonctions réalisées par des transducteurs bidirectionnels déterministes sont caractérisés par plusieurs modèles différents, y compris par les transducteurs MSO, et ont ainsi été nommées transductions régulières.Nous introduisons une logique expressive pour les transduction et nous résolvons le problème de synthèse régulière pour cette logique.Plus précisément nous fournissons un algorithme qui produit toujours une fonction régulière satisfaisant une spécification donnée en entrée.Nous exposons également un lien intéressant entre les transductions et les mots avec données.Par conséquent nous obtenons une logique expressive pour les mots avec données, pour laquelle le problème de satisfiabilité est décidable. / Option Informatique du Doctorat en Sciences / info:eu-repo/semantics/nonPublished

Titre de l'écran-titre (visionné le 5 septembre 2023) / L'industrie forestière canadienne joue un rôle majeur dans l'économie du pays et les forêts canadiennes représentent une source importante de bois à l'échelle mondiale. Dans ce contexte, le triage et le transport du bois revêtent une grande importance pour assurer le bon fonctionnement de la chaîne de valeur forestière. Ce projet de recherche vise à explorer différentes stratégies de triage dans les secteurs forestiers, dans le but de mieux coordonner l'approvisionnement en bois avec les besoins spécifiques des usines de transformation. Pour atteindre cet objectif, nous avons développé un modèle d'optimisation basé sur la programmation mathématique, en plus d'un outil de traitement de données permettant de traiter les données reçues de notre partenaire industriel et de former des fichiers de données pour alimenter notre modèle d'optimisation. Ce modèle permet d'évaluer la rentabilité des différentes stratégies de triage pour fournir par la suite la meilleurs distribution des méthodes de triage dans les zones de récolte forestière. Des expérimentations ont été menées en prenant en compte différents paramètres comme le nombre et le type de piles de bois formées en forêt. Notre étude a permis de mettre sur pied un modèle d'aide à la prise de décision qui facilite le choix des méthodes de triage à utiliser en forêt. Ce modèle prend en compte plusieurs facteurs, dont les types de piles pouvant être formées en forêt, la demande des usines, les distances de transport forêt-usines et les distances inter-usines. Cette recherche constitue donc une contribution intéressante dans le domaine de l'optimisation du triage et du transport du bois, en fournissant une méthodologie solide, un outil de traitement de données et un modèle d'optimisation précis. / The Canadian forest industry plays a significant role in the country's economy, while Canadian forests represent a major source of timber. In this context, wood sorting and transportation are of great importance to ensure the smooth functioning of the forest value chain. This research project aims to explore different sorting strategies in forest sectors in order to better coordinate wood supply with the specific needs of processing mills. To achieve this goal, we developed an optimization model based on mathematical programming, along with a data processing tool to exploit the data received from our industrial partner. This model allows for evaluating the profitability of different sorting strategies to subsequently provide the best distribution of sorting methods in forest harvesting areas. Experiments were conducted, taking into account various parameters such as the number and type of wood piles formed in the forest. Our study has resulted in the development of a decision-making tool that facilitates the selection of sorting methods to be used in the forest. This model takes into consideration several factors, including the types of piles that can be formed in the forest, the demand from mills, the distances for forest-to-mill and inter-mill wood transportation. This research contributes to the field of wood sorting and transportation optimization by providing a robust methodology, a data processing tool, and an accurate optimization model.

En 1995, la technologie LIDAR fait émergence en télédétection et entraîne avec elle une nouvelle forme de concurrence dans un domaine jusqu'alors dominé par les systèmes RADAR. Contrairement à ces derniers, l'émetteur d'un LIDAR opère à des fréquences au-delà des ondes radios, habituellement dans l'infrarouge, ce qui fait qu'une détection non cohérente doit être employée et que seule l'enveloppe des signaux est récupérée, formant ainsi des signaux réels. Alors que de multiples algorithmes ont été développés au l des années pour faire le traitement des signaux captés par l'antenne-réseau d'un RADAR, aucun n'était reconnu jusqu'à présent comme étant particulièrement performant lorsque utilisé avec des signaux réels. En 2015, dans le cadre d'un projet de recherche visant à améliorer la distance et la précision de la détection des objets à l'aide d'un LIDAR, une adaptation [1] du très populaire algorithme MUSIC développé par Schmidt fut réalisée a n de pouvoir l'utiliser selon le principe du temps de vol plutôt que pour les directions d'arrivée. Cette adaptation ouvrit la voie à l'utilisation d'algorithmes statistiques, à l'origine conçus pour les signaux avec information de phase, pour des signaux réels. Malheureusement, l'application directe de ces algorithmes requiert un temps d'exécution considérable et ce, en particulier lors de la formation, du traitement et de la décomposition propre de la matrice ReXX. Par conséquent, des optimisations doivent être considérées pour être en mesure d'en faire l'implantation dans du matériel à faible coût lorsqu'il est question d'opération en temps réel. Parmi ces optimisations, c'est l'utilisation de méthodes de suivi fondées sur la notion de sous-espace qui fait l'objet de cet ouvrage. Ces algorithmes reposent sur l'idée qu'il est possible d'oublier, de façon graduelle, les données du passé au pro t des nouvelles données sans avoir à passer par la formation de la matrice ReXX à chaque fois. Ainsi, les résultats démontrent qu'une réduction de 25% à 95% du temps d'exécution est possible dans un contexte d'utilisation conjointe, mais moins fréquente, avec une méthode à complexité algorithmique plus élevée. Par ailleurs, les résultats des essais réalisés par [1] ne couvrent que les cibles stationnaires. Par conséquent, ce projet vise à étendre cette étude aux cibles en mouvement. Les résultats obtenus permettent de démontrer l'efficacité des méthodes de suivi du sous-espace pour de tels cas. / In 1995, LIDAR systems emerged as a new alternative to the well-known RADAR systems for remote sensing applications. However, unlike RADAR, the operating frequency of LIDAR systems is above the radio frequencies and usually in the infrared which means that a non-coherent detection has to be used to retrieve the signal's enveloppe. While several signal processing algorithms have been developped for RADAR phased arrays, none of these algorithms are known, to this day, to be e cient when dealing with real, phaseless signals. In 2015, as part of a research project to enhance the detection precision and maximal distance of a LIDAR system, an adaptation [1] of the so-called MUSIC algorithm developped by Schmidt was realised to be used with the time-of- ight principle instead of the direction of arrival principle. Unfortunately, the direct application of the adapted algorithm was time consuming, especially the creation, processing and eigendecomposition stages of the ReXX matrix. As so, optimizations are required to allow its implementation into a low-cost system for real-time purposes. Among those optimizations, the use of subspace tracking methods will be studied in this thesis. Subspace tracking algorithms are based on the idea that instead of having to create ReXX at each data update, one can use the known data while adding the new data with a forgetting factor. The result of these optimizations is that a decrease of 25% to 95% in execution time is observed when subspace tracking is used together with a higher complexity method to initialize its parameters. The study realised by [1] was mostly done for stationary objects. This thesis aims to extend that study to non stationary objects. Results show that using subspace tracking methods is even more efficient in these cases.

No description available.

Dans ce mémoire nous définissons la fonction de profondeur de Tukey d’une mesure positive et finie sur Rd. Par la suite nous étudions les propriétés de cette fonction, notamment les propriétés de continuité et de convexité. Notre objectif est d’établir une caractérisation d’une mesure par sa fonction de profondeur. Plus précisément, étant donné μ et v deux mesures de Borel positives et finies sur Rd, a-t-on μ = v si μ et v ont la même fonction de profondeur? En utilisant des propriétés de la fonction de profondeur, nous établissons une caractérisation lorsque la mesure satisfait certaines propriétés géométriques. Par la suite, nous présentons quelques approches afin de calculer la fonction de profondeur d’une mesure. Enfin nous prouvons le théorème de caractérisation d’une mesure discrète par sa fonction de profondeur de Tukey. / In this memoir we define the Tukey depth function of a positive finite measure on Rd. Then we study the properties of this function, in particular the properties of continuity and convexity. We seek to establish a characterization of a measure by its depth function. That is, given μ, v finite positive measures on Rd, do we have μ = v if μ and v have the same Tukey depth function? We use the properties of the depth function to establish such a characterization when the measure satisfies certain geometric properties. Then we exhibit some approaches for computing the Tukey depth function. Finally we prove the theorem of characterisation of a discrete measure by its Tukey depth function.