Contribution à l'algorithmique anytime (contrôle et conception)

Un des aspects les plus contraignants pour l'implantation d'applications temps-reel est que beaucoup des problemes poses sont de complexite elevee (problemes np-durs) et ont un comportement general difficilement previsible. Une solution est de faire un compromis entre temps de calcul et qualite du resultat, comme le permettent les algorithmes anytime. Cette these apporte deux contributions principales a l'algorithmique anytime : l'une concernant l'ordonnancement d'algorithmes anytime a contrat, l'autre traitant du probleme de conception des algorithmes anytime et plus particulierement de leurs profils de performance. Dans la premiere partie, nous proposons d'etudier une situation dans laquelle un evenement vient interrompre le calcul d'un algorithme anytime a contrat (non-interruptible) et ou il faut fournir une reponse exploitable au moment de cette interruption.La date d'occurence de l'evenement est definie par une probabilite uniforme sur un intervalle. Nous proposons de maximiser la qualite moyenne sur l'intervalle, ce qui permet par definition de donner la meilleure qualite sur la moyenne des occurrences possibles de l'evenement interrupteur. Les problemes de choix du critere de qualite et de la fonction de generation des entrees representatives du fonctionnement de l'algorithme dans son contexte d'utilisation, meme si elles semblent fortement dependantes de l'application, ne sont pas pour autant aises a resoudre. C'est pourquoi nous proposons dans une seconde partie, par l'intermediaire d'experimentations a la fois simples et representatives, de soulever les problemes qu'il est possible de rencontrer dans ce cadre. A l'aide de la theorie de la complexite de kolmogorov, nous etablissons que l'approche aleatoire pour le choix des entrees n'est pas appropriee pour obtenir des profils de performance representatifs des cas reels. Cette approche experimentale montre qu'il n'est pas aise de construire des profils de performance.LILLE1-BU (590092102) / SudocSudocFranceF