Information  –  Calcul  –  Communication    

Syllabus  de  cours      

Chapitre  1  –  Les  Algorithmes      

R.  Guerraoui  

 1. Introduction  

 Le  monde  moderne  est  régit  par  l’informatique.  Le  chapître  précédent  a  insisté  sur  cela.  Mais   qu’est   ce   que   l’informatique   au   fait  ?L’informatique   est   la   convergence   de   deux  entités:  des  algorithmes  et  des  ordinateurs.  Les  algorithmes  sont  bien  plus  anciens  que  les  ordinateurs.  Comme  nous  allons  le  voir  plus  tard  dans  ce  livre  (lecon  3),  de  manière  abstraite,   les   ordinateurs   modernes   sont   tous   équivalents   à   ce   que   l’on   appelle   la  machine  universelle  de  Turing.  Par  contre,  les  algorithmes  peuvent  être  très  différents,  même  quand  ils  résolvent  le  même  problème.      L’objectif   de   ce   chapitre   est   d’expliquer   ce   qu’est   un   algorithme.  Nous   en   donnerons  une   idée   intuitive,   avant   d’en   étudier   les   ingrédients   de   base,   de   souligner   ce   qui   est  important  dans  sa  conception,  et  en  particulier  sa  complexité.  La  matière  sous-­‐jacente  à  cette  étude  s’appelle  l’algorithmique.      

2. Tout  d’abord  deux  exemples    Avant   de   nous   lancer   dans   la   description   de   la   notion   d’algorithme,   regardons   de  manière  un  peu  abstraite  et  simplifiée  deux  exemples  qui  ont  probablement  changé  les  modes  de  vie  de  beaucoup  d’entre  nous.      

 -­‐ 2.1  Au  cœur  de  Google  :  PageRank  

 Qu’est  ce  qui  se  passe  si  on  cherche  Michael   Jackson    sur  Google  ?  On  voit  apparaître  des   liens   vers  des  pages   concernant   le   chanteur  :   sa   vie,   ses  photos,   ses   clips,   ses   fan  clubs  etc.  Tout  cela  nous  paraît  bien  logique  a  priori.  Mais  si  l’on  y  réflechit  un  peu,  cela  devrait  nous  intriguer.  Après  tout,  il  y  a  des  milliers  de  Michael  Jackson  dans  le  monde.  Pourquoi   Google   ne   nous   propose   rien   sur   Michael   Jackson   menuisier   à   Dallas  ?   Ou  Michael  Jackson  professeur  de  chant  à  San  Francisco  ?  Si  vous  étiez  ce  même  menuisier  ou  professeur   de   chant,   vous  pourriez  même  être  outrés   de  ne   voir   aucun   lien  d’une  page  qui  parle  de  vous  alors  que  vous  en  maintenez  plusieurs.      En  fait,  Google  retourne  des  liens  sur  les  pages  du  chanteur  car  il  suppose  que  c’est   le  chanteur  que  nous  cherchons.  Et   il  y  a  une   forte  probabilité  que  ce  soit   le  cas  pour   la  grande  majorité  d’entre  nous.  Mais   comment  Google  peut-­‐il   savoir  qu’il   y  a  une   forte  probabilité  que  nous  cherchons  Michael  Jackson  le  chanteur  ?      Google  ne   le  sait  pas.  Ce  que  Google  sait  par  contre,  c’est  que  parmi   toutes   les  pages  qu’il   indexe   avec   le   nom  Michal   Jackson,   celles   concernant   le   chanteur   sont   les   plus  importantes.   Deux   notions   sont   cruciales   ici  :   la   notion   d’indexation   et   la   notion  d’importance.      

Le  terme  indexer  une  page  signifie  ici  que  Google  a  extrait  de  cette  page  des  mots  clés  importants   (comme   le  nom  Michael   Jackson)  et  qu’il  est  susceptible  de   les  proposer  à  ses   utilisateurs   comme   réponses   à   leurs   requêtes.   A   l’heure   où   ce   chapitre   est   écrit,  Google   indexe  près  de  1012  pages.   Il  en   indexait  109  en  2000.  Peut-­‐être  arrivera  t-­‐il  un  jour  à  en  indexer  10100  :   le  fameux  nombre  mathématiques  googol  qui  aurait   inspiré  le  nom  de  la  société.      Grossièrement,   Google   calcule   périodiquement   l’  importance   relative   des   pages  indexées   sous   forme   d’un   score.   Lorsqu’on   soumet   une   requête   à   Google,   il   nous  affiche,   parmi   celles   qui   correspondent   à   cette   requête   (e.g.,   parmi   toutes   celles  indexées   «  Michael   Jackson  »)   celles   qui   ont   le   score   le   plus   élevé   (i.e.,   celles   du  chanteur).    Pour  calculer  le  score  d’une  page,  Google  utilise  un  procédé  systématique  :  un  algorithme  appelé  PageRank,  du  nom  du  créateur  de  la  société,  Larry  Page,  ainsi  que  de  l’entité  centrale  du  système  Google  :   la  page  web.  Cet  algorithme  a  été  inventé  par  Larry  Page  et  Sergey  Brin  à  l’université  de  Stanford  en  1996.  Il  y  a  eu  plusieurs  versions  de   cet   algorithme  et   beaucoup  de  détails   sont   secrets  :  mais   l’idée   centrale  que  nous  allons  présenter  ici  est  assez  simple.      Comme  son  nom   l’indique,   l’algorithme  PageRank   permet  de   classer   l’importance  des  pages  webs   indexées  par  Google.   Il   se  base  pour  cela   sur   les   liens   entre   les  pages.  En  effet,  chaque  page  typiquement  cite  un  certain  nombre  d’autres  pages  :  elle  a  des  liens  vers  ces  pages.  Quelqu’un  qui  atterit  sur  une  page  p  peut  trouver  un  lien  vers  une  page  q   et   y   aller   directement.   C’est   ce   qui   se   passe   quand   dans   une   page   wikipedia   sur  PageRank  on  rencontre  un  lien  vers  la  page  de  Larry  Page.      Alors  comment  PageRank  fonctionne  t-­‐il  ?  Avant  de  se  lancer  dans  sa  description  de  cet  algorithme,  il  est  important  de  rappeler  le  problème  résolu  :      Il   s’agit  de  calculer   le  score  d’une  page,  censé  représenter  son   importance  relative  aux  pages  du  système,  en  fonction  des  liens  entre  ces  pages.      L’idée  de  PageRank   est  de   représenter   le   score  d’une  page  p   par   la  probabilité  qu’un  utilisateur   qui   se   baladerait   dans   une   bibliothèque   constituée   de   toutes   les   pages,  atterrisse  sur  p.    Cette  probabilité  est  d’autant  plus  grande  que  :      

(1)  Il  y  a  des  pages  q  qui  ont  des  liens  vers  p;      (2)  Ces  pages  q  ont  elles-­‐même  un  score  important  ;      (3)  Ces  pages  q  ont  peu  de  liens  vers  d’autres  pages  p’  par  ailleurs.      

Une  manière  de  synthétiser  (1),  (2)  et  (3)  est  de  faire  la  somme  des  scores  des  pages  q  ayant  un   lien  vers  p  en  divisant   chacun  par   le  nombre  de   liens   sortant  de  q.  Ainsi,  en  

première  approximation,  si  l’on  représente  par  liens(q)  le  nombre  de  liens  sortant  d’une  page  q:  

                 Score(p)  =  Somme(Score(q)/liens(q))                                                                    –  pour  toutes  les  pages  q  ayant  un  lien  vers  p      En  gros,  c’est  comme  si  chaque  page  avait  un  certain  nombre  de  votes,  représenté  par  son   score,   et   qu’elle   pouvait   transferrer   tous   ses   votes   à   une   autre   page,   ou   les  distribuer  sur  d’autres  pages.  Considèrons  le  petit  dessin  ci-­‐dessous  représentant  quatre  pages  :  q  ayant  un  lien  vers  p  et  p’  et  q’  ayant  un  lien  vers  p’.  Supposons  par  ailleurs  que  les  scores  de  q  et  q’  sont  1.    On  aura  :  Score(p)  =  0.5  et  Score(p’)  =  1.5.    

En   fait,   l’algorithme   PageRank   prend   aussi   en   compte   le   fait   qu’un   utilisateur   qui   se  balade  dans  la  bibliothèque  puisse  aller  directement  d’une  page  à  une  autre  sans  passer  par   des   liens,   un   peu   comme   s’il   sautait   par   dessus   les  murs   de   la   bibliothèque.   Plus  précisément,  PageRank   relativise   le   score   ci-­‐dessus   en   le  multipliant   par   un  damping  factor  d  entre  0  et  1,  auquel  il  rajouter  (1-­‐d)  pour  avoir  une  probabilité.  Ainsi  :      

PageRank(p)  =  (1-­‐d)  +  d  *  Somme(PageRank(q)/liens(q))    – pour  toutes  les  pages  q  ayant  un  lien  vers  p  

   Le  damping  factor  est  en  général  0.85  ;    Ainsi  :                      PageRank(p)  =  0.15  +  0.85  *  Somme(PageRank(q)/liens(q))    

– pour  toutes  les  pages  q  ayant  un  lien  vers  p    

