Dans cette thèse, nous explorons de nouvelles méthodes d'analyse d'images pour la détection précoce des changements métaboliques cérébraux causés par la maladie d'Alzheimer (MA). Nous introduisons deux apports méthodologiques que nous appliquons à un ensemble de données réelles. Le premier est basé sur l'apprentissage automatique pour créer une carte des informations de classification pertinente dans un ensemble d'images. Pour cela nous échantillonnons des blocs de voxels de l'image selon un algorithme de Monte-Carlo. La mise en oeuvre d'une classification basée sur ces patchs 3D a pour conséquence importante la réduction significative du volume de patchs à traiter, et l'extraction de caractéristiques dont l'importance est statistiquement quantifiable. Cette méthode s'applique à différentes caractéristiques de l'image et donc est adaptée à des types d'images très variés. La résolution des cartes produites par cette méthode peut être affinée à volonté et leur contenu informatif est cohérent avec les résultats antérieurs basés sur les statistiques sur les voxels obtenus dans la littérature. Le second apport méthodologique porte sur la conception d'un nouvel algorithme de décomposition de tenseur d'ordre important, adapté à notre application. Cet algorithme permet de réduire considérablement la consommation de mémoire et donc évite la surcharge de la mémoire. Il autorise la décomposition rapide de tenseurs, y compris ceux de dimensions très déséquilibrées. Nous appliquons cet algorithme en tant que méthode d'extraction de caractéristiques dans une situation où le clinicien doit diagnostiquer des stades MA précoce ou MCI (Mild Cognitive Impairment) en utilisant la TEP FDG seule. Les taux de classification obtenus sont souvent au-dessus des niveaux de l'état de l'art. Dans le cadre de ces tâches d'analyse d'images, nous présentons notre source de données, les scans de patients retenus et les pré-traitements réalisés. Les principaux aspects que nous voulons prendre en compte sont la nature volumétrique des données, l'information a priori disponible sur la localisation des changements métaboliques et comment l'identification des zones de changements métaboliques participe à la réduction de la quantité de données à analyser et d'extraire des caractéristiques discriminantes. Les méthodes présentées fournissent des informations précises sur la localisation de ces changements métaboliques. Les taux de classification allant jusqu'à 92,6% pour MA et 83,8% pour MCI. En outre, nous sommes capables de séparer les patients MCI stables des MCI patients évoluant vers la MA dans les 2 ans après l'acquisition du PET-scan avec un taux de classification de 84.7%. Ce sont des étapes importantes vers une détection fiable et précoce de la MA.

A reactive system is a system that continuously interacts with its environment. The environment provides an input signal, to which the system reacts with an output signal, and so on ad infinitum. In reactive synthesis, the goal is to automatically generate an implementation from a specification of the reactive and non-terminating input/output behaviours of a system. In the classical setting, the set of signals is assumed to be finite. however, this assumption is not realistic to model systems which process sequences of signals accompanied with data from a possibly infinite set (e.g. a client id, a sensor value, etc.), which need to be stored in memory and compared against each other.The goal of this thesis is to lift the theory of reactive system synthesis over words on a finite alphabet to data words. The data domain consists in an infinite set whose structure is given by predicates and constants enriched with labels from a finite alphabet. In this context, specifications and implementations are respectively given as automata and transducers extended with a finite set of registers that they use to store data values. To determine the transition to take, they compare the input data with the content of the registers using the predicates of the domain.In a first part, we consider both the bounded and unbounded synthesis problem; the former additionally asks for a bound on the number of registers of the implementation, along with the specification. We do so for different instances, depending on whether the specification is a nondeterministic, universal (a.k.a. co-non-deterministic) or deterministic automaton, for various domains.While the bounded synthesis problem is undecidable for non-deterministic specifications, we provide a generic approach consisting in a reduction to the finite alphabet case, that is done through automata-theoretic constructions. This allows to reprove decidability of bounded synthesis for universal specifications over (ℕ,=), and to obtain new ones, such as the case of a dense order, or the ability of data guessing, all with a 2-ExpTime complexity.We then move to the unbounded synthesis problem, which is undecidable for specifications given by non-deterministic and universal automata, but decidable and ExpTime-complete for deterministic ones over (ℕ,=) and (ℚ,<). We also exhibit a decidable subclass in the case of (ℕ,<), namely one-sided specifications.In a second part, we lift the reactivity assumption, considering the richer class of implementations that are allowed to wait for additional input before reacting, again over data words. Specifications are modelled as non-deterministic asynchronous transducers, that output a (possibly empty) word when they read an input data. Already in the finite alphabet case, their synthesis problem is undecidable.A way to circumvent the difficulty is to focus on functional specifications, for which any input sequence admits at most one acceptable output. Targeting programs computed by input-deterministic transducers is again undecidable, so we shift the focus to deciding whether a specification is computable, in the sense of the classical extension of Turing-computability to infinite inputs. We relate this notion with that of continuity for the Cantor distance, which yields a decidable characterisation of computability for functional specifications given by asynchronous register transducers over (ℕ,=) and for the superseding class of oligomorphic data domains, that also encompasses $(ℚ,<)$. The study concludes with the case of (ℕ,<), that is again decidable. Overall, we get PSpace-completeness for the problems of deciding computability and refined notions, as well as functionality. / Option Informatique du Doctorat en Sciences / info:eu-repo/semantics/nonPublished

