L'évolution technologique et scientifique à l'heure actuelle se répercute, en tout ou en partie, sur le domaine de la CAO. On assiste à une universalisation des techniques de conception, qui se basent souvent sur les mêmes algorithmes, que ce soit pour l'industrie aéronautique, pour la médecine ou pour d'autres domaines. Cette pluridisciplinarité naît des différentes vues de la conception, qui ne se fait plus seulement par des ingénieurs, mais par un public très varié, et qui entraîne, à son tour, des différentes techniques d'interaction. Pour répondre à cette diversité, les systèmes de CAO devraient assister l'utilisateur par des outils de modélisation adaptés. Une approche dans ce sens serait d'intégrer les déformations avec des contraintes métier. Ainsi, le concepteur pourrait se concentrer sur son métier plutôt que sur le modèle géométrique, laissant au système la tache du passage des paramètres métier aux paramètres géométriques, applicables au modèle. L'étude présente se place dans le contexte du projet DIJA, avec le but de créer un modeleur de déformation de surfaces avec un comportement métier bien précis, non pas en utilisant le modèle géométrique sous-jacent, tel que réalisé jusqu'à présent, mais en prenant en compte une triangulation de la surface aussi fine que nécessaire. L'étude permet de démontrer également le passage des paramètres métier aux paramètres géométriques et l'interaction avec l'utilisateur des différents niveaux de l'architecture du système, selon ses compétences.

La théorie des automates est apparue pour résoudre des problèmes aussi bien pratiques que théoriques, et ceci dès le début de l'informatique. Désormais, les automates font partie des notions fondamentales de l'informatique, et se retrouvent dans la plupart des logiciels. En 1974, Samuel Eilenberg proposa un modèle de calcul qui unifie la plupart des automates (transducteurs, automates à pile et machines de Turing) et qui a une propriété de modularité intéressante au vu d'applications reposant sur différentes couches d'automates ; comme cela peut être le cas en linguistique computationnelle. Nous proposons d'étudier les techniques permettant d'avoir des machines d'Eilenberg effectives. Cette étude commence par la modélisation de relations calculables à base de flux, puis continue avec l'étude de la simulation des machines d'Eilenberg définies avec ces relations. Le simulateur est un programme fonctionnel énumérant progressivement les solutions, en explorant un espace de recherche selon différentes stratégies. Nous introduisons, en particulier, la notion de machine d'Eilenberg finie pour laquelle nous fournissons une preuve formelle de correction de la simulation. Les relations sont une première composante des machines d'Eilenberg, la deuxième composante étant son contrôle, qui est défini par un automate fini. Dans ce contexte, on peut utiliser une expression régulière comme syntaxe pour décrire la composante de contrôle d'une machine d'Eilenberg. Récemment, un ensemble de travaux exploitant la notion de dérivées de Brzozowski, a été la source d'algorithmes efficaces de synthèse d'automates non-déterministes à partir d'expressions régulières. Nous faisons l'état de l'art de ces algorithmes, tout en donnant une implémentation efficace en OCaml permettant de les comparer les uns aux autres.

Mobile Ad hoc networks are a step closer to the vision of pervasive computing where all devices dynamically discover each other, organize communication networks between themselves and share resources/information to provide seamless service to the end-user. But providing any reliable service over such a network requires a secure and well-functioning network. Lack of infrastructure, energy-constrained nature of devices and high dynamism in the network makes the task of securing such networks quite challenging. In this thesis we propose cryptographic protocols, which are a stepping stone to a secure ad hoc network. In particular, we contribute to the areas of key establishment and secure routing in ad hoc networks. Key establishment is concerned with making available cryptographic keys to the devices, necessary for participating in the security services of the network. On the other hand routing needs to be secured in such networks as almost all nodes need to participate in the routing process (for eciency reasons) and presence of one malicious node could easily have drastic consequences on the routing performance of the whole network. Thus security checks are required to prevent such malicious nodes from hampering the routing process and to recover from it in case they do succeed. Our rst result is a new group key agreement protocol which is especially suitable for ad hoc networks but also outperforms most known protocols for traditional networks as well. The protocol adapts well to the dynamics of the network and is robust enough to deal with message losses and link failures. It requires little self-organization by the nodes in the network. We present some modied versions of the same and vii tel-00469429, version 1 - 1 Apr 2010 security proofs showing that the security of these protocols is tightly related to the security of the Decisional Die-Hellman problem. We also discuss issues related to implementation of this protocol in real scenarios. Our second result is the introduction of the notion of an Aggregate Designated Verier Signature (ADVS) scheme. An ADVS scheme allows ecient aggregation of multiple signatures on dierent messages designated to the same verier. We show how this primitive can be eciently utilized to secure reactive routing protocols in ad hoc networks. We provide a security model to analyze such schemes and propose an ADVS scheme which aggregates signatures more eciently than existing schemes.

