51781 Algorithmique Pour l Apprenti Programmeur

7/31/2019 51781 Algorithmique Pour l Apprenti Programmeur

1/70

Algorithmique pourl'apprenti

programmeurPar bluestorm ,

Cygalet lastsseldon

www.siteduzero.com

Licence Creative Commons BY-SA 2.0
http://www.siteduzero.com/


2/70

Dernire mise jour le 10/08/2011


3/70

Sommaire

1Sommaire ...........................................................................................................................................1Partager ..............................................................................................................................................3Algorithmique pour l'apprenti programmeur .......................................................................................

3But du tutoriel ....................................................................................................................................................................3Prrequis ...........................................................................................................................................................................3Historique ..........................................................................................................................................................................

4Partie 1 : Prsentation de la notion de complexit algorithmique .......................................................5Qu'est-ce qu'un algorithme ? ............................................................................................................................................5Omniprsence des algorithmes ..................................................................................................................................................................................5Rle privilgi des ordinateurs ....................................................................................................................................................................................5Notion de structure de donnes ..................................................................................................................................................................................

6Les grenouilles partent en vacances ................................................................................................................................7Situation ......................................................................................................................................................................................................................7Les deux possibilits ...................................................................................................................................................................................................7Tous les ans : choix personnalis ...............................................................................................................................................................................8Cette anne : choix de groupe ....................................................................................................................................................................................8Comparaison ...............................................................................................................................................................................................................

10La notion de complexit ..................................................................................................................................................10Correction de l'algorithme .........................................................................................................................................................................................10Complexit ................................................................................................................................................................................................................11Mesure 'asymptotique' ...............................................................................................................................................................................................11Notation "grand O" .....................................................................................................................................................................................................12Complexit en temps, complexit mmoire ..............................................................................................................................................................12Complexit dans le pire des cas ...............................................................................................................................................................................

14Un peu de pratique ..........................................................................................................................................................14Qu'est-ce qu'on attend de vous ? ..............................................................................................................................................................................14Chercher le plus grand / petit lment ......................................................................................................................................................................15Trouver les lments uniques ...................................................................................................................................................................................15Solution propose .....................................................................................................................................................................................................16Complexit ................................................................................................................................................................................................................17Trouver les lments uniques : autre solution ...........................................................................................................................................................

19Partie 2 : Premiers exemples de structures de donnes et d'algorithmes courants ..........................19Notions de structures de donnes : tableaux et listes chanes .....................................................................................

19Dfinition ................................................................................................................................................................................................................... 19Tableaux ....................................................................................................................................................................................................................20Listes .........................................................................................................................................................................................................................21Ajout / retrait, taille, accs un lment ...................................................................................................................................................................21Ajout / Retrait .............................................................................................................................................................................................................23Taille ..........................................................................................................................................................................................................................23Accs un lment ...................................................................................................................................................................................................24Concatnation, filtrage ..............................................................................................................................................................................................24Concatnation ...........................................................................................................................................................................................................26Filtrage ......................................................................................................................................................................................................................27Synthse ...................................................................................................................................................................................................................27Oprations .................................................................................................................................................................................................................27Conversions ..............................................................................................................................................................................................................28Attention aux langages de moches ..........................................................................................................................................................................

29Une classe d'algorithme non nafs : diviser pour rgner .................................................................................................29Gagner au jeu du 'Plus ou Moins' ..............................................................................................................................................................................29Dichotomie : Recherche dans un dictionnaire ...........................................................................................................................................................30Calcul de la complexit .............................................................................................................................................................................................31Trouver un zro d'une fonction ..................................................................................................................................................................................34Diviser pour rgner : exponentiation rapide ..............................................................................................................................................................

36Introduction au problme du tri .......................................................................................................................................36Formuler le problme du tri .......................................................................................................................................................................................36Question de la structure de donne ..........................................................................................................................................................................36Tri par slection .........................................................................................................................................................................................................37Complexit ................................................................................................................................................................................................................38Implmentation du tri par slection ...........................................................................................................................................................................38Pour une liste ............................................................................................................................................................................................................39Pour un tableau .........................................................................................................................................................................................................41Comparaison .............................................................................................................................................................................................................41Tri par insertion .........................................................................................................................................................................................................41Le retour du "diviser pour rgner" : Tri fusion ............................................................................................................................................................42Algorithme .................................................................................................................................................................................................................43Implmentation avec des listes .................................................................................................................................................................................

47Implmentation avec des tableaux ............................................................................................................................................................................48Complexit ................................................................................................................................................................................................................49Efficacit en pratique .................................................................................................................................................................................................

51Partie 3 : Quelques autres structures de donnes courantes ...........................................................52Piles et files .....................................................................................................................................................................52Concept .....................................................................................................................................................................................................................

Sommaire 1/68

www.siteduzero.com
http://www.siteduzero.com/http://-/?-


4/70

53Mise en pratique ........................................................................................................................................................................................................53Piles ..........................................................................................................................................................................................................................54Files ...........................................................................................................................................................................................................................

57Arbres ..............................................................................................................................................................................58Dfinition ...................................................................................................................................................................................................................61Quelques algorithmes sur les arbres ........................................................................................................................................................................61Taille ..........................................................................................................................................................................................................................63Hauteur ......................................................................................................................................................................................................................63Liste des lments ....................................................................................................................................................................................................

64Parcours en profondeur ............................................................................................................................................................................................. 65Parcours en largeur ...................................................................................................................................................................................................65En mettant des couches ............................................................................................................................................................................................66Avec une file ..............................................................................................................................................................................................................67Comparaison des mthodes de parcours .................................................................................................................................................................67Une symtrie assez surprenante ...............................................................................................................................................................................67Choix de l'implmentation .........................................................................................................................................................................................67Analyse de complexit ..............................................................................................................................................................................................68Utilisation en pratique ................................................................................................................................................................................................

Sommaire 2/68

www.siteduzero.com


5/70

Algorithmique pour l'apprenti programmeur

Par blues torm et lastsseldon et Cygal

Mise jour : 12/06/2010Difficult : Facile

2 847 visites depuis 7 jours, class 51/778

Vous venez d'apprendre les bases d 'un langage de programmation ? Vous vous tes peut-tre rendu compte que parfois, enmodifiant un peu votre programme, vous pouvez obtenir le mme rsultat mais 2, 10 ou 1000 fois plus vite ?

De telles amliorations ne s ont pas le fruit du hasard, ni mme dues une augmentation de la mmoire vive ou un changementde processeur : il y a plusieurs manires de programmer quelque chose et certaines sont incroyablement meilleures que d'autres.

Avec un peu de rflexion, et des outils thoriques de bas e, vous serez vous auss i en mesure de faire de bons choix pour vosprogrammes. la fin de ce tutoriel, vous serez de meilleurs dveloppeurs , en mesure de comprendre, corriger et concevoir desprogrammes plus efficaces.

But du tutoriel

Les deux notions cls de ce tutoriel sont les s uivantes : la complexit, et les s tructures de donnes. La complexit es t une manired'estimer les performances d'un algorithme. Les structures de donnes sont la manire dont vous organisez les informations dansvotre programme. En choisissant une structure de donnes adapte, vous serez capables de coder des oprations trs

performantes (de faible complexit).

Chaque algorithme rsout un problme donn. Pour chaque problme, il existe un ou plusieurs algorithmes intressants (mais onen dcouvre de nouveaux tous les ans !). Nous vous prsenterons, dans ce tutoriel, un petit panorama de problmes "courants",dans le but de vous familiariser avec la complexit et les st ructures de donnes . Vous apprendrez par exemple chercher unlment qui vous intresse l'intrieur d'un ensemble d'lments, trier un ensemble, ou mme trouver le plus court chemind'un "endroit" un autre.

Prrequis

Le but de ce tutoriel n'est pas de vous apprendre programmer. Pourle lire, vous devez dj savoir programmer. L'apprentissagede l'algorithmique n'utilise pas de concepts bas niveau (assembleur, etc.) ou de bibliothques logicielles spcialises (SDL, Qt...),mais vous devez tre l'aise avec les variables, conditions , boucles et fonctions. La connaissance du concept de 'rcursivit' (sivous vous sentez en manque, il y a dj un tuto ce s ujet sur le SDZ) est aussi un avantage.

Le langage que vous utilisez n'est pas trs important, car on tentera de formuler les algorithmes d 'une manire qui en estindpendante. Nous donnerons auss i, pour les curieux, des exemples dans quelques langages de programmation. Si vous n 'yvoyez pas le vtre, trouvez-en un suffisamment proche, et faites un petit effort.

La complexit algorithmique es t une mesure formelle de la complexit d'un algorithme. Elle s 'exprime donc en langagemathmatique. Le calcul de certains algorithmes avancs est trs compliqu et demande des connaissances mathmatiques

pouss es. Cependant, notre tutoriel se concentre sur des choses s imples, et devrait tre largement accessible : une connaiss ancedes puissances et des racines (carres) devrait suffire tre l'aise. Un objet plus avanc, la fonction logarithme, sera prsentet expliqu avant son utilisation.

