Cette thèse vise à développer des stratégies permettant d'augmenter la puissance du calcul séquentiel et des systèmes distribués, elle traite en particulier, la décomposition séquentielle des opérations ainsi que des systèmes d'édition collaboratifs décentralisés. Nous introduisons, une méthode d'indexage avec précision contrôlée. Celle-ci permet la génération d'identifiants uniques utilisés dans l'indexage des communications dans les systèmes distribués, plus particulièrement dans les systèmes d'édition collaboratifs décentralisés. Ces identifiants sont des nombres réels avec un motif de précision contrôlé. Un ensemble fini d'identifiants est conservé pour permettre le calcul de cardinalités locales et globales. Cette propriété joue un rôle prépondérant dans la gestion des communications indexées. De plus, d'autres propriétés incluant la préservation de l'ordre sont observées. La méthode d'indexage a été testée et vérifiée avec succès. Ceci a permis la conception d'un système d'édition collaboratif décentralisé. Aussi, nous explorons les stratégies existantes, relatives a la décomposition séquentielle d'opérations, que nous étendons à de nouvelles stratégies. Ces stratégies mènent à une optimisation (processeur, compilateur, mémoire, code). Ces styles de décomposition portent un intérêt majeur à la communauté scientifique. Des recherches et des implémentations de plus en plus rapides résultent de la conception d'unité arithmétique. / This thesis aims at developing strategies to enhance the power of sequential computation and distributed systems, particularly, it deals with sequential break down of operations and decentralized collaborative editing systems. In this thesis, we introduced precision control indexing method that generates unique identifiers which are used for indexed communication in distributed systems, particularly, in decentralized collaborative editing systems. These identifiers are still real numbers with a specific controlled pattern of precision. Set of identifiers is kept finite that makes it possible to compute local as well as global cardinality. This property plays important role in dealing with indexed communication. Besides this, some other properties including order preservation are observed. The indexing method is tested and verified by experimentation successfully and it leads to design decentralized collaborative editing system. Dealing with sequential break down of operations, we explore limitations of the existing strategies, extended the idea by introducing new strategies. These strategies lead towards optimization (processor, compiler, memory, code). This style of decomposition attracts research communities for further investigation and practical implementation that could lead towards designing an arithmetic unit.

Dans cette thèse, nous nous sommes intéressés à divers problèmes mettant en oeuvre des structures algébriques de certains anneaux fonctionnels, en particulier dans l'espace H infini des fonctions holomorphes bornées dans le disque unité, dans l'algèbre de Sarason H infini + C et dans C(X,t)={fEC(X) : fot=f}, avec X un espace compact séparé et t une involution topologique sur X. Plus précisément, nous avons caractérisé les idéaux radicaux finiment engendrés dans H infini + C. En second lieu, nous avons démontré que le rang stable absolu de C(X,t) coïncide avec le rang stable Bass et topologique de cette dernière. En dernier lieu, nous nous sommes intéressés au problème de la couronne généralisé dans H infini / In this thesis, we are interested in various problems of algebraic structures of some functional rings, in particular in the space H infinity of bounded analytic functions in the unit disc, in the Sarason algebra H infinity + C and in C(X,t)={fEC(X) : fot=f} with X compact Hausdorff space and t a topological involution on X. More precisely, we have characterized the finitely generated radical ideals in H infinity + C. Secondly, we have demonstrated that the absolute stable rank of C (X, t) coincides with Bass stable rank and topological stable rank. Finally, we are interested in the generalized corona problem in H infinity

