Les applications temps réel durs sont celles qui doivent exécuter en respectant des contraintes temporelles. L'ordonnancement temps réel a bien été étudié sur mono-processeurs depuis plusieurs années. Récemment, l'utilisation d'architectures multiprocesseurs a augmenté dans les applications industrielles et des architectures parallèles sont proposées pour que le logiciel devienne compatible avec ces plateformes. L'ordonnancement multiprocesseurs de tâches parallèles dépendantes n'est pas une simple généralisation du cas mono-processeur et la problématique d'ordonnancement devient plus complexe et difficile.
Dans cette thèse, nous étudions le problème d'ordonnancement temps réel de graphes de tâches parallèles acycliques sur des plateformes multiprocesseurs. Dans ce modèle, un graphe est composé d'un ensemble de sous-tâches dépendantes sous contraintes de précédence qui expriment les relations de précédences entre les sous-tâches. L'ordre d'exécution des sous-tâches est dynamique, c'est-à-dire que les sous-tâches peuvent s'exécuter en parallèle ou séquentiellement par rapport aux décisions de l'ordonnanceur temps réel. Pour traiter les contraintes de précédence, nous proposons deux méthodes pour l'ordonnancement des graphes : par transformation du modèle de graphe de sous tâches parallèles en un modèle de tâches séquentielles indépendantes, plus simple à ordonnancer et par ordonnancement direct des graphes en prenant en compte les relations de dépendance entre les sous-tâches. Nous proposons un ordonnancement des graphes en prenant directement en compte les paramètres temporels des graphes et un ordonnancement au niveau des sous-tâches, par rapport à des paramètres temporels attribués aux sous-tâches par un algorithme spécifique.
Enfin, nous prouvons que les deux méthodes d'ordonnancement de graphes ne sont pas comparables. Nous fournissons alors des résultats de simulation pour comparer ces méthodes en utilisant les algorithmes d'ordonnancement globaux EDF et DM. Nous avons développé un logiciel nommé YARTISS pour générer des graphes aléatoires et réaliser les simulations / The interest for multiprocessor systems has recently been increased in industrial applications, and parallel programming API's have been introduced to benefit from new processing capabilities. The use of multiprocessors for real-time systems, whose execution is performed based on certain temporal constraints is now investigated by the industry. Real-time scheduling problem becomes more complex and challenging in that context. In multiprocessor systems, a hard real-time scheduler is responsible for allocating ready jobs to available processors of the systems while respecting their timing parameters.
In this thesis, we study the problem of real-time scheduling of parallel Directed Acyclic Graph (DAG) tasks on homogeneous multiprocessor systems. In this model, a DAG task consists of a set of subtasks that execute under precedence constraints. At all times, the real-time scheduler is responsible for determining how subtasks execute, either sequentially or in parallel, based on the available processors of the system. We propose two DAG scheduling approaches to determine the execution form of DAG tasks. The first approach is the DAG Stretching algorithm, from the Model Transformation approach, which forces DAG tasks to execute as sequentially as possible. The second approach is the Direct Scheduling, which aims at scheduling DAG tasks while respecting their internal dependencies. We provide real-time schedulability analyses for Direct Scheduling at DAG-Level and at Subtask-Level.
Due to the incomparability of DAG scheduling approaches, we use extensive simulations to compare performance of global EDF with global DM scheduling using our simulation tool YARTISS

Dans cette thèse, nous nous intéressons à la coloration circulaire des graphes planaires. Des bornes supérieures ont été données pour des graphes avec degré maximum borné, avec girth, la longueur de son plus petit cycle, bornée, avec des cycles manquants, etc. Ici nous donnerons de nouvelles bornes pour les graphes avec degré moyen maximum borné. Nous étudions également la coloration totale et la coloration (d,1)-totale de plusieurs familles infinies de graphes. Nous décrivons le nouveau concept de coloration (d,1)-totale circulaire. Enfin, nous discutons les conditions nécessaires pour qu'un graphe planaire admette une coloration acyclique par listes de taille 4. / In this thesis, we study the circular coloring of planar graphs. Upper bounds have been given for graphs with bounded maximum degree, with bounded girth, that is the length of its smallest cycle, with missing cycles, and so on. It has also been studied for graphs with bounded maximum average degree. Here we give new upper bounds for that latter case. We also study the total coloring and ($d,1$)-total labeling of a few infinite families of graphs and describe the new concept of circular ($d,1$)-total labeling of graphs. In the last part, we will discuss conditions for a planar graph to be acyclically $4$-choosable.

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. / Recently, subjective measurements have increasingly been used in epidemiology, alongside the growing will to integrate individuals’ point of view on their health in studies on diseases or health interventions. Psychometrics includes statistical methods used to develop questionnaires and to analyze questionnaire data. This doctoral dissertation aimed to explore methodological issues raised by the use of psychometric techniques in epidemiology. Three empirical studies are presented and cover 1 / the validation stage of a questionnaire: the objective was to develop, using simulated data, a tool to determine sample size for internal validity studies on psychiatric scale; 2 / the mathematical properties of the subjective measurement: the objective was to compare the performances of the minimal clinically important difference of a questionnaire, assessed on data from a cohort study, computed using the classical test theory (CTT) framework or the item response theory framework (IRT); 3 / its use in a longitudinal design: the objective was to compare, using simulated data, the performances of a statistical method aimed to analyze the longitudinal course of a subjective phenomenon measured using the CTT or IRT framework, especially when some of the available items used for its measurement differ at each time of data collection. Finally, directed acyclic graphs were used to discuss the results from these three studies and the concept of information bias when subjective measurements are used in epidemiology.

