Introduction
Bien que les médias se découvrent une passion nouvelle pour les algorithmes, l'algorithmique est une science ancienne qui a débuté bien avant l'informatique. C'est une science extrêmement dynamique dont l'essort fulgurant est lié à la dématérialisation croissante de pans entiers de notre univers technologique. Les algorithmes sont utilisés dans tous les secteurs, et les fondamentaux de cette science sont à présent largement stabilisés, au même titre que l'algèbre linéaire en mathématiques.
L'idée d'un cours d'algorithmique en ligne n'a rien de révolutionnaire. Elle s'est imposée progressivement au gré des mutations d'un polycopié destiné aux étudiants de licence d'informatique et de mathématiques, qui après des années d'ajustements devait obtenir sa consécration sous forme de monographie. Les développements récents des technologies web, la qualité croissante des écrans et la possibilité de rédiger les mathématiques sans trop de souffrance et avec un aspect convenable, ont fini par me convaincre qu'il était préférable de dématérialiser ce cours plutôt que de le publier sous la forme d'un n-ème ouvrage papier.
Outre la possibilité de le mettre à jour et de corriger les inévitables erreurs en temps réel, la diffusion d'un document en ligne permet d'atteindre un public plus vaste que le cercle de plus en plus restreint des étudiants qui empruntent des livres à la bibliothèque ou qui en achètent (et qui les lisent !). Les progrès effectués sur les langages interprétés et la puissance de calcul des ordinateurs sont devenus tels qu'il est aujourd'hui possible de réaliser de véritables applications sur les navigateurs sans se préoccuper des outils dont le lecteur dispose pour les utiliser. C'est très certainement cette unification qui a été l'élément moteur de l'expansion surprenante de javascript plus qu'une adhésion massive à un langage affublé de défauts de conception particulièrement agaçants.
On aborde ici les thèmes classiques de l'algorithmique à travers l'étude d'algorithmes désormais classiques et fondamentaux. Ils sont présentés dans un pseudo langage de programmation dont les spécifications sont suffisamment floues pour pouvoir utiliser des boites noires quand cela est nécessaire. Cette concession à la rigueur a pour objectif de se concentrer sur la nature des algorithmes que l'on étudie et de ne pas se disperser sur des difficultés techniques accessoires. C'est pour la même raison qu'en aucun cas nous ne faisons de programmation en cours ou en travaux dirigés. La rigidité et les spécificités des langages de programmation ne font que compliquer la compréhension des algorithmes, la programmation reste donc cantonnée aux travaux pratiques. Nous ferons une exception quand la nature même d'un langage et que les structures de données qu'il propose impactent la conception de l'algorithme.
Pour résumer, l'objectif de ce cours en ligne est de présenter une sélection d'algorithmes pour la plupart classiques dans des domaines variés en tentant d'être progressif. Dans un cycle de licence d'informatique ou de mathématiques, l'algorithmique est généralement enseignée en trois phases qui coïncident globalement avec les trois années du cursus. Ce cours fournit également au lecteur des exemples interactifs quand ils sont susceptibles de faciliter la compréhension. Cette part interactive, difficile à obtenir sur un support papier, et l'échelonnement des difficultés sur les trois années d'un cursus de licence constituent certainement les éléments qui le distinguent d'un ouvrage classique d'algorithmique.
À qui s'adresse ce cours ?
Ce cours s'adresse tout d'abord aux étudiants d'informatique ou de mathématiques de licence et bien entendu à tous les internautes intéressés par l'algorithmique et qui auront convergé vers ces pages lors de leur pérégrination électronique. Il n'a pas vocation à être exhaustif, le choix des algorithmes qui y sont étudiés a été motivé par leur utilité, tant sur le plan pratique que sur le plan théorique.
Les prérequis pour commencer ce cours d'algorithmique sont ceux d'une terminale scientifique. Comme son nom l'indique, un prérequis est requis. L'expérience prouve que le simple fait d'avoir suivi le programme d'une terminale scientifique ne signifie nullement que ce programme a été compris et encore moins acquis. Le cours de mathématiques pour l'informatique est rédigé, il reprend certaines notions étudiées au lycée et qui sont intensivement exploitées en informatique et les développe. Certaines de ces notions sont déjà abordées dans les enseignements de mathématiques de la licence mais y trouvent une place réduite au strict nécessaire. En effet, faute de temps, l'enseignement des mathématiques se focalise plus volontiers sur les éléments d'analyse en négligeant tout ce qui est structurel, tout au moins en première année (le volume horaire d'une première année universitaire est aujourd'hui inférieur à 500 heures contre plus de 1000 heures en classe préparatoire). D'autres notions sont nouvelles mais toutes sont indispensables à la formation d'un informaticien. Le lecteur pourra s'y référer, soit pour combler ses lacunes soit pour compléter sa formation. Ce cours comprend donc peu d'éléments d'analyse car ceux-ci sont déjà étudiés dans le cours commun de mathématiques de première année scientifique.
La première année est consacrée à l'apprentissage d'algorithmes élémentaires dont la description reste très proche de la langue naturelle. Les modèles de données abordés sont atomiques, comme les nombres ou les symboles et le premier modèle composite est le modèle de donnée liste. La complexité n'est pas un objet d'étude à part entière même si l'on cherche à dénombrer les opérations caractéristiques utilisées dans la résolution d'un problème. Le langage de programmation pour l'implantation effective des algorithmes est le langage Python.
L'enseignement de deuxième année permet d'étudier progressivement des algorithmes plus sophistiqués et d'introduire des modèles et des structures de données plus évolués que les tableaux/listes et les scalaires, comme les arbres, quand bien même les tableaux/listes restent majoritaires à ce stade. La récursivité est abordée naïvement comme une simple déclinaison de la récurrence en mathématiques sans être un objet d'étude à part entière. La notion de preuve est abordée et on justifie systématiquement la justesse des algorithmes présentés sans pour autant utiliser un formalisme spécifique. C'est également ici que l'on commence l'analyse systématique de la complexité des algorithmes en introduisant un modèle de calcul abstrait (la machine ram) pour étudier précisément cette notion. L'implantation des algorithmes en tp se fait cette fois en langage C.
C'est en troisième année que les notions les plus délicates sont un sujet d'étude à part entière, comme la récursivité, les preuves de programmes, et que l'on utilise intensivement des modèles et des structures de données évolués comme les arbres, les graphes ou les relations. Les algorithmes sont parfois sophistiqués et leur analyse peut être difficile. L'évaluation de leurs fonctions de complexité reste une préoccupation majeure, en particulier la complexité moyenne qui est étudiée à chaque fois que possible. Ce cours prépare également les étudiants à aborder les théories de la calculabilité, de la complexité et de l'approximation du master.
Programme et documents de travail
Les enseignements sont essentiellement axés sur l'étude des algorithmes qui sont implantés en travaux pratiques, néanmoins un bon tiers des cours magistraux est consacré aux fondamentaux de l'algorithmique, structures et modèles de données, machine abstraite, fonction de complexité, techniques de calculs, etc. Les exercices de td sont insérés pendant les séances de cours afin de s'assurer que les notions sont acquises, de déporter la preuve de certains résultats, ou d'étudier d'autres algorithmes moins connus mais en relation avec ceux qui sont étudiés. Certaines notions théoriques sont abordées en amont de l'étude pratique des algorithmes, d'autres au fur et à mesure. Les travaux pratiques consistent à implanter en langage Python et/ou en langage C les algorithmes étudiés en cours et en travaux dirigés. Le nombre de séances de tp est notoirement insuffisant, il est impossible d'acquérir des compétences de programmeur sans une pratique régulière qui ne peut rester circonscrite aux séances de tp.