Dans cette thèse, nous nous sommes intéressée à la mise en oeuvre d'algorithmes itératifs sur des grappes hétérogènes. Ces algorithmes fonctionnent avec un volume important de données (calcul de matrices, traitement d'images, etc.), qui sera réparti sur l'ensemble des processeurs. À chaque itération, des calculs indépendants sont effectués en parallèle et certaines communications ont lieu. Il n'existe pas de raison a priori de réduire le partitionnement des données à une unique dimension et de ne l'appliquer que sur un anneau de processeurs unidimensionnel. Cependant, un tel partitionnement est très naturel et nous montrerons que trouver l'optimal est déjà très difficile. Après cette étude sur le placement et l'équilibrage de charge pour plates-formes hétérogènes, nous nous sommes intéressée à la redistribution de données sur ces mêmes plates-formes, lorsque que les caractéristiques de ces dernières changent. En ce qui concerne les anneaux de processeurs homogènes, nous avons totalement résolu le problème : nous avons obtenu des algorithmes optimaux et prouvé leur exactitude dans le cas homogène et dans le cas hétérogène. En ce qui concerne les anneaux hétérogènes, le cas unidirectionnel a été totalement résolu, alors que le cas bidirectionnel reste ouvert. Cependant, sous l'hypothèse de redistribution légère, nous sommes capable de résoudre le problème de manière optimale.

Il existe de nombreux démonstrateurs automatiques qui effectuent des raisonnements modulo une théorie équationnelle, c'est-à-dire enconsidérant non pas des termes, mais des classes d'équivalence de termes. En général, les travaux accomplis dans ce domaine ont pour but de concevoir des techniques pour faire de la déduction modulo une théorie particulière. Dans [Avenhaus & Plaisted, 2001], Jürgen Avenhaus et David Plaisted ont cherché à déterminer des techniques qui pourraient être employées dans le traitement non plus d'une théorie particulière, mais de toute une classe de théories équationnelles: les théories permutatives. Les auteurs ont introduit les notions de terme stratifié et d'ensemble stratifié, et décrit les procédures qui devraient être implémentées dans un démonstrateur automatique basé sur ces termes stratifiés. Les propriétés de régularité de ces théories font qu'il est possible d'employer des techniques efficaces de théorie algorithmique des groupes pour les traiter. Les auteurs espéraient que l'efficacité de ces techniques contrebalancerait le nombre élevé de clauses qui pourraient être générées dans un démonstrateur automatique basé sur ces termes stratifiés. Cependant, les algorithmes proposés pour faire de la déduction avec des termes stratifiés sont basés sur une énumération explicite des éléments des groupes, et sont donc exponentiels. Dans ce mémoire, nous développons les travaux d'Avenhaus et Plaisted, et modifions leur formalisme pour pouvoir faire l'usage le plus intensif possible des techniques de théorie algorithmique des groupes.

L'objectif de cette thèse est d'étudier l'impact de la fatigue du consommateur sur son traitement de l'information ublicitaire. Plus précisément, nous désirons comprendre comment la fatigue influence le processus de traitement visuel de la publicité, ainsi que les attitudes et la mémorisation. En nous appuyant sur la théorie d'adéquation des ressources, nous postulons que le traitement de l'information publicitaire, et donc l'efficacité de la publicité, est optimal quand le niveau de ressources cognitives disponible (niveau de fatigue du consommateur) correspond au niveau de ressources exigé (niveau de complexité de la publicité). Nos résultats mettent en lumière des effets de la fatigue différents selon les deux échantillons de notre recherche (étudiants et salariés). Les étudiants fatigués adoptent une stratégie visuelle de balayage pour compenser les effets de la fatigue et rendre le traitement de l'information plus facile. Les salariés fatigués adoptent une stratégie visuelle d'attention soutenue consistant à mobiliser le peu de ressources disponibles pour traiter l'information de façon efficace. Cette stratégie visuelle d'attention soutenue a un impact positif sur la mémorisation de la publicité. Nous montrons enfin que la théorie d'adéquation des ressources n'est pas le cadre théorique approprié pour étudier notre objet de recherche. En effet, les ressources cognitives s'avèrent être dynamiques : si elles y sont motivées, les personnes peuvent adapter leur niveaude ressources à la tache à accomplir. Les implications théoriques, méthodologiques et managériales de ces résultats sont discutées.

