La conjecture de partitionnement des chemins

Soit G = (V, E) un graphe simple fini. Soit (a, b) un couple d’entiers positifs. On note par τ(G) le nombre de sommets d’un chemin d’ordre maximum dans G. Une partition (A,B) de V(G) est une (a,b)−partition si τ(⟨A⟩) ≤ a et τ(⟨B⟩) ≤ b. Si G possède une (a, b)−partition pour tout couple d’entiers positifs satisfaisant τ(G) = a+b, on dit que G est τ−partitionnable. La conjecture de partitionnement des chemins, connue sous le nom anglais de Path Partition Conjecture, cherche à établir que tout graphe est τ−partitionnable. Elle a été énoncée par Lovász et Mihók en 1981 et depuis, de nombreux chercheurs ont tenté de démontrer cette conjecture et plusieurs y sont parvenus pour certaines classes de graphes. Le présent mémoire rend compte du statut de la conjecture, en ce qui concerne les graphes non-orientés et ceux orientés.

Génération efficace de graphes d’appels dynamiques complets

Analyser le code permet de vérifier ses fonctionnalités, détecter des bogues ou améliorer sa performance. L’analyse du code peut être statique ou dynamique. Des approches combinants les deux analyses sont plus appropriées pour les applications de taille industrielle où l’utilisation individuelle de chaque approche ne peut fournir les résultats souhaités. Les approches combinées appliquent l’analyse dynamique pour déterminer les portions à problèmes dans le code et effectuent par la suite une analyse statique concentrée sur les parties identifiées. Toutefois les outils d’analyse dynamique existants génèrent des données imprécises ou incomplètes, ou aboutissent en un ralentissement inacceptable du temps d’exécution. Lors de ce travail, nous nous intéressons à la génération de graphes d’appels dynamiques complets ainsi que d’autres informations nécessaires à la détection des portions à problèmes dans le code. Pour ceci, nous faisons usage de la technique d’instrumentation dynamique du bytecode Java pour extraire l’information sur les sites d’appels, les sites de création d’objets et construire le graphe d’appel dynamique du programme. Nous démontrons qu’il est possible de profiler dynamiquement une exécution complète d’une application à temps d’exécution non triviale, et d’extraire la totalité de l’information à un coup raisonnable. Des mesures de performance de notre profileur sur trois séries de benchmarks à charges de travail diverses nous ont permis de constater que la moyenne du coût de profilage se situe entre 2.01 et 6.42. Notre outil de génération de graphes dynamiques complets, nommé dyko, constitue également une plateforme extensible pour l’ajout de nouvelles approches d’instrumentation. Nous avons testé une nouvelle technique d’instrumentation des sites de création d’objets qui consiste à adapter les modifications apportées par l’instrumentation au bytecode de chaque méthode. Nous avons aussi testé l’impact de la résolution des sites d’appels sur la performance générale du profileur.

Comparaisons de projections des niveaux d'incapacité de la population canadienne de 65 ans et plus en 2031

Le vieillissement de la population canadienne prévisible dans les prochaines années entrainera d’importants changements au point de vue social. L’un d’eux est l’augmentation fulgurante du nombre d’aînés en état d’incapacité. Utilisant le modèle de microsimulation LifePaths, cette recherche compare deux projections, ayant des méthodologies différentes, du nombre d’individus en incapacité de 65 ans et plus vivant en ménage privé en 2031. La première méthode utilise le module d’incapacité de LifePaths pour générer les individus en incapacité tandis que la seconde méthode utilise plutôt une régression logistique ordonnée pour les obtenir. Les projections du nombre d’individus en état d’incapacité des deux méthodes nous permettent une comparaison entre ces résultats. Suite à l’élaboration de tableaux et de graphiques permettant de tracer un portait de la situation, cette recherche essaie de démystifier les sources possibles à l’origine de ces différences. Les résultats montrent d’importantes différences entre les projections, spécifiquement pour les individus en état d’incapacité sévère. De plus, lorsqu’on s’intéresse aux variables d’intérêts, on remarque que les différences de projections d’effectifs sont importantes chez les hommes et les gens mariés. Par contre, lorsque les proportions sont analysées, c’est plutôt le groupe d’âges 80 ans et plus ainsi que les projections pour la province du Québec qui créent problème. Ces différences sont attribuables aux caractéristiques d’un modèle de microsimulation, aux populations de départ ainsi qu’aux paramètres définis. Les résultats démontrés dans cette recherche mettent en garde sur les travaux étudiant le nombre d’individus en incapacité dans le futur. Nos deux méthodes ayant des résultats différents, nous ne pouvons pas conclure avec certitude quelle sera la situation dans le futur.