No description available.

La visualisation d'information est une approche des plus prometteuses pour l'exploration, l'analyse et la comprehension de donnees. Dans le cadre de cette these, les dierentes collaborations avec les utilisateurs naux de nos methodes (biologistes et geographes) ont permis d'elaborer de nouvelles visualisations et interactions adaptees aux besoins speciques de leur domaine. La notion d'exploration \focus+contexte" est ici centrale. Nous l'avons abordee tant au travers de la visualisation de donnees multidimensionnelles que de graphes hierarchiques. Une methode permettant de visualiser et d'interagir sur des donnees multidimensionnelles est proposee. Cette methode permet d'identier visuellement des correlations non lineaires a l'aide d'une matrice de graphes de correlation. Nous presentons alors une technique permettant de visualiser de facon interactive les structures hierarchiques sous forme de graphes orientes acycliques (DAGs). Les resultats d'une evaluation formelle de la methode sont alors presentes. Une extension a des donnees plus massive utilisant des techniques de visualisation "focus+context" est alors proposee.

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.

No description available.

Les événements spatio-temporels regroupent une large diversité de phénomènes comportant des caractéristiques propres. Par exemple, l’étude de flux migratoires se révèle ainsi très différente de l’étude de propagation de maladies. En effet, le domaine d’intérêt de la première porte sur le suivi des trajectoires, tandis que celui de la deuxième porte sur les facteurs de la propagation. De plus, chaque classe d’un problème spatio-temporel peut être abordée différemment, que l’on considère ou non un voisinage spatial, une caractérisation des objets d’étude unique ou multiple, ou bien une (in)dépendance entre les événements. Ainsi, les techniques de fouilles de données développées sont souvent restées spécifiques à une sous-classe de problème spatio-temporel, c’est-à-dire sous un ensemble restreint d’hypothèses.Or, pour réussir à dégager des connaissances nouvelles à partir de données, il est nécessaire d’élargir cet ensemble d’hypothèses, c’est-à-dire élargir le champs des possibles quant aux corrélations qu’il peut exister entre événements. Nous proposons donc une modélisation de ces phénomènes spatio-temporels permettant de prendre en compte plus de considérations que dans l’état de l’art. En outre, cette modélisation permet d’exprimer des événements qui existent dans les phénomènes d’érosion : un objet d’étude peut se diviser en plusieurs objets, ou fusionner avec d’autres objets pour n’en former qu’un seul. Plus précisément, nous modélisons les dynamiques spatio-temporelles sous la forme d’un unique graphe orienté, que la composante temporelle des problèmes rend acyclique, et dont les sommets sont attribués par plusieurs caractéristiques. / Spatio-temporal events denote a large range of phenomena with different characteristics. For example, migration flows studies appear to be very different from disease spread studies. Indeed, interestingness of the first relies on tracking trajectories, whereas the second is about finding the factors of spread. Moreover, each class of a spatio-temporal problem can be tackled differently, depending on which parameters are considered: the studied spatial neighbourhood, the number of characteristics associated with the objects, or whether events are supposed correlated or independent. As a result, data mining techniques are often specificto a sub-class of spatio-temporal problem, that is to say, to a limited set of hypothesis.In order to bring out new knowledge from data, it seems to be necessary to enlarge this set of hypothesis, that is to say, to widen the field of possibilities regarding correlations that may exist between events. For this, we propose a new model that allows to take into account more considerations than existing studies. For example, this representation allows to model the complex spatio-temporal dynamic of erosion phenomenon: an object can be split up in several other objects, or can merge with other objects into one. More precisely, we use a single directed graph, that becomes acyclic thanks to the temporal component of the problem, and that is attributed by several characteristics.