Si   l’on  revient  à   l’exemple  ci-­‐dessus,  on  aura  en   fait  :  PageRank(p)  =  0.15  +  0.85*0.5  =  0.575  et    PageRank(p’)  =  1.425.    

 Comme   on   calcule   le   score   d’une   page   en   fonction   de   scores   d’autres   pages,   il   est  légitime   de   se   poser   la   question,   et   comment   ont   été   calculés   les   scores   des   pages  initiales,   i.e.,   q   et   q’     ci-­‐dessus  ?   Nous   y   reviendrons,   mais   PageRank   suppose   une  procédure  d’initialisation  préalables  des  scores  des  pages,  en  l’occurence  q  et  q’  ici.      Nous   sommes   quasiment   prêts   à   présenter   l’algorithme   PageRank  ;   quasiment   car   il  nous   faut   un   moyen   de   l’exprimer.   Lorsqu’il   s’agit   d’exécuter   un   algorithme   par   un  ordinateur,  nous  passons  par  un  langage  de  programmation.  Souvent  néanmoins,  il  est  important   de   d’abord   exprimer   l’algorithme  dans   une   langue  naturelle   qui   permet   de  mieux  comprendre  le  procédé  systématique  que  l’on  a  en  tête.  C’est  ce  que  nous  allons  faire  dans  ce  chapître  (et  d’ailleurs  dans  tout  le  livre).        Voici  quelques  éléments  de  notation  que  nous  utiliserons  :    

 - Entrée :   indique   ce   que   l’utilisateur   de   l’algorithme   doit   transmettre  

comme  paramètre  à  cet  algorithme  ;  dans  notre  exemple  ici,  il  s’agit  de  la  page  dont  on  veut  calculer  le  score  ainsi  que  le  graphe  des  pages  du  système.      

 - Sortie : indique   ce   que   l’algorithme   retourne   à   son   utilisateur  ;   dans  

notre  exemple  ci-­‐dessous,  il  s’agit  du  score  de  la  page.      

- Tant que : signifie  que  l’on  veut  répéter  des  instructions  plusieurs  fois    -­‐   x   ←   E  :   signifie   que   la   valeur   de   l’expression   E   est   affectée   à   x   (x   est   une  

variable  :  ce  qui  signifie  qu’elle  peut  contenir  différentes  valeurs  à  différents  moments  de  l’exécution  d’un  algorithme)  

 Sortir :  signifie  que  l’algorithme  s’arrête  pour  sortir  une  valeur  

 -­‐   //   Est   un   signe   qui   précède   un   commentaire   qui   ne   fait   pas   partie   de  

l’algorithme  mais  qui  permet  d’expliquer  certains  détails  à  celui  qui  le  lit      

 

Avec  ces  notations,  voici  une  manière  d’exprimer  l’algorithme  PageRank.    

 Algorithme  1.A  :  PageRank(p,G)    L’algorithme   calcule   le   score  d’une  page  p   en   fonction  des   scores  des  pages   ayant  des  liens  vers  p  dans  le  graphe  G.  On  note     liens(q)   le  nombre  de  liens  de  la  page  q  vers  d’autres  pages  de  G.    Entrée  :  p,  G  

Sortie :  score    //  Score  de  la  page  p    score  ←  0  //  Au  départ  score  est  égal  0  L  ←  G  //  on  met  le  graphe  G  dans  une  variable  L  que  l’on  peut  ensuite  manipuler  Tant que  L  est  non  vide  :  //  Parcourir  l’ensemble  L              e  ←  extraire  un  élément  de  L  //  Vider  petit  à  petit  L            score  ←  score  +  PageRank(e,G)/liens(e)    //  Calcul  intermédiaire  du  score      score  ←  0.15  +  0.85  *  score  //  Prise  en  compte  du  damping  factor  Sortir :  score  

 

Notez  qu’il  n’est  pas  nécessaire  d’initialiser  la  variable  e  par  exemple  car  la  première  fois  qu’elle   est   utilisée,   elle   l’est   pour   contenir   une   valeur.   Par   contre,   il   a   été   nécessaire  d’initialiser  la  variable  score  car  la  première  fois  qu’elle  est  utilisée,  c’est  pour  y  chercher  une  valeur.  Notez  aussi  que   l’on  suppose   ici  que   l’extraction  d’un  élément  de  L  enlève  en   effet   cet   élément  :   la   taille   de   L   va   donc   diminuer   à   chaque   itération   de   la   boucle  Tant que.    Enfin,   la   notation   score  ←   score   +   PageRank(e,G)/liens(e)   peut   sembler   troublante   à  double   titre.   D’une   part,   on   y   retrouve   la   variable   score   à   gauche   et   à   droite   de  l’affection  ;   en   fait,   l’idée   est   d’évaluer   la   valeur   de   la   variable   score     à   droite   de  l’affectation,   d’effectuer   un   calcul   (une   division,   puis   une   somme),   puis   d’affecter   le  résultat  de  ce  calcul  dans  la  variable  score.  D’autre  part,  comme,  l’algorithme  s’utilise  de  manière   itérative  :   on   a   besoin   de   calculer   le   scores   de   pages   pour   calculer   le   score  d’autres  pages.  En  fait,  on  peut  supposer  qu’à  la  base,  toutes  les  pages  sont  initialisées  avec  le  même  score  :  1/n  ou  n  désigne  le  nombre  total  de  pages  dans  G.  Puis  on  répète  le  calcul  du  score  de  chaque  page  en  utilisant  les  scores  précédents.      Si  l’ensemble  des  pages  n’évolue  pas,  les  calculs  finiront  par  converger  sur  un  seul  score  par  page  après  un  certain  nombre  d’itérations  (ceci  est  un  résultat  mathématique  important).  Mais  le  Web  évolue  toujours  et  les  scores  continueront  donc  d’évoluer.    

-­‐ 2.2  Au  cœur  de  Facebook  :  EdgeRank    A   la   base,   Facebook   avait   pour   objectif   de   connecter   les   étudiants   de   l’Université   de  Harvard.   A   l’heure   où   ce   chapitre   est   écrit.   Facebook   connecte   près   d'un   milliard  d’utilisateurs.   Facebook   permet   à   chacun   de   partager   en   temps   réel   toutes   sortes  d’informations   avec   ses   “amis”:   des   notes   décrivant   ses   états   d’âme   ou   ses   activités  quotidiennes,   des   photos,   de   la   musique,   des   recommandations   pour   des   livres,   des  liens  vers  des  articles  de  journaux,  etc.      En  gros,  chaque  utilisateur  possède  deux  espaces:  un  espace  qu’il  utilise  pour  décrire  les  informations  qu’il  souhaite  partager,  ses  posts,  et  un  espace  dans  lequel  il  voit  défiler  les  posts  partagés  par  ses  amis.    Ce  second  espace  est  parfois  appelé  fil  d’actualité.        Mais  

quelles   informations   Facebook   décide   t-­‐il   d'afficher   sur   le   fil   d'actualité   de   chaque  personne?      Toutes  les  posts  de  ses  amis?  Certainement  pas.  Facebook  fait  une  sélection  radicale  et  en   élimine   près   de   90%.   D'une   part   Facebook   fait   cela   pour   ne   pas  inonder   les  utilisateurs   d'informations   qui   disparaîtraient   en   une   fraction   de   seconde   à   cause   de  leur  trop  grand  nombre.    D'autre  part  Facebook  filtre  les  informations  afin  que  chacun  trouve  son  fil  d'actualité  suffisamment   intéressant  pour  rester  connecté  et  être  actif  à  son   tour.    Plus   il   y   a   de   personnes   connectées   et   plus   Facebook   peut  monnayer   son  support  publicitaire.        Alors  sur  quoi  Facebook  se  base  t-­‐il  pour  faire  sa  sélection  de  ce  qui  doit  être  affiché  sur  le  fil  d’actualité  de  chaque  personne?    Sur  un  algorithme  appelé  EdgeRank.  Le  principe  de  cet  algorithme  n’est  pas  sorcier.  Si  on  omet  certains  détails,  en  particulier  de  mise  en  oeuvre  et  d’optimisation,  on  peut  le  décrire  de  manière  assez  simple.      Avant   de   se   lancer   dans   cette   description,   il   est   important   de   rappeler   le   problème  résolu  pas  l’algorithme  EdgeRank.    Il  s’agit,  pour  chaque  utilisateur  u  de  déterminer  le  score  des  posts  partagés  par  les  amis  de  u  :  plus  le  score  d’un  post  p  est  élevé  et  plus  u  devrait  trouver  p  intéressant.      En   première   approximation,   le   score   pour   un  utilisateur   u,   d’un   post   p   émis   par   un  utilisateur  v,  correspond  au  produit  de  trois  variables:    a  *  t  *  f.    

-­‐   La   variable   a   désigne   l'affinité   de   v   par   rapport   à   u.   Plus   v   à   l'habitude  d’aimer  ou  de  commenter  des  informations  postées  par  u,  voire  d’envoyer  des  messages  à  u,  et  plus  a  sera  grand.  Cette  notion  d’affinité  est  asymétrique  et  le  fait  que  v  soit  fan  de  u  n’implique  pas  l’inverse.        -­‐   La   variable   t   représente   le   type  du  post:  une  photo  a  plus  de  poids  qu'un  petit  texte  par  exemple.    

 -­‐  La  variable  f   représente   la  fraîcheur  du  poste:  plus  un  post  est  ancien,  plus  f  diminue.      

 La   notion   de   score   dans   ce   contexte   est   relative.   Le   score   d’un   post   p   posté   par   un  utilisateur  v  peut  être  différent  pour  deux  amis  de  v,  u  et  u’.      En  fait,  EdgeRank  ne  fait  pas  simplement  un  produit,  mais  une  somme  de  produits.    A  chaque  post  p  est  associé  un  ensemble  de  liens.  Le  premier  lien  est  celui  de  la  création  de   p:   il   est   généré   par   l’utilisateur   v   qui   a   partagé   p.     A   chaque   fois   qu’un   nouvel  utilisateur  v’  souligne  qu’il  aime  p  ou  le  commente,  un  nouveau  lien  est  généré  par  v’.  

