Un tour d'horizon de plusieurs systèmes de numération "exotiques" et leurs applications en cryptographie est proposé.

Les recherches menées dans le domaine des implants médicaux visent à améliorer la qualité de vie de patients atteints de pathologies diverses. Dans ce cadre la Stimulation Electrique Fonctionnelle (SEF) consistant à produire des contractions artificielles de groupements musculaires par stimulation électrique sur les voies nerveuses ou sur les muscles, est une solution utilisée pour contourner certains dysfonctionnements du système neural. Le Projet DEMAR (DEambulation et Mouvement ARtificiel), dont les axes ont pour objectifs la compréhension et la quantification objective des désordres moteurs d'une part, et la recherche de solutions palliatives des déficiences motrices d'autre part, a développé en 2005 par le travail de thèse de Jean-Denis TECHER, un stimulateur électrique implantable. Afin de pourvoir contrôler ce système de stimulation en boucle fermée, nous avons développé les deux premiers étages d'une chaîne d'acquisition de signaux neurophysiologiques sensoriels. Ces étages sont l'électrode cuff multipolaire à distribution hexagonale et l'amplificateur faible-bruit à calcul de moyenne pondérée.

L'objectif de notre travail est la conception d'un cadre théorique et méthodologique permettant l'aide à la décision au sein d'un modèle de représentation des connaissances, illustré par un cas d'étude issu de la filière céréalière. Le domaine d'application plus particulièrement considéré est la définition de la qualité alimentaire, pour laquelle entrent en jeu différents points de vue (intérêt nutritionnel, qualités gustatives, sécurité sanitaire des produits) et différents acteurs (industriels, chercheurs, citoyens) dont les intentions divergent. La base de notre approche est l'utilisation de systèmes d'argumentation issus de la littérature en IA. Les systèmes d'argumentation sont des cadres formels visant à représenter des arguments, les interactions entre ces arguments, et à déterminer quels énoncés sont inférables par un ensemble d'arguments jugé cohérent, ces énoncés pouvant par exemple correspondre à des croyances ou à des décisions à prendre. L'un des cadres formels les plus abstraits, qui fait référence dans le domaine, est celui proposé par Dung en 1995. Dans ce cadre, un système d'argumentation est défini par un ensemble fini d'arguments et une relation binaire sur cet ensemble, appelée relation d'attaque. On peut également voir un tel système comme un graphe étiqueté dont les sommets sont les arguments et les arcs représentent la relation d'attaque directe. Un argument en "attaque'' un autre s'il existe un chemin de longueur impaire du premier au second, et il le ''défend'' s'il en existe un de longueur paire. Un argument est inférable s'il appartient à un ensemble d'arguments ayant certaines propriétés relatives aux notions d'attaque et de défense. C'est en ce sens que l'acceptabilité des arguments est dite collective. Le système d'argumentation de Dung a été étendu notamment par l'ajout de préférences entre arguments. Celles-ci, agrégées aux attaques, donnent une relation de ''défaite'', changeant le calcul de l'acceptabilité collective des arguments. Ainsi, sur la base de l'acceptabilité collective, nous proposerons une méthode pour déterminer l'équivalence entre deux systèmes d'argumentation afin d'unifier ces systèmes abstraits d'argumentation à base de préférences. Un système contextuel à base de préférences est ainsi proposé (les préférences et les attaques entre arguments ont une validité contextuelle), des méthodes d'agrégations entre attaques et préférences et de fusions entre contextes sont investiguées au regard de la consistance entre arguments collectivement acceptés. La consistance est obtenue lorsque de tels ensembles ne contiennent pas de conflits en termes d'informations véhiculées et de conclusions et/ou de décisions supportées au niveau de leurs arguments. Notre démarche s'appuie sur trois courants bien connus de l'argumentation : nous proposons une vue emboîtée de l'argument répondant aux attentes du courant ''micro'', qui s'attache à définir les structures internes de l'argument; nous proposons de générer des attaques entre arguments basées sur les actions qu'ils soutiennent ou qu'ils rejettent. Ceci nous permet de nous intéresser également aux préoccupations du courant ''macro'' pour le traitement des relations entre arguments en vue du calcul d'une acceptabilité collective. Enfin, nous nous intéressons à certains aspects du courant ''rhétorique'', à savoir la définition d'audiences donnant une force contextuelle à l'argument et générant des préférences. Ce dernier aspect nous permet notamment d'établir des recommandations contextuelles. L'ensemble de la démarche, illustrée au travers d'exemples situationnels et d'un cas d'application, est inclus dans un modèle d'arbitrage argumenté, lui même en partie implémenté dans un formalisme de représentation des connaissances et de raisonnement (les graphes conceptuels).

