Le placement de caméra en environnement virtuel consiste à positionner et orienter une caméra virtuelle 3D de façon à respecter un ensemble de propriétés visuelles ou cinématographiques définies par l'utilisateur. Réaliser cette tâche est difficile en pratique. En effet, l'utilisateur possède une vision claire du résultat qu'il souhaite obtenir en termes d'agencement des objets à l'image. Toutefois le processus classique de placement de caméra est particulièrement contre-intuitif. L'utilisateur doit effectuer une inversion mentale afin d'inférer la position et l'orientation de la caméra dans l'environnement 3D amenant au résultat souhaité. Des méthodes d'aide au placement de caméra apparaissent donc particulièrement profitables pour les utilisateurs. Dans cette thèse, nous identifions trois axes de recherche relativement peu couverts par la littérature dédiée au placement de caméra et qui nous apparaissent pourtant essentiels. D'une part, les approches existantes n'offrent que peu de flexibilité tant dans la résolution que dans la description d'un problème en termes de propriétés visuelles, en particulier lorsque celui-ci ne possède aucune solution. Nous proposons une méthode de résolution flexible qui calcule l'ensemble des solutions, maximisant la satisfaction des propriétés du problème, que celui-ci soit sur-contraint ou non. D'autre part, les méthodes existantes ne calculent qu'une seule solution, même lorsque le problème possède plusieurs classes de solutions équivalentes en termes de satisfaction de propriétés. Nous introduisons la méthode des volumes sémantiques qui calcule l'ensemble des classes de solutions sémantiquement équivalentes et propose un représentant de chacune d'elles à l'utilisateur. Enfin, le problème de l'occlusion, bien qu'essentiel dans la transmission de l'information, n'est que peu abordé par la communauté. En conséquence, nous présentons une nouvelle méthode de prise en compte de l'occlusion dans des environnements dynamiques temps réel.

Class-Add, une procédure de sélection de variables basée sur une troncature k-additive de l'information mutuelle et sur une classification ascendante hiérarchique en pré-traitement Lorem ipsum dolor sit amet, consectetuer adipiscing elit. Sed non risus. Suspendisse lectus tortor, dignissim sit amet, adipiscing nec, ultricies sed, dolor. Cras elementum ultrices diam. Maecenas ligula massa, varius a, semper congue, euismod non, mi. Proin porttitor, orci nec nonummy molestie, enim est eleifend mi, non fermentum diam nisl sit amet erat. Duis semper. Duis arcu massa, scelerisque vitae, consequat in, pretium a, enim. Pellentesque congue. Ut in risus volutpat libero pharetra tempor. Cras vestibulum bibendum augue. Praesent egestas leo in pede. Praesent blandit odio eu enim. Pellentesque sed dui ut augue blandit sodales

Les outils de simulation ont déjà été éprouvés pour l'étude de nombreux phénomènes, mais simuler le comportement humain reste un défi à la fois pour l'informatique et les sciences humaines. Dans ce contexte, nous avons travaillé sur la simulation des comportements individuels et des interactions sociales dans les groupes d'individus pour observer l'émergence de phénomènes sociaux. À cette fin, nous avons mener un travail inter-disciplinaire mêlant des techniques d'intelligence artificielle, de systèmes multi-agents, de sciences humaines et de fouille de données spatio-temporelles. Cette thèse présente un nouveau modèle d'agent émotionnel : l'agent EFT (Emotion, Feeling, Temperament). Basée sur une architecture BDI, notre modèle intègre le modèle émotionnel OCC et le modèle comportemental PerformanSe. Nous présentons également une implémentation concrète de notre modèle : la simulation de personnes cérébrolésés sur une chaîne de conditionnement. Nous décrivons la modélisation des interactions de notre système grâce à AgentUML. Via des méthodes de fouille de données spatio-temporel, nous extrayons les informations pertinentes à partir des données issues de la simulation.