Complexité des homomorphismes de graphes avec listes

Les problèmes de satisfaction de contraintes, qui consistent à attribuer des valeurs à des variables en respectant un ensemble de contraintes, constituent une large classe de problèmes naturels. Pour étudier la complexité de ces problèmes, il est commode de les voir comme des problèmes d'homomorphismes vers des structures relationnelles. Un axe de recherche actuel est la caractérisation des classes de complexité auxquelles appartient le problème d'homomorphisme, ceci dans la perspective de confirmer des conjectures reliant les propriétés algébriques des structures relationelles à la complexité du problème d'homomorphisme. Cette thèse propose dans un premier temps la caractérisation des digraphes pour lesquels le problème d'homomorphisme avec listes appartient à FO. On montre également que dans le cas du problèmes d'homomorphisme avec listes sur les digraphes télescopiques, les conjectures reliant algèbre et complexité sont confirmées. Dans un deuxième temps, on caractérise les graphes pour lesquels le problème d'homomorphisme avec listes est résoluble par cohérence d'arc. On introduit la notion de polymorphisme monochromatique et on propose un algorithme simple qui résoud le problème d'homomorphisme avec listes si le graphe cible admet un polymorphisme monochromatique TSI d'arité k pour tout k ≥ 2.

Modélisation des bi-grappes et sélection des variables pour des données de grande dimension : application aux données d’expression génétique

Les simulations ont été implémentées avec le programme Java.

Le progiciel PoweR : un outil de recherche reproductible pour faciliter les calculs de puissance de certains tests d'hypothèses au moyen de simulations de Monte Carlo

Notre progiciel PoweR vise à faciliter l'obtention ou la vérification des études empiriques de puissance pour les tests d'ajustement. En tant que tel, il peut être considéré comme un outil de calcul de recherche reproductible, car il devient très facile à reproduire (ou détecter les erreurs) des résultats de simulation déjà publiés dans la littérature. En utilisant notre progiciel, il devient facile de concevoir de nouvelles études de simulation. Les valeurs critiques et puissances de nombreuses statistiques de tests sous une grande variété de distributions alternatives sont obtenues très rapidement et avec précision en utilisant un C/C++ et R environnement. On peut même compter sur le progiciel snow de R pour le calcul parallèle, en utilisant un processeur multicœur. Les résultats peuvent être affichés en utilisant des tables latex ou des graphiques spécialisés, qui peuvent être incorporés directement dans vos publications. Ce document donne un aperçu des principaux objectifs et les principes de conception ainsi que les stratégies d'adaptation et d'extension.

Rétro ingénierie des modèles d’objets dynamiques pour JavaScript

La compréhension des objets dans les programmes orientés objet est une tâche impor- tante à la compréhension du code. JavaScript (JS) est un langage orienté-objet dyna- mique, et son dynamisme rend la compréhension du code source très difficile. Dans ce mémoire, nous nous intéressons à l’analyse des objets pour les programmes JS. Notre approche construit de façon automatique un graphe d’objets inspiré du diagramme de classes d’UML à partir d’une exécution concrète d’un programme JS. Le graphe résul- tant montre la structure des objets ainsi que les interactions entre eux. Notre approche utilise une transformation du code source afin de produire cette in- formation au cours de l’exécution. Cette transformation permet de recueillir de l’infor- mation complète au sujet des objets crées ainsi que d’intercepter toutes les modifications de ces objets. À partir de cette information, nous appliquons plusieurs abstractions qui visent à produire une représentation des objets plus compacte et intuitive. Cette approche est implémentée dans l’outil JSTI. Afin d’évaluer l’utilité de l’approche, nous avons mesuré sa performance ainsi que le degré de réduction dû aux abstractions. Nous avons utilisé les dix programmes de réfé- rence de V8 pour cette comparaison. Les résultats montrent que JSTI est assez efficace pour être utilisé en pratique, avec un ralentissement moyen de 14x. De plus, pour 9 des 10 programmes, les graphes sont suffisamment compacts pour être visualisés. Nous avons aussi validé l’approche de façon qualitative en inspectant manuellement les graphes gé- nérés. Ces graphes correspondent généralement très bien au résultat attendu. Mots clés: Analyse de programmes, analyse dynamique, JavaScript, profilage.

Mesures subjectives et épidémiologie : problèmes méthodologiques liés à l'utilisation des techniques psychométriques

