Letteratura scientifica selezionata sul tema "Réduction de la complexité de calcul"

La complexité de la nature est multiforme, et il est nécessaire de mettre en oeuvre des approches méthodologiques variées pour tenir compte de cette variété. Les efforts de représentation et d’explication des phénomènes naturels nous conduisent toujours à rechercher, en priorité, des relations de proportionnalité entre les mesures de ce que nous considérons comme des variables pertinentes. La linéarité a été et reste la règle d’or de nos représentations. Mais beaucoup de phénomènes sont rebelles à cette réduction. Les ordinateurs nous aident aujourd’hui à intégrer des myriades de données et à bâtir des modèles non linéaires. Ils ne se substituent pas à la pensée heuristique du savant, mais ils allègent les calculs et permettent des tests d’hypothèses quasiment instantanés. Il a fallu de longs mois de calcul pour que Le Verrier définisse l’orbite d’Uranus. Aujourd’hui, les ordinateurs exécutent ces calculs en quelques microsecondes, et ils ne font pas d’erreurs. Les complexités auxquelles nous devons faire face sont de plusieurs ordres : 1– celles de la physique statistique et de l’astrophysique, 2– celle des constructions moléculaires complexes, qui sont les précurseurs des organismes vivants, 3– celle des morphogenèses et des embryogenèses, 4– celle de la complexité neuronale, de ses processus que nous appelons le mental, 5- celles des phénomènes sociaux chez les animaux inférieurs, 6– celle des animaux sociaux, y compris les humains, particulièrement compliqués par leurs capacité d’anticipation, donc d’interactions réciproques.

RésuméSi k est un corps fini, toute fonction f(x1, … , xm) de {0, 1}m dans k s'écrit de manière unique comme un polynôme, à coefficients dans k, de degré un ou zéro en chacune de ses variables ; on peut donc lui associer une fonction f*(x1, … , xm), sa duale inverse, qui exprime les coefficients de son polynôme canonique. Nous considérons l'improbable hypothèse que la classe P(k), formée des suites de fonctions calculables en un nombre d'opérations (additions et multiplications) de croissance polynomialement bornée, soit close par dualité ; nous montrons qu'elle équivaut à une hypothèse bien connue en Théorie de la Complexité sous le nom de P = #pP, où p est la caractéristique de k.Dans une première section, nous exposons ce résultat lorsque k = ℤ/2ℤ, c'est-à-dire dans le cadre des calculs booléens classiques ; sa démonstration évite l'emploi d'un polynôme universel comme le hamiltonien : ses ingrédients sont d'une part la réduction parcimonieuse des circuits aux termes, et d'autre part la constatation que les expressions arithmétiques ont une duale très facile à calculer.Dans la deuxième section, nous traitons le cas général, en introduisant une classe SP(k) obtenue par sommation à partir de la classe P(k) ; nous vérifierons dans la quatrième section l'équivalence des hypothèses SP(k) = P(k) et #pP = P. Nous y définissons également une notion de transformation, dont la dualité est un cas particulier. Les transformations forment un groupe isomorphe à GL2(k), avec un sous-groupe B(k) de transformations que nous qualifions de bénignes, car elles n'ont que peu d'effet sur la complexité des fonctions ; nous montrons que toutes les transformations non-bénignes ont à peu près la même influence sur la complexité des fonctions, sauf si k = F3 ou k = F5 ; dans ces deux cas exceptionnels, la transformation de Fourier joue un rôle particulier.Dans la troisième section, nous considérons des fonctions de km dans k ; nous n'y trouvons pas des classes de complexité vraiment nouvelles, mais seulement un groupe de transformations plus riche.La quatrième section introduit l'égalité #P = P dans le paysage ; quant à la cinquième et dernière, elle examine le lien entre nos résultats et ceux de Guillaume Malod concernant la clôture par fonction-coefficient de diverses classes de complexité pour le calcul des polynômes à la manière de Valiant.Nous nous sommes efforcés de rédiger cet article de manière à ce qu'il puisse être lu par des personnes non spécialisées en algorithmie.

À partir de phénomènes sémantiques qui semblent complexes (au sens courant), et de ce que l’on appelle complexité là où, en linguistique, cette notion est mieux établie, une définition générale de la complexité sémantique est proposée. La complexité de certains faits est susceptible d’expliquer les différences entre les idiolectes, laissant prévoir un rapport avec la notion de difficulté. Un phénomène correspondant à un certain type de complexité sémantique – les comparaisons d’intensité – est ensuite analysé. Les paramètres qui allongent le calcul du sens de ces comparaisons et qui permettent de les hiérarchiser en fonction de leur complexité sont mis au jour.

Ce travail constate qu’il peut très souvent persister des incohérences entre la complexité des modèles hydrologiques (qui progressent en fonction de la connaissance acquise du fonctionnement du milieu naturel) et les données disponibles pour la documentation du modèle et son application. Ainsi, les modèles hydrologiques « intégrés » traitent de la dynamique hydrique complète d’un bassin versant mais ne sont conditionnables que sur des données qui ne distinguent que très partiellement toute la dimension de l’écoulement. Il est proposé de réduire ce type de modèle en agrégeant sa physique pour en réduire la dimension euclidienne. Le modèle devient alors un outil manipulable et en meilleure adéquation avec les données d’observation. Paradoxalement, la complexité de la physique d’un modèle peut aussi en faciliter la réduction. Traiter par exemple des écoulements dans un aquifère carbonaté par une approche double continuum augmente le nombre de paramètres locaux comparé à une approche simple continuum. Cependant, l’hétérogénéité structurale du réservoir étant inscrite dans les équations du modèle, la paramétrisation à l’échelle de l’aquifère se simplifie fortement. La réduction est ici le fait d’une diminution des efforts de conditionnement du modèle sur les données ; les exercices d’inversion et de prédiction deviennent abordables. Finalement, il semble aujourd’hui nécessaire d’envisager et jauger les progrès réalisés par les modèles, d’une part sur leur complexité accrue, d’autre part sur la capacité de réduire cette complexité en fonction des applications ciblées et des informations disponibles.