Plus   un   post   p   est   “liké”   ou   commenté   par   des   amis   de   u   et   plus   p   a   de   chances  d’apparaitre  sur  le  fil  d’actualités  de  u.      Chacun  des  liens  sur  p  a  donc  un  score  qui  correspond  à  un  produit  de  variables  a  *  t  *  f.  Le  score  de  p  est  la  somme  des  scores  des  liens.      

EdgeRank(p,u)  =  Somme(a*t*f)    – pour  tous  les  liens  vers  p  

 Algorithme  1.B  :  EdgeRank(p,u,G)    L’algorithme   calcule   le   score   du   post   p   pour   l’utilisateur   u   dans   un   graphe   G.   On  désigne   par  G(p)     l’ensemble   des   liens   vers   p:   chacun   de   ces   liens   l   représente   un  élément  d’information  mis  par  un  utilisateur  v(l).  Le  premier   lien  est   la  création  du  post  lui  même.      Entrée :  p,  u    Sortie :  score  //  score  du  post  p  pour  l’utilisateur  u      score  ←  0  //  Initialisation  de  la  variable  score  liens  ←  G(p)  //  Initialisation  d’une  variable  liens    Tant que  liens  est  non  vide  :  //  Parcourir  l’ensemble  des  liens              l  ←  extraire  un  élément  de  liens    //  Vider  petit  à  petit  liens            a  ←  affinité(u,v(l)))  //  Affinité  de  u  par  rapport  au  créateur  de  l              t  ←  type(l)              f  ←  1/d  durée  de  vie  de  l  //  Plus  l  est  vieux  et  plus  f  est  petit            score  ←  score    +  a  *  t  *  f  //  Calcul  de  la  somme  pour  le  score  du  poste    

 

On   a   suppose   ci-­‐dessus   que   le   calcul   de   l’affinité   est   déterminé   par   une   fonction  affinité(u,v)  que  l’on  suppose  disponible  au  concepteur  de  l’algorithme  EdgeRank.  Bien  entendu,  ce  calcul  est  lui  aussi  à  travers  un  autre  algorithme.  Nous  y  reviendrons.      

3. Qu’est  ce  qu’un  algorithme  ?    Nous   avons   vu   qu’un   algorithme   est   une   sorte   de   procédé   systématique.   Plus  précisément,   c’est   un   ensemble   ordonné   d’instructions   élémentaires   permettant   de  résoudre  un  problème.  Plusieurs   concepts   sont   importants  dans   cette  définition.   Tout  d’abord  le  fait  que  ce  soit  un  ensemble  ordonné,  c’est  à  dire  muni  d’une  relation  d’ordre  qui   stipule  quelles   instructions  doivent   s’exécuter  avant  quelles  autres.  Ensuite,   le   fait  que   ces   instructions   soient   élémentaires   par   rapport   au   problème   général   résolu   par  l’algorithme   est   une   motivation   centrale   de   la   conception   même   d’un   algorithme  :  concevoir  un  algorithme   signifie  déconstruire   un  problème.  En  général,   le  but  est  que  

ces   instructions   soient   tellement   élémentaires   qu’il   est   possible   de   les   exécuter   sans  réflechir  :   comme   le   fait   un   ordinateur.   Mais   comme   nous   allons   le   voir,   la   notion  d’instruction  élémentaire  est  très  relative.    

-­‐ 3.1  Au  sens  général    

Certes,   nous   utilisons   souvent   le   terme   algorithme   pour   désigner   l’ensemble   des  instructions   executées   par   un   ordinateur   pour   résoudre   un   problème.   Mais   nous  l’utilisons  aussi,  et  à  bon  escient,  pour  décrire  un  ensemble  d’instructions  executées  par  un  humain  pour  accomplir  une  tâche.      Pour  se  préparer  à  un  marathon  qui  a  lieu  dans  12  semaines,  avec  comme  objectif  de  le  finir   en   moins   de   3h30,   un   entraîneur   pourrait   vous   conseiller   l’algorithme  d’entrainement   suivant.   L’idée   est   d’alterner   des   séances   courtes   et   rapides,   des  séances  longues  et  lentes  et  des  jours  de  repos.        

 Algorithmes  1.C  :  Marathon  en  3h30    Pour  semaine  de  -­‐12  à  0  :            Pour  jour  de  1  à  7:                    Si  jour  =  3    ou  6  :  repos                    Si  jour  =    1  ou  5:                              Pour  série  de  1  à  20  :                                                    courir  40s  à  15km/h                                                  repos  pendant  20s                  Si  jour  =    2  ou  4:  courir  50mn  à  11km/h                  Si  jour  =  7:                                                      courir  1h30  à  11km/h                                                      courir  30mn  à  13km/h      

 Cet   algorithme  est   une   sorte   de   promesse   que   si   toutes   les   instructions   élémentaires  sont  executées,  l’objectif  sera  atteint.  Si  on  n’arrive  pas  à  courir  40s  à  15km/h,  il  y  a  peu  de   chances   que   l’objectif   soit   atteint.   Mais   si   on   est   capable   de   suivre   à   la   lettre  l’algorithme,   il   y   a   de   fortes   chances   d’y   arriver.   Il   est   important   de   noter   ici   que   les  instructions  sont  assez  précises  et  qu’il  n’y  a  pas  besoin  de  réflechir  pour  les  exécuter.  En  particulier,  il  n’est  pas  important  de  savoir  pourquoi  on  arrivera  à  courir  en  moins  de  3h30:   des   experts   en   marathon   ont   fait   des   expériences   avec   des   coureurs   et   sont  arrivés   à   cet   algorithme.   Pour   le   coureur   amateur,   il   suffit   de   faire   confiance   à  l’algorithme.    

 -­‐ 3.2  Au  sens  arithmétique  

 Bien  avant  les  ordinateurs,  les  mathématiciens  utilisaient  les  algorithmes  pour  effectuer  de  manière  automatique  certains  calculs.  L’un  des  exemples  les  plus  anciens  dont  nous  avons  connaissance  est   l’algorithme  d’Euclide  qui  permet  de  déterminer   le  plus  grand  divisieur  commun  entre  deux  entiers  a  et  b.    

 Algorithme  1.D  :  PGCD(a,b)    Entrée :  Deux  entiers  naturels  non  nuls  a  et  b  tels  que  a  >=  b  Sortie :  pgcd        Répéter:      r  ←  reste  de  la  division  de  a  par  b        a  ←  b        b  ←  r  Tant que  r  >  0    Sortir :  a  

 Peu   de   gens   aujourd’hui   savent   qu’à   l’origine,   Euclide   avait   utilisé   des   arguments  géomètriques   pour   arriver   à   cet   algorithme.   La   plupart   d’entre   nous   se   contente  d’exécuter   les   instructions   élémentaires  de   manière   répétitive:   à   savoir   une   simple  division,   jusqu’à   arriver   au   résultat.   Autrement   dit,   on   exécute   l’algorithme   comme   si  nous  étions  des  automates.  C’est  bien  cela  l’idée  sous-­‐jacente  à  l’algorithmique.    

 -­‐ 3.3  Au  sens  algèbrique    

 En   fait,   «  Algorithme  »   est   le   nom   du   mathématicien   Mohammed   Al-­‐Khawarizmi.   Ce  dernier  avait  très   jeune  traduit  au  9ème  siècle  en  arabe   le   livre  d’Euclide  Les  Eléments  :  un   traité  de  géomètrie   rédigé  près  de  3   siècles  avant   JC.     Ensuite,  et  parmi  beaucoup  d’autres  choses,  Khawarizmi  avait  inventé  la  notion  d’inconnue  (x  vient  de  «  chay  »  -­‐  la  chose   en   arabe),   et   avait   proposé   une   manière   simple   de   résoudre   des   équations  complexes  dans  son  fameux  ouvrage  sur  le  calcul  par  la  comparaison  et  la  restauration.  La  motivation  était  de  permettre  à  des  non-­‐mathématiciens  de  résoudre  des  problèmes  compliqués  en  exécutant  des  instructions  simples.  La  même  motivation  qu’aujourd’hui.  Lorsque   l’on   résoud   des   équations   du   second   degré,   ce   que   l’on   appelle   aussi   des  équations   quadratiques,   on   exécute   l’algorithme   suivant.   On   fait   cela   comme   des  automates,   sans   savoir   que   pour   le   concevoir,   il   a   fallu   passer   par   des   résolutions  géomètriques,  puis  par  des  identités  remarquables.    

 Algorithme  1.E  :  Quadratique(a,b,c)      Entrée :  Trois  réels  non  nuls  a,  b  et  c  ;  a  >  0  

