Tableau d'honneur de la Faculté des études supérieures et postdoctorales, 2016-2017 / Les courriels Spams (courriels indésirables ou pourriels) imposent des coûts annuels extrêmement lourds en termes de temps, d’espace de stockage et d’argent aux utilisateurs privés et aux entreprises. Afin de lutter efficacement contre le problème des spams, il ne suffit pas d’arrêter les messages de spam qui sont livrés à la boîte de réception de l’utilisateur. Il est obligatoire, soit d’essayer de trouver et de persécuter les spammeurs qui, généralement, se cachent derrière des réseaux complexes de dispositifs infectés, ou d’analyser le comportement des spammeurs afin de trouver des stratégies de défense appropriées. Cependant, une telle tâche est difficile en raison des techniques de camouflage, ce qui nécessite une analyse manuelle des spams corrélés pour trouver les spammeurs. Pour faciliter une telle analyse, qui doit être effectuée sur de grandes quantités des courriels non classés, nous proposons une méthodologie de regroupement catégorique, nommé CCTree, permettant de diviser un grand volume de spams en des campagnes, et ce, en se basant sur leur similarité structurale. Nous montrons l’efficacité et l’efficience de notre algorithme de clustering proposé par plusieurs expériences. Ensuite, une approche d’auto-apprentissage est proposée pour étiqueter les campagnes de spam en se basant sur le but des spammeur, par exemple, phishing. Les campagnes de spam marquées sont utilisées afin de former un classificateur, qui peut être appliqué dans la classification des nouveaux courriels de spam. En outre, les campagnes marquées, avec un ensemble de quatre autres critères de classement, sont ordonnées selon les priorités des enquêteurs. Finalement, une structure basée sur le semiring est proposée pour la représentation abstraite de CCTree. Le schéma abstrait de CCTree, nommé CCTree terme, est appliqué pour formaliser la parallélisation du CCTree. Grâce à un certain nombre d’analyses mathématiques et de résultats expérimentaux, nous montrons l’efficience et l’efficacité du cadre proposé. / Spam emails yearly impose extremely heavy costs in terms of time, storage space, and money to both private users and companies. To effectively fight the problem of spam emails, it is not enough to stop spam messages to be delivered to end user inbox or be collected in spam box. It is mandatory either to try to find and persecute the spammers, generally hiding behind complex networks of infected devices, which send spam emails against their user will, i.e. botnets; or analyze the spammer behavior to find appropriate strategies against it. However, such a task is difficult due to the camouflage techniques, which makes necessary a manual analysis of correlated spam emails to find the spammers. To facilitate such an analysis, which should be performed on large amounts of unclassified raw emails, we propose a categorical clustering methodology, named CCTree, to divide large amount of spam emails into spam campaigns by structural similarity. We show the effectiveness and efficiency of our proposed clustering algorithm through several experiments. Afterwards, a self-learning approach is proposed to label spam campaigns based on the goal of spammer, e.g. phishing. The labeled spam campaigns are used to train a classifier, which can be applied in classifying new spam emails. Furthermore, the labeled campaigns, with the set of four more ranking features, are ordered according to investigators priorities. A semiring-based structure is proposed to abstract CCTree representation. Through several theorems we show under some conditions the proposed approach fully abstracts the tree representation. The abstract schema of CCTree, named CCTree term, is applied to formalize CCTree parallelism. Through a number of mathematical analysis and experimental results, we show the efficiency and effectiveness of our proposed framework as an automatic tool for spam campaign detection, labeling, ranking, and formalization.

