Nous introduisons un nouveau modèle de la communication à deux parties dans lequel nous nous intéressons au temps que prennent deux participants à effectuer une tâche à travers un canal avec délai d. Nous établissons quelques bornes supérieures et inférieures et comparons ce nouveau modèle aux modèles de communication classiques et quantiques étudiés dans la littérature. Nous montrons que la complexité de la communication d’une fonction sur un canal avec délai est bornée supérieurement par sa complexité de la communication modulo un facteur multiplicatif d/ lg d. Nous présentons ensuite quelques exemples de fonctions pour lesquelles une stratégie astucieuse se servant du temps mort confère un avantage sur une implémentation naïve d’un protocole de communication optimal en terme de complexité de la communication. Finalement, nous montrons qu’un canal avec délai permet de réaliser un échange de bit cryptographique, mais que, par lui-même, est insuffisant pour réaliser la primitive cryptographique de transfert équivoque. / We introduce a new communication complexity model in which we want to determine how much time of communication is needed by two players in order to execute arbitrary tasks on a channel with delay d. We establish a few basic lower and upper bounds and compare this new model to existing models such as the classical and quantum two-party models of communication. We show that the standard communication complexity of a function, modulo a factor of d/ lg d, constitutes an upper bound to its communication complexity on a delayed channel. We introduce a few examples on which a clever strategy depending on the delay procures a significant advantage over the naïve implementation of an optimal communication protocol. We then show that a delayed channel can be used to implement a cryptographic bit swap, but is insufficient on its own to implement an oblivious transfer scheme.

Thèse numérisée par la Direction des bibliothèques de l'Université de Montréal.

Cette thèse présente une nouvelle optimisation de l'interprétation fonctionnelle (dite "Dialectica") de Gödel pour l'extraction de programmes plus efficaces à partir de preuves arithmétiques et même analytiques (classiques). La version dite "légère" de Dialectica se combine aussi et encore plus facilement avec l'optimisation dite "monotone" de Kohlenbach sur l'interprétation fonctionnelle de Gödel pour l'extraction de majorants et marges plus efficaces à partir de preuves monotones (classiques). La Dialectica légère est obtenue par l'adaptation des quantificateurs "uniformes" (sans signification computationnelle) de Berger. En plus, sa présentation est faite dans le style de la Déduction Naturelle, comme amélioration de l'adaptation récente de Jørgensen s! ur la Dialectica originelle de Gödel. Un bon nombre d'exemples concrèts sont traités sur l'ordinateur par la nouvelle technique d'extraction de programmes. La comparaison en machine avec la technique de synthèse de programmes appelée "A-traduction raffinée" de Berger, Buchholz et Schwichtenberg montre une très bonne performance de la Dialectica légère. Cette dernière n'est dépassée que dans le cas du Lemme de Dickson. Nous développons aussi la théorie de la synthèse de programmes efficaces, de complexité calculatoire polynômiale en temps, par la nouvelle Dialectica légère (monotone). Dans ce but nous métissons deux structures préexistantes de Cook-Urquhart-Ferreira et respectivement Kohlenbach pour obtenir une "Analyse bornée par des polynômes en temps". Ici, le résultat théorique est prometteur mais des exemple! s pratiques restent encore à trouver pour montrer la diff! ére nce de cette structure par rapport à l'"Analyse bornée par un polynôme" de Kohlenbach.

Les modèles géométriques de calcul permettent d'effectuer des calculs à l'aide de primitives géométriques. Parmi eux, le modèle des machines à signaux se distingue par sa simplicité, ainsi que par sa puissance à réaliser efficacement de nombreux calculs. Nous nous proposons ici d'illustrer et de démontrer cette aptitude, en particulier dans le cas de processus massivement parallèles. Nous montrons d'abord à travers l'étude de fractales que les machines à signaux sont capables d'une utilisation massive et parallèle de l'espace. Une méthode de programmation géométrique modulaire est ensuite proposée pour construire des machines à partir de composants géométriques de base -- les modules -- munis de certaines fonctionnalités. Cette méthode est particulièrement adaptée pour la conception de calculs géométriques parallèles. Enfin, l'application de cette méthode et l'utilisation de certaines des structures fractales résultent en une résolution géométrique de problèmes difficiles comme les problèmes de satisfaisabilité booléenne SAT et Q-SAT. Ceux-ci, ainsi que plusieurs de leurs variantes, sont résolus par machines à signaux avec une complexité en temps intrinsèque au modèle, appelée profondeur de collisions, qui est polynomiale, illustrant ainsi l'efficacité et le pouvoir de calcul parallèle des machines à signaux.