Cet article essaie de démontrer qu’il est possible d’avoir une mesure unifiée et standardisée de la plupart des types de complexité linguistique quelle que soit la langue à condition de recourir à un système de description et d’interprétation du fonctionnement des langues – en l’occurrence l’analyse matricielle définitoire (AMD) – qui s’appuie sur cette propriété remarquable des langues naturelles de pouvoir se décrire avec leurs termes les plus courants à travers la construction de classes d’équivalence au sein desquelles les faits grammaticaux – principale source de complexité – sont « décomplexifiés » et mesurés en termes d’opérations régulières de réduction.

Il est nécessaire de fournir des outils efficaces pour l'estimation et la prévision de l'énergie électrique produite par les modules photovoltaïques. Le modèle à une diode est le plus utilisé actuellement pour décrire le comportement électrique d'un module photovoltaïque. Dans ce travail, nous proposons une méthode de réduction pour le calcul des paramètres du modèle en utilisant les données fournies par le fabricant. La méthode permet de résoudre un système de deux équations au lieu du système plus important à cinq équations et cinq inconnus. Pour un module qui a déjà fonctionné durant quelques années, les paramètres calculés du modèle ne sont pas fiables. Il est nécessaire de les recalculer selon l'état actuel du module. Nous avons développé une méthode de réduction permettant de le faire. La méthode a donné de bons résultats avec un temps de calcul relativement correct.

The alpha-proteobacteria displayed diverse and often unconventional life-styles. In particular, they keep close relationships with the eucaryotic cell. Their genomic organization is often atypical. Indeed, complex genomes, with two or more chromosomes that could be linear and sometimes associated with plasmids larger than one megabase, have been described. Moreover, polymorphism in genome size and topology as well as in replicon number was observed among very related bacteria, even in a same species. Alpha-proteobacteria provide a good model to study the reductive evolution, the role and origin of multiple chromosomes, and the genomic fluidity. The amount of new data harvested in the last decade should lead us to better understand emergence of bacterial life-styles and to build the conceptual basis to improve the definition of the bacterial species.Key words: alpha-proteobacteria, genome, dynamics, diversity.

Depuis 2015, la métropole de Montpellier finance des actions de recherche et développement au travers de contrats de délégation de service public de l’assainissement. Un des projets a porté sur l’évaluation des actions de réduction à la source des micropolluants d’un établissement de soin, la Polyclinique Saint-Roch, engagé depuis 2013 dans une politique de développement durable, de réduction de ses impacts sur l’environnement, qui a fait l’objet d’un transfert dans un nouvel établissement en 2016. Veolia a lancé, dans ce contexte, une étude multipartenaire (Polyclinique Saint-Roch, UMR HydroSciences Montpellier, métropole de Montpellier et Veolia Eau), afin de caractériser les rejets d’assainissement de l’ancien et du nouvel établissement, ce dernier ayant mis en oeuvre de nouvelles pratiques pour diminuer ses rejets. Cette étude se décline en plusieurs actions : sélectionner au préalable des molécules susceptibles d’être représentatives de l’activité de soins, les quantifier dans les eaux usées, prédire les concentrations de molécules médicamenteuses représentatives (calcul d’un PEC : concentration prédite dans l’environnement) et les comparer aux valeurs mesurées. Le changement des pratiques a une répercussion significative sur la réduction des flux de micropolluants rejetés au réseau par la Polyclinique Saint-Roch, qui est suffisante pour ne pas engager de prétraitements sur leur site. La démarche est transposable aux autres établissements de soins de la métropole. La méthode de calcul des PEC dans les eaux usées est acceptable et intéressante pour un diagnostic préalable et/ou une approche globale des émissions.

Le problème abordé dans cette thèse est celui du dénombrement des solutions du problème de la satisfiabilité d'une formule booléenne sous forme normale conjonctive (problème #SAT). Ce problème est #P-complet et les résultats actuels montrent que la résolution de #SAT, même approchée, est, dans le pire des cas, exponentielle en temps. Notre approche utilise une algorithmique issue de l'analyse combinatoire des données et s'appuie sur une représentation ensembliste, géométrique et logique des clauses définies par une bijection entre clauses et sous-ensemble de l'ensemble des interprétations. Une telle représentation permet une vision synthétique du problème #SAT et la prise en compte de caractéristiques statistiques globales de l'instance. En appliquant le principe général "diviser pour résoudre", la méthode de résolution approchée de #SAT que nous proposons permet de réduire de facon considérable la complexité algorithmique du problème. Elle est basée sur la segmentation d'une sériation établie sur la table d'incidence associée à la formule. Nous montrons, dans le cas difficile des instances SAT aléatoires, l'intérêt de la sériation et de sa meilleure coupure en deux parties connexes et de tailles comparables. De plus, nous définissons la notion d'indépendance en probabilité entre clauses et entre ensembles de clauses. La méthode proposée est validée à la fois théoriquement et par une vaste expérimentation. Par ailleurs, nous nous intéressons à la distribution de probabilité du nombre de solutions d'une instance kSAT aléatoire. L'espérance et la variance du nombre de solutions sont connues, nous montrons en utilisant des tests statistiques que la distribution suit une loi log-normale.