Les jeux de policiers et voleurs sont étudiés depuis une trentaine d’années en informatique et en mathématiques. Comme dans les jeux de poursuite en général, des poursuivants (les policiers) cherchent à capturer des évadés (les voleurs), cependant ici les joueurs agissent tour à tour et sont contraints de se déplacer sur une structure discrète. On suppose toujours que les joueurs connaissent les positions exactes de leurs opposants, autrement dit le jeu se déroule à information parfaite. La première définition d’un jeu de policiers-voleurs remonte à celle de Nowakowski et Winkler [39] et, indépendamment, Quilliot [46]. Cette première définition présente un jeu opposant un seul policier et un seul voleur avec des contraintes sur leurs vitesses de déplacement. Des extensions furent graduellement proposées telles que l’ajout de policiers et l’augmentation des vitesses de mouvement. En 2014, Bonato et MacGillivray [6] proposèrent une généralisation des jeux de policiers-voleurs pour permettre l’étude de ceux-ci dans leur globalité. Cependant, leur modèle ne couvre aucunement les jeux possédant des composantes stochastiques tels que ceux dans lesquels les voleurs peuvent bouger de manière aléatoire. Dans ce mémoire est donc présenté un nouveau modèle incluant des aspects stochastiques. En second lieu, on présente dans ce mémoire une application concrète de l’utilisation de ces jeux sous la forme d’une méthode de résolution d’un problème provenant de la théorie de la recherche. Alors que les jeux de policiers et voleurs utilisent l’hypothèse de l’information parfaite, les problèmes de recherches ne peuvent faire cette supposition. Il appert cependant que le jeu de policiers et voleurs peut être analysé comme une relaxation de contraintes d’un problème de recherche. Ce nouvel angle de vue est exploité pour la conception d’une borne supérieure sur la fonction objectif d’un problème de recherche pouvant être mise à contribution dans une méthode dite de branch and bound. / Cops and robbers games have been studied for the last thirty years in computer science and mathematics. As in general pursuit evasion games, pursuers (cops) seek to capture evaders (robbers), however here the players move in turn and are constrained to move on a discrete structure. It is always assumed that players know the exact location of their adversary, in other words the game is played with perfect information. The first definition of a cops and robbers game dates back to Nowakowski and Winkler [39] and, independantly, Quilliot [46]. This first definition presents a game opposing a single cop against a lone robber, both with constraints on their speed. Extensions were gradually formulated such as increasing the number of cops and the speed of the players. In 2014, Bonato and MacGillivray [6] presented a general characterization of cops and robbers games in order for them to be globally studied. However, their model does not take into account stochastic events that may occur such as the robbers moving in a random fashion. In this thesis, a novel model that includes stochastic elements is presented. Furthermore, we present in this thesis a concrete application of cops and robbers games in the form of a method of resolution of a problem from search theory. Although cops and robbers games assume perfect information, this hypothesis cannot be maintained in search problems. It appears however that cops and robbers games can be viewed as constraint relaxations of search problems. This point of view is made use of in the conception of an upper bound on the objective function of a search problem that is a applied in a branch and bound method.

La sécurité informatique est plus que jamais une préoccupation majeure de toute entreprise privée comme publique. Le contrôle d’accès, qui représente une composante importante de la sécurité des systèmes d’information, consiste à vérifier si un sujet possède les droits nécessaires pour accéder à un objet [43]. Il est régi par des règles qui peuvent être exprimées en différents langages. La validation de contrôle d’accès, également appelée analyse de conformité, consiste à vérifier, à intervalles réguliers, si ces règles de contrôle d’accès mises en oeuvre sont cohérentes et complètes par rapport à une politique de sécurité donnée. Plusieurs outils de contrôle d’accès sont applicables à cette fin. AVTAC (Automatic Validation Tool of Access Control) est un outil sur lequel nous avons apporté notre contribution. / Computer security is more than ever a major concern for any private or public company. Access control which is an important component of security of information systems consists on verifying whether a subject has the rights to access to an object. It is governed by rules that can be expressed in different languages. Validation of access control also called compliance is to check at regular intervals if the access control implemented rules are consistent and complete with respect to a given security policy or not. Several access control tools are applicable to this end. AVTAC (Automatic Validation Tool of Access Control) is the tool on which we made our contribution.

