Tesi sul tema "Réduction de la complexité de calcul"
Segui questo link per vedere altri tipi di pubblicazioni sul tema: Réduction de la complexité de calcul.
Cita una fonte nei formati APA, MLA, Chicago, Harvard e in molti altri stili
Vedi i top-50 saggi (tesi di laurea o di dottorato) per l'attività di ricerca sul tema "Réduction de la complexité de calcul".
Accanto a ogni fonte nell'elenco di riferimenti c'è un pulsante "Aggiungi alla bibliografia". Premilo e genereremo automaticamente la citazione bibliografica dell'opera scelta nello stile citazionale di cui hai bisogno: APA, MLA, Harvard, Chicago, Vancouver ecc.
Puoi anche scaricare il testo completo della pubblicazione scientifica nel formato .pdf e leggere online l'abstract (il sommario) dell'opera se è presente nei metadati.
Vedi le tesi di molte aree scientifiche e compila una bibliografia corretta.
1
Rouat, Valérie. "Validité de l'approche classification dans la réduction statistique de la complexité de #SAT". Rennes 1, 1999. http://www.theses.fr/1999REN10021.
Abstract (sommario):
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.
2
Barbanchon, Régis. "Réductions fines entre problèmes NP-complets : linéarité, planarité, parcimonie, et minimalité logique". Caen, 2003. http://www.theses.fr/2003CAEN2066.
Abstract (sommario):
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.
3
Berthomieu, Jérémy. "Contributions à la résolution des systèmes algébriques : réduction, localisation, traitement des singularités ; implantations". Phd thesis, Palaiseau, Ecole polytechnique, 2011. https://theses.hal.science/docs/00/67/19/68/PDF/Main.pdf.
Abstract (sommario):
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éeThis 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
4
Berthomieu, Jérémy. "Contributions à la résolution des systèmes algébriques : réduction, localisation, traitement des singularités ; implantations". Phd thesis, Ecole Polytechnique X, 2011. http://pastel.archives-ouvertes.fr/pastel-00670436.
Abstract (sommario):
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.
5
Stehlé, Damien. "Algorithmique de la réduction de réseaux et application à la recherche de pires cas pour l'arrondi defonctions mathématiques". Phd thesis, Université Henri Poincaré - Nancy I, 2005. http://tel.archives-ouvertes.fr/tel-00011150.
Abstract (sommario):
Les réseaux euclidiens sont un outil particulièrement puissant dansplusieurs 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.
6
Shahkarami, Abtin. "Complexity reduction over bi-RNN-based Kerr nonlinearity equalization in dual-polarization fiber-optic communications via a CRNN-based approach". Electronic Thesis or Diss., Institut polytechnique de Paris, 2022. http://www.theses.fr/2022IPPAT034.
Abstract (sommario):
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
7
Guiraud, Maël. "Ordonnancement periodiques de messages pour minimiser la latence dans les réseaux dans un contexte 5G et au delà". Electronic Thesis or Diss., université Paris-Saclay, 2021. http://www.theses.fr/2021UPASG034.
Abstract (sommario):
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éveloppementThis 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
8
Cagniart, Nicolas. "Quelques approches non linéaires en réduction de complexité". Thesis, Sorbonne université, 2018. http://www.theses.fr/2018SORUS194/document.
Abstract (sommario):
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éduitModel 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
9
Madet, Antoine. "Complexité implicite dans des Lambda -calculs concurrents". Paris 7, 2012. http://www.theses.fr/2012PA077222.
Abstract (sommario):
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 BrunelControlling 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
10
Ayad, Ali. "Complexité de résolution de systèmes algébriques paramétrés". Rennes 1, 2006. https://tel.archives-ouvertes.fr/tel-00127383.
Abstract (sommario):
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.
11
Senot, Maxime. "Modèle géométrique de calcul : fractales et barrières de complexité". Phd thesis, Université d'Orléans, 2013. http://tel.archives-ouvertes.fr/tel-00870600.
Abstract (sommario):
Les modèles géométriques de calcul permettent d'effectuer des calculs à l'aide de primitives géométriques. Parmi eux, le modèle des machines à signaux se distingue par sa simplicité, ainsi que par sa puissance à réaliser efficacement de nombreux calculs. Nous nous proposons ici d'illustrer et de démontrer cette aptitude, en particulier dans le cas de processus massivement parallèles. Nous montrons d'abord à travers l'étude de fractales que les machines à signaux sont capables d'une utilisation massive et parallèle de l'espace. Une méthode de programmation géométrique modulaire est ensuite proposée pour construire des machines à partir de composants géométriques de base -- les modules -- munis de certaines fonctionnalités. Cette méthode est particulièrement adaptée pour la conception de calculs géométriques parallèles. Enfin, l'application de cette méthode et l'utilisation de certaines des structures fractales résultent en une résolution géométrique de problèmes difficiles comme les problèmes de satisfaisabilité booléenne SAT et Q-SAT. Ceux-ci, ainsi que plusieurs de leurs variantes, sont résolus par machines à signaux avec une complexité en temps intrinsèque au modèle, appelée profondeur de collisions, qui est polynomiale, illustrant ainsi l'efficacité et le pouvoir de calcul parallèle des machines à signaux.
12
Lafitte, Grégory. "Calculs et infinis". Lyon, École normale supérieure (sciences), 2002. http://www.theses.fr/2002ENSL0239.
Abstract (sommario):
"Nous introduisons une hiérarchie de notions de calcul généralisé. L'idée est de regrouper en une notion tout ce que l'on pourrait qualifier de "calculabilité", de pouvoir étudier ces notions et en fin de compte d'établir des théorèmes de transfert entre elles. Ces notions correspondent certaines fois aussi à des modèles de calcul obtenues par le biais de machines concrètes. Nous avons ainsi un nouveau modèle de calcul avec les " automates cellulaires à temps infini " qui ont l'avantage sur les machines de Turing d'être plus homogènes (absence de tête). La notion de complexité de calcul (selon une certaine notion de calcul) est également généralisée et étudiée. Enfin, nous obtenons des notions de réels aléatoires plus fines que la notion classique de Martin-Löf (ou Kolmogorov) que l'on peut affiner de plus en plus. Tout ceci mène à la notion de complexité de Kolmogorov généralisée qui ouvre des perspectives intéressantes. "We introduce a hierarchy of notions of generalized computation. The idea is to almagamate in one concept all that we could qualify of "computability", to study those notions and ultimately to have transfer theorems between those notions. Those notions correspond also in some cases to computation models obtained by means of concrete machines. We obtain in this way a new computation model, "infinite time cellular automata", which are more homogeneous than Turing machines (lack of head). The notion of computational complexity (according to a certain notion of computation) is also generalized and studied. Finally, we obtain notions of random reals that are finer than the classical notion of Martin-Löf (or Kolmogorov) and yet more and more refinable. All of this leads to a notion of generalized Kolmogorov complexity which opens up interesting prospects.
13
Pégny, Maël. "Sur les limites empiriques du calcul : calculabilité, complexité et physique". Thesis, Paris 1, 2013. http://www.theses.fr/2013PA010673/document.
Abstract (sommario):
Durant ces dernières décennies, la communauté informatique a montré un intérêt grandissant pour les modèles de calcul non-standard, inspirés par des phénomènes physiques, biologiques ou chimiques. Les propriétés exactes de ces modèles ont parfois été l'objet de controverses: que calculent-ils? Et à quelle vitesse? Les enjeux de ces questions sont renforcés par la possibilité que certains de ces modèles pourraient transgresser les limites acceptées du calcul, en violant soit la thèse de Church-Turing soit la thèse de Church-Turing étendue. La possibilité de réaliser physiquement ces modèles a notamment été au coeur des débats. Ainsi, des considérations empiriques semblent introduites dans les fondements même de la calculabilité et de la complexité computationnelle, deux théories qui auraient été précédemment considérées comme des parties purement a priori de la logique et de l'informatique. Par conséquent, ce travail est consacré à la question suivante : les limites du calcul reposent-elles sur des fondements empiriques? Et si oui, quels sont-ils? Pour ce faire, nous examinons tout d'abord la signification précise des limites du calcul, et articulons une conception épistémique du calcul, permettant la comparaison des modèles les plus variés. Nous répondrons à la première question par l'affirmative, grâce à un examen détaillé des débats entourant la faisabilité des modèles non-standard. Enfin, nous montrerons les incertitudes entourant la deuxième question dans l'état actuel de la recherche, en montrant les difficultés de la traduction des concepts computationnels en limites physiquesRecent years have seen a surge in the interest for non-standard computational models, inspired by physical, biological or chemical phenomena. The exact properties of some of these models have been a topic of somewhat heated discussion: what do they compute? And how fast do they compute? The stakes of these questions were heightened by the claim that these models would violate the accepted limits of computation, by violating the Church-Turing Thesis or the Extended Church-Turing Thesis. To answer these questions, the physical realizability of some of those models - or lack thereof - has often been put at the center of the argument. It thus seems that empirical considerations have been introduced into the very foundations of computability and computational complexity theory, both subjects that would have been previously considered purely a priori parts of logic and computer science. Consequently, this dissertation is dedicated to the following question: do computability and computational complexity theory rest on empirical foundations? If yes, what are these foundations? We will first examine the precise meaning of those limits of computation, and articulate a philosophical conception of computation able to make sense of this variety of models. We then answer the first question by the affirmative, through a careful examination of current debates around non-standard models. We show the various difficulties surrounding the second question, and study how they stem from the complex translation of computational concepts into physical limitations
14
LACROSE, Véronique. "Réduction de la complexité des contrôleurs flous : applications à la commande multivariable". Phd thesis, INSA de Toulouse, 1997. http://tel.archives-ouvertes.fr/tel-00010030.
Abstract (sommario):
La commande en logique floue permet de s'affranchir de l'utilisation de modèles mathématiques parfois difficiles à obtenir. Sa capacité à traduire la connaissance d'un opérateur humain en règles d'expertise énoncées dans un langage simple en fait une technique très prometteuse. Néanmoins, lorsque le nombre de variables entrant en jeu devient trop important, la base de règles explose très vite, et des problèmes liés à sa réalisation pratique en découlent. Cette thèse s'inscrit dans la mouvance des travaux actuels sur la commande floue et s'attache au problème de l'explosion combinatoire du nombre de règles. Dans une première partie, les principes de base de la logique floue et de la commande floue sont rappelés. Dans une deuxième partie, des solutions visant à simplifier la synthèse d'un contrôleur flou sont présentées. Deux cas sont considérés : la base de règles existe déjà, la base de règles n'est pas disponible et la synthèse d'un contrôleur flou de complexité réduite est à réaliser. Dans la pratique, on ne dispose généralement pas de cette base de règles, aussi, on insiste davantage sur le deuxième cas de figure. Une fois la structure du contrôleur flou défini, le nombre de paramètres à régler pouvant atteindre un nombre important, il est intéressant d'utiliser des techniques d'apprentissage afin d'automatiser la mise au point du contrôleur flou. Les paramètres de ce dernier (gains et fonctions d'appartenance, en entrée et en sortie) sont ici réglés à travers la méthode, très simple, de descente du gradient. Dans une troisième partie, la démarche proposée dans ce mémoire est appliquée avec succès à la commande de deux processus multivariables : un bac mélangeur et un procédé biologique de traitement des eaux-usées.
15
Lanco, Antoine. "Stratégies pour la réduction forte". Electronic Thesis or Diss., université Paris-Saclay, 2023. http://www.theses.fr/2023UPASG097.
Abstract (sommario):
La sémantique d'un langage de programmation, et d'un langage fonctionnel en particulier, laisse généralement une certaine liberté quant à l'ordre dans lequel sont effectuées les différentes opérations. Les différentes stratégies qui peuvent être adoptées, comme l'appel par valeur ou l'évaluation paresseuse, bénéficient déjà à la fois d'un large corpus théorique et de nombreuses implémentations efficaces. Ce corpus cependant est majoritairement tourné vers un objectif d'évaluation des programmes, c'est-à-dire de production d'une valeur. Le cadre associé est celui de l'évaluation faible, dans lequel aucune évaluation n'est effectuée à l'intérieur d'une fonction qui ne serait pas totalement appliquée. En effet, dans un langage fonctionnel la clôture représentant une telle fonction est déjà en elle-même considérée comme une valeur.Cependant plusieurs situations justifient d'aller au-delà de ce cadre vers un objectif de normalisation, où la réduction est poussée jusqu'au bout, y compris à l'intérieur de ce qui est usuellement considéré comme une valeur. On parle alors de réduction forte. L'évaluation forte peut notamment intervenir comme un outil d'optimisation à la compilation, pour évaluer partiellement le corps d'une fonction en fonction de valeurs qui seraient déjà connues pour certains de ses arguments. Dans un autre contexte, cela concerne également l'implémentation des assistants à la preuve, avec par exemple dans Coq les différentes machines de conversion, en stratégie paresseuse, et de réduction, en appel par valeur.Malgré l'importance des applications, le corpus théorique fondant l'extension des stratégies usuelles de l'évaluation faible au cadre de la réduction forte reste très en-deçà du corpus traditionnel de l'évaluation faible, tant du point de vue du volume que de la maturité. Il se concentre sur quelques extensions particulières ou sur des cadres intermédiaires comme l'évaluation ouverte. Ces travaux, pour l'essentiel très récents, n'apportent cependant pas encore de réponses satisfaisantes à tous les nouveaux comportements observés en réduction forte, par exemple relatifs à l'explosion de la taille de certains termes. Par conséquent, les implémentations déjà réalisées utilisent souvent des stratégies ad hoc pour limiter l'impact de ces problèmes.Cette thèse définit un calcul en appel par nécessité avec réduction forte, c'est-à-dire des stratégies de normalisation qui étendent les stratégies usuelles d'évaluation en appel par nécessité. Le calcul utilise des substitutions explicites afin de supprimer certains effets d'explosion de la taille des termes. Par ailleurs, les stratégies détectent de manière précoce certains radicaux nécessaires, réduisant ainsi le nombre de calculs dupliqués.De plus, notre calcul bénéficie de propriétés de correction (les résultats obtenus correspondent bien à des formes normales du lambda-calcul) et de complétude (pour tout terme normalisable, nos stratégies atteignent bien la forme normale). Nous avons formalisé ce calcul et prouvé sa correction avec l'assistant de preuve Abella.Parmi les stratégies autorisées par notre calcul, nous en avons isolé une qui produit systématiquement les séquences de réduction les plus courtes, et défini et implémenté une machine abstraite qui réalise cette stratégie. L'implémentation a permis de réaliser un grand nombre de tests qui confirment les gains attendus par rapport aux stratégies d'évaluation usuellesSemantics of a programming language, especially functional ones, usually leaves underspecified the order in which the various operations are performed. Some usual strategies, such as call by value or lazy evaluation, already benefit from a large theoretical corpus as well as numerous efficient implementations. This corpus, however, mainly focuses on program evaluation, that is, producing a value. This is the framework of weak evaluation, in which no evaluation is performed inside a function that is not fully applied. Indeed, in a functional language, the closure that represents such a function is already considered as a value.Yet, several situations necessitate to go further and to look at normalization, which means that reduction is performed as far as possible, including in objects that are already values. That is called strong reduction. Among other things, strong evaluation can be used as an optimization pass during compilation, in order to partly evaluation the body of a function depending on the already known values of some of its arguments. Strong evaluation is also used inside proof assistants, for example Coq's machines of conversion (lazy strategy) and of reduction (call by value).Despite the importance of these applications, the theoretical corpus that extends the usual strategies from weak evaluation to strong reduction is way less comprehensive than the corpus for weak evaluation. It either focuses on some specific extensions or on some intermediate frameworks such as open evaluation. These works, very recent for the most part, do not yet bring any satisfying explanation to the way strong reduction behaves, for example the size explosion of some terms. As a consequence, the existing implementations often rely on some adhoc strategies to alleviate the impact of these issues.This thesis defines a call-by-need calculus with strong reduction, meaning a normalization strategies that extend the usual call-by-need evaluation strategies. The computation uses explicit substitutions to eliminate certain term size explosion effects, Furthermore, the strategies offer early detection of certain necessary redexes, thereby reducing the number of duplicated computations.Furthermore, our computation benefits from correctness properties (the obtained results correspond to normal forms of the lambda calculus), and completeness (for any normalizable term, our strategies reach the normal form). We have formalized our computation and prove its correctness with the Abella proof assistant.In this space, we have isolated a strategy that consistently produces the shortest reduction sequences and defined and implemented an abstract machine that executes this strategy. The implementation allowed us to conduct numerous tests which confirm the expected gains over conventional évaluation strategies
16
Ziegler, Yvan. "Calcul effectif sur les courbes hyperelliptiques à réduction semi-stable". Thesis, Rennes 1, 2019. http://www.theses.fr/2019REN1S023/document.
Abstract (sommario):
Dans cette thèse nous étudions la filtration par le poids sur la cohomologie de De Rham d’une courbe hyperelliptique C définie sur une extension finie de Qp et à réduction semi-stable. L’objectif est de fournir des algorithmes calculant explicitement, étant donné une équation de C, les bases des crans de la filtration par le poids ainsi que la matrice de l’accouplement de Poincaré. Dans le premier chapitre, nous mettons en place des outils relatifs à la cohomologie de De Rham algébrique de la courbe hyperelliptique. Nous construisons une base adaptée de la cohomologie de De Rham de C, nous établissons une formule explicite pour le cup-produit et la trace, et enfin nous proposons un algorithme calculant la matrice de l’accouplement de Poincaré. Le deuxième chapitre est consacré à la description explicite de la flèche induite par l’inclusion du tube d’un point double sur les espaces de cohomologie. C’est l’ingrédient essentiel pour pouvoir décrire la filtration par le poids sur la cohomologie de De Rham de C. À cette fin nous nous plaçons dans le cadre de la géométrie analytique à la Berkovich et nous introduisons puis développons les notions de point résiduellement singulier standard et de forme apparente de l’équation de la courbe. Dans le troisième et dernier chapitre, nous faisons la synthèse des résultats obtenus et achevons la description de la filtration par le poids. Enfin, nous donnons les algorithmes calculant les bases de Fil0 et Fil1. Pour les algorithmes obtenus dans la thèse nous proposons une implémentation en sage, ainsi que des exemples concrets sur des courbes de genre un et deuxIn this thesis we study the weight filtration on the De Rham cohomology of an hyperelliptic curve C defined over a finite extension of Qp and with semi-stable reduction. The goal is to provide algorithms computing explicitly, given an equation of C, the basis of the weight filtration’s spaces as well as the matrix of the Poincaré pairing. In the first chapter we introduce tools related to the algebraic De Rham cohomology of the hyperelliptic curve. We build a suitable basis of the De Rham cohomology of C, we establish explicit formulae for the cup-product and the trace, and we give an algorithm computing the matrix of the Poincaré pairing. The second chapter is dedicated to the explicit description of the morphism induced by the inclusion of the tube of a double point on the cohomology spaces. It is the main ingredient that allows us to describe the weight filtration on the De Rham cohomology of C. To achieve that, we use the framework of the Berkovitch analytical geometry. We introduce and then we develop the notion of standard residually singular points and the notion of apparent form of the curve’s equation. In the third and last chapter, we synthesize all the results and we complete the description of the weight filtration. Finally, we give the algorithms that compute the basis of Fil0 and Fil1. For each of our algorithm, we propose a sage implementation and concrete examples on genus one and two curves
17
Nesme, Vincent. "Complexité en requêtes et symétries". Phd thesis, Ecole normale supérieure de lyon - ENS LYON, 2007. http://tel.archives-ouvertes.fr/tel-00156762.
Abstract (sommario):
Ces travaux portent sur l'étude de la complexité en requêtes de problèmes symétriques, dans les cadres du calcul probabiliste classique
et du calcul quantique.
Il est montré, dans le cas quantique, une application de la méthode de
bornes inférieures dite "polynomiale" au calcul de la complexité en
requêtes des problèmes de sous-groupes cachés abéliens, via la technique de "symétrisation".
Dans le cas du calcul probabiliste, sous une hypothèse de "symétrie
transitive" des problèmes, il est donné une formule combinatoire
permettant de calculer la complexité en requêtes exacte du meilleur
algorithme non-adaptatif. De plus, il est mis en évidence que sous
certaines hypothèses de symétrie, ce meilleur algorithme non-adaptatif
est optimal même parmi les algorithmes probabilistes plus généraux, ce qui donne pour la classe de problèmes correspondante une expression exacte de la complexité en requêtes.
18
Henrio, Ludovic. "Asynchronous object calculus : confluence and determinacy". Nice, 2003. http://www.theses.fr/2003NICE4047.
Abstract (sommario):
L'objectif de cette thèse est de concevoir un calcul d'objets permettant d'écrire des applications parallèles et distribuées, en particulier dans un cadre à grande échelle, tout en assurant de bonnes propriétés. Le calcul proposé s'intitule ASP : Asynchronous Sequential Processes. Les principales caractéristiques de ce calcul sont : des communications asynchrones, la présence de futurs et une exécution séquentielle dans chacun des processus. Ce calcul exhibe de fortes propriétés de confluence et de déterminisme. Cette thèse a donc aussi pour objectif de prouver de telles propriétés dans un cadre aussi général que possible. ASP est basé sur une répartition des objets en différentes activités disjointes. Une activité est un ensemble d'objets gérés par un unique processus. Les objets actifs sont des objets accessibles par des références globales/distantes. Ils communiquent à travers des appels de méthodes asynchrones avec un mécanisme de futurs. Un futur est une référence globale désignant un résultat qui n'est pas encore calculé. Cette thèse modélise ces différents aspects, leurs principales propriétés et les conséquences de ces mécanismes sur la notion de comportement déterministe des programmes. Le résultat principal consiste en une propriété de confluence et son application à l'identification d'un ensemble de programmes se comportant de façon déterministe. Du point de vue pratique, ASP peut aussi être considéré comme une modélisation de la librairie ProActive. Cette librairie fournit des outils pour développer des applications parallèles et distribuées en JavaThe objective of this thesis is to design an object calculus that allows one to write parallel and distributed applications, particularly on wide range networks, while ensuring good properties. This calculus is named ASP : Asynchronous Sequential Processes. The main characteristics of ASP are: asynchronous communications, futures, and a sequential execution within each process. ASP presents strong confluence and determinism properties, proved in a context as general as possible within this thesis. A first design decision is the absence of sharing : objects live in disjoint activities. An activity is a set of objects managed by a unique process and a unique active object. Active objects are accessible through global/distant references. They communicate through asynchronous method calls with futures. A future is a global reference representing a result not yet computed. This thesis models those aspects, their main properties, and the consequences of these mechanisms on the deterministic behavior of programs. The main result consists in a confluence property and its application to the identification of a set of programs behaving deterministically. From a practical point of view, ASP can also be considered as a model of the ProActive library. This library provides tools for developing parallel and distributed applications in Java
19
Trystram, Denis. "Quelques résultats de complexité en algorithmique parallèle et systolique". Grenoble INPG, 1988. http://tel.archives-ouvertes.fr/tel-00009202.
Abstract (sommario):
L'objet de cette thèse est l'étude de la parallélisation d'algorithmes du calcul scientifique et leur implémentation sur des ordinateurs parallèles à mémoire partagée et sur des réseaux systoliques. Un accent particulier est mis sur l'obtention de résultats de complexité. La thèse est organisée autour d'articles et textes de conférences qui sont analysés et discutés dans une première partie de façon à permettre de replacer les problèmes traités dans leur contexte. Dans le premier chapitre, nous présentons les principaux résultats théoriques concernant l'étude de complexité des algorithmes parallèles, ainsi qu'une description critique de l'architecture de référence, qui est une machine de type MIMD à mémoire partagée. Le chapitre suivant est dédie" à l'ensemble des résultats de complexité concernant les algorithmes de diagonalisation et l'élimination de Gauss, il a pour but d'illustrer la méthodologie. Il existe en tout dix écritures possibles de la méthode de Gauss, qui conduisent principalement à deux grandes classes de graphes de précédente, conceptuellement différents : les graphes de type "glouton" et ceux du type "2 pas". Ces types de graphes se rencontrent d'une manière plus générale dans d'autres problèmes d'algèbre linéaire et même dans certaines méthodes non numériques de la théorie des graphes. Nous développons les résultats de complexité concernant ces deux types de graphes sur les exemples les plus courant (versions kji et kij de Gauss en parallèle), puis nous montrons comment adapter l'étude en prenant en compte t'es temps de communication entre tes processeurs, ce qui rend le modèle théorique plus réaliste. Le chapitre 6 est consacré aux architectures systoliques. Le problème du chemin algébrique permet d'unifier plusieurs problèmes informatiques. Nous présentons un réseau résolvant ce problème en Sn-2 pas sur un réseau de taille n(n+l ). De plus, quelques modifications permettent de calculer des projections en filtrage adaptatif en vu d'obtenir une solution en temps réel pour le traitement numérique des signaux. Avant de conclure, nous présentons des résultats complémentaires de parallélisation effective sur d'autres types d'architectures : l'étude de l'algorithme du gradient conjugué sur des super calculateurs (CRAY-XMP et IBM 3090-VF).
20
Spaenlehauer, Pierre-Jean. "Résolution de systèmes multi-homogènes et déterminantiels algorithmes - complexité - applications". Paris 6, 2012. http://www.theses.fr/2012PA066467.
Abstract (sommario):
De nombreux systèmes polynomiaux multivariés apparaissant en Sciences de l'Ingénieur possèdent une structure algébrique spécifique. En particulier, les structures multi-homogènes, déterminantielles et les systèmes booléens apparaissent dans une variété d'applications. Une méthode classique pour résoudre des systèmes polynomiaux passe par le calcul d'une base de Gröbner de l'idéal associé au système. Cette thèse présente de nouveaux outils pour la résolution de tels systèmes structurés. D'une part, ces outils permettent d'obtenir sousdes hypothèses de généricité des bornes de complexité du calcul debase de Gröbner de plusieurs familles de systèmes polynomiauxstructurés (systèmes bilinéaires, systèmes déterminantiels, systèmesdéfinissant des points critiques, systèmes booléens). Ceci permetd'identifier des familles de systèmes pour lequels la complexité arithmétique de résolution est polynomiale en le nombre de solutions. D'autre part, cette thèse propose de nouveaux algorithmequi exploitent ces structures algébriques pour améliorer l'efficacité du calcul de base de Gröbner et de la résolution (systèmes multi-homogènes, systèmes booléens). Ces résultats sontillustrés par des applications concrètes en cryptologie (cryptanalyse des systèmes MinRank et ASC), en optimisation et en géométrie réelle effective (calcul de points critiques)Multivariate polynomial systems arising in Engineering Science often carryalgebraic structures related to the problems they stem from. Inparticular, multi-homogeneous, determinantal structures and booleansystems can be met in a wide range of applications. A classical method to solve polynomial systems is to compute a Gröbner basis ofthe ideal associated to the system. This thesis provides new tools forsolving such structured systems in the context of Gröbner basis algorithms. On the one hand, these tools bring forth new bounds on the complexity of thecomputation of Gröbner bases of several families of structured systems(bilinear systems, determinantal systems, critical point systems,boolean systems). In particular, it allows the identification of families ofsystems for which the complexity of the computation is polynomial inthe number of solutions. On the other hand, this thesis provides new algorithms which takeprofit of these algebraic structures for improving the efficiency ofthe Gröbner basis computation and of the whole solving process(multi-homogeneous systems, boolean systems). These results areillustrated by applications in cryptology (cryptanalysis of MinRank),in optimization and in effective real geometry (critical pointsystems)
21
Markey, Nicolas. "Logiques temporelles pour la vérification : expressivité, complexité, algorithmes". Orléans, 2003. http://www.theses.fr/2003ORLE2004.
Abstract (sommario):
Ce travail s'inscrit dans le cadre de la vérification formelle de programmes: le model checking est une technique qui permet de s'assurer qu'une propriété, exprimée en logique temporelle, est vérifiée par le modèle d'un système. Cette thèse étudie plusieurs logiques temporelles, du point de vue de l'expressivité et de la complexité. Nous étudions trois grands types de logiques temporelles : - concernant la logique temporelle du temps linéaire, nous prouvons que l'ajout de modalités du passé permet de simplifier l'écriture des formules sans augmenter la complexité des problèmes de model checking. Nous étudions également l'impact de l'ajout de la modalité Now ; - concernant la logique temporelle du temps arborescent, nous établissons la complexité du model checking pour plusieurs extensions classiques de CTL ; - enfin, nous montrons qu'il est possible, sous certaines conditions, de vérifier efficacement des propriétés quantitatives sur la durée séparant deux évènements.
22
Madet, Antoine. "Complexité Implicite de Lambda-Calculs Concurrents". Phd thesis, Université Paris-Diderot - Paris VII, 2012. http://tel.archives-ouvertes.fr/tel-00794977.
Abstract (sommario):
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.
23
Bonfante, Guillaume. "Constructions d'ordres, analyse de la complexité". Vandoeuvre-les-Nancy, INPL, 2000. http://docnum.univ-lorraine.fr/public/INPL_T_2000_BONFANTE_G.pdf.
Abstract (sommario):
Le thème de la thèse concerne l'étude des ordres, en termes de complexité en réécriture, mais aussi dans le cadre des termes ordinaux, des hiérarchies de fonctions sous-récursives. Nous avons cherché à extraire de la notion de preuve de terminaison des informations concernant la complexité des fonctions calculées par des systèmes de réécriture. Cela nous a permis d'établir de nombreuses caractérisations, en termes de complexité, des systèmes de réécriture. Ainsi, est-il possible de déterminer a priori la complexité d’un système, au seul vu de sa preuve de terminaison. Nous étudions plus spécifiquement le cas de l'ordre de Knuth-Bendix et celui de l'ordre par interprétation polynomiale. D'autre part, nous avons entamé une recherche plus fondamentale concernant la représentation de la notion d'ordre dans les λ-calculs typés. Cet intérêt provient de ce qu'une telle représentation est nécessaire dès lors que l'on veut représenter des structures définies par des opérateurs ω -aire, ce qui est le cas des termes ordinaux par exemple. Nous étudions d'un point de vue sémantique l'univers de travail, nous dégageons en particulier une notion de structure monoïdale fermée, mais aussi de manière syntaxique en proposant un calcul pour lequel un type représente un graphe plutôt qu'un (traditionnel) ensembleOur concern in the thesis is in the study of orders, through the analysis of complexity within rewriting, but also through the construction of monotonous λ-calculi within the framework of ordinal terms, and subrecursivc hierarchies. We show how to extract some knowledge in terms of complexity from the proof of termination in rewriting theory. This allows us to establish some hierarchies of caracterisation of complexity classes in terms of rewriting. So, one has an a priori complexity measure of functions with respect to their proof of termination. We study more specifically the case of the Knuth-Bendix ordering and polynomial interpretations. Next to that, we engaged ourselves into an other challenge, a more fundamental approach. This concerns the notion of ordering within typed λ-calculi. The interest comes from the fact that such a representation is necessary when one has to represent a structure with an ω -ary operation: that is an operation that only applies to monotonous sequences (which is the case of ordinal terms). We develop semantical tools, in particular we present a mono id al close category on graphs, but also syntactical constructions, in particular a calcul us where types arc graphs in which the traditional approach would be in terms of sets
24
Vidal, Didier. "Nouvelles notions de réduction en lambda-calcul : Application à la réalisation d'un langage fonctionnel fondé sur la réduction forte". Nancy 1, 1989. http://www.theses.fr/1989NAN10488.
25
Brault-Baron, Johann. "De la pertinence de l’énumération : complexité en logiques". Caen, 2013. http://www.theses.fr/2013CAEN2056.
Abstract (sommario):
Au-delà de la décision de problèmes de satisfaisabilité, on s’intéresse à la génération exhaustive de leurs solutions, l’énumération. Nous interrogeons d’abord la pertinence du problème d’énumération dans le cadre très classique de la logique propositionnelle. La dichotomie de Creignou et Hébrard prouve déjà l’équivalence entre les classes polynomiales pour la décision non triviale et celles pour l’énumération. On donne des algorithmes d’énumération optimaux pour chacune de ces classes, qui généralisent tout algorithme de décision non triviale, suggérant que l’énumération est le problème pertinent dans ce cadre. Ensuite, nous complétons et simplifions des résultats de dichotomie de Bagan et al. Qui établissent un lien étroit entre la facilité d’une requête conjonctive et une notion d’acyclicité d’hypergraphe. On prouve alors, grâce à un nouvel d’algorithme, des résultats similaires pour la classe duale de celle des requêtes conjonctives. Finalement, en généralisant le résultat classique de combinatoire de Brouwer et Kolen, on unifie l’ensemble de ces résultats sous forme d’une dichotomie pour l’énumération des requêtes conjonctives dites signées, qui établit un lien fort entre facilité de l’énumération et facilité de la décisionBeyond the decision of satisfiability problems, we investigate the problem of enumerating all their solutions. In a first part, we consider the enumeration problem in the framework of the propositional satisfiability problem. Creignou and Hébrard proved that the polynomial classes for the non-trivial sat problem are exactly those for the enumeration problem. We give optimal enumeration algorithms for each of these classes, that generalize any non-trivial decision algorithm for this class. This suggests that enumeration is the relevant problem in this case, rather than the decision problem. Beyond the decision of satisfiability problems, we investigate the problem of enumerating all their solutions. In a first part, we consider the enumeration problem in the framework of the propositional satisfiability problem. Creignou and Hébrard proved that the polynomial classes for the non-trivial sat problem are exactly those for the enumeration problem. We give optimal enumeration algorithms for each of these classes, that generalize any non-trivial decision algorithm for this class. This suggests that enumeration is the relevant problem in this case, rather than the decision problem. In a second part, we simplify and complete some results of Bagan et al. That establish a strong connection between the tractability of a conjunctive query and a notion of hypergraph acyclicity. We establish similar results for the dual class of the class of conjunctive queries, thanks to a new algorithm. Finally, we generalize all these results through a single dichotomy for the enumeration problem of conjunctive signed queries, by generalizing some classical combinatorial result by Brouwer and Kolen. This dichotomy establishes a close connection between enumeration strong tractability and decision strong tractability. In a second part, we simplify and complete some results of Bagan et al. That establish a strong connection between the tractability of a conjunctive query and a notion of hypergraph acyclicity. We establish similar results for the dual class of the class of conjunctive queries, thanks to a new algorithm. Finally, we generalize all these results through a single dichotomy for the enumeration problem of conjunctive signed queries, by generalizing some classical combinatorial result by Brouwer and Kolen. This dichotomy establishes a close connection between enumeration strong tractability and decision strong tractability
26
Chapdelaine, Philippe. "Contribution à la théorie de la complexité algorithmique : problèmes de contraintes, complétude et résultats de classification, complexité structurelle". Caen, 2004. http://www.theses.fr/2004CAEN2042.
Abstract (sommario):
Cette thèse se divise en deux parties indépendantes ayant comme point commun la théorie de la complexité algorithmique. Dans la première partie, nous étudions la complexité des problèmes de satisfaction de contraintes. Nous montrons que celle-ci est fortement liée au pouvoir d'expression des contraintes, et que celui-ci peut être déterminé, grâce à une correspondance de Galois, par les propriétés de clôture de ces contraintes. Dans le cas booléen, la structure de ce système de clôture étant connue, nous en déduisons des classifications complètes de la complexité des problèmes de l'audit et du comptage pour les requêtes conjonctives. Nous donnons également, par une technique constructive, la classification de la complexité de la recherche locale pour la satisfaisabilité des contraintes booléennes. Dans la deuxième partie, nous nous intéressons à la classe de complexité du temps linéaire non déterministe, NLIN. Nous étudions des raffinements de celle-ci, notamment les classes obtenues en bornant l'espace. Nous montrons qu'elles contiennent de nombreux problèmes naturels, et nous donnons, pour ces classes, des caractérisations logiques et des problèmes complets. Dans un deuxième temps, nous détaillons la structure interne de NLIN. Nous établissons que, sous certaines hypothèses, il existe une infinité de niveaux de réductions linéaires incomparables entre le niveau du temps linéaire déterministe et celui des problèmes NLIN-complets. Nous développons également la notion d'isomorphie linéaire permettant de préciser la notion d'équivalence linéaire en montrant que des problèmes sont, non seulement de même complexité, mais également structurellement identiques.
27
Taveneaux, Antoine. "Puissance logique et calculatoire de l'aléa algorithmique". Paris 7, 2013. http://www.theses.fr/2013PA077217.
Abstract (sommario):
La théorie de l'aléa effective étudie l'absence de structure qui caractérise l'aléa. La complexité de Kolmogorov est un outil fondamental de cette théorie et nous étudions les propriétés caractéristiques de cette fonctions. Dans un second temps noùs nous intéressons à la possibilité d'étendre l'étude de l'aléa aux suites de bits biaisés en nous demandant si la connaissance précise du biais ou non modifie la qualité de l'aléa que nous décrivons. Nous nous intéressons ensuite à la puissance logique de l'aléa: que peut on déduire du fait (non prouvable) qu'une suite est dénué de structure ? Enfin on s'intéresse a la possibilité de calculer une complétion de l'arithmétique à partir d'un algorithme utilisant de l'aléaTheory of algorithmic randomness theory studies the Jack of structure that characterizes random objects Kolmogorov complexity is a fimdamental tool of this theory and we study the characteristic properties of this fonction. In a second step we investigate the possibility of extending the study of the biased random bit sequences wondering if precise knowledge of using or not changes the quality of randomness we describe, We then focus on the logic power of the random object: What can be inferred from the fact (non provable) that a sequence has no structure? Finally we look a the possibility of calculating a completion of arithmetic from an randomized algorithm
28
Revol, Nathalie. "Complexité de l'évaluation parallèle de circuits arithmétiques". Grenoble INPG, 1994. http://tel.archives-ouvertes.fr/tel-00005109.
Abstract (sommario):
Les algorithmes d'évaluation parallèle des expressions et des circuits arithmétiques peuvent être vus comme des extracteurs du parallélisme intrinsèque contenu dans les programmes séquentiels, parallélisme qui dépasse celui qui peut être lu sur le graphe de précédence et qui tient à la sémantique des opérateurs utilisés. La connaissance des propriétés algébriques, comme l'associativité ou la distributivité, permet une réorganisation des calculs qui n'affecte pas les résultats. Plus la structure algébrique utilisée sera riche en propriétés simples, plus il sera possible d'en tirer parti pour améliorer les algorithmes d'évaluation. Généralisant les algorithmes conçus pour les semi-anneaux, nous proposons un algorithme qui améliore les majorations précédemment connues pour la contraction de circuits arithmétiques dans un treillis. Des simulations de cet algorithme ont permis de mettre en évidence ses qualités de prédicteur automatique de complexité. Réorganiser explicitement les calculs à l'aide de ces algorithmes, c'est-à-dire réaliser un compilateur complet, permet de comparer la réalité des algorithmes parallèles sur machines à mémoire distribuée et la puissance des algorithmes théoriques. Un prototype a été réalisé, basé sur une simplification/extension du langage C. Enfin, l'intérêt de ces techniques dans le domaine de la parallélisation des nids de boucles, pour guider la recherche de réductions cachées dans ces nids, semble prometteuse, parce qu'elle est peu coûteuse à mettre en oeuvre et fournit des informations de qualité. En cela, les recherches en algorithmique parallèle théorique rejoignent les préoccupations de la parallelisation effective
29
Nguyen, Hai-Nam. "Optimisation de la précision de calcul pour la réduction d'énergie des systèmes embarqués". Phd thesis, Université Rennes 1, 2011. http://tel.archives-ouvertes.fr/tel-00705141.
Abstract (sommario):
Cette thèse s'inscrit dans le contexte de la forte augmentation du débit et de la puissance de calcul des systèmes de télécommunications. Cette augmentation entraîne une consommation d'énergie importante et réduit la durée de batterie, ce qui est primordiale pour un système embarqué. Nous proposons des mécanismes permettant de réduire la consommation d'énergie dans un système embarqué, plus particulièrement dans un terminal mobile sans fil. L'implantation efficace des algorithmes de traitement numérique du signal dans les systèmes embarqués requiert l'utilisation de l'arithmétique virgule fixe afin de satisfaire des contraintes de coût, de consommation et d'encombrement. Dans les approches classiques, la largeur des données et des calculs est considérée au pire cas lors de la détermination des spécifications afin qu'elles soient satisfaites dans tout les cas. Nous proposons une approche d'adaptation dynamique, permettant de changer la spécification en fonction de l'environnement (par exemple les conditions d'un canal de transmission) avec pour objectif de réduire la consommation d'énergie dans certaines conditions. Tout d'abord, la relation entre la puissance de bruit de quantification et le taux d'erreur binaire du système en fonction du bruit au récepteur est établie pour une chaîne de transmission QPSK. Ce résultat est appliqué dans la technique d'accès multiple par répartition de codes en séquence directe (DS-CDMA). Parmi plusieurs systèmes de télécommunications utilisant la technique DS-CDMA, nous montrons comment adapter dynamiquement la précision de calcul d'un récepteur 3G WCDMA. La conversion en virgule fixe nécessite un algorithme d'optimisation combinatoire pour l'optimisation des largeurs des opérateurs sous une contrainte de précision. La deuxième axe de ces travaux de thèse concerne l'étude d'algorithmes d'optimisation adaptés au problème de l'optimisation des largeurs de données. Nous proposons de nouveaux algorithmes pour les problèmes à une seule contrainte ou à une suite des contraintes correspondant à différents niveaux de précision pour les systèmes auto-adaptatifs. Le résultat des algorithmes génétiques multi-objectifs, sous forme d'une frontière de Pareto, permet d'obtenir la largeur correspondant à chaque niveau du bruit de quantification. Une version améliorée des algorithmes génétiques combinée avec l'élitisme et la recherche tabou est proposée. En plus, nous proposons d'appliquer GRASP, un algorithme de recherche locale stochastique permettant de trouver le résultat dans un temps plus faible en comparaison avec les algorithmes génétiques.
30
Otaño, Aramendi Nerea. "Réduction du coût de calcul pour la simulation du comportement mécanique de câbles". Thesis, Université Paris-Saclay (ComUE), 2016. http://www.theses.fr/2016SACLC061.
Abstract (sommario):
Le travail présenté dans ce mémoire s'intéresse à la simulation du comportement mécanique de câbles d'ascenseurs. Le but de ce travail est d'élaborer une méthode permettant de simuler le comportement mécanique de tels câbles à moindre coût, et avec une précision suffisante.Dans un premier temps, différentes méthodes permettant de modéliser ou de simuler le comportement de ces câbles ont été comparées, et leurs avantages et inconvénients ont été analysés. Les résultats de modèles analytiques et de simulations éléments finis ont été comparés avec des données expérimentales. Les modèles analytiques considérés dans ce travail présentent un coût de calcul bien moins élevé que les modèles éléments finis, mais n'offrent pas une précision suffisante dans leurs résultats pour simuler le comportement de câbles d'ascenseurs. L'approche éléments finis a été retenue pour cette raison comme la plus adaptée pour simuler ce genre de câbles. Les coûts de calcul liés à cette approche sont cependant très élevés, et demandent la mise en oeuvre de méthodes particulières en vue de les réduire.Afin de réduire les temps de calculs, trois types de méthodes ont été considérées : les méthodes d'homogénéisation, les méta-modèles, et les techniques de réduction de modèle. L'approche de réduction de modèle a été retenue comme la plus appropriée et a été implémentée dans le code de simulation par éléments finis Multifil. Des résultats avec une bonne précision ont été obtenus en utilisant cette méthode, mais les coûts des simulations initiales sur le modèle complet afin d'obtenir un ensemble de solutions permettant de construire une base réduite apparaissent trop élevés dès qu'il s'agit de traiter des câbles de longueurs importantes. Pour remédier à ce problème, une méthode de réduction par tronçon a été formulée et implémentée. Cette méthode tire parti de la structure périodique du câble et permet d'identifier a base de réduction seulement sur un motif périodique élémentaire. Cette base est ensuite utilisée pour représenter la solution sur l'ensemble d'un câble composé de plusieurs tronçons.Le coût des multiplications matricielles nécessaires pour transformer le système linéaire du problème initial, en système linéaire réduit reste cependant trop important pour obtenir un gain significatif, en particulier dans le contexte de la résolution d'un problème non-linéaire. Pour pallier cette difficulté, une technique supplémentaire, appelée ``Discrete Empirical Interpolation Method'' (DEIM), a été mise en oeuvre avec succès, et a permis d'obtenir au final une réduction du coût de calcul d'un facteur 4The work presented in this dissertation is focused on the simulation of the mechanical behaviour of lift's wire ropes. The aim of the work is to elaborate a method to simulate the mechanical behaviour of such wire ropes with low computational cost and sufficient accuracy.First of all, several methods to model or simulate wire ropes have been compared and their weak and strong points have been highlighted. Analytical and finite element methods have been compared with experimental tests. It was concluded that analytical methods considered in this work have a lower computational cost than finite element methods, but the results obtained using them are not accurate enough to simulate lift wire ropes. Therefore, finite element methods have been considered as the most appropriate to simulate these wire ropes. However, their computational cost is high so some methods to reduce it must be applied.In order to reduce the computational time, three type of methods have been considered: homogenization, metamodeling and model order reduction. Model order reduction technique was chosen as the most adequate method and it was implemented in the wire rope finite element simulation program Multifil. Accurate results have been obtained, however the computational cost needed by initial simulations to get the snapshots used to define a reduce basis was too high for long wire ropes. To solve this problem, a sectionwise reduction method was proposed and implemented. This formulation takes advantage of the periodic structure of wire ropes: the reduced basis is identified only on a reference elementary section and used for all repetitive sections of a multi-section wire rope. The computational cost induced by the multiplication of matrices in order to transform the linear system of the initial problem into the linear system of the reduced problem was shown to remain too high, particularly in the context of the solving of a non-linear problem, to allow the global computational time to be significantly decreased using the proposed techniques. To overcome this difficulty, an additional technique, namely the so-called Discrete Empirical Interpolation Method (DEIM) was successfully implemented and tested, allowing a time reduction factor of 4 to be obtained
31
Ceroi, Stéphan. "Ordres et géométrie plane : application au nombre de sauts". Montpellier 2, 2000. http://www.theses.fr/2000MON20114.
Abstract (sommario):
P etant un ordre, le nombre de sauts de p est le nombre minimum de comparaisons qu'il faut rajouter a p pour obtenir un ordre total. Ce parametre intervient dans certains problemes d'ordonnancement de taches, et son calcul est np-difficile en general. Par contre la complexite sur les ordres de dimension 2 (i. E. Les ordres qui sont l'intersection de 2 ordres totaux) est inconnue. Cette these presente des arguments de geometrie du plan qui permettent de resoudre certaines questions reliees au probleme du nombre de sauts sur les ordres de dimension 2. Nous montrons que ce probleme est equivalent au probleme suivant : etant donne un ensemble de rectangles ponderes du plan, quel est le poids maximum d'un sous-ensemble constitue de rectangles 2 a 2 disjoints ? grace a cette interpretation, nous montrons que le calcul est polynomial sur la classe des ordres de hauteur h (meme dans la version ponderee ou on attribue un poids a chaque couverture), alors que cette derniere version ponderee est np-difficile si la hauteur est quelconque, montrant que la complexite du probleme est dependante de la hauteur de l'ordre. D'autre part, nous nous interessons aux 2 ordres totaux dont un ordre p de dimension 2 est l'intersection, vis a vis du nombre de sauts, montrant entre autre que la somme des nombres de sauts produits par l'un et l'autre de ces ordres totaux ne depend que du graphe d'incomparabilite de p. Par ailleurs, nous nous interessons a certains problemes de representation des ordres de dimension 2 et 3. En montrant que les ordres de dimension 3 sont exactement les ordres d'inclusion de triangles isothetiques dans le plan, nous prouvons que la complexite de set packing passe de polynomial a np-complet lorsque le biparti d'adjacence sous-jacent passe de la dimension 2 a la dimension 3.
32
Leroy, Julien. "Contribution à la résolution de la conjecture S-adique". Amiens, 2012. http://www.theses.fr/2012AMIE0101.
Abstract (sommario):
Cette thèse concerne la Conjecture S-adique qui stipule l'existence d'une version forte de S-adicité dans les suites qui serait équivalente à une complexité p (en facteurs) sous-linéaire. Une suite w à valeurs dans un alphabet fini A est dite S-adique si S est un ensemble de morphismes permettant de dé-substituer indéfiniment w. Sans condition supplémentaire, la complexité en facteurs d'une suite S-adique peut être arbitrairement grande. Cependant, de nombreuses familles de suites bien connues admettent des développements S-adiques avec S de cardinalité finie et sont également de complexité sous-linéaire. La conjecture S-adique apparaît alors naturellement comme une tentative de relier ces deux notions. Dans cette thèse, nous étudions en détails une méthode constructive basée sur les graphes de Rauzy et qui produit un développement S-adique des suites uniformément récurrentes de complexité sous-linéaire. Par ce biais, nous exhibons certaines propriétés nécessaires (mais pas suffisantes) du développement obtenu. Dans le cas particulier des suites uniformément récurrentes dont la différence première de complexité est majorée par deux, cette méthode est poussée à l'extrême, si bien que les conditions nécessaires obtenues en deviennent suffisantesThis thesis is about the S-adic conjecture which supposes the existence of a stronger notion of S-adicity that would be equivalent to having a sub-linear factor complexity. A sequence w over a finite alphabet A is said to be S-adic if S is a set of morphisms that allows to indefinitely de-substitute w. Without additional condition, the factor complexity of an S-adic sequence might be arbitrarily large. However, many well-known families of sequences have a sub-linear complexity and admit some S-adic expansions with a finite set S. The S-adic conjecture is therefore a natural attempt to link these two notions. In this thesis, we study in detail a method based on Rauzy graphs that provides an S-adic expansion of uniformly recurrent sequences with a sub-linear complexity. By this way we are able to determine some necessary (but not sufficient) conditions of these expansions. In the particular case of uniformly recurrent sequences with first difference of complexity bounded by two, the method is studied with even much more details, which makes the necessary conditions sufficient
33
Simoncini, David. "Sélection topologique dans les algorithmes évolutionnaires cellulaires : étude du compromis exploration exploitation". Nice, 2009. http://www.theses.fr/2009NICE4079.
Abstract (sommario):
Les algorithmes évolutionnaires sont des méthodes d'optimisation approchées manipulant une population de solutions. Leur fonctionnement s'inspire de la théorie de l'évolution de Darwin. L'application combinée d'opérateurs stochastiques et de mécanismes de sélection permet de renouveler la population en explorant l'espace de recherche et en exploitant la qualité des solutions déjà découvertes. La vitesse de convergence d'un algorithme évolutionnaire dépend de sa capacité à générer de nouvelles solutions performantes en se dirigeant vers des régions prometteuses de l'espace de recherche et de celles des solutions à survivre en fonction de leur qualité déterminée par la pression de sélection. Celle-ci permet de contrôler le compromis entre exploration et exploitation et d'éviter une convergence prématurée vers un optimum local. Les algorithmes évolutionnaires cellulaires introduisent une notion de voisinage géographique en structurant spatialement les solutions sur une grille. Cela permet d'ajouter un niveau topologique entre les niveaux phénotypique et génotypique. Dans ce contexte, nous définissons de nouvelles méthodes de sélection permettant à l'aide d'un paramètre continu et borné de contrôler la topologie et ainsi d'obtenir des dynamiques plus complexes. Plutôt que de restreindre les solutions à évoluer sur une grille régulière où chaque cellule est indifférenciée, nous proposons d'enrichir la topologie en introduisant des notions d'anisotropie et de localité. Nous étudions l'influence de la sélection topologique sur la préservation de la diversité génotypique. Les expériences menées sur deux classes de problèmes NP-complets montrent que la prise en compte d'un point de vue topologique permet d'obtenir un bon équilibre entre exploration et exploitation. Dans le but d'étudier la dynamique de recherche et en particulier d'analyser l'efficacité des compromis observés, nous définissons un modèle théorique basé sur la notion d'équilibres ponctués. Enfin, nous proposons des algorithmes de contrôle utilisant la sélection topologique afin de réguler dynamiquement la pression de sélection et ainsi de gérer le rapport entre phases d'exploration et d'exploitation sans connaissance a priori sur les problèmes étudiésEvolutionary algorithms are stochastic optimization methods manipulating a population of solutions. Their behaviour is inspired by Darwin's theory of evolution. The combined application of stochastic operators and selection mechanisms allow renewing the population by exploring the search space and exploiting the already found solutions. The convergence speed of an evolutionary algorithm relies on its ability to generate efficient solutions by leading the search toward promising regions of the search space, and the ability of solutions to survive according to their fitness defined by the selective pressure. The latter allows dealing with the exploration / exploitation trade-off and prevents the algorithm from converging prematurely toward a local optimum. Evolutionary cellular algorithms introduce a notion of geographical neighborhood by embedding the solution on a grid. This adds a topological level between the phenotypical and genotypical ones. In this context, we define new selection methods that allow controlling the topology and obtain complex dynamics thanks to a single continuous and bounded parameter. Instead of restricting solutions to evolve on a uniform grid, we propose to enhance the topology with notions of anisotropy and locality. We study the influence of the topological selection on the preservation of genotypic diversity. Experiences made on two classes of NP-complete problems show that taking into account the topological level leads to a fine equilibrium between exploration and exploitation. In order to study the search dynamic and especially to analyze the efficiency of the observed trade-offs, we define a model based on the notion of punctuated equilibria. Finally, we propose adaptive algorithms in the intent of dynamically controlling the selective pressure and thus dealing with the relation between exploration and exploitation phases without any knowledge on the studied problems
34
Afif, Mohammed. "Approches algorithmiques pour la résolution de certains problèmes NP-Complets". Paris 9, 1999. https://portail.bu.dauphine.fr/fileviewer/index.php?doc=1999PA090026.
Abstract (sommario):
L'objet de cette thèse est de présenter de nouvelles approches de résolution de certains problèmes combinatoires de la classe NP-Complet. Ces approches sont représentées par des algorithmes efficaces basés sur des métaphores physiques ou sur des modèles qui se caractérisent par des solutions non combinatoires. Dans la première partie nous définirons les problèmes combinatoires traites, et les modèles mathématiques que nous avons défini pour les étudier. Nous avons aussi, pour chacun des problèmes étudiés, défini les algorithmes classiques de résolution optimale et approchée, ainsi que les méthodes et les heuristiques proposées. Dans la seconde partie, nous avons illustré par une étude expérimentale et comparative, les performances ainsi que les lacunes des différents algorithmes présentés
35
Monnot, Jérôme. "Familles d'instances critiques et approximation polynomiale". Paris 9, 1998. https://portail.bu.dauphine.fr/fileviewer/index.php?doc=1998PA090028.
Abstract (sommario):
S'il est facile de concevoir que le comportement d'un algorithme approché diffère suivant l'instance à traiter, quel est réellement le rôle de ces instances dans l'approximation d'un problème ? Quelles influences ont-elles sur le comportement d'un algorithme ? A quel niveau ? Pour répondre à ces questions, nous avons construit un formalisme permettant d'ordonner les instances selon le niveau d'information qu'elles procurent. Ce formalisme nous conduit à définir des familles d'instances dépendant soit d'un problème soit d'un triplet (problème, algorithme approche, mesure d'approximation). La classification en familles critiques et fortement critiques permet de comprendre, d'analyser et d'éventuellement améliorer le comportement de cet algorithme au pire des cas. Afin de construire de telles familles, nous proposons divers outils et méthodes basés sur la notion centrale de plus mauvaise instance. D'un point de vue opérationnel, concernant la mesure différentielle, nous avons spécifié certaines formes d'instances empêchant la très bonne approximabilité et caractérise les classes ptas() et fptas(). Ensuite, nous avons obtenu, grâce aux familles critiques, des résultats d'approximation positifs et négatifs sur une classe de problèmes de partitionnement définis par certaines propriétés logiques. Les problèmes de la coloration, du bin-packing, de l'ensemble dominant de Steiner en font partie. Précisons toutefois qu'une étude spécifique de ces problèmes met en évidence des différences d'approximation : la coloration appartient à apx()ptas() tandis que le bin-packing appartient à ptas()isfptas(). Enfin, par les mêmes procédés, nous obtenons de bons résultats d'approximation pour les problèmes connexes à celui de l'arbre de Steiner
36
Grunspan, Cyril. "Théorie de Toda discrète et espaces homogènes quantiques". Palaiseau, École polytechnique, 2000. http://www.theses.fr/2000EPXX0042.
37
Turuani, Mathieu. "Sécurité des protocoles cryptographiques : décidabilité et complexité". Nancy 1, 2003. http://www.theses.fr/2003NAN10223.
38
Letombe, Florian. "De la validité des formules booléennes quantifiées : étude de complexité et exploitation de classes traitables au sein d'un prouveur QBF". Artois, 2005. http://www.theses.fr/2005ARTO0407.
Abstract (sommario):
Cette thèse est centrée sur le problème QBF de décision de la validité des formules booléennes quantifiées : étant donnée une formule de la forme Σ = ∀y1 Ǝx1. . . ∀yn Ǝxn. ø où ø est une formule propositionnelle construite sur {x1, y1,. . . , xn, yn} (la matrice de Σ), il s’agit de déterminer si pour toute affectation d’une valeur de vérité à y1 dans ø, il existe une affectation d’une valeur de vérité à x1 dans ø,. . . , pour toute affectation d’une valeur de vérité à yn dans ø, il existe une affectation d’une valeur de vérité à xn dans ø qui rend ø valide. Le problème QBF est calculatoirement difficile (PSPACE-complet). Il importe donc de mettre en évidence des cas particuliers où sa résolution pratique est envisageable. Dans cette thèse, nous avons considéré des restrictions de QBF portant sur la matrice des instances. Notre objectif principal était double : (1) identifier la complexité de QBF pour des restrictions non considérées jusqu’ici et (2) explorer dans quelle mesure les classes polynomiales pour QBF peuvent être exploitées au sein d’un prouveur QBF général afin d’améliorer son efficacité. Concernant le premier point, nous avons montré que QBF restreint aux fragments cibles pour la compilation de « connaissances » étudiés dans (Darwiche & Marquis 2002), qui sont traitables pour SAT, reste PSPACE-complet et donc intraitable en pratique. Nous avons également mis en évidence le lien étroit qui existe entre notre étude et le problème de compilabilité de QBF. Concernant le second point, nous avons décrit une nouvelle heuristique de branchement Δ visant à promouvoir la génération de formules Horn renommables quantifiées durant le parcours de l’arbre de recherche effectué par une procédure de type Q-DPLL pour QBF. Les résultats expérimentaux présentés montrent qu’en pratique, hormis notre prouveur Qbfl, les prouveurs QBF actuels ne sont pas capables de résoudre facilement les instances Horn quantifiées ou Horn renommables quantifiées ; ceci suffit à justifier l’intérêt de l’approche suivie. Les résultats obtenus montrent également que, muni de l’heuristique Δ, Qbfl améliore significativement ses performances sur certains types d’instances, même s’il obtient des résultats moyens en général, comparé aux autres prouveurs QBF actuelsThis thesis is centered on QBF, the validity problem for quantified Boolean formulae: given a formula of the form Σ = ∀y1 Ǝx1. . . ∀yn Ǝxn. ø where ø is a propositional formula built on {x1, y1,. . . , xn, yn} (the matrix of Σ), is it the case that for each assignment of a truth value to y1 in ø, there exists an assignment of a truth value to x1 in ø,. . . , for each assignment of a truth value to yn in ø, there exists an assignment of a truth value to xn in ø that makes ø valid ? Since QBF is computationally hard (PSPACE-complete), it is important to point out some specific cases for which the practical solving of QBF could be achieved. In this thesis, we have considered some restrictions of QBF based on the matrices of instances. Our main purpose was (1) to identify the complexity of QBF for some restrictions not considered so far and (2) to explore how to take advantage of polynomial classes for QBF within a general QBF solver in order to increase its efficiency. As to the first point, we have shown that QBF, when restricted to the target fragments for knowledge compilation studied in (Darwiche & Marquis 2002), remain typically PSPACE-complete. We have shown a close connexion between this study and the compilability issue for QBF. As to the second point, we have presented a new branching heuristics Δ which aims at promoting the generation of quantified renamable Horn formulae into the search-tree developed by a Q-DPLL procedure for QBF. We have obtained experimental results showing that, in practice, state-of-the-art QBF solvers, except our solver Qbfl, are unable to solve quantified Horn instances or quantified renamable Horn instances of medium size. This observation is sufficient to show the interest of our approach. Our experiments have also shown the heuristics Δ to improve the efficiency of Qbfl, even if this solver does not appear as one of the best QBF solvers at this time
39
Aubert, Clément. "Logique linéaire et classes de complexité sous-polynominales". Paris 13, 2013. https://theses.hal.science/tel-00957653.
Abstract (sommario):
This research in Theoretical Computer Science extends the gateways between Linear Logic and Complexity Theory by introducing two innovative models of computation. It focuses on sub-polynomial classes of complexity : AC and NC —the classes of efficiently parallelizable problems— and L and NL —the deterministic and non-deterministic classes of problems efficiently solvable with low resources on space. Linear Logic is used through its Proof Net resentation to mimic with efficiency the parallel computation of Boolean Circuits, including but not restricted to their constant-depth variants. In a second moment, we investigate how operators on a von Neumann algebra can be used to model computation, thanks to the method provided by the Geometry of Interaction, a subtle reconstruction of Linear Logic. This characterization of computation in logarithmic space with matrices can naturally be understood as a wander on simple structures using pointers, parsing them without modifying them. We make this intuition formal by introducing Non Deterministic Pointer Machines and relating them to other well-known pointer-like-machines. We obtain by doing so new implicit characterizations of sub-polynomial classes of complexityCette recherche en informatique théorique construit de nouveaux ponts entre logique linéaire et théorie de la complexité. Elle propose deux modèles de machines abstraites qui permettent de capturer de nouvelles classes de complexité avec la logique linéaire, les classes des problèmes efficacement parallélisables (NC et AC) et celle des problèmes solutionnables avec peu d’espace, dans ses versions déterministes et non-déterministes (L et NL). La représentation des preuves de la logique linéaire comme réseaux de preuves est employée pour représenter efficacement le calcul parallèle des circuits booléens, y compris à profondeur constante. La seconde étude s’inspire de la géométrie de l’interaction, une délicate reconstruction de la logique linéaire à l’aide d’opérateurs d’une algèbre de von Neumann. Nous détaillons comment l’interaction d’opérateurs représentant des entiers et d’opérateurs représentant des programmes peut être reconnue nilpotente en espace logarithmique. Nous montrons ensuite comment leur itération représente un calcul effectué par des machines à pointeurs que nous définissons et que nous rattachons à d’autres modèles plus classiques. Ces deux études permettent de capturer de façon implicite de nouvelles classes de complexité, en dessous du temps polynomial
40
Rossi, Fabrice. "Calcul de différentielles dans les réseaux de neurones généralisés : algorithmes, complexité, implantation logicielle et applications". Paris 9, 1996. https://portail.bu.dauphine.fr/fileviewer/index.php?doc=1996PA090043.
Abstract (sommario):
Les réseaux de neurones sont des outils de régression non linéaire asymptotiquement plus parcimonieux que les b-splines ou les polynômes. Certains types de réseaux comme les perceptrons multicouches et réseaux de radial basis functions ont été étudiés de façon assez complète. D'autres types, comme les réseaux d'ondelettes ou les neurones d'ordre supérieur, restent plus délicats à mettre en œuvre. Nous développons un cadre mathématique général permettant une unification de tous les types de réseaux de neurones dans une unique définition. Nous montrons que les réseaux classiques sont tous des cas particuliers de la définition proposée. Ce cadre mathématique permet d'analyser les réseaux de neurones sans se préoccuper de la fonction implantée par chaque neurone, mais en préservant la structure du réseau étudié. Nous introduisons ainsi des algorithmes de calcul des différentielles du premier et second ordre portant sur les fonctions calculables par ce modèle. Nous étudions les complexités exactes de ces algorithmes et montrons que la rétropropagation (étendue au cas général) n'est pas nécessairement la méthode la plus efficace. Nous décrivons enfin une implantation orientée objet des réseaux généralisés proposés. Nous illustrons ainsi l'utilisation pratique du cadre mathématique proposé. Il permet une unification des algorithmes d'apprentissage sous la forme de méthodes de minimisation de fonctions. Il permet aussi d'obtenir un logiciel très facilement extensible et résout ainsi un des problèmes liés à la simulation neuronale dans un environnement de recherche : l'implantation dans un simulateur d'un nouveau type de réseau de neuronesNeural networks are non linear régression tools. They are asymptotically more efficient than B-spline or polynomial régression. Classical types of neural network hâve been studied rather completely. This is the case for instance for Multi-Layer Perceptron and Radial Basis Function based networks. Less common neural network types such as wavelet network or high order neurons hâve not been studied as completely as classical ones. VVe introduce a general mathematical framework that allows to uniformly describe every neural network type. We show that classic neural networks are particular cases of our general model. The proposed mathematical framework allows the analysis of neural networks without précisé knowledge of functions implemented by each neuron while keeping the architecture of the network build into the mathematical définition. We introduce this way algorithms that allow to compute first and second dérivatives of different functions computed with this model. We study the time complexities of these algorithms and show that the back-propagation algorithm (extended to our general définition) is not always the fastest algorithm. We finally describe an object-oriented implémentation of our generalized neural networks. We thus illustrate a practical use of our framework. It allows to unify neural network training methods, which are considered as function minimization algorithms. It allows also to obtain an easy to extend neural network simulator which solves one of the important problems of neural network simulation in a research framework : the implémentation of a new neural network type in an already existing simulator
41
Ayad, Ali. "Complexité de la résolution des systèmes algébriques paramétriques". Phd thesis, Université Rennes 1, 2006. http://tel.archives-ouvertes.fr/tel-00127383.
Abstract (sommario):
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.
42
Maire, Sylvain. "Réduction de variance pour l'intégration numérique et pour le calcul critique en transport neutronique". Toulon, 2001. http://www.theses.fr/2001TOUL0013.
Abstract (sommario):
Cette thèse est consacrée aux méthodes de Monte-Carlo et plus particulièrement à la réduction de variance. Dans la première partie, on étudie un algorithme probabiliste, fondée sur une utilisation itérative de la méthode des variables de contrôle, permettant le calcul d'approximations quadratiques. Son utilisation en dimension un pour les fonctions régulières à l'aide de la base de Fourier après périodisation, des bases de polynômes orthogonaux de Legendre et Tchebychef, fournit des estimateurs ayant un ordre de convergence accru pour l'intégration Monte-Carlo. On l'étend ensuite au cadre multidimensionne! par un choix judicieux des fonctions de base, permettant d'atténuer l'effet dimensionnel. La validation numérique est effectuée sur de nombreux exemples et applications. La deuxième partie est consacrée à l'étude du régime critique en transport neutronique. La méthode développée consiste à calculer numériquement la valeur propre principale de l'opérateur de transport neutronique en combi¬nant le développement asymptotique de la solution du problâme d'évolution associé avec le calcul par une méthode de Monte-Carlo de son interprétation probabiliste. Différentes techniques de réduction de varîance sont mises en place dans l'étude de nombreux modèles homogènes et inhomogènes. Une interprétation probabiliste de la valeur propre principale est donnée pour un modèle homogène particulierThis work deals with Monte Carlo methods and is especially devoted to variance-reduction. In the first part, we study a probabilistic algorithm, based on iterated control variates, wich enables the computation of mean-square ap-. Proximations. We obtain Monte Carlo estimators with increased convergence rate for monodimensional regular functions using it with periodized Fourier basis, Legendre and Tchebychef polynomial basis. It is then extended to the multidimensional case in trying to attenuate the dimensional effect by making a good choice of the basis functions. Various numerical examples and applications are studied. The second part deals with criticality in neutron transport theory. We develop a numerical method to compute the principal eigenvalue of the neutron transport operator by combining the Monte-Carlo computation of the solution of the relative Cauchy problem and its formal eigenfunction expansion. Various variance-reduction methods are tested on both homogeneous and inhomo-geaeous models. The stochastic representation of the principal eigenvalue is obtained for a peculiar homogeneous model
43
Thomasse, Rémy. "Analyse de complexité d'enveloppes convexes aléatoires". Thesis, Nice, 2015. http://www.theses.fr/2015NICE4116/document.
Abstract (sommario):
Dans cette thèse, nous donnons de nouveaux résultats sur la taille moyenne d’enveloppes convexes de points choisis dans un convexe. Cette taille est connue lorsque les points sont choisis uniformément (et indépendamment) dans un polytope convexe, ou un convexe suffisamment «lisse» ; ou encore lorsque les points sont choisis indépendamment selon une loi normale centrée. Dans la première partie de cette thèse, nous développons une technique nous permettant de donner de nouveaux résultats lorsque les points sont choisis arbitrairement dans un convexe, puis «bruités» par une perturbation aléatoire. Ce type d’analyse, appelée analyse lissée, a initialement été développée par Spielman et Teng dans leur étude de l’algorithme du simplexe. Pour un ensemble de points arbitraires dans une boule, nous obtenons une borne inférieure et une borne supérieure de cette complexité lissée dans le cas de perturbations uniformes dans une boule en dimension arbitraire, ainsi que dans le cas de perturbations gaussiennes en dimension 2. La taille de l'enveloppe convexe de points choisis uniformément dans un convexe, peut avoir un comportement logarithmique si ce convexe est un polytope ou polynomial s’il est lisse. Nous construisons un convexe produisant un comportement oscillant entre ces deux extrêmes. Dans la dernière partie, nous présentons un algorithme pour engendrer efficacement une enveloppe convexe aléatoire de points choisis uniformément et indépendamment dans un disque sans avoir à engendrer explicitement tous les points. Il a été implémenté en C++ et intégré dans la bibliothèque CGALIn this thesis, we give some new results about the average size of convex hulls made of points chosen in a convex body. This size is known when the points are chosen uniformly (and independently) in a convex polytope or in a "smooth" enough convex body. This average size is also known if the points are independently chosen according to a centered Gaussian distribution. In the first part of this thesis, we introduce a technique that will give new results when the points are chosen arbitrarily in a convex body, and then noised by some random perturbations. This kind of analysis, called smoothed analysis, has been initially developed by Spielman and Teng in their study of the simplex algorithm. For an arbitrary set of point in a ball, we obtain a lower and a upper bound for this smoothed complexity, in the case of uniform perturbation in a ball (in arbitrary dimension) and in the case of Gaussian perturbations in dimension 2. The asymptotic behavior of the expected size of the convex hull of uniformly random points in a convex body is polynomial for a "smooth" body and polylogarithmic for a polytope. In the second part, we construct a convex body so that the expected size of the convex hull of points uniformly chosen in that body oscillates between these two behaviors when the number of points increases. In the last part, we present an algorithm to generate efficiently a random convex hull made of points chosen uniformly and independently in a disk. We also compute its average time and space complexity. This algorithm can generate a random convex hull without explicitly generating all the points. It has been implemented in C++ and integrated in the CGAL library
44
Osswald, Christophe. "Classification, analyse de la similitude et hypergraphes". Paris, EHESS, 2003. http://www.theses.fr/2003EHES0079.
Abstract (sommario):
L'un des objectifs de la classification est d'expliciter les relations entre éléments et classes. Les modèles usuels sont les hiérarchies, les pyramides et les systèmes de classes arborés, classiques en biologie. Ils nécessitent de faire le choix d'une structure pour approcher les données, et la plupart mènent à des problèmes NP-difficiles. Dans le cadre de l'analyse de la similitude (Flament 'et al. ',1962-1981) nous cherchons un 'graphe de rigidité' le plus petit possible, tel que les classes d'un système donné en soient des classes connexes. Il existe plusieurs méthodes pour engendrer un système de classes à partir d'une dissimilarité : cliques maximales, boules, 2-boules, réalisations (Brucker, 2003). Le problème est NP-difficile dans le cas général et pour les trois premières méthodes ; il existe un algorithme en O(n4) pour les réalisations. Nous identifions les 'hypercycles', dont un graphe de rigidité est un cycle, en O(n4) opérations et analysons les dissimilarités circulaires, dont les classes forment un hypercycle, en relation avec le modèle de Hubert 'et al. ' (1998). Nous appliquons ces méthodes à des données issues de la psychologie de la mémoire, de l'analyse de données textuelles et de la génétiqueA classical purpose of clustering is to make explicit the relationship between elements, and between the clusters, 'i. E. ' sets of elements. Partitions and hierarchies are often used. Clusters of a pyramid are parts of some path; trees and arboreal set systems are common in biology. Most of these models require an 'a priori' structure choice and lead to NP-hard problems. Within similarity analysis (Flament 'et al. ', 1962-1981), we search a smallest 'rigidity graph' of a given hypergraph, such that hyperedges are connected classes of the graph. Many methods are classical to generate a set system from a dissimilarity : maximal cliques, balls, 2-balls, realizations (Brucker, 2003). We prove our problem is NP-hard in general and with the first three methods; there is an algorithm in O(n4) operations for realisations. We identify hypercycles - admitting a cycle as graph of rigidity - O(n4) operations and study circular dissimilarities, whose clusters form a hypercycle, in relation with the model of Hubert 'et al. ' (1998). We apply these methods to memory psychology, text analysis and genetic data
45
Dang, Minh Dung. "Autour des primitifs quantiques pour le calcul sécurisé à deux parties". Paris, ENST, 2008. http://pastel.archives-ouvertes.fr/pastel-00005098.
Abstract (sommario):
Dans cette thèse, nous sommes intéressés à la construction inconditionnelle du calcul sécurisé à deux parties dont Oblivious Transfer (OT) et Bit Commitment (BC) sont les primitifs fondamentaux. D'une part, mes oeuvres sont inspirées du framework de Crépeau et al. Pour la construction de OT à partir des canaux bruités. Le principe est de concevoir, à partir des canaux bruités, un modèle d'effacement intermédiaire qui est un variant de OT. Nous avons contribué à ce framework en proposant un modèle intermédiaire plus générique, le Binary Symmetric Multi-Error-Rate Channel, qui peut également être construit à partir des canaux bruités. Avec ce modèle intermédiaire, nous pouvons construire le protocole de OT de manière plus efficace. En outre, nous exposons quelques études de cas sur l'émulation des modèles bruités par un codage quantique nonorthogonal qui utilise deux états non-orthogonaux pour coder deux valeurs du bit classique. D'autre part, nous révisons le modèle quantique des protocoles quantiques à deux parties, couvrant les calculs et les communications classiques. Nous constatons que, dans le modèle général, un canal classique est inévitablement macroscopique et la decoherence est si forte que l'information quantique n'est pas acceptée d'être transférée sur ce canal. Ainsi, le modèle quantique des protocoles à deux parties consiste en trois parties, y compris l'environnement du canal. Avec cette fidèle interprétation, nous réaffirmons les théorèmes No-go de Mayers et Lo & Chau sur l'impossibilité de OT, BC quantiques. En addion, nous pouvons étendre ces résultats négatifs aux protocoles utilisant certains oracles quantiques, comme Coin-FlippingIn this thesis, we are interested in the theory of unconditional secure two-party computations of which Oblivious Transfer (OT) and Bit Commitment (BC) are the central primitives. On one hand, my works are inspired from Crépeau's et al. 's framework of building of OT protocol from noisy communication channels. The principle of this framework is to conceive, from noisy channels, an intermediate erasure model which is a variant of OT. We contributed to this framework by proposing a more general intermediate model, the Binary Symmetric Multi-Error-Rate Channel, which also can be built from noisy channels. With this intermediate model, we can build OT protocol from the noisy channels more effectively. In addition, we expose some case studies on emulating noisy models by a quantum nonorthogonal coding (QNOC) scheme which uses two non-orthogonal pure states for encoding two values of the classical bit. On the other hand, we revise the quantum model for general two-party protocols concerning classical and quantum computations and communications. We state that in the general model, a classical channel is inevitably macroscopic and its decoherence is so strong that quantum information is not accepted to be transfered on it. Thus, the quantum model for two-party protocols becomes three-party, including an environment of the channel. Indeed, with the faithful interpretation of general quantum two-party protocols in this three-party model, we reaffirm the no-go theorems of Mayers and Lo & Chau on the impossibilities of quantum OT, BC. In addion, we can go further to apply these negative results to protocols using some quantum trusted oracles, such as Coin-Flipping
46
Martin, Sébastien. "Analyse structurelle des systèmes algébro-différentiels conditionnels : complexité, modèles et polyèdres". Paris 9, 2011. https://basepub.dauphine.psl.eu/handle/123456789/9724.
Abstract (sommario):
Les systèmes algébro-différentiels permettent de modéliser des systèmes physiques complexes comme les circuits électriques et les mouvements dynamiques. Ils sont souvent de grande taille et difficiles à résoudre. L'analyse structurelle des systèmes algébro-différentiels permet de vérifier si un tel système ne pourra pas être résolu par des méthodes numériques. Elle consiste à résoudre un problème sous-jacent de couplage dans les graphes. Dans cette thèse, nous étudions ce problème dans le cas des systèmes algébro-différentiels conditionnels. Nous montrons que ce problème est équivalent au problème du sous-graphe sans couplage parfait. Nous montrons que ce dernier est NP-difficile. Nous proposons une formulation en termes de graphes et deux formulations en nombres entiers pour ce problème. Nous étudions le polyèdre associé et décrivons plusieurs classes de contraintes valides. Nous donnons des conditions nécessaires et suffisantes pour que ces contraintes définissent des facettes. Nous discutons également d'algorithmes de séparation pour ces contraintes et en utilisant ces résultats, nous développons un algorithme de coupes et branchements. Nous étudions aussi une extension de ce problème pour les systèmes algébro-différentiels conditionnels imbriqués. Nous étendons la plupart des résultats précédents à ce cas. Nous identifions de nouvelles contraintes valides pour cette variante du problème. Dans une deuxième partie, nous nous intéressons au problème de parallélisation des systèmes algébro-différentiels. Ce problème se ramène au problème du séparateur. Nous proposons plusieurs formulations en nombres entiers du modèle et pour l'une d'entre elle, nous étudions le polyèdre associé. Nous proposons quelques résultats expérimentaux obtenus suite à cette étudeDifferential algebraic systems are used for modeling complex physical systems as electrical networks and dynamic movements. They are often large and difficult to solve. The structural analysis for differential algebraic systems permits to verify if these systems can not be solved with numerical methods. It consists to solve an underlying matching problem in graphs. In this thesis, we consider the structural analysis problem for differential algebraic systems with conditional equations. We show that the structural analysis problem for differential algebraic systems with conditional equations reduces to which we call the perfect matching free subgraph problem. We show the NP-completeness of this latter problem. We propose a formulation in terms of graphs and two integer programming formulations. We study the polytope associated to this problem and describe several classes of valid inequalities. We give necessary and sufficient conditions for these inequalities to be facet defining. We also discuss separation algorithms for these constraints. We develop a branch-and-cut algorithm based on these results. We also study an extension of this problem to differential algebraic systems with conditional embedded equations. We generalize the results obtained for the first variant and give new valid inequalities for this more general problem. In a second part, we study the parallelization problem for differential algebraic systems. This problem reduces to which is called the separator problem. We give several integer programming formulations, and for one of them we study the associated polytope. We give a few experimental results associated to this polyhedral study
47
Cervelle, Julien. "Complexité structurelle et algorithmique des pavages et des automates cellulaires". Aix-Marseille 1, 2002. https://hal.archives-ouvertes.fr/tel-01208375.
Abstract (sommario):
Ce travail de thèse étudie la complexité des pavages et des automates cellulaires. L'analyse débute par des considérations structurelles : la quasipériodicité des pavages. A tout ensemble de tuiles qui pave le plan, on associe une fonction de quasipériodicité qui quantifie sa complexité. Tout d'abord, on montre que toute fonction "raisonnable" peut être capturée par un ensemble de tuiles et qu'il existe des pavages dont la fonction de quasipériodicité croît plus rapidement que n'importe quelle fonction récursive. Ensuite, on démontre un théorème de Rice pour les pavages : l'ensemble des ensembles de tuiles qui admettent les mêmes pavages qu'un autre fixé est indécidable et récursivement énumérable. Enfin, on transpose notre résultat dans le contexte des automates cellulaires. La seconde partie de notre travail concerne l'étude des automates cellulaires sous l'angle des systèmes dynamiques, et plus particulièrement des automates chaotiques. Les définitions usuelles classifiant les automates chaotiques ne sont pas satisfaisantes. Pour palier ce problème, on utilise deux nouvelles topologies. La première est dite de Besicovitch, et permet de supprimer la prédominance du motif central lors de l'étude de l'évolution de l'automate. On apporte plusieurs résultats, les premiers indiquant que notre nouvel espace de travail est acceptable à l'étude des automates cellulaires, en tant que systèmes dynamiques ; les seconds montrent que la notion de chaos subsiste, grâce à la définition de sensibilité aux conditions initiales, mais que les classes plus chaotiques sont vides. La seconde topologie employée est définie à l'aide de la complexité algorithmique. Le but de cette approche est d'avoir une distance qui traduit la facilité à calculer un élément à l'aide de l'autre. Nos résultats complètent les précédents. Ils attestent de manière formelle que les automates cellulaires ne peuvent pas modifier continûment l'information contenue dans une configuration, et surtout qu'ils sont incapables d'en créer
48
Férée, Hugo. "Complexité d'ordre supérieur et analyse récursive". Thesis, Université de Lorraine, 2014. http://www.theses.fr/2014LORR0173/document.
Abstract (sommario):
Alors que la complexité des fonctions d'ordre 1 est bien définie et étudiée, il n'existe pas de notion satisfaisante à tout ordre. Une telle théorie existe déjà à l'ordre 2 et permet de définir une classe analogue aux fonctions calculables en temps polynomial usuelles. Cela est tout particulièrement intéressant dans le domaine de l'analyse récursive où l'on peut représenter, entre autres, les nombres et les fonctions réelles par des fonctions d'ordre 1. On peut alors remarquer un lien fort entre calculabilité et continuité, et aussi rapprocher la complexité avec certaines propriétés analytiques, ce que nous illustrons dans le cas des opérateurs réels. Nous prouvons cependant que, du point de vue de la complexité, les fonctions d'ordre 1 ne permettent pas de représenter fidèlement certains espaces mathématiques. Ce résultat appuie tout particulièrement la nécessité d'une théorie de la complexité d'ordre supérieur. Nous développons alors un modèle de calcul basé sur la sémantique des jeux, où l'application de deux fonctions est représentée par la confrontation de deux stratégies dans un jeu. En définissant la taille de telles stratégies, nous pouvons déduire une notion robuste et pertinente de complexité pour ces stratégies et donc pour les fonctions d'ordre supérieur. Nous définissons aussi une classe de fonctions calculables en temps polynomial qui paraît être un bon candidat pour définir une classe de complexité raisonnable à tout ordreWhile first order complexity is well defined and studied, higher order lacks a satisfactory notion of complexity. Such a theory already exists at order 2 and provides a complexity class analogue to usual polynomial time computable functions. This is already especially interesting in the domain of computable analysis, where real numbers or real functions for example can be represented by first order functions. In particular, there is a clear link between computability and continuity, and we also illustrate in the case of real operators that complexity can be related to some analytical properties. However, we prove that, from a complexity point of view, some mathematical spaces can not be faithfully represented by order 1 functions and require higher order ones. This result underlines that there is a need to develop a notion of complexity at higher types which will be, in particular but not only, useful to computable analysis. We have developed a computational model for higher type sequential computations based on a game semantics approach, where the application of two functions is represented by the game opposing two strategies. By defining the size of such strategies, we are able to define a robust and meaningful notion of complexity at all types, together with a class of polynomial time computable higher order functionals which seems to be a good candidate for a class of feasible functionals at higher types
49
Cegarra, Julien. "La gestion de la complexité dans la planification : le cas de l'ordonnancement". Paris 8, 2004. http://www.theses.fr/2004PA082447.
Abstract (sommario):
Cette recherche, menée dans un cadre pluridisciplinaire associant Psychologie Cognitive Ergonomique et Recherche Opérationnelle, porte sur les activités de planification cognitive. Au sein de ces activités, l’ordonnancement constitue une problématique importante notamment de par la complexité des problèmes de terrain. Pour mieux comprendre les aspects humains de l’ordonnancement, trois études ont été menées. Tout d’abord, il s’agissait d’identifier la nature de l’expertise par l’étude des activités de planification en fonction de l’expertise des opérateurs. Les résultats ont alors conduit à s’intéresser, dans une deuxième étude, au rôle des exigences de la tâche (comme le niveau de complexité) sur les stratégies des opérateurs. Enfin, l’influence de la représentation externe sur la complexité des problèmes a été abordée dans une troisième partie. Finalement, la combinaison de ces différentes études a conduit à la proposition de recommandations pour la conception d’interfacesThis research relates to cognitive planning activities. It was conducted in a multi-disciplinary field associating Cognitive Ergonomics and Operational Research. Within these activities, scheduling constitutes an interesting problem in particular due to the complexity of field problems. In order to better understand human aspects of scheduling, three studies were undertaken. The first experiment was done to identify the nature of scheduling expertise by the study of novice and experts schedulers. Results led to a second experiment investigating the effect of task demands (e. G. Complexity level) on operators’ strategies. Then, the influence of external representation on problems complexity was studied in a third experiment. Finally, the combination of these various studies led to the proposal of hints for interfaces design
50
Poteaux, Adrien. "Calcul de développements de Puiseux et application au calcul du groupe de monodromie d'une courbe algébrique plane". Limoges, 2008. https://aurore.unilim.fr/theses/nxfile/default/b6d84d62-1bad-4a2f-9405-b23ed771029e/blobholder:0/2008LIMO4032.pdf.
Abstract (sommario):
Dans cette thèse, nous présentons un nouvel algorithme symbolique-numérique pour calculer une approximation numérique des développements de Puiseux au-dessus des points critiques, que nous utilisons pour calculer le groupe de monodromie d'une courbe algébrique plane. Essentiellement, l'algorithme de calcul de développements de Puiseux utilise des calculs modulo un nombre premier p bien choisi pour obtenir des informations exactes sur les séries de Puiseux. Ensuite, nous décrivons comment calculer une approximation numérique de ces séries de Puiseux à partir de ces informations exactes. Nous étudions également la complexité de la partie symbolique de notre algorithme. Enfin, nous proposons un algorithme symbolique-numérique pour calculer le groupe de monodromie d'une courbe algébrique plane qui utilise ces développements de PuiseuxWe present a new symbolic-numeric algorithm to compute numerical approximations of Puiseux expansions above critical points. We use this new algorithm to compute monodromy groups of plane algebraic curves. In essence, we compute numerical approximations of Puiseux expansions in the following way: computations modulo a well chosen prime number p are used to obtain the exact information required to guide floating point computations. We also give complexity bounds for the symbolic part of our algorithm. Then, we propose a new strategy to compute monodromy groups of plane algebraic curves using this numerical approximations of Puiseux expansions