Dans cette thèse, nous cherchons à comparer la complexité booléenne classique et la complexité algébrique, en étudiant des problèmes sur les polynômes. Nous considérons les modèles de calcul algébriques de Valiant et de Blum, Shub et Smale (BSS). Pour étudier les classes de complexité algébriques, il est naturel de partir des résultats et des questions ouvertes dans le cas booléen, et de regarder ce qu'il en est dans le contexte algébrique. La comparaison des résultats obtenus dans ces deux domains permet ainsi d'enrichir notre compréhension des deux théories. La première partie suit cette approche. En considérant un polynôme canoniquement associé à toute formule booléenne, nous obtenons un lien entre les questions de complexité booléenne sur la formule booléenne et les questions de complexité algébrique sur le polynôme. Nous avons étudié la complexité du calcul de ce polynôme dans le modèle de Valiant en fonction de la complexité de la formule booléenne, et avons obtenu des analogues algébriques à certains résultats booléens. Nous avons aussi pu utiliser des méthodes algébriques pour améliorer certains résultats booléens, en particulier de meilleures réductions de comptage. Une autre motivation aux modèles de calcul algébriques est d'offrir un cadre pour l‘analyse d’algorithmes continus. La seconde partie suit cette approche. Nous sommes partis d’algorithmes nouveaux pour la recherche de zéros approchés d'un système de n polynômes complexes à n inconnues. Jusqu'à présent il s'agissait d'algorithmes pour le modèle BSS. Nous avons étudié l'implémentabilité de ces algorithmes sur un ordinateur booléen et proposons un algorithme booléen. / In the present thesis, we try to compare the classical boolean complexity with the algebraic complexity, by studying problems related to polynomials. We consider the algebraic models from Valiant and from Blum, Shub and Smale (BSS). To study the algebraic complexity classes, one can start from results and open questions from the boolean case, and look at their translation in the algebraic context. The comparison of the results obtained in the two settings will then boost our understanding of both complexity theories. The first part follows this framework. By considering a polynomial canonically associated to a boolean formula, we get a link between boolean complexity issues on the formula and algebraic complexity problems on the polynomial. We studied the complexity of computing the polynomial in Valiant's model, as a function of the complexity of the boolean formula. We found algebraic counterparts to some boolean results. Along the way, we could also use some algebraic methods to improve boolean results, in particular by getting better counting reductions. Another motivation for algebraic models of computation is to offer an elegant framework to the study of numerical algorithms. The second part of this thesis follows this approach. We started from new algorithms for the search of approximate zeros of complex systems of n polynomials in n variables. Up to now, those were BSS machine algorithms. We studied the implementation of these algorithms on digital computers, and propose an algorithm using floating arithmetic for this problem.

Ce mémoire se veut d'abord un recueil des principales variantes de l'algorithme optimal en pire cas pour la résolution de problèmes convexes et fortement convexes sans contraintes présenté par Yurii Nesterov en 1983 et en 2004. Ces variantes seront présentées dans un cadre unifié et analysées de manière théorique et empirique. On y retrouve une analyse des rôles des différents paramètres composant l'algorithme de base ainsi que de l'influence des constantes L et mu, respectivement la constante de Lipschitz du gradient et la constante de forte convexité de la fonction objectif, sur le comportement des algorithmes. On présentera également une nouvelle variante hybride et nous démontrerons empiriquement qu'elle performe mieux que plusieurs variantes dans la majorité des situations. La comparaison empirique des différentes variantes sur des problèmes sans contraintes utilise un modèle de calcul se basant sur le nombre d'appels à un oracle de premier ordre plutôt que sur le nombre d'itérations. Enfin, une application de ces variantes sur trois instances de problèmes en imagerie numérique ainsi qu'une analyse empirique des résultats obtenus en confrontation avec la méthode optimale FISTA et l'algorithme classique L-BFGS-B viennent clore ce mémoire.

Récemment, une décision ministérielle crée un vent d’inquiétude au sein de la formation professionnelle (FP) de niveau secondaire. Le ministère de l’Éducation, du Loisir et du Sport (MELS) fait le choix de stopper la production des référentiels en évaluation, un instrument jugé indispensable à l’activité évaluative de sanction des compétences. La présente recherche tire son origine des changements exigés par le MELS pour l’évaluation des compétences et des répercussions que cela entraine sur les fonctions du personnel enseignant de cette filière. Pour nous, cette situation est préoccupante du fait que nous oeuvrons à la formation universitaire en enseignement professionnel. En effet, dans notre recherche doctorale, nous voulons mieux appréhender l’évaluation en FP, dans le but de soutenir les enseignants dans leur pratique. D’une manière spécifique, notre étude vise à comprendre les niveaux de complexité des situations évaluatives de compétences utilisées durant la première année du programme de Santé, assistance et soins infirmiers (SASI). Pour étudier ces situations évaluatives, nous avons conçu des outils d’analyse prenant la forme de différents continuums ciblant trois éléments particuliers: les ressources internes et externes, l’articulation qui existe entre ces ressources, puis le contexte déployé au moment de leur mise en oeuvre. Les données qualitatives examinées dans cette recherche proviennent d’une analyse documentaire, complétée par des entrevues semi-dirigées. S’ajoutant à ces modalités, un journal de bord a été tenu par la chercheure tout au long des phases de collecte et d’analyse des données. Au final, les résultats de cette étude montrent 5 configurations référant à des niveaux de complexité des situations évaluatives. Ces configurations particulières témoignent de « l’évaluation de l’installation des ressources » où figurent des zones d’évaluation et des niveaux de complexité distincts. Parmi ces niveaux, il existe des situations évaluatives d’« exploration », d’« appropriation », d’« application procédurale » et d’« intégration partielle ». C’est entre autres en prenant pour appuis théoriques les travaux de Roegiers (2007) et Roegiers, Dehon, Rampy, Ratziu et Rosy (2010) que nous sommes parvenues à conceptualiser, puis à produire ces résultats.