Les protocoles cryptographiques constituent le coeur de la sécurité dans les communications de tous genres. Ils assurent l’authentification des agents, la confidentialité des données, leur intégrité, l’atomicité des biens et de l’argent, la non-répudiation, etc. Ils sont utilisés dans tous les domaines : le commerce électronique, le domaine militaire, le vote électronique, etc. L’utilisation de la cryptographie est essentielle pour assurer la sécurité d’un protocole, mais elle n’est pas suffisante. En effet, on rapporte un nombre important de protocoles qui ont été longtemps considérés sécuritaires, mais qui se sont avérés défaillants avec le l’usage. Dire qu’un protocole est correct ou non est un problème nondécidable en général. Cependant, plusieurs méthodes (basées sur les logiques, sur le Model-Checking ou sur le typage, etc.) ont vu le jour pour répondre à cette question sous des hypothèses restrictives et ont abouti à des résultats variables. Dans cette thèse, nous suggérons une méthode semi-décidable d’analyse des protocoles cryptographiques pour la propriété de confidentialité. Elle se base sur une intuition : "Un protocole croissant est correct". Nous validons cette intuition et nous proposons le théorème fondamental de correction des protocoles croissants sous des conditions minimales. Ensuite nous proposons une famille de fonctions témoins ayant les propriétés requises pour certifier qu’un protocole est correct. Nous validons enfin notre méthode sur des protocoles communs. / Cryptographic protocols are the fundament of security in all communications. They allow agents’ authentication, data confidentiality, data integrity, atomicity of goods, atomicity of money, nonrepudiation, etc. They are used in all areas: e-commerce, military fields, electronic voting, etc. The use of cryptography is essential to ensure the protocol security, but it is not sufficient. Indeed, we report a significant number of cryptographic protocols that had long been considered safe, but have been proven faulty with usage. Saying that a protocol is correct or not is an undecidable problem in general. However, several methods (logic-based methods, Model-Checking-based methods, typing-based methods, etc.) have emerged to address this question under restrictive assumptions and led to varying results. In this thesis, we suggest a semi-decidable method for analyzing cryptographic protocols for secrecy. It is based on an intuition: "An increasing protocol is correct". We formally validate this intuition, and we state the fundamental theorem of correctness of increasing protocols under few conditions. Then, we propose a safe way to build a family of reliable functions that we call the witness-functions, to certify protocol’s correctness. Finally, we validate our method on common protocols.

Les services logiciels offerts par le cloud sont très en vogue dernièrement étant donné qu’ils exploitent une architecture offrant plusieurs avantages à leurs utilisateurs. Ces services permettent entre-autres à des utilisateurs distants de travailler de manière transparente sur des logiciels ou des applications internes avec toute l’infrastructure nécessaire au bon fonctionnement de ceux-ci. On pense par exemple à des documents Office ou aux bases de données exploitées par des logiciels développés à l’interne. Le présent mémoire s’intéresse au cas où plusieurs usagers voudraient travailler en parallèle sur des documents partagés en profitant des avantages du cloud tout en ne faisant pas de compromis sur la confidentialité des données manipulées. Pour éviter l’accès aux données confidentielles des utilisateurs par un fournisseur de services, nous proposons un processus qui permet de protéger la confidentialité des données qui transitent par ce fournisseur. Cette technique permet d’utiliser les services d’un cloud sans avoir besoin d’avoir confiance en celui-ci en ce qui concerne la confidentialité de nos données. Notre technique permet aussi de signer numériquement les changements apportés au document et éviter ainsi qu’un cloud malveillant puisse altérer les données. La technique présentée est par ailleurs compatible avec l’utilisation d’un secure element permettant d’encapsuler les opérations cryptographiques au niveau matériel. Le processus proposé s’applique aux contenus ne requérant pas d’interprétation de la part du fournisseur de services. / Software services provided by the cloud are very popular lately as they offer an architecture that has many advantages for their users. These services, for example, allow distant users to work transparently on legacy software provided by an enterprise, with all the resources needed by those. We can think of office documents or databases exploited by internally developped software. In this thesis, we take interest in the particular case where multiple users have to work simultaneously on shared office documents and take advantage from all the benefits provided by the cloud without having to compromise on the manipulated data’s confidentiality. To prevent cloud providers from accessing their users’s confidential data, we propose a process that protects both data’s confidentiality and integrity while it transfers in and out of the provider’s infrastructure. This technique allows the use of a cloud’s services for confidential work without the need for the users to trust the cloud’s behavior regarding confidentiality. Our technique also implements digital signatures for every change to the documents, which prevents unauthorized manipulations on it. The presented technique also uses a secure element enabling the encapsulation of cryptography operations at the hardware level. The process is applicable only to content which does not need any server-side interpretation from the cloud provider.