Dans cette thèse nous étudions quatre problèmes de théorie des graphes. En particulier,Nous étudions le problème du cycle hamiltonien dans les line graphes, et aussi nous prouvons l’existence de cycles hamiltoniens dans certains sous graphes couvrants d’un line graphe. Notre résultat principal est: Si L(G) est hamiltonien, alors SL(G) est hamiltonien. Grâce à ce résultat nous proposons une conjecture équivalente à des conjectures célèbres. Et nous obtenons deux résultats sur les cycles hamiltoniens disjoints dans les line graphes.Nous considérons alors la bipancyclicité résistante aux pannes des graphes de Cayley engendrés par transposition d’arbres. Nous prouvons que de tels graphes de Cayley excepté le “star graph” ont une bipancyclicité (n − 3)-arête résistante aux pannes.Ensuite nous introduisons la coloration des arcs d’un digraphe sommet distinguant. Nous étudions la relation entre cette notion et la coloration d’arêtes sommet distinguant dans les graphes non orientés. Nous obtenons quelques résultats sur le nombre arc chromatique des graphes orientés (semi-)sommet-distinguant et proposons une conjecture sur ce paramètre. Pour vérifier cette conjecture nous étudions la coloration des arcs d’un digraphe sommet distinguant des graphes orientés réguliers.Finalement nous introduisons la coloration acyclique des arcs d’un graphe orienté. Nous calculons le nombre chromatique acyclique des arcs de quelques familles de graphes orientés et proposons une conjecture sur ce paramètre. Nous considérons les graphes orientés de grande maille et utilisons le Lemme Local de Lovász; d’autre part nous considérons les graphes orientés réguliers aléatoires. Nous prouvons que ces deux classes de graphes vérifient la conjecture. / In this thesis, we study four problems in graph theory, the Hamiltonian cycle problem in line graphs, the edge-fault-tolerant bipancyclicity of Cayley graphs generated by transposition trees, the vertex-distinguishing arc colorings in digraph- s and the acyclic arc coloring in digraphs. The first two problems are the classic problem on the cycles in graphs. And the other two arc coloring problems are related to the modern graph theory, in which we use some probabilistic methods. In particular,We first study the Hamiltonian cycle problem in line graphs and find the Hamiltonian cycles in some spanning subgraphs of line graphs SL(G). We prove that: if L(G) is Hamiltonian, then SL(G) is Hamiltonian. Due to this, we propose a conjecture, which is equivalent to some well-known conjectures. And we get two results about the edge-disjoint Hamiltonian cycles in line graphs.Then, we consider the edge-fault-tolerant bipancyclicity of Cayley graphs generated by transposition trees. And we prove that the Cayley graph generated by transposition tree is (n − 3)-edge-fault-tolerant bipancyclic if it is not a star graph.Later, we introduce the vertex-distinguishing arc coloring in digraphs. We study the relationship between the vertex-distinguishing edge coloring in undirected graphs and the vertex-distinguishing arc coloring in digraphs. And we get some results on the (semi-) vertex-distinguishing arc chromatic number for digraphs and also propose a conjecture about it. To verify the conjecture we study the vertex-distinguishing arc coloring for regular digraphs.Finally, we introduce the acyclic arc coloring in digraphs. We calculate the acyclic arc chromatic number for some digraph families and propose a conjecture on the acyclic arc chromatic number. Then we consider the digraphs with high girth by using the Lovász Local Lemma and we also consider the random regular digraphs. And the results of the digraphs with high girth and the random regular digraphs verify the conjecture.

Dans un premier chapitre, nous avons présenté un historique succinct de la chimiothérapie antivirale et l'utilisation d'analogues nucléos(t)idiques. Nous nous sommes focalisés en particulier sur les nucléosides phosphonates acycliques (ANP) en tant qu'antiviraux potentiels. Dans un second chapitre, nous avons décrit la synthèse de β-céto, β-hydroxylamino et β-O-(benzyl)hydroxylamino ANP dérivés de l'adénine et de la cytosine. Les isomèrs (R) et (S)-β-hydroxy-ANP ont été préparés par dédoublement du racémique correspondant avec le (S)-MPA et l'attribution des configurations absolues a été effectuée par RMN et calculs de modélisation moléculaire. Nous avons aussi développé une méthodologie de synthèse de β-azido-ANP, ces derniers étant utilisés pour la préparation de β-amino-ANP par hydrogénation catalytique. Dans un troisième chapitre, nous avons présenté la synthèse des 2H-azirine et cis-aziridne-ANP et examiné lʹ ouverture de cycle comme voie d'accès à des ANP α,β-fonctionnalisés. Les propriétés biologiques de ces nouveaux ANP ont été évaluées en culture cellulaire sur un certain nombre de virus à ADN et ARN. / In the first chapter, we presented a brief history of antiviral chemotherapy and use of nucleos(t)ide analogues, especially acyclic nucleoside phosphonates as potential antiviral agents. In the chapter-II we have successfully synthesized ¦Â-keto, ¦Â-hydroxylamino and ¦Â-O-(benzyl)hydroxylamino ANPs of adenine and cytosine derivatives. Then (R) and (S)-¦Â-hydroxy-ANPs were prepared via chiral resolution of racemic ¦Â-hydroxy-ANPs with (S)-MPA and assignment of absolute configuration was achieved using NMR and molecular modeling studies. We also developed a methodology for the synthesis of ¦Â-azido-ANPs and those were used for the preparation of ¦Â-amino-ANPs by catalytic hydrogenation. In third chapter, we synthesized 2H-azirine and cis-aziridine-ANPs and explored their ring opening to functionalized ¦Á,¦Â-ANPs. The novel ANPs obtained during this study were evaluated for their inhibitory effect on a number of DNA and RNA viruses in cell culture experiments.