La thèse couvre deux problèmes motivés par la biologie: l'étude des réarrangements génomiques, et celle des réseaux d'haplotypes. Les problèmes de réarrangements génomiques sont un cas particulier des problèmes de distances d'édition, où l'on cherche à transformer un objet en un autre en utilisant le plus petit nombre possible d'opérations, les opérations autorisées étant fixées au préalable; on s'intéresse également à la distance entre les deux objets, c'est-à-dire au calcul du nombre d'opérations dans une séquence optimale plutôt qu'à la recherche d'une telle séquence. Les problèmes de réarrangements génomiques peuvent souvent s'exprimer comme des problèmes de tri de permutations (vues comme des arrangements linéaires de {1,2,...,n}) en utilisant le plus petit nombre d'opérations (autorisées) possible. Nous examinons en particulier les ``transpositions', qui déplacent un intervalle de la permutation. Beaucoup de problèmes liés au tri par transpositions sont ouverts, en particulier sa complexité algorithmique. Nous nous écartons des ``outils standards' utilisés dans le domaine des réarrangements génomiques, et utilisons la décomposition en cycles disjoints des permutations pour prouver de nouvelles majorations sur la distance des transpositions ainsi que des formules permettant de calculer cette distance en temps polynomial dans de nombreux cas. Cette décomposition nous sert également à résoudre un problème d'énumération concernant le ``graphe des cycles' de Bafna et Pevzner, et à construire une technique générale permettant d'obtenir de nouvelles minorations en reformulant tous les problèmes de distances d'édition sur les permutations en termes de factorisations de permutations paires associées. Les réseaux d'haplotypes sont des graphes dont une partie des sommets porte des étiquettes, utilisés en génomique comparative quand les arbres sont trop restrictifs, ou quand l'on ne peut choisir une ``meilleure' topologie parmi un ensemble donné d'arbres. Nous formalisons une nouvelle méthode due à Cassens, Mardulyn et Milinkovitch, qui consiste à construire un graphe contenant tous les arbres partiellement étiquetés donnés et possédant le moins d'arêtes possible, et donnons des algorithmes résolvant le problème de manière optimale sur deux graphes, dont le temps d'exécution est exponentiel en général mais polynomial dans quelques cas que nous caractérisons.

Nous étudions les décompositions arborescentes de graphes et les paramètres de largeur associés (largeur arborescente, largeur linéaire) sous plusieurs aspects. Nous proposons des algorithmes pour le calcul de la largeur arborescente des graphes ayant une quantité polynomiale de séparateurs minimaux et des algorithmes exacts et d'approximation dans le cas général. Nous abordons le problème de la largeur linéaire à travers une approche heuristique basée sur les complétions d'intervalles minimales, mais aussi avec des algorithmes polynomiaux pour certaines classes de graphes.

La largeur linéaire et la largeur arborescente ont été introduites par Robertson et Seymour dans leurs travaux sur les mineurs de graphes. De manière informelle, la largeur linéaire (resp. la largeur arborescente) d'un graphe mesure l'écart entre ce graphe et la classe des chaînes (des arbres). Les deux paramètres se sont révélés très puissants de point de vue algorithmique, car de nombreux problèmes NP-difficiles deviennent polynomiaux lorsque l'on se restreint à des classes de graphes de largeur linéaire ou de largeur arborescente bornée. Etant donné un graphe G=(V,E) quelconque, un graphe d'intervalles H=(V,F) contenant G est appelé complétion d'intervalles de G. Calculer la largeur linéaire de G revient à trouver une complétion d'intervalles H, tout en minimisant la clique maximum de H. Le problème étant NP-difficile, nous calculerons des complétions d'intervalles minimales, où l'on demande seulement que l'ensemble d'arêtes rajoutées F\E soit minimal par inclusion parmi toutes les complétions possibles. Une approche similaire, à travers les triangulations minimales, est fortement utilisée pour comprendre et calculer la largeur arborescente. Ce mémoire présente nos résultats sur les complétions d'intervalles minimales. Nous donnons trois algorithmes calculant une complétion d'intervalles minimale, basés sur des approches différentes. Nous présentons également un algorithme calculant une complétion d'intervalles propres minimale. Enfin, nous montrons que la largeur linéaire des graphes d'intervalles circulaires peut être calculée en temps polynomial.

Cette thèse a été réalisée dans le cadre d'une collaboration entre l'université d'Angers et la société Perinfo. Elle porte sur le développement de nouveaux modèles et algorithmes dédiés à la détermination des horaires de lignes dans les réseaux de bus. Le coeur de ce manuscrit est la qualité de service perçue par l'usager. Nous réalisons dans un premier temps un état de l'art des étapes relatives à la planification du réseau. Nous proposons ensuite un modèle et des fonctions d'évaluation pour les objectifs de synchronisation des correspondances et de régularité du cadencement. Ces éléments sont utilisés au sein d'une méthode de recherche locale basée sur un ensemble de voisinages que nous définissons pour le problème. Notre troisième contribution est la modélisation d'un problème original et intégré qui résout simultanément le problème de fixation des horaires et de création des affectations de véhicules. Pour ce problème complexe, nous proposons une méthode de résolution hybride basée sur une recherche locale itérée et un algorithme exact par enchères, ainsi que deux voisinages spécifiques. Les tests réalisés sur données réelles valident la supériorité de l'approche simultanée par comparaison avec la situation existante et l'approche séquentielle, tant au niveau de la qualité de service que des coûts économiques. Enfin, nous étudions une problématique originale qui prend à contre-courant le processus traditionnel de planification. Ce problème de fixation des horaires, visant des objectifs liés aux correspondances, prend pour contraintes les séquences de courses affectées aux véhicules et aux conducteurs. Cette approche permet d'améliorer la qualité de service sans remettre en cause les plannings d'exploitation. Une méthode tabou basée sur deux voisinages adaptés est développée et testée sur un cas d'étude.

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.