Nous étudions les problèmes combinatoires NP-complets autour de la Satisfaisabilité (SAT) : 3-Colorabilité (3COL), Hamiltonicité (HAM), etc. , et les réductions fines entre ces problèmes et leurs versions planaires. Nous cherchons à préserver la structure des solutions (parcimonie), la complexité des problèmes (linéarité), et la géométrie des instances (planarité). Nous exhibons une réduction quadratique et parcimonieuse de 3COL à PLAN-3COL et une réduction linéaire, planaire, et parcimonieuse de SAT à 3COL, unifiant et rafinant les preuves de NP-complétude et de \#P-complétude pour 3COL, PLAN-3COL, \#3COL et \#PLAN-3COL, et montrant la DP-complétude de UNIQUE-3COL et UNIQUE-PLAN-3COL. Nous établissons l'équivalence linéaire et parcimonieuse de PLAN-SAT et de PLAN-HAM, un lien peu probable entre SAT et HAM. Nous exhibons enfin une formule Existentielle Monadique du Second Ordre prouvée minimale et unique, définissant un problème NP-complet sur structures bijectives.

Cette thèse traite de certains aspects particuliers de la résolution des systèmes algébriques. Dans un premier temps, nous présentons une façon de minimiser le nombres de variables additives apparaissant dans un système algébrique. Nous utilisons pour cela deux invariants de variété introduits par Hironaka : le faîte et la directrice. Dans un second temps, nous proposons une arithmétique rapide, dite détendue, pour les entiers p-adiques. Cette arithmétique nous permet ensuite de résoudre efficacement un système algébrique à coefficients rationnels localement, c'est-à-dire sur les entiers p-adiques. En quatrième partie, nous nous intéressons à la factorisation d'un polynôme à deux variables qui est une brique élémentaire pour la décomposition en composantes irréductibles des hypersurfaces. Nous proposons un algorithme réduisant la factorisation du polynôme donné en entrée à celle d'un polynôme dont la taille dense est essentiellement équivalente à la taille convexe-dense de celui donné en entrée. Dans la dernière partie, nous considérons la résolution en moyenne des systèmes algébriques réels. Nous proposons un algorithme probabiliste calculant un zéro approché complexe du système algébrique réel donné en entrée
This PhD thesis deals with some particular aspects of the algebraic systems resolution. Firstly, we introduce a way of minimizing the number of additive variables appearing in an algebraic system. For this, we make use of two invariants of variety introduced by Hironaka: the ridge and the directrix. Then, we propose fast arithmetic routines, the so-called relaxed routines, for p-adic integers. These routines allow us, then, to solve efficiently an algebraic system with rational coefficients locally, i. E. Over the p-adic integers. In a fourth part, we are interested in the factorization of a bivariate polynomial, which is at the root of the decomposition of hypersurfaces into irreducible components. We propose an algorithm reducing the factorization of the input polynomial to that of a polynomial whose dense size is essentially equivalent to the convex-dense size of the input polynomial. In the last part, we consider real algebraic systems solving in average. We design a probabilistic algorithm computing an approximate complex zero of the real algebraic system given as input

Cette thèse traite de certains aspects particuliers de la résolution des systèmes algébriques. Dans un premier temps, nous présentons une façon de minimiser le nombres de variables additives apparaissant dans un système algébrique. Nous utilisons pour cela deux invariants de variété introduits par Hironaka : le faîte et la directrice. Dans un second temps, nous proposons une arithmétique rapide, dite détendue, pour les entiers p-adiques. Cette arithmétique nous permet ensuite de résoudre efficacement un système algébrique à coefficients rationnels localement, c'est-à-dire sur les entiers p-adiques. En quatrième partie, nous nous intéressons à la factorisation d'un polynôme à deux variables qui est une brique élémentaire pour la décomposition en composantes irréductibles des hypersurfaces. Nous proposons un algorithme réduisant la factorisation du polynôme donné en entrée à celle d'un polynôme dont la taille dense est essentiellement équivalente à la taille convexe-dense de celui donné en entrée. Dans la dernière partie, nous considérons la résolution en moyenne des systèmes algébriques réels. Nous proposons un algorithme probabiliste calculant un zéro approché complexe du système algébrique réel donné en entrée.