Historique

Ce tutoriel est en cours d 'criture. Vous l'avez dj lu, et vous voulez savoir si quelque chos e a t rajout ?Voici un historique des modifications , les plus rcentes en premier :

Algorithmique pour l'apprenti programmeur 3/68

www.siteduzero.com
http://www.siteduzero.com/membres-294-227.htmlhttp://www.siteduzero.com/membres-294-432.htmlhttp://www.siteduzero.com/membres-294-17460.htmlhttp://www.siteduzero.com/http://www.siteduzero.com/tutoriel-3-36703-la-recursivite.htmlhttp://www.siteduzero.com/tutoriels-les-plus-visiteshttp://www.siteduzero.com/tutoriel-21-51781-algorithmique-pour-l-apprenti-programmeur.htmlhttp://www.siteduzero.com/membres-294-17460.htmlhttp://www.siteduzero.com/membres-294-432.htmlhttp://www.siteduzero.com/membres-294-227.html


6/70

08 aot 2011 : correction d'une bvue repre parArnolddu51, et clarification par Cygal de la recherche de racine pardichotomie, suite une question de bouboudu2115 juin 2010 : rvision de l'implmentation C du tri par fusion sur les listes13 juin 2010 : diverses reformulations suite aux commentaires des lecteurs (candide, Equinoxe, programLyrique)12 juin 2010 : implmentation en C du tri par slection sur les tableaux

juillet 2009 : correction de quelques typos , clarification de certains passages26 avril 2009 : ajout d'exemples de code pour le chapitre sur les arbres

25 avril 2009 : ajout d'icnes pour les chapitres existants22 avril 2009 (partie 3) ajout du deuxime chapitre : arbres; les exemples de code sont venir20 avril 2009 (partie 3) ajout d'un premier chapitre, assez simple, sur les piles et les files27 fvrier 2009 (partie 1) reformulation et clarification de certains paragraphes22 fvrier 2009 : ajout de l'historique, prsentation d'un site d 'exercices en fin de deuxime partie18 fvrier 2009 (partie 2) ajout d 'exemples de code C pour les listes chanes11 fvrier 2009 (partie 2) chapitre "Introduction au problme du tri"

janvier 2009 : zcorrection parptipilou (rdaction arrte cause d'un bug du SdZ)mi octobre 2008 (partie 2) chapitre "Notions de s tructures de donnes : tableaux et listes chanes"dbut septembre 2008 (partie 2) chapitre "Une classe d'algorithme non nafs : diviser pour rgner", par lasts et Cygalmi aot 2008 (partie 1) publication de la premire partie

Partie 1 : Prsentation de la notion de complexit algorithmique 4/68

www.siteduzero.com
http://www.siteduzero.com/http://www.siteduzero.com/membres-294-7500.htmlhttp://www.siteduzero.com/forum-83-676069-p1-multiplication-inexplicable.htmlhttp://www.siteduzero.com/tutoriel-50-58341-p1-une-classe-d-algorithme-non-naifs-diviser-pour-regner.html#r60642


7/70

Partie 1 : Prsentation de la notion de complexit algorithmique

Qu'est-ce qu'un algorithme ?Un algorithme est la description prcise, sous forme de concepts simples, de la manire dont on peut rsoudre un problme.

Dans la vie de tous les jours, nous avons souvent besoin de rsoudre des problmes. Surtout si on cons idre la notion de"problme" au sens large.

Omniprsence des algorithmesUn exemple de problme qui nous concerne tous (oui, mme vous) est celui de la cuisine : vous tes dans une cuisine, voustrouvez du riz, comment le cuire ? Voici une marche s uivre s imple :

remplir une casserole d'eau ;y ajouter une pince de s el ;la mettre s ur le feu ;attendre l'bullition de l'eau ;mettre le riz dans la casserole ;le laiss er cuire 10 15 minutes ;goutter le riz.

J'ai dcrit une solution au problme "il faut faire cuire du riz", sous forme de concepts simples. Vous remarquerez qu'il y apourtant beaucoup de choses implicites : j'ai prcis que vous tiez au dpart en possess ion du riz, mais il faut auss i unecasserole, de l'eau, etc. On peut se trouver dans des situations spcifiques o tous ces objets ne sont pas disponibles, et ilfaudra alors utiliser un autre algorithme (ou commencer par construire une casserole...).

Les instructions que j'ai utilises s ont "prcises", mais on pourrait prciser moins de choses , ou plus . Comment fait-on pourremplir une casserole d'eau, plus prcisment ? Si le cuisinier qui la recette est destine ne sait pas interprter la ligne "remplirune casserole d'eau" , il faudra l'expliquer en termes plus simples (en expliquant comment utiliser le robinet, par exemple).

De mme, quand vous programmez, le degr de prcision que vous utilisez dpend de nombreux paramtres : le langage quevous utilisez, les bibliothques que vous avez dispos ition, etc.

Rle privilgi des ordinateursSi on t rouve des algorithmes dans la vie de tous les jours, pourquoi en parle-t-on principalement en informatique ? La raison es ttrs s imple : les ordinateurs sont trs pratiques pour effectuer des tches rptitives. Ils sont rapides, efficaces, et ne se lassent

pas .

On peut dcrire un algorithme permettant de calculer les dcimales de la racine carre de deux, qui soit utilisable par un humain.Vous pourrez ains i calculer, l'aide d'une feuille et d'un crayon, les 10 premires dcimales (1,4142135624). Mais s'il vous en fautun million ? Un ordinateur deviendra alors beaucoup plus adapt.

De manire gnrale, on peut concevoir de nombreux algorithmes comme des mthodes de traitement d'information : recherche,

comparaison, analyse, classement, extraction, les ordinateurs sont s ouvent trs utiles pour tripoter la mass e d'informations quinous entoure continuellement.

Vous aurez peut-tre pens au clbre moteur de recherche Google (qui a initialement domin le march grce aux capacits deson algorithme de recherche), mais ce genre d'activits n'est pas restreint au (vaste) secteur d'Internet : quand vous jouez un

jeu de st ratgie en temps rel, et que vous ordonnez une unit de se dplacer, l'ordinateur a en sa pos sess ion plusieursinformations (la structure de la carte, le point de dpart, le point d'arrive) et il doit produire une nouvelle information : l'itinraireque doit suivre l'unit.

Notion de structure de donnesEn plus de manipuler l'information, il faut aussi la stocker. La manire dont on organise cette information stocke peut avoir desconsquences trs importantes sur leur manipulation.

Concrtement, prenez par exemple un dictionnaire : on peut dfinir un dictionnaire comme "un ensemble de mots et leurdfinition" . Cependant, pourrait-on u tiliser correctement un dictionnaire dont les mots sont placs dans le dsordre ?Certainement pas, parce qu'il serait trs difficile de trouver la dfinition d'un mot que l'on cherche (c'est encore possible, il suffitde lire le dictionnaire page par page jusqu' ce qu'on trouve le mot). L'ordre alphabtique est clairement une solution t rs efficace

pour pouvoir retrouver rapidement le mot que l'on cherche.

Il y a des liens forts entre les algorithmes (qui dcrivent des mthodes) et les s tructures de donnes (qui dcrivent une


www.siteduzero.com


8/70

organisation). Typiquement, certaines s tructures de donnes sont indispensables la mise en place de certaines mthodes , et l'inverse certains algorithmes sont ncessaires aux structures de donnes : par exemple, si on veut rajouter un mot dans undictionnaire class alphabtiquement, on ne peut pas juste l'crire dans l'espace libre sur la dernire page, il faut utiliser unalgorithme pour l'ajouter au bon endroit. L'tude des structures de donnes est donc insparable de celle des algorithmes, etvous n'y chapperez pas.


www.siteduzero.com


9/70

Les grenouilles partent en vacancesPour vous faire comprendre la notion de complexit, nous avons choisi un exemple simple, de la vie de tous les jours. Aquatique.

SituationHaskell est un gentil fermier, qui lve des grenouilles. Il a des relations trs chaleureuses avec celles-ci, qui peuvent se

promener leur guise dans leur champ pendant toute l'anne, et ont droit une petite cahute avec chauffage pendant l'hiver.

Mais ce qui fait vritablement la joie des grenouilles de Haskell, ce sont les vacances : tous les ans, juste avant de s'occuper desmoissons, il les amne dans les marcages prs de sa ferme pour qu'elles puissent y passer des vacances aquatiques.

Le dtail compliqu es t le dpart en vacances . Haskell charge toutes ses grenouilles dans une grande caisse, qu'il met sur soncamion, et part vers les nombreux marcages pour les y dpos er. Le problme vient du fait que les grenouilles, surtout pendantles vacances , n'apprcient pas la foule : elles veulent aller dans un des marcages les moins peupls.

Plus prcisment, la caisse est un carr en forme de quadrillage de N cases de large par N cases de long (N est un nombreinconnu de nous, mais fix). Chaque case de la caiss e contient une grenouille. Il y aussi N marcages vides, dans lesquels lesgrenouilles pourront se rpartir.

Les deux possibilits