Sortie :  ensemble  de  réels      Delta  ←  b2  –  4ac    Si  Delta  <  0  :            Sortir :  φ    Si  Delta  =  0  :            Sortir :  ⎨-­‐b/(2*a)⎬    Si  Delta  >  0  :                x1  =  -­‐b-­‐Racine(Delta)/(2*a)              x2  =  -­‐b+Racine(Delta)/(2*a)   Sortir :  ⎨  x1,x2⎬    

 Dans   les  trois  cas  ci-­‐dessus,  une   idée  centrale  qui  ressort  est  qu’il  n’est  pas  nécessaire  de   comprendre   le   problème,   et   pourquoi   l’algorithme   marche,   pour   qu’il   marche.   Il  suffit  de  savoir  exécuter  les  instructions  élémentaires.        

4. Les  ingrédients  de  base  d’un  algorithme    Comme   expliqué   et   illustré   ci-­‐dessus  :   un   algorithme   est   un   ensemble   ordonné  d’instructions   élémentaires.   Deux   choses   sont   importantes   ici  :   les   instructions  élémentaires  et  la  relation  d’ordre.      

-­‐ 4.1  Des  instructions  élémentaires      En  toute  généralité,  la  notion  d’instruction  élémentaire  est  relative  au  problème  résolu.  Dans  la  plupart  des  exemples  ci-­‐dessus,  les  instructions  élémentaires  consistent  à  :  

-­‐  Assigner  une  valeur  à  une  variable  -­‐   Effectuer   des   calculs   élémentaires,   telles   que   des     division/multiplication,  addition/soustraction,  extraction  de  racine,  etc.    -­‐  Manipuler  des  structures  de  données  simples,  comme  extraire  un  élément  d’un  ensemble,  accèder  au  ième  élément  d’une  liste,  etc    

Ces   instructions   sont   élémentaires   par   rapport   au   problème   général     qui   consiste   à  résoudre  une  équation  quadratique  ou  calculer  le  score  d’un  post  par  exemple.    Dans   les   cas   de   l’algorithme   de   l’entraînement   au   marathon,   les   instructions  élémentaires  consistent  à  courir  à  une  certaine  vitesse  pendant  un  certains  temps  :  au  maximum   2h.   Chacune   de   ces   instructions   est   élémentaire   par   rapport   au   problème  général  qui  consiste  à  courir  pendant  42km  à  3h30  le  jour  j  (12  semaines  après  le  début  de  l’entrainement).      Dans   le   cas   de   EdgeRank,   on   a   considéré   comme   instruction   élémentaire   le   fait   de  calculer   par   exemple   une   affinité   d’un   utilisateur   par   rapport   à   un   autre.   Il   est   assez  

évident   que   cette   instruction   cache   un   sous-­‐algorithme   qui   lui   aussi   doit   être  déconstruit   en   instructions   élémentaires   pour   être   exécuté   sur   un   ordinateur.   Nous  verrons   souvent   des   cas   d’algorithmes   que   l’on   construit   à   partir   d’instructions  élémentaires,   puis   que   l’on   utilise   ensuite   comme   instructions   élémentaires   dans  d’autres  algorithmes,  plus  sophistiqués.      

-­‐ 4.2  Des  structures  de  contrôle      Il  est  très  rare  que  l’on  souhaite  toujours  exécuter  les  instructions  d’un  algorithme  de  la  même  manière.  Souvent,  on  souhaite  que  cet  ordre  dépende  de  conditions  spécifiques  représentées  par  la  valeur  des  variables  manipulées.  C’est  le  cas  de  tous  les  algorithmes  étudiés  dans   ce   chapitre.  Dans   la   résolution  des  équations  quadratiques  par  exemple,  les  valeurs  de  x1  et  x2  dépendent  de  la  valeur  du  discriminant  Delta.  Dans  l’algorithme  du  marathon,  l’entrainement  dépend  du  jour  de  la  semaine.      Parmi  les  différents  types  de  structure  de  contrôle,  en  voici  quatre  principales  :    (a) L’interruption  de  l’algorithme:  Sortir :  x.        L’algorithme   est   arrêté   et   il   retourne   la   valeur   x.   Cela   interrompt   la   séquence  d’exécution  des   instructions.  Dans   la   résolution  d’une  équation  quadratique  ci-­‐dessus,  on  a  écrit:    

 Si  Delta  <  0  :            Sortir :  φ  

 Les   instructions   après   l’expression   «  Sortir :  φ   »   ne   seront   pas   exécutées   si   cette  instruction  est  elle-­‐même  exécutée  par  l’algorithme.      (b)  Les  branchements  conditionnels  :  Si  A  :  B  Sinon :  C.      Dans  cette  expression,  A  doit  être  évaluée  et  retourner  une    valeur  booléenne  (vraie  ou  fausse)  ;  B  et  C  sont  des  ensembles  d’instructions.    L’expression  «  Si  A  :  B  Sinon :  C  «    signifie  que  si  A  est  vrai,  alors  il  faut  exécuter  les  instructions  de  B,  sinon  on  exécutera  les  instructions  de  C.  La  partie  «    Sinon:  C  «  n’est  nécessaire  que  si  l’on  désire  expliciter  le   fait   que   C   ne   doit   s’exécuter   que   si   A   est   faux.   Dans   la   résolution   d’une   équation  quadratique  ci-­‐dessus,  on  a  écrit:  

   

Si  Delta  <  0  :            Sortir :  φ  Si  Delta  =  0  :    

         Sortir ⎨-­‐b/(2*a)⎬  Si  Delta  >  0  :                x1  =  -­‐b-­‐Racine(Delta)/(2*a)              x2  =  -­‐b+Racine(Delta)/(2*a)   Sortir :  ⎨  x1,x2⎬  

   

On  aurait  aussi  pu  écrire  :      

Si  Delta  <  0  :            Sortir :  φ  Si  Delta  =  0  :              x1  ←  -­‐b/(2*a)            x2  ←  -­‐b/(2*a)  Sinon  :              x1  =  -­‐b-­‐Racine(Delta)/(2*a)              x2  =  -­‐b+Racine(Delta)/(2*a)  Sortir :  ⎨  x1,x2⎬    Ou  alors  :    

 Si  Delta  <  0  :            Sortir :  φ  Si  Delta  =  0  :              x1  ←  -­‐b/(2*a)            x2  ←  -­‐b/(2*a)   Sortir :  ⎨  x1,x2⎬  //  On  sort  de  l’algorithme  x1  =  -­‐b-­‐Racine(Delta)/(2*a)  x2  =  -­‐b+Racine(Delta)/(2*a)  Sortir :  ⎨  x1,x2⎬    Dans   la  dernière  alternative  ci-­‐dessus,  on  utilise   implicitement   le   fait  que  «  Sortir :  (x1,x2)  »  est  une  structure  de  contrôle  qui  permet  d’arrêter  l’exécution  en  agissant  donc  sur  l’ordre  entre  les  instructions.    (c  )  Les  boucles  conditionnelles  :  Tant que  A  :  B.      Dans  cette  expression  A  a  une  valeur  booléenne  (vraie  ou  fausse)  et  B  est  un  ensemble  d’instructions.  Tant  que  A  est  vraie  on  répète  l’ensemble  des  instructions  de  B.  Dès  que  A   est   fausse,   on   passe   directement   aux   instructions   qui   suivent   B.   Dans   l’algorithme  PageRank  par  exemple  :    

 ….    

Tant que  L(l)  est  non  vide  :          e  ←  extraire  un  élément  de  L(l)    

 Une   autre   forme   de   la   même   boucle   conditionnelle   consiste   à   exécuter   d’abord   une  itération  de  la  boucle  avant  de  vérifier  si  une  condition  est  vraie.  Ainsi,  dans  l’algorithme  d’Euclide  :  

 Répéter:      r  ←  reste  de  la  division  de  a  par  b        a  ←  b        b  ←  r  Tant que  r  >  0    La  différence  est  qu’ici  on  ne  peut  évaluer  la  condition  tant  que  r  n’as  pas  de  valeur.    

 (d)  Les  itérations  :  Pour  X  allant  de  Y  à  Z  :  I.      Dans  cette  expression  X,  Y  et  Z  sont  typiquement  des  entiers  naturels  ;  Z  est  supérieur  strictement  à  Y.  alors  que   I  est  un  semble  d’instructions.  X  vaudra  tout  d’abord  Y,  puis  Y+1,  puis  Y+2,  etc  jusqu’à  Z.  Dans  l’exemble  de  l’entrainement  au  marathon  :    

 Pour  jour  de 1  à  7  :                    Si  jour  =  3    ou  6  :  repos    

   

Mais  encore  !      On  retrouve   les  structures  de  contrôle  décrites  ci-­‐dessus  sous  différentes   formes  dans  les   langages   de   programmation   utilisés   aujourd’hui.   Mais   on   en   retrouve   aussi   sous  d’autres   formes.   Par   exemple,   dans   les   langages   de   programmation   permettant  d’exécuter   des   algorithmes   sur   plusieurs   processeurs,   on   retrouve   des   structures   qui  stipulent  que  certains  sous-­‐ensembles  d’exécutions  peuvent  s’exécuter  en  parallèle,  ou  au  contraire  qu’ils  doivent  s’exécuter  de  manière  séquentielle.    Nous  ne  verrons  pas  de  telles  structures  dans  cet  ouvrage.      

 5. Qu’est  ce  qu’un  algorithme  correct  ?    

 On   peut   voir   l’algorithme   comme   un   contrat   impliquant   trois   participants  :   (1)  l’utilisateur   de   l’algorithme,   qui   propose   par   exemple   une   valeur  d’entrée   et   souhaite  récupérer  une  valeur  de  sortie,  (2)   l’exécutant  des  instructions  de  base  de  l’algorithme  et  (3)  Le  concepteur  de  l’algorithme.    