With the advent of portable devices (e.g., smartphones) and the advances in wireless networking technologies (e.g., WLAN, GPRS, UMTS), the vision of ubiquitous computing is becoming a reality. It aims to facilitate user tasks through the seamless utilization of heterogeneous computing and communication capabilities (represented as services) available in the environment. Service discovery, which is necessary for achieving the above goal, must be aware of the service's non-functional properties due to the challenges posed by ubiquitous computing, such as device portability and mobility. This thesis proposes an overall solution that supports QoS-aware service discovery in ubiquitous computing environments. Our contribution lies in substantiating QoS awareness in the following three aspects. Firstly, during the process of discovering services, the expiring wireless links resulting from device mobility are identified and avoided since they cause service failures and thus hamper service reliability. Secondly, as mu tiple services can be discovered, a comprehensive utility function is proposed to evaluate services in terms of their various non-functional properties, meanwhile taking into account the service user's preferences among them, for the purpose of selecting the best one. Thirdly, to avoid untrustworthy services, a distributed reputation mechanism is proposed to facilitate the evaluation of the service host's trustworthiness. The above three proposed solutions are extensively evaluated respectively, based on analysis and simulation. They are further incorporated into a middleware that supports QoS aware Web service discovery in ubiquitous computing environments. A prototype implementing the middleware is deployed and evaluated. The results show that the overhead introduced by QoS awareness seems reasonable.

Intergiciel Sémantique pour les Services de l'Informatique Diffuse

Le nombre croissant des terminaux (PDAs, ordinateurs portables, téléphones) et l'expansion des réseaux sans fil (GSM, GPRS, UMTS, WLAN, Bluetooth) témoignent de la demande croissante des utilisateurs pour un accès à des ressources telles que des données ou des services applicatifs, à tout moment, et, n'importe où. Dans ce contexte, les réseaux ad hoc peuvent jouer un rôle important puisqu'ils ne nécessitent pas d'infrastructures pour communiquer, ils peuvent également être utilisés lorsque le déploiement d'infrastructures est coûteux ou sans objet, ou encore pour accroître la portée des réseaux à base d'infrastructure. De plus ces réseaux ad hoc peuvent opérer de façon autonome ou être connectés à d'autres types de réseaux afin de fournir à l'utilisateur un accès vers un ensemble plus important de ressources. Dans les réseaux filaires ou sans fil basés sur des infrastructures, les solutions proposées afin de localiser les ressources se basent majoritairement sur un répertoire centralisant les informations relatives aux ressources du réseau. Ces solutions sont inexploitables dans les réseaux ad hoc en raison du manque de connectivité induit notamment par les changements de topologie du réseau, et par l'épuisement des réserves énergétiques des batteries. Les solutions proposées pour les réseaux ad hoc se basent quant à elle sur des techniques de diffusion coûteuses, en terme de bande passante, et conduisent à surcharger le réseau. Cette inefficacité des solutions existantes demeure l'un des freins majeurs au développement d'applications pour les réseaux sans fil intégrant des réseaux ad hoc. L'objectif de cette thèse est d'offrir une localisation efficace des ressources afin de garantir un accès transparent aux ressources disponibles dans un environnement intégrant des réseaux ad hoc. Tout d'abord, cette thèse présente les travaux de recherche portant sur la localisation des terminaux et des ressources dans un réseau ad hoc. Nous introduisons ensuite les techniques que nous proposons pour effectuer une localisation des ressources adaptée aux caractéristiques des réseaux ad hoc (e.g., densité des nœuds, surface du réseau), et cela afin de limiter le trafic généré par cette localisation. Ceci nous conduit notamment à aborder distinctement la localisation de ressources dans les réseaux ad hoc à petite et large échelle. La première approche que nous proposons est entièrement distribuée. Les terminaux coopèrent ensemble afin de localiser des ressources sur le réseau. De plus, ce protocole inclut des techniques de caching et de préchargement afin d'améliorer les performances lors de la localisation et lors de l'accès aux ressources. Afin d'effectuer une localisation efficace des ressources dans un réseau ad hoc à grande échelle, nous introduisons une solution semi-distribuée basée sur un ensemble de répertoire déployés dynamiquement sur le réseau ad hoc (ou possiblement hybride). Ces contributions sont complétées par une évaluation des performances incluant une étude théorique et pratique basée sur des simulations et des expérimentations. Enfin, nous présentons une mise en œuvre de notre protocole de localisation de ressources dans le contexte des services Web. Cet intergiciel supporte un accès ubiquitaire à des services Web mobiles en se basant sur une découverte dynamique des instances de services Web présentes dans l'environement.