Cette thèse présente une nouvelle approche pour l'évaluation quantitative de la sécurité des systèmes informatiques. L'objectif de ces travaux est de définir et d'évaluer plusieurs mesures quantitatives. Ces mesures sont des mesures probabilistes visant à quantifier les influences de l'environnement sur un système informatique en présence de vulnérabilités. Dans un premier temps, nous avons identifié les trois facteurs ayant une influence importante sur l'état du système : 1) le cycle de vie de la vulnérabilité, 2) le comportement de la population des attaquants et 3) le comportement de l'administrateur du système. Nous avons étudié ces trois facteurs et leurs interdépendances et distingué ainsi deux scénarios principaux, basés sur la nature de la découverte de la vulnérabilité, malveillante ou non. Cette étape nous a permis d'identifier les états possibles du système en considérant le processus d'exploitation de la vulnérabilité et de définir quatre mesures relatives à l'état du système qui peut être vulnérable, exposé, compromis, corrigé ou sûr. Afin d'évaluer ces mesures, nous avons modélisé ce processus de compromission. Par la suite, nous avons caractérisé de manière quantitative les événements du cycle de vie de la vulnérabilité à partir de données réelles issues d'une base de données de vulnérabilités pour paramétrer nos modèles de manière réaliste. La simulation de ces modèles a permis d'obtenir les valeurs des mesures définies. Enfin, nous avons étudié la manière d'étendre le modèle à plusieurs vulnérabilités. Ainsi, cette approche a permis l'évaluation de mesures quantifiant les influences de différents facteurs sur la sécurité du système.