Cocoa bean fermentation is an essential but spontaneous fermentation process to obtain the necessary raw material for the production of cocoa-derived products, among which chocolate. Successful cocoa bean fermentation processes are typically dominated by three microbial groups, namely yeasts, lactic acid bacteria, and acetic acid bacteria. The use of functional starter cultures may allow to gain a better control over the fermentation process. Previously, a number of candidate functional starter cultures have been proposed for the lactic acid bacteria, namely Lactobacillus fermentum 222 and Lactobacillus plantarum 80, and for the acetic acid bacteria, namely Acetobacter pasteurianus 386B, Acetobacter ghanensis LMG 23848T, and Acetobacter senegalensis 108B. The metabolism of bacteria determines an important part of their physiology, and this is recently being investigated by using computational models. The aim of this PhD thesis was to develop such models for the candidate functional starter cultures for the cocoa bean fermentation process and to perform the related computational analysis. The computational models developed were genome-scale metabolic models, which constitute a comprehensive repertoire of metabolic enzymes with their concomitant reactions, and this at genome-scale. The reconstruction of such models requires a combination of high-quality genome re-annotation, comparative genomics, manual curation, and experimental validation. Genome-scale metabolic modeling together with the use of previously published experimental data under cocoa fermentation conditions allowed to contextualize the experimental data and to gain new insights into the metabolic properties of the candidate functional starter cultures. Simulations with the A. pasteurianus 386B genome-scale metabolic model revealed the metabolic roles of lactate and ethanol, the energetic properties of the strains’ aerobic respiratory chain, and the possible functional role of an NAD(P)+ transhydrogenase. Modeling the metabolite dynamics of A. ghanensis LMG 23848T under cocoa fermentation conditions revealed an alternative strategy for its diauxic growth, compared with A. pasteurianus 386B, which was related to a difference in lactate consumption rate and pyruvate overflow. For A. senegalensis 108B, it was shown that, next to lactic acid, also citric acid could sustain its growth in vitro as the sole carbon source. Furthermore, the absence of the glyoxylate cycle predicted from its genome did not correspond with its species description that reports growth on ethanol as the sole carbon source. For L. fermentum 222 and L. plantarum 80, core genome-scale metabolic models allowed to gain insight into the possible metabolic flux distributions as a function of environmental conditions. The modeling also indicated a current lack in knowledge; for example, concerning the presence and consumption of undefined substrates in the complex medium used.In summary, genome-scale metabolic modelling of candidate functional starter cultures for the cocoa bean fermentation process provided useful in silico tools to gain insight into their metabolic properties at a systemic level. / La fermentation du cacao est un processus essentiel pour obtenir la matière première nécessaire pour la production de produits dérivés du cacao, comme par exemple le chocolat. Une fermentation de cacao favorable est caractérisée par la domination de trois groupes de microorganismes :les levures, les bactéries lactiques, et les bactéries acétiques. L'utilisation de cultures de départ fonctionnelles permet un meilleur contrôle sur le processus de fermentation. En ce qui concerne les bactéries, de nombreuses cultures "starter" ont été proposées, à savoir Lactobacillus fermentum 222 et Lactobacillus plantarum 80 pour les bactéries lactiques et Acetobacter pasteurianus 386B, Acetobacter ghanensis LMG 23848T, et Acetobacter senegalensis 108B pour les bactéries acétiques. Le métabolisme des bactéries constitue une partie importante de leur physiologie et la recherche actuelle se concentre de plus en plus sur la modélisation du métabolisme et la simulation des flux métaboliques par ordinateur. Cette thèse de doctorat a été consacrée au développement et à l'analyse de tels modèles computationnels pour des cultures fonctionnelles "starter" proposés pour la fermentation du cacao.Les modèles qui ont été développés dans cette thèse sont des modèles métaboliques à l’échelle du génome. La reconstruction du réseau métabolique a entraîné la ré-annotation du génome, une étude de génomique comparative, la curation manuelle des annotations et la validation du modèle par des expériences in vitro. La modélisation nous a permis de contextualiser des données expérimentales déjà publiées pour en obtenir de nouvelles informations concernant les propriétés métaboliques des cultures starter. Des simulations utilisant le modèle métabolique de A. pasteurianus 386B ont clarifié les rôles métaboliques de l’acide lactique et de l’éthanol, les propriétés énergétiques de sa chaîne respiratoire, et ont permis d'assigner un rôle possible à une NAD(P)+ transhydrogénase. La modélisation de la dynamique des métabolites provenant d’un milieu de croissance de A. ghanensis LMG 23848T dans des conditions simulant la fermentation du cacao, a mis en évidence une stratégie alternative de croissance biphasique comparé à A. pasteurianus 386B. Ceci est dû à une différence dans le taux de consommation de l’acide lactique et à l’éventuelle production de pyruvate. Pour A. senegalensis 108B, les expériences ont démontré, tant pour l’acide lactique que pour l’acide citrique, que ces sources de carbone permettaient, à elles seules, la croissance de cette bactérie. L’absence du cycle du glyoxylate chez A. senegalensis 108B ne correspondait pas à la description de cette espèce, laquelle pouvant croître sur l’éthanol comme seule source de carbone. Pour L. fermentum 222 et L. plantarum 80, la modélisation de leur métabolisme du carbone a permis d’explorer les distributions de flux métaboliques en fonction des substrats consommés. Les simulations ont aussi révélé le manque de connaissance que nous avons sur ces bactéries lactiques, telle que la consommation de substrats non identifiés venant du milieu de croissance et qui pourrait influencer leur dynamique de croissance.En résumé, la modélisation métabolique à l’échelle du génome des cultures starter proposées pour la fermentation du cacao a permis le développement d’outils in silico qui peuvent être utilisés pour mieux comprendre le métabolisme global de ces souches. / Het cacaoboonfermentatieproces is een essentieel maar spontaan proces dat nodig is om de noodzakelijke grondstof, met name de gefermenteerde cacaobonen, voor de productie van cacao-afgeleide producten, waaronder chocolade, te bekomen. Succesvolle cacaoboonfermentatieprocessen worden typisch gedomineerd door drie microbiële groepen, met name gisten, melkzuurbacteriën en azijnzuurbacteriën. Om meer controle te verkrijgen over het fermentatieproces is het gebruik van functionele starterculturen aangewezen. In vorige studies werd reeds een reeks kandidaat-functionele starterculturen voorgesteld. Voor de melkzuurbacteriën zijn dit Lactobacillus fermentum 222 en Lactobacillus plantarum 80 en voor de azijnzuurbacteriën zijn dit Acetobacter pasteurianus 386B, Acetobacter ghanensis LMG 23848T en Acetobacter senegalensis 108B. Het metabolisme van bacteriën bepaalt in grote mate hun fysiologie, en dit wordt recent onderzocht door middel van computationele modellen. Het ontwikkelen en analyseren van zulke modellen voor de voorgestelde kandidaat-functionele starterculturen vormde het onderwerp van deze doctoraatsthesis.De computationele modellen waarvan sprake waren genoomwijde metabole modellen (GEMs), dewelke het repertoire aan metabole enzymen en de biochemische reacties die zij katalyseren in de bacteriële cellen omvat. De reconstructie van het metabole netwerk op genoomschaal vraagt om een gecombineerde aanpak van hoge-kwaliteit genoomherannotatie, comparatieve genomica en experimentele validatie. De GEMs werden gebruikt om reeds gepubliceerde experimentele data onder cacaofermentatiecondities te contextualiseren en nieuwe inzichten te verkrijgen in de metabole karakteristieken van de kandidaat-functionele starterculturen. Door middel van simulaties met het A. pasteurianus 386B GEM kon de metabole rol van melkzuur en ethanol, en de energetische karakteristieken van de aerobe respiratieketen van deze stam aangetoond worden, alsook de mogelijke metabole functie van een NAD(P)+ transhydrogenase. Het modelleren van de microbiële dynamica van A. ghanensis LMG 23848T onder cacaofermentatiecondities wees op een alternatieve strategie voor de tweevoudige groei van deze stam ten opzichte van de tweevoudige groei van A. pasteurianus 386B onder dezelfde condities, en dit omwille van een verschil in melkzuurconsumptiesnelheid en pyruvaatsecretie. Voor A. senegalensis 108B werd aangetoond dat deze stam, naast melkzuur, ook op citroenzuur als enige koolstofbron kon groeien. De afwezigheid van de glyoxylaatcyclus, voorspeld op basis van het genoom, bij A. senegalensis 108B is in tegenstelling tot de soortbeschrijving, dewelke stipuleert dat deze azijnzuurbacteriesoort in staat is tot groei op ethanol als enige koolstofbron. Voor L. fermentum 222 en L. plantarum 80 leidde de ontwikkeling van GEMs tot nieuwe inzichten in de mogelijke metabole fluxverdelingen, voornamelijk ten aanzien van substraatverbruik. Het modelleren van de microbiële dynamica wees ook op een tekortkoming aan huidige kennis over deze stammen, bijvoorbeeld met betrekking tot het gebruik van ongedefinieerde substraten in een rijk groeimedium.Samenvattend werden door middel van de ontwikkelde GEMs van de kandidaat-functionele starterculturen voor cacaoboonfermentatieprocessen nieuwe inzichten verkregen in hun metabolisme en dit op systeemniveau. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

