Contribution de l'algorithme anytime : contrôle et conception Algorithme flexible Complexité algorithmique Complexité calcul Système temps réel Ordonnancement Complexité Kolmogorov 004.0151 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. Electronic Thesis or Dissertation Text FR application/pdf 1 : 8612 Ko https://pepite-depot.univ-lille.fr/LIBRE/Th_Num/2000/50376-2000-382.pdf Delhay Arnaud 2000-01-01 Informatique Université Lille1 - Sciences et Technologies thesis.degree.grantor_1 026404184 Doctorat non oui Daucher Max intervenant_1 Vanheeghe Philippe intervenant_2 intervenant_3 Daucher Max Vanheeghe Philippe Université Lille1 - Sciences et Technologies ASCII PDF Version complète 8819169