Les travaux présentés dans cette thèse s'inscrivent dans le thème général de l'adaptabilité des systèmes de communication pour la QoS. La contribution proposée porte sur l'adaptation dynamique de protocoles de Transport, pour répondre aux besoins en QoS d'applications multimédia distribuées dans un contexte d'activités coopératives de groupe de type opérations d'intervention d'urgence. La première partie a été réalisée dans le cadre du projet européen projet IST NETQoS et porte sur une proposition d'architecture conceptuelle pour la mise en oeuvre de l'adaptation au niveau Transport. Suivant une approche basée politique, les contributions exposées portent sur l'élaboration de l'architecture du composant central du système, chargé de concevoir, d'adapter et de faire appliquer des politiques opérationnelles aux entités en charge de la gestion directe de la QoS. La deuxième partie porte sur le problème de la décision et propose une approche originale de gestion collaborative des protocoles de Transport pour la QoS dans les activités coopératives de groupe. L'approche explorée vise à privilégier les connexions de Transport les plus prioritaires au détriment des connexions les moins prioritaires. Nous nous intéressons au problème de la répartition de la bande passante entre ces connexions. Après avoir défini le problème et les données nécessaires à sa résolution, nous le formulons sous la forme d'un problème de programmation linéaire résolu grâce à la méthode du simplexe. Deux critères de minimisation sont envisagés et discutés. Enfin, des mesures de performance réalisées en simulation permettent de mettre en évidence le bien fondé et les limites des solutions proposées.

Les règles d'association révèlent des régularités non triviales et potentiellement utiles pour l'aide a la décision, dans les bases de données. Leur validité est évaluée par le biais de mesures de qualités dont les plus utilisées sont le support et la confiance. Pour une base de données transactionnelles d'un supermarché, elles sont du type "90% des clients ayant acheté du vin et du fromage ont également acheté du pain, sachant que 75% des clients ont acheté ces articles". Dans ce travail, nous spécifions une classe de mesures de qualité normalisées en ce sens qu'elles reflètent les situations de référence comme l'incompatibilité, la dépendance négative, l'indépendance, la dépendance positive, et l'implication logique entre la prémisse et le conséquent. Nous caractérisons les mesures de qualité normalisables, donnons les formules de normalisation et montrons que la plupart de celles qui sont normalisables ont la même normalisée, à savoir la mesure de qualité Mgk introduite dans Guillaume (2000). De plus, nous caractérisons des bases pour les règles positives et les règles négatives valides au sens de Mgk, et proposons des algorithmes de génération de ces bases