Le travail de recherche présenté dans cette thèse se place en cryptographie symétrique. En particulier, nous nous intéressons à l'analyse et à la conception des systèmes de chiffrement par blocs. Les années 90 ont vu l'avènement de nombreuses attaques statistiques sur ces systèmes de chiffrement. Durant cette thèse, je me suis intéressée aux généralisations de la cryptanalyse différentielle. La première partie de ce manuscrit est dédiée à la présentation d'un certain nombre d'attaques statistiques sur les systèmes de chiffrement par blocs. Dans cette thèse nous donnons une méthode générale qui permet de calculer la complexité en donnée et la probabilité de succès des attaques statistiques simples. En en utilisant plusieurs différentielles nous généralisons la cryptanalyse différentielle et la cryptanalyse différentielle tronquée et nous étudions les complexités de cette attaque différentielle multiple. La seconde partie de cette thèse est dédiée à l'étude des critères sur les boîtes-S des systèmes de chiffrement par blocs qui permettent de prémunir ces systèmes de chiffrement contre les attaques différentielles. À la suite d'une étude approfondie de la résistance des boîtes-S, nous avons introduit un nouveau critère, plus précis que l'uniformité différentielle, nous permettant de mesurer la vulnérabilité des boîtes-S aux attaques différentielles. Dans cet manuscrit, nous introduisons la notion de spectre différentiel et étudions le spectre différentiel de différentes classes de fonctions puissances.

L'assimilation du contenu informatif à la complexité de calcul a plus de 50 ans, mais une manière d'exploiter pratiquement cette idée est venue plus récemment, avec la définition de mesures de similarité basées sur la compression des données, qui permettent d'estimer la quantité d'information partagée entre deux objets. Ces techniques sont effectivement utilisées dans des applications sur divers types de données avec une approche universelle et pratiquement sans paramètres. Toutefois, les difficultés de les appliquer à des grands ensembles de données ont été rarement abordées. Cette thèse propose une nouvelle mesure de similarité basée sur la compression des dictionnaires qui est plus rapide comparativement aux solutions connues, sans perte de performance. Cela augmente l'applicabilité de ces notions, ce qui permet de les tester sur des ensembles de données de taille jusqu'à 100 fois plus grande que ceux précédemment analysés dans la littérature. Ces résultats ont été obtenus par l'étude des relations entre la théorie du codage classique, la compression des données et la notion de complexité par Kolmogorov. Les objets sont décomposés dans un dictionnaire, qui est considéré comme un ensemble de règles pour générer un code ayant une signification sémantique de la structure de l'image: les dictionnaires extraits décrivent les régularités des données, et sont comparés pour estimer l'information partagée entre deux objets. Cela permet de définir un système de recherche des images qui nécessite une supervision minimale par l'utilisateur, car il saute les étapes d'extraction de caractéristiques typiques, souvent dépendantes de paramètres. Ainsi, les hypothèses subjectives qui peuvent fausser l'analyse sont enlevées, et a leur place une approche guidée par les données est adoptée. Diverses applications sont présentées, et ces méthodes sont employées sans aucun changement des paramètres à différents types de données: photographies numériques, images radar, textes, génomes d'ADN, et signaux sismiques.

Cette note de synthèse concerne le travail collectif enseignant (TCE), question que j'ai explorée au cours de mes recherches, à l'occasion d'enseignements à l'université et à travers la conduite de travaux d'étudiants. Trois objectifs sont poursuivis : 1/ comprendre les conceptualisations et les pratiques professionnelles spécifiques que le TCE génère chez les acteurs ; 2/ préciser la nature des situations de travail ou des dispositifs de formation qui sont propices à l'émergence de systèmes de représentations et de savoir-faire pertinents, ceux qui correspondent aux objectifs des acteurs et du curriculum ; 3/ identifier des postures et des démarches de recherche qui rendent possible l'étude du TCE en identifiant et en soutenant les dynamiques de développement professionnel propres aux acteurs et aux collectifs. La note comporte trois parties, référées à mes publications. La première vise à élaborer un cadre conceptuel permettant d'étudier l'enseignement comme un travail collectif faisant interagir de multiples acteurs au long du parcours éducationnel des apprenants. La deuxième concerne, d'abord, les conceptualisations et savoir-faire professionnels mobilisés au cours de ce travail collectif puis leur transformation sous l'effet des interactions sociales, celles qui sont inscrites dans le quotidien ou provoquées par un dispositif de formation. La troisième partie trace des cadres méthodologiques et épistémologiques permettant d'approfondir l'étude du TCE. La conclusion générale rassemble les aboutissements des réflexions et des recherches mises au jour au cours de la note afin de poser des principes pour la direction de futures recherches.

Au sein de cette thèse, nous étudions l'utilisation de codes dans les systèmes de diffusion distribués et dans les systèmes de stockage auto-réparant. Les codes ont été largement utilisés afin de construire des systèmes fiables à partir d'éléments non fiables. A ce titre, les codes sont très utiles dans les systèmes distribués et surpassent les approches sans codes. Cependant, dans la pratique, les codes sont souvent délaissés notamment à cause de leurs coûts de décodage élevés et de leurs coûts de réparation plus élevés. Nous étudions la possibilité de réduire les coûts annexes afin de rendre les codes plus attrayants. Ainsi, nous proposons d'adapter un protocole de diffusion épidémique afin de profiter au plus des codes fontaines et nous construisons de nouveaux codes réseau basse complexité. Puis nous étudions l'utilisation de codes réseaux dans les systèmes de stockage afin d'offrir des compromis optimaux entre coûts de stockage et de réparation.