Dans  certains  cas,  certains  de  ces  acteurs  sont  les  mêmes.  Dans  l’exemple  du  marathon,  le   concepteur   de   l’algorithme   est   par   exemple   un   professionnel   de   la   course   longue  distance.  Celui  qui  s’en  sert  est  le  même  que  celui  qui  exécute  les  instructions  de  base  de   l’algorithme.  Dans   le   cas  des  algorithmes  d’EdgeRank   et  PageRank,   les   instructions  sont  executées  par  des  machines  puissantes.  Les  concepteurs  des  algorithmes  sont  des  ingénieurs   en   Californie.   Ceux   qui   les   utilisent   sont   éparpillés   aux   quatre   coins   du  monde.   Dans   le   cas   des   algorithmes   d’Euclide   ou   de   l’algorithme   de   résolution  d’équations   quadratiques,   les   concepteurs   sont   des   grands   mathématiciens,   les  utilisateurs   sont   souvent   des   élèves   et   les   instructions   élémentaires   peuvent   être  exécutées  par  des  calculatrices.    

-­‐ (1)  Les  valeurs  d’entrée  d’un  algorithme    

Dans  le  cas  de  l’algorithme  d’Euclide,  l’utilisateur  doit  entrer  deux  entiers  non  nuls  a  et  b  tels  que  a  >=  b.  C’est  sa  part  du  contrat.  Si  l’un  des  deux  est  nul,  ou  a  est  inférieur  à  b,  l’algorithme  ne  fonctionnerait  pas.  Cela  ne  serait  pas  la  responsabilité  du  concepteur  de  l’algorithme.   Une   source   d’erreur   classique   est   d’utiliser   des   entrées   pour   lesquelles  l’algorithme  n’est  pas  concu.        En  fait,  souvent,  on  rajoute  parfois  des  tests  pour  nous  assurer  que  les  valeurs  d’entrées  sont  conformes  à  la  spécification  de  l’algorithme.  Dans  le  cas  de  l’algorithme  d’Euclide,  nous   pourrions   rajouter   un   test   au   début   de   l’algorithme   qui   testerait   si   les   valeurs  entrées  pour  a   et  b   ne   sont  pas   correctes   et   retournerait   par   exemple   la   valeur  «  0  »  signalant   une   erreur,   sans   entrer   dans   la   boucle   de   répétition   des   divisions.   (Le   pgdc  n’est   pas   sensé   être   «  0  »   donc   l’utilisateur   saurait   qu’il   y   un   problème).   Voici   cet  exemple  :  

 Algorithme  1.D’  :  PGCD’(a,b)      Entrée :  Deux  entiers  naturels  non  nuls  a  et  b  tels  que  a  >=  b  Sortie  :  pgcd        Si  (a  =  0)  ou  (b  =  0)  ou  (a  <  b)  :            Sortir :  0    Répéter:      r  ←  reste  de  la  division  de  a  par  b        a  ←  b        b  ←  r  Tant que  r  >  0  :          pdgc  ←  a  Sortir :  a  

 Rajouter  de  tels   tests  est  une  manière  de  rendre   l’algorithme  plus  général  en  tolérant  plus  d’erreurs  de  l’utilisateur.    

 -­‐ (2)  Les  instructions  élémentaires    

 La   deuxième   partie   du   contrat   concerne   les   instructions   élémentaires.   Le   concepteur  d’un   algorithme   ne   peut   rien   assurer   si   ces   instructions   ne   sont   pas   exécutées  correctement.  Une  panne  de   la  machine  sous-­‐jacente  par  exemple  ne  signifie  pas  que  l’algorithme  n’est  pas  correct.      Il  est  par  ailleurs   important  de  se   rappeler  que   la  notion  d’instruction  élémentaire  est  une  notion  relative.  Parfois,  cette  instruction  est  elle  même  mise  en  œuvre  à  travers  un  sous-­‐algorithme   qui   retourne   une   valeur   (une   sortie).   La   défaillance   de   ce   sous-­‐algorithme,   qui   peut   se   traduire   par   une   sortie   non   correcte,   ne   signifie   pas   que  l’algorithme  général  n’est  pas  correct.    

-­‐ (3)  L’algorithme  en  question      Donc   si   les   entrées   sont   correctes   et   les   instructions   élémentaires   exécutées  correctement,   la   responsabilité   du   concepteur   de   l’algorithme   est   d’assurer   que   son  algorithme  est  correct.      Cela  recouvre  deux  aspects.  Il  s’agit  d’une  part  de  s’assurer  que  l’algorithme  ne  retourne  pas   de   valeurs   fausses.   D’autre   part,   il   s’agit   de   s’assurer   que   l’algorithme   retourne  toujours  une  valeur.  Dans  le  premier  cas,  on  parle  parfois  de  propriété  de  sûreté.  Dans  le  second  cas,  on  parle  parfois  de  propriété  de  terminaison.      Il  y  a  des  techniques  de  preuves  mathématiques  qui  permettent  de  se  convaincre  que  ces   deux   propriétés   sont   assurées.   Il   y   a   aussi   des   algorithmes   de   vérification  automatique  qui  permettent  de  déceler  des  risques  de  violation  de  ces  propriétés.  (Un  algorithme  de  vérification  a  pour  entrée  un  autre  algorithme).  Aucune  de  ces  techniques  n’est  complète  en  général.  C’est  surtout  l’expérience  qui  permet  d’éviter  les  pièges  qui  conduisent  à  enfreindre  la  sûreté  ou  empêcher  la  terminaison.      Par  exemple,  une  source  d’erreur  classique  est  celle  de  la  boucle  infinie.  Si  l’on  reprend  l’exemple  de    PageRank.  

 ….    Tant que  L(p)  est  non  vide  :    //  Parcourir  l’ensemble  des  pages  L(p)              ….        Pour  qu’un  tel  algorithme  se  termine,  l’ensemble  L(p)  doit  finir  par  se  vider.  Autrement  dit,   il   est   crucial   d’avoir   une   instruction   qui   vide   l’ensemble   et   cette   instruction   doit  s’exécuter  dans  la  boucle.      

De  manière  similaire,  dans  l’algorithme  d’Euclide,  il  est  important  pour  que  l’algorithme  se  termine  que  r  finisse  par  atteindre  le  nombre  0.    Répéter:      r  ←  reste  de  la  division  de  a  par  b        a  ←  b        b  ←  r  Tant que  r  >  0    Souvent,   une  manière   de   déceler   des   problèmes   de   sûreté   est   de   définir   ce   que   l’on  appelle  des   invariants  :  des  propriétés  qui  doivent  être  satisfaites  à  chaque   instant  de  l’exécution  d’un  algorithme,  en  particulier  à  chaque  itération  d’une  boucle.      De   manière   générale,   s’efforcer   de   concevoir   des   algorithmes   simples   et   de   les  décomposer   en   sous-­‐algorithmes   sont   de   bonnes   pratiques   pour   concevoir   des  algorithmes  corrects.  Nous  verrons  cela  dans  l’algorithme  suivant.      