Cette thèse est composée de deux axes principaux, le premier portant sur le chiffrement homomorphe et le second sur l’algèbre linéaire creuse sur corps finis. Avec l’essor des technologies de communication et en particulier d’internet, de nouveaux protocoles de chiffrement sont développés. En particulier, le besoin de systèmes de chiffrement permettant de manipuler les données chiffrées tout en assurant leur sécurité. C’est dans ce contexte que des systèmes de chiffrement homomorphe sont développés, ces protocoles permettent d’effectuer des calculs avec des données chiffrées. La sécurité de ce type système repose sur l’ajout de bruit aux messages à chiffrer. Ce bruit augmente avec chaque opération effectuée, mais il ne doit pas dépasser un certain seuil. Pour contourner ce problème, une technique nommée bootstrapping est utilisée permettant de réduire le bruit d’un chiffré. Les bootstrappings sont le goulot d’étranglement lors des calculs sur des données chiffrées, il est important d’en faire le moins possible. Or la quantité de bootstrappings à faire est déterminée par la nature des calculs à effectuer ainsi que du protocole de chiffrement utilisé.C’est dans ce contexte que notre travail intervient, nous proposons une méthode effective pour réduire le nombre bootstrappings basé sur la programmation linéaire en nombre entier. Cette méthode s’adapte à un grand nombre de protocoles de chiffrement. De plus, nous effectuons une analyse de la complexité de ce problème en montrant qu’il est APX-complet et nous fournissons un algorithme d’approximation.La résolution de système linéaire sur corps finis est une brique de calcul essentielle dans de nombreux problèmes de calcul formel. En particulier, beaucoup de problèmes produisent des matrices comprenant un grand nombre de zéros, on dit qu’elles sont creuses. Les meilleurs algorithmes permettant de résoudre ce type de système linéaire creux sont des algorithmes dits itératifs. L’opération fondamentale de ces algorithmes itératifs est la multiplication de la matrice par un vecteur ou une matrice dense. Afin d’obtenir les meilleures performances, il est important de tenir compte des propriétés (SIMD, multicoeurs, hiérarchie des caches ....) des processus modernes .C’est dans ce contexte que notre travail intervient, nous étudions la meilleure façon d’implanter efficacement cette opération sur les processeurs récents.Nous proposons un nouveau format permettant de tenir compte du grand nombre de +- 1 présents dans une matrice.Nous proposons une implantation parallèle basée sur le paradigme du vol de tâche offrant un meilleur passage à l’échelle que le parallélisme par threads.Nous montrons comment exploiter au mieux les instructions SIMD des processeurs dans les différentes opérations.Finalement, nous proposons une méthode efficace permettant d’effectuer cette opération lorsque le corps finis est multiprécision (les éléments sont stockés sur plusieurs mots machine) en ayant recours au système de représentation RNS. / This thesis is composed of two independent parts.The first one is related to homomorphic encryption and the second part deal with sparse linear algebra on finite fields.Homomorphic encryption extends traditional encryption in the sense that it becomes feasible to perform operations on ciphertexts, without the knowledge of the secret decryption key. As such, it enables someone to delegate heavy computations on his sensitive data to an untrusted third party, in a secure way. More precisely, with such a system, one user can encrypt his sensitive data such that the third party can evaluate a function on the encrypted data, without learning any information on the underlying plain data. Getting back the encrypted result, the user can use his secret key to decrypt it and obtain, in clear, the result of the evaluation of the function on his sensitive plain data. For a cloud user, the applications are numerous, and reconcile both a rich user experience and a strong privacy protection.The first fully homomorphic encryption (FHE) scheme, able to handle an arbitrary number of additions and multiplications on ciphertexts, has been proposed by Gentry in 2009.In homomorphic encryption schemes, the executed function is typically represented as an arithmetic circuit. In practice, any circuit can be described as a set of successive operation gates, each one being either a sum or a product performed over some ring.In Gentry’s construction, based on lattices, each ciphertext is associated with some noise, which grows at each operation (addition or multiplication) done throughout the evaluation of the function. When this noise reaches a certain limit, decryption is not possible anymore.To overcome this limitation, closely related to the number of operations that the HE.Eval procedure can handle, Gentry proposed in a technique of noise refreshment called“bootstrapping”.The main idea behind this bootstrapping procedure is to homomorphically run the decryptionprocedure of the scheme on the ciphertext, using an encrypted version of the secret key. In this context, our contribution is twofold. We first prove that the lmax-minimizing bootstrapping problem is APX-complete and NP-complete for lmax ≥ 3. We then propose a new method to determine the minimal number of bootstrappings needed for a given FHE scheme and a given circuit.We use linear programming to find the best outcome for our problem. The main advantage of our method over the previous one is that it is highly flexible and can be adapted for numerous types of homomorphic encryption schemes and circuits.Computing a kernel element of a matrix is a fundamental kernel in many computer algebra and cryptography algorithms. Especially, many applications produces matrices with many matrix elements equals to 0.Those matrices are named sparse matrices. Sparse linear algebra is fundamentally relying on iterative approaches such as Wiedemann or Lanczos. The main idea is to replace the direct manipulation of a sparse matrix with its Krylov subspace. In such approach, the cost is therefore dominated by the computation of the Krylov subspace, which is done by successive product of a matrix by a vector or a dense matrix.Modern processor unit characteristics (SIMD, multicores, caches hierarchy, ...) greatly influence algorithm design.In this context our work deal with the best approach to design efficient implementation of sparse matrix vector product for modern processors.We propose a new sparse matrix format dealing with the many +-1 matrix elements to improve performance.We propose a parallel implementation based on the work stealing paradigm that provide a good scaling on multicores architectures.We study the impact of SIMD instructions on sparse matrix operations.Finally, we provide a modular arithmetic implementation based on residue number system to deal with sparse matrix vector product over multiprecision finite fields.