Today, as computer systems are ubiquitous in our everyday life, there is no need to argue that their correctness is of capital importance. In order to prove (in a mathematical sense) that a given system satisfies a given property, formal methods have been introduced. They include concepts such as model checking and synthesis. Roughly speaking, when considering synthesis, we aim at building a model of the system which is correct by construction. In order to do so, models are mainly borrowed from game theory. During the last decades, there has been a shift from two-player qualitative zero-sum games (used to model antagonistic interactions between a system and its environment) to multiplayer quantitative games (used to model complex systems composed of several agents whose objectives are not necessarily antagonistic). In the latter setting, the solution concepts of interest include numerous equilibria, such as Nash equilibrium (NE) and subgame perfect equilibrium (SPE). While the existence of equilibria is widely studied, it is also well known that several equilibria may coexist in the same game. Nevertheless, some equilibria are more relevant than others. For example, if we consider a game in which each player aims at satisfying a given qualitative objective, it is possible to have both an equilibrium in which no player satisfies his objective and another one in which each player satisfies it. In this case one prefers the latter equilibrium which is more relevant.In this thesis, we focus on multiplayer turn-based games played on graphs either with qualitative or quantitative objectives. Our contributions are twofold: (i) we provide equilibria characterizations and (ii) we use these characterizations to solve decision problems related to the existence of relevant equilibria; and characterize their complexities. Firstly, we provide a characterization of a weaker notion of SPE (weak SPE) in multiplayer games with omega-regular objectives based on the payoff profiles which are realizable by a weak SPE. We then adopt another point of view by characterizing the outcomes of equilibria instead of their payoff profiles. In particular we focus on weak SPE outcome characterization. As for some kinds of games (e.g. multiplayer quantitative Reachability games), weak SPEs and SPEs are equivalent, this characterization is useful in order to study SPEs in these games.Secondly, we use those different equilibrium characterizations to provide the exact complexity classes of different decision problems related to the existence of relevant equilibria. We mainly focus on the constrained existence problem: if each player aims at maximizing his gain, this problem asks whether there exists an equilibrium such that each resulting player’s gain is greater than a threshold (one per player). We also consider variants of relevant equilibria based on the social welfare and the Pareto optimality of the players’ payoff. In this way, we prove the exact complexity classes for (i) the weak SPE constrained existence problem in multiplayer games with classical qualitative objectives such as Büchi, co-Büchi and Safety and (ii) the NE and SPE constrained existence problems (and variants) for qualitative and quantitative reachability games. In the latter case, the upper bounds on the required memory for such relevant equilibria are studied and proved to be finite. Studying memory requirements of strategies is important since with the synthesis process those strategies have to be implemented.Finally, we consider multiplayer, non zero-sum, turn-based timed games with qualitative Reachability objectives together with the concept of SPE. We prove that the SPE constrained existence problem is EXPTIME-complete for qualitative Reachability timed games. In order to obtain an EXPTIME algorithm, we proceed in different steps. In the first step, we prove that the game variant of the classical region graph is a good abstraction for the SPE constrained existence problem. In fact, we identify conditions on bisimulations under which the study of SPE in a given game can be reduced to the study of its quotient. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