6. Qu’est  ce  qu’un  algorithme  efficace  ?      S’assurer   qu’un   algorithme   assure   la   terminaison   et   la   sûreté   est   fondamentale.  Mais  cela  n’est  pas  suffisant  pour  en  faire  un  algorithme  utile.  Un  algorithme  qui  mettrait  un  siècle   à   se   terminer   ne   serait   pas   très   utile   si   nous   avons   besoin   d’un   résultat  rapidement.    Il  est  donc  tout  aussi  important  qu’un  algorithme  soit  efficace.  Mais  qu’est  ce   qu’un   algorithme   efficace  ?   C’est   un   algorithme   qui   utilise   peu   de   ressources.    Regardons  cela  de  plus  près.  

 -­‐ 6.1  De  l’efficacité  à  la  complexité  

 Dans   ce   chapître,   nous   allons   nous   concentrer   sur   la   ressource   «  temps  »  :   on   parle  d’efficacité   temporelle   d’un   algorithme.   D’une   part   c’est   une   ressource   souvent  privilégiée   dans   la   conception   des   algorithmes   car   considérée   la   plus   importante   en  pratique.  D’autre  part,  son  étude  est  suffisante  pour  avoir  une  bonne  idée  de  la  notion  de   complexité.   En   se   concentrant   sur   la   ressource   temps,   l’objectif   est   d’étudier   la  question  suivante  :  Combien  de  temps  mettra  un  algorithme  pour  résoudre  une  certaine  tâche  ?        A   priori,   on   peut   penser   qu’il   est   impossible   de   répondre   cette   question   de  manière  générale   car   tout   dépend   du   temps   d’exécution   des   instructions   élémentaires   de  l’agorithme.     Prenons   par   exemple   l’algorithme   d’Euclide.   Son   temps   d’exécution  dépend  du  temps  qu’il  faut  pour  exécuter  les  divisions  entières.  Si  c’est  un  ordinateur  B  qui  exécute  l’algorithme,  ce  temps  dépendra  de  B.    De  même,    on  peut  penser  qu’il  est  impossible  de  comparer  dans   l’absolu  deux  algorithmes  A  et  A’  qui  résolvent   le  même  problème  :  A  peut-­‐être  plus   rapide  que  A’  sur  un  ordinateur  B   et  moins   rapide  sur  un  ordinateur  B’.    

 Et   pourtant,   il   existe   un   moyen   de   s’affranchir   des   spécificités   de   l’ordinateur   sous-­‐jacent   et   de   comparer   l’efficacité   des   algorithmes  de  manière   abstraite.   Il   s’agit   de   la  théorie   de   la   complexité.   Dans   notre   contexte,   nous   considérerons   naturellement   la  complexité  temporelle.      La   complexité   temporelle   mesure   l’évolution   du   nombre   d’instructions   élémentaires  absolues  en  fonction  de  la  taille  des  entrées  de  l’algorithme.    

 Avant   d’expliquer   cela   plus   en   détails,   et   en   particulier   la   notion   d’instruction  élémentaire  absolue,  regardons  d’abord  deux  exemples  simples.  

 -­‐ 6.2  Illustration  de  la  complexité  à  travers  deux  algorithmes  de  recherche  

 Les   deux   algorithmes   ci-­‐dessous   résolvent   le   même   problème.   Ils   déterminent   si   un  élément  appartient  à  une   liste,  e.g.,  si  un  étudiant  est  bien  dans  une  classe.    Les  deux  algorithmes   prennent   comme   entrée   un   élément   x   et   une   liste   E,   et   retournent   une  valeur  booléenne  indiquant  si  oui  ou  non  l’élément  x  est  dans  la  liste  E.  Cette  liste  E  est  indexée   par   un   entier,   i.e.,   elle   possède   un   élément   que   l’on   considère   comme   le  premier,  puis  le  second  etc.  On  peut  donc  la  représenter  sous  la  forme  :  E(1),  E(2),  ..  E(i),  E(i+1)….   En   plus   des   instructions   élémentaires   vues   jusqu’à   maintenant,   les   deux  algorithmes   ci-­‐dessous   utilisent   deux   instructions   spécifiques   aux   manipulations   de  listes.   La   première   est   l’instruction   E(i)   qui   retourne   la   i-­‐ème   valeur   de   la   liste   et   la  seconde  est  l’instruction  taille(E)  qui  calcule  la  taille  de  la  liste.        Algorithme  1.F  :  Recherche-­‐1(x,E)      Entrée :  x,  E  Sortie :  x  dans  E  ?        i  ←  1  Tant que  i  <=  taille(E)  :          Si  x  =  E(i)  :    Sortir :  vrai        i  ←  i  +1  Sortir :  faux  

   

Algorithme  1.G  :  Recherche-­‐2(x,E)      Entrée :  x,  E  Sortie :  x  dans  E  ?        i  ←  1  

n  ←  taille(E)  Tant que  i  <=  n  :        Si  x  =  E(i)  :  Sortir :  vrai        i  ←  i  +1  Sortir :  faux  

   Les   deux   algorithmes   utilisent   la   même   stratégie.   Il   s’agit   à   travers   une   boucle   de  parcourir  les  éléments  de  la  liste  E  un  à  un,  en  partant  du  premier,  et  de  tester  à  chaque  fois  si  l’élément  rencontré  (le  i-­‐ème)  est  l’élément  recherché.  Si  c’est  le  cas,  l’algorithme  s’arrête   et   retourne   «  vrai  ».   Sinon   l’algorithme   fait   une   nouvelle   itération   en  incrémentant   la   valeur   de   i   pour   passer   à   l’élément   suivant.   Si   la   fin   de   la   liste   est  atteinte  sans  avoir  trouvé  l’élément  recherché,  l’algorithme  retourne  «  faux  ».      Il  y  a  néanmoins  une  différence  de  taille  entre  les  deux  algorithmes  (oui  c’est  un  jeu  de  mots).   Dans   le   premier   cas   (Algorithme   1.F),   on   calcule   la   taille   de   la   liste   à   chaque  itération   de   la   boucle.   Dans   le   second   cas   (Algorithm  1.G),   on   calcule   cette   taille   une  seule  fois.  La  valeur  de  la  taille  est  mise  dans  la  variable  n    avant  d’entrer  dans  la  boucle.    Ensuite  on  accède  directement  à  la  variable  n.    Le  calcul  de  la  taille  est  une  instruction  élémentaire  des  deux  algorithmes.  Mais  ce  n’est  pas   ce  que   l’on  peut  appeler  une   instruction  élémentaire  absolue.   Le   temps  qu’il   faut  pour  exécuter  cette  instruction  dépend  de  la  taille  n  de  la  liste.  En  effet,  l’instruction  de  calcul  de  la  taille  de  la  liste  est  lui  aussi  un  algorithme.  Imaginions  ici  que  cet  algorithme  consiste  à  faire  une  boucle  allant  de  1  jusqu’à  la  fin  de  la  liste,  en  passant  en  revue  les  éléments  E(i),  et  en  testant  à  chaque  fois  si  on  est  arrivé  au  bout  de  la  liste.  (On  suppose  ici   que   le  dernier   élément  de   la   liste   a  une  valeur   spéciale   indiquant   la   fin.)   Le   temps  d’exécution  global  du  calcul  de  la  taille  est  une  fonction  linéaire  qui  peut  s’écrire  a  *  n  :  a   étant  une   constante  qui   représente   le   temps  qu’il   faut  pour   aller   à   la   variable   E(i)   -­‐  aller  directement   à   la   variable  E(i)   est   considérée   comme  une   instruction  élémentaire  absolue   -­‐   et   qui   dépend   de   la   machine   sous-­‐jacente.   Comme   notre   objectif   est   de  comparer  des  algorithmes,  on  peut  supposer  que  ce  temps  est  unitaire  :  a  =  1.  Ainsi,  le  temps  qu’il  faut  pour  calculer  la  taille  de  la  liste  est  n.      Les  autres  instructions  élémentaires  des  deux  algorithmes  sont  absolues  car  aucune  ne  dépend  de  la  taille  de  la  liste.  On  peut  supposer  ici  qu’elles  mettent  un  temps  constant  pour  s’exécuter,  ou  tout  simplement  supposer  ici  que  chacune  met  une  unité  de  temps.  Encore  une   fois,   cette  supposition  ne  porte  pas  préjudice  au   fait  que  nous  souhaitons  comparer  deux  algorithmes.    Comparons   maintenant   le   temps   nécessaire   pour   chaque   algorithme   à   chaque   fois.  Clairement,  cela  dépend  de   l’élément  recherché  :   s’il  est  dans   la   liste  ou  pas  et  à  quel  endroit.  En  fait,  on  étudie  souvent  le  pire  cas.  Dans  notre  contexte,  cela  correspond  à  la  situation  ou  l’élément  ne  se  trouve  pas  dans  la  liste.  Dans  ce  cas,  l’algorithme  finira  par  

sortir  «  faux  ».  Mais  avant,   il  aura   fait   le  maximum  de  travail  possible,  à  savoir,   il  aura  fait  la  boucle  n  fois.      

Ainsi,  dans  le  pire  des  cas,  le  premier  algorithme  1.F  nécessitera  1  +  n  *  (n+  1  +  1+1)  +  1  =  n2  +  3n  +  2  unités  de  temps    Concernant  le  second  algorithme  1.G,  dans  le  pire  des  cas,  il  nécessitera  1  +  n  +    n  *  3  +  1  =  4n+2    unités  de  temps.    

 Supposons   que   l’unité   de   temps   dont   on   parle   correspond   à   1/100s.   Autrement   dit,  chaque   instruction   élémentaire   absolue   met   0,01s   à   s’exécuter.     Pour   n   =   1000,   le  premier  algorithme  nécessitera  près  de  3h  alors  que  le  second  nécessitera  30s.    Pour  n  =  10000,   le  premier  nécessitera  près  d’une  année  alors  que   le  second  nécessitera  moins  de  2mn.    Ce  sont  les  grandes  tailles  de  données  qui  marquent  les  différences  entre  les  algorithmes.      Nous   pouvons   donc   facilement   déduire   que   le   premier   algorithme   est  moins   efficace  que   le   second.   Nous   sommes   arrivés   à   cette   déduction   en   évaluant   le   nombre  d’instructions   élémentaires   absolues   exécutées   dans   le   pire   cas   par   chacun   des  algorithmes.      Nous  avons  fait  encore  plus,  en  représentant  ce  nombre  par  une  fonction  de   la   taille  de   l’entrée  des   algorithmes.  Cette   fonction   représente   ce  que   l’on  appelle  communément  la  complexité  temporelle  (au  pire  cas)  de  l’algorithme.      Nulle  part  nous  n’avons  parlé  des  spécificités  de   l’ordinateur  qui  pourrait  exécuter  ces  algorithmes.  Et  c’est  tant  mieux  car  ces  spécificités  changent  tout  le  temps.    

 -­‐ 6.3  Notation  de  Laudau  :  un  pas  de  plus  vers  l’abstraction  de  l’efficacité        

 Ce  que  nous  avons  aussi  vu  à  travers   l’exemple  des  deux  algorithmes  de  recherche  ci-­‐dessus   c’est   que   ce   qui   est   important   dans   le   calcul   de   complexité,   c’est   le   facteur  d’évolution  du  nombre  d’instructions  élémentaires  absolues  en  fonction  de   la  taille  de  l’entrée,   i.e.,   de   n.   Autrement   dit,   ce   qui   importe   c’est   le   fait   que   ce   soit   n2   pour   le  premier  algorithme  et  n  dans  le  second.  On  dit  que  le  premier  algorithme  est  en  O(n2)  et  le   second   en   O(n).   On   appelle   cette   notation,   la   notation   de   Landau,   du   nom   d’un  mathématicien  du  même  nom.  On  parle  aussi  de  notation  en  «  Grand  O  ».      La  définition  est  la  suivante.  Soient  f  et  g  deux  fonctions  :  f  ∈  O(g)  si  et  seulement  si:  

   Autrement  dit,  g(x)  croit  plus  vite  que  f(x)  à  un  facteur  multiplicatif  près  c  lorsque  x  tend  vers  l’infini.    