Notre recherche porte sur la question de l'enseignement de l'algèbre linéaire au niveau universitaire, plus précisément sur les applications linéaires en Classes Préparatoires aux Grandes Écoles. La théorie des situations didactiques avec la sémiotique de Peirce fournissent le cadre principal de nos travaux et nous permettent d'analyser les raisonnements produits par les étudiants en situation d'interrogation orale. Nous proposons dans un premier temps des éléments d'analyse épistémologique concernant le rôle des applications linéaires dans l'émergence de l'algèbre linéaire. Puis nous présentons dans une optique d'analyse didactique les principaux éléments de la sémiotique de Peirce et son algébrisation par le treillis des classes de signes. Nous complétons alors le modèle d'analyse des raisonnements de Bloch et Gibel et proposons un outil d'analyse sémiotique, le diagramme sémantique. Nous utilisons cet outil pour une analyse sémiotique locale a priori d'une situation mathématique. Cette analyse met en évidence le lien entre les premiers signes et premières actions de la situation et la sémiose qui en découle. Nous procédons ensuite à une analyse des raisonnements produits par des étudiants en situation d'interrogation orale, dite « classique ». Cette analyse confirme le lien entre l'absence de niveaux de milieu adidactiques et la difficulté sémantique d'organiser les objets en situation de preuve. Puis, nous expérimentons une situation d'interrogation orale de telle sorte que les niveaux de milieu adidactiques soient riches et stabilisés. L'analyse des raisonnements produits dans cette situation nous permet de montrer que les étudiants sollicitent un point de vue sémantique sur les objets utile lors de leurs validations et contrôles. Ces trois moments de notre travail confirment l'importance du discours et des pratiques heuristiques dans le cadre de l'algèbre linéaire. / Our research is concerned with the teaching of linear algebra at the university level. More precisely, it focuses on the teaching of linear transformations in Classes Préparatoires aux Grandes Écoles. The theory of didactical situations, jointly with Peirce’s semiotics, constitute the main theoretical framework of our works and allow us to analyse student’s reasoning in situations of oral evaluation. Firstly, we put forward some epistemological aspects highlighting the links between linear transformations and the emergence of linear algebra. Then, with a didactical objective, we outline the main features of Perice’s semiotics and its algebraization with the treillis of sign’s categories. Hence, we can enhance the model of analysis for reasoning processes of Bloch and Gibel and build a tool for semiotic analysis called semantic diagram. We illustrate the use of this tool by conducting a local semiotic a priori analysis of a mathematical situation. This analysis highlight the link between the first signs and actions of the situation and the resulting semiosis. Next, we analyse some students’ reasonings produced during oral evaluations said « classical ». This analysis confirms the link between the lack of an adidactical milieu and the semantic difficulty to organize and articulate the objects and signs in a proof situation. Then we experiment a situation of oral evaluation in which the adidactical milieus are rich enough and stabilized. The analysis of the reasoning process conducted in this experimental situation allows us to show that, in this case, the students rely on a semantic point of view on the objects to produce their validations and controls their productions. These three different moments of our research attest the importance of the heuristic practices and discourse in the field of linear algebra.

