Dissertations / Theses on the topic 'Sciences de la complexité'
To see the other types of publications on this topic, follow the link: Sciences de la complexité.
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Sciences de la complexité.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Eynaud, Yoan. "Contribution à la gestion de la complexité des modèles en sciences de l'environnement." Thesis, Aix-Marseille, 2012. http://www.theses.fr/2012AIXM4109.
Abstract:
La modélisation en écologie est aujourd'hui une pratique scientifique de premier plan. Portée par l'avancement technologique, les modèles utilisés en sciences de l'environnement présentent une complexité grandissante. La complexification des modèles est une nécessité pour une variété d'études, mais elle peut être une source d'incompréhension, voire d'erreurs. Savoir gérer son implémentation apparaît donc nécessaire. Fort de ce constat, deux approches complémentaires se sont distinguées et furent étudiées dans ce travail de thèse. D'une part, il est possible de gérer la complexité a priori, en contraignant directement les hypothèses de construction et le formalisme du modèle par l'utilisation d'un cadre théorique. Une illustration de l'utilisation d'un schéma théorique, la théorie des Budgets Dynamiques d'Énergie, présente comment une description précise de l'effet des ultraviolets fut adjointe à un modèle de l'endosymbiose corallienne. Cette étude met en lumière leur possible rôle dans le blanchiment des coraux scléractiniaires. La gestion de la complexité pouvant aussi s'opérer a posteriori, c'est à dire une fois l'étape de construction passée. Ainsi, une méthodologie d'analyse statistique des sorties de modèles ayant pour but de permettre leur simplification fut établie. À titre d'exemple, cette méthode a été appliquée sur un modèle à micro-échelle de l'écosystème mésopélagique. Ne plus avoir la possibilité d'entreprendre une approche analytique de son modèle n'est donc pas une fatalité pour qui veut maitriser son outil, car une multitude d'approches permettent d'obtenir des informations toutes aussi intéressantesEcological modelling is nowadays a leading topic. the models used in environmental science turn to be more and more complex. Driven by technological advancement, the models used in environmental sciences are increasingly complex. The complexity of models is a need for a variety of studies, but it can also be a source of misunderstanding, or even errors. How to manage its implementation is therefore necessary. With this in mind, two complementary approaches have been studied in this thesis. On the one hand, it is possible to manage the complexity textit a priori, by directly constraining the construction assumptions and formalism of the model using a theo- retical framework. An illustration of the use of a theoretical framework, the theory of Dynamic Energy Budgets, shows how an accurate description of the effect of ultraviolet was added to a model of scleractinian corals. This study enlightened their possible role in coral bleaching events. Managing complexity can also be carried out textit a posteriori, ie once the construc- tion phase is done. Thus, a simplification methodology using a statistical analysis of the model outputs was established . As an example, this method was applied on a micro- scale model of the mesopelagic ecosystem. Eventually, not being able of pursuing an analytical approach of the model is not inevitable for those who want to still mastering their model, it exists a multitude of tool who brings equally interesting informations
2
Bonfante, Guillaume. "Complexité implicite des calculs : interprétation de programmes." Habilitation à diriger des recherches, Institut National Polytechnique de Lorraine - INPL, 2011. http://tel.archives-ouvertes.fr/tel-00656766.
Abstract:
L'étude que nous proposons s'inscrit dans le cadre de la complexité implicite des calculs. Selon Daniel Leivant, il s'agit de donner des caractérisations de la complexité sans faire de référence explicite à un modèle de calcul. Nous montrons que les interprétations de programmes sont un bon outil d'analyse dans ce contexte. Les aspects théoriques et pratiques sont abordés.
3
Hadjiat, Malika. "Problèmes de tension sur un graphe : algorithmes et complexité." Aix-Marseille 2, 1996. http://www.theses.fr/1996AIX22061.
Abstract:
Un grand nombre d'applications pratiques concernants les reseaux, tels que l'ordonnancement, peuvent etre modelises par un probleme de determination d'une tension de cout minimum (tcm) dans un graphe oriente. Ce probleme d'optimisation combinatoire, issu de la theorie des graphes et de la programmation lineaire, a ete relativement ignore par la litterature scientifique. L'objectif de cette these est d'entreprendre une etude algorithmique plus complete du probleme de la tcm, en developpant de nouveaux algorithmes de complexite pseudo-polynomiale, polynomiale et fortement polynomiale. Un autre probleme plus connu d'optimisation combinatoire sur les graphes est celui du flot de cout minimum (fcm). Les problemes de tcm et de fcm sont tres lies puisque nous prouvons qu'il existe entre eux une relation de dualite indirecte. Les algorithmes de tcm que nous proposons dans ce document sont des adaptations de methodes resolvant le probleme du fcm. En particulier, nous decrivons les versions primale et duale de la methode simplex, ainsi que l'applicatiion sur l'algorithme de mise a conformite de la technique polynomiale de mise a l'echelle des couts et celle des capacites. Nous proposons aussi le premier algorithme fortement polynomial combinatoire qui determine directement une tcm. Cet algorithme, s'inspirant des idees recentes de goldberg et tarjan pour le flot, est base sur la saturation de cocycles residuels de couts moyens minimums. Une methode pour la recherche de tels cocycles est egalement donnee. D'autre part, nous montrons comment determiner une tension compatible, et s'il en existe une, comment calculer celle de valeur maximale sur un arc particulier du graphe. Enfin, nous nous interessons a l'etude de la complexite theorique de certain algorithmes classiques de tcm. En particulier, nous prouvons que la version tension de l'algorithme de mise a conformite est non polynomiale. En plus de l'analyse theorique de complexite des divers algorithmes de tcm, une etude empirique et comparative de leurs implementations est decrite dans ce rapport
4
Rosiello, Immacolata. "Méthodes de simulation, analyse de la complexité, utilisation de modèles, interdisciplinarité." Aix-Marseille 1, 2009. http://www.theses.fr/2009AIX10111.
Abstract:
L'objectif de cette thèse est une réflexion épistémologique sur le rôle et les limites de la simulation dans les sciences exactes et dans les sciences sociales. Dans les sciences exactes, la simulation est désormais entérinée comme une pratique scientifique courante, qui s'étale du simple calcul numérique jusqu'à se positionner en vraie source d'investigation et de fabrication de modèles. Plus critique est la position de la simulation dans les sciences sociales, surtout quand elle se décline en mathématisation et calcul des phénomènes humains et économiques et dans la validation conséquente de ses résultats. Nous verrons que le cadre paradigmatique qui à la fois fonde et justifie le recours à la simulation dans les sciences sociales est celui de la complexité. Le chapitre final essaie de tracer le parcours historique des différents aspects de la simulation en économie et finance, là où le recours à la modélisation est constant et lourd de conséquences.
5
Poreau, Brice. "Biologie et complexité : histoire et modèles du commensalisme." Phd thesis, Université Claude Bernard - Lyon I, 2014. http://tel.archives-ouvertes.fr/tel-01063917.
Abstract:
Le commensalisme est une association biologique au sein de laquelle le commensal obtient un avantage, alors que son hôte n'obtient ni avantage, ni désavantage. Ce type d'association est théorisé durant la seconde moitié du dix-neuvième siècle, notamment par Pierre-Joseph Van Beneden (1809-1894). Zoologiste belge, professeur à l'université de Louvain, il propose dans son ouvrage de 1875 intitulé Les commensaux et les parasites dans le règne animal, 264 exemples d'associations qu'il classe parmi le commensalisme. Ses travaux ont un retentissement majeur dans l'univers des zoologistes de son époque. Le concept de commensalisme perdure alors jusqu'au vingt-et-unième siècle et interroge sur les notions d'individualité, d'individuation et d'association. Notre étude porte non seulement sur le développement de ce concept au cours du dix-neuvième siècle, que nous démontrons par de nombreux documents inédits issus des archives de Pierre-Joseph Van Beneden, mais aussi sur la pérennité du concept jusqu'à nos jours. Le commensalisme est interprété comme un " marqueur " de l'émergence de nouvelles sciences du vivant : la microbiologie et l'écologie. Plus qu'un concept scientifique, le commensalisme apparaît alors comme un concept illustrant la complexité du vivant
6
Ka, Ahmad Khoureich. "Méthodes à faible complexité algorithmique pour l'analyse d'ECG." Phd thesis, Rennes 1, 2012. https://ecm.univ-rennes1.fr/nuxeo/site/esupversions/96446b82-5669-4387-bb4f-bda6a14bfe0a.
Abstract:
This thesis focused on the analysis of electrocardiograms in view of developing new effective methods of classification of arrhythmias (a diagnostic tool) and automatic localisation of abnormal beats (monitoring tool) in real time in an ECG signal. The ECG signals are preprocessed and the extracted beats are compressed and then analysed using wavelet transform. The proposed classification method exploits specificities of the patient by doing a contextuel clustering of beats and using a database of annotated heart beats. The method uses also a similarity function to compare two given beats. The localisation method also uses the wavelet decomposition but operates only on a portion of available data (set of parsimony) to automatically detect in real time abnormal heart beats with the aid of a mask function. Both methods were tested on ECG signals from MIT-BIH arrhythmia database and good results have been obtainedCette thèse a porté sur l'analyse des électrocardiogrammes en vu de développer de nouvelles méthodes efficaces de classification des arythmies (un outil de diagnostique) et de localisation automatique des battements anormaux en temps réel dans un signal ECG (un outil de surveillance). Les signaux ECG sont prétraités et les battements extraits sont compressés puis analysés à l'aide de la décomposition en ondellettes. La méthode de classification proposée exploite les spécificités du patient en faisant un regroupement contextuel des battements et en utilisant une base de données de battements cardiaques annotés. La méthode utilise également une fonction de similarité pour comparer deux battements donnés. La méthode de localisation exploite aussi la décomposition en ondelettes mais se base sur une partie des données disponibles (set of parsimony) pour détecter automatiquement et temps réel à l'aide d'une fonction masque les battements cardiaques anormaux contenus dans le signal ECG. Les deux méthodes ont été testées sur les signaux électrocardiogrammes du MIT-BIH arrhythmia database et des bons résultats ont été obtenus
7
Ka, Ahmad Khoureich. "Méthodes à faible complexité algorithmique pour l'analyse d'ECG." Phd thesis, Université Rennes 1, 2012. http://tel.archives-ouvertes.fr/tel-00816445.
Abstract:
Cette thèse a porté sur l'analyse des électrocardiogrammes en vu de développer de nouvelles méthodes efficaces de classification des arythmies (un outil de diagnostique) et de localisation automatique des battements anormaux en temps réel dans un signal ECG (un outil de surveillance). Les signaux ECG sont prétraités et les battements extraits sont compressés puis analysés à l'aide de la décomposition en ondellettes. La méthode de classification proposée exploite les spécificités du patient en faisant un regroupement contextuel des battements et en utilisant une base de données de battements cardiaques annotés. La méthode utilise également une fonction de similarité pour comparer deux battements donnés. La méthode de localisation exploite aussi la décomposition en ondelettes mais se base sur une partie des données disponibles (set of parsimony) pour détecter automatiquement et temps réel à l'aide d'une fonction masque les battements cardiaques anormaux contenus dans le signal ECG. Les deux méthodes ont été testées sur les signaux électrocardiogrammes du MIT-BIH arrhythmia database et des bons résultats ont été obtenus.
8
Madet, Antoine. "Complexité Implicite de Lambda-Calculs Concurrents." Phd thesis, Université Paris-Diderot - Paris VII, 2012. http://tel.archives-ouvertes.fr/tel-00794977.
Abstract:
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.
9
Wells, Jennifer. "Complexité et changement climatique : une étude épistémologique des théories de la complexité transdisciplinaires et leur apport aux phénomènes socio-écologiques." Thesis, Paris 4, 2009. http://www.theses.fr/2009PA040136/document.
Abstract:
Cette thèse propose une analyse épistémologique des théories de la complexité, une évaluation de leur portée générale et de leur utilité dans des domaines particuliers, et la mise au jour de leur contribution décisive à la question centrale du changement climatique. L’objectif est de cerner la nature de la complexité à travers tout l’éventail des disciplines, car les théories de la complexité ne cessent de s’éteindre et la liste des bénéfices qu’on leur attribue de s’allonger. L’étude de cas du changement climatique est riche, y sont impliqués de nombreux systèmes complexes d’importance décisive pour le genre humain, parmi lesquels l’agriculture, l’énergie, l’eau et l’économie. Le présent travail propose d’abord une définition de la complexité généralisée, comprise comme cadre général de la pensée fondé sur six grandes catégories. Il procède ensuite à l’analyse à travers ce cadre, des dimensions scientifiques, politiques et éthiques du changement climatique. Notre point de départ est constitué par un examen attentif du trois corpus importants : le rapport du GEIC « Climate Change 2007, » « le Millennium Ecosystem Assessment, » et l’éthique du changement climatique. Il s’avère que la mise en œuvre des théories de la complexité est nécessaire pour mesurer de manière rigoureuse la portée non seulement des aspects multiples des différents systèmes complexes impliqués, mais aussi de l’ensemble dans toutes sa signification polyvalente. En s’interrogeant sur le rôle et l’utilité des théories de la complexité dans des domaines et à des échelles multiples, nous mettons en lumière une série de principes-clés sur la nature et l’usage de ces théoriesThis dissertation presents an epistemological analysis of complexity theories, an evaluation of their contribution, both generally and to specific domains, and a demonstration of their important contribution to climate change. The objective is to provide a description of complexity theories across the whole range of disciplines, as complexity theories continue to expand and the list of their proposed benefits continue to grow. The case study of climate change is rich, as it touches on a number of complex systems of primary significance to humanity, such as agriculture, energy, water, and the economy. The present work proposes first a definition of generalized complexity, comprised of a general framework of the field based upon six major categories. It proceeds to analyze, in light of this framework, the scientific, ethical and political dimensions of climate change. Our point of departure consists in a thorough examination of three important bodies of literature: the IPCC report “Climate Change 2007,” the “Millennium Ecosystem Assessment,” and the ethics of climate change. The dissertation shows that the use of complexity theories is necessary in order to measure in a rigorous manner the contribution, not only of the multiple aspects of different complex systems involved, but also of the framework as an ensemble, with its polyvalent signification. By examining the role and the utility of complexity theories in multiple fields at multiple scales, we reveal a series of key principles regarding the nature and usage of these theories
10
Loubet, Lilian. "Les maires confrontés à l'apprentissage de l'intercommunalité : l'exemple de l'agglomération toulousaine." Phd thesis, Université Toulouse le Mirail - Toulouse II, 2011. http://tel.archives-ouvertes.fr/tel-00638938.
Abstract:
Le développement de l'intercommunalité donne lieu à des recompositions territoriales et gouvernementales majeures. Les élus se confrontent alors à l'exercice complexe de la coopération et à la définition d'un projet territorial. Il s'agira d'étudier la coopération intercommunale au regard des apprentissages (techniques, politiques et territoriaux) opérés par les maires. Ce propos est illustré par l'étude de l'agglomération toulousaine qui, fragmentée en trois communautés d'agglomérations ou urbaine, donne à voir des territoires plus ou moins avancés dans le mouvement d'intégration communautaire. A cette occasion, plus de 80 maires, ainsi que des responsables techniques, ont été interrogés.
11
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:
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.
12
Zeitoun, Xavier. "Complexité des dynamiques de jeux." Phd thesis, Université Paris Sud - Paris XI, 2013. http://tel.archives-ouvertes.fr/tel-00870614.
Abstract:
La théorie de la complexité permet de classifier les problèmes en fonction de leur difficulté. Le cadre classique dans lequel elle s'applique est celui d'un algorithme centralisé qui dispose de toutes les informations. Avec l'essor des réseaux et des architectures décentralisées, l'algorithmique distribuée a été etudiee. Dans un grand nombre de problèmes, en optimisation et en économie, les décisions et les calculs sont effectu'es par des agents indépendants qui suivent des objectifs diff'erents dont la réalisation dépend des décisions des autres agents. La théorie des jeux est un cadre naturel pour analyser les solutions de tels problèmes. Elle propose des concepts de stabilité, le plus classique étant l'équilibre de Nash.Une manière naturelle de calculer de telles solutions est de " faire réagir " les agents ; si un agent voit quelles sont les décisions des autres joueurs ou plus généralement un " état du jeu ", il peut décider de changer sa décision pour atteindre son objectif faisant ainsi 'évoluer l'etat du jeu. On dit que ces algorithmes sont des " dynamiques " On sait que certaines dynamiques convergent vers un concept de solution. On s'intéresse 'a la vitesse de convergence des dynamiques. Certains concepts de solutions sont même complets pour certaines classes de complexité ce qui rend peu vraisemblable l'existence de dynamiques simples qui convergent rapidement vers ces solutions. On a utilisé alors trois approches pour obtenir une convergence rapide : améliorer la dynamique (en utilisant par exemple des bits aléatoires), restreindre la structure du problème, et rechercher une solution approchée.Sur les jeux de congestion, on a étendu les résultats de convergence rapide vers un équilibre de Nash approche aux jeux négatifs. Cependant, on a montré que sur les jeux sans contrainte de signe, calculer un équilibre de Nash approche est PLS-complet. Sur les jeux d'appariement, on a étudie la vitesse de dynamiques concurrentes lorsque les joueurs ont une information partielle paramétrée par un reseau social. En particulier, on a améliore des dynamiques naturelles afin qu'elles atteignent un équilibre enO(log(n)) tours (avec n le nombre de joueurs).
13
Massart, David. "La gestion de la complexité des schémas conceptuels à base d'objets." Doctoral thesis, Universite Libre de Bruxelles, 2001. http://hdl.handle.net/2013/ULB-DIPOT:oai:dipot.ulb.ac.be:2013/211495.
14
Briquel, Irénée. "Complexité de problèmes de comptage, d'évaluation et de recherche de racines de polynômes." Phd thesis, Ecole normale supérieure de lyon - ENS LYON, 2011. http://tel.archives-ouvertes.fr/tel-00677977.
Abstract:
Dans cette thèse, nous cherchons à comparer la complexité booléenne classique et la complexité algébrique, en étudiant des problèmes sur les polynômes. Nous considérons les modèles de calcul algébriques de Valiant et de Blum, Shub et Smale (BSS). Pour étudier les classes de complexité algébriques, il est naturel de partir des résultats et des questions ouvertes dans le cas booléen, et de regarder ce qu'il en est dans le contexte algébrique. La comparaison des résultats obtenus dans ces deux domaines permet ainsi d'enrichir notre compréhension des deux théories. La première partie suit cette approche. En considérant un polynôme canoniquement associé à toute formule booléenne, nous obtenons un lien entre les questions de complexité booléenne sur la formule booléenne et les questions de complexité algébrique sur le polynôme. Nous avons étudié la complexité du calcul de ce polynôme dans le modèle de Valiant en fonction de la complexité de la formule booléenne, et avons obtenu des analogues algébriques à certains résultats booléens. Nous avons aussi pu utiliser des méthodes algébriques pour améliorer certains résultats booléens, en particulier de meilleures réductions de comptage. Une autre motivation aux modèles de calcul algébriques est d'offrir un cadre pour l'analyse d'algorithmes continus. La seconde partie suit cette approche. Nous sommes partis d'algorithmes nouveaux pour la recherche de zéros approchés d'un système de n polynômes complexes à n inconnues. Jusqu'à présent il s'agissait d'algorithmes pour le modèle BSS. Nous avons étudié l'implémentabilité de ces algorithmes sur un ordinateur booléen et proposons un algorithme booléen.
15
Cheikh-Alili, Fahima. "Composition de services: algorithmes et complexité." Phd thesis, Université Paul Sabatier - Toulouse III, 2009. http://tel.archives-ouvertes.fr/tel-00459114.
Abstract:
Le problème de la combinaison des services, autrement appelé problème de la composition, constitue le foyer d'une intense activité de recherche. Composer les services entre eux, c'est entrelacer leurs séquences d'actions, de manière à obtenir des séquences qui satisfassent les exigences des clients. Le problème de la composition de services est difficile à résoudre en général. Dans cette thèse nous considérons des services qui peuvent à la fois exécuter des actions de communications ainsi que des actions internes. De plus, des conditions peuvent être exigées et des effets peuvent être appliqués sur les transitions. Formellement, les services sont représentés par des automates communicants conditionnels. Nous définissons, pour ce modèle, le problème de la composition et nous étudions sa décidabilité pour différentes relations d'équivalence et de préordre à savoir : l'inclusion de traces, l'équivalence de traces, la simulation et la bisimulation. Suite aux résultats de décidabilité obtenus, nous proposons trois variantes pour le modèle initial. Pour chacune d'elles, nous définissions le problème de la composition et nous étudions sa complexité pour les relations citées ci-dessus.
16
Blondin, Michael. "Algorithmique et complexité des systèmes à compteurs." Thèse, Université Paris-Saclay (ComUE), 2016. http://hdl.handle.net/1866/16025.
Abstract:
Réalisé en cotutelle avec l'École normale supérieure de Cachan – Université Paris-SaclayL'un des aspects fondamentaux des systèmes informatiques modernes, et en particulier des systèmes critiques, est la possibilité d'exécuter plusieurs processus, partageant des ressources communes, de façon simultanée. De par leur nature concurrentielle, le bon fonctionnement de ces systèmes n'est assuré que lorsque leurs comportements ne dépendent pas d'un ordre d'exécution prédéterminé. En raison de cette caractéristique, il est particulièrement difficile de s'assurer qu'un système concurrent ne possède pas de faille. Dans cette thèse, nous étudions la vérification formelle, une approche algorithmique qui vise à automatiser la vérification du bon fonctionnement de systèmes concurrents en procédant par une abstraction vers des modèles mathématiques. Nous considérons deux de ces modèles, les réseaux de Petri et les systèmes d'addition de vecteurs, et les problèmes de vérification qui leur sont associés. Nous montrons que le problème d'accessibilité pour les systèmes d'addition de vecteurs (avec états) à deux compteurs est PSPACE-complet, c'est-à-dire complet pour la classe des problèmes solubles à l'aide d'une quantité polynomiale de mémoire. Nous établissons ainsi la complexité calculatoire précise de ce problème, répondant à une question demeurée ouverte depuis plus de trente ans. Nous proposons une nouvelle approche au problème de couverture pour les réseaux de Petri, basée sur un algorithme arrière guidé par une caractérisation logique de l'accessibilité dans les réseaux de Petri continus. Cette approche nous a permis de mettre au point un nouvel algorithme qui s'avère particulièrement efficace en pratique, tel que démontré par notre implémentation logicielle nommée QCover. Nous complétons ces résultats par une étude des systèmes de transitions bien structurés qui constituent une abstraction générale des systèmes d'addition de vecteurs et des réseaux de Petri. Nous considérons le cas des systèmes de transitions bien structurés à branchement infini, une classe qui inclut les réseaux de Petri possédant des arcs pouvant consommer ou produire un nombre arbitraire de jetons. Nous développons des outils mathématiques facilitant l'étude de ces systèmes et nous délimitons les frontières au-delà desquelles la décidabilité des problèmes de terminaison, de finitude, de maintenabilité et de couverture est perdue.
One fundamental aspect of computer systems, and in particular of critical systems, is the ability to run simultaneously many processes sharing resources. Such concurrent systems only work correctly when their behaviours are independent of any execution ordering. For this reason, it is particularly difficult to ensure the correctness of concurrent systems. In this thesis, we study formal verification, an algorithmic approach to the verification of concurrent systems based on mathematical modeling. We consider two of the most prominent models, Petri nets and vector addition systems, and their usual verification problems considered in the literature. We show that the reachability problem for vector addition systems (with states) restricted to two counters is PSPACE-complete, that is, it is complete for the class of problems solvable with a polynomial amount of memory. Hence, we establish the precise computational complexity of this problem, left open for more than thirty years. We develop a new approach to the coverability problem for Petri nets which is primarily based on applying forward coverability in continuous Petri nets as a pruning criterion inside a backward coverability framework. We demonstrate the effectiveness of our approach by implementing it in a tool named QCover. We complement these results with a study of well-structured transition systems which form a general abstraction of vector addition systems and Petri nets. We consider infinitely branching well-structured transition systems, a class that includes Petri nets with special transitions that may consume or produce arbitrarily many tokens. We develop mathematical tools in order to study these systems and we delineate the decidability frontier for the termination, boundedness, maintainability and coverability problems.
17
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:
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
18
Brochenin, Rémi. "Separation logic : expressiveness, complexity, temporal extension." Phd thesis, École normale supérieure de Cachan - ENS Cachan, 2013. http://tel.archives-ouvertes.fr/tel-00956587.
Abstract:
This thesis studies logics which express properties on programs. These logics were originally intended for the formal verification of programs with pointers. Overall, no automated verification method will be proved tractable here- rather, we give a new insight on separation logic. The complexity and decidability of some essential fragments of this logic for Hoare triples were not known before this work. Also, its combination with some other verification methods was little studied. Firstly, in this work we isolate the operator of separation logic which makes it undecidable. We describe the expressive power of this logic, comparing it to second-order logics. Secondly, we try to extend decidable subsets of separation logic with a temporal logic, and with the ability to describe data. This allows us to give boundaries to the use of separation logic. In particular, we give boundaries to the creation of decidable logics using this logic combined with a temporal logic or with the ability to describe data.
19
Lagniaux, Franck. "Epistémologie des savoirs enseignés, appropriés et utilisés en masso-kinésithérapie. : Contribution des résultats de recherche en sciences de l’éducation à la création d’une discipline en masso-kinésithérapie pour garantir la sécurité des patients et la qualité des soins." Thesis, Aix-Marseille, 2013. http://www.theses.fr/2013AIXM3019.
Abstract:
La profession de masseur-kinésithérapeute est située à un tournant de son histoire. Les réformes en cours conduisent à questionner les savoirs enseignés et les compétences des masseurs-kinésithérapeutes pour garantir la sécurité du patient et la qualité des soins. Il a été cherché à connaître l'origine des savoirs en masso-kinésithérapie et à évaluer les dispositifs d'enseignements et d'appropriation de ces savoirs par les étudiants et par les professionnels de santé. Les résultats des études montrent que les écarts aux compétences attendues sont liés aux modalités d'enseignement et d'évaluation utilisées par les formateurs en formation initiale et en formation continue. Il apparait que les modalités pédagogiques utilisées par les formateurs sont souvent basées sur un socle théorique behavioriste, un modèle d'évaluation contrôle et des pratiques dogmatiques qui empêchent l'accès à la pensée et à la pratique « complexe » du soin. La formation n'optimise pas le développement des compétences de réflexivité, d'esprit critique et d'innovation nécessaires à la relation humaine de soin et à la sécurité idéale du patient. Cette thèse montre l'intérêt majeur de réaliser les enseignements en masso-kinésithérapie par des enseignants-chercheurs qui pensent, écrivent, discourent, agissent différemment des formateurs en formation initiale et en formation continue. Il est donc indispensable pour la sécurité du patient et pour la qualité des soins que la formation initiale et la formation continue en masso-kinésithérapie soient réalisées dans le cadre d'une discipline en masso-kinésithérapie sous la responsabilité d'enseignants-chercheurs en masso-kinésithérapieThe profession of physiotherapist is located at a crossroads. Ongoing reforms lead to questioning the knowledge and skills taught physiotherapists to ensure patient safety and quality of care. It was sought to know the origin of knowledge in physiotherapy devices and evaluate teaching and ownership of such knowledge by students and health professionals. The study results show that the differences are expected to skills related to teaching methods and assessment used by teachers in initial training and continuing education. It appears that the teaching methods used by teachers are often based on a theoretical foundation behaviorist model evaluation and control practices that prevent access dogmatic thinking and practice "complex" care. Training of physiotherapists does not optimize the skills development of reflexivity, critical thinking and innovation needed in the human relationship of care and patient safety ideal. This thesis shows the major interest to carry out physiotherapy lessons by teachers and researchers who think, write, discoursing, act differently trainers in initial training and continuing education. It is therefore essential for patient safety and quality of care that initial training and continuing education in physiotherapy are carried out within the framework of a discipline physiotherapy under the responsibility of teachers researchers in physiotherapy
20
Alhadeff-Jones, Michel. "Education, critique et complexité : modèle et expérience de conception d'une approche multiréférentielle de la critique en Sciences de l'éducation." Paris 8, 2007. http://www.theses.fr/2007PA082800.
Abstract:
Partant du constat de la diversité des conceptions de la critique développées dans le champ académique (critiques philosophiques, sociales, littéraires, esthétiques, etc. ) cette thèse vise à problématiser les présupposés à partir desquels cette notion est envisagée et fragmentée en Sciences de l'éducation. A partir d'une posture constructiviste complexe et multiréférentielle, deux perspectives sont proposées. D'abord une macro-conceptualisation des notions associées à l'idée de critique et une modélisation de leur organisation sont proposées (téléologie, écologie, ontologie, fonctiologie et généalogie de la critique). La prise en considération de l'implication biographique du chercheur est ensuite envisagée pour rendre compte de certains des apprentissages nécessaires pour conjuguer des conceptions hétérogènes de la critique. La démarche adoptée permet ainsi de repenser conjointement le développement de référentiels critiques pluriels et le développement de ceux qui les produisentTaking as a starting point, the diversity of conceptions of critique developed in the academic field (in philosophy, sociology, literature, esthetics, etc. ) this thesis aims to reconsider the assumptions, which ground the understanding of this notion and the fragmentation of its study in Educational Sciences. Based on a constructivist, complex and multireferential epistemology, two perspectives are proposed. First, notions associated to the idea of critique are macro-conceptualized and organized through a model (teleology, ecology, ontology, fonctiology and genealogy of critique). Second, the biographical experience of the author is considered in order to make explicit the learning involved in the process of conjugating heterogeneous conceptions of critique. Such an approach provides a point of view allowing for a consideration of both the plural development of critical frames of thought and the development of those who participate in their production
21
Amitrano, David. "Complexité et Dynamique de l'endommagement et de la rupture,Mécanique, sismicité et invariance d'échelle des objets géologiques." Habilitation à diriger des recherches, Institut National Polytechnique de Lorraine - INPL, 2005. http://tel.archives-ouvertes.fr/tel-00173641.
Abstract:
Ce rapport rassemble des travaux portant sur l'endommagement et la rupture de roches à des échelles allant de celle de l'échantillon de laboratoire à la celle de la croûte terrestre en passant par celle des massifs rocheux (falaises et mines souterraines). On y associe l'analyse de données acquises au laboratoire et in situ , leur modélisation statistique et conceptuelle et la simulation numérique. Cette approche permet d'appréhender la complexité du comportement des roches selon différents aspects. L'accent est d'abord mis sur les propriétés statistiques et les invariances d'échelles des structures d'endommagement et des événements sismiques observés pendant le processus de déformation et de rupture. Un modèle numérique, basé sur une approche mésoscopique de l'endommagement, est présenté pour la simulation des processus de rupture à court et long terme. Il permet de reproduire de nombreuses observations expérimentales en leur donnant un cadre mécanique et en permettant ainsi de préciser leurs conditions d'apparition. Cette approche permet de considérer le processus de déformation et de rupture des roches comme un système complexe dont les propriétés macroscopiques émergent de l'interaction entre éléments de plus petite échelle ayant des propriétés simples. Le rôle des fluides dans ce processus est abordé par l'observation de la sismicité induite dans un massif rocheux fracturé et la simulation numérique du couplage roche fluides. Enfin un projet de recherche est développé sur le thème de l'endommagement à long terme et du couplage hydromécanique.
22
Lehoux-Fleury, Catherine. "L'influence de la reconnaissance sur la puissance d'agir : une approche biographique de personnes en situation de vulnérabilité." Thesis, Sorbonne Paris Cité, 2017. http://www.theses.fr/2017USPCD085/document.
Abstract:
Cette thèse étudie les mécanismes qui entrent en action dans le développement du pouvoir d’agir des individus en situation de vulnérabilité. À cette fin, nous nous appuyons d’une part sur des travaux en sociologie, philosophie, linguistique, et d’autre part sur notre expérience professionnelle dans le domaine du socio-éducatif (expérience retransmise et analysée ici via un récit d’investigation professionnelle), qui nous a permis de recueillir le témoignage de praticiens et de patients. L’auteure a ainsi procédé à douze échanges conversationnels avec des personnes en situation de handicap et de précarité. Ces entretiens sont retranscrits en annexe dans le tome II de cette thèse, tandis que le tome I procède à leur analyse avec les outils de la recherche biographique (socianalyse issue de l’analyse institutionnelle, étude via les catégories de Walter R. Heinz : des grilles d’analyses adaptées par Christine Delory-Momberger). Nous montrons aussi comment un tiers-lieu, un groupe d’échanges de pratiques, a été utilisé pour « déplier la complexité », au sens d’Edgar Morin, de l’approche biographique et de la question de l’implication du chercheur. Les intrications entre pouvoir d’agir et reconnaissance se retrouvent incarnées,au sein de cette recherche, par l’ensemble des personnes dont nous analysons les entretiens. À cette occasion, nous revisitons notamment les réflexions de Blaise Pascal,Hegel, Hannah Arendt, et les travaux de Paul Ricoeur, d’Axel Honneth et d’Emmanuel Renault. Cette démarche théorique s’est doublée de deux interactions concrètes avec la caisse primaire d’assurance maladie et avec un foyer d’accueil de personnes handicapées : nous illustrons comment, via la jonction de nos considérations universitaires et de notre sensibilité de praticienne dans le social, nous avons pu amener ces deux institutions à modifier leur approche, leur regardThis PhD thesis studies the mechanisms which play a role in the development of the empowerment of people in a vulnerable situation. To this end, we base our approach on previous works in sociology, philosophy, linguistics, and also on our professional experiences in the socio-educative area which allowed us to collect testimonies of social workers and their patients.The author thus proceeded to twelve conversational exchanges with people with disabilities or in situations of precariousness. These exchanges are transcribed into an annex, which constitutes the second volume of this thesis, while the first volume provides their analysis via biographical research tools (socianalysis stemming from institutional analysis, analysis via Walter R. Heinz's categories : an analysis framework adapted by Christine Delory-Momberger). What is more, our experience is summarized and analyzed here via a professional investigation narrative account. We also show how a « Third Place » (a group of exchanges of practices) was used in order to, to quote Edgar Morin, « unfold the complexity » of the biographical approach and of the issue of the researcher’s implication.The entanglements between empowerment and social recognition are here embodied, in this research, by each person we interviewed. On this occasion, we revisit in particular some thoughts by Blaise Pascal, Hegel, Hannah Arendt, and the works of Paul Ricoeur, Axel Honneth, and Emmanuel Renault. This theoretical approach is accompanied by two concrete interactions with the CPAM (the main institution of the French Health System) and a group home for people with disabilities : We illustrate how, via the junction of our university point of view and our sensibility as a social worker, we have been able to convince these two institutions to adapt their approach and their perspectives
23
Ilcinkas, David. "Complexité en espace de l'exploration de graphes." Phd thesis, Université Paris Sud - Paris XI, 2006. http://tel.archives-ouvertes.fr/tel-00412139.
Abstract:
Le problème de l'exploration de graphes trouve ses motivations en informatique fondamentale, notamment en logique et en théorie de la complexité. Il possède également de nombreuses applications en robotique. Quel que soit le cadre, la quantité de mémoire utilisée par l'entité mobile (robot, automate fini, etc.) effectuant l'exploration est un des paramètres importants à considérer. Dans cette thèse, nous étudions en détail la complexité en espace de l'exploration de graphes, à travers différents modèles. Nous distinguons principalement deux cadres d'études.Dans la première partie de la thèse, nous nous attachons à l'étude de l'exploration ``sans assistance'', c'est-à-dire lorsque l'entité mobile ne possède aucune information sur le graphe à explorer. Dans ce contexte, nous prouvons plusieurs bornes inférieures et supérieures sur la quantité de mémoire nécessaire et suffisante à l'entité pour explorer tous les graphes. En particulier, nous montrons que l'algorithme très simple de parcours en profondeur d'abord est optimal en mémoire lorsque la complexité est exprimée en fonction du degré et du diamètre.
Dans la seconde partie de la thèse, nous nous attachons à l'étude de l'exploration ``avec assistance''. Nous considérons un modèle supposant l'existence d'un oracle ayant une connaissance exhaustive du graphe exploré, et capable d'aider l'entité mobile en lui fournissant de l'information. Nous nous intéressons ainsi à la quantité minimale d'information (mesurée en nombre de bits) que l'oracle doit fournir à l'entité pour permettre l'exploration. Cette information peut être soit donnée directement à l'entité, soit codée sur les sommets du graphes.
24
Li, Vigni Guido Fabrizio. "Les systèmes complexes et la digitalisation des sciences. Histoire et sociologie des instituts de la complexité aux États-Unis et en France." Thesis, Paris Sciences et Lettres (ComUE), 2018. http://www.theses.fr/2018PSLEH134/document.
Abstract:
Comment penser la relation entre les cultures scientifiques contemporaines et l’usage grandissant de l’ordinateur dans la production des savoirs ? Cette thèse se propose de donner une réponse à telle question à partir de l’analyse historique et sociologique d’un domaine scientifique fondé par le Santa Fe Institute (SFI) dans les années 1980 aux États-Unis : les « sciences des systèmes complexes » (SSC). Rendues célèbres par des publications grand-public, les SSC se répandent au cours des années 1990 et 2000 en Europe et dans d’autres pays du monde. Ce travail propose une histoire de la fondation de ce domaine en se concentrant sur le SFI et sur le Réseau National des Systèmes Complexes français. Avec un regard sociologique ancré dans les Science & Technology Studies et dans le courant pragmatiste, elle pose ensuite des questions sur le statut socio-épistémique de ce domaine, sur les modalités de l’administration de la preuve dans des savoirs fondés sur la simulation numérique et enfin sur les engagements épistémiques tenus par les spécialistes des systèmes complexes. Le matériau empirique – composé d’environ 200 entretiens, plusieurs milliers de pages d’archives et quelques visites de laboratoire – nous amène non seulement à mieux connaître ce champ de recherche – dont le langage est très répandu aujourd’hui, mais peu étudié par les historiens et les sociologues ; il nous porte aussi à questionner trois opinions courantes dans la littérature humaniste à propos des sciences numériques. À savoir : 1) l’ordinateur produit des connaissances de plus en plus interdisciplinaires, 2) il donne vie à des savoirs de type nouveau qui nécessitent une toute autre épistémologie pour être pensés et 3) il fait inévitablement advenir des visions du monde néolibérales. Or, cette thèse déconstruit ces trois formes de déterminisme technologique concernant les effets de l’ordinateur sur les pratiques scientifiques, en montrant d’abord que, dans les sciences computationnelles, les rapports interdisciplinaires ne se font pas sans effort ni pacifiquement ou sur pied d’égalité ; ensuite que les chercheurs et les chercheuses des SSC mobilisent des formes d’administration de la preuve déjà mises au point dans d’autres disciplines ; et enfin que les engagements épistémiques des scientifiques peuvent prendre une forme proche de la vision (néo)libérale, mais aussi des formes qui s’en éloignent ou qui s’y opposentHow to think the relationship between contemporary scientific cultures and the rising usage of computer in the production of knowledge ? This thesis offers to give an answer to such a question, by analyzing historically and sociologically a scientific domain founded by the Santa Fe Institute (SFI) in the 1980s in the United States : the « complex systems sciences » (CSS). Become well-known thanks to popular books and articles, CSS have spread in Europe and in other countries of the world in the course of the 1990s and the 2000s. This work proposes a history of the foundation of this domain, by focussing on the SFI and on the French Complex Systems National Network. With a sociological take rooted into Science & Technology Studies and into pragmatism, it then asks some questions about the socio-epistemic status of such a domain, about the modalities of production of evidence as they are employed in the context of digital simulation and, finally, about the epistemic engagements hold by complexity specialists. Empirical material – composed by circa 200 interviews, several thousands archival pages and a small number of laboratory visits – allows us not only to improve knowledge about this field – whose language is very common today, but little studied by historians and sociologists ; it also brings us to question three current opinions in the human and social sciences literature regarding digital sciences. That is : 1) that the computer produces more and more interdisciplinary knowledge, 2) that it gives birth to a new type of knowledge which needs an entirely new epistemology to be well understood and 3) that it inevitably brings about neoliberal visions of the world. Now, this thesis deconstructs these three forms of technological determinism concerning the effects of computer on scientific practices, by showing firstly that, in digital sciences, the interdisciplinary collaborations are not made without any effort and in a symetrical and pacific way ; secondly, that CSS’ researchers mobilize a kind of evidence production techniques which are well known in other disciplines ; and, thirdly, that scientists’ epistemic engagements can take (neo)liberal forms, but also other forms that depart from neoliberalism or that stand against it
25
Crozier, Sophie. "Le pari éthique de la complexité : Action médicale dans le champ des accidents vasculaires cérébraux graves." Phd thesis, Université Paris Sud - Paris XI, 2012. http://tel.archives-ouvertes.fr/tel-00815733.
Abstract:
L'accident vasculaire cérébral, est une pathologie aigüe et grave, qui peut conduire au décès rapide du patient ou à un handicap neurologique sévère, moteur et/ou cognitif. Dans les situations les plus sévères, l'action médicale amène à envisager des limitations ou arrêt de certains traitements si le pronostic s'avère " catastrophique ", signifiant le plus souvent le risque d'un handicap " inacceptable ".L'action médicale dans ces situations est particulièrement complexe. Elle pose la question de la finalité de l'acte médical au regard de la qualité de vie future du patient, qui suppose l'estimation délicate de la valeur de la vie, prédiction par essence incertaine. Mais si le pronostic tient une place centrale dans cette action, d'autres facteurs jouent également un rôle déterminant, comme celui du contexte. Ce travail de thèse propose une exploration des notions de pronostic et de " proportionnalité des soins " et une approche éthique reposant sur la prise en compte de la complexité et la délibération aristotélicienne.
26
Robin, Nelly. "Migrations, observatoire et droit. Complexité du système migratoire ouest-africain. Migrants et normes juridiques." Habilitation à diriger des recherches, Université de Poitiers, 2014. http://tel.archives-ouvertes.fr/tel-01071279.
Abstract:
Le volume scientifique d'habilitation à diriger des recherches présenté par Nelly Robin vise à offrir une synthèse de ses travaux et des positionnements qui les ont orientés depuis son recrutement à l'ORSTOM en 1992. Migrations, observatoire et droit, tel est le titre général proposé pour cet essai. À partir d'analyses inédites, l'auteur réinterroge les différents moments de son parcours scientifique, centré sur l'Afrique de l'Ouest et marqué par un glissement inattendu, de la géographie, et plus largement des sciences sociales, vers l'univers judiciaire. Une synthèse régionale des migrations internationales en Afrique de l'Ouest sur cinquante ans, de 1960 à 2010, introduit l'analyse ; elle est portée par trois ambitions : celle d'une approche historique des mouvements migratoires afin d'apprécier le rôle des logiques "traditionnelles" sur l'ordre régional actuel, d'une réflexion en terme de systèmes sur l'organisation des échanges migratoires, leurs nouvelles configurations et leur ouverture extrarégionale et, enfin, d'une interrogation sur l'intégration régionale qui dévoile toute la complexité du jeu de recompositions spatiales des migrations internationales. Nelly Robin aborde ensuite l'Observatoire des migrations internationales au Sénégal, la manière dont il a été fabriqué et la qualité des données produites. La réflexion est axée tout à la fois sur la question de la production de statistiques publiques par l'administration et sur l'usage et l'analyse critique que peut en faire la recherche. Il s'agit de convoquer la statistique administrative du sud pour comprendre le processus d'externalisation du contrôle des frontières de l'UE et ses incidences sur la gestion concertée des flux par les États membres de la CEDEAO comme sur l'organisation des réseaux de traite des êtres humains et de trafic illicite de migrants. L'analyse est enrichie par une réflexion sur les parcours migratoires des mineurs, du Sahel aux rives sud de la Méditerranée. Il s'agit de rendre compte des évolutions des savoir-migrer et des routes empruntées, de reconstituer et d'étudier les systèmes d'alliances entre les acteurs (États, migrants, groupes criminels) et les relations de pouvoirs qui les lient ou les opposent sur les territoires parcourus. Travailler sur la parole du migrant à partir des récits de vie permet aussi de décrire les tensions entre les normes sociales (individuelles ou collectives) et les normes juridiques établies par les États. C'est en analysant dans l'acte individuel du migrant la part de ce qui relève d'une ressource ou d'une contrainte juridique que l'auteur entend révéler ce qui dans cet acte est conditionné par les politiques de contrôle des migrations. Le volume s'achève sur une réflexion d'ouverture beaucoup plus que de conclusion dans laquelle on dépasse un certain nombre de catégories d'analyse habituelles en géographie pour s'interroger sur la place des sciences juridiques dans l'étude des migrations internationales. Si les itérations entre le statisticien et le thématicien sont communes en recherche, celles entre le magistrat, le praticien du droit, et le géographe sont plus rares ; elles ont été remarquables dans le cadre de l'Observatoire des migrations internationales au Sénégal et trouvent leur accomplissement dans cette proposition de dialogue avec le droit.
27
Gavoille, Cyril. "Complexité mémoire du routage dans les réseaux distribués." Lyon, École normale supérieure (sciences), 1996. http://www.theses.fr/1996ENSL0015.
Abstract:
Au plus bas niveau des communications, le routage consiste a decider localement de la route des messages transitant par les nuds intermediaires d'un reseau distribue de processeurs dans un ordinateur parallele, ou, plus generalement, dans un reseau distribue d'ordinateurs. Nous etudions les caracteristiques locales du routeur (coprocesseur effectuant le routage) par rapport a la globalite du reseau communiquant. Precisemment, nous mesurons la quantite minimale d'information necessaire par chacun des routeurs pour assurer des communications rapides sur n'importe quel type de reseau
28
Brandão, Eduardo. "Complexity Methods in Physics-Guided Machine Learning." Electronic Thesis or Diss., Saint-Etienne, 2023. http://www.theses.fr/2023STET0062.
Abstract:
La complexité est facile à reconnaître mais difficile à définir : il existe de nombreuses mesures de complexité, chacune pertinente pour une application particulière.Dans le domaine de l'ingénierie des surfaces, l'auto-organisation entraîne la formation de motifs sur la matière par irradiation laser femtoseconde, ce qui a d'importantes applications biomédicales. Les détails de la formation des motifs ne sont pas entièrement compris. Dans des travaux menant à deux publications [1,2], grâce à un argument de complexité et un cadre d'apprentissage automatique guidé par la physique, nous montrons que le problème sévèrement contraint d'apprendre l'interaction laser-matière avec peu de données et une connaissance physique partielle est bien posé dans ce contexte. Notre modèle nous permet de faire des prédictions utiles et suggère des intuitions physiques.Dans une autre contribution [3], nous proposons une nouvelle formulation du principe de la Longueur Minimale de Description, définissant la complexité du modèle et des données en une seule étape, en tenant compte du signal et du bruit dans les données d'entraînement. Les expériences indiquent que les classificateurs de réseaux neuronaux qui généralisent bien suivent ce principe.Dans un travail non publié, nous proposons l'entropie de Taylor, une nouvelle mesure de la complexité des systèmes dynamiques qui peut être estimée via une seule image SEM. Cette approche pourrait faciliter l'apprentissage du processus physique dans de nouveaux matériaux grâce à l'adaptation de domaine.Cette thèse ouvre la voie à une représentation unifiée de la complexité dans les données et la connaissance physique, qui peut être utilisée dans le contexte de l'apprentissage automatique guidé par la physique.[1] Brandao, Eduardo, et al. "Learning PDE to model self-organization of matter." Entropy 24.8 (2022): 1096.[2] Brandao, Eduardo, et al. "Learning Complexity to Guide Light-Induced Self-Organized Nanopatterns." Physical Review Letters 130.22 (2023): 226201.[3] Brandao, Eduardo, et al. "Is My Neural Net Driven by the MDL Principle?." Joint European Conference on Machine Learning and Knowledge Discovery in Databases. Cham: Springer Nature Switzerland, 2023Complexity is easy to recognize but difficult to define: there are a host of measures of complexity, each relevant for a particular application.In Surface engineering, self-organization drives the formation of patterns on matter by femtosecond laser irradiation, which have important biomedical applications. Pattern formation details are not fully understood. In work leading to two publications [1,2], via a complexity argument and a physics-guided machine learning framework, we show that the severely constrained problem of learning the laser-matter interaction with few data and partial physical knowledge is well-posed in this context. Our model allows us to make useful predictions and suggests physical insights.In another contribution [3] we propose a new formulation of the Minimum Description Length principle, defining model and data complexity in a single step, by taking into account signal and noise in training data. Experiments indicate that Neural Network classifiers that generalize well follow this principle.In unpublished work, we propose Taylor entropy, a novel measure of dynamical system complexity which can be estimated via a single SEM image. This approach could facilitate learning the physical process in new materials through domain adaptation.This thesis paves the way for a unified representation of complexity in data and physical knowledge, which can be used in the context of Physics-guided machine learning.[1] Brandao, Eduardo, et al. "Learning PDE to model self-organization of matter." Entropy 24.8 (2022): 1096.[2] Brandao, Eduardo, et al. "Learning Complexity to Guide Light-Induced Self-Organized Nanopatterns." Physical Review Letters 130.22 (2023): 226201.[3] Brandao, Eduardo, et al. "Is My Neural Net Driven by the MDL Principle?." Joint European Conference on Machine Learning and Knowledge Discovery in Databases. Cham: Springer Nature Switzerland, 2023
29
Baptiste, Philippe. "Résultats de complexité et programmation par contraintes pour l'ordonnancement." Habilitation à diriger des recherches, Université de Technologie de Compiègne, 2002. http://tel.archives-ouvertes.fr/tel-00124998.
Abstract:
Baker [9] defines scheduling as the problem of allocating scarce resources to activities over time1. Inthis manuscript, we consider several scheduling problems with a variety of different environments.
The two parts of this manuscript provide an overview of two of our major research interests. The first
part (Chapters 2 to 5) is dedicated to polynomial time solutions of equal{processing{time scheduling
problems. The second one (Chapters 7 to 15) deals with the application of Constraint Programming
to scheduling. These two parts re
ect the balance we have tried to keep between theoretical and
more applied research.
Although all the topics covered in this manuscript are related to scheduling, Parts 1 and 2 are
dedicated to very different aspects of scheduling. Some few results discussed in Part 1 are occasionally
used in Part 2 but they are independent one from another. In the following, we brie
y review the
content Parts 1 and 2. More detailed introductions are provided in Sections 1 and 7 respectively.
30
Francois, Nicolas. "Alignement, séquence consensus, recherche de similarités : complexité et approximabilité." Phd thesis, Université Montpellier II - Sciences et Techniques du Languedoc, 2005. http://tel.archives-ouvertes.fr/tel-00108020.
Abstract:
Dans ce mémoire, nous étudions la complexité algorithmique de plusieurs problèmes combinatoiresconcernant la comparaison de séquences biologiques. Nous nous pla¸cons successivement du point de vue de
chacune des trois principales théories de la complexité algorithmique : la NP-complétude, l'approximabilité
et la complexité paramétrique.
Dans un premier temps, nous considérons plusieurs formes du problème de l'extraction des motifs communs
à un ensemble de séquences donné. Les motifs communs permettent, en pratique, de classifier les protéines
grâce à leur structure primaire, par exemple en fabriquant des séquences consensus.
En particulier, le problème de la médiane (resp. du centre) pour la distance d'édition consiste à rechercher
une séquence consensus minimisant la somme (resp. le maximum) des distances d'édition la séparant de
chacune des séquences prises en entrée. Nous affinons les résultats connus sur la difficulté de chacun de ces
deux problèmes : nous montrons, par exemple, qu'ils sont tous les deux W[1]-difficiles lorsqu'on les
paramétrise par le nombre des séquences étudiées et ce, même dans le cas d'un alphabet binaire. Nous
considérons également le problème de la plus longue sous-séquence commune. Ce problème a été
exhaustivement étudié dans sa forme usuelle. Or, on trouve dans la nature des séquences d'ADN et d'ARN
circulaires qu'il est utile de comparer. Dans ce mémoire, nous menons à bien la première étude du problème
de la plus longue sous-séquence commune à plusieurs séquences circulaires et/ou non orientées.
Dans un second temps, nous considérons plusieurs problèmes liés à la recherche de similarités approchées
entre séquences biologiques. C'est dans ce domaine que l'application de l'informatique à la biologie
moléculaire a été la plus fructueuse. En pratique les similarités permettent de déterminer les propriétés des
molécules nouvellement séquencées à l'aide de celles des séquences déjà annotées. En effet, une similarité en
séquence entraîne généralement une similarité en structure ou en fonction.
La plupart des nombreux logiciels dédiés à la détection de similarités locales, mettent en oeuvre des filtres
heuristiques : deux portions de séquences ne possédant pas certains motifs spécifiques en commun sont
considérées d'emblée comme dissimilaires. Le choix des motifs conditionne la sensibilité et la sélectivité du
filtre associé. Dans ce mémoire nous considérons un certain type de motifs appelé graine. Il s'agit en fait de
sous-chaînes à trous.
Nous étudions plusieurs problèmes algorithmiques liés à la conception de bonnes graines. En particulier,
nous montrons que le problème suivant est NP-difficile : étant donnés deux entiers naturels k, m et une
graine, décider si le filtre associé est sans perte lorsque l'on restreint la notion de similarité aux paires de
mots de même longueur m, séparés par une distance de Hamming au plus k. Notons que plusieurs
algorithmes exponentiels ont été proposés pour des généralisations de ce problème.
31
Richeton, Thiebaud. "Dynamique et complexité de la déformation plastique : étude par émission acoustique." Phd thesis, Grenoble INPG, 2006. http://tel.archives-ouvertes.fr/tel-00118329.
Abstract:
L'émission acoustique est un moyen unique d'étude des avalanches de dislocations, à la fois en termes d'énergie, de temps et d'espace. L'émission acoustique mesurée lors d'essais de fluage sur des monocristaux de glace avait révélé une très forte intermittence du processus de déformation plastique, associée à des distributions en loi de puissance de la taille des avalanches. Cette thèse a permis de montrer que cette dynamique critique invariante d'échelle était perturbée dans les polycristaux de glace, où un effet de taille finie non trivial lié à la taille de grain a été mis en évidence. Cette thèse a aussi révélé que la criticalité observée dans les monocristaux de glace se retrouvait au cours de la déformation de monocristaux de Cd, de Zn et de Cu. La température, l'écrouissage par la forêt, le mâclage et le glissement multiple n'ont notamment pas affecté la valeur de l'exposant critique. Ces résultats suggèrent que la plasticité monocristalline pourrait ainsi être gouverner par une dynamique universelle.
32
Aubert, Clément. "Logique linéaire et classes de complexité sous-polynomiales." Phd thesis, Université Paris-Nord - Paris XIII, 2013. http://tel.archives-ouvertes.fr/tel-00957653.
Abstract:
Cette 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.
33
Araujo, Julio. "Coloration et convexité dans les graphes." Phd thesis, Université de Nice Sophia-Antipolis, 2012. http://tel.archives-ouvertes.fr/tel-00732919.
Abstract:
Dans cette thèse, nous étudions plusieurs problèmes de théorie des graphes concernant la coloration et la convexité des graphes. La plupart des résultats gurant ici sont liés à la complexité de calcul de ces problèmes pour certaines classes de graphes. Dans la première, et principale, partie de cette thèse, nous traitons de coloration des graphes qui est l'un des domaines les plus étudiés de théorie des graphes. Nous considérons d'abord trois problèmes de coloration appelés coloration gloutone, coloration pondérée et coloration pondérée impropre. Ensuite, nous traitons un probl ème de décision, appelé bon étiquetage de arêtes, dont la dé nition a été motivée par le problème d'affectation de longueurs d'onde dans les réseaux optiques. La deuxième partie de cette thèse est consacrée à un paramètre d'optimisation des graphes appelé le nombre enveloppe (géodésique). La dé nition de ce paramètre est motivée par une extension aux graphes des notions d'ensembles et d'enveloppes convexes dans l'espace Euclidien. En n, nous présentons dans l'annexe d'autres travaux développées au cours de cette thèse, l'un sur les hypergraphes orientés Eulériens et Hamiltoniens et l'autre concernant les systèmes de stockage distribués.
34
Vaiter, Samuel. "Régularisations de Faible Complexité pour les Problèmes Inverses." Phd thesis, Université Paris Dauphine - Paris IX, 2014. http://tel.archives-ouvertes.fr/tel-01026398.
Abstract:
Cette thèse se consacre aux garanties de reconstruction et de l'analyse de sensibilité de régularisation variationnelle pour des problèmes inverses linéaires bruités. Il s'agit d'un problème d'optimisation convexe combinant un terme d'attache aux données et un terme de régularisation promouvant des solutions vivant dans un espace dit de faible complexité. Notre approche, basée sur la notion de fonctions partiellement lisses, permet l'étude d'une grande variété de régularisations comme par exemple la parcimonie de type analyse ou structurée, l'antiparcimonie et la structure de faible rang. Nous analysons tout d'abord la robustesse au bruit, à la fois en termes de distance entre les solutions et l'objet original, ainsi que la stabilité de l'espace modèle promu. Ensuite, nous étudions la stabilité de ces problèmes d'optimisation à des perturbations des observations. À partir d'observations aléatoires, nous construisons un estimateur non biaisé du risque afin d'obtenir un schéma de sélection de paramètre.
35
Salah, Abdellatif. "Schémas de décodage MIMO à complexité réduite." Phd thesis, Paris, Télécom ParisTech, 2010. https://pastel.hal.science/pastel-00682392.
Abstract:
L'utilisation des antennes MIMO est une technique qui permet d'exploiter de façon très efficace la diversité spatiale et temporelle présente dans certains systèmes de communication, dont le canal sans fil. Le principal avantage de cette technique est une très grande efficacité spectrale. De nos jours, où le canal radio-mobile est de plus en plus utilisé pour transmettre tout type d'information, les méthodes permettant une utilisation plus efficace du spectre électromagnétique ont une importance fondamentale. Les algorithmes de réception connus aujourd'hui sont très complexes, même en ce qui concerne les systèmes MIMO avec les codes espace-temps les plus simples. Cette complexité reste l'un des obstacles principaux à l'exploitation réelle. Cette thèse présente une étude très détaillée de la complexité, la performance et les aspects les plus intéressants du comportement des algorithmes de la réception pour le décodage MIMO, étude qui présente un moyen rapide pour une éventuelle conception des architectures adaptées à ce problème. Parmi les sujets présentés dans cette thèse, une étude approfondie de la performance et la complexité de ces algorithmes a été réalisée, ayant pour objectif d'avoir une connaissance suffisante pour pouvoir choisir, parmi le grand nombre d'algorithmes connus, le mieux adapté à chaque système particulier. Des améliorations aux algorithmes connus ont aussi été proposées et analyséesThe use of MIMO antennas is a technique that allows to exploit in a very effective way the spatial and temporal diversity in certain systems of communication, of which the wireless communication systems. The main advantage of this technique is a good spectral efficiency. Nowadays, the mobile radio channel is increasingly used to transmit all type of information and methods allowing a more effective use of the spectrum have a fundamental importance. Today, the well-known reception algorithms are very complex, even as regards the MIMO systems with the simplest space-time codes. This complexity remains one of the main obstacles in the real exploitation of this technique. This thesis presents a detailed study of the complexity, the performance and the most interesting aspects of the behavior of the reception algorithms for MIMO decoding. This study presents a quick mean for a possible architectural conception adapted to this problem. Among the subjects presented in this thesis, an in-depth study of the performance and the complexity of these algorithms was realized, having for objective to acquire enough knowledge to be able to choose, among the large number of known algorithms, the best adapted to every particular system. Improvements in the known algorithms were also proposed and analyzed
36
Salah, Abdellatif. "Schémas de décodage MIMO à Complexité Réduite." Phd thesis, Télécom ParisTech, 2010. http://pastel.archives-ouvertes.fr/pastel-00682392.
Abstract:
L'utilisation des antennes MIMO est une technique qui permet d'exploiter de façon très efficace la diversité spatiale et temporelle présente dans certains systèmes de communication, dont le canal sans fil. Le principal avantage de cette technique est une très grande efficacité spectrale. De nos jours, où le canal radio-mobile est de plus en plus utilisé pour transmettre tout type d'information, les méthodes permettant une utilisation plus efficace du spectre électromagnétique ont une importance fondamentale. Les algorithmes de réception connus aujourd'hui sont très complexes, même en ce qui concerne les systèmes MIMO avec les codes espace-temps les plus simples. Cette complexité reste l'un des obstacles principaux à l'exploitation réelle. Cette thèse présente une étude très détaillée de la complexité, la performance et les aspects les plus intéressants du comportement des algorithmes de la réception pour le décodage MIMO, étude qui présente un moyen rapide pour une éventuelle conception des architectures adaptées à ce problème. Parmi les sujets présentés dans cette thèse, une étude approfondie de la performance et la complexité de ces algorithmes a été réalisée, ayant pour objectif d'avoir une connaissance suffisante pour pouvoir choisir, parmi le grand nombre d'algorithmes connus, le mieux adapté à chaque système particulier. Des améliorations aux algorithmes connus ont aussi été proposées et analysées.
37
Derhy, Nicolas. "Multicoupes et sous-graphes induits : complexité et algorithmes." Phd thesis, Conservatoire national des arts et metiers - CNAM, 2008. http://tel.archives-ouvertes.fr/tel-00367626.
Abstract:
Dans ce travail de thèse, nous nous intéressons à plusieurs problèmes de théorie des graphes. Dans un premier temps, nous étudions différents problèmes de coupes et de multicoupes puis, dans un second temps, nous nous focalisons sur des problèmes de recherche de sous-graphes induits. Néanmoins, ces deux parties suivent la même ligne directrice : donner une vue d'ensemble de la complexité des problèmes en établissant leur NP-complétude ou en déterminant un algorithme polynomial de moindre complexité. Dans la première partie de la thèse, nous abordons les problèmes de coupes et de multicoupes. Tout d'abord, nous étudions la conséquence de l'ajout d'une contrainte de cardinalité à ces deux types de problèmes et démontrons leur NP- complétude dans le cas général. Puis, nous déterminons leur complexité dans plusieurs classes de graphes particuliers telles que les étoiles orientées et les chaînes en élaborant, pour les cas polynomiaux, différents algorithmes reposant principalement sur la programmation dynamique et l'utilisation de relaxations lagrangiennes. Nous généralisons ensuite cette approche en considérant les versions multicritères des problèmes de coupes et de multicoupes. Nous prouvons que ces derniers sont NP-complets même dans des topologies très simples comme les chaînes ou les cycles. Dans la seconde partie de ce mémoire, nous abordons des problèmes de recherche de sous-graphes induits. Nous nous intéressons principalement à la recherche d'arbres, de chaînes et de cycles induits couvrant un ensemble T de sommets donnés. Après avoir prouvé la NP-complétude des cas généraux, nous nous focalisons davantage sur les cas où la cardinalité de T est fixée. Nous donnons également plusieurs résultats structurels pour les graphes de maille suffisamment large.
38
Pechoux, Romain. "Analyse de la complexité des programmes par interprétation sémantique." Phd thesis, Institut National Polytechnique de Lorraine - INPL, 2007. http://tel.archives-ouvertes.fr/tel-00321917.
Abstract:
Il existe de nombreuses approches développées par la communauté Implicit Computational Complexity (ICC) permettant d'analyser les ressources nécessaires à la bonne exécution des algorithmes. Dans cette thèse, nous nous intéressons plus particulièrement au contrôle des ressources à l'aide d'interprétations sémantiques. Après avoir rappelé brièvement la notion de quasi-interprétation ainsi que les différentes propriétés et caractérisations qui en découlent, nous présentons les différentes avancées obtenues dans l'étude de cet outil : nous étudions le problème de la synthèse qui consiste à trouver une quasi-interprétation pour un programme donné, puis, nous abordons la question de la modularité des quasi-interprétations. La modularité permet de diminuer la complexité de la procédure de synthèse et de capturer un plus grand nombre d'algorithmes. Après avoir mentionné différentes extensions des quasi-interprétations à des langages de programmation réactif, bytecode ou d'ordre supérieur, nous introduisons la sup-interprétation. Cette notion généralise la quasi-interprétation et est utilisée dans des critères de contrôle des ressources afin d'étudier la complexité d'un plus grand nombre d'algorithmes dont des algorithmes sur des données infinies ou des algorithmes de type diviser pour régner. Nous combinons cette notion à différents critères de terminaison comme les ordres RPO, les paires de dépendance ou le size-change principle et nous la comparons à la notion de quasi-interprétation. En outre, après avoir caractérisé des petites classes de complexité parallèles, nous donnons quelques heuristiques permettant de synthétiser des sup-interprétations sans la propriété sous-terme, c'est à dire des sup-interprétations qui ne sont pas des quasi-interprétations. Enfin, dans un dernier chapitre, nous adaptons les sup-interprétations à des langages orientés-objet, obtenant ainsi différents critères pour contrôler les ressources d'un programme objet et de ses méthodes.
39
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:
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.
40
Schwoerer, Jean. "Études et implémentation d'une couche physique UWB impulsionnelle à bas débit et faible complexité¶." Phd thesis, INSA de Rennes, 2006. http://tel.archives-ouvertes.fr/tel-00638640.
Abstract:
De par son approche nouvelle, la radio impulsionnelle ultra large bande (UWB-IR) est porteuse de nombreuses promesses en termes de débit, de robustesse et de faible consommation. Du fait de sa largeur de bande (supérieure à 500 MHz), elle offre également la possibilité de faire de la géolocalisation avec une précision submétrique. Ce travail de thèse a débuté alors que les premières publications sur l'UWB présentaient des résultats de simulation extraordinaires. Afin de mieux cerner son réel potentiel dans le domaine des communications bas débit auquel l'UWB-IR semble particulièrement adaptée, cette étude a été orientée vers la réalisation matérielle d'une chaîne de communication, sous-tendue par la contrainte de forte réduction de complexité. Cette étude commence par la spécification d'une couche physique adaptée à la technologie et au domaine d'application envisagé, qui repose sur un schéma de transmission très simple. La plate-forme d'émission réalisée est basée sur une architecture très simple et des composants discrets de bas de gamme. Elle démontre ainsi la possibilité d'embarquer une telle structure dans un objet communicant autonome de faible coût. La chaîne de réception suit une approche originale basée sur un détecteur d'enveloppe et un comparateur à seuil variable, ce qui permet de relâcher certaines contraintes bloquantes comme celles liées à l'acquisition de synchronisation. Un ensemble d'algorithmes de réception à faible complexité permet d'exploiter au mieux cette structure de détection en levant différents verrous technologiques. Par ce travail, une réflexion globale sur un système UWB-IR bas débit a été menée et a abouti à la réalisation d'un lien radio physique qui démontre la viabilité technique de cette technologie en rupture. De plus, les résultats obtenus ont été la base d'une proposition complète portée en normalisation.
41
Muhammad, F. "Ordonnancement de tâches efficace et à complexité maîtrisée pour des systèmes temps-réel." Phd thesis, Université de Nice Sophia-Antipolis, 2009. http://tel.archives-ouvertes.fr/tel-00454616.
Abstract:
Les performances des algorithmes d'ordonnancement ont un impact direct sur les performances du système complet. Les algorithmes d'ordonnancement temps réel possèdent des bornes théoriques d'ordonnançabilité optimales mais cette optimalité est souvent atteinte au prix d'un nombre élevé d'événements d'ordonnancement à considérer (préemptions et migrations de tâches) et d'une complexité algorithmique importante. Notre opinion est qu'en exploitant plus efficacement les paramètres des tâches il est possible de rendre ces algorithmes plus efficaces et à coût maitrisé, et ce dans le but d'améliorer la Qualité de Service (QoS) des applications. Nous proposons dans un premier temps des algorithmes d'ordonnancement monoprocesseur qui augmentent la qualité de service d'applications hybrides c'est-à-dire qu'en situation de surcharge, les tâches à contraintes souples ont leur exécution maximisée et les échéances des tâches à contraintes strictes sont garanties. Le coût d'ordonnancement de ces algorithmes est aussi réduit (nombre de préemptions) par une meilleure exploitation des paramètres implicites et explicites des tâches. Cette réduction est bénéfique non seulement pour les performances du système mais elle agit aussi positivement sur la consommation d'énergie. Aussi nous proposons une technique associée à celle de DVFS (dynamic voltage and frequency scaling) afin de minimiser le nombre de changements de points de fonctionnement du fait qu'un changement de fréquence implique un temps d'inactivité du processeur et une consommation d'énergie. Les algorithmes d'ordonnancement multiprocesseur basés sur le modèle d'ordonnancement fluide (notion d'équité) atteignent des bornes d'ordonnançabilité optimales. Cependant cette équité n'est garantie qu'au prix d'hypothèses irréalistes en pratique du fait des nombres très élevés de préemptions et de migrations de tâches qu'ils induisent. Dans cette thèse un algorithme est proposé (ASEDZL) qui n'est pas basé sur le modèle d'ordonnancement fluide. Il permet non seulement de réduire les préemptions et les migrations de tâches mais aussi de relâcher les hypothèses imposées par ce modèle d'ordonnancement. Enfin, nous proposons d'utiliser ASEDZL dans une approche d'ordonnancement hiérarchique ce qui permet d'obtenir de meilleurs résultats que les techniques classiques.
42
Gigleux, Sylvain. "Modélisation du transfert des pesticides du sol jusqu'à l'aquifère : étude par approches de complexité croissante - site de Montreuil-sur-Epte." Phd thesis, Université d'Avignon, 2009. http://tel.archives-ouvertes.fr/tel-00464260.
Abstract:
Le continuum sol-zone non saturée-aquifère est rarement abordé en modélisation des pesticides car il requiert des outils et une méthodologie élaborés. Ces outils peuvent avoir des niveaux de complexités variables, le plus simple étant le modèle global et le plus complexe, le modèle hydrogéologique de transport en 3 dimensions prenant en compte chacun des compartiments dans le détail. Dans ce contexte une modélisation associant de manière dynamique des outils ou des méthodes propres à chaque compartiment propose une solution intermédiaire intéressante. Une approche progressive de la modélisation hydrodynamique ainsi que de la modélisation des transferts de pesticides, appliqué au cas du bassin versant hydrogéologique de la source des Brévilles à Montreuil-sur-Epte (Val d'Oise) a pu être réalisée et fournir un modèle couplé 1D / 2D prenant en compte l'écoulement et le transport dans le sol, la zone non saturée et la zone saturée
43
Guézo, Bernard. "Le territoire-étagé : un outil d'ingénierie pour agir sur la vulnérabilité des espaces métapolitains." Phd thesis, Université de Grenoble, 2012. http://tel.archives-ouvertes.fr/tel-00806092.
Abstract:
Si l'Ingénieur s'efforce de coordonner sur les territoires les deux facettes de son activité : d'un côté la gestion des fonctions urbaines, de l'autre celle des risques, il hésite à se démarquer de celles-ci comme il le devrait, pour affronter la complexité spatiale. Or notre pratique des espaces urbanisés comme notre engagement dans la prévention des risques montrent que la complexité se manifeste à lui, tant dans la réalisation des projets que dans la survenue des catastrophes. En proposant un outil d'analyse spatiale : le territoire-étagé, en le dotant d'une fonction - le monitorage - nous proposons une voie qui permette à l'ingénierie d'anticiper du plus possible le développement de processus dommageables. En permettant une plus grande compréhension des mécanismes à l'œuvre au sein des espaces métapolitains [Ascher, 1995], l'ingénierie du territoire-étagé offre la possibilité d'agir en retour sur les pratiques de gestion pour espérer réduire, par la résilience, les perturbations ou leurs effets de différentes natures et intensités.
44
Darties, Benoit. "Problèmes algorithmiques et de complexité dans les réseaux sans fil." Phd thesis, Université Montpellier II - Sciences et Techniques du Languedoc, 2007. http://tel.archives-ouvertes.fr/tel-00270118.
Abstract:
Ces dernières années ont connu l'avènement des réseaux sans fil, dopés par leur facilité de déploiement et par leur usage dans de multiples domaines : réseaux domestiques Wi-Fi, téléphonie mobile, réseaux ad-hoc, réseaux de capteurs, ... L'objet de cette thèse porte sur l'étude de problèmes algorithmiques directement inspirés des contraintes de fonctionnement rencontrées dans de tels réseaux, et se découpe en trois parties.La première partie de nos travaux s'intéresse à l'étude du problème de la diffusion d'un message émis depuis un noeud source unique vers l'ensemble des noeuds participant au réseau. Ce problème est abordé dans plusieurs modèles de communication, qui supposent tous des émissions omnidirectionnelles à portée fixée et l'existence de phénomènes d'interférences. Il en résulte l'incapacité pour un noeud donné de garantir la réception correcte de deux transmissions voisines simultanées. Nous étudions la complexité de ce problème et proposons des stratégies de résolution exactes ou avec garantie de performance.
Dans une seconde partie, l'un des modèles de communication précédemment introduits sert de support à l'étude d'un autre problème algorithmique, dont l'objet est la satisfaction de requêtes de communications. Les travaux menés sur ce problème visent à établir sa complexité ainsi que les facteurs dont elle dépend.
La dernière partie nous amène au problème de conception de réseaux sans fil. L'objectif est d'assurer une distribution de flux depuis des noeuds sources vers des noeuds clients, en minimisant le coût de l'infrastructure déployée. Les communications établies ici à l'aide d'antennes directionnelles ne sont pas sujettes aux phénomènes d'interférences. La difficulté du problème réside dans la satisfaction de contraintes de déploiement (nombre d'antennes limitées par noeud, résistance aux pannes, ...). Nous étudions la complexité de ce problème, et proposons plusieurs méthodes de résolution exactes et approchées pour des instances de taille raisonnable.
45
Romero, ugalde Héctor manuel. "Identification de systèmes utilisant les réseaux de neurones : un compromis entre précision, complexité et charge de calculs." Phd thesis, Ecole nationale supérieure d'arts et métiers - ENSAM, 2013. http://pastel.archives-ouvertes.fr/pastel-00869428.
Abstract:
Ce rapport porte sur le sujet de recherche de l'identification boîte noire du système non linéaire. En effet, parmi toutes les techniques nombreuses et variées développées dans ce domaine de la recherche ces dernières décennies, il semble toujours intéressant d'étudier l'approche réseau de neurones dans l'estimation de modèle de système complexe. Même si des modèles précis ont été obtenus, les principaux inconvénients de ces techniques restent le grand nombre de paramètres nécessaires et, en conséquence, le coût important de calcul nécessaire pour obtenir le niveau de pratique de la précision du modèle désiré. Par conséquent, motivés pour remédier à ces inconvénients, nous avons atteint une méthodologie complète et efficace du système d'identification offrant une précision équilibrée, la complexité et les modèles de coûts en proposant, d'une part, de nouvelles structures de réseaux de neurones particulièrement adapté à une utilisation très large en matière de modélisation système pratique non linéaire, d'autre part, un simple et efficace technique de réduction de modèle, et, troisièmement, une procédure de réduction de coût de calcul. Il est important de noter que ces deux dernières techniques de réduction peut être appliquée à une très large gamme d'architectures de réseaux de neurones sous deux simples hypothèses spécifiques qui ne sont pas du tout contraignant. Enfin, la dernière contribution importante de ce travail est d'avoir montré que cette phase d'estimation peut être obtenue dans un cadre robuste si la qualité des données d'identification qu'il oblige. Afin de valider la procédure d'identification système proposé, des exemples d'applications entraînées en simulation et sur un procédé réel, de manière satisfaisante validé toutes les contributions de cette thèse, confirmant tout l'intérêt de ce travail.
46
Kerbrat, Olivier. "Méthodologie de conception d'outillages modulaires hybrides basée sur l'évaluation quantitative de la complexité de fabrication." Phd thesis, Ecole centrale de nantes - ECN, 2009. http://tel.archives-ouvertes.fr/tel-00439589.
Abstract:
Dans le contexte actuel de concurrence industrielle internationale, la diversité des produits proposés et leur complexité croissante imposent aux industriels de proposer des produits manufacturés innovants, de qualité, à moindre coût et dans des délais de plus en plus contraignants. Le marché de la fabrication d'outillages de mise en forme (moules d'injection, matrices d'emboutissage, etc) a fortement évolué. Les outillages doivent désormais être conçus et mis au point plus rapidement, être adaptables aux différentes variantes de produits et fabriqués à coût maîtrisé.Ainsi, les outillages peuvent avantageusement être conçus avec une double approche : modulaire et hybride. Les outillages sont vus non plus comme une seule pièce, mais comme un puzzle en trois dimensions, avec différents modules fabriqués séparément puis assemblés. L'approche modulaire permet de prendre en compte les différentes variantes d'une même famille de pièces à produire en facilitant un changement rapide des parties de l'outillage. L'approche hybride permet de choisir le procédé de fabrication le plus adapté pour chacun des modules de l'outillage. Nous nous sommes intéressés aux procédés d‟usinage par enlèvement de matière ainsi qu'aux procédés de fabrication rapide par ajout de matière. Ces technologies additives arrivent à maturité et, bien qu'un haut niveau de qualité soit encore délicat à obtenir, les possibilités de réalisation de formes difficiles, voire impossibles, à usiner par enlèvement de matière rendent ces procédés très attractifs.
Ce travail de thèse consiste donc en l'élaboration d'une méthodologie de conception d'outillages modulaires hybrides. Cette méthode permet, dans un premier temps, d'analyser la complexité de fabrication des outillages lors de leur conception. Dans un deuxième temps, afin de réduire la complexité de fabrication (et par conséquent, diminuer les temps et coûts de réalisation à qualité égale), une nouvelle conception de l'outillage est proposée, en appliquant les points de vue modulaire et hybride. La complexité de fabrication de ce nouvel outillage est ensuite analysée, puis comparée à la première afin de quantifier les gains induits par notre approche modulaire hybride.
Une maquette informatique a donc été développée et implémentée dans un logiciel de CAO pour mettre en évidence les possibilités d'utilisation de la méthodologie lors de la phase de conception d'outillages. Elle est testée sur différentes pièces-test et outillages industriels, en particulier dans le cadre du projet EMOA (Excellence dans la Maîtrise de l'Ouvrant Automobile haut de gamme) piloté par PSA Peugeot-Citroën.
47
Tourniaire, Emeric. "Problèmes NP-difficiles : approximation modérément exponentielle et complexité paramétrique." Phd thesis, Université Paris Dauphine - Paris IX, 2013. http://tel.archives-ouvertes.fr/tel-00874599.
Abstract:
Nous détaillons dans cette thèse des algorithmes modérément exponentiels pour l'approximation du problème MAX SAT. Nous discutons d'une méthode générique pour la conception d'algorithmes exponentiels réalisant des schémas d'approximation dans un cadre plus général. Enfin, nous présentons des résultats paramétrés pour des problèmes de coupe à cardinalité contrainte.
48
Ada, Anil. "Communication complexity." Thesis, McGill University, 2014. http://digitool.Library.McGill.CA:80/R/?func=dbin-jump-full&object_id=121119.
Abstract:
Communication complexity studies how many bits a certain number of parties need to communicate with each other in order to compute a function whose input is distributed among those parties. Although it is a natural area of investigation based on practical considerations, the main motivation comes from the myriad of applications in theoretical computer science.This thesis has three main parts, studying three different aspects of communication complexity.1. The first part is concerned with the k-party communication complexity of functions F:({0,1}^n)^k -> {0,1} in the 'number on the forehead' (NOF) model. This is a fundamental model with many applications. In this model we study composed functions f of g. These functions include most of the well-known and studied functions in communication complexity literature. A major goal is to understand which combinations of f and g lead to hard communication functions. In particular, due to important circuit applications, it is of great interest to understand how powerful the NOF model becomes when k is log n or more. Motivated by these goals, we show that there is an efficient O(log^3 n) cost simultaneous protocol for sym of g when k > 1+log n, sym is any symmetric function and g is any function. This class of functions includes some functions that were previously conjectured to be hard and our result rules this class out for possible very important circuit complexity applications. We also give Ramsey theoretic applications of our efficient protocol. In the setting of k < log n, we study more closely functions of the form majority of g, mod_m of g, and nor of g, where the latter two are generalizations of the well-known functions Inner Product and Disjointness respectively. We characterize the communication complexity of these functions with respect to the choice of g. As the main application, we answer a question posed by Babai et al. (SIAM Journal on Computing, 33:137--166, 2004) and determine the communication complexity of majority of qcsb, where qcsb is the "quadratic character of the sum of the bits" function. 2. The second part is about Fourier analysis of symmetric boolean functions and its applications in communication complexity and other areas. The spectral norm of a boolean function f:{0,1}^n -> {0,1} is the sum of the absolute values of its Fourier coefficients. This quantity provides useful upper and lower bounds on the complexity of a function in areas such as communication complexity, learning theory and circuit complexity. We give a combinatorial characterization for the spectral norm of symmetric functions. We show that the logarithm of the spectral norm is of the same order of magnitude as r(f)log(n/r(f)) where r(f) = max(r_0,r_1), and r_0 and r_1 are the smallest integers less than n/2 such that f(x) or f(x)parity(x) is constant for all x with x_1 + ... + x_n in [r_0, n-r_1]. We present some applications to the decision tree and communication complexity of symmetric functions. 3. The third part studies privacy in the context of communication complexity: how much information do the players reveal about their input when following a communication protocol? The unattainability of perfect privacy for many functions motivates the study of approximate privacy. Feigenbaum et al. (Proceedings of the 11th Conference on Electronic Commerce, 167--178, 2010) defined notions of worst-case as well as average-case approximate privacy, and presented several interesting upper bounds, and some open problems for further study. In this thesis, we obtain asymptotically tight bounds on the trade-offs between both the worst-case and average-case approximate privacy of protocols and their communication cost for Vickrey Auction, which is the canonical example of a truthful auction. We also prove exponential lower bounds on the approximate privacy of protocols computing the Intersection function, independent of its communication cost. This proves a conjecture of Feigenbaum et al.La complexité de communication étudie combien de bits un groupe de joueurs donné doivent échanger entre eux pour calculer une function dont l'input est distribué parmi les joueurs. Bien que ce soit un domaine de recherche naturel basé sur des considérations pratiques, la motivation principale vient des nombreuses applications théoriques.Cette thèse comporte trois parties principales, étudiant trois aspects de la complexité de communication.1. La première partie discute le modèle 'number on the forehead' (NOF) dans la complexité de communication à plusieurs joueurs. Il s'agit d'un modèle fondamental en complexité de communication, avec des applications à la complexité des circuits, la complexité des preuves, les programmes de branchement et la théorie de Ramsey. Dans ce modèle, nous étudions les fonctions composeés f de g. Ces fonctions comprennent la plupart des fonctions bien connues qui sont étudiées dans la littérature de la complexité de communication. Un objectif majeur est de comprendre quelles combinaisons de f et g produisent des compositions qui sont difficiles du point de vue de la communication. En particulier, à cause de l'importance des applications aux circuits, il est intéressant de comprendre la puissance du modèle NOF quand le nombre de joueurs atteint ou dépasse log n. Motivé par ces objectifs nous montrons l'existence d'un protocole simultané efficace à k joueurs de coût O(log^3 n) pour sym de g lorsque k > 1 + log n, sym est une function symmétrique quelconque et g est une fonction arbitraire. Nous donnons aussi des applications de notre protocole efficace à la théorie de Ramsey.Dans le contexte où k < log n, nous étudions de plus près des fonctions de la forme majority de g, mod_m de g et nor de g, où les deux derniers cas sont des généralisations des fonctions bien connues et très étudiées Inner Product et Disjointness respectivement. Nous caractérisons la complexité de communication de ces fonctions par rapport au choix de g.2. La deuxième partie considère les applications de l'analyse de Fourier des fonctions symmétriques à la complexité de communication et autres domaines. La norme spectrale d'une function booléenne f:{0,1}^n -> {0,1} est la somme des valeurs absolues de ses coefficients de Fourier. Nous donnons une caractérisation combinatoire pour la norme spectrale des fonctions symmétriques. Nous montrons que le logarithme de la norme spectrale est du même ordre de grandeur que r(f)log(n/r(f)), avec r(f) = max(r_0,r_1) où r_0 et r_1 sont les entiers minimaux plus petits que n/2 pour lesquels f(x) ou f(x)parity(x) est constant pour tout x tel que x_1 + ... + x_n à [r_0,n-r_1]. Nous présentons quelques applications aux arbres de décision et à la complexité de communication des fonctions symmétriques.3. La troisième partie étudie la confidentialité dans le contexte de la complexité de communication: quelle quantité d'information est-ce que les joueurs révèlent sur leur input en suivant un protocole donné? L'inatteignabilité de la confidentialité parfaite pour plusieurs fonctions motivent l'étude de la confidentialité approximative. Feigenbaum et al. (Proceedings of the 11th Conference on Electronic Commerce, 167--178, 2010) ont défini des notions de confidentialité approximative dans le pire cas et dans le cas moyen, et ont présenté plusieurs bornes supérieures intéressantes ainsi que quelques questions ouvertes. Dans cette thèse, nous obtenons des bornes asymptotiques précises, pour le pire cas aussi bien que pour le cas moyen, sur l'échange entre la confidentialité approximative de protocoles et le coût de communication pour les enchères Vickrey Auction, qui constituent l'exemple canonique d'une enchère honnête. Nous démontrons aussi des bornes inférieures exponentielles sur la confidentialité approximative de protocoles calculant la function Intersection, indépendamment du coût de communication. Ceci résout une conjecture de Feigenbaum et al.
49
Vander, Linden Marc. "Archéologie, complexité sociale et histoire des idées: l'espace campaniforme en Europe au 3e millénaire avant notre ère." Doctoral thesis, Universite Libre de Bruxelles, 2001. http://hdl.handle.net/2013/ULB-DIPOT:oai:dipot.ulb.ac.be:2013/211540.
50
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:
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.