Dans le monde d'aujourd'hui où la plupart des aspects de la vie moderne sont traités par des systèmes informatiques, la vie privée est de plus en plus une grande préoccupation. En outre, les données ont été générées massivement et traitées en particulier dans les deux dernières années, ce qui motive les personnes et les organisations à externaliser leurs données massives à des environnements infonuagiques offerts par des fournisseurs de services. Ces environnements peuvent accomplir les tâches pour le stockage et l'analyse de données massives, car ils reposent principalement sur Hadoop MapReduce qui est conçu pour traiter efficacement des données massives en parallèle. Bien que l'externalisation de données massives dans le nuage facilite le traitement de données et réduit le coût de la maintenance et du stockage de données locales, elle soulève de nouveaux problèmes concernant la protection de la vie privée. Donc, comment on peut effectuer des calculs sur de données massives et sensibles tout en préservant la vie privée. Par conséquent, la construction de systèmes sécurisés pour la manipulation et le traitement de telles données privées et massives est cruciale. Nous avons besoin de mécanismes pour protéger les données privées, même lorsque le calcul en cours d'exécution est non sécurisé. Il y a eu plusieurs recherches ont porté sur la recherche de solutions aux problèmes de confidentialité et de sécurité lors de l'analyse de données dans les environnements infonuagique. Dans cette thèse, nous étudions quelques travaux existants pour protéger la vie privée de tout individu dans un ensemble de données, en particulier la notion de vie privée connue comme confidentialité différentielle. Confidentialité différentielle a été proposée afin de mieux protéger la vie privée du forage des données sensibles, assurant que le résultat global publié ne révèle rien sur la présence ou l'absence d'un individu donné. Enfin, nous proposons une idée de combiner confidentialité différentielle avec une autre méthode de préservation de la vie privée disponible. / In nowadays world where most aspects of modern life are handled and managed by computer systems, privacy has increasingly become a big concern. In addition, data has been massively generated and processed especially over the last two years. The rate at which data is generated on one hand, and the need to efficiently store and analyze it on the other hand, lead people and organizations to outsource their massive amounts of data (namely Big Data) to cloud environments supported by cloud service providers (CSPs). Such environments can perfectly undertake the tasks for storing and analyzing big data since they mainly rely on Hadoop MapReduce framework, which is designed to efficiently handle big data in parallel. Although outsourcing big data into the cloud facilitates data processing and reduces the maintenance cost of local data storage, it raises new problem concerning privacy protection. The question is how one can perform computations on sensitive and big data while still preserving privacy. Therefore, building secure systems for handling and processing such private massive data is crucial. We need mechanisms to protect private data even when the running computation is untrusted. There have been several researches and work focused on finding solutions to the privacy and security issues for data analytics on cloud environments. In this dissertation, we study some existing work to protect the privacy of any individual in a data set, specifically a notion of privacy known as differential privacy. Differential privacy has been proposed to better protect the privacy of data mining over sensitive data, ensuring that the released aggregate result gives almost nothing about whether or not any given individual has been contributed to the data set. Finally, we propose an idea of combining differential privacy with another available privacy preserving method.

