Algorithmique pour la licence

Introduction

Bien que les médias se découvrent une passion nouvelle pour les algorithmes (il ne s'écoule pas une journée sans qu'un article de presse n'en parle) l'algorithmique est une science ancienne qui a débuté bien avant l'informatique. C'est une science extrêmement dynamique et qui connaît un essort ful­gu­rant car ses applications impactent absolument tous les secteurs de la société. Sa maturité est ce­pen­dant suffisante aujourd'hui pour que ses fondamentaux soient stabilisés.

L'idée d'un cours d'algorithmique en ligne n'a rien de révolutionnaire. Elle s'est imposée pro­gres­si­ve­ment au gré des mutations d'un po­ly­copié destiné aux étudiants de licence d'informatique et de ma­thé­ma­ti­ques, qui après des années d'ajustements devait obtenir sa consécration sous forme de monographie. Les dé­ve­lop­pe­ments récents des technologies web, la qualité croissante des écrans et la pos­si­bi­li­té de rédiger les mathématiques sans trop de souffrance avec un aspect convenable, ont fini par me con­vain­cre 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 sur la question.

Outre la possibilité de le mettre à jour et de corriger les inévitables erreurs en temps réel, la dif­fu­sion d'un document en ligne permet d'atteindre un public plus vaste que le cercle de plus en plus res­treint 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 na­vi­ga­teurs sans se préoccuper des outils dont le lecteur dispose pour les utiliser. C'est très certainement cet­te unification qui a été l'élément moteur de la croissance fulgurante de javascript plus qu'une adhésion massive à un langage affublé de défauts de conception par­ti­cu­liè­re­ment agaçants.

On aborde ici les thèmes classiques de l'algorithmique à travers l'étude d'algorithmes désormais clas­si­ques et fon­da­men­taux. Ils sont présentés dans un pseudo langage de pro­gram­ma­tion dont les spé­ci­fi­ca­tions sont suffisamment floues pour pouvoir utiliser des boites noires quand cela est né­ces­sai­re. L'objectif est de se concentrer sur la nature des algorithmes que l'on étudie et de ne pas se disperser sur des difficultés techniques ac­ces­soi­res. C'est pour la même raison qu'en aucun cas nous ne faisons de pro­gram­ma­tion en cours ou en travaux dirigés. La rigidité et les spé­ci­fi­ci­tés des langages de pro­gram­ma­tion ne font que compliquer la compréhension des algorithmes, la pro­gram­ma­tion reste donc cantonnée aux travaux pratiques. Nous ferons une exception quand la nature même d'un lan­ga­ge et que les structures de données qu'il propose impactent la conception de l'al­go­ri­thme.

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é­ra­lement enseignée en trois phases qui coïncident glo­ba­le­ment 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 cons­ti­tuent certainement les éléments qui le distinguent d'un ouvrage classique d'al­go­ri­thmi­que.

À 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 algo­ri­th­mes 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. Com­me son nom l'indique un prérequis est requis, l'expérience prouve que le simple fait d'avoir suivi le pro­gram­me d'une terminale scientifique ne signifie nullement que ce programme a été compris et encore moins acquis. Un cours de mathématiques pour l'informatique est en cours de rédaction, il reprend certaines notions étudiées au lycée et qui sont intensivement exploitées en in­for­ma­ti­que 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 ma­thé­ma­ti­ques se focalise plus volontiers sur les éléments d'analyse en négligeant tout ce qui est struc­turel, tout au moins en première année (le volume horaire d'une première année universitaire est d'environ 550 heures contre 1200 heures en classe préparatoire). D'autres notions sont nouvelles mais toutes sont in­dis­pen­sa­bles à la formation d'un informaticien. Le lecteur pourra s'y référer, soit pour combler ses la­cu­nes 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 ca­rac­té­ris­ti­ques utilisées dans la résolution d'un problème. Le langage de pro­gram­ma­tion pour l'im­plan­ta­tion ef­fec­ti­ve des algorithmes est le langage Python.

L'enseignement de deuxième année permet d'étudier progressivement des algorithmes plus so­phis­ti­qué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 ma­jo­ri­tai­res à ce stade. La récursivité est abordée naïvement comme une simple déclinaison de la ré­cur­ren­ce en ma­thé­ma­ti­ques sans être un objet d'étude à part entière. C'est 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 encore en langage Python mais le langage C est introduit dès le deuxième semestre.

C'est en troisième année que les notions les plus délicates sont un sujet d'étude à part entière, com­me 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 so­phis­ti­qués et leur analyse peut être difficile. L'évaluation de leurs fonctions de complexité reste une préoc­cu­pa­tion majeure, en particulier la complexité moyenne qui est étudiée à chaque fois que possible. Le langage Python laisse la place au langage C, la définition des structures d'arbres et de listes chaînées sont plus aptes à mettre en exergue certaines questions algorithmiques. Ce cours prépare également les étudiants à aborder les théories de la calculabilité, de la complexité et de l'ap­pro­xi­ma­tion du master.

Documents de travail

Les enseignements sont essentiellement axés sur l'étude des algorithmes qui sont implantés en tra­vaux 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é, techni­ques 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 en langage C en troisième année les algorithmes étudiés en cours et en travaux dirigés. Le nombre de séances de tp est notoirement in­suf­fi­sant, surtout dans la maquette de licence si actuelle. Il est impossible d'acquérir des com­pé­ten­ces de programmeur sans une pratique régulière qui ne peut rester circonscrite aux séances de tp.

La rédaction du cours de deuxième année est achevée et quasiment stabilisée, le cours de troisième année est parcellaire, tous les chapitres ne sont pas en ligne mais devraient l'être au courant de l'année 2016-2017. Quelques chapitres du cours de première année feront progressivement leur apparition en 2016-2017 également. J'ai choisi de présenter un travail inachevé plutôt que d'attendre une hypothétique version définitive. Ces pages sont amenées à être corrigées et à évoluer en per­ma­ne­nce, c'est l'un des atouts de ce support, vos correctifs, remarques et suggestions sont donc les bien­ve­nus.

Le symbole indique que le chapitre est principalement un chapitre de cours alors que le symbole ⚙ indique que le chapitre concerne principalement l'étude d'un algorithme. Les sujets de travaux pratiques sont de difficultés variables et sont disséminés dans les chapitres, cela permet également de s'assurer que l'on est en mesure d'appliquer les résultats étudiés. Le symbole ⚒ indique que l'exer­ci­ce ou le sujet de tp est dif­ficile.

La plupart des chapitres contiennent des applications interactives qui permettent d'étudier pas à pas le fonctionnement d'un algorithme ou d'un objet et d'aider le lecteur à comprendre un concept à travers quelques expérimentations. Pour cela, les ma­té­ria­li­sés par un cadre en trai­til­lés jaunes permettent de modifier la valeur de certains paramètres. Pour les étudiants régulièrement inscrits, des qcm et exercices dynamiques seront prochainement disponibles sur la pla­te­for­me Moodle afin de s'assurer que les notions sont acquises d'une part et de préparer les séances de questions en présentiel d'autre part.

  1. Algorithmique I
  2. Algorithmique II
  3. Algorithmique III

Bibliographie

L'étudiant est invité à compléter sa formation en parcourant des ouvrages classiques ou d'autres cours sur le réseau. Il existe plusieurs excellentes références en algorithmique, je n'en citerai que quel­ques unes pour leur spectre large et pour y avoir puisé un grand nombre d'idées pour élaborer ce cours.

  1. Concepts fondamentaux de l'informatique. A. Aho, J. Ullman ;
  2. Algorithmique. T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein ;
  3. Algorithms + Data Structures = Programs, N. Wirth ;
  4. The Art of Computer Programming, D.E. Knuth.

Le premier ouvrage est très accessible et ne demande que peu de connaissances préalables si ce n'est une connaissance solide du programme de mathématiques d'une terminale scientifique. Le second ouvrage est plus technique et d'un niveau plus élevé mais constitue une source encore accessible. Ces deux ouvrages sont en revanche très volumineux et sont de nature à décourager l'étudiant qui voudrait s'y aventurer (à tort car les chapitres y sont relativement indépendants). Le livre de Niklaus Wirth, inventeur du langage Pascal entre autres, n'est plus disponible neuf mais reste une référence.

Le dernier ouvrage (en 7 volumes de près de 800 pages, dont 4 ont été publiés depuis 1966, toujours en cours de rédaction) par D. Knuth est la bible de l'algorithmique qui contient tous les problèmes fondamentaux de l'informatique et a une vocation encyclopédique affichée. Cette compilation est mise à jour régulièrement et reste la ré­fé­ren­ce absolue en la matière. Le niveau scientifique requis est élevé, voire très élevé et s'adresse principalement aux spécialistes ce qui constitue un réel frein à la lecture pour les algorithmiciens en herbe. Il n'en reste pas moins qu'en cas de doute sur une question algorithmique, c'est l'ouvrage qu'il faut consulter.