Les paramètres des Algorithmes Evolutionnaires (AEs) ont une forte influence sur leur capacité à produire de bons résultats. Ces paramètres définissent les aspects structuraux et comportementaux de l'AE, comme la définition des composants qui seront inclus (e.g., l'ensemble d'opérateurs à utiliser, le codage, le schéma de sélection) ou la façon dont ces composants seront employés (e.g., le taux d'application des opérateurs). La paramétrisation des AEs a ´et´e longtemps un domaine de spécialistes, et même si de nombreuses études ont abordé le problème de la paramétrisation, il existe un déficit d'approches génériques qui puissent être appliquées à une grande variété d'AEs d'une manière simple. Cette thèse traite le problème de la conception d'un contrôleur générique, qui puisse être inclus dans n'importe quel AE avec un minimum d'efforts. Ceci est accompli en incorporant un composant d'apprentissage adaptatif, qui surveille l'état de la recherche et modifie les valeurs des paramètres. Le contrôleur se focalise sur les objectifs communs à tout EA, i.e., la maximisation de la diversité de la population et de la qualité des individus, afin de maintenir un équilibre convenable entre l'exploration et l'exploitation. Des nombreuses configurations des mécanismes d'apprentissage et d'ajustement ont ´et´e essayées et analysées, en utilisant AEs différents qui résolvent des problèmes combinatoires connus. Les bons résultats obtenus suggèrent que notre objectif de construire un contrôleur générique et facile à utiliser constitue une approche encourageante.

De nos jours, la grande puissance de calcul et l'importante capacité de stockage fournie par les systèmes de calcul distribué à large échelle sont exploitées par des applications dont les besoins grandissent continuellement. Les plates-formes de ces systèmes sont composées d'un ensemble de ressources reliées entre elles par une infrastructure de communication. Dans ce type de système, comme dans n'importe quel environnement de calcul, il est courant que des solutions innovantes soient étudiées. Leur adoption nécessite une phase d'expérimentation pour que l'on puisse les valider et les comparer aux solutions existantes ou en développement. Néanmoins, de par leur nature distribuée, l'exécution d'expériences dans ces environnements est difficile et coûteuse. Dans ces systèmes, l'ordre d'exécution dépend de l'ordre des événements, lequel peut changer d'une exécution à l'autre. L'absence de reproductibilité des expériences rend complexe la conception, le développement et la validation de nouvelles solutions. De plus, les ressources peu- vent changer d'état ou intégrer le système dynamiquement ; les architectures sont partagées et les interférences entre applications, ou même entre processus d'une même application, peuvent affecter le comportement général du système. Enfin, le temps d'exécution d'application à large échelle sur ces sys- tèmes est souvent long, ce qui empêche en général l'exploration exhaustive des valeurs des éventuels paramètres de cette application. Pour toutes ces raisons, les expérimentations dans ce domaine sont souvent basées sur la simulation. Diverses approches existent actuellement pour simuler le calcul dis- tribué à large-échelle. Parmi celles-ci, une grande partie est dédiée à des architectures particulières, comme les grappes de calcul, les grilles de calcul ou encore les plates-formes de calcul bénévole. Néan- moins, ces simulateurs adressent les mêmes problèmes : modéliser le réseau et gérer les ressources de calcul. De plus, leurs besoins sont les même quelle que soit l'architecture cible : la simulation doit être rapide et passer à l'échelle. Pour respecter ces exigences, la simulation de systèmes distribués à large échelle repose sur des techniques de modélisation pour approximer le comportement du système. Cependant, les estimations obtenues par ces modèles peuvent être fausses. Quand c'est le cas, faire confiance à des résultats obtenus par simulation peut amener à des conclusions aléatoires. En d'autres mots, il est nécessaire de connaître la précision des modèles que l'on utilise pour que les conclusions basées sur des résultats de simulation soient crédibles. Mais malgré l'importance de ce dernier point, il existe très rarement des études sur celui-ci. Durant cette thèse, nous nous sommes intéressés à la problématique de la précision des modèles pour les architectures de calcul distribué à large-échelle. Pour atteindre cet objectif, nous avons mené une évaluation de la précision des modèles existants ainsi que des nouveaux modèles conçus pendant cette thèse. Grâce à cette évaluation, nous avons proposé des améliorations pour atténuer les erreurs dues aux modèles en utilisant SimGrid comme cas d'étude. Nous avons aussi évalué les effets des ces améliorations en terme de passage à l'échelle et de vitesse d'exécution. Une contribution majeure de nos travaux est le développement de modèles plus intuitifs et meilleurs que l'existant, que ce soit en termes de précision, vitesse ou passage à l'échelle. Enfin, nous avons mis en lumière les principaux en- jeux de la modélisation des systèmes distribuées à large-échelle en montrant que le principal problème provient de la négligence de certains phénomènes importants.