La gestion du trafic aerien (air-traffic management, ATM) consiste en une composante predictive (planification du trafic) et en une composante adaptative (controle du trafic). Le but de la composante predictive est de trouver un equilibre entre la demande de l'espace et la capacite disponible. Une fois que les avions ont decolle, la composante adaptative doit les guider en toute securite vers leurs destinations. Des incertitudes, telles que retards ou defaillances techniques, creent des phenomenes d'ecarts entre la composante predictive et adaptative. Cela entraine des problemes de securite ainsi qu'une utilisation sous-optimale de capacite. Meme si les causes majeures des incertitudes sont connues (incertitude de demande, incertitude de capacite, incertitude de gestion de flux), les mecanismes perturbateurs restent inconnus. L'approche de cette these est d'analyser des donnees d'ecoulement de trafic afin d'engendrer de nouvelles hypotheses sur les mecanismes qui causent des ecarts entre la composante predictive et adaptative dans l'ATM. C'est un premier pas pragmatique dans l'analyse d'un phenomene physique. Il est fonde sur le calcul des probabilites et plus precisement sur l'interpretation frequentiste des probabilites. On utilise des techniques d'analyse de donnees multi-variees et des processus ponctuels stochastiques afin d'inferer de nouvelles connaissances sur le phenomene. Nos resultats principaux sont: (i) des ecarts systematiques existent dans tous les secteurs evalues. Leur taille peut etre caracterisee par des distributions de Poisson et on constate une tendance systematique a supprimer le trafic sur des niveaux eleves de planification. C'est un resultat contre-intuitif car l'on s'attend a ce que les differents facteurs d'incertitude s'annullent en moyenne. Ensuite on montre que des perturbations aleatoires d'un processus d'arrivee causent des ecarts systematiques dans deux classes de plan de vol. On conclut que meme si toutes les incertitudes controlables etaient eliminees, des ecarts systematiques entre le nombre planifie et observe de vols apparaisseraient. Ce resultat est utile pour la planification tactique des flux. De nouvelles contraintes pour le probleme de l'allocation de creneaux peuvent etre formulees en identifiant des plans de vol qui sont robustes aux perturbations aleatoires. (ii) on montre que les ecarts se propagent uniquement le long des routes aeriennes. Aucune propagation non-attendue n'est identifiee. Cela indique que les controlleurs aeriens n'utilisent pas systematiquement le re-routage pour compenser les ecarts. On remarque egalement des probabilites de queue elevees et on propose deux (nouveaux) modeles de series chronologiques qui decrivent les caracteristiques du processus de perturbation des plans de vol. Cela indique que les perturbations sont d'une nature heterogene et non-independante. Le resultat est empirique et on affirme que le comportement observe est du a des dependances entre les avions intervenant sur un long-terme. Comme travaux futurs on propose de continuer l'identification des ordonnancements de vol qui absorbent l'impact des incertitudes non-controlables et de developper des modeles statistiques qui expliquent les echantillons long-terme de congestion. Ceci constitue une base pour la quantifiaction de l'impact des decisions locales sur la performance globale du reseau de transport.

Les travaux de cette thèse portent sur la cryptanalyse d'un système de chiffrement simple, mais important : le registre filtré. Ils concernent les deux principales familles d'attaques que sont les attaques algébriques et les attaques probabilistes. Pour les attaques algébriques, il est important de pouvoir calculer efficacement l'immunité algèbrique de la fonction booléenne par laquelle le registre est filtré. Cette quantité est intimement liée au comportement des codes de Reed-Muller sur le canal à effacements et son étude a permis la découverte de plusieurs résultats qui s'expriment naturellement dans le cadre de la théorie des codes correcteurs. Nous avons ainsi construit une nouvelle borne sur la probabilité de pouvoir compenser un nombre d'effacements fixé. Cette borne montre que l'immunité algébrique d'une fonction booléenne aléatoire est presque toujours maximale. Nous avons également explicité une méthode de décodage fondée sur des algorithmes d'algèbre linéaire creuse (comme l'algorithme de Wiedemann) qui donne un des algorithmes les plus efficace pour calculer l'immunité algébrique. Pour les attaques probabilistes, un outil très important est de parvenir à trouver efficacement de nombreux multiples de poids faible du registre à décalage du système. Un nouvel algorithme fondé sur les logarithmes discrets à été proposé. Il est particulièrement interessant pour les multiples de poids 4, améliorant dans de nombreux cas pratiques le meilleur algorithme connu. Ce travail s'est poursuivi par une nouvelle cryptanalyse probabiliste du registre filtré qui utilise ces multiples de poids faible pour reconnaître les entrées nulles de la fonction de filtrage. Cette attaque est l'une des plus efficaces connue à l'heure actuelle.

La vérification des programmes est indispensable pour maintenir un certain niveau de qualité et de fiabilité. Le test est à ce jour le moyen de vérification des logiciels le plus utilisé dans l¤industrie. La programmation par contraintes est vue comme un moyen efficace pour automatiser la génération de données de test. Dans cette thèse nous proposons une modélisation par contraintes de la sémantique du bytecode Java, ainsi qu¤une méthode, basée sur cette modélisation, pour générer automatiquement des données de test. Notre modèle à contraintes de la sémantique d¤un programme en bytecode Java permet de faire des déductions efficaces, y compris en présence de structures de données complexes ou d¤héritage. En particulier, l¤utilisation de variables de type permet de prendre en compte l¤héritage et les appels de méthodes polymorphes. Notre méthode de génération de données de test exploite le modèle à contraintes pour couvrir des instructions particulières du programme sous test. Elle se base sur un parcours en arrière du graphe de flot de contrôle pour énumérer des chemins menant aux instructions cibles. Elle est en particulier adaptée à la couverture d¤instructions non couvertes par les autres méthodes de génération de données de test. Enfin cette méthode est mise en application dans un prototype, JAUT (Java Automatic Unit Testing). Les expériences montrent que le prototype permet d¤augmenter la couverture des instructions obtenue avec les autres outils disponibles.

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.