Cette thèse développe une méthodologie pour résoudre les problèmes d'ordonnancement de programmes conditionnels où savoir si une tâche doit être exécutée n'est pas connue à l'avance mais dynamiquement. Le modèle utilisé est à base d'automates temporisés représentant l'espace d'états à explorer. Le problème est donc formulé comme le calcul d'une stratégie gagnante (pire cas optimale) dans un jeu contre l'environnement. Dans un premier temps nous étudions le problème d'ordonnancement sur graphes de tâches déterministe puis nous étendons l'étude au problème d'ordonnancement avec incertitude conditionnelle. Pour les deux problèmes nous étudions différentes classes d'ordonnancements et de stratégies pour réduire l'espace d'états, des décompositions en chaînes pour réduire sa taille, puis nous investiguons plusieurs classes d'algorithmes exactes pour en évaluer l'efficacité et à partir desquels nous dérivons de bonnes heuristiques. Des résultats expérimentaux sur plusieurs exemples de benchmarks sont présentés afin de montrer l'efficacité de chaque algorithme et la précision des heuristiques proposées, puis des bornes théoriques sont déduites pour prouver la garantie de performance pire cas de chaque heuristique.

La théorie des processus empiriques joue un rôle central en statistique, puisqu'elle concerne l'ensemble des résultats limites généraux se rapportant aux échantillons aléatoires. En particulier, des lois uniformes du logarithme ont permis d'aborder de manière systématique la convergence en norme sup des estimateurs à noyau. Dans cette thèse, nous obtenons premièrement des lois fonctionnelles uniformes du logarithme pour les incréments du processus des quantiles normé, qui permettent d'établir des propriétés nouvelles des estimateurs basés sur les k-plus proches voisins. Le même type de résultat est ensuite obtenu pour les incréments du processus empirique de Kaplan-Meier, conduisant naturellement à des lois du logarithme uniformes pour des estimateurs de la densité et du taux de mortalité en présence de censure à droite. Dans le cas de la régression multivariée, des lois analogues sont obtenues pour des estimateurs à noyau, notamment dans le cas censuré. Enfin, nous développons un estimateur non paramétrique de la régression sous l'hypothèse du modèle additif dans le cas de censure à droite, permettant de se défaire du fléau de la dimension. Cet estimateur repose essentiellement sur la méthode d'intégration marginale.

Thèse d'exercice : Médecine. Médecine générale : Paris 12 : 2007. / Titre provenant de l'écran-titre. 89 f. : ill. Bibliogr. f. 63-71.

Technology scaling in the nanometer era comes with a significant amount of process variation, leading to lower yield and new types of defective parts. These challenges necessitate robust design to ensure adequate yield, and smarter testing to screen out bad chips. Statistical static timing analysis (SSTA) en- ables this but suffers from crude approximation algorithms. This dissertation first studies the underlying theories of timing graphs and proposes two fundamental techniques enhancing the core statistical timing algorithms. We first propose the refactoring technique to capture topological correlation. Static timing analysis is based on levelized breadth-first traversal, which is a fundamental graph traversal technique and has been used for static timing analysis over the past decades. We show that there are numerous alternatives to the traversal because of an algebraic property, the distributivity of addition over maximum. This new interpretation extends the degrees of freedom of static timing analysis, which is exploited to improve the accuracy of SSTA. We also propose a novel operator for computing joint probabilities in SSTA. In many SSTA applications, this is very common but is done using the max operator which results in much error due to the linear approximation. The new operator provides significantly higher accuracy at a small cost of run time. Second, based on the two fundamental studies, this dissertation devel- ops three applications. We propose a criticality computation method that is essential to robust design and test synthesis; The proposed method, combined with the two fundamental techniques, achieves drastic accuracy improvement over the state-of-the-art method, demonstrating the benefits in practical ap- plications. We formulate the statistical path selection problem for at-speed test as a gambling problem and present an elegant solution based on the Kelly criterion. To circumvent the coverage loss issue in statistical path selection, we propose a testability driven approach, making it a practical solution for coping with parametric defects. / text

The international air transportation industry has historically been a paradox. While the industry enables globalization, historically, the international air transportation regulatory regime has been largely mired in protectionism. This restrictive regime was developed by national actors, who either owned or heavily subsidized their domestic carriers, and guarded their interests very closely, thus insulating the industry from large levels of foreign competition. This paradox of international air transportation continued until the development of convergence in regulatory policy through the 2007 ‘open skies-plus’ air transportation agreement between the United States (US) and the European Union (EU). This thesis examines the developmental process of this agreement as an examination of policy convergence theory, in order identify the explanatory powers leading to the formation of the ‘open skies-plus’ agreement. To identify the explanatory powers, a comparative analysis is established, using two historical reference points, t(0) and t(1), as case studies. This thesis uses two mechanisms for the development of policy convergence, international harmonization and regulatory competition, to identify why the convergence took place at this specific time and why it was set at this specific level of regulation. Using these mechanisms, the 2002 European Court of Justice (ECJ) ‘open skies’ ruling is identified as the explanatory power for the convergence of policy in this field, and the precedent set by the previous bilateral agreement between the US and the Netherlands is identified as establishing the standards of regulation in the 2007 ‘open skies-plus’ agreement. The thesis concludes with an examination of the prospects for further liberalization of transatlantic air transportation, as well as recommendations for the continued development of the field.