Cette these presente les techniques d'optimisation combinatoire et de programmation entiere transversales a nos differents projets de recherche.

Le but de cette thèse est d'établir des résultats énumératifs sur certaines classes de chemins et d'animaux. Ces résultats sont obtenus en appliquant la théorie des empilements de pièces développée par Viennot. Nous étudions les excursions discrètes (ou chemins de Dyck généralisés) de hauteur bornée; nous obtenons des interprétations combinatoires et des extensions de résultats de Banderier, Flajolet et Bousquet-Mélou. Nous décrivons et énumérons plusieurs classes de chemins auto-évitants, dits chemins faiblement dirigés. Ces chemins sont plus nombreux que les chemins prudents qui forment la classe naturelle la plus grande jusqu'alors. Nous calculons le périmètre de site moyen des animaux dirigés, prouvant des conjectures de Conway et Le Borgne. Enfin, nous obtenons des résultats nouveaux sur l'énumération des animaux de Klarner et les animaux multi-dirigés de Bousquet-Mélou et Rechnitzer.

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.

This document is a long abstract of my research work, concerning graph theory and algorithms on graphs. It summarizes some results, gives ideas of the proof for some of them and presents the context of the different topics together with some interesting open questions connected to them The first part precises the notations used in the rest of the paper; the second part deals with some problems on cycles in digraphs; the third part is an overview of two graph coloring problems and one problem on structures in colored graphs; finally the fourth part focus on some results in algorithmic graph theory, mainly in parametrized complexity.

