• Langue : Français
• Discipline : Informatique
• Identifiant : Inconnu
• Type de thèse : Doctorat
• Date de soutenance : 01/01/2000

Résumé en langue originale

Un des aspects les plus contraignants pour l'implantation d' applications temps-réel est que beaucoup des problèmes posés sont de complexité élevée (problèmes NP-durs) et ont un comportement général difficilement prévisible. Une solution est de faire un compromis entre temps de calcul et qualité du résultat, comme le permettent les algorithmes anytime. Cette thèse apporte deux contributions principales à l'algorithme anytime : l'une concernant l'ordonnancement d'algorithme anytime à contrat, l'autre traitant du problème de conception des algorithmes anityme et plus particulièrement de leurs profils de performance. Dans la première partie, nous proposons d'étudier une situation dans laquelle un événement vient interrompre le calcul d'un algorithme anytime à contrat (non-interruptible) et où il faut fournir une réponse exploitable au moment de cette interruption. La date d'occurrence de l'événement est définie par une probabilité uniforme sur un intervalle. Nous proposons de maximiser la qualité moyenne sur l'intervalle, ce qui permet par définition de donner la meilleure qualité sur la moyenne des occurrences possibles de l'événement interrupteur. Les problèmes de choix du critère de qualité et de la fonction de génération des entrées représentatives du fonctionnement de l'algorithme dans son contexte d'utilisation, même si elles semblent fortement dépendantes de l'application, ne sont pas pour autant aisés à résoudre. C'est pourquoi nous proposons dans une seconde partie, par l'intermédiaire d'expérimentations à la fois simples et représentatives, de soulever les problèmes qu'il est possible de rencontrer dans ce cadre. A l'aide de la théorie de la complexité de Kolmogorov, nous établissons que l'approche aléatoire pour le choix des entrées n'est pas appropriées pour obtenir des profils de performance représentatifs des cas réels. Cette approche expérimentale montre qu'il n'est pas aisé de construire des profils de performance.