Description

L'algorithmique peut se définir comme l'art de résoudre efficacement des problèmes a priori difficiles. Lorsque ces problèmes semblent insurmontables, plusieurs relaxations du problème initial sont alors possibles. Une façon d'observer l'évolution de l'algorithmique de ces quinze dernières années est d'observer l'évolution de ces relaxations parallèlement aux techniques algorithmiques développées. Si initialement les relaxations se focalisaient sur la sortie du problème étudié (algorithmes d'approximation), elles se sont progressivement déplacées vers les données en entrée (algorithmes pour les données massives), ou encore vers le modèle de calcul lui-même (informatique quantique).

Algorithmes d'approximation (Approx)

Sous-thèmes : programmation semi-définie, résultats d'impossibilité, modele de données perturbées
Responsable : Claire Mathieu, Professeur à l'University of Brown (Providence, RI, USA)

Lorsque des problèmes sont trop difficiles, mais qu'une solution approchée est suffisante en pratique, les algorithmes d'approximation fournissent une alternative pertinente. Couplés à des techniques probabilistes, ils ont donnés lieu à des techniques algorithmiques utilisées dans de nombreux domaines. L'une des plus récentes (1994) repose sur la programmation semi-définie. Comme pour la programmation linéaire, l'approche est en deux étapes. La première consiste à reformuler le problème à l'aide de contraintes quadratiques (au lieu de linéaires, pour la programmation linéaire), où chaque bit est encodé par un vecteur (au lieu d'un réel). Les méthodes connues et efficaces fournissent alors une solution, à partir de laquelle il faut revenir à une solution admissible pour le problème initial, en associant à chaque vecteur un bit. Dans cette dernière étape (rounding), les techniques probabilistes sont centrales.

Les algorithmes probabilistes d'approximation ont aussi porté un nouveau regard sur les classes de complexité, et sont à l'origine de concepts fondateurs, tels que les preuves holographiques (PCP). Ces derniers permettent d'identifier dans cet univers les problèmes difficiles à approcher, même de manière probabiliste.

Enfin, lorsque le problème est difficile à approcher, il reste la possibilité de rajouter des hypothèses sur les données en entrée. Pour certains modèles de données perturbées, l'approximation devient alors possible.

Algorithmes pour les données massives (Massive)

Sous-thèmes : algorithmes de streaming, à mémoire externe, complexité de communication
Responsable : Frédéric Magniez, Chercheur CNRS au LIAFA (Université Paris 7)

Partant du constat que la taille des données traitées augmentent de manière exponentielle, les contraintes algorithmiques doivent être redéfinies. Habituellement, une donnée est d'abord écrite dans la mémoire de l'ordinateur avant d'être traitée. L'accès à cette donnée est selon le modèle random access memory (RAM), où l'accès à n'importe quelle partie de la donnée se fait en temps constant. Ce modèle n'est plus valide dès lors que la donnée est de l'ordre de quelques centaines de GigaOctets : la mémoire RAM de l'ordinateur ne peut contenir toute l'entrée.

L'accès aux données est alors séquentiel sur un support externe de type disque dur ou bande : lors d'une passe sur la donnée, chaque octet défile une et une seule fois. Si une partie de la donnée est à nouveau nécessaire pour le calcul, il faut procéder à une nouvelle passe. Les algorithmes doivent être repensés dans ce modèle : ils deviennent la plupart du temps inefficaces car ils utilisent un nombre de passes sur les donnés beaucoup trop élevé.

Les techniques mises en jeux sont essentiellement des estimateurs probabilistes de statistiques et des constructions probabilistes de fonctions de hachage. La complexité de communication est intimement liée à ce modèle et permet d'en exhiber ses contraintes.

Informatique quantique (Quantum)

Sous-thèmes : concepts, outils, preuves quantiques de résultats non-quantiques
Responsable : Iordanis Kerenidis, Chercheur CNRS au LIAFA (Université Paris 7)

L'informatique quantique est un prolongement naturel (d'un point de vue mathématique mais aussi en raison des technologies actuelles) de l'informatique probabiliste tant pour la théorie de l'information, la communication, la cryptographie ou encore l'algorithmique. Son développement a eu des retombées à la fois en physique mais aussi en informatique probabiliste. C'est pour cette raison que sa connaissance est importante.

En partant d'une question posée par Feynman, l'informatique quantique pose la question du traitement de l'information, et donc aussi du calcul, par un ordinateur qui pourrait utiliser à son profit des phénomènes quantiques. Plus qu'un nouveau modèle de calcul, cette discipline a profondément changé notre perception de l'information ainsi que les outils mathématiques nécessaires pour la modéliser, la quantifier et l'utiliser.

D'un point de vue pratique, la communication quantique est un concept dont les applications à court terme sont nombreuses, essentiellement en cryptographie. Le calcul quantique est lui plus futuriste et cherche à quantifier la supériorité calculatoire qu'aurait un hypothétique ordinateur quantique. L'information quantique est un nouvel angle de vision apporté par les informaticiens à la physique pour définir et quantifier les phénomènes quantiques. Il est au cœur de l'interface informatique-physique de la discipline.

Mais le plus surprenant est que les outils développés pour étudier l'information quantique servent à fournir des preuves "élégantes'' de résultats de l'informatique probabiliste. Par analogie, ils sont en quelques sortes le pendant des nombres complexes à la géométrie du plan. Plusieurs résultats difficiles et d'autres nouveaux ont pu être démontrés simplement à l'aide de ces nouveaux outils.