Cette thèse traite de l'étude des spanneurs multichemins, comme extension des spanneurs de graphes classiques. Un spanneur H d'un graphe G est un sous-graphe couvrant tel que pour toute paire de sommets du graphe a, b ∈ V (G) la distance dans le spanneur dH (a, b) n'est pas trop étirée par rapport à la distance dans le graphe d'origine dG(a, b). Ainsi il existe un facteur d'étirement (α, β) tel que pour tout a, b ∈ V(G), d_h(a, b) <= α*d_G(a, b) + β. Motivés par des considérations de routage à plusieurs chemins et après la remarque que le concept de spanneur peut être étendu à toute métrique " non décroissante ", nous introduisons la notion de spanneur multichemins. Après une introduction au domaine, nous parlerons des résultats obtenus concernant d'une part les spanneurs multichemins arêtes disjoints et d'autre part les spanneurs multichemins sommets disjoints.

Dans cette thèse, nous nous intéressons à différentes notions de colorations sous contraintes. Nous nous intéressons plus spécialement à la coloration acyclique, à la coloration forte d'arêtes et à la coloration d'arêtes sommets adjacents distinguants.Dans le Chapitre 2, nous avons étudié la coloration acyclique. Tout d'abord nous avons cherché à borner le nombre chromatique acyclique pour la classe des graphes de degré maximum borné. Ensuite nous nous sommes attardés sur la coloration acyclique par listes. La notion de coloration acyclique par liste des graphes planaires a été introduite par Borodin, Fon-Der Flaass, Kostochka, Raspaud et Sopena. Ils ont conjecturé que tout graphe planaire est acycliquement 5-liste coloriable. De notre côté, nous avons proposé des conditions suffisantes de 3-liste coloration acyclique des graphes planaires. Dans le Chapitre 3, nous avons étudié la coloration forte d'arêtes des graphes subcubiques en majorant l'indice chromatique fort en fonction du degré moyen maximum. Nous nous sommes également intéressés à la coloration forte d'arêtes des graphes subcubiques sans cycles de longueurs données et nous avons également obtenu une majoration optimale de l'indice chromatique fort pour la famille des graphes planaires extérieurs. Nous avons aussi présenté différents résultats de complexité pour la classe des graphes planaires subcubiques. Enfin, au Chapitre 4, nous avons abordé la coloration d'arêtes sommets adjacents distinguants en déterminant les majorations de l'indice avd-chromatique en fonction du degré moyen maximum. Notre travail s'inscrit dans la continuité de celui effectué par Wang et Wang en 2010. Plus précisément, nous nous sommes focalisés sur la famille des graphes de degré maximum au moins 5.