Au fil des dernières années, le développement d'applications Internet et le développement rapide des technologies mobiles ont provoqué, dans les organisations publiques et privées, la mise en place d'un mécanisme capable d'intégrer ces nouveaux développements aux systèmes d'information existants. Ce mécanisme doit être en mesure d'intégrer différentes structures et des technologies hétérogènes par le partage des données. C'est pourquoi il est important de faire un choix éclairé lorsqu'il faut sélectionner l'outil approprié pour l'intégration de ces systèmes. Dans ce projet de recherche, on propose le développement d'un cadre d'évaluation systématique pour les outils d'intégration de systèmes d'information par l'approche par médiateur, en focalisant l'évaluation sur trois critères : le temps d'implémentation, la performance et la complexité d'implémentation. (1) Le critère du temps porte sur l'évaluation du temps que prend l'implémentation d'un outil depuis l'étude bibliographique jusqu'à l'implémentation dans un prototype qui implémente différentes structures de données. (2) Le critère de performance consiste en la vitesse avec laquelle l'outil peut traiter différents jeux de données. (3) Le critère de complexité correspond à l'évaluation de la complexité d'implémentation de l'outil de manière quantitative basée sur l'application de différentes métriques logicielles. Ce dernier critère permet, en ajoutant une partie quantitative, de renforcer le premier critère qui donne une évaluation plus qualitative de la complexité d'implémentation de l'outil. Les résultats obtenus avec l'application du cadre d'évaluation pour les outils d'intégration ont permis de proposer un système de médiation comme mécanisme d'intégration de systèmes hétérogènes capable de traiter différentes structures de données, de faire le stockage de ces données et de les partager entre les systèmes intégrés en privilégiant la facilité d'implémentation, la performance ou encore la maintenabilité.

Les travaux exposés dans ce document portent essentiellement sur l'étude des cryptanalyses statistiques des chiffrements par blocs. Certains des résultats présentés sont cependant suffisamment généraux pour pouvoir être utilisés dans d'autres contextes comme les chiffrements à flot, les attaques par canaux cachés, ... Après avoir donné quelques notions de base nécessaires à la compréhension du document, l'on s'intéresse aux deux grandes familles de cryptanalyses statistiques : les cryptanalyses linéaires et cryptanalyses différentielles. Un état de l'art est effectué afin de pouvoir appréhender les différentes problématiques liées à ces cryptanalyses. Dans un second temps, le document présente les travaux effectués durant ces trois années de thèse. Ceux-ci portent en majorité sur l'analyse de la complexité en données et de la probabilité de succès des cryptanalyses statistiques. Est aussi présenté un algorithme de décodage des codes linéaires qui peut être utilisé pour retrouver la clef lors d'une cryptanalyse linéaire. Notons que deux attaques sont proposées sur des schémas de chiffrement reconnus. Une cryptanalyse linéaire multiple sur la totalité du DES et une cryptanalyse différentielle multiple sur 18 tours du chiffrement PRESENT. Ces deux attaques sont, à ce jour, les meilleures attaques connues de leur catégorie sur ces chiffrements. Enfin, un appendice contient tous les détails techniques et preuves calculatoires permettant d'obtenir les résultats importants de ce document.

La cryptographie basée sur le logarithme discret a connu de nombreuses avancées dans les dix dernières années, notamment avec l'utilisation de tores algébriques introduite par Lenstra et Verheul. Ici on axe notre travail sur la facette constructive de ces idées et se penche sur le paramétrage de ces structures. Van Dijk et Woodruff ont récemment proposé une solution pour représenter de manière compacte une famille de points d'un tore algébrique. Afin d'améliorer la complexité asymptotique de cet algorithme, on a recours à plusieurs outils. D'une part on utilise un nouveau type de bases pour les extensions de corps finis, les bases normales elliptiques dues à Couveignes et Lercier. Par ailleurs, les tailles des objets manipulés font intervenir des polynômes cyclotomiques et leurs inverses modulaires. L'amplitude de leurs coefficients intervient directement dans l'étude de complexité. Dans le cas où leurs indices sont des diviseurs d'un produit de deux nombres premiers, on parvient à des bornes voire des expressions explicites pour ces coefficients, qui permettent de conclure quant à l'amélioration du coût de communication dans des protocoles cryptographiques comme une négociation de clefs multiples de Diffie-Hellman.