Les logiques modales sont des logiques permettant la représentation et l'inférence de connaissances. La logique hybride est une extension de la logique modale de base contenant des nominaux, permettant de faire référence à un unique individu ou monde du modèle. Dans cette thèse nous présentons plusieurs algorithmes de tableaux pour logiques hybrides expressives. Nous présentons aussi une implémentation de ces calculs, et nous décrivons les tests de correction et de performance que nous avons effectués, ainsi que les outils les permettant. De plus, nous étudions en détail une famille particulière de logiques liée aux logiques hybrides : les logiques avec opérateurs de comptage. Nous étudions la complexité et la décidabilité de certains de ces langages.

L'UMTS est un nouveau standard de radiocommunications mobiles destiné à résoudre les problèmes des actuels réseaux de deuxième génération, proches localement de la saturation et limités dans leur offre de services multimédias par les faibles débits utiles supportés. L'UMTS représente une rupture technologique importante et nécessite un effort particulier pour la réa- lisation des équipements, car la complexité des traitements à effectuer a augmenté dans des proportions considérables. Les terminaux 3G, par exemple, devront embarquer une puissance de calcul supérieure de plus d'un ordre de grandeur à celle embarquée par leurs prédécesseurs. Après avoir introduit l'UMTS et une de ses interfaces radios, le Wideband CDMA, nous avons identifié l'estimation par le terminal du canal radiomobile par lequel a transité le signal émis par la station de base comme étant une des tâches susceptibles d'entraîner le plus grand nombre d'opérations à effectuer. Une solution originale à ce problème est proposée sous la forme d'un algorithme d'estimation itérative de canal à suppression de trajets. La complexité calculatoire de cet algorithme a l'inconvénient majeur de varier avec le carré du facteur de suréchantillonnage, ce qui empêche de travailler avec une valeur élevée de celui-ci, et par consé- quent ne permet pas d'obtenir une grande précision quant à l'estimation des instants d'arrivée des trajets. Ce problème est résolu en introduisant une version optimisée de cet algorithme, dont la complexité varie linéairement avec le facteur de suréchantillonnage. Conserver une com- plexité raisonnable tout en travaillant avec des facteurs de suréchantillonnage élevés devient réaliste, ce qui permet d'accéder à coût égal à une précision plus élevée qu'avec l'algorithme origininal. De plus, cette optimisation simplifie les opérations élémentaires effectuées par l'algo- rithme, ce qui a pour conséquence de rendre son implémentation sur une architecture hybride matérielle-logicielle plus efficace que son implémentation sur un seul processeur de signal. Une méthodologie de conception au niveau système est ensuite proposée pour réaliser cette architecture hybride dans un but de prototypage rapide. Cette méthodologie, bâtie autour du logiciel N2C, de la société CoWare, utilise un langage de haut niveau, surensemble du langage C auquel ont été rajoutées les constructions nécessaires pour décrire des architectures matérielles. L'algorithme est partitionné en une partie logicielle s'exécutant sur un cœur de DSP ST100 et un coprocesseur réalisé en logique câblée. De sévères incompatibilités logicielles ont empêché la réalisation de cette architecture hybride selon la méthodologie proposée, mais des résultats intéressants ont néanmoins été obtenus à partir d'une implémentation purement logicielle de l'algorithme proposé. L'architecture obtenue avec l'application des premières étapes de la méthodologie proposée à l'algorithme d'estimation de canal est décrite, ainsi que quelques suggestions faites à la société CoWare, Inc. pour l'amélioration de leur outil. Enfin, l'adéquation de la méthodologie proposée à un environnement de prototypage rapide est discutée et des pistes pour la réalisation d'un éventuel démonstrateur sont données.

On présente trois algorithmes dans cette thèse: Le premier algorithme résout de systèmes polynomiaux homogènes et paramétrés zéro-dimensionnels avec un temps simplement exponentiel en le nombre n des inconnus, cet algorithme décompose l'espace des paramètres en un nombre fini d'ensembles constructibles et calcule le nombre fini de solutions par de représentations rationnelles paramétriques uniformes sur chaque ensemble constructible. Le deuxième algorithme factorise absolument de polynômes multivariés paramétrés avec un temps simplement exponentiel en n et en la borne supérieure d de degrés de polynômes à factoriser. Le troisième algorithme décompose les variétés algébriques définies par de systèmes algébriques paramétrés de dimensions positives en composantes absolument irréductibles d'une manière uniforme sur les valeurs des paramètres. La complexité de cet algorithme est doublement exponentielle en n. D'autre part, la borne inférieure du problème de résolution de systèmes algébriques paramétrés est doublement exponentielle en n.