Le Network Calculus est une théorie visant à calculer des bornes pire-cas sur les performances des réseaux de communication. Le réseau est modélisé par un graphe orienté où les noeuds représentent des serveurs, et les flux traversant le réseau doivent suivre les arcs. S'ajoutent à cela des contraintes sur les courbes de trafic (la quantité de données passées par un point depuis la mise en route du réseau) et sur les courbes de service (la quantité de travail fournie par chaque serveur). Pour borner les performances pire-cas, comme la charge en différents points ou les délais de bout en bout, ces enveloppes sont combinées à l'aide d'opérateurs issus notamment des algèbres tropicales : min, +, convolution-(min, +)... Cette thèse est centrée sur l'algorithmique du Network Calculus, à savoir comment rendre effectif ce formalisme. Ce travail nous a amené d'abord à comparer les variations présentes dans la littérature sur les modèles utilisés, révélant des équivalences d'expressivité comme entre le Real-Time Calculus et le Network Calculus. Dans un deuxième temps, nous avons proposé un nouvel opérateur (min, +) pour traiter le calcul de performances en présence d'agrégation de flux, et nous avons étudié le cas des réseaux sans dépendances cycliques sur les flux et avec politique de service quelconque. Nous avons montré la difficulté algorithmique d'obtenir précisément les pires cas, mais nous avons aussi fourni une nouvelle heuristique pour les calculer. Elle s'avère de complexité polynomiale dans des cas intéressants.

Une approche fondamentale pour la résolution de problémes de contrôle optimal est basée sur le principe de programmation dynamique. Ce principe conduit aux équations d'Hamilton-Jacobi, qui peuvent être résolues numériquement par des méthodes classiques comme la méthode des différences finies, les méthodes semi-lagrangiennes, ou les schémas antidiffusifs. À cause de la discrétisation de l'espace d'état, la dimension des problèmes de contrôle pouvant être abordés par ces méthodes classiques est souvent limitée à 3 ou 4. Ce phénomène est appellé malédiction de la dimension. Cette thèse porte sur les méthodes numériques max-plus en contôle optimal deterministe et ses analyses de convergence. Nous étudions et developpons des méthodes numériques destinées à attenuer la malédiction de la dimension, pour lesquelles nous obtenons des estimations théoriques de complexité. Les preuves reposent sur des résultats de théorie de Perron-Frobenius non linéaire. En particulier, nous étudions les propriétés de contraction des opérateurs monotones et non expansifs, pour différentes métriques de Finsler sur un cône (métrique de Thompson, métrique projective d'Hilbert). Nous donnons par ailleurs une généralisation du "coefficient d'ergodicité de Dobrushin" à des opérateurs de Markov sur un cône général. Nous appliquons ces résultats aux systèmes de consensus ainsi qu'aux équations de Riccati généralisées apparaissant en contrôle stochastique.

Standard measures used in animal welfare assessments include animal-based measures obtained by observing animals, resource-based measures obtained by observing facilities, and management-based measures obtained by interviewing farmers and checking records. Animal welfare assessments are composed of a variety of measures and can be very different from each other. The objectives of the research presented in this thesis were to investigate inter-observer reliability of three swine welfare assessment programs (ACA™, PQA Plus®, and Welfare Quality®), and to determine the concordance of rankings across the 3 assessments. All assessments and all types of measures were found to be highly reliable. Moderate concordance was found for the rankings of farms across all three assessments. The lowest ranked farms were correlated, indicating that all assessments identified the farms with the lowest levels of animal welfare. Results of this study can be used to identify the best measures and revise current on-farm animal welfare assessments. / Canadian Swine Research and Development Cluster, a Growing Canadian Agri-Innovation Program – Canadian Agri-Science Cluster Initiative of Agriculture and Agri-Food Canada (AAFC); and the Ontario Pork Council

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. / Let G = (V,E) be a finite simple graph. We denote the number of vertices in a longest path in G by τ(G). A partition (A,B) of V is called an (a,b)−partition if τ(⟨A⟩) ≤ a and τ(⟨B⟩) ≤ b. If G can be (a,b)−partitioned for every pair of positive integers (a, b) satisfying a + b = τ (G), we say that G is τ −partitionable. The following conjecture, called The Path Partition Conjecture, has been stated by Lovász and Mihók in 1981 : every graph is τ−partitionable. Since that, many researchers prove that this conjecture is true for several classes of graphs and digraphs. This study summarizes the different results about the Path Partition conjecture.

La vérification en ligne de spécifications formelles permet de créer des détecteurs d'erreur dont le pouvoir de détection dépend en grande partie du formalisme vérifié à l'exécution. Plus le formalisme est puissant plus la séparation entre les exécutions correctes et erronées peut être précise. Cependant, l'utilisation des vérifieurs en-ligne dans le but de détecter des erreurs est entravée par deux problèmes récurrents : le coût à l'exécution de ces vérifications, et le flou entourant les propriétés sémantiques exactes des signaux d'erreur ainsi générés. L'objectif de cette thèse est de clarifier les conditions d'utilisation de tels détecteurs dans le cadre d'applications " temps réel " critiques. Dans ce but, nous avons donné l'interprétation formelle de la notion d'erreur comportementale " temps réel". Nous définissions la propriété de détection " au plus tôt " qui permet de d'identifier la classe des détecteurs qui optimisent la latence de détection. Pour illustrer cette classe de détecteurs, nous proposons un prototype qui vérifie un comportement décrit par un automate temporisé. La propriété de détection au plus tôt est atteinte en raisonnant sur l'abstraction temporelle de l'automate et non sur l'automate lui-même. Nos contributions se déclinent dans trois domaines, la formalisation de la détection au plus tôt, sa traduction pour la synthèse de détecteurs d'erreur à partir d'automate temporisés, puis le déploiement concret de ces détecteurs sur une plate-forme de développement temps réel, Xenomai.