Les réseaux euclidiens sont un outil particulièrement puissant dans
plusieurs domaines de l'algorithmique, en cryptographie et en théorie
algorithmique des nombres par exemple. L'objet du présent mémoire est dual : nous améliorons les algorithmes de réduction des réseaux,
et nous développons une nouvelle application dans le domaine
de l'arithmétique des ordinateurs. En ce qui concerne l'aspect algorithmique, nous nous intéressons aux cas des petites dimensions (en dimension un, où il s'agit du calcul de pgcd, et aussi en dimensions 2 à 4), ainsi qu'à la description d'une nouvelle variante de l'algorithme LLL, en dimension quelconque. Du point de vue de l'application, nous utilisons la méthode
de Coppersmith permettant de trouver les petites racines de polynômes modulaires multivariés, pour calculer les pires cas pour l'arrondi des fonctions mathématiques, quand la fonction, le mode d'arrondi, et la précision sont donnés. Nous adaptons aussi notre technique aux mauvais cas simultanés pour deux fonctions. Ces deux méthodes sont des pré-calculs coûteux, qui une fois
effectués permettent d'accélérer les implantations des fonctions mathématiques élémentaires en précision fixée, par exemple en double précision.

La plupart des algorithmes décrits dans ce mémoire ont été validés
expérimentalement par des implantations, qui sont
disponibles à l'url http://www.loria.fr/~stehle.

Les dégradations dues à la non-linéarité de Kerr dans les fibres optiques limitent les débits d’information des systèmes de communications. Les effets linéaires, tels que la dispersion chromatique et la dispersion modale de polarisation, peuvent être compensés par égalisation linéaire, de mise en oeuvre relativement simple, au niveau du récepteur. A l’inverse, la complexité de calcul des techniques classiques de réduction de la non-linéarité, telles que la rétro-propagation numérique, peut être considérable. Les réseaux neuronaux ont récemment attiré l’attention, dans ce contexte, pour la mise en oeuvre d’égaliseurs non-linéaires à faible complexité. Cette thèse porte sur l’étude des réseaux neuronaux récurrents pour compenser efficacement les dégradations des canaux dans les transmissions à longue distance multiplexés en polarisation. Nous présentons une architecture hybride de réseaux neuronaux récurrents convolutifs (CRNN), comprenant un encodeur basé sur un réseau neuronal convolutif (CNN) suivie d’une couche récurrente travaillant en tandem. L’encodeur basé sur CNN représente efficacement la mémoire de canal à court terme résultant de la dispersion chromatique, tout en faisant passer le signal vers un espace latent avec moins de caractéristiques pertinentes. La couche récurrente suivante est implémentée sous la forme d’un RNN unidirectionnel de type vanille, chargé de capturer les interactions à longue portée négligées par l’encodeur CNN. Nous démontrons que le CRNN proposé atteint la performance des égaliseurs actuels dans la communication par fibre optique, avec une complexité de calcul significativement plus faible selon le modèle du système. Enfin, le compromis performance-complexité est établi pour un certain nombre de modèles, y compris les réseaux neuronaux multicouches entièrement connectés, les CNN, les réseaux neuronaux récurrents bidirectionnels, les réseaux long short-term memory bidirectionnels (bi-LSTM), les réseaux gated recurrent units bidirectionnels, les modèles bi-LSTM convolutifs et le modèle hybride proposé
The impairments arising from the Kerr nonlinearity in optical fibers limit the achievable information rates in fiber-optic communication. Unlike linear effects, such as chromatic dispersion and polarization-mode dispersion, which can be compensated via relatively simple linear equalization at the receiver, the computational complexity of the conventional nonlinearity mitigation techniques, such as the digital backpropagation, can be substantial. Neural networks have recently attracted attention, in this context, for low-complexity nonlinearity mitigation in fiber-optic communications. This Ph.D. dissertation deals with investigating the recurrent neural networks to efficiently compensate for the nonlinear channel impairments in dual-polarization long-haul fiber-optic transmission. We present a hybrid convolutional recurrent neural network (CRNN) architecture, comprising a convolutional neural network (CNN) -based encoder followed by a recurrent layer working in tandem. The CNN-based encoder represents the shortterm channel memory arising from the chromatic dispersion efficiently, while transitioning the signal to a latent space with fewer relevant features. The subsequent recurrent layer is implemented in the form of a unidirectional vanilla RNN, responsible for capturing the long-range interactions neglected by the CNN encoder. We demonstrate that the proposed CRNN achieves the performance of the state-of-theart equalizers in optical fiber communication, with significantly lower computational complexity depending on the system model. Finally, the performance complexity trade-off is established for a number of models, including multi-layer fully-connected neural networks, CNNs, bidirectional recurrent neural networks, bidirectional long short-term memory (bi-LSTM), bidirectional gated recurrent units, convolutional bi-LSTM models, and the suggested hybrid model

Cette thèse est le fruit d’une collaboration entre les laboratoires DAVID et Nokia Bell Labs France.L’idée originale est de trouver des solutions algorithmiques pour gérer des flux periodiques de manière déterministe dans les réseaux afin de contrôler et de minimiser le temps de transmission, appelé latence. L’un des objectifs de la 5G (le C-RAN, pour Cloud Radio Access Network) est de centraliser les unités de calculs des antennes radio des réseaux de télécommunications (appelé Radio Access Network) dans un même centre de calcul (le Cloud). Le réseau entre le centre de calcul et les antennes doit être capable de satisfaire les contraintes de latence imposées par les protocoles.Nous définissions le problème de trouver un ordonnancement periodique pour les messages de façon à ce qu'ils ne se disputent jamais la même ressource, et prouvons que les différentes variantes du problème étudiés sont NP-complets. Nous étudions dans un premier temps le problème pour une topologie particulière dans laquelle tous les flux partagent un même lien. Nous proposons dans un premier temps des algorithmes polynomiaux, de plus en plus évolués, ainsi que des algorithmes FPT permettant de trouver une solution quand le nombre de route est raisonnable, ce qui est le cas des réseaux C-RAN.Les algorithmes développés dans cette première partie n’étant pas applicables directement aux topologies plus générales, nous proposons ensuite une forme compacte au problème qui nous permet de définir une notion de voisinage efficace pour des heuristiques de recherches locales (descente, recherche tabou, recuit simulé). Nous utilisons cette forme compacte pour définir un algorithme Branch and Bound efficace quand le nombre de routes est modéré.Nous proposons aussi une évaluation de performance des solutions proposés par rapport aux solutions courantes de gestion des flux et montrons que notre modèle est réalisable en pratique grâce aux nouveaux équipements en cours de développement
This thesis is the result of a collaboration between DAVID Laboratory and Nokia Bell Labs France.The original idea is to find algorithmic solutions to deterministically manage periodic flows in networks in order to control and minimize the transmission time, called latency. One of the objectives of 5G (C-RAN, for Cloud Radio Access Network) is to centralize the calculation units of the radio antennas of telecommunications networks (called Radio Access Network) in the same computer center (the Cloud). The network between the computing center and the antennas must be able to satisfy the latency constraints imposed by the protocols.We define the problem of finding a periodic scheduling for messages so that they never compete for the same resource, and prove that the different variants of the problem studied are NP-complete. We first study the problem for a particular topology in which all the streams share the same link. We first propose polynomial algorithms of increased sophistication, and FPT algorithms that allow us to find a solution when the number of routes is reasonable, which is the case for C-RAN networks.Since the algorithms developed in this first part are not directly adaptable to more general topologies, we then propose a canonical form to the problem which allows us to define an efficient neighborhood notion for local search heuristics (hill climbing, tabu search, simulated annealing). We use this canonical form to define an efficient Branch and Bound algorithm when the number of routes is moderate.We also propose a performance evaluation of the proposed solutions compared to current flow management solutions, and show that our model is feasible in practice thanks to new equipment under development

Les méthodes de réduction de modèles offrent un cadre général permettant une réduction de coûts de calculs substantielle pour les simulations numériques. Dans cette thèse, nous proposons d’étendre le domaine d’application de ces méthodes. Le point commun des sujets discutés est la tentative de dépasser le cadre standard «bases réduites» linéaires, qui ne traite que les cas où les variétés solutions ont une petite épaisseur de Kolmogorov. Nous verrons comment tronquer, translater, tourner, étirer, comprimer etc. puis recombiner les solutions, peut parfois permettre de contourner le problème qui se pose lorsque cette épaisseur de Kolmogorov n’est pas petite. Nous évoquerons aussi le besoin de méthodes de stabilisation sur-mesure pour le cadre réduit
Model reduction methods provide a general framework for substantially reducing computational costs of numerical simulations. In this thesis, we propose to extend the scope of these methods. The common point of the topics discussed here is the attempt to go beyond the standard linear "reduced basis" framework, which only deals with cases where the solution manifold have a small Kolmogorov width. We shall see how truncate, translate, rotate, stretch, compress etc. and then recombine the solutions, can sometimes help to overcome the problem when this Kolmogorov width is not small. We will also discuss the need for tailor-made stabilisation methods for the reduced frame

Contrôler la consommation en ressources des programmes informatiques est d'importance capitale, non seulement pour des raisons de performance, mais aussi pour des questions de sécurité quand par exemple certains systèmes mobiles ou embarqués disposent de quantités limitées de ressources. Dans cette thèse, nous développons des critères statiques pour contrôler la consommation en ressources de programmes concurrents d'ordre supérieur. Nous prenons comme point de départ le cadre des Logiques Light qui a été étudié afin de contrôler la complexité de programmes fonctionnels d'ordre supérieur au moyen de la correspondance preuves-programmes. La contribution de cette thèse est d'étendre ce cadre aux programmes concurrents d'ordre supérieur. Plus généralement, cette thèse s'inscrit dans le domaine de la complexité implicite qui cherche à caractériser des classes de complexité par des principes logiques ou des restrictions de langage. Les critères que nous proposons sont purement syntaxiques et sont développés graduellement afin de contrôler le temps de calcul des programmes de plus en plus finement: dans un premier temps nous montrons comment garantir la terminaison des programmes (temps fini), puis nous montrons comment garantir la terminaison des programmes en temps élémentaire, et enfin nous montrons comment garantir la terminaison des programmes en temps polynomial. Nous introduisons également des systèmes de types tels que les programmes bien typés terminent en temps borné et retournent des valeurs. Enfin, nous montrons que ces systèmes de types capturent des programmes concurrents intéressants qui itèrent des fonctions produisant des effets de bord sur des structures de données inductives. Dans la dernière partie, nous étudions une méthode sémantique alternative afin de contrôler la consommation en ressources de programmes impératifs d'ordre supérieur. Cette méthode est basée sur la réalisabilité quantitative de Dal Lago et Hofmann et permet d'obtenir plusieurs bornes de complexité de manière uniforme. Cette dernière partie est un travail en collaboration avec Aloïs Brunel
Controlling the resource consumption of programs is crucial: besides performance reasons, it has many applications in the field of computer security where e. G. Mobile or embedded Systems dispose of limited amounts of resources. In this thesis, we develop static criteria to control the resource consumption of higher-order concurrent programs. Our starting point is the framework of Light Logics which has been extensively studied to control the complexity of higher-order functional programs through the proofs-as-programs correspondent. The contribution of this thesis is to extend this framework to higher-order concurrent programs. More generally, this thesis fits in the research field of Implicit Computational Complexity which aims at characterizing complexity classes by logical principles or language restrictions. The criteria that we propose are purely syntactic and are developed gradually to control the computational time of programs in a finer and finer way: first, we show how to guarantee the termination of programs (finite time); then, we show how to guarantee the termination of programs in elementary time and last, we show how to guarantee the termination of programs in polynomial time. We also introduce type Systems so that well-typed programs are guaranteed to terminate in bounded time and to return values. Finally, we show that the type Systems capture some interesting concurrent programs that iterate functions producing side effects over inductive data structures. In the last part, we study an alternative semantic method to control the resource consumption of higher-order imperative programs. The method is based on Dal Lago and Hofmann's quantitative realizability framework and allows to obtain various complexity bounds in a uniform way. This last par is joint work with Aloïs Brunel

On présente trois algorithmes dans cette thèse. Le premier algorithme résout des 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 des représentations rationnelles paramétriques uniformes sur chaque ensemble constructible. Le deuxième algorithme factorise absolument des 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 des 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.

Ce chapitre aborde la question de la réduction des temps de calcul en hydrodynamique, en s’intéressant en particulier, d’une part à la Proper Orthogonal Decomposition (POD) et à la Lattice Boltzman Method (LBM). Les principes de ces méthodes sont exposés dans le contexte des écoulements hydrodynamiques et leurs interactions avec le mouvement de structures.

Ce chapitre expose des techniques avancées pour les calculs vibro-acoustiques, visant à prendre en compte des chargements complexes ainsi que les incertitudes sur les données de conception et les variables d’environnement, et met l’accent sur les méthodes de réduction de modèles paramétriques, lesquelles permettent de diminuer les temps de calcul, et de mener des études de sensibilité, de propagation d’incertitudes et d’optimisation.

En partant de données chiffrées sur les langues, la densité linguistique des différents états, le nombre de locuteurs L1 de ces langues et leurs fonctions (officielles, véhiculaires…) on obtient une photographie de la situation linguistique du monde, qui est traversée par l’histoire ( pratiques sociales, politiques linguistiques, exportation ou importation sur le marché aux langues, etc.). Peut-on en tirer des conclusions sur l’évolution de cette situation ? Quelques intuitions de Charles Ferguson et surtout l’analyse de la situation de l’anglais dans l’Union Européenne post-Brexit permettent d’avancer quelques hypothèses sur les facteurs (réduction des diglossies, évolution des bilinguismes, nationalisme et mondialisation, véhicularisation, etc.) qui peuvent jouer un rôle dans cette complexité.

Cette étude porte sur une des innovations contemporaines liées à l’économie de la publication scientifique : les accords dits transformants, un objet relativement circonscrit au sein des relations entre consortiums de bibliothèques et éditeurs scientifiques, et temporellement situé entre 2015 et 2020. Ce type d’accords a pour objectif affiché d’organiser la transition du modèle traditionnel de l’abonnement à des revues (souvent proposées par regroupements thématiques ou collections) vers celui de l’accès ouvert en opérant une réaffectation des budgets qui y sont consacrés. Notre travail d’analyse sociologique constitue une première étude systématique de cet objet, fondée sur la recension de 197 accords. Le corpus ainsi constitué inclut des accords caractérisés par la coprésence d’une composante d’abonnement et d’une composante de publication en accès ouvert, même minimale (« jetons » de publication offerts, réduction sur les APC...). En conséquence, ont été exclus de l’analyse les accords portant uniquement sur du financement centralisé de publication en accès ouvert, que ce soit avec des éditeurs ne proposant que des revues avec paiement par l’auteur (PLOS, Frontiers, MDPI...) ou des éditeurs dont une partie du catalogue est constitué de revues en accès ouvert. L’accord le plus ancien de notre corpus a été signé en 2010, les plus récents en 2020 – les accords ne commençant qu’en 2021, même annoncés au cours de l’étude, n’ont pas été retenus. Plusieurs résultats se dégagent de notre analyse. Tout d’abord, on note une grande diversité des acteurs impliqués avec 22 pays et 39 éditeurs, même si certains consortiums (Pays-Bas, Suède, Autriche, Allemagne) et éditeurs (CUP, Elsevier, RSC, Springer) en ont signé beaucoup plus que d’autres. Ensuite, la durée des accords, comprise entre une et six années, révèle une distribution très inégalitaire, avec plus de la moitié des accords (103) signés pour 3 ans, ainsi qu’une faible proportion pour 4 ans ou plus (22 accords). Enfin, en dépit d’appels répétés à la transparence, moins de la moitié des accords (96) ont un texte accessible au moment de cette étude, sans qu’on puisse observer une tendance récente à une plus grande disponibilité. L’analyse montre également des degrés d’ouverture très variables, allant d’une simple information sur le répertoire ESAC en passant par la mise à disposition d’un format annotable jusqu’à l’attribution d’un DOI et d’une licence de réutilisation (CC-BY), en incluant le détail des sommes monétaires. Parmi les 96 accords disponibles, dont 47 signés en 2020, 62 ont fait l’objet d’une analyse en profondeur. C’est à notre connaissance la première analyse à cette échelle, sur un type de matériel non seulement inédit, mais qui était auparavant soumis à des clauses de confidentialité. Fondée sur une lecture minutieuse, l’étude décrit de manière fine leurs propriétés, depuis la matérialité du document jusqu’aux formules financières, en passant par leur morphologie et l’ensemble des droits et devoirs des parties. Les contenus des accords sont donc analysés comme une collection dont nous cherchons à déterminer les points communs et les variations, à travers des codages explicites sur certaines de leurs caractéristiques. L’étude pointe également des incertitudes, et notamment leur caractère « transitionnel », qui demeure fortement discuté. D’un point de vue morphologique, les accords montrent une grande diversité en matière de taille (de 7 à 488 pages) et de structure. Néanmoins, par définition, ils articulent tous deux objets essentiels : d’une part, les conditions de réalisation d’une lecture d’articles de revues, sous forme d’abonnement, mêlant des préoccupations d’accès et de sécurité ; d’autre part, les modalités de publication en accès ouvert, articulant la gestion d’un nouveau type de workflow à toute une série d’options possibles. Parmi ces options, mentionnons notamment le périmètre des revues considérées (hybrides et/ou accès ouvert), les licences disponibles, le degré d’obligation de cette publication, les auteurs éligibles ou le volume d’articles publiables. L’un des résultats les plus importants de cette analyse approfondie est la mise au jour d’un découplage presque complet, au sein même des accords, entre l’objet abonnement et l’objet publication. Bien entendu, l’abonnement est systématiquement configuré dans un monde fermé, soumis à paiement qui déclenche des séries d’identification des circulations légitimes tant du contenu informationnel que des usagers. Il insiste notamment sur les interdictions de réutilisation ou même de copie des articles scientifiques. À l’opposé, la publication en accès ouvert est attachée à un monde régi par l’accès gratuit au contenu, ce qui induit des préoccupations de gestion du workflow et des modalités d’accessibilité. De plus, les différents éléments constitutifs de ces objets contractuels ne sont pas couplés : d’un côté, les lecteurs sont constitués de l’ensemble des membres des institutions abonnées, de l’autre, seuls les auteurs correspondants (« corresponding authors ») sont concernés ; les listes de revues accessibles à la lecture et celles réservées à la publication en accès ouvert sont le plus souvent distinctes ; les workflows ont des objectifs et des organisations matérielles totalement différentes, etc. L’articulation entre les deux objets contractuels relève uniquement d’une formule de distribution financière qui, outre des combinaisons particulières entre l’un et l’autre, permet d’attribuer des étiquettes distinctes aux accords (offset agreement, publish & read, read & publish, read & free articles, read & discount). Au-delà de cette distribution, l’étude des arrangements financiers montre une gamme de dispositions allant d’une prévisibilité budgétaire totale, donc identique aux accords d’abonnement antérieurs, à une incertitude sur le volume de publication ou sur le montant définitif des sommes échangées. Les modalités concrètes de calcul des montants associés à la publication en accès ouvert sont relativement variées. S’il existe effectivement des formules récurrentes (volume d’articles multiplié par un prix individuel, reprise de la moyenne des sommes totales d’APC des années précédentes...), le calcul des sommes en jeu est toujours le résultat d’une négociation singulière entre un consortium et un éditeur scientifique, et aboutit parfois à des formules originales et complexes. À ce titre, l’espace des possibles en matière de formules financières n’est jamais totalement clos. Par ailleurs, la volonté des consortiums d’opérer une « transformation » de leurs accords vers la publication à coût constant renvoie à des définitions diversifiées du « coût » (inclusion ou non des dépenses d’APC préexistantes) et de la constance (admission ou pas d’une « inflation » à 2 ou 3%). De plus, nous n’avons observé aucune disposition contractuelle permettant d’anticiper les sommes en jeu au-delà de l’horizon temporel de l’accord courant. La grande diversité des accords provient d’une part des conditions initiales des relations entre consortiums et éditeurs scientifiques – les sommes dépensées en abonnement étant le point de départ des nouveaux accords –, d’autre part des objectifs de chaque partie. Même si cette étude excluait volontairement les négociations, les accords portent des traces de ces objectifs. Ainsi, de nombreux accords sont de nature explicitement expérimentale, quand certains visent un contrôle budgétaire strict, ou d’autres ambitionnent, dans la période plus récente, la publication du plus grand nombre possible d’articles en accès ouvert. C’est dans ce dernier cas qu’on touche à l’ambiguïté des attentes générales sur les accords transformants. En effet, pour les consortiums, la dimension « transformante » consiste essentiellement à transférer les sommes traditionnellement allouées à l’abonnement vers la publication en accès ouvert. Mais l’objectif n’est jamais de transformer le modèle économique des revues, c'est-à-dire de faire basculer des revues sous abonnement ou hybrides en revues entièrement en accès ouvert. D’ailleurs, aucune clause ne vise une telle fin – à l’exception du modèle d’accord proposé par l’éditeur ACM. Du côté des éditeurs, et notamment de Springer, le caractère cumulatif des accords nationaux passés vise à projeter un monde de la publication où l’accès ouvert devient de fait quantitativement très dominant, sans pour autant modifier de manière pérenne le modèle économique de leurs revues. Notre étude montre que les accords transformants actuels ne permettent pas d’assurer de manière durable une transition de l’économie de la publication vers l’accès ouvert, dans la mesure où ils n’offrent pas de garantie sur le contrôle des dépenses ni sur la pérennité de l’ouverture des contenus. L’avenir des relations entre consortium et éditeur demeure largement indéterminé.Cette étude porte sur une des innovations contemporaines liées à l’économie de la publication scientifique : les accords dits transformants, un objet relativement circonscrit au sein des relations entre consortiums de bibliothèques et éditeurs scientifiques, et temporellement situé entre 2015 et 2020. Ce type d’accords a pour objectif affiché d’organiser la transition du modèle traditionnel de l’abonnement à des revues (souvent proposées par regroupements thématiques ou collections) vers celui de l’accès ouvert en opérant une réaffectation des budgets qui y sont consacrés. Notre travail d’analyse sociologique constitue une première étude systématique de cet objet, fondée sur la recension de 197 accords. Le corpus ainsi constitué inclut des accords caractérisés par la coprésence d’une composante d’abonnement et d’une composante de publication en accès ouvert, même minimale (« jetons » de publication offerts, réduction sur les APC...). En conséquence, ont été exclus de l’analyse les accords portant uniquement sur du financement centralisé de publication en accès ouvert, que ce soit avec des éditeurs ne proposant que des revues avec paiement par l’auteur (PLOS, Frontiers, MDPI...) ou des éditeurs dont une partie du catalogue est constitué de revues en accès ouvert. L’accord le plus ancien de notre corpus a été signé en 2010, les plus récents en 2020 – les accords ne commençant qu’en 2021, même annoncés au cours de l’étude, n’ont pas été retenus. Plusieurs résultats se dégagent de notre analyse. Tout d’abord, on note une grande diversité des acteurs impliqués avec 22 pays et 39 éditeurs, même si certains consortiums (Pays-Bas, Suède, Autriche, Allemagne) et éditeurs (CUP, Elsevier, RSC, Springer) en ont signé beaucoup plus que d’autres. Ensuite, la durée des accords, comprise entre une et six années, révèle une distribution très inégalitaire, avec plus de la moitié des accords (103) signés pour 3 ans, ainsi qu’une faible proportion pour 4 ans ou plus (22 accords). Enfin, en dépit d’appels répétés à la transparence, moins de la moitié des accords (96) ont un texte accessible au moment de cette étude, sans qu’on puisse observer une tendance récente à une plus grande disponibilité. L’analyse montre également des degrés d’ouverture très variables, allant d’une simple information sur le répertoire ESAC en passant par la mise à disposition d’un format annotable jusqu’à l’attribution d’un DOI et d’une licence de réutilisation (CC-BY), en incluant le détail des sommes monétaires. Parmi les 96 accords disponibles, dont 47 signés en 2020, 62 ont fait l’objet d’une analyse en profondeur. C’est à notre connaissance la première analyse à cette échelle, sur un type de matériel non seulement inédit, mais qui était auparavant soumis à des clauses de confidentialité. Fondée sur une lecture minutieuse, l’étude décrit de manière fine leurs propriétés, depuis la matérialité du document jusqu’aux formules financières, en passant par leur morphologie et l’ensemble des droits et devoirs des parties. Les contenus des accords sont donc analysés comme une collection dont nous cherchons à déterminer les points communs et les variations, à travers des codages explicites sur certaines de leurs caractéristiques. L’étude pointe également des incertitudes, et notamment leur caractère « transitionnel », qui demeure fortement discuté. D’un point de vue morphologique, les accords montrent une grande diversité en matière de taille (de 7 à 488 pages) et de structure. Néanmoins, par définition, ils articulent tous deux objets essentiels : d’une part, les conditions de réalisation d’une lecture d’articles de revues, sous forme d’abonnement, mêlant des préoccupations d’accès et de sécurité ; d’autre part, les modalités de publication en accès ouvert, articulant la gestion d’un nouveau type de workflow à toute une série d’options possibles. Parmi ces options, mentionnons notamment le périmètre des revues considérées (hybrides et/ou accès ouvert), les licences disponibles, le degré d’obligation de cette publication, les auteurs éligibles ou le volume d’articles publiables. L’un des résultats les plus importants de cette analyse approfondie est la mise au jour d’un découplage presque complet, au sein même des accords, entre l’objet abonnement et l’objet publication. Bien entendu, l’abonnement est systématiquement configuré dans un monde fermé, soumis à paiement qui déclenche des séries d’identification des circulations légitimes tant du contenu informationnel que des usagers. Il insiste notamment sur les interdictions de réutilisation ou même de copie des articles scientifiques. À l’opposé, la publication en accès ouvert est attachée à un monde régi par l’accès gratuit au contenu, ce qui induit des préoccupations de gestion du workflow et des modalités d’accessibilité. De plus, les différents éléments constitutifs de ces objets contractuels ne sont pas couplés : d’un côté, les lecteurs sont constitués de l’ensemble des membres des institutions abonnées, de l’autre, seuls les auteurs correspondants (« corresponding authors ») sont concernés ; les listes de revues accessibles à la lecture et celles réservées à la publication en accès ouvert sont le plus souvent distinctes ; les workflows ont des objectifs et des organisations matérielles totalement différentes, etc. L’articulation entre les deux objets contractuels relève uniquement d’une formule de distribution financière qui, outre des combinaisons particulières entre l’un et l’autre, permet d’attribuer des étiquettes distinctes aux accords (offset agreement, publish & read, read & publish, read & free articles, read & discount). Au-delà de cette distribution, l’étude des arrangements financiers montre une gamme de dispositions allant d’une prévisibilité budgétaire totale, donc identique aux accords d’abonnement antérieurs, à une incertitude sur le volume de publication ou sur le montant définitif des sommes échangées. Les modalités concrètes de calcul des montants associés à la publication en accès ouvert sont relativement variées. S’il existe effectivement des formules récurrentes (volume d’articles multiplié par un prix individuel, reprise de la moyenne des sommes totales d’APC des années précédentes...), le calcul des sommes en jeu est toujours le résultat d’une négociation singulière entre un consortium et un éditeur scientifique, et aboutit parfois à des formules originales et complexes. À ce titre, l’espace des possibles en matière de formules financières n’est jamais totalement clos. Par ailleurs, la volonté des consortiums d’opérer une « transformation » de leurs accords vers la publication à coût constant renvoie à des définitions diversifiées du « coût » (inclusion ou non des dépenses d’APC préexistantes) et de la constance (admission ou pas d’une « inflation » à 2 ou 3%). De plus, nous n’avons observé aucune disposition contractuelle permettant d’anticiper les sommes en jeu au-delà de l’horizon temporel de l’accord courant. La grande diversité des accords provient d’une part des conditions initiales des relations entre consortiums et éditeurs scientifiques – les sommes dépensées en abonnement étant le point de départ des nouveaux accords –, d’autre part des objectifs de chaque partie. Même si cette étude excluait volontairement les négociations, les accords portent des traces de ces objectifs. Ainsi, de nombreux accords sont de nature explicitement expérimentale, quand certains visent un contrôle budgétaire strict, ou d’autres ambitionnent, dans la période plus récente, la publication du plus grand nombre possible d’articles en accès ouvert. C’est dans ce dernier cas qu’on touche à l’ambiguïté des attentes générales sur les accords transformants. En effet, pour les consortiums, la dimension « transformante » consiste essentiellement à transférer les sommes traditionnellement allouées à l’abonnement vers la publication en accès ouvert. Mais l’objectif n’est jamais de transformer le modèle économique des revues, c'est-à-dire de faire basculer des revues sous abonnement ou hybrides en revues entièrement en accès ouvert. D’ailleurs, aucune clause ne vise une telle fin – à l’exception du modèle d’accord proposé par l’éditeur ACM. Du côté des éditeurs, et notamment de Springer, le caractère cumulatif des accords nationaux passés vise à projeter un monde de la publication où l’accès ouvert devient de fait quantitativement très dominant, sans pour autant modifier de manière pérenne le modèle économique de leurs revues. Notre étude montre que les accords transformants actuels ne permettent pas d’assurer de manière durable une transition de l’économie de la publication vers l’accès ouvert, dans la mesure où ils n’offrent pas de garantie sur le contrôle des dépenses ni sur la pérennité de l’ouverture des contenus. L’avenir des relations entre consortium et éditeur demeure largement indéterminé.