La programmation linéaire est un outil algorithmique très puissant. Essentiellement, un problème de programmation linéaire vous demande d'optimiser une fonction linéaire de variables réelles contrainte par un système d'inégalités linéaires. Il s'agit d'un cadre extrêmement polyvalent qui généralise immédiatement les problèmes de flux, mais qui peut également être utilisé pour discuter d'une grande variété d'autres problèmes, depuis l'optimisation des procédures de production jusqu'à la recherche du moyen le moins coûteux d'obtenir un régime alimentaire sain. Étonnamment, ce cadre très général admet des algorithmes efficaces. Dans cette unité, nous discuterons de l'importance des problèmes de programmation linéaire ainsi que des outils utilisés pour les résoudre.

Bien que la plupart des algorithmes que vous avez appris jusqu'à présent soient souvent appliqués dans la pratique, il s'avère que le monde est dominé par des problèmes réels pour lesquels il n'existe pas d'algorithme prouvé efficace. Nombre de ces problèmes peuvent être réduits à l'un des problèmes classiques appelés problèmes NP-complets, qui soit ne peuvent être résolus par un algorithme polynomial, soit vous permettraient de gagner un million de dollars (voir les problèmes du Millenium Prize) et une renommée mondiale éternelle pour avoir résolu le principal problème de l'informatique, appelé P vs NP. Il est bon de le savoir avant d'essayer de résoudre un problème avant la date limite du lendemain :) Bien qu'il soit très peu probable que ces problèmes puissent être résolus efficacement dans un avenir proche, les gens trouvent toujours des solutions de contournement. Dans ce module, vous étudierez les problèmes NP-complets classiques et les réductions entre eux. Vous vous entraînerez également à résoudre de grandes instances de certains de ces problèmes malgré leur difficulté en utilisant des logiciels spécialisés très efficaces basés sur des tonnes de recherches dans le domaine des problèmes NP-complets.

Après le module précédent, vous êtes peut-être triste : vous venez de suivre 5 cours sur les algorithmes pour apprendre qu'ils ne sont pas adaptés à la plupart des problèmes du monde réel. Mais n'abandonnez pas pour autant ! Les gens sont créatifs, et ils ont besoin de résoudre ces problèmes de toute façon, donc en pratique il y a souvent des moyens de faire face à un problème NP-complet. Nous commençons par montrer que certains cas particuliers de problèmes NP-complets peuvent, en fait, être résolus en temps polynomial. Nous considérons ensuite des algorithmes exacts qui trouvent une solution beaucoup plus rapidement que l'algorithme de force brute. Nous concluons avec des algorithmes d'approximation qui fonctionnent en temps polynomial et trouvent une solution proche de l'optimum.

Dans la plupart des exposés précédents, nous nous sommes intéressés à la conception d'algorithmes ayant un temps d'exécution rapide (par exemple un petit polynôme) et nous avons supposé que l'algorithme avait un accès aléatoire à ses données d'entrée, qui sont chargées en mémoire. Cependant, dans de nombreuses applications modernes d'analyse de données massives, l'entrée est si volumineuse qu'elle ne peut pas être stockée en mémoire. Au lieu de cela, l'entrée est présentée sous la forme d'un flux de mises à jour, que l'algorithme parcourt tout en conservant un petit résumé du flux vu jusqu'à présent. C'est précisément le cadre du modèle de calcul en continu, que nous étudions dans ce cours. Le modèle de flux est bien adapté à la conception et au raisonnement sur les algorithmes à espace réduit. Il a reçu beaucoup d'attention dans la littérature, et plusieurs primitives algorithmiques puissantes pour calculer les statistiques de base des flux dans ce modèle ont été conçues, plusieurs d'entre elles ayant un impact sur la pratique de l'analyse des données massives (big data). Dans cet exposé, nous verrons l'un de ces algorithmes (CountSketch), un algorithme à espace réduit permettant de trouver les k éléments les plus fréquents dans un flux de données.