L’utilisation des mesures subjectives en épidémiologie s’est intensifiée récemment, notamment avec la volonté de plus en plus affirmée d’intégrer la perception qu’ont les sujets de leur santé dans l’étude des maladies et l’évaluation des interventions. La psychométrie regroupe les méthodes statistiques utilisées pour la construction des questionnaires et l’analyse des données qui en sont issues. Ce travail de thèse avait pour but d’explorer différents problèmes méthodologiques soulevés par l’utilisation des techniques psychométriques en épidémiologie. Trois études empiriques sont présentées et concernent 1/ la phase de validation de l’instrument : l’objectif était de développer, à l’aide de données simulées, un outil de calcul de la taille d’échantillon pour la validation d’échelle en psychiatrie ; 2/ les propriétés mathématiques de la mesure obtenue : l’objectif était de comparer les performances de la différence minimale cliniquement pertinente d’un questionnaire calculée sur des données de cohorte, soit dans le cadre de la théorie classique des tests (CTT), soit dans celui de la théorie de réponse à l’item (IRT) ; 3/ son utilisation dans un schéma longitudinal : l’objectif était de comparer, à l’aide de données simulées, les performances d’une méthode statistique d’analyse de l’évolution longitudinale d’un phénomène subjectif mesuré à l’aide de la CTT ou de l’IRT, en particulier lorsque certains items disponibles pour la mesure différaient à chaque temps. Enfin, l’utilisation de graphes orientés acycliques a permis de discuter, à l’aide des résultats de ces trois études, la notion de biais d’information lors de l’utilisation des mesures subjectives en épidémiologie.

Narration et mathématiques l’utilisation des graphes au cinéma et dans la bande dessinée

Il est possible de modéliser la trame temporelle d’une histoire à l’aide de courbes paramétrées et la juxtaposition de ces différentes courbes permet la construction de graphes. Ce modèle peut servir à la fois à comprendre certaines histoires et à explorer de nouvelles narrations possibles basées sur ces graphes. Dans ce mémoire, nous présentons ce modèle de pair avec les notions mathématiques sur lesquelles il se base. Finalement, nous explorons des différentes narrations possibles qui apparaissent lorsque nous considérons ces graphes sur différentes surfaces.

Analyse de maillages surfaciques par construction et comparaison de modèles moyens et par décomposition par graphes s’appuyant sur les courbures discrètes : application à l’étude de la cornée humaine

Réalisé en cotutelle avec Aix Marseille Université.

The P3 Intersection Graph

We define a new graph operator called the P3 intersection graph, P3(G)- the intersection graph of all induced 3-paths in G. A characterization of graphs G for which P-3 (G) is bipartite is given . Forbidden subgraph characterization for P3 (G) having properties of being chordal , H-free, complete are also obtained . For integers a and b with a > 1 and b > a - 1, it is shown that there exists a graph G such that X(G) = a, X(P3( G)) = b, where X is the chromatic number of G. For the domination number -y(G), we construct graphs G such that -y(G) = a and -y (P3(G)) = b for any two positive numbers a > 1 and b. Similar construction for the independence number and radius, diameter relations are also discussed.

ON THE MEDIAN AND THE ANTIMEDIAN OF A COGRAPH

this paper, the median and the antimedian of cographs are discussed. It is shown that if G, and G2 are any two cographs, then there is a cograph that is both Eulerian and Hamiltonian having Gl as its median and G2 as its antimedian. Moreover, the connected planar and outer planar cographs are characterized and the median and antimedian graphs of connected, planar cographs are listed.

Studies on Some Graph Classes

Department of Mathematics, Cochin University of Science and Technology

Bioactivity Profile of Polyunsaturated Fattyacid extracts from Sardinella longiceps and Sardinella fimbriata – A comparative study