La programmation par contraintes est une technique puissante pour résoudre, entre autres, des problèmes d'ordonnancement de grande envergure. L'ordonnancement vise à allouer dans le temps des tâches à des ressources. Lors de son exécution, une tâche consomme une ressource à un taux constant. Généralement, on cherche à optimiser une fonction objectif telle la durée totale d'un ordonnancement. Résoudre un problème d'ordonnancement signifie trouver quand chaque tâche doit débuter et quelle ressource doit l'exécuter. La plupart des problèmes d'ordonnancement sont NP-Difficiles. Conséquemment, il n'existe aucun algorithme connu capable de les résoudre en temps polynomial. Cependant, il existe des spécialisations aux problèmes d'ordonnancement qui ne sont pas NP-Complet. Ces problèmes peuvent être résolus en temps polynomial en utilisant des algorithmes qui leur sont propres. Notre objectif est d'explorer ces algorithmes d'ordonnancement dans plusieurs contextes variés. Les techniques de filtrage ont beaucoup évolué dans les dernières années en ordonnancement basé sur les contraintes. La proéminence des algorithmes de filtrage repose sur leur habilité à réduire l'arbre de recherche en excluant les valeurs des domaines qui ne participent pas à des solutions au problème. Nous proposons des améliorations et présentons des algorithmes de filtrage plus efficaces pour résoudre des problèmes classiques d'ordonnancement. De plus, nous présentons des adaptations de techniques de filtrage pour le cas où les tâches peuvent être retardées. Nous considérons aussi différentes propriétés de problèmes industriels et résolvons plus efficacement des problèmes où le critère d'optimisation n'est pas nécessairement le moment où la dernière tâche se termine. Par exemple, nous présentons des algorithmes à temps polynomial pour le cas où la quantité de ressources fluctue dans le temps, ou quand le coût d'exécuter une tâche au temps t dépend de t. / Constraint programming is a powerful methodology to solve large scale and practical scheduling problems. Resource-constrained scheduling deals with temporal allocation of a variety of tasks to a set of resources, where the tasks consume a certain amount of resource during their execution. Ordinarily, a desired objective function such as the total length of a feasible schedule, called the makespan, is optimized in scheduling problems. Solving the scheduling problem is equivalent to finding out when each task starts and which resource executes it. In general, the scheduling problems are NP-Hard. Consequently, there exists no known algorithm that can solve the problem by executing a polynomial number of instructions. Nonetheless, there exist specializations for scheduling problems that are not NP-Complete. Such problems can be solved in polynomial time using dedicated algorithms. We tackle such algorithms for scheduling problems in a variety of contexts. Filtering techniques are being developed and improved over the past years in constraint-based scheduling. The prominency of filtering algorithms lies on their power to shrink the search tree by excluding values from the domains which do not yield a feasible solution. We propose improvements and present faster filtering algorithms for classical scheduling problems. Furthermore, we establish the adaptions of filtering techniques to the case that the tasks can be delayed. We also consider distinct properties of industrial scheduling problems and solve more efficiently the scheduling problems whose optimization criteria is not necessarily the makespan. For instance, we present polynomial time algorithms for the case that the amount of available resources fluctuates over time, or when the cost of executing a task at time t is dependent on t.