Si   l’on   prend   la   première   fonction   ci-­‐dessus,   représentant   la   complexité   du   premier  algorithme  1-­‐F,  n2  +  3n  +  2,  elle  est  en  O(n2)  alors  que  la  seconde  1-­‐G,  4n+2,    est  en  O(n).  En  pratique,  on  utilise  le  plus  petit  des  O(..)  possible  (que  l’on  note  en  toute  rigueur  ω).  Autrement,  nous  pourrions  aussi  dire  que  3n+2  est  en  O(n2)  mais  nous  ne  serions  pas  très  avancés  pour  comparer  les  deux  algorithmes.    Deux   propriétés   importantes   de   la   notation   en   question  permettent   de   faciliter   les  calculs  :       -­‐  Si  f  ∈  O(g)  et  f’  ∈  O(g’)  alors  f+f’  ∈  O(g+g’)  et  f*f’  ∈  O(g*g’)            

-­‐ 6.4  Complexité  d’un  algorithme  ou  complexité  d’un  problème    Une  fois  que  l’on  a  concu  un  algorithme,  que  l’on  est  convaincu  qu’il  est  correct  et  que  l’on   a  mesuré   sa   complexité,   on   se   trouve   naturellement   face   à   la   question  :   peut-­‐on  faire  mieux  ?  Si  l’on  a  concu  le  premier  algorithme  ci-­‐dessus,  on  peut  estimer  que  O(n2)    n’est   pas   satisfaisant   et   essayer   de   réduire   cette   complexité.   Cela   nous   conduirait  naturellement  au  second  algorithme  dont  la  complexité  est  O(n).  Mais  peut-­‐on  aller  plus  loin  ?      Peut-­‐on   imaginer   un   algorithme   de   recherche   d’un   élément   dans   une   liste   dont   la  complexité  est  moins  que  O(n)  ?  Par  exemple  un  algorithme  dont   la   complexité   serait  constante  ?  On  dirait  qu’elle  est  de  O(1).   La   réponse  est  non.   Il   semble  naturel  que   la  complexité   est   toujours   dépendante   de   la   taille   de   la   liste  n.     Cela   est   intrinsèque   au  problème  de  la  recherche.      Mais  peut-­‐on  quand  même  faire  moins  que  O(n)  ?  Cela  dépend  des  hypothèses  que  l’on  peut   faire   sur   la   liste   en   entrée.   Supposons   que   cette   liste   soit   ordonnée.   Plus  précisèment,   supposons   qu’il   existe   une   relation   d’ordre   total   sur     les   éléments   de   la  liste.  Supposons  que  ces  éléments  soient  rangés  par  rapport  à  cet  ordre  :  E(1)  étant   le  plus  petit,  puis  E(2),  E(3)  etc…  C’est  ce  que  nous  aurions  par  exemple  si   la   liste  est  un  dictionnaire  dont  les  éléments  sont  des  mots  classés  par  ordre  alphabétique.      Voici  un  algorithme  qui  permet  de  savoir  si  un  élément   fait  partie  de   la   liste  avec  une  complexité  moindre  que  O(n).    On  coupe  la   liste  au  «  milieu  »    et  on  teste  si   l’élément  que   l’on  cherche  est  au-­‐dessus  ou  en  dessous  de  ce  mileu.  Le   terme  «  milieu  »  est  un  abus  de  langage  car  la  liste  ne  contient  pas  forcèment  un  nombre  d’éléments  pair.  Mais  on  suppose  que  le  découpage  si  la  taille  est  impaire  donne  d’un  côté  n-­‐1/2  et  de  l’autre  n-­‐1/2+1.  Dans  le  premier  cas,  on  se  concentre  sur  la  moitié  supérieure  de  la  liste  ;  dans  le   second  cas,  on   se  concentre   sur   le   second.  Puis  on   refait   la  même  recherche  sur   la  moitié  de  la   liste  en  question.  C’est  en  gros  comme  cela  d’ailleurs  que  nous  cherchons  

un  mot   dans   le   dictionnaire   (sauf   que   l’on   ne   démarre   pas   forcèment   au  milieu).   On  parle  de  recherche  par  dichotomie.    

 Algorithme  1.H  :  Recherche-­‐Dichotomie  (x,E)    Entrée :  x,  E  ordonnée    Sortie :  x  dans  E  ?        Si  E  est  vide  :                Sortir  :  faux  Si E  contient  un  seul  élément  e  :                Si  e=  x  :    Sortir  :  vrai              Sinon : Sortir :  faux  Découper  E  en  deux  sous-­‐ensembles  disjoints  E1  et  E2  de  taille  (quasi)  égale  Si  x  >  max(E1)  :  Sortir  :  Recherche-­‐Dichotomie(x,E2)  Sinon : Sortir  :  Recherche-­‐Dichotomie(x,E1)  

 Le  fait  que  l’algorithme  s’appelle   lui-­‐même,  c’est  à  dire  qu’il  constitute  une  instruction  élémentaire  de  lui-­‐même,  s’appelle  la  récursivité.    C’est  une  notion  très  importante  sur  laquelle  nous  reviendrons  dans  le  prochain  chapitre.        

 Quelle  est  la  complexité  de  l’algorithme  1.H?  Nous  considérons  ici  aussi  le  pire  des  cas  ou  l’élément  n’est  pas  dans  la  liste.    Avant  de  se  lancer  dans  ce  calcul,  il  est  important  de  noter   qu’à   part   l’appel   à   l’algorithme   lui-­‐même,   toutes   les   autres   instructions  élémentaires  le  sont  de  manière  absolue.  La  question  que  l’on  doit  alors  se  poser  est  la  suivante  :   combien   de   fois   l’algorithme   s’appelle   t-­‐il   lui-­‐même  ?   Dans   le   pire   des   cas,  l’algorithme  s’appelera  autant  de  fois  qu’on  peut  diviser   la   liste  en  deux  parties   (quasi  égales).      Pour  une  liste  de  taille  n,  ce  nombre  s’appelle  le  logarithme  en  base  2  de  n  :  log2  (n).    On  appelle  logarithme  en  base  2,  ou  logarithme  entier  d’un  nombre  x  supérieur  ou  égal  à  1,  le   nombre   de   fois   qu’il   faut   diviser   ce   nombre   par   deux   pour   obtenir   un   nombre  inférieur  ou  égal  à  1.  Si  y  =  2x  alors  x  =  log2  (y).    

 Ainsi,   la   complexité   de   l’algorithme   1.H     est   en  O(log2   (n)).   Le   gain   en   complexité   par  rapport  aux  algorithmes  1-­‐F  et  1-­‐G  est  énorme.  Si  l’on  reprend  l’exemple  d’une  liste  de  taille   n   =   10000   et   qu’il   faut   0,01   s   pour   exécuter   chaque   instruction   élémentaire,   le  calcul   de   la   complexité   indique   que   l’algorithme   1-­‐F   mettra   près   d’une   année,  l’algorithme   1-­‐G   nécessitera   quelques   minutes   et   l’algorithme   de   recherche  dichomotique  1-­‐H  moins  d’1  s.        

Ainsi,   si   l’on   suppose   que   la   liste   est   ordonnée,   on   peut   obtenir   une   complexité  intéressante.   Nous   verrons   dans   le   chapître   suivant   comment   ordonner   une   liste   en  étudiant  le  problème  du  tri.    Mais   peut-­‐on   faire   encore   mieux  ?   Pas   vraiment.   Autrement   dit,   la   complexité   de   la  recherche  dans  une  liste  est  O(n)  si  la  liste  n’est  pas  ordonnée  et  O(log2  (n))  si  elle  l’est.    On  ne  peut  pas  trouver  d’algorithmes  pour  faire  mieux  que  cela.  Il  s’agit  de  complexités  intrinsèques  des  problèmes.  Démontrer  formellement  ce  genre  de  choses  n’est  pas  aisé.    Le  chapître  3  reviendra  sur  la  notion  de  complexité  d’un  problème.      

-­‐ 6.5  Classes  de  complexité  -­‐  

Voici  différentes  classes  de  complexité  qui  permettent  de  caractériser  les  algorithmes  (n  représentant  la  taille  d’entrée):    

Complexité  constante:  O(1)      .   Complexité  logarithmique:  O(log  n)  

Complexité  linéaire:  O(n)  Complexité  quasi-­‐linéaire:  O(n  log(n))  Complexité  polynomiale:  O(n2),  ...  O(nk  )  