Tous les ans : choix personnalis

Jusqu' prsent, Haskell le fermier, qui ne voulait pas se prendre la tte, utilisait la mthode suivante : aprs avoir charg le carrde grenouilles sur son camion, il choisissait l'une d'entre elles, et lui demandait de lui dsigner le marcage dans lequel elle


www.siteduzero.com


10/70

voulait passer ses vacances, puis l'y amenait.

Aprs l'avoir dpose, il demandait une seconde grenouille de choisir son marcage. Celle-ci, prfrant les marcages les moinspeupls, choisiss ait systmatiquement un autre marcage encore vide. Il l'y amenait, puis demandait la grenouille suivante, etainsi de suite.

Les marcages s e rempliss aient petit petit. Ds qu'un marcage tait un peu moins peupl que les autres , les grenouilles

suivantes s'y rendaient et s a population augmentait. Globalement, la fin de la distribution des grenouilles, tous les marcagestaient galement peupls : ils contenaient N grenouilles chacun.

Cette anne : choix de groupe

Cette anne, Haskell le fermier en a un peu marre des interminables voyages en camion pour satisfaire chaque grenouille. Il adcid d'appliquer une autre mthode : il va au premier marcage, et y dpose la premire range de N grenouilles. Celles-ci

protestent vigoureusement puisqu'elles s ont entasses N dans un seul marcage, alors que tous les autres sont vides . Mais illes quitte pour aller dposer la deuxime range de N grenouilles dans le deuxime marcage, et ainsi de suite jusqu' avoir vidchacune des N ranges, et donc rempli les N marcages. la fin, les grenouilles (qui s'taient communiqu leur indignation parSMS) se calment, puisqu 'elles sont toutes dans un marcage peupl de N grenouilles, et qu'il n'y a donc plus aucun marcagemoins peupl disponible.

ComparaisonDans les deux cas, les conditions de dpart sont respectes : les grenouilles sont rparties de faon ce qu'aucun marcage nesoit plus peupl que les autres , et sont donc satisfaites. Les deux mthodes de Haskell le fermier rsolvent bien le problmecorrectement.

La diffrence vient du fait que dans la premire mthode, chaque grenouille ou presque lui demandait de changer de marcage. Ilfaisait donc environ autant de voyages en camion qu'il y a de grenouilles. Dans le deuxime cas, il dpos ait les grenouilles par

blocs d'une range, et donc faisait moins de voyages : seulement le nombre de ranges de grenouilles.

La diffrence n 'a pas l'air importante, mais cela dpend beaucoup du nombres de ranges . Pour N ranges, comme la caisse est

carre, il y a N grenouilles par range, soit au total N*N, ou N2 grenouilles. La mthode habituelle demande environ N2 voyages Haskell le fermier, alors que la deuxime mthode n'en demande que N.

La deuxime mthode es t plus rapide, et s urtout le temps gagn en l'appliquant augmente plus il y a de grenouilles. S'il y a 6ranges de grenouilles et que le dplacement en camion d'un marcage l'autre dure 5 minutes environ, il faut 6 * 5 = 30 minutes,soit une demi-heure avec la nouvelle mthode, alors qu'il fallait auparavant 6 * 6 * 5 = 180 minutes, soit 3 heures pour rpartir lemme nombre de grenouilles. Et l'cart se creuse quand il y a plus de ranges : s'il y en a 20, avec le mme calcul, il faut un peumoins de 2 heures avec la deuxime mthode, mais 33 heures avec l'ancienne !

Clairement, la nouvelle mthode de Haskell le fermier est bien meilleure. En termes informatiques, on dira que l'algorithme qu'il achoisi est plus performant. On peut mme quantifier cette performance en termes de "complexit", c'est ce que l'on verra dans le

prochain chapitre.


www.siteduzero.com


11/70


www.siteduzero.com


12/70

La notion de complexitQuand un programmeur a besoin de rsoudre un problme informatique, il crit (gnralement) un programme pour cela. Son

programme contient une implmentation , c'est--dire si on veut une "transcription dans un langage informatique" d'unalgorithme : l'algorithme, c'est juste une description des tapes effectuer pour rsoudre le problme, a ne dpend pas dulangage ou de l'environnement du programmeur ; de mme, si on traduit une recette de cuisine dans une autre langue, a reste la"mme" recette.

Correction de l'algorithmeQue fait, ou que doit faire un programmeur qui implmente un algorithme ? Comme Haskell le fermier, il doit commencer parvrifier que son algorithme est correct, c'est--dire qu'il produit bien le rsultat attendu, qu'il rsout bien le problme demand.C'est trs important (si l'algorithme ne fait pas ce qu'on veut, on n'a pas besoin de chercher l'optimiser), et c'est parfois l'tape la

plus complique.

Dans la pratique, la plupart des informaticiens "font confiance" leurs algorithmes : avec un peu d'habitude et pour desproblmes abordables, un programmeur expriment peut s e convaincre qu'un algorithme fonctionne correctement, ou aucontraire trouver un problme s 'il y en a ("et que s e pas se-t-il si tu as un nombre impair de grenouilles ?"). L'approche plus'srieuse' consiste crire une preuve que l'algorithme est correct. Il y a diffrents niveaux de preuves, mais ils s ont tous un peutrop formels pour ce tutoriel, et nous n'aborderons sans doute pas (ou alors trs brivement) cet aspect.

Bien sr, un algorithme correct ne veut pas dire un programme sans bug : une fois qu'on a un algorithme correct, on l'implmente(en crivant un programme qui l'effectue), et on est alors expos toutes les petites erreurs, en partie spcifiques au langage deprogrammation utilis, qui peuvent s 'incrus ter pendant l'criture du programme. Par exemple, l'algorithme ne dcrit pas en gnralcomment grer la mmoire du programme, et la vrification des erreurs de s egmentations et aut res rjouissances de la sorte estlaisse aux soins du programmeur.

ComplexitUne fois que le programmeur est convaincu que son algorithme est correct, il va ess ayer d'en valuer l'efficacit. Il veut s avoir

par exemple, "est-ce que cet algorithme va vite ?".On pourrait penser que la meilleure faon de savoir ce genre de choses est d'implmenter l'algorithme et de le tester sur sonordinateur. Curieusement, ce n'es t gnralement pas le cas. Par exemple, si deux programmeurs implmentent deux algorithmesdiffrents et mesurent leur rapidit chacun sur son ordinateur, celui qui a l'ordinateur le plus puissant risque de penser qu'il al'algorithme le plus rapide, mme si ce n'est pas vrai. De plus, cela demande d'implmenter l'algorithme avant d'avoir une ide desa rapidit, ce qui est gnant (puisque la phase d'implmentation, d'criture concrte du code, n'es t pas facile), et mme pas

toujours pos sible : si le problme que l'on veut rsoudre est li une centrale nuclaire, et demande d 'utiliser les capteurs de lacentrale pour grer des informations, on peut difficilement se permettre d'implmenter pour tes ter en conditions relles tous lesalgorithmes qui nous passent par la tte.

Les scientifiques de l'informatique ont cr pour cela un outil extrmement pratique et puissant, que nous tudierons dans lasuite de ce tutoriel : la complexit algorithmique. Le terme de 'complexit' est un peu trompeur parce qu'on ne parle pas d'unedifficult de comprhension, mais d'efficacit : "complexe" ne veut pas dire "compliqu". Un algorithme de forte complexit a uncomportement asymptotique (le mot est expliqu dans la prochaine section) moins efficace qu'un algorithme de faible complexit,il est donc gnralement plus lent. Mais on peut avoir des algorithmes trs faible complexit qui sont extrmement compliqus.

L'ide en deux mots de la complexit algorithmique, c'est :Citation

si je donne mon programme une entre de taille N, quel est l'ordre de grandeur, en fonction de N, du nombre d'oprationsqu'il va effectuer ?

Elle repose sur le fait que les programmes qui rsolvent un problme dpendent des conditions du problme : si les conditionschangent, ils peuvent s'effectuer en plus ou moins de temps. La complexit permet de quantifier (mettre une formulemathmatique) la relation entre les conditions de dpart et le temps effectu par l'algorithme.

Pour "compter les oprations" , il faut dcider de ce qu'est une opration. cette ques tion, les sages s cientifiques n'ont pas purpondre dfinitivement, parce que le choix dpend du problme (et mme de l'algorithme) considr. Il faut en fait choisir soi-mme quelques petites oprations que l'algorithme effectue souvent, et que l'on veut utiliser comme oprations de bas e pourmesurer la complexit. Par exemple, pour faire une omelette, on peut cons idrer que les trois oprations de bas e sont de cas ser un

oeuf, de battre un oeuf en omelette, et de faire cuire un oeuf battu en omelette. On peut donc pour chaque recette compter lenombre d'oeufs casss, cuits et battus, et avoir ainsi une ide de la complexit de la recette (l'omelette tant un plat bien connu etcodifi, on peut s'attendre ce que toutes les recettes aient la mme complexit : pour N oeufs , on effectue 3N oprations) :l'ajout de s el, poivre ou herbes es t trs rapide, et n'a pas besoin d'tre pris en compte dans l'analyse de la complexit (doncindirectement des performances de ma recette).


www.siteduzero.com


13/70

Par exemple, dans le cas de Haskell le fermier, on peut dire que pour N ranges de grenouilles, il a besoin avec sa vieille mthode

d'environ N2 dplacements de camion, et seulement de N dplacements avec la nouvelle. C'est une bonne mesure de lacomplexit, car le dplacement du camion est vraiment l'opration importante prendre en compte : c'est la plus longue desoprations simples (sortir une grenouille, choisir un lieu, etc.) qu'il effectue : on peut donc s 'attendre ce que le temps total so itquasiment exactement le temps pass en dplacement de camion, que l'on peut donc relier directement aux performances globalesde s on algorithme.

Ne vous inquitez pas si cette not ion est toujours un peu floue pour l'instant, vous l'assimilerez sans doute mieux avec les deuxexemples concrets dans le chapitre su ivant.

Mesure 'asymptotique'J'ai dit que la complexit tait une mesure du comportement asymptotique de l'algorithme. Que veut dire ce mot compliqu ?

Il veut dire "quand l'entre devient trs grande" (voire mme "tend vers l'infini"). "entre"dsigne ici la quantification desconditions de dpart de l'algorithme. Dans le cas de Haskell le fermier, cela voudra dire "quand il y a beaucoup de ranges degrenouilles", par exemple 200. En informatique, "beaucoup" a un sens lgrement diffrent : un moteur de recherche dira "quandil y a beaucoup de pages web", comme par exemple, 100 milliards ...

Il y a deux consquences (qui sont en fait lies aux fondements mathmatiques de la notion de complexit, qui ne seront pasabords ici). D'une part, les temps constants ne sont pas pris en compte. On appelle "temps cons tants " les dlais qui ne

dpendent pas de l'entre. Par exemple, si avant d'emmener ses grenouilles en vacances, Haskell le fermier remet de l'huile detournesol dans son camion, le temps de rempliss age de s on rservoir est cons idr "constant" : qu'il aie 10 ou 100 ranges degrenouilles, cela met autant de temps. Comme on considre l'efficacit de l'algorithme quand il y a "beaucoup" de grenouilles, letemps de rempliss age du rservoir sera ngligeable devant le temps de dplacement des grenouilles.

D'autre part, les "facteurs multiplicatifs constants " ne sont pas non plus pris en compte : la mesure de la complexit ne fait pas ladiffrence entre un algorithme qui effectue (en fonction de N) N, 2N ou 157N oprations.

Pourquoi cette dcision ? Considrez les deux algorithmes s uivants , dpendant de N :

Code : Autre

faire N fois l'opration A

faire N fois (l'opration B puis l'opration C)

Dans le premier cas, on fait N fois l'opration A, et dans le deuxime cas on fait au total N fois l'opration B, et N fois l'oprationC. En admettant que ces deux algorithmes rsolvent le mme problme (donc s ont corrects), et que toutes les oprations sont

prises en compte pour la mesure de la complexit, le premier algorithme fait N oprations et le deuxime 2N.

Mais est -ce que l'on peut dire lequel est le plus rapide ? Pas du tout, car cela dpend des temps mis par les trois oprations :peut-tre que B et C sont tous les deux quatre fois plus rapides que A, et que globalement c'est donc l'algorithme en 2Noprations qui est le plus rapide.

Plus gnralement, les facteurs multiplicatifs n 'ont pas forcment d'influence sur l'efficacit d 'un algorithme, et ne sont donc paspris en compte dans la mesure de la complexit. Cela permet auss i de rpondre notre question de tout l'heure : si deuxprogrammeurs ont deux ordinateurs , et que l'un est plus rapide que l'autre, il sera par exemple 3 fois plus rapide en moyenne ; cefacteur cons tant sera nglig, et les deux programmeurs peuvent donc comparer la complexit de leurs algorithmes sans

problme.

On a donc nglig pas mal de chos es, ce qui aboutit une notion plutt simple et ass ez gnrale. Cette gnralit fait de lacomplexit un outil trs pratique, mais elle a videmment des inconvnients : dans certains cas trs particuliers, un algorithme

plus complexe mettra en ralit moins de temps s 'effectuer (par exemple, les facteurs constants peuvent jouer en ralit un rletrs important : et s i le rservoir de Haskell le fermier tait norme et mettait toute la journe se remplir ?). Cependant, dans lagrande majorit des cas, la complexit est une indication fiable des performances de l'algorithme. En particulier, le fait que ce soitune mesure asymptotique veut dire que les carts entre deux complexits se font de plus en plus importants quand la taille del'entre augmente. Un algorithme en N oprations longues sera peut-tre un peu plus lent qu'un algorithme en N*N oprations

trs rapides quand N vaut 10 ou 20, mais pour N = 3000 ou N = 8 millions, l'algorithme le moins complexe sera trs certainement leplus rapide.

Notation "grand O"On a vu que la complexit ne prenait en compte qu 'un ordre de grandeur du nombre d'oprations (on nglige des choses ). Pourreprsenter cette approximation on utilise une notation s pcifique, la notation O. Par exemple, pour dire que (avec N ranges de

grenouilles) la premire mthode de Haskell s'effectue en environ N2 oprations, on dit qu'elle a une complexit O(N2). De mme,


www.siteduzero.com


14/70

la deuxime mthode, plus rapide, a une complexit O(N).

La notation O es t comme un grand s ac, qui permet de ranger ensemble des nombres d'oprations diffrents, mais qui ont le mmeordre de grandeur. Par exemple, des algorithmes effectuant environ N oprations, 2*N+5 oprations ou N/2 oprations ont tous

la mme complexit : on la note O(N) (lire "grand O de N"). De mme, un algorithme en (2*N2 + 3*N + 5) oprations aura une

complexit de O(N2 ) : on nglige les termes 3*N et 5 qui sont de plus pet its degrs que 2N2 , donc croissent moins vite.

Plus gnralement, s i f(N) dsigne une express ion mathmatique dpendant de la variable N qui reprsente un nombre (le choixdu nom de la variable N est libre : on pourrait auss i la noter par exemple E, P ou R), O(f(N)) dsigne la complexit des algorithmess'excutant en "environ" (pour une s ignification bien prcise de cet "environ") f(N) oprations .

La s ignification de la notation O (appele auss i "notation de Landau") varie lgrement s elon les auteurs , et certains utilisentd'autres notations approchantes (par exemple, on peut faire une distinction entre "environ N oprations ou (beaucoup) moins" et"prcisment environ N oprations", mais utiliser O pour exprimer prcisment la complexit d'un algorithme est une conventioncommune aux scientifiques du domaine. Si vous dcidez de vous spcialiser dans l'algorithmique (ou que vous avez la chanced'tudier les comportements asymptotiques en analyse), il vous faudra sans doute approfondir un peu plus les fondementsformels de cette notation, mais cela devrait largement suffire pour ce texte, et plus gnralement pour une comprhension solidede la complexit des algorithmes (qui dpend en pratique remarquablement peu des subtilits mathmatiques de la notation O).

Complexit en temps, complexit mmoireOn peut faire plusieurs choix pour exprimer le plus prcisment possible la complexit d'un algorithme. On a choisi tout d'abordune quantification des conditions d'entre, par exemple par la variable N (pour N ranges de grenouilles, N pages web, Nracteurs nuclaires, etc.). On peut videmment choisir un autre nom de variable, mais surtout on peut avoir plusieurs variablesdiffrentes. Si on cherche tondre la pelouse d'un jardin rectangulaire, on exprimera sans doute sa complexit en fonction lafois de la largeur L et de la longueur R du jardin. De mme, si Haskell le fermier avait plus de ranges de grenouilles que demarcages d isponibles, il pourrait calculer ses algorithmes en fonction la fois du nombre N de ranges de grenouilles et dunombre M de marcages.

Mais un autre choix important est celui du type des oprations mesurer. On a parl jusqu'ici d'efficacit ou deperformances,termes plutt flous , ou de rapidit. Il faut savoir, et c'est trs important, que les programmeurs ne s 'intress ent pas uniquementau temps d'excution de leurs algorithmes. Il peuvent en mesurer bien d'autres caractrist iques, la plus courante tant laconsommation mmoire.

C'est aussi une mesure de la complexit. Si par exemple vous avez besoin d'allouer en moyenne N Kilo-octets de mmoire pour unalgorithme dont l'entre est de taille N, la complexit mmoire est en O(N). Plus gnralement, on ne connat pas la taille concrte(en octets ) demande par l'algorithme, mais un ordre de grandeur des structures utilises : s i vous utilisez N tableaux de taille N(par exemple, un par range de grenouilles, qui contient le nom de chacune des grenouilles de la range) vous avez une

complexit mmoire en O(N2 ). Si on remarque qu'on n'a besoin que d 'une range la fois, et qu'on n'alloue qu'un seul tableau lafois au lieu de N en mme temps, on a une complexit en O(N).

Il est intressant en gnral de mesurer la fois la complexit en temps (la rapidit d 'excution) et en mmoire (la quantitd'espace occup pendant l'excution) de l'algorithme. Dans les cas simples la complexit mmoire est trs simple, mais pour des

problmes plus compliqus, elles peuvent interargir de manire trs riche : on peut choisir par exemple de sacrifier un peu derapidit d'excution pour utiliser moins de mmoire, ou au contraire d'augmenter la vitesse en augmentant la complexit enmmoire de notre algorithme, par exemple en stockant dans un tableau les rsultats dj calculs (c'est le principe de la mise encache).

Plus les contraintes s ur les programmes s ont fortes , plus on a besoin d'informations prcises . Dans certains domaines del'informatique on s'intressera d 'autres caractristiques, parfois mesurables elles aussi en terme de complexit, des algorithmes.Par exemple, un programmeur pour calculatrice ou systme embarqu pourra s'interroger sur la consommation lectrique de sonalgorithme, afin d'conomiser la batterie. Dans le cas gnral, on s'intressera cependant uniquement aux complexits en temps eten mmoire, et mme principalement la complexit en temps.

Complexit dans le pire des casLe nombre d'oprations qu'effectue un algorithme dpend videmment des conditions de dpart. Par exemple, voici un algorithmetrs s imple permettant de savoir si une valeur donne s e trouve ou non dans une liste de valeurs (par exemple "est-ce que j'aidj mis la farine dans ma liste de course ?") :

Code : Autre

pour savoir si la valeur se trouve dans la liste, on parcourt laliste, en s'arrtant si on trouve la valeur recherche. Si ona parcouru toute la liste sans rien trouver, c'est qu'elle ne contientpas la valeur recherche.


www.siteduzero.com


15/70

Imaginons que l'lment que l'on cherche ne se trouve pas dans la liste, et que celle-ci est de taille L. Pour vrifier qu'il ne s'ytrouve pas, l'algorithme a parcouru tous les lments de la liste, en comparant chaque lment avec celui que l'on cherche : on adonc effectu L comparaisons. On peut donc dire que notre algorithme a une complexit de O(L). On dit aussi qu'il s'excute entemps linaire (car sa progression est linaire : si on double la taille de la liste d'entre, il mettra deux fois plus de temps, de mmeque si on double la longueur d'une ligne droite, vous mettrez deux fois plus de temps la parcourir).

Mais que se pas se-t-il si l'lment recherch se trouve au tout dbut de la liste ? Par exemple, si "farine" se trouve en premierdans notre liste de course, on s 'en apercevra immdiatement et on arrtera la recherche aprs avoir fait une opration seulement.Dans d 'autres cas on s'arrtera au bout de 2, 3 oprations, mme s i la liste contient 5000 lments .

C'est l qu'intervient la notion de "pire des cas " : quand on calcule la complexit d'un algorithme, on peut cons idrer que l'entredonne est la "pire" possible pour notre algorithme. Ici par exemple, on calculera le nombre d'oprations avec une ent re quidemande le plus grand nombre d'oprations (et non pas juste une ou deux), c'est dire une liste qui ne contient pas la valeurrecherche.

C'est une sorte de scurit du point de vue du programmeur : les complexits calcules tant dans le "pire des cas", il sait que ase passera forcment mieux. De la mme faon que les programmeurs web scurisent leurs applications en s e demandant "qu'est-ce que l'utilisateur le plus malicieux pourra entrer comme texte pour pirater mon site ?", l'algorithmicien s e demande "quelle est la

liste vicieuse qui fera prendre plein de temps mon algorithme, et combien ?".Cette mthode permet de mesurer ce qu'on appelle "complexit dans le pire des cas". Dans le cadre de ce tuto, nous nousintresserons quas i-uniquement cette mthode de mesure, donc les complexits seront toujours (sauf indication expresse)exprimes dans ce cadre.

L'intrt pour le pire des cas vient du fait que trs s ouvent, une s ituation quelconque a un comportement as sez proche du p iredes cas. Pour notre exemple, supposons que l'lment s e trouve effectivement dans la liste, mais qu'il soit plac une pos itionalatoire, inconnue du programmeur. Elle a autant de chances de se trouver au dbut de la liste (donc qui s'arrte trs vite), qu'aumilieu ou carrment la fin (on doit alors parcourir toute la liste). En moyenne, on fera donc un demi-parcours par essai : entre un

parcours complet et un demi-parcours , il y a seulement un facteur multiplicatif cons tant, donc c'est quivalent du point de vue dela complexit.

Il existe des algorithmes dont le cas "moyen" et le pire des cas ont une complexit trs diffrente. Dans ce cas , il est poss ible defaire des tudes plus approfondies, avec d 'autres mthodes de calcul de la complexit, mais ce sujet plus dlicat ne sera pasabord pour l'instant.


www.siteduzero.com


16/70

Un peu de pratiqueQu'est-ce qu'on attend de vous ?

C'est bien beau, la complexit, mais quel est le rapport avec un "cours d'algorithmique" ?

L'algorithmique est la science de la conception et de l'tude des algorithmes. Elle est bien antrieure l'informatique telle que

vous la connaiss ez, mais aujourd'hui pratique quas i-exclusivement par des scientifiques informaticiens. C'est un domaine trsvaste, et qui demande un niveau avanc de connaissances mathmatiques.

Tous les informaticiens n'ont pas besoin d'tre des algorithmiciens de gnie. En effet, les problmes auxquels s ont confronts laplupart des programmeurs s ont en ralit assez simples du point de vue algorithmique, et jouent s ur beaucoup d'autres as pectset difficults de la programmation (fiabilit face aux bugs, respect des spcifications, ergonomie de l'interface, interoprabilit,etc.).

Cependant, vous aurez quelque fois besoin de mettre en place quelque chose d'un peu plus sophistiqu. Dans ce cas, desconnaiss ances de bas e en algorithmique pourraient se rvler trs utiles. On ne vous demande pas d'inventer vous-mmes unnouvel algorithme rvolutionnaire et de faire une preuve bton de sa complexit, mais ne serait-ce que pour pouvoir utiliser demanire adapte les algorithmes que vous trouverez sur le net ou dans vos bibliothques logicielles, il est nces saire d'avoir uneformation de base.

Une connaissance de l'algorithmique vous permettra donc d 'tre plus efficace, de comprendre mieux les indications sur ce sujetqui vous entourent, et aussi de ne pas crire de choses aberrantes : certains codes s ont justes mais s ont abs urdes d'un point devue algorithmique. L o un programmeur non averti risquera de les utiliser ("a marche donc a va"), vous reprerez rapidementle problme et pourrez mettre en place une vraie solution.

Aprs ces palabres, vous avez sans doute envie de mettre un peu les mains dans le cambouis. Voici deux petites tudes decomplexit trs s imples, qui devraient vous permettre d'avoir une ide un peu plus prcise des raisonnements destins mesurerla complexit.

Chercher le plus grand / petit lmentVous dispos ez d'une liste d'entiers pos itifs, et vous voulez trouver le plus grand de la liste. La faon classique de procder est lasuivante : on parcourt la liste en conservant tout du long : l'lment le plus grand trouv jusqu' prsent, que l'on nomme"maximum actuel".

Code : Autre

Au dbut, le maximum actuel est 0. On compare chaque lment avec lemaximum actuel : s'il est plus grand que le maximum connu, il devientle maximum actuel son tour. la fin du parcours, le maximum actuelest le maximum de tout le tableau.

Voici deux implmentations de cet algorithme, l'une en PHP, l'autre en OCaml :

Code : PHP

Code : OCaml

let maximum liste = letrec parcours max_actuel =function |[]-> max_actuel | elem::reste -> parcours (max max_actuel elem) reste


www.siteduzero.com


17/70


18/70

la liste donne en entre, et pour chaque lment, on regarde s'ilest prsent dans U (on peut utiliser pour cela l'algorithme prsentdans la section prcdente). S'il n'y est pas, on l'y ajoute. lafin du parcours, U contient tous les lments uniques de la liste dedpart : on peut la renvoyer, c'est une solution notre problme.

Exercice : implmentez l'algorithme de rcupration des lments uniques d'une liste dans le langage de votre choix.

Complexit

Quelle est la complexit de cet algorithme ? Si vous avez bien compris le calcul de la complexit des algorithmes prcdents,celui-ci vous parat peut-tre simple, mais autant faire trop que pas ass ez.

Pour chaque lment de la liste de dpart, on effectue un parcours de la liste U, donc autant d'oprations que U a d'lments . Leproblme c'est que la taille de U change pendant le parcours de la liste de dpart, puisqu'on y ajoute des lments. Quand onconsidre le premier lment, la liste U est vide (donc on n'effectue aucune opration). Quand on considre le deuxime lment,U a 1 lment, donc on effectue une opration de plus .


www.siteduzero.com


19/70

Mais quand on arrive au troisime lment, on ne peut plus tre aussi sr : soit les deux premiers lments taient diffrents, etils ont tous les deux t ajouts U, et dans ce cas on effectue 2 oprations, soit ils taient gaux et le deuxime n'a pas tajout : on n'effectue qu'une seule opration. Comme on l'a dj dit, on calcule la complexit dans "le pire des cas" : c'est--direcelui qui nous fait faire le plus d'oprations. On va donc cons idrer que tous les lments de la liste de dpart sont diffrents(puisque c'est la situation qui cre la liste U la plus grande, et donc demande le plus d'oprations).

Dans le pire des cas , on ajoute U tous les lments de la liste de dpart, un par un. Au n-ime lment de la liste de dpart, on a

donc ajout les (n-1) lments prcdents, ce qui fait n-1 oprations. On a donc au total 0 + 1 + 2 + ... + (L-1) oprations (L-1oprations pour le dernier lment de la liste). On a fait trs peu d'oprations au dbut mais beaucoup d 'oprations la fin : cela

se compense et au to tal cela fait environ L*L/2, soit L2 /2, oprations (si vous ne connaissez pas la formule, vous trouverez uneanalyse plus dtaille de cette somme dans le tuto sur le tri par insertion. Notre algorithme a donc une complexit en temps de

O(L2 ) : on enlve le facteur 1/2 constant. Il faut savoir que pour O(L2) on dit aus si "quadratique" (comme on dit "linaire" pourO(L)), parce que a augmente "au carr".

En plus d'tre plus lent, l'algorithme a aussi une complexit en mmoire plus importante : on a construit une liste (donc demandde l'espace mmoire) qui n'existait pas au dpart. Dans le pire des cas, la liste U a autant d'lments que la liste de dpart : onaurait donc allou de l'espace pour L lments, ce qui fait une complexit mmoire de O(L) : l'utilisation mmoire tait cons tante

pour le premier algorithme, elle est maintenant linaire.

On peut au passage remarquer que cet algorithme demande uniquement de comparer des lments entre eux. En particulier, ils

n'ont pas besoin d'tre des entiers naturels : on pourrait trs bien utiliser le mme algorithme pour liminer des doublons dansune liste de mots, de couples de nombres virgule, etc. De nombreux algorithmes s'expriment ainsi, indpendamment du typeconcret des lments des structures manipules.

Trouver les lments uniques : autre solutionIl existe une autre solution, laquelle vous avez peut-tre (si vous tes un peu tordus ) pens en rflchiss ant l'algorithme :

il est possible de commencer par trier les lments de la liste. Ainsi, tous les lments identiques s e retrouvent cte cte, et ildevient trs simple d'liminer les doublons :

Citation

Il suffit de parcourir la liste en se souvenant du dernier lmentparcouru. Si l'lment actuel est le mme que l'lment prcdent,

alors c'est un doublon et on ne l'inclut pas dans la liste deslments uniques.

L'algorithme n'est plus valable s i les lments gaux ne sont pas juste ct les uns des autres, donc il faut forcment trier laliste avant. Quelle est sa complexit ? L'limination des doublons se fait en un seul parcours de la liste, elle est donc linaire.Mais comme on a d trier la liste avant, ce tri a aus si effectu des oprations qu'il faut prendre en compte dans la complexittotale de ce deuxime algorithme.

C'est un peu de la triche, parce que vous ne savez pas encore comment trier les lments d'une liste (j'espre que vous saurez lefaire, et mme de plusieurs manires diffrentes , la fin de ce cours). Vous aurez donc d utiliser une des fonctions de votrelangage de programmation ou d'une bibliothque externe fournie ct, ce qui ne correspond pas forcment la dfinition d'unalgorithme, qui demande des descriptions "prcises , l'aide de concepts simples" : on peut attendre d'un ordinateur qu'il sache

parcourir une liste ou comparer des lments, mais trier c'est p lus difficile (un peu comme ranger sa chambre, ou sa centralenuclaire). Quand vous connatrez de nombreux algorithmes, vous pourrez facilement les utiliser pour mettre au point vos

propres solutions, mais actuellement vous devriez vous limiter ce que vous avez dj conu (donc, pas de tri de tableau).

Dans tous les cas, cette mthode marche, et le fait que ce soit de la triche ne me permet pas d'esquiver la ques tion de lacomplexit. Il se trouve que la complexit de cet algorithme dpend de la complexit du tri : si par exemple le tri effectue environ

L2 oprations, c'est beaucoup plus que les L oprations que l'on fait ensuite, et la complexit globale est bien en O(L2 ).Cependant, il existe des tris plus sophistiqus (et plus compliqus) qui, tout en faisant toujours plus de L oprations (et en ayant

dans le cas gnral une complexit plus grande que O(L)), font beaucoup moins de L2 oprations. Nous le verrons le momentvenu, mais ces tris l produisent un algorithme plus efficace que le premier propos , qui est plus "naf".

Enfin, il faut noter qu'il n'est pas ncess aire de trier la liste pour obtenir un algorithme plus efficace. On peut auss i choisir

d'utiliser la place de la liste U une s tructure de donnes plus efficace : dans notre cas , il faudrait qu'elle puiss e rpondrerapidement la ques tion "l'lment machin a-t-il dj t rencontr ?" . Si l'on peut y rpondre s ans parcourir toute la st ructure(comme on fait pour U), on peut avoir un algorithme plus rapide. De telles structures de donnes existent, et permettent d'obtenirun algorithme aussi efficace qu'avec le tri (en plus, comme il est proche de l'algorithme naf, il est plus naturel concevoir et plusfacile comprendre), mais nous ne les aborderons pas non plus tout de suite.Vous avez maintenant dj trois algorithmes dans votre carquois.


www.siteduzero.com
http://www.siteduzero.com/http://www.siteduzero.com/tuto-3-4643-1-le-tri-par-insertion.html#ss_part_3


20/70

La recherche d'un lment donn dans une liste, et la recherche du p lus grand lment d'une liste sont des algorithmes ass ezproches, linaire en temps (en O(N)) et utilisation mmoire cons tante (en O(1)). L'limination des lments en double dans uneliste est plus complique, puisque l'algorithme le plus simple a une complexit quadratique (en O(N*N)) en temps et linaire enmmoire.

J'espre que ces tudes plus concrtes (mais avec encore un peu trop de blabla) vous ont convaincus que cette discipline

servait quand mme parfois quelque chos e, et que vous commencez vous habituer aux concepts de base : algorithme,complexit en temps et en mmoire, structure de donnes.


www.siteduzero.com


21/70

Partie 2 : Premiers exemples de structures de donnes et d'algorithmescourants

Notions de structures de donnes : tableaux et listeschanes

Maintenant que vous avez vos premires notions concernant ce qu'est la complexit algorithmique, il est temps de faire uneintroduction au concept destructure de donnes que l'on vous a fait miroiter dans l'introduction. Tout comme la premire partie,nous ne ferons rien de compliqu pour l'instant, mais les bases prsentes ici seront utiles pour la suite du cours.

Nous nous concentrerons sur deux structures extrmement courantes : les listes (simplement chanes) et les tableaux.

DfinitionLe principe de base d 'une structure de donnes, c'est de s tocker des lments auxquels le programmeur veut pouvoir accder

plus tard. On appelle les diffrentes utilisations pos sibles de la structure de donnes des oprations.

Par exemple, une opration courante est la lecture : on veut rcuprer un lment s tock dans la structure. Il existe denombreuses autres oprations, comme l'insertion, qui rajoute un nouvel lment dans la structure de donnes , ou la

suppression, qui en enlve.

Toutes les structures de donnes ne permettent pas les mmes oprations , et surtout elles n'ont pas toujours le mme cot. Parexemple, sur certaines s tructures, il est trs rapide d'ajouter un lment, dans d'autres c'est difficile et cela peut demander unerorganisation complte. Le cot des structures de donnes peut s e mesurer ass ez finement, mais ce qui nous intress e dans cecours, c'est la complexit : pour chaque s tructure de donnes utilise, on ess aiera d'avoir une bonne ide de la complexit desoprations que l'on effectue.

Cette connaissance des cots a deux intrts : quand on nous donne un algorithme utilisant une structure de donnesparticulire, on a besoin de connatre le cot (la complexit) des oprations effectues pour valuer la complexit globale del'algorithme. Mais surtout, et c'est sans doute l'aspect le plus intressant, quand on a une ide des oprations dont on a besoin

pour un algorithme, on peut choisirla structure de donnes la plus adapte (celle pour laquelle ces oprations s ont les moinscoteuses).

Dans la pratique, la plupart des gens utilisent des algorithmes ass ez simples (qui ne reposent pas sur des manipulationssophistiques), o le seul choix de la bonne s tructure de donnes peut faire la diffrence au niveau des performances. Bienconnatre ses structures de donnes et savoir faire un choix joue donc un rle trs important pour le programmeur.

Tableaux

Le tableau est sans doute la structure de donnes la plus courante, du moins dans les langages drivs ou inspirs par lelangage C.

Le principe d'un tableau est trs simple : on s tocke les lments dans des cases , chaque case tant t iquete d'un numro(gnralement appel indice). Pour accder un lment particulier d'un tableau, on donne son indice.

Les indices sont des entiers conscutifs, et on considrera qu'ils commencent 0, comme dans la plupart des langages deprogrammation. Le premier lment es t donc l'indice 0, le deuxime l'indice 1, etc. (attention au dcalage). En particulier, si nest la taille du tableau, le dernier lment se trouve l'indice n-1. Demander l'accs un indice qui n'existe pas provoque uneerreur.

On cons idre que la taille d'un tableau est toujours connue (le programmeur a d la connatre quand il a demand la cration dutableau, et ens uite il suffit de la conserver).

Partie 2 : Premiers exemples de structures de donnes et d'algorithmes courants 19/68

www.siteduzero.com


22/70

Le temps de cration du tableau dpend des langages . En gnral, la fonction de cration met dans chaque cas e une valeur pardfaut, et s on temps d'excution es t alors proportionnel la longueur du tableau (donc en complexit O(N) si N est la taille dutableau). Cependant, il est possible dans certains langages de crer des tableaux "non initialiss " (avec des valeurs inconnues

pour chaque case) plus rapidement. C'est une pratique qui peut tre dangereus e car on a alors parfois des valeurs qui n'ontaucun s ens dans notre tableau. On considrera ici que tous les tableaux sont initialiss ds leur cration, et donc qu'elle esttoujours en O(N).

Listes

La liste est une structure de donnes extrmement utilise. En particulier, elle a jou un rle majeur dans le langageLisp et restetrs prsente dans les nombreux langages qui s'en sont inspirs.

Remarque : pour dcrire correctement une liste, je suis forc de m'carter lgrement des pures cons idrations algorithmiques ,pour dtailler un peu plus prcisment la manire dont les langages de programmation grent les s tructures de donnes . Je vaisutiliser ici une description indpendante du langage de programmation : on parlera de cellules poss dant un ou plusieurschamps. Une cellule est tout simplement un ensemble de cases qui permettent de s tocker des donnes , et auxquelles on accde

par leur nom (que l'on appelle nom du champ, comme les champs des formulaires par exemple). Par exemple, on pourra dcrire unestructure servant stocker l'adresse et le numro d'une personne comme une cellule trois champs, nom, adresse et

tlphone.

Selon votre langage, les cellules auront des formes diffrentes : struct en C, objets en Java, etc. : vous de choisir latraduction qui vous p lat le plus. Nous ne rentrerons pas non plus dans les dtails de bas niveau sur l'organisation mmoire, maisil est bon d'avoir un modle commun pour pouvoir discuter.

On considrera de plus que la cration (et la destruction) d'une cellule (si elle a un nombre fix de champs), ainsi que la lecture oula modification d'un champ, se fait en temps cons tant.

Venons-en maintenant la dfinition d'une liste. Une liste est :

soit la liste vide ;soit une cellule deux champs, un champ tte contenant un lment, et un champ queue contenant l'adresse d'une

autre liste.

Autrement dit, une liste est "soit vide, soit un lment suivi d'une liste". Cette dfinition est amusante car elle est rcursive : elleutilise le mot "liste". La dfinition d'une liste utilise la dfinition d'une liste ! Mais, de mme que les programmes rcursifs netournent pas tous en boucle l'infini, cette dfinition n'est pas un cercle vicieux, et elle est tout fait correcte (vous le verrez l'usage).

Une liste peut donc tre la liste vide (0 lment), ou un lment suivi de la liste vide (1 lment), ou un lment suivi d'un lmentsuivi de la liste vide (2 lments), etc.

On dira que l'lment dans le champ tte est la tte de la liste, et que la liste dans le champ queue est s a queue. La queued'une liste contient tous les lments de la liste, sauf le premier. Par exemple, la queue de la liste [1; 2; 3] est [2; 3]. Biensr, la liste v ide n'a ni queue ni tte : essayer d'accder un de ces champs provoque une erreur.

Il existe en ralit de nombreuses variantes de cette structure. J'ai dcrit ici la plus simple, que l'on appelle aussi liste simplementchane car les cellules contiennent seulement, en plus d'un lment, une flche vers le suivant (on imagine que ces flches

forment une chane). D'autres s tructures sont u tiles dans des cas particuliers (par exemple on peut mettre deux flches par cellule,une vers l'lment s uivant, et une vers l'lment prcdent, c'est le principe de la liste doublement chane), mais celle-ci est laplus courante et la plus utile.

Implmentation : la reprsentation des listes chaines dpend beaucoup des langages de programmation. Dans les langagesfonctionnels, ce type est dj dfini (par exemple en Caml on note [] la liste vide et tete::queue la cellule dont la tte est


www.siteduzero.com


23/70

tete et la queue queue. En C, il faut le construire soi-mme. On utilise une reprsentation trs class ique : une s tructure pourles cellules, et le pointeurNULL pour la liste vide :

Code : C

struct list{

int val; struct list *next;};typedefstruct list List;

On reprsentes alors les listes comme des pointeurs vers une cellule :Code : C

List *une_liste;

Comme en C, il faut allouer et librer la mmoire la main, on aura aussi besoin d'une fonction qui libre toutes les cellules d'uneliste :

Code : C

voidfree_list(List *list){ while (list !=NULL) { /* tant que la liste n'est pas vide */

List *cell = list;list = list->next;free(cell);

}

}

chaque tape de la boucle while, on s tocke la tte de la liste dans une variable cell, on avance dans la liste (list devientla queue de la liste), et on libre cell. On est oblig d'utiliser cette variable intermdiaire, parce que si on commenait parfree(list), alors list->next n'aurait plus de sens (puisque list a t efface) et on ne pourrait pas passer la suite dela liste.

Ajout / retrait, taille, accs un lment

Ajout / Retrait

Quelle est la manire la plus simple d'ajouter, ou d'enlever un lment un tableau ou une liste ?

Pour une liste, ces deux oprations s ont trs simples tant que l'on considre seulement un ajout (ou une suppress ion) en tte deliste : pour supprimer l'lment de tte, il suffit de remplacer la liste par sa queue (qui est la liste de tous les lments suivants).Pour ajouter un lment en tte, il suffit de crer une nouvelle cellule, de mettre cet lment dans le champ tte, et la liste dedpart dans le champ queue.


www.siteduzero.com


24/70

Ces deux oprations se font en temps constant (la premire revient lire un champ, et la deuxime crer une cellule), donc leurcomplexit est en O(1).

Remarque : l'opration d'ajout en tte de liste (c'est--dire la cration d'une nouvelle liste partir d'un lment et d'une ancienneliste) es t fondamentale dans les manipulations de liste. Elle poss de un nom spcifique, cons (lire "conss e"), qui a mme donnlieu un verbe (utilis seulement en informatique) en anglais, to cons. Elle est fondamentale parce qu'en quelque sorte elle fait

partie de la dfinition des listes , que l'on peut reformuler ainsi : soit une liste vide, soit un cons d'une liste.

Implmentation : Dans les langages o les listes existent dj, il est extrmement simple de dfinircons. Par exemple en Caml :

Code : OCaml

let cons tete queue = tete::queue

Sinon, il faut utiliser le type que l'on a dfini soi-mme. En C, il faut en plus s'occuper de l'allocation mmoire :Code : C

List *cons(int valeur, List *liste){

List *elem = malloc(sizeof(List)); if (NULL== elem)

exit(EXIT_FAILURE);elem->val = valeur;elem->next = liste;

return elem;}

Pour les tableaux, la question est plus dlicate. La taille d'un tableau tant fixe l'avance, il n'est pas possible de rajouter deslments (tout simplement parce qu'il n'y a pas forcment de place disponible dans la mmoire, sur les bords du tableau, pour

pouvoir l'agrandir). La mthode s re pour ajouter un (ou plusieurs) lments es t de crer un tableau plus grand autre part, quicontienne as sez de place pour tous les anciens lments et le (ou les) nouveau(x), et de recopier les anciens lments dans le

nouveau tableau, avant d 'ajouter les nouveaux. Cette mthode demande la cration d'un tableau de taille N+1, puis une recopiede chaque lment du tableau, elle est donc en O(N) (o N est la taille du tableau avant insertion), ou encore linaire. De mme, lataille d'un tableau tant fixe l'avance, il n'est pas pos sible d'en retirer des cases .

Remarque : dans certains langages, il est possible d'essayer de redimensionner les tableaux sur place dans certains cas , ou biend'liminer des lments qui sont en dbut ou en fin de tableau. Cela reste as sez hasardeux, et nous ne cons idrerons pas ces


www.siteduzero.com


25/70

oprations.

Taille

Quand il s'agit de calculer la taille de la structure de donnes, c'est le tableau qui a le beau rle. En effet, on considre que la tailled'un tableau est toujours connue, donc il n'y a pas de calculs faire pour l'obtenir : c'est une opration en O(1).

Pour une liste, on ne connat pas en gnral la taille d'une liste (surtout si on vient d'ajouter ou d'enlever beaucoup d'lments entte de cette liste). Pour calculer la taille d'une liste, on applique l'algorithme suivant :

si c'est la liste vide, sa taille est 0 ;sinon, on calcule la taille de s a queue, et on rajoute 1.

Ainsi, on va parcourir la liste jusqu' tomber sur la liste vide, en rajoutant 1 pour chaque lment. Cette mthode marche trsbien, mais demande un parcours complet de la liste, donc es t en O(N) (o N est la taille de la liste).

Remarque : comme pour les tableaux, il serait possible de stocker la taille des listes dans la structure elle-mme, au lieu de devoirla calculer chaque fois : en plus d'avoirtte et queue, on ajouterait chaque cellule un champ taille qui contiendrait lataille de la liste. Le problme de cette mthode est que l'opration cons devient plus coteuse : quand on cre une nouvellecellule pour l'lment rajouter, il faut y mettre le nouvel lment et la queue comme auparavant, mais ensuite il faut accder la

premire cellule de la queue, pour y lire la taille N de l'ancienne liste, pour pouvoir mettre N+1 dans le champ taille de lanouvelle cellule. Cela ne fait que rajouter une tape (plus prcisment, deux lectures de cellules, une addition et une initialisationde champ en plus), donc l'opration reste en O(1), mais cela ralentit quand mme sensiblement l'opration, ce qui est gnantquand on utilise beaucoup cons. En pratique, la plupart des gens utilisent beaucoup cons, et ont trs peu s ouvent besoin dela taille de la liste ; cette "optimisation" n'est donc pas intressante, car elle ralentirait le programme. Encore une fois, on retrouvel'ide centrale, qui est qu'il faut choisir ses structures de donnes selon l'utilisation qu'on veut en faire, pour que les oprationsles plus courantes s oient les plus rapides poss ibles.

Accs un lment

Comment faire si l'on veut rcuprer par exemple le cinquime lment de notre collection (liste ou tableau) ? Pour un tableau,c'est simple : on demande l'lment d'indice 4 (attention au dcalage), et on l'obtient immdiatement. Cette opration est en O(1).

Pour une liste, c'est plus d ifficile : quand on a une liste, on a accs directement la premire cellule, donc on ne connat que satte, et s a queue ; on ne peut donner rapidement que le premier lment. Mais en fait, on peut auss i avoir accs au deuxime :

c'est la tte de la queue de la liste ! Et au troisime : la tte de la queue de la queue de la liste. En fait, on cherche la tte de la

queue de la queue de la queue de la queue de la liste. Trop facile.

Voici un algorithme pour rcuprer l'lment d'indice n dans une liste :

si n = 0 (on demande le premier lment), renvoyer l'lment qui est dans le champ tte ;sinon, renvoyer l'lment qui est l'indice n-1 dans la liste qui est dans le champ queue.

Vous pouvez remarquer qu'on cons idre directement notre liste comme une cellule : si la liste es t vide, on ne peut pas y rcuprerd'lment, donc c'est une erreur.

Pour accder un lment, il faut parcourir toute la liste jusqu' la position voulue. Pour accder l'lment d'indice k il fautdonc faire environ k oprations . Quelle es t la complexit de l'opration ? Comme expliqu dans la premire partie, il faut tre

pessimiste et considrer la complexit dans lepire des cas : dans le pire des cas , on cherche le dernierlment de la liste, il fautdonc la parcourir toute entire. L'opration est donc linaire, en O(N).

Vous avez sans doute remarqu la grande diffrence entre le problme de l'accs aupremierlment, et l'accs "n'importe quel"lment. Dans une liste, la premire opration est en O(1) ( ) et la deuxime en O(N) ( ).

Pour bien les diffrencier, les informaticiens ont un terme spcifique pour dire "l'accs n'importe quel lment" : ils parlentd'accs arbitraire. De nombreuses structures de donnes peuvent accder certains lments privilgis trs rapidement, mais


www.siteduzero.com


26/70

sont plus lentes pour l'accs arbitraire. Les tableaux ont la proprit d'avoir un accs arbitraire en temps cons tant, ce qui est rareet trs utile dans certains cas.

Remarque : vous ne connaissiez peut-tre pas le terme "accs arbitraire", mais vous avez srement dj rencontr sonquivalent anglais, random access. Ou alors, vous ne vous tes jamais demand, en tripotant la mmoire vive de votreordinateur, ce que s ignifiait RAM : Random Access Memory, mmoire accs arbitraire.

Le problme de l'accs une liste ne s e limite pas seulement la lecture de l'lment une position donne : on pourrait auss ivouloir rajouter ou enlever un lment cet te position. Ces algorithmes sont proches de celui de lecture, et ont eux aussi unecomplexit linaire.

Petite anecdote pour illustrer l'importance de l'tude de la complexit : lorsque nous ne travaillons pas sur ce tutoriel, il nousarrive de jouer. Parmi ces jeux, l'un d'entre eux avait un temps de chargement de 90 secondes ds qu'il fallait gnrer une nouvellecarte du monde. Un peu surpris, et tant donn que le code source du jeu tait disponible, nous avons tudi la fonctionnalitfautive. Le jeu passait 88 secondes accder de manire alatoire aux lments d'une liste ! En transformant cette liste en simpletableau, le chargement est devenu quas i-instantan. Les plus curieux peuvent aller tudierle changement effectu qui a t

accept par l'auteur du jeu vido en question.

Concatnation, filtrage

Concatnation

Imaginons que l'on ait deux groupes d'lments , stocks dans deux listes (ou deux tableaux) diffrents, et que l'on veuille lesrunir. On veut construire une structure qui est en quelque sorte la "somme" des deux structures de dpart. On appelle cetteopration la "concatnation" (cela vient du latin pour "enchaner ensemble").

Pour des tableaux, c'est assez facile : si le premier tableau est A, et le deuxime B, et que l'on note L la taille de A et L' (lire "Lprime") la taille de B, on cre un tableau de taille L + L', o l'on recopie tous les lments de A, puis tous les lments de B. Celademande L + L' copies (et la cration de L + L' cases) : l'opration est en O(L + L').

Remarque : j'ai ici donn la complexit en fonction de deux variables, L et L'. J'avais auparavant dfini la complexit commedpendant d'une s eule variable, mais c'est un cas particulier. La complexit d'un algorithme peut dpendre de tous les paramtresdont dpend l'algorithme, et pas seulement d 'un seul. De plus, la complexit n'a de sens que quand les variables que l'on utilise

pour l'exprimer sont bien dfinies : dire O(N3) ne suffit pas, il faut s'ass urer que tout le monde comprend ce que dsigne lavariable N (mme si en gnral, c'est vident et laiss implicite).

Pour une liste, la situation est un peu diffrente : comme on peut facilement ajouter un lment en tte de liste, on peut aus siajouter une s uite d'lments . Il suffit donc d'ajouter tous les lments de A en tte de la liste B. Cela revient faire une copie de Adevant B. Vous pouvez dj deviner (l'algorithme sera prcis ensuite) que comme on ajoute L (la taille de A) lments en tte deB, la complexit sera en O(L).


www.siteduzero.com
http://www.siteduzero.com/https://bitbucket.org/genericcontainer/goblin-camp/changeset/e2010496af0a


27/70

Voil un algorithme plus dtaill effectuant la concatnation de A et de B :

si elle est v ide, on n 'a rien faire : on renvoie la deuxime liste, B ;si c'est une cellule, on procde en deux temps :

on calcule la concatnat ion de sa queue avec B,

on rajoute la tte ce rsultat ;

On peut rsumer cela parcons(tete(A), concat(queue(A), B)).

Encore une fois, cette fonction est rcursive, je vous invite vrifier qu'elle marche bien en l'implmentant vous-mmes dans

votre langage prfr. Quelle est sa complexit ? On va appeler la fonction concat une fois s urA, puis surqueue(A), puissurqueue(queue(A)), etc., jusqu' parvenir la liste vide. En d'autres termes, on aura appel concat autant de fois que Aa d'lments . Le reste des oprations (effectues chaque appel de concat) est un cons (et la lecture de la tte), donc en O(1).Faire L (o L est la taille de A) fois une opration en O(1), c'est--dire L fois une opration en temps constant, met un temps

proportionnel L. C'est en O(L).


www.siteduzero.com


28/70

Remarque : avec cet algorithme, on recopie (par le cons) chaque cellule de la liste A : la liste B est laisse inchange, mais on acr L cellules. Vous avez peut-tre remarqu qu'une autre manire de faire serait poss ible : on pourrait prendre directement ladernire flche de A (celle qui pointe vers la liste v ide), et la modifierpour la faire pointer vers la premire cellule de B. Cettemthode a l'avantage de ne pas demander de recopie des cellules de A, mais aussi un inconvnient majeur : elle modifie la liste A.Si vous aviez une variable qui dsignait A avant l'opration, elle ds igne maintenant concat(A, B). La liste A, en quelquesorte, a t "dtruite".

Ce comportement, que l'on appelle un effet de bord, peut donner lieu des bugs s i vous ne faites pas attention (par exemple sivous croyez avoir encore accs A, alors qu'en fait vous tes en train de manipulerc

Documents

51781 Algorithmique Pour l Apprenti Programmeur