The oceans have proved to be an interminable source of new and effective drugs. Innumerable studies have proved that specific compounds isolated from marine organisms have great nutritional and pharmaceutical value. Polyunsaturated fattyacids (PUFA) in general are known for their dietary benefits in preventing and curing several critical ailments including Coronary heart disease (CHD) and cancers of various kinds. Eicosapentaenoic Acid (EPA) and Docosahexaenoic Acid (DHA) are two PUFA which are entirely marine in origin – and small Clupeoid fishes like sardines are known to be excellent sources of these two compounds. In this study, we selected two widely available Sardine species in the west coast, Sardinella longiceps and Sardinella fimbriata, for a comparative analysis of their bioactive properties. Both these sardines are known to be rich in EPA and DHA, however considerable seasonal variation in its PUFA content was expected and these variations studied. An extraction procedure to isolate PUFA at high purity levels was identified and the extracts obtained thus were studied for anti-bacterial, anti-diabetic and anti-cancerous properties.Samples of both the sardines were collected from landing centre, measured and their gut content analysed in four different months of the year – viz. June, September, December and March. The fish samples were analyzed for fattyacid using FAME method using gas chromatography to identify the full range of fattyacids and their respective concentration in each of the samples. The fattyacids were expressed in mg/g meat and later converted to percentage values against total fatty acids and total PUFA content. Fattyacids during winter season (Dec-Mar) were found to be generally higher than spawning season (June-Sept). PUFA dominated the profiles of both species and average PUFA content was also higher during winter. However, it was found that S. longiceps had proportionately higher EPA as compared to S. fimbriata which was DHA rich. Percentage of EPA and DHA also varied across months for both species – the spawning season seemed to show higher EPA content in S. longiceps and higher DHA content in S. fimbriata. Gut content analysis indicate that adult S. fimbriata is partial to zooplanktons which are DHA rich while adult S. longiceps feed mainly on EPA rich phytoplankton. Juveniles of both species, found mainly in winter, had a gut content showing more mixed diet. This difference in the feeding pattern reflect clearly in their PUFA profile – adult S. longiceps, which dominate the catch during the spawn season, feeding mostly on phytoplankton is concentrated with EPA while the juveniles which are found mostly in the winter season has slightly less EPA proportion as compared to adults. The same is true for S. fimbriata adults that are caught mostly in the spawning season; being rich in DHA as they feed mainly on zooplankton while the juveniles caught during winter season has a relatively lower concentration of DHA in their total PUFA.Various extraction procedures are known to obtain PUFA from fish oil. However, most of them do not give high purity and do not use materials indicated as safe. PUFA extracts have to be edible and should not have harmful substances for applying on mice and human subjects. Some PUFA extraction procedures, though pure and non-toxic, might induce cis-trans conversions during the extraction process. This conversion destroys the benefits of PUFA and at times is harmful to human body. A method free from these limitations has been standardized for this study. Gas Chromatography was performed on the extracts thus made to ensure that it is substantially pure. EPA: DHA ratios for both samples were derived - for S. longiceps this ratio was 3:2, while it was 3:8 for S. fimbriata.Eight common strains of gram positive and gram negative bacterial strains were subjected to the PUFA extracts from both species dissolved in acetone solution using Agar Well Diffusion method. The activity was studied against an acetone control. At the end of incubation period, zones of inhibition were measured to estimate the activity. Minimum inhibitory concentration for each of the active combinations was calculated by keeping p < 0.01 as significant. Four of the bacteria including multi-resistant Staphylococcus aureus were shown to be inhibited by the fish extracts. It was also found that the extracts from S. fimbriata were better than the one from S. longiceps in annihilating harmful bacteria.Four groups of mice subjects were studied to evaluate the antidiabetic properties of the PUFA extracts. Three groups were induced diabetes by administration of alloxan tetra hydrate. One group without diabetes was kept as control and another with diabetes was kept as diabetic control. For two diabetic groups, a prescribed amount of fish extracts were fed from each of the extracts. The biochemical parameters like serum glucose, total cholesterol, LDL & HDL cholesterol, triglycerides, urea and creatinine were sampled from all four groups at regular intervals of 7 days for a period of 28 days. It was found that groups fed with fish extracts had marked improvement in the levels of total LDL & HDL cholesterol, triglycerides and creatinine. Groups fed with extracts from S. fimbriata seem to have fared better as compared to S. longiceps. However, both groups did not show any marked improvement in blood glucose levels or levels of urea.Cell lines of MCF-7 (Breast Cancer) and DU-145 (Prostate Cancer) were used to analyse the cytotoxicity of the PUFA extracts. Both cell lines were subjected to MTT Assay and later the plates were read using an ELISA reader at a wavelength of 570nm. It was found that both extracts had significant cytotoxic effects against both cell lines and a peak cytotoxicity of 85-90% was apparent. IC50 values were calculated from the graphs and it was found that S. longiceps extracts had a slightly lower IC50 value indicating that it is toxic even at a lower concentration as compared to extracts from S. fimbriata.This study summarizes the bioactivity profile of PUFA extracts and provides recommendation for dietary intake; fish based nutritional industry and indigenous pharmaceutical industry. Possible future directions of this study are also elaborated.