Cette thèse explore l'utilisation de croquis et d'annotation pour contrôler la modélisation 3D d'objets complexes (comme des chevelures, des arbres, des vêtements, etc). Nous introduisons une méthodologie basée sur trois idées princpales: Premièrement, le fait que l'expression de connaissances à priori sur l'objet modélisé peut être déterminante pour l'interprétation d'un croquis. Deuxièmement, l'idée que la chaîne de traitements doit se rapprocher au maximum de celle utilisée par un artiste, avec en particulier une esquisse de la forme globale avant que les détails ne soient précisés. Troisièmement, le fait que la structure 3D sous jacente peut soit servir de base au croquis (ils s'agit alors d'une technique d'annotation), soit être inférée à partir des silhouettes tracées par l'utilisateur, ce qui réduit grandement la quantité d'information à donner. Nous illustrons cette méthodologie en détaillant quatre exemples d'application: la modélisation par croquis de vêtements (pour laquelle sont comparées différents niveaux de connaissances a priori), de chevelures, de nuages et d'arbres.

L'explosion de la puissance de calcul permet actuellement de réaliser des simulations physiques comportant jusqu'à plusieurs milliards d'éléments. Pour extraire l'information importante de tels volumes de données, les ingénieurs doivent disposer d'outils de visualisation permettant d'explorer et d'analyser interactivement les champs calculés. Cette thèse vise à améliorer les visualisations réalisées en prenant en compte les caractéristiques de la perception visuelle chez l'homme, notamment en ce qui concerne la perception de l'espace et du volume au cours de visualisations 3D denses. D'abord, trois expériences de psychophysique ont montré que les rendus volumiques, reposant sur l'accumulation ordonnée de transparences, génèrent des difficultés importantes de perception de la profondeur. Cela est particulièrement vrai lors de visualisations statiques, mais l'ajout de mouvement dans la scène ainsi que l'amplification de la projection perspective permettent de lever en partie ces ambiguïtés. Ensuite, deux algorithmes améliorant la perception de l'espace lors de la visualisation de structures tridimensionnelles complexes ont été développés. Leur implémentation sur GPU permet des rendus interactifs indépendamment de la nature géométrique des données visualisées. L'EyeDome Lighting, un nouvel ombrage non photoréaliste basé sur l'image de profondeur, améliore la perception des formes et des profondeurs dans des scènes 3D complexes. Par ailleurs, une nouvelle technique d'écorché dépendant du point de vue a été implémentée. Elle autorise la visualisation d'objets normalement occultés tout en rendant compte de la structure des surfaces masquantes.

Le squelette de visibilité est une structure de donnée qui encode l'information de visibilité globale pour une scène donnée en 2D ou 3D. Cette structure de donnée est en principe très utile pour répondre à des requêtes de visiblité globale, mais elle est, en particulier en 3D, d'une complexité de haut degré dans le pire des cas qui semble prohibitive. Cependant, les recherches théoriques précédentes ont indiqué que l'espérance de la taille de cette structure de donnée peut être linéaire sous certaines conditions restreintes. Cette thèse approfondit l'étude de la taille du squelette de visibilité, au moyen d'une approche expérimentale. Nous montrons d'abord qu'aussi bien théoriquement qu'empiriquement, l'espérance de la taille du squelette de visibilité en 2D est linéaire, et présentons une asymptote affine qui facilite l'estimation de la taille du squelette de visibilité en 2D. Nous étudions ensuite le squelette de visibilité 3D défini par événement visuels, qui est un sous-ensemble du squelette complet défini par Durand et al. . Nous présen- tons tout d'abord une implantation calculant les sommets de ce squelette pour des polytopes convexes disjoints en position générale. Cette implantation nous permet de continuer notre étude empirique en 3D. Nous considérons des scènes données consis- tant en des polytopes convexes disjoints qui sont une approximation de sphères unités distribuées aléatoirement. Nous avons découvert que, dans ces conditions, la taille du squelette de visibilité 3D a une relation quadratique en le nombre de polytopes donnés, et linéaire en l'espérance de la taille de la silhouette des polytopes donnés. Cette estimation est bien plus basse que la complexité dans le pire des cas, mais plus haute que la complexité linéaire que nous espérions initialement. Nous présentons aussi des arguments qui pourraient expliquer la complexité obtenue. Nous prouvons finalement qu'en utilisant le squelette de visibilité 3D défini par événement visuels, nous pouvons calculer les sommets restants du squelette complet en temps presque linéaire en la taille du résultat.

Ce mémoire d'habilitation présente 14 articles différents, structurés en trois parties : algorithmes randomisés, algorithmes sur les sphères et placements de robots.<br /><br />Les algorithmes randomisés ont été un des sujets ``chauds'' de ces dernières années et nous proposons ici des travaux ayant trait à des algorithmes dynamiques ou semi-dynamiques : tout d'abord un schéma général d'algorithmes semi-dynamiques avec des applications aux diagrammes de Voronoï, aux diagrammes de Voronoï d'ordre k aux arrangements, et ensuite deux algorithmes dynamiques (permettant d'insérer et de supprimer des données) pour la triangulation de Delaunay et le calcul d'un arrangement de segments. D'autres résultats concernent des algorithmes statiques, notamment le calcul du squelette d'un polygone simple en temps O(n log* n).<br /><br />La deuxième partie explore différentes modélisations des sphères. On peut en déduire notamment un algorithme en O(tk log n) pour la triangulation de Delaunay de n points appartenant à k plans en 3 dimensions, si t désigne la taille du résultat; dans la cas de deux plans cet algorithme atteint une complexité optimale de O(t+n log n). Nous proposons également un algorithme de complexité O(n^ ceil(d/2) +n log n) pour le calcul de l'enveloppe convexe de n sphères en dimension d, et un algorithme optimal (quadratique) pour le calcul de la surface de Connolly.<br /><br />La dernière partie traite de problèmes spécifiques à la planification de trajectoires, un premier chapitre concerne le cas de plusieurs robots polygonaux en translation dans le plan: certaines configurations appellées double-contacts peuvent jouer un rôle particulier dans certains cas. Ensuite deux résultats à propos de robots à pattes : l'analyse d'un cas simple que nous avons baptisé robot araignée, et l'étude de la stabilité d'un robot un peu plus complexe.

Nos travaux s'inscrivent dans la discipline de l'interaction homme-machine (IHM), et concernent l'utilisation d'une nouvelle " forme " de systèmes informatiques : les tables interactives ou " tabletop ". Les systèmes tabletop prennent la forme d'une table dans son entier, qui sert à la fois de périphérique d'entrée tactile et de périphérique de sortie graphique. Grâce aux technologies multi-tactile, plusieurs utilisateurs peuvent toucher la table en même temps, et interagir avec le système de façon indépendante. Cette propriété rend les tables interactives particulièrement adaptées au support de la collaboration. Pourtant, nous constatons que les tables interactives ne sont que peu utilisées dans un objectif collaboratif en dehors des laboratoires. Nous pensons que plusieurs causes permettent d'expliquer cet état de fait. Nous remarquons, d'une part, que les applications existantes, pour ordinateurs de bureau, forment une part importante de l'utilisation actuelle des systèmes informatiques. Ces applications, qu'elles soient des applications grand public largement utilisées ou des applications spécifiques à une tâche précise, sont indispensables à leurs utilisateurs. Des projets ont créés des nouvelles applications aux mêmes fonctionnalités que les applications existantes, mais adaptées à des prototypes de nouveaux systèmes d'interaction. Elles offrent nettement moins de fonctionnalités que les applications pour ordinateurs de bureau existantes. Une telle réécriture reste de plus coûteuse au regard des efforts de développement déjà investis dans la création des applications existantes. D'autre part, les tables interactives se présentent sous un aspect matériel différent des ordinateurs traditionnels, au-delà du trio écran-clavier-souris. Cela introduit de nouvelles possibilités mais aussi de nouveaux défis pour l'interface utilisateur des applications. En revanche, les besoins des utilisateurs, en termes de fonctionnalités des applications, restent les mêmes. Nous étudions comment ce changement peut se répercuter sur les applications existantes. Nous proposons d'utiliser les mêmes applications sur la table interactive que sur l'ordinateur de bureau. Plusieurs types d'interactions sont envisageables pour remplacer les styles d'interaction de l'ordinateur de bureau qui ne sont pas adaptés aux systèmes tabletops. Nous entrons ici dans le domaine des interactions post-WIMP, des interactions qui vont au-delà des interacteurs 2D classiques que sont les fenêtres, les icônes, les menus et le pointeur (WIMP : Windows, Icons, Menus, Pointer). Les applications pour tables interactives ne se programment pas de la même manière que les applications pour ordinateurs de bureau. Nous évaluons six technologies permettent faire le lien entre les techniques utilisées pour programmer des applications pour ordinateurs de bureau et les techniques utilisées pour programmer des applications pour tables interactives : capture d'écran, carte graphique virtuelle, clavier virtuel et souris virtuelle, langage de script, API d'accessibilité numérique, réécriture d'une boîte à outils d'interface homme machine. Pour les évaluer, nous définissons cinq axes (structuration des données, flexibilité, performance, compatibilité et réutilisabilité, et difficulté d'implémentation). Nous avons implémenté des prototypes pour la carte graphique virtuelle, le langage de script, et la réécriture d'une boîte à outils (la boîte à outils win32). Les applications pour tables interactives ne s'utilisent pas de la même façon que les applications pour ordinateurs de bureau non plus. Les interfaces utilisateur des applications existantes ont été conçues pour être utilisées par un seul utilisateur avec un ordinateur de bureau. Les technologies que nous avons présentées ne résolvent pas ce problème. Nous présentons des scénarios mettant en évidence ces limitations. Pour concevoir de nouvelles techniques d'interaction adaptées, nous introduisons la métaphore du papier. Les métaphores sont utilisées, en interaction homme-machine, pour aider les utilisateurs à appréhender le fonctionnement d'un nouveau système plus rapidement en y appliquant des connaissances d'un système qu'ils connaissent déjà. Le papier, probablement le support d'information le plus courant, offre de nombreuses possibilités d'interaction. Nous proposons ainsi trois techniques d'interaction inspirées du papier. Nous proposons des fentes qui permettent de transmettre à distance des documents à un autre utilisateur, ainsi que d'effectuer des traitements sur les documents. Le pliage durable permet de nouvelles interactions avec un document. Il rend accessible le dos du document, qui peut contenir une interface graphique pour l'utilisateur. En observant le recto de documents papier existants, nous sommes arrivés à la conclusion que certains artefacts informatiques existants auraient toute leur place au dos d'un document : le système d'aide de l'application, des outils pour gérer le cycle de vie du document, des métadonnées sur le document,... Enfin, le plier pour empiler permet la création de piles de façon spontanée, en " recyclant " un document existant comme couverture pour de pile, simplement en le pliant en deux. Certaines des interactions peuvent être effectuées de plusieurs manières. Nous proposons un formalisme que nous appelons matrice des interactions, dédié aux interactions de gestion des documents sur la surface d'une table interactive, pour les comparer. Nous nous basons sur les interactions déjà existantes dans la gestion des fenêtres sur les ordinateurs de bureau : le déplacement et le redimensionnement, auxquelles nous ajoutons trois interactions : la rotation, le zoom et le pliage. Ces interactions s'approchent de devenir des standards en matière d'interface pour table interactive dans la communauté des tabletops. Nous avons identifié trois moyens distincts d'effectuer ces cinq interactions : l'utilisation d'un interacteur dédié, l'utilisation de la position du document sur la table, et l'utilisation de la trajectoire du doigt de l'utilisateur. Notre matrice met en évidence que ces trois moyens peuvent être proposés simultanément par le système informatique, imitant ainsi cette propriété du monde physique.

Ce mémoire résume ma contribution aux problèmes de la représentation et de la comparaison des formes et propriétés chimiques de molécules au moyen de nouvelles techniques de transformées de Fourier rapides (FFT). Les trois principaux domaines abordés ici sont le clustering et la classification des formes de macromolécules protéiques, le docking ou amarrage protéine-protéine visant à modéliser la conformation structurale de deux partenaires susceptible d'exister in vivo, et enfin la comparaison rapide de nombreuses petites molécules pour le criblage virtuel de potentiels inhibiteurs thérapeutiques. Les techniques basées sur la FFT sont largement utilisées dans de nombreux domaines de la science. Par ailleurs, les approches conventionnelles basées sur les grilles cartésiennes de FFT peuvent accélérer les calculs d'appariement moléculaire dans seulement trois des six degrés de liberté (ceux de translation) du corps rigide. Le thème principal de mon travail repose sur l'idée que la comparaison des formes complexes en trois dimensions (3D) de molécules est en grande partie un problème de rotation, dès lors les molécules peuvent efficacement être représentées par des systèmes de coordonnées polaires afin de pouvoir les comparer à l'aide de FFT rotationelles. Dans ce mémoire, je montre qu'en représentant les molécules par des développements orthogonaux en harmoniques sphériques et des polynômes de Gauss-Laguerre et en n'utilisant que des techniques classiques de calcul, leurs formes peuvent être mises en rotation et translatées analytiquement. Les paires de formes peuvent alors être comparées ou amarrées de façon très efficace en utilisant une série de 1D, 3D, ou même 5D FFT de rotation. Même si une grande partie des fondamentaux théoriques sont bien connue dans les domaines de la chimie ou de la physique, l'approche globale est originale dans le contexte de l'appariement de formes moléculaires, du docking de protéines et plus généralement de la reconnaissance d'objets 3D. La dernière partie de ce mémoire ouvre sur les perspectives futures visant à étendre ces différentes approches aux défis actuels posés par la biologie systémique et structurale tels que le criblage virtuel à haut-débit, l'intégration de la flexibilité des protéines lors de leur complexation mais aussi l'assemblage de structures macromoléculaires multi-composants.