Cette étude propose une application innovante de deux concepts très étudiés par la communauté mathématique, le fibré des k-repères et la connexion de Cartan. D'une part, l'utilisation d'une connexion de Cartan particulière sur le fibré des 2-repères nous permet de proposer une généralisation de la notion de dérivée de Schwarz en dimension arbitraire, pour les difféomorphismes projectifs et conformes. D'autre part, nous avons pu élaborer une structure de BRS permettant de reproduire infinitésimalement l'action des difféomorphismes sur des champs de jauge à un terme de courbure près. Ainsi, la notion de connexion de Cartan sur le fibré des 2-repères a permis de résoudre un problème ouvert, originellement formulé par A.M. Polyakov en 1990 qui obtient formellement l'action de difféomorphismes (symétrie de l'espace-temps) à partir d'une transformation de jauge (symétrie interne). Les symétries d'espace-temps et les symétries internes peuvent ainsi être exprimées dans un formalisme similaire.

Les travaux présentés dans ce mémoire sont relatifs à l'élaboration formelle de la commande d'un Système à Évènements Discrets (SED) logique à partir des exigences exprimées dans le cahier des charges. La méthode proposée est basée sur la résolution de manière littérale d'un système d'équations représentant ces exigences.<br />Le cadre mathématique, support de ces travaux, est l'algèbre de Boole des fonctions booléennes. Ce cadre mathématique a été retenu pour les raisons suivantes :<br />- Dans le cas particulier des SED logiques non temporisés, toute loi de commande peut être décrite à l'aide de fonctions booléennes.<br />- Les exigences exposées dans un cahier des charges peuvent être formalisées sous forme de relations entre des fonctions booléennes.<br />- Les résultats obtenus dans le cadre de cette thèse nous permettent de déterminer automatiquement quelles sont les fonctions booléennes qui satisfont le système d'équations entre fonctions booléennes représentant ces exigences.<br />La méthode proposée permet au concepteur d'exprimer les exigences dans des formalismes différents. Il a également la possibilité de fixer la forme de la solution qu'il souhaite obtenir ou de ne réaliser la synthèse que sur une partie du modèle.<br />Le chapitre 2 de ce mémoire est consacré à la présentation des résultats mathématiques que nous avons établis pour pouvoir résoudre un système d'équations à n inconnues dans toute structure d'algèbre de Boole. <br />L'approche de synthèse est détaillée au chapitre 3 au travers du traitement de 3 exemples de taille et de complexité croissantes. Nous montrons comment les exigences exprimées dans un cahier des charges peuvent être formalisées sous forme de relations entre des fonctions booléennes. La résolution du système d'équations est réalisée automatiquement grâce à une maquette informatique développée au LURPA.

L'objectif de cette thèse est la modélisation et la commande du trafic. Je considère des modèles microscopiques du trafic pour dériver des relations entre des variables macroscopiques du trafic. Plus précisément, il s'agit de dériver le diagramme fondamental du trafic 2D, qui donne la relation entre la densité et le flot des véhicules. Ce diagramme est utilisé, par exemple, pour déterminer la densité des véhicules qui maximise le flot. Cette information peut aussi être utilisée pour la commande du trafic 2D. Les modèles mathématiques sont basés sur la commande optimale déterministe ou stochastique.<br /><br />La première partie de la thèse est sur le trafic 1D. Il s'agit de généraliser un modèle déterministe de trafic basé sur l'algèbre minplus, qui donne le diagramme fondamental du trafic sur une route. La généralisation permet de réaliser une large classe de diagrammes fondamentaux.<br /><br />Dans la deuxième partie, j'étudie les systèmes dynamiques additivement homogènes de degré 1. En effet, tous les systèmes dynamiques donnés dans ce travail sont additivement homogènes de degré 1. Je m'intéresse dans cette partie à l'existence et à l'unicité de taux de croissance et de valeurs propres additives associées à ces systèmes. Je parts du cas général où zéro, un ou plus de taux de croissance et de valeurs propres peuvent exister, et où des comportement chaotiques peuvent apparaître. Je rappelle les résultats existants dans le cas où on suppose que le systèmes dynamique est, en plus, monotone, et dans le cas ou il est aussi convexe. A la fin de cette partie, je caractérise une classe de systèmes dynamiques additivement homogène de degré 1, non nécessairement monotone, mais dont le comportement asymptotique peut être décrit.<br /><br />La troisième partie consiste à généraliser un modèle de trafic 1D basé sur les réseaux de Petri et l'algèbre minplus, dans le but de modéliser des intersections, et puis dériver le diagramme fondamental du trafic 2D. Une intersection peut être gérée de plusieurs façons, et peut être considérée avec ou sans possibilité de tourner (pour les véhicules). Plusieurs modèles tenant en compte ses hypothèses sont donnés dans cette partie.<br /><br />Le modèle le plus exploré ici est celui de deux routes circulaires avec une intersection gérée par la priorité à droite, et avec possibilité de tourner. Dans ce cas, et sous certaines conditions, le problème de valeur propre additive associé au système dynamique peut être résolu. Le taux de croissance du système dynamique, qui correspond au flot moyen des véhicules est obtenu numériquement. En comparant la valeur propre obtenue théoriquement et le flot moyen donné numériquement, j'ai conclus que les deux quantités, qui sont données en fonction de la densité des véhicules, sont très proches, et sont égales en plusieurs valeurs de la densité. Ainsi, la valeur propre représente une bonne approximation du diagramme fondamental du trafic 2D.<br /><br />D'autres approches de gestion d'intersections consiste à les commander moyennant des feux de signalisation. Une évaluation de la commande de l'intersection peut se baser sur le diagramme fondamental obtenue pour chacune des approches considérées. Une comparaison des différentes approches est donnée. <br /><br />Dans la quatrième partie j'ai développé un code en Scilab qui facilite la construction informatique de grands réseaux de trafic routier. Il s'agit de définir des systèmes élémentaires et des opérateurs sur l'ensemble de ces systèmes, et puis de combiner des systèmes basique pour construire de grands systèmes.<br /><br />La dernière partie est sur la commande du trafic à deux modes: trafic des véhicules particulier, et trafic des véhicules de transport en commun. L'idée est de déterminer un plan de feux de signalisation qui favorise le trafic des véhicules de transport en commun.

Cette thèse étudie l'existence de points de torsion pour les modules de Drinfeld de rang 2 sur des extensions finies de F_q(T), pour q puissance d'un nombre premier. Notre approche suit celle de Mazur et Merel pour la torsion des courbes elliptiques sur les corps de nombres : nous introduisons un quotient de la jacobienne d'une courbe modulaire de Drinfeld, défini à l'aide d'un symbole modulaire de Teitelbaum particulier, et étudions ses propriétés. Sous une hypothèse de dualité entre algèbre de Hecke et formes modulaires pour F_q[T], ainsi qu'une hypothèse technique mineure, on montre le résultat suivant : s'il existe un module de Drinfeld de rang 2 sur une extension de degré au plus q de F_q(T), muni d'un point de torsion d'ordre un idéal premier n de F_q[T], alors le degré de n est au plus max(q,4). Nous utilisons pour cela une description de l'action de l'algèbre de Hecke sur les symboles modulaires de Teitelbaum et sur les formes modulaires pour F_q[T]. Lorsque le degré de n est petit, on obtient des résultats non conditionnels : il n'existe aucun module de Drinfeld de rang 2 sur une extension de degré au plus 2 (resp. au plus 3) de F_q(T) possédant un point de torsion d'ordre un idéal premier de degré 3 (resp. de degré 4 si q est au moins 7). Cela confirme partiellement une conjecture de Poonen et Schweizer de borne uniforme sur la torsion des modules de Drinfeld.

Cette thèse présente les limites du mode s.i.m.d. Dans le cadre de la programmation parallèle d'algorithmes d'algèbre linéaire. Plus précisément, celles de la règle d'or du parallélisme massif: un élément de la matrice par processeur, sont développées. Des expérimentations sont effectuées sur une connection machine 2. Néanmoins, la première partie montre comment la création de procédures de communications écrites a partir d'un nouvel algorithme de construction d'arbres équilibres, et un placement de données judicieux permettent d'atteindre des performances proches de la puissance crête. Mais ce type de travail ne peut pas être effectue sur n'importe quel algorithme, et tout ne s'adapte pas aussi bien. Dans la deuxième partie, nous présentons les avantages de la décomposition en blas pour la construction d'algorithmes massivement parallèles. Elle met, dans le chapitre 4, en évidence la barrière de synchronisation pour la methode du gradient conjugue. Nous proposons dans ce cas particulier comme solution, une ancienne methode qui bien qu'elle soit, en séquentiel, de convergence plus lente, est plus rapide en parallèle. De plus, la structure des matrices est un facteur important. Elle permet d'accélérer les calculs et d'augmenter la dimension des problèmes a résoudre. L'architecture des machines actuelles en limite encore trop l'utilisation. La dernière partie est entièrement consacrée aux permutations, et aux communications qu'elles entrainent. Dans le cadre de l'algorithme de Burg, nous proposons une solution qui calcule a la fois les coefficients de réflexion et ceux d'autoregression sans cout supplémentaire

L'apprentissage des tableurs par des utilisateurs débutants, élevés de la fin de la scolarité obligatoire ou adultes du secteur tertiaire, pose un certain nombre de problèmes lies aux concepts algébriques en jeu, en particulier dans les formules du tableur; notamment la notion de références relatives. L'objet de ce travail est d'étudier la contextualisation des connaissances algébriques de ces utilisateurs dans un tableur. Nous avons particulièrement étudié le cas de multiplan#t#m. Nous avons ainsi pu mettre en évidence certains des obstacles que présente l'apprentissage a l'utilisation de ce type de logiciels. Nous avons également étudié la mise en œuvre de processus itératifs dans un tel environnement et étudie les aspects spécifiques présents dans multiplan au niveau d'itérations déroulées (replication)