.   Complexité  exponentielle:    O(2n  )    Les   algorithmes   linéaires   (et   a   fortiori   constants   et   logarithmiques)   sont   considérés  rapides.  Les  algorithmes  polynomiaux  sont  considérés  plus  lents,  mais  souvent  acceptés  en  pratique.  Les  algorithmes  exponentiels  sont  considérés  impraticables.        Mais  encore  !      Nous  nous  sommes  concentrés  sur   la  complexité  temporelle.   Il  est   important  de  noter  qu’il  y  a  d’autres   formes  de  complexités,  comme   la  complexité  spatiale,  qui  étudie   les  ressources  nécessaire  en  terme  de  mémoire,  ou  la  complexité  en  termes  d’accès  à  une  mémoire   partagée   pour   les   algorithmes   concurrents,   ou   de   messages   pour   les  algorithmes  réparties  sur  plusieurs  machines.      Nous   nous   sommes   aussi   concentrés   sur   la   complexité   dans   le   pire   des   cas.   On  s’intéresse   aussi   parfois   de   manière   optimiste   au   meilleur   des   cas   ou   de   manière  pragmatique  au  cas  moyen.      

   

7. Résumé    L’objectif  de  ce  chapitre  était  de  donner  une   idée   intuitive  de   la  notion  d’algorithme,  centrale   à   l’informatique,   mais   beaucoup   plus   ancienne   que   les   ordinateurs.  

Aujourd’hui,   la  tâche  de  beaucoup  de  scientifiques,  quel  que  soit   leur  domaine,  est  de  trouver   un   algorithme   pour   résoudre   leur   problème.   L’étude   des   algorithmes   est   une  branche  importante  des  sciences  appelée  l’algorithmique.    

 Nous  avons  présenté  quelques  algorithmes  modernes  que  beaucoup  utilisent  dans  leur  vie  de  tous  les  jours,  tels  que  PageRank,  au  cœur  de  Google,  et  EdgeRank,  au  cœur  de  Facebook,   ainsi   que   certains   algorithmes   utilisés   en   mathématiques   depuis   très   très  longtemps.      Le  premier  but  de  ces  exemples  était  d’illustrer  l’idée  qu’un  algorithme  est  un  ensemble  ordonné   d’instructions   élémentaires.   Ses   deux   ingrédients   de   base   sont   l’instruction  élémentaire    et  la  structure  de  contrôle  qui  permet  de  décrire  la  relation  d’ordre  entre  ces  mêmes   instructions.   Nous   avons   passé   en   revue   plusieurs   types   de   structures   de  contrôle.  Lorsqu’il  s’agit  de  faire  exécuter  des  algorithmes  par  des  ordinateurs,  on  passe  par  un   langage  de  programmation  qui  offre  différentes  variantes  de  ces   structures  de  contrôle.     Pour   exprimer   les   algorithmes   dans   ce   chapitre,   nous   avons   considéré   un  langage   assez   simple   et   assez   vague.   Nous   avons   privilégié   en   cela   l’intuition   à   la  précision.      Concevoir   un   algorithme   correct   n’est   pas   chose   aisée.   Il   est   important   avant   tout   de  réaliser   qu’un   algorithme   est   un   contrat   entre   un   utilisateur,   un   concepteur   et   un    exécutant.   Bien   clarifier   ces   termes   est   une   condition   nécessaire   à   la   démarche   de  conception.  Les  propriétés  que  le  concepteur  doit  pour  sa  part  assurer  sont  la  sûreté  et  la  terminaison.     Il  existe  des  mécanismes  de  vérification  automatique  d’algorithmes  et  des  techniques  de  preuve.  Mais  souvent,  l’expérience  est  fondamentale.  Pour  assurer  la  sûreté,  on  doit  par  exemple   typiquement   identifier   les   invariants  qui  doivent   toujours  être  vérifiées  à  l’intérieur  d’une  boucle.  En  ce  qui  concerne  la  terminaison,  assurer  que  la  boucle  n’est  pas  infinie  est  souvent  un  pas  important.    Enfin,  et  comme  nous  l’avons  souligné,  pour  qu’un  algorithme  soit  considéré  pratique,  il  ne  suffit  pas  qu’il  soit  correct.   Il   faut  en  plus  qu’il  soit  efficace.  Nous  avons  donné  une  idée  intuitive  de  la  notion  de  complexité,  en  particulier  dans  sa  forme  temporelle.  Cette  notion  permet  d’étudier  l’efficacité  relative  des  algorithmes  de  manière  abstraite,  sans  devoir  plonger  dans   les  détails  de  mises  en  œuvre  des  ordinateurs.  Nous  avons  étudié  cette   notion   à   travers   le   problème  de   la   recherche.  Nous   étudierons   dans   le   chapître  prochain  le  problème  du  tric  et  celui  du  plus  court  chemin.    

8. Pour  en  savoir  plus      Qu’est  ce  qu’un  algorithme  ?  https://www.youtube.com/watch?v=kk-­‐iLfqfFks    Qu’est  ce  la  complexité  ?  https://www.youtube.com/watch?v=exaHKrP6RsA    Comment  fonctionne  Facebook  (EdgeRank)?    

https://www.youtube.com/watch?v=1ParbwnSJpM    Comment  fonctionne  Google  (PageRank)?    https://www.youtube.com/watch?v=wR0wVxK3m_o      

9.  Exercises      

9.1  Algorithme  EdgeRank      Considèrez   l’algorithme  EdgeRank   tel  qu’il  a  été  décrit  dans  ce  chapitre.  Pourriez-­‐vous  expliquer   comment   le   score   d’un   post   peut-­‐il   augmenter   avec   le   temps  pour   un  utilisateur  u?    9.2  Algorithme  PageRank      Considèrez  l’algorithme  PageRank  tel  qu’il  a  été  décrit  dans  ce  chapitre  dans  sa  version  simplifiée,   sans   prendre   en   compte   le   damping   factor.   Considérez   par   ailleurs   un  système  de  quatre  pages  :  q  a  un  lien  vers  p  et  p’  alors  que    q’  a  seulement  un  lien  vers  p’.  Aucun  autre  lien  n’existe.  Supposons  par  ailleurs  que  le  score  de  q  est  de  1.  Quel  est  le  petit  score  que  devrait  avoir  q’  pour  que  le  score  de  p  soit  plus  grand  que  celui  de  p’  ?    9.3  Algorithme  Netflix      Inspirez-­‐vous   de   l’algorithme   EdgeRank   pour   concevoir   et   décrire   un   algorithme   qui  pourrait  proposer  à  chaque  utilisateur  u   les  films  qui  ont  été  les  plus  appréciés  par   les  utilisateurs  qui  ont  aimé  par  le  passé  les  mêmes  films  que  u.  Pour  simplifier,  concentrez-­‐vous   sur   le   score   de   chaque   film   f   pour   chaque   utilisateur   et   utilisez   la   fonction  suivante  :       -­‐  aime(f,u,v)  qui  retourne  vrai  si  u  et  v  ont  aimé  le  même  film  f.    

 9.4.  Algorithme  Twitter      Quelles   sont   les   deux   différences   principales   entre   la   diffusion   de   posts   sur   Twitter  (tweets)  et  la  diffusion  de  posts  sur  Facebook  ?    

 9.5.  Algèbre  élémentaire      9.5.1  Que  fait  l’algorithme  suivant  ?  

 Algorithme  1.M  :  Inconnu(b,d)    Entrée :  Deux  entiers  naturels  non  nuls  a  et  b  tels  que  a  >  b  

Sortie :  x              d  ←  a-­‐b        Si  d  =  0  :  Sortir  :  b          Sinon  :  Inconnu(b,d)    

 9.5.2  Est-­‐il  plus  efficace  que  l’Algorithme  1.C  ?  

   9.6.  Des  boucles      9.6.1  L’algorithme  suivant  peut-­‐il  se  terminer  ?      Algorithme  1.M  (a,b,r)        Entrée :  a,  b,  r  des  entiers  naturels  supérieurs  à  0  Sortie : x    Répéter :      b  ←  reste  de  la  division  de  a  par  b        a  ←  b  Tant que  r  >  0  :  Sortir :  b      9.6.2  Que  faudrait-­‐il  au  minimum  corriger    pour  qu’il  se  termine  ?  

 9.7.      Manipulation  de  listes    

 9.7.1  Que  fait  l’algorithme  suivant  ?  

 Algorithme  1.N  (x,E)    Entrée :  Un  entier  x  et  une  liste  E  ordonnée  d’entiers  dont  le  premier  élément  est  E(1),  puis  E(2)  …  E(taille(E))  Sortie :    ?        min  ←  1  max  ←  taille(E)  Répéter :      c  ←  min+max/2  //  division  entière          Si  x  =  E(c)  :                Sortir :  c  

     Sinon :              Si  E(c)    <  x  :                            max  =  c-­‐1                  Sinon  :  min  =  c+1      Tant que  min  <=  max    Sortir :  -­‐1  

   

9.7.2  Quelle  est  sa  complexité  ?    

9.8.  Complexités    Considérez   un   ordinateur   qui   met   1s   pour   exécuter   chacune   de   ses   instructions  élémentaires.    Donner  l’ordre  de  grandeur  du  temps  qu’il  faudra  pour  exécuter  chacun  des  algorithmes  suivant  sur  une  donnée  n  de  taille  1.000.000    

-­‐ Un  algorithme  A  de  complexité  O(1)    -­‐ Un  algorithme  B  de  complexité  O(n)    -­‐ Un  algorithme  C  de  complexité  O(n2)  -­‐ Un  algorithme  D  de  complexité  O(log2  (n))