Tableau d'honneur de la Faculté des études supérieures et postdoctorales, 2015-2016 / La compression des données est la technique informatique qui vise à réduire la taille de l'information pour minimiser l'espace de stockage nécessaire et accélérer la transmission des données dans les réseaux à bande passante limitée. Plusieurs techniques de compression telles que LZ77 et ses variantes souffrent d'un problème que nous appelons la redondance causée par la multiplicité d'encodages. La multiplicité d'encodages (ME) signifie que les données sources peuvent être encodées de différentes manières. Dans son cas le plus simple, ME se produit lorsqu'une technique de compression a la possibilité, au cours du processus d'encodage, de coder un symbole de différentes manières. La technique de compression par recyclage de bits a été introduite par D. Dubé et V. Beaudoin pour minimiser la redondance causée par ME. Des variantes de recyclage de bits ont été appliquées à LZ77 et les résultats expérimentaux obtenus conduisent à une meilleure compression (une réduction d'environ 9% de la taille des fichiers qui ont été compressés par Gzip en exploitant ME). Dubé et Beaudoin ont souligné que leur technique pourrait ne pas minimiser parfaitement la redondance causée par ME, car elle est construite sur la base du codage de Huffman qui n'a pas la capacité de traiter des mots de code (codewords) de longueurs fractionnaires, c'est-à-dire qu'elle permet de générer des mots de code de longueurs intégrales. En outre, le recyclage de bits s'appuie sur le codage de Huffman (HuBR) qui impose des contraintes supplémentaires pour éviter certaines situations qui diminuent sa performance. Contrairement aux codes de Huffman, le codage arithmétique (AC) peut manipuler des mots de code de longueurs fractionnaires. De plus, durant ces dernières décennies, les codes arithmétiques ont attiré plusieurs chercheurs vu qu'ils sont plus puissants et plus souples que les codes de Huffman. Par conséquent, ce travail vise à adapter le recyclage des bits pour les codes arithmétiques afin d'améliorer l'efficacité du codage et sa flexibilité. Nous avons abordé ce problème à travers nos quatre contributions (publiées). Ces contributions sont présentées dans cette thèse et peuvent être résumées comme suit. Premièrement, nous proposons une nouvelle technique utilisée pour adapter le recyclage de bits qui s'appuie sur les codes de Huffman (HuBR) au codage arithmétique. Cette technique est nommée recyclage de bits basé sur les codes arithmétiques (ACBR). Elle décrit le cadriciel et les principes de l'adaptation du HuBR à l'ACBR. Nous présentons aussi l'analyse théorique nécessaire pour estimer la redondance qui peut être réduite à l'aide de HuBR et ACBR pour les applications qui souffrent de ME. Cette analyse démontre que ACBR réalise un recyclage parfait dans tous les cas, tandis que HuBR ne réalise de telles performances que dans des cas très spécifiques. Deuxièmement, le problème de la technique ACBR précitée, c'est qu'elle requiert des calculs à précision arbitraire. Cela nécessite des ressources illimitées (ou infinies). Afin de bénéficier de cette dernière, nous proposons une nouvelle version à précision finie. Ladite technique devienne ainsi efficace et applicable sur les ordinateurs avec les registres classiques de taille fixe et peut être facilement interfacée avec les applications qui souffrent de ME. Troisièmement, nous proposons l'utilisation de HuBR et ACBR comme un moyen pour réduire la redondance afin d'obtenir un code binaire variable à fixe. Nous avons prouvé théoriquement et expérimentalement que les deux techniques permettent d'obtenir une amélioration significative (moins de redondance). À cet égard, ACBR surpasse HuBR et fournit une classe plus étendue des sources binaires qui pouvant bénéficier d'un dictionnaire pluriellement analysable. En outre, nous montrons qu'ACBR est plus souple que HuBR dans la pratique. Quatrièmement, nous utilisons HuBR pour réduire la redondance des codes équilibrés générés par l'algorithme de Knuth. Afin de comparer les performances de HuBR et ACBR, les résultats théoriques correspondants de HuBR et d'ACBR sont présentés. Les résultats montrent que les deux techniques réalisent presque la même réduction de redondance sur les codes équilibrés générés par l'algorithme de Knuth. / Data compression aims to reduce the size of data so that it requires less storage space and less communication channels bandwidth. Many compression techniques (such as LZ77 and its variants) suffer from a problem that we call the redundancy caused by the multiplicity of encodings. The Multiplicity of Encodings (ME) means that the source data may be encoded in more than one way. In its simplest case, it occurs when a compression technique with ME has the opportunity at certain steps, during the encoding process, to encode the same symbol in different ways. The Bit Recycling compression technique has been introduced by D. Dubé and V. Beaudoin to minimize the redundancy caused by ME. Variants of bit recycling have been applied on LZ77 and the experimental results showed that bit recycling achieved better compression (a reduction of about 9% in the size of files that have been compressed by Gzip) by exploiting ME. Dubé and Beaudoin have pointed out that their technique could not minimize the redundancy caused by ME perfectly since it is built on Huffman coding, which does not have the ability to deal with codewords of fractional lengths; i.e. it is constrained to generating codewords of integral lengths. Moreover, Huffman-based Bit Recycling (HuBR) has imposed an additional burden to avoid some situations that affect its performance negatively. Unlike Huffman coding, Arithmetic Coding (AC) can manipulate codewords of fractional lengths. Furthermore, it has attracted researchers in the last few decades since it is more powerful and flexible than Huffman coding. Accordingly, this work aims to address the problem of adapting bit recycling to arithmetic coding in order to improve the code effciency and the flexibility of HuBR. We addressed this problem through our four (published) contributions. These contributions are presented in this thesis and can be summarized as follows. Firstly, we propose a new scheme for adapting HuBR to AC. The proposed scheme, named Arithmetic-Coding-based Bit Recycling (ACBR), describes the framework and the principle of adapting HuBR to AC. We also present the necessary theoretical analysis that is required to estimate the average amount of redundancy that can be removed by HuBR and ACBR in the applications that suffer from ME, which shows that ACBR achieves perfect recycling in all cases whereas HuBR achieves perfect recycling only in very specific cases. Secondly, the problem of the aforementioned ACBR scheme is that it uses arbitrary-precision calculations, which requires unbounded (or infinite) resources. Hence, in order to benefit from ACBR in practice, we propose a new finite-precision version of the ACBR scheme, which makes it efficiently applicable on computers with conventional fixed-sized registers and can be easily interfaced with the applications that suffer from ME. Thirdly, we propose the use of both techniques (HuBR and ACBR) as the means to reduce the redundancy in plurally parsable dictionaries that are used to obtain a binary variable-to-fixed length code. We theoretically and experimentally show that both techniques achieve a significant improvement (less redundancy) in this respect, but ACBR outperforms HuBR and provides a wider class of binary sources that may benefit from a plurally parsable dictionary. Moreover, we show that ACBR is more flexible than HuBR in practice. Fourthly, we use HuBR to reduce the redundancy of the balanced codes generated by Knuth's algorithm. In order to compare the performance of HuBR and ACBR, the corresponding theoretical results and analysis of HuBR and ACBR are presented. The results show that both techniques achieved almost the same significant reduction in the redundancy of the balanced codes generated by Knuth's algorithm.

La navigation sécuritaire et efficace des robots mobiles repose grandement sur l’utilisation des capteurs embarqués. L’un des capteurs qui est de plus en plus utilisé pour cette tâche est le Light Detection And Ranging (LiDAR). Bien que les recherches récentes montrent une amélioration des performances de navigation basée sur les LiDARs, faire face à des environnements non structurés complexes ou des conditions météorologiques difficiles reste problématique. Dans ce mémoire, nous présentons une analyse de l’influence de telles conditions sur la navigation basée sur les LiDARs. Notre première contribution est d’évaluer comment les LiDARs sont affectés par les flocons de neige durant les tempêtes de neige. Pour ce faire, nous créons un nouvel ensemble de données en faisant l’acquisition de données durant six précipitations de neige. Une analyse statistique de ces ensembles de données, nous caractérisons la sensibilité de chaque capteur et montrons que les mesures de capteurs peuvent être modélisées de manière probabilistique. Nous montrons aussi que les précipitations de neige ont peu d’influence au-delà de 10 m. Notre seconde contribution est d’évaluer l’impact de structures tridimensionnelles complexes présentes en forêt sur les performances d’un algorithme de reconnaissance d’endroits. Nous avons acquis des données dans un environnement extérieur structuré et en forêt, ce qui permet d’évaluer l’influence de ces derniers sur les performances de reconnaissance d’endroits. Notre hypothèse est que, plus deux balayages laser sont proches l’un de l’autre, plus la croyance que ceux-ci proviennent du même endroit sera élevée, mais modulé par le niveau de complexité de l’environnement. Nos expériences confirment que la forêt, avec ses réseaux de branches compliqués et son feuillage, produit plus de données aberrantes et induit une chute plus rapide des performances de reconnaissance en fonction de la distance. Notre conclusion finale est que, les environnements complexes étudiés influencent négativement les performances de navigation basée sur les LiDARs, ce qui devrait être considéré pour développer des algorithmes de navigation robustes. / To ensure safe and efficient navigation, mobile robots heavily rely on their ability to use on-board sensors. One such sensor, increasingly used for robot navigation, is the Light Detection And Ranging (LiDAR). Although recent research showed improvement in LiDAR-based navigation, dealing with complex unstructured environments or difficult weather conditions remains problematic. In this thesis, we present an analysis of the influence of such challenging conditions on LiDAR-based navigation. Our first contribution is to evaluate how LiDARs are affected by snowflakes during snowstorms. To this end, we create a novel dataset by acquiring data during six snowfalls using four sensors simultaneously. Based on statistical analysis of this dataset, we characterized the sensitivity of each device and showed that sensor measurements can be modelled in a probabilistic manner. We also showed that falling snow has little impact beyond a range of 10 m. Our second contribution is to evaluate the impact of complex of three-dimensional structures, present in forests, on the performance of a LiDAR-based place recognition algorithm. We acquired data in structured outdoor environment and in forest, which allowed evaluating the impact of the environment on the place recognition performance. Our hypothesis was that the closer two scans are acquired from each other, the higher the belief that the scans originate from the same place will be, but modulated by the level of complexity of the environments. Our experiments confirmed that forests, with their intricate network of branches and foliage, produce more outliers and induce recognition performance to decrease more quickly with distance when compared with structured outdoor environment. Our conclusion is that falling snow conditions and forest environments negatively impact LiDAR-based navigation performance, which should be considered to develop robust navigation algorithms.

La prédiction de séquence comporte plusieurs applications en traitement du langage naturel, en bioinformatique, et en vision numérique. La complexité de calcul requise pour trouver la séquence optimale parmi un nombre exponentiel de possibilités limite cependant l’utilisation de tels algorithmes. Dans ce mémoire, nous proposons une approche permettant de résoudre cette recherche efficacement pour deux types de problèmes différents. Plus précisément, nous adressons le problème de pré-image en prédiction de structure nécessitant de trouver la séquence associée à une entrée arbitraire, et le problème consistant à trouver la séquence qui maximise la fonction de prédiction de plusieurs classificateurs et régresseurs à noyaux. Nous démontrons que ces deux problèmes se réduisent en un même problème combinatoire valide pour plusieurs noyaux à séquences. Pour ce problème, nous proposons une borne supérieure sur la fonction de prédiction pouvant être utilisée dans un algorithme de recherche branch and bound pour l’obtention de solutions optimales. Sur les tâches de reconnaissance de mots et de prédiction de phonèmes, l’approche proposée obtient des résultats compétitifs avec les algorithmes de prédiction de structure de l’état de l’art. De plus, la solution exacte du problème de pré-image augmente de manière significative les performances de prédiction en comparaison avec une approximation trouvée par l’heuristique la plus connue. Pour les tâches consistant à trouver la séquence maximisant la fonction de prédiction de classificateurs et régresseurs, nous montrons que des méthodes existantes peuvent être biaisées à prédire de longues séquences comportant des symboles répétitifs. Nous soulignons que ce biais est enlevé lorsque le noyau est normalisé. Finalement, nous présentons des résultats en conception de médicaments sur la découverte de composés principaux. Le code source peut être téléchargé à https://github.com/a-ro/preimage. / Sequence prediction algorithms have many applications in natural language processing, bioinformatics, and computer vision. However, the computational complexity required to find the optimal sequence among an exponential number of possibilities limits the use of such algorithms. In this thesis, we propose an approach to solve this search efficiently for two types of sequence prediction problems. More precisely, we address the pre-image problem encountered in structured output prediction, which consists of finding the sequence associated with an arbitrary input, and the problem of finding a sequence maximizing the prediction function of various kernel-based classifiers and regressors. We demonstrate that these problems reduce to a common combinatorial problem valid for many sequence kernels. For this problem, we propose an upper bound on the prediction function which has low computational complexity and which can be used in a branch and bound search algorithm to obtain optimal solutions. On the practical tasks of optical word recognition and grapheme-to-phoneme prediction, the proposed approach is shown to be competitive with state-of-the-art structured prediction algorithms. Moreover, the exact solution of the pre-image problem is shown to significantly improve the prediction accuracy in comparison with an approximation found by the best known heuristic. On the task of finding a sequence maximizing the prediction function of kernelbased classifiers and regressors, we highlight that existing methods can be biased toward long sequences that contain many repeated symbols. We demonstrate that this bias is removed when using normalized kernels. Finally, we present results for the discovery of lead compounds in drug discovery. The source code can be found at https://github.com/a-ro/preimage.