Quels sont les différents types d'algorithmes ?
On distingue trois principales catégories d'algorithmes de Machine Learning : supervisés, non-supervisés, et semi-supervisés.
Chacune de ces catégories repose sur une méthode d'apprentissage différente.Quelles sont les 3 grandes phases d'un algorithme ?
Définition : Un algorithme comprend ensuite trois phases : Une phase d'initialisation ou d'entrée qui permet de donner une valeur initiale aux variables.
Une phase de traitement du problème.
Une phase de sortie des résultats. 2 .
0) Instructions d'entrées et de sortie.Quelle est l'algorithme le plus utilisé actuellement ?
La méthode la plus utilisée actuellement est sans doute la méthode de tri rapide ou Quicksort, qui a été inventée par Sir Charles Antony Richard Hoare en 1960 – d'aucuns disent que c'est l'algorithme le plus utilisé au monde
- Le langage algorithmique est un langage générique permettant de traiter des problèmes par concaténation d'instructions élémentaires.
Il est à la base de tous les langages de programmation (enfin tous les langages de programmations impératifs).
Algorithmique avancée
Algorithmique Avancée pour l'Intelligence Artificielle et les graphes
Algorithmique Avancée exercices
Algorithmique avancée
Algorithmique 2 et Structures de Données Avancées
Algorithmique et programmation
COURS ALGORITHMIQUE ET PROGRAMMATION INFORMATIQUE
ALGORITHMIQUE ET PROGRAMMATION STRUCTUREE EN
Cours de l'algorithmique et programmation: Licence SMI
Algorithmique avancéeBloc 5 du DIU " Enseignement de l"Informatique au Lycée »Bruno GrenetUniversité de MontpellierJuin 2020Ce texte présente les principaux points du programme du bloc 5Algorithmique avancéedu diplômeinter-universitaire " Enseignement de l"Informatique au Lycée » (cf.https://sourcesup.renater.fr/www/diu-eil/).
Les choix de rédaction ont été effectués dans l"idée de rester relativementproche du programme en vigueur de NSI en terminale générale, tout en dépassant ce programme àplusieurs reprises.
En particulier, la partie 3 possède une quatrième partie largement hors programmede NSI, et hors programme du DIU.Tout retour est bienvenu par email à l"adressebruno.grenet@umontpellier.fr, en particulierpour éliminer des erreurs et typos qui restent certainement1.Exercice?.?.Ilestrecommandéd"essayerdeprogrammerenPythonchacundesalgorithmesprésentésdanscetexte!La mise en page de ce document est fortement inspirée du canevasLegrand Orange Book, disponibleà l"adressehttp://www.latextemplates.com/template/the-legrand-orange-book.Copyright©2020 Bruno Grenet (http://www.lirmm.fr/~grenet/)Ce document est mis à disposition selon les termes de la licence CreativeCommons " Attribution - Pas d"utilisation commerciale - Partage dans lesmêmes conditions 4.
0) International ».1.Je remercie vivement Éric Zabban pour sa relecture détaillée de ces notes.12Bibliographie commentéeLes ouvrages suivants couvrent ce qui est présenté dans ce texte, et permettent surtout d"aller(beaucoup) plus loin.§Parties 1 et 2Th.
Cormen, Ch. Leiserson, R. Rivest, C.Stein.Introduction à l"algorithmique, Dunod, 2004(traduit de l"américain).La fameuse bible d"algorithmique.
Ce n"est pas l"ouvrage que je préfère, mais il fautreconnaître que son exhaustivité est impressionnante.J .E rickson.Algorithms, auto-publié, 2018.Mon bouquin préféré d"algorithmique.
Très complet, avec de nombreux exercices.Disponible en ligne :https://algorithms.wtf.S .D asgupta,Ch.
P apadimitriou,U .V azirani.Algorithms, McGraw-Hill, 2006.Super bouquin très concis, efficace (l"anti-thèse du " Cormen »).
Disponible trèsfacilement2en ligne.D .Bea uquier,J .Berstel, P h.Chréti enne.Éléments d"algorithmique, Masson, 1992.Ouvrage épuisé mais disponible en ligne :http://www-igm.univ-mlv.fr/~berstel/Elements/Elements.html.§Partie 3E.
Asarin.Calculabilité, support de cours et de TD, 2003.Mon introduction préférée à la calculabilité! En 44 pages, l"essentiel est présenté.
Enligne :https://www.irif.fr/~asarin/calc2k3/calcul_cours.pdf.S .P erifel.Complexité algorithmique, Ellipses, 2014.Très bon bouquin sur la théorie de la complexité, avec une approche assezscolaire.
Dis-ponibleenligne:https://www.irif.fr/~sperifel/livre_complexite.html.B.Bara k.Introduction to Theoretical Computer Science, en cours d"écriture.Ce bouquin ambitieux, toujours en cours d"écriture (mais qui compte déjà 600 pages),explore de manière assez complète3la théorie du calcul, de la calculabilité historiqueà la complexité la plus moderne.
Beaucoup de références à d"autres très bons ouvragesanglophones. En ligne :https://introtcs.org/.2. Je ne mets pas de lien car je doute de leur légalité.3.Certes, il manque les fonctions récursives primitives,cf.3.4.4.©Bruno GrenetAlgorithmi quea vancéeTable des matières3Table des matières1Algorithmes cl assiques41.
1) Arbres binaires 41.1. 1) Rappel de vocabulaire et notations41.1. 2) Algorithmes de base sur les arbres binaires51.1. 3) Arbres binaires de recherche81. 2) Graphes111.2. 1) Rappel de vocabulaire et notations111.2. 2) Parcours en largeur et plus courts chemins121.2. 3) Parcours en profondeur et cycles152Algorithmes a vancés172. 1) Programmation dynamique 172.1. 1) Un premier exemple : le rendu de monnaie182.1.2) La programmation dynamique,qu"es aquó?. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222.1.
3) L"alignement de séquences242. 2) Recherche textuelle 302.2. 1) Recherche naïve302.2. 2) La règle du mauvais caractère322.2. 3) Règle du bon suffixe342.2. 4) Algorithme de Boyer et Moore383Ca lculabilitéet co mplexité393. 1) Algorithmes, problèmes, fonctions 393.1. 1) Définitions393.1. 2) Algorithmes comme données413. 2) Calculabilité 423.2. 1) Toutes les fonctions ne sont pas calculables433.2. 2) Formalisation : la machine de Turing443. 3) Complexité483.3.1) Complexité des problèmes, classesPetNP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 483.3.
2) NP-complétude et "P=NP? ». . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 503.
4) Pour aller plus loin533.4. 1) Dénombrabilité533.4. 2) Autres formalisations de la notion d"algorithme553.4. 3) Autres problèmes incalculables563.4.4) Les fonctions récursives primitives et la bouclefor . . . . . . . . . . . . . . . . . . . . . . . . . . . . 593.4.
5) Formes normales et autres curiosités633.4. 6) Le non-déterminisme633.4. 7) Autres classes de complexité65Algorithmique avancée©Bruno Grenet41.Algorithmes classiques1Algorithmes cl assiquesCette partie est consacrée à des algorithmes sur les structures de données classiques que sont lesarbres binaires et les graphes.1.
1) A rbresbin airesDans cette partie, on s"intéresse aux algorithmes classiques sur les arbres binaires.
On suppose lastructure de données connue mais on rappelle dans une première partie le vocabulaire et les notationsutiles.
On ne se préoccupe pas de l"implantation précise sous-jacente.1.1.1) Ra ppelde v ocabulaireet n otationsUnarbre binaireest une structure de données hiérarchique, constituée denoeuds.
Le noeud initialest appeléracine. Chaque noeud peut posséder jusqu"à deuxfils(fils gauche et droit), dont il est lepère. La racine est le seul noeud deniveau0, et les fils d"un noeud de niveauisont des noeuds deniveaui+1. Le niveau maximal d"un noeud est appelé lahauteurde l"arbre. Un noeud sans fils estunefeuille. Seule la racine n"a pas de père.Chaque noeud possède unevaleur, qui peut être n"importequel objet (entier, chaîne de caractère, ).270458946Figure1 - Exemple d"arbre binaire de racine de valeur6, à9noeuds et de hauteur3.
Il possède4feuilles (en couleur).La valeur d"un noeudxest notéeval(x). Ses fils sont notésfilsG(x)etfilsD(x)et son père est notépere(x). On utilise le noeud spécial;(noeud vide) quandfilsG(x)(oufilsD(x)oupere(x)) n"existepas.SifilsG(x)6=;,pere(filsG(x)) =x, et de même pour le fils droit.Un arbre binaire est une structure récursive.
On appelledescendantsd"un noeud l"ensembleconstitué de ses fils, des fils de ses fils, etc. L"arbre dont le fils gauche d"un noeudxest racine estappelé lesous-arbre gauchedex.On définit de même lesous-arbre droitd"un noeudx.Exercice?.?.Montrerquelahauteurhd"unarbrebinaireApeutsecalculerrécursivementdelamanièresuivante:silaracineestunefeuille,lahauteurdeAest0;sinon,lahauteurdeAest1+max(hg,hd)oùhgestlahauteurdesonsous-arbregaucheethdcelledesonsous-arbredroit.Parconvention,lahauteurd"unarbredontlaracineestlenoeudvideest1:pourquoichoisircetteconvention?©Bruno GrenetAlgorithmi quea vancée1.1.
Arbres binaires51.1.2) Algorithmes de ba sesur l esarbres bin airesLes arbres binaires sont une structure de données fondamentalement récursive.
Ainsi, les algo-rithmes sur les arbres binaires sonta priorides algorithmes récursifs.On peut baser un grand nombredes algorithmes sur les arbres binaires sur la notion deparcours: parcourir un arbre, c"est passerpar chacun de ses noeuds.
Dans sa version la plus simple, il s"agit simplement d"afficher la valeur dechaque noeud.Algorithme 1.1- ParcoursInfixeEntrée :La racinexd"un arbre binaireASortie :L"algorithme affiche tous les noeuds deA1Six6=;:2ParcoursInfixe(filsG(x))3Afficherval(x)4ParcoursInfixe(filsD(x))Théorème 1.
2) L"algorithmeParcoursInfixeaffiche les valeurs de tous les noeuds deA, entempsO(n)oùnest le nombre de noeuds dansA.Démonstration.Pour démontrer queParcoursInfixeaffiche bien les valeurs de tous les noeuds deA,on utilise uneinduction structurelle, c"est-à-dire une récurrence sur la structure des arbres binaires.On effectue la démonstation en détail pour montrer le fonctionnement de cette induction, bien que lerésultat en lui-même soit évident.Le cas de base est l"arbre vide : il n"a aucun noeud et aucun affichage n"est effectué.
SiA6=;, lavaleur de sa racine est affichée à la ligne 3.Par hypothèse d"induction, les valeurs de tous les noeudsdu sous-arbre gauche de la racine sont affichées par l"appel récursif de la ligne 2.
De même, lesvaleurs des noeuds de son sous-arbre droit sont affichées par l"appel récursif de la ligne 4.
Puisquetout noeud est soit la racine, soit appartient à l"un des deux sous-arbres de la racine, les valeurs detous les noeuds sont affichées parParcoursInfixe.La complexité vient du fait que chaque noeud est affiché une fois.
On peut également la démontrerpar induction structurelle. La complexité pour l"arbre vide est constante.Si on notenGle nombrede noeuds du sous-arbre gauche etnDle nombre de noeuds du sous-arbre droit, la complexité del"appel récursif de la ligne 2 est par hypothèseO(nG), et celui de la ligne 4 estO(nD).
La complexitétotale est doncO(nG)+O(nD)+O(1) =O(nG+nD+1).Le nombre total de noeuds dans l"arbre étantn=nG+nD+1, la complexité estO(n).À côté du parcours infixe, on peut effectuer les parcourspréfixeetsuffixe, qui sont très proches.Alors que le parcours infixe affiche d"abord les noeuds du sous-arbre gauche, puis la racine, puis lesous-arbre droit, le parcours préfixe affiche la racine en premier et le parcours suffixe affiche la racineen dernier.Algorithmique avancée©Bruno Grenet61.
Algorithmes classiquesAlgorithme 1.3- ParcoursPréfixe1Six6=;:2Afficherval(x)3ParcoursPréfixe(filsG(x))4ParcoursPréfixe(filsD(x))Algorithme 1.4- ParcoursSuffixe1Six6=;:2ParcoursSuffixe(filsG(x))3ParcoursSuffixe(filsD(x))4Afficherval(x)EOn peut représenter une expression arithmétique par un arbre binaire, dont les valeurs desnoeuds sont soit des opérations (disons+,,) soit des entiers (pour les feuilles).
Par exemple,l"expression2(3+4)(62+4)est représentée par l"arbre ci-dessous. Le parcours infixede l"arbre fournit l"expression (en ajoutant les parenthèses nécessaires).Le parcours préfixecorrespond lui à lanotation polonaise 2+3 4+6 2 4et le parcours suffixe à lanotationpolonaise inverséea2 3 4+6 24+, qui ont l"avantage de ne pas nécessiter de parenthèse!2+34+624a.
Utilisée sur certaines calculatrices HP par exemple.Exercice?.?.Appliquerlestroisparcoursàl"arbredelafigure?,page?.Étant donné ces parcours, on peut effectuer des traitements sur l"arbre, plutôt que de se contenterd"afficher les valeurs.
On prend l"exemple du calcul de la hauteur et du nombre de noeuds d"un arbrebinaire.Les deux algorithmes sont quasiment identiques.Algorithme 1.5- HauteurEntrée :La racinexd"un arbre binaireASortie :La hauteur deA1Six6=;:2hG Hauteur(filsG(x))3hD Hauteur(filsD(x))4Renvoyer1+max(hG,hD)5Renvoyer1Algorithme 1.6- NombreNoeudsEntrée :La racinexd"un arbre binaireASortie :Le nombre de noeuds dansA1Six6=;:2nG NombreNoeuds(filsG(x))3nD NombreNoeuds(filsD(x))4Renvoyer1+nG+nD5Renvoyer0©Bruno GrenetAlgorithmi quea vancée1.1.
Arbres binaires7Lemme 1.7) Les algorithmesHauteuretNombreNoeudssont corrects, et ont comme com-plexitéO(n), oùnest le nombre de noeuds deA.Exercice?.?.Démontr erlelemmeprécédent.ÉcriredesalgorithmespourtestersiunevaleurapparaîtdansunarbreA,calculerlavaleurminimaleprésentedansl"arbre,compterlenombredefeuillesdel"arbre,On s"intéresse maintenant à un problème un petit peu plus complexe : on souhaite parcourirl"arbreen largeur, c"est-à-dire afficher la racine, puis les noeuds du niveau1(les fils de la racine),puis ceux du niveau2, etc.
Par exemple, on souhaite afficher les noeuds de l"arbre de la figure 1 dansl"ordre6 9 4 4 5 8 2 7 0.Une première méthode consiste à écrire une fonction auxiliaire qui affichetous les noeuds d"un niveau donné, puis de l"appeler sur chaque niveau.Exercice?.?.ModifierParcoursInfixepourqu"ilprenneenentréesupplémentaireunehauteurhetn"affichequelesnoeudsdeniveauhdansl"arbre.E ndéduireunalgorithmequiparcourtl"arbreenlargeur.Analysersacomplexité.L"algorithme de l"exercice précédent n"est pas efficace.
On peut en fait effectuer ce parcours enlargeur en temps linéaire.L"idée pour cela est d"utiliser unefile4pour retenir les noeuds à afficher,dans le bon ordre.Algorithme 1.8- ParcoursLargeurEntrée :La racinexd"un arbre binaireASortie :L"algorithme affiche tous les noeuds deA, niveau par niveau et de gauche à droite1F file vide2Six6=;, l"ajouter àF3Tant queFest non vide :4y défiler un élément deF5Afficherval(y)6SifilsG(y)6=;, l"ajouter àF7SifilsD(y)6=;, l"ajouter àFThéorème 1.
9) L"algorithmeParcoursLargeuraffiche les valeurs de tous les noeuds deAdans l"ordre du parcours en largeur, en tempsO(n)oùnest le nombre de noeuds dansA.Démonstration.La complexité ne pose pas de difficulté, puisque la gestion de la file n"est pas coûteux.De même il est assez clair que tous les noeuds deAsont affichés.
On va démontrer que l"ordre estbien celui du parcours en largeur.Pour cela, il suffit de montrer que les noeuds sont insérés dans lebon ordre dans la file (puisque dans ce cas, le défilement respectera l"ordre).4.
Unefileest une structure de données de type " premier arrivé, premier servi » : quand ondéfileun élément d"une file, onobtient l"élément qui avait été inséré le premier dans la file.Algorithmique avancée©Bruno Grenet81.
Algorithmes classiquesOn démontre, par récurrence sur les niveauxide l"arbre, le résultat suivant : tous les noeuds duniveau(i1)sont insérés dans la file avant ceux du niveaui, et les noeuds du niveauisont insérésde gauche à droite.
Pouri=1, c"est évident puisque la racine, seul noeud de niveau0, est le premiernoeud inséré dansFet que ses deux fils sont insérés dans le bon ordre.
Supposons que c"est le cas aurangi1et soitxun noeud au niveau(i+1), etpson père. Pour quexsoit inséré dansF, il fautquepsoit défilé deF. Or tous les noeuds de niveau(i1)se trouvent avantpdansFpar hypothèsede récurrence. Cela signifie qu"ils sont défilés avantpégalement.En particulier, tous les noeuds deniveauisont donc insérés dansFavant quepsoit défilé, donc avant quexsoit inséré.
Considéronsmaintenant un deuxième noeudyau niveau(i+1), situé à droite dex. Sixetyont le même pèrep,x=filsG(p)ety=filsD(p)doncxest bien inséré dansFavanty. Sinon, le pèrepxdexse situe àgauche du pèrepydey, tous deux au niveaui. Par hypothèse de récurrence,pxse situe avantpydansF, donc est défilé avant. Ainsi,xest inséré avantydansF.Le principe de récurrence permet deconclure.Résumé-Les algorithmes sur les arbres binaires sont en général basés sur les parcoursen profondeur(infixe, préfixe ou suffixe) ouen largeur.-Ces algorithmes de parcours ont une complexitéO(n)oùnest le nombre de noeuds.1.1.
3) A rbresbin airesde rechercheUne utilisation particulière des arbres binaires est la notion d"arbre binaire de recherche.
Onsuppose que les valeurs des noeuds sont des objets comparables entre eux : pour fixer les idées, onconsidère n"avoir que des entiers.Définition 1.10Unarbre binaire de recherche, ou ABR, est un arbre binaire avec la propriétésuivante : pour tout noeudx, tous les noeuds situés dans le sous-arbre gauche dexont unevaleurval(x), et tous ceux situés dans son sous-arbre droit ont une valeurval(x).EL"arbre de la figure 1n"est pasun ABR car par exemple9se situe dans le sous-arbre gauche de6.Dans la figure ci-dessous, l"arbre de gauche est un ABR, mais celui de droite n"en est pas un carle noeud3se situe dans le sous-arbre gauche du noeud5.
On remarque ici qu"être un ABR n"estpas une propriétélocale: il ne suffit pas que chaque noeud ait son fils gauche inférieur et son filsdroit supérieur (propriété respectée dans l"arbre de droite, qui n"est pourtant pas un ABR).258476139265Les ABR servent à maintenir un ensemble de valeurs ordonnées, avec une meilleure complexitéqu"une liste chaînée par exemple.
On commence par la recherche d"un élément.La structure de l"ABRpermet d"éviter de le parcourir en entier.©Bruno GrenetAlgorithmi quea vancée1.1.
Arbres binaires9Algorithme 1.11- RechercheABREntrées :La racinexd"un ABRA, et une valeurvSortie :Un noeud de valeurvdansA, ou;s"il n"en existe pas1Tant quex6=;etval(x)6=v:2Sival(x)>v:x filsG(x)3Sinon :x filsD(x)4RenvoyerxLemme 1.12L"algorithmeRechercheABRest correct, et sa complexité estO(h)oùhest lahauteur de l"ABR.Démonstration.La correction est relativement évidente, en remarquant que la dernière ligne renvoiebien;sivn"apparaît pas dans l"ABR.
Pour la complexité, on note qu"à chaque passage dans la boucle,le niveau du noeud courant augmente de1.
Le nombre de passages est donc borné par la hauteur del"arbre.La deuxième question qu"on peut se poser est l"ajout d"un nouvel élément dans l"ABR.Algorithme 1.13- InsertionABREntrées :La racinexd"un ABRA, et une valeurvSortie :La valeurva été insérée dansA1p ;2Tant quex6=;:3p x4Sival(x)>v:x filsG(x)5Sinon :x filsD(x)6Sip=;: Ajouter un noeud de valeurvcomme racine deA7Sinon siv Sa complexité estO(h)oùhest la hauteur deA.Démonstration.Pour la correction, on note que le nouveau noeud de valeurvse trouve dans le sous-arbre gauche d"un noeudxsi et seulement sival(x)>v. La complexité se démontre de la même façon que pourRechercheABR.Exercice?.?.É crirelesdeuxalgorithmesRechercheABRetInsertionABRsousformerécursive.É crireunalgorithmederechercheduminimumdansunABR,etanalysersacomplexité.Onappellesuccesseurd"unnoeudxdansAunnoeudytelqueval(x)val(y)etpourtoutnoeudz6=x,y,soitAlgorithmique avancée©Bruno Grenet101. Algorithmes classiquesval(z) Intuitivement, un ABR sera efficace s"il estéquilibré, c"est-à-dire de hauteur la plus petite possible.Théorème 1.15SoitAun arbre binaire ànnoeuds et de hauteurh. Alorsh Sini2i, comme chaque noeud du niveauia au plusdeux fils, le nombre de noeuds au niveau(i+1)estni+12ni2i+1.On a doncn=Phi=0ni. Une façon facile de montrer cette dernière égalité est de considérer l"écriturebinaire des entiers :2iest un1suivi deizéros, donc la somme est l"entier constitué deh+1bitségaux à1; c"est bien l"entier2h+11.On en déduit donc queh Parmi celles-ci, une techniqueest simple à mettre en oeuvre : si on insère des éléments dans un ordre aléatoire dans unABR initialement vide, on obtient avec grande probabilité un ABR équilibré. Puisqu"on n"a pastoujours le choix de l"ordre d"insertion, on peut simuler ce comportement avec la notion detarbre, qui combine la notion d"ABR avec celle de tas (autre structure de données basée surles arbres binaires).On peut utiliser les ABR pour effectuer le tri d"un tableau : on insère tous les éléments dutableau dans un ABR initialement vide, puis on supprime itérativement le minimum de l"ABR(jusqu"à obtenir l"ABR vide) pour insérer ces minima successifs dans l"ordre dans le tableau.On peut montrer que cet algorithme est strictement équivalent (en termes de comparaisonseffectuées) à l"algorithme du tri rapide. En particulier, en insérant les éléments du tableaudans l"ABR dans un ordre aléatoire, on obtient un ABR de hauteurO(logn)et l"algorithme a5. Graphes11une complexitéO(nlogn).Résumé-Les ABR sont des arbres binairesordonnés: le sous-arbre gauche d"un noeudxne contientque des valeursval(x)et son sous-arbre droit que des valeursvalx.-Les opérations courantes sur les ABR (recherche, insertion, suppression) ont une complexitéproportionnelle à la hauteurhde l"ABR, qui vérifieblognc h 2) Gra phesCettepartieestdédiéeàl"algorithmiquedesgraphes.Onrappelled"abordquelquesnotionsbasiquessur les graphes, le vocabulaire et les notations utiles. En particulier, les graphes sont classiquement représentés soit par listes d"adjacence, soitpar matrice d"adjacence. Les algorithmes décrits dans cette partie seront exprimés de manière assezgénérique, mais les analyses de complexité prendront en compte ces représentations. On présentedans cette partie les généralisations aux graphes des parcours présentés sur les arbres binaires, ainsique des utilisations assez directes mais importantes de ces parcours : la recherche de plus courtschemins et la détection de cycles.1.2. 1) Ra ppelde v ocabulaireet n otationsUngraphe6est un ensemble desommetsreliés entre eux par desarêtes. Ledegréd"un sommetuest son nombre devoisins, c"est-à-dire le nombre de sommetsvtels qu"il existe une arête entreuetv. Un chemin de longueur`entredeux sommetsuetvest un ensemble de sommetsx0=u,x1, ,x`=vtels qu"il existe une arêteentrexietxi+1pour touti< `. Un chemin estsimplesi tous ses sommets sont distincts (on ne passepas deux fois par le même sommet). Un graphe estconnexesi deux sommets quelconques sont toujours reliés par (au moins) un chemin.ROn peut voir les arbres binaires comme un cas particulier des graphes. Un arbre est binaire si chaque sommet est de degré au plus3.Dans cette vision des arbres binaires, la racine n"est pas spécifiée, et pour un sommet de degré3,on ne distingue pas le père des fils gauche et droit : c"est une présentation non-hiérarchique desarbres binaires.La représentation d"un graphe parlistes d"adjacenceest la donnée, pour chaque sommet, de laliste de ses voisins dans le graphe. Lamatrice d"adjacenced"un graphe ànsommetsf0, ,n1gestune matricenndont le coefficient d"indice(u,v)vaut1s"il y a une arêteuvdans le graphe, et0sinon.6. 2) P arcoursen l argeuret plu sco urtscheminsDe même que pour les arbres binaires, on cherche àparcourirtous les sommets d"un graphe.On commence par présenter leparcours en largeur, qui fait écho au parcours en largeur des arbresbinaires. La seule différence est la nécessité demarquerles sommets visités pour ne pas les visiterdeux fois.Algorithme 1.16- ParcoursLargeurEntrées :Un grapheGet un sommetsdeGSortie :Affiche tous les sommets du grapheG, siGest connexe1F file vide2AjoutersàFet marquers3Tant que la fileFn"est pas vide :4u défilerF5Afficheru6Pour tout voisin non marquévdeu:7AjoutervàFet marquervOn n"a pas défini ce qu"on entend parmarquerun sommet. On utilise dans ce cas un tableau denbooléens initialisés àFaux, etmarquerun sommet consiste à passer sa case àVrai.ESi on appliqueParcoursLargeurau graphe de la figure 2 à partir du sommet0, et en supposantque les voisins d"un sommet sont ajoutés àFdans l"ordre donné par leurs numéros, on obtientles sommets dans l"ordre0 1 2 8 4 5 6 3 7 9.Exercice?.?.AppliquerParcoursLargeuraugraphedelafigure?àpartirdusommet9,etàpartirdusommet5.Théorème 1.17SiGest connexe, l"algorithmeParcoursLargeuraffiche une fois et une seulechaque sommet du graphe, par ordre de distance às. Sa complexité estO(m+n)si le grapheest représenté par listes d"adjacence, etO(n2)s"il est représenté par matrice d"adjacence, oùmest le nombre d"arêtes etnle nombre de sommets.©Bruno GrenetAlgorithmi quea vancée1.2. On montre parrécurrence surdla propriété suivante : tous les sommets deGà distanceddessont insérés dansFau cours de l"algorithme, et les sommets à distanceddessont insérés après ceux à distanced1. Pourd=1, c"est clair car le sommet à distance0, à savoirs, est inséré en premier et ceux à distance1, lesvoisins des, sont insérés ensuite. Puisquexdest à distanceddes, il est inséré dansFparhypothèse de récurrence, doncuest inséré au plus tard quandxdest défilé. Gardons la notationxdpour le sommet à partir duqueluest inséré dansF:xdne peut être qu"un sommet à distanceddes. Le principede récurrence permet de conclure que tous les sommets à distance finie dessont insérés dansFaucours de l"algorithme (donc affichés), et que ceux à distancedsont toujours affichés avant ceux àdistanced+1.Pour la complexité, on remarque que chaque sommet est inséré une fois et une seule dans la file.Donc la boucle Tant que est exécutéenfois. SiGest représenté par matrice d"adjacence, la boucle Pour doit parcourir lesnsommets pour testers"ils sont voisins des. On en déduit la complexitéO(m+n).Exercice?.?.Adapterl"algorithmeParcoursLargeurpourqu"ilcalcule,pourtoutsommetudugraphe,ladistanceentresetu.L"algorithmerenvoieuntableaudetaillencontenantlesdistances.L"exercice précédent montre qu"on est capable, à l"aide du parcours en largeur, de calculer ladistanceentre un sommet donné et tous les sommets du graphe. L"algorithme de Dijkstra généralisecette approche aux graphespondérésdont chaque arête peut avoir une longueur différente. Lalongueur d"un chemin est alors définie comme la somme des longueurs des arêtes qui le compose.Formellement, on se donne unefonction de longueur`sur les arêtes du graphe, qui associe àchaque arête une longueur positive ou nulle :`(u,v) =`(v,u)0pour tous sommetsuetvdugraphe reliés par une arête. L"algorithme utilise unefile de priorité: c"est simplement une structurede données qui permet de représenter un ensemble d"éléments, et d"en extraire rapidement l"élémentdepriorité maximale(cf.la démonstration du théorème suivant pour plus de détails).Algorithme 1.18- DijkstraEntrées :Un grapheG, un sommetsdeGet une fonction de longueur`sur les arêtesSortie :La distance (pondérée par`) entreset chaque sommet deG1F filede prioritévide2D tableau de taillen(nombre de sommets du graphe), initialisé à+13T tableau denbooléens, initialisé àFaux# sommets traités4AjoutersàF5D[s] 0#sest à distance nulle de lui-même6Tant que la fileFn"est pas vide :7. Car chaque arête contribue au degré des deux sommets qu"elle relie.Algorithmique avancée©Bruno Grenet141. Algorithmes classiques7u sommet non traité deFde distanceD[u]minimale8T[u] Vrai9Pour tout voisinvdeu:10SiD[v] = +1: ajoutervà la fileF11SiT[v]estFaux:D[v] min(D[v],D[u]+`(u,v))EOn applique l"algorithme de Dijkstra au graphe suivant, dont les longueurs sont indiqués sur lesarêtes, à partir du sommet0. On affiche la valeur du tableauDau cours de l"algorithme, après letraitement du sommetu(en gras les valeurs modifiées).42301515143362u0 1 2 3 4 5006 11 1 12051121404172110 4 172130 4 1 7 21050 4 1 7 2 10Théorème 1.19SoitGun graphe connexe,sun sommet deGet`une fonction de longueur.L"algorithmeDijkstracalcule les longueurs des plus courts chemins desà chaque sommetdeG. Sa complexité estO((m+n)logn)si le graphe est représenté par listes d"adjacence, etO(n2)s"il est représenté par matrice d"ajacence, oùmest le nombre d"arêtes etnle nombre desommets.Démonstration.La similarité de l"algorithmeDijkstraavecParcoursLargeurpermet de calculerfacilement sa complexité. La différence avecParcoursLargeurest la file de priorité : contrairementà une file standard, l"accès au premier élément ne se fait pas en tempsO(1). L"implantation la plusclassique des files de priorité utilise lestas8et permet d"accéder au sommet de distance minimale entempsO(logn), ce qui conduit à la complexitéO((m+n)logn)pour un graphe représenté par listesd"adjacence. On peut également, à la ligne 7, parcourir tous les sommets deFet garder celui qui ala plus courte distance au sommet initials. Cette stratégie mène à la complexité annoncée pour lamatrice d"adjacence.Pour montrer que l"algorithme est correct, on démontre par récurrence sur le nombre de sommetstraités que pour chaque sommet traitév(i.e.tel queT[v] =Vrai),D[v]contient la distance entresetv. On remarque en premier lieu queD[v]ne peut contenir qu"une valeur supérieure ou égale à cettedistance. Supposons maintenant queksommets ont été traités et que pour chacunD[v]contient la distance entresetv. On considère un plus court chemin entresetx, et onveut montrer qu"à l"étapek+1,D[x]contient la longueur de ce plus court chemin. Puisquesa déjàété traité mais pasx, il existe une arêteyzdans ce chemin telle queya déjà été traité, maiszpasencore. Par hypothèse de récurrence,D[y]contient la distance entresetyet après le traitement dey,D[z]D[y]+`(y,z). Autre structure de données basée sur les arbres binaires, non présentées ici.©Bruno GrenetAlgorithmi quea vancée1.2. D"autre part, le sommetxsélectionné à l"étape(k+1)a la valeurD[x]minimale parmi les sommets à traiter : doncD[x]D[z]D[y]+`(y,z).DoncD[x]est inférieure ou égale à la distance entresetx, et donc égale à cette distance.Exercice?.?.Modifierl"algorithmedeDijkstrapourqu"ilrenvoieenplusdesdistances,unpluscourtchemindesàupourtoutsommetudeG.Pour aller plus loinAvec des files de priorités plus complexes (tas de Fibonacci), on peut atteindre la complexitéO(m+nlogn)pour l"algorithme de Dijkstra, voire encore mieux si on sait que les longueurssont des entiers.On peut également calculer des plus courts chemins avec des longueurs d"arêtes pouvant êtrenégatives, tant qu"il n"existe pas de cycle de longueur totale strictement négative : en effet,dans un tel cas lemeilleurchemin consisterait à répéter un infinité de fois le cycle négatif, pourune longueur totale1. L"algorithme deDijkstradevient alors exponentiel, mais il existeun autre algorithme, dû à Bellman et Ford, de complexité polynomiale. On peut remarquer queDijkstraest un algorithmegloutonpour ce problème, alors que l"algorithme de Bellman-Fordest un algorithme de programmation dynamique pour le même problème (cf.2.1).Résumé-Le parcours en largeur permet de parcourir un graphe, en tempsO(m+n)si le graphe estreprésenté par listes d"adjacence.On peut l"étendre au cas de graphes pondérés grâce à l"algorithme de Dijkstra, de complexitéO(mlogn+n), qui permet de calculer des plus courts chemins dans un graphe.1.2. 3) P arcoursen pro fondeuret cycl esL"équivalent pour les graphes des parcours infixe, préfixe et suffixe est le parcours en profondeur.Contrairement au cas des arbres binaires, il est nécessaire de retenir, à l"instar du parcours en largeur,une liste de sommets à visiter. L"aspect à remarquer est la très forte similarité du prochain algorithmeavecParcoursLargeur: la seule différence est l"utilisation d"unepile(" premier arrivé dernier servi») à la place d"unefile(" premier arrivé premier servi »).Algorithme 1.20- ParcoursProfondeurEntréesUn grapheGet un sommetsdeGSortie :Affiche tous les sommets du grapheG, siGest connexe1P pile vide2AjoutersàPet marquers3Tant que la pilePn"est pas vide :4u dépilerP5Afficheru6Pour tout voisin non marquévdeu:7AjoutervàPet marquervELe parcours en profondeur appliqué sur le graphe de la figure 2 à partir du sommet0produitl"ordre0 8 7 6 9 3 5 4 2 1si on ajoute toujours les sommets dans l"ordre de leurs numéros.Algorithmique avancée©Bruno Grenet161. Algorithmes classiquesExercice?.?.?.Appliquerleparcoursenprofondeuraugraphedelafigure?àpartirdusommet9etàpartirdusommet5.É crireuneversionrécursivedeParcoursProfondeur,sansutiliserdepile.Théorème 1.21SiGest connexe, l"algorithmeParcoursProfondeuraffiche une fois etune seule chaque sommet du graphe. Sa complexité estO(m+n)si le graphe est représentépar listes d"adjacence, etO(n2)s"il est représenté par matrice d"ajacence, oùmest le nombred"arêtes etnle nombre de sommets.La preuve de ce théorème est similaire à celle pourParcoursLargeur, en plus simple car onne garantit rien sur l"ordre des sommets. Le parcours en profondeur peut être utilisé pour détecterla présence d"un cycle dans un graphe (connexe), autrement dit déterminer s"il s"agit ou non d"unarbre. L"idée est de modifier légèrement le parcours en profondeur grâce à la remarque suivante : s"iln"existe pas de cycle, il existe un seul chemin entre le sommet initial et n"importe quel sommet dugraphe; à l"inverse, un cycle assure qu"il existe au moins un sommet qui est atteignable depuis lesommet initial par au moins deux chemins distincts. Au lieu demarquerles sommets visités avec unbooléenVrai/Faux, on les marque avec le numéro de leurprédécesseurdans un chemin depuis lesommet initial. On détecte alors un cycle si un sommet a deux prédécesseurs possibles.Algorithme 1.22- DétectionCycleEntrée :Un graphe connexeGsur lesnsommetsf0, ,n1gSortie :Existe-t-il un cycle dansG?1Pred tableau denentiers, initialisé à1# Prédécesseurs2P pile vide3Pred[0] 04Ajouter0àP5Tant que la pilePn"est pas vide :6u dépilerP7Pour tout voisinvdeu:8SiPred[v] =1:9Pred[v] u10AjoutervàPu.Sinon siv6=Pred[u]:v.RenvoyerVraiw.RenvoyerFauxThéorème 1.23SiGest connexe,DétectionCyclerenvoieVraisi et seulement siGpossèdeun cycle, en tempsO(n)si le graphe est représenté par listes d"adjacence etO(n2)s"il estreprésenté par matrice d"adjacence.Démonstration.On remarque une différence de complexité par rapport au parcours en profondeur.En effet, dans les parcours onvisiteune fois chaque arête. Or on peut montrer facilement qu"un graphe qui possèdenarêtes possède©Bruno GrenetAlgorithmi quea vancée17forcément un cycle : ainsi, au moment où l"algorithme s"arrête, il a visité au plusnarêtes. Cela justifiela complexité dans le cas de listes d"adjacence, mais ne change pas la complexité dans le cas desmatrices d"adjacence.Montrons en premier lieu qu"il y a un cycle dansGsi et seulement s"il existe un sommetv6=0telqu"il existe deux chemins distincts entre0etv. On notexle dernier sommet avantvqu"ils ont en communen partant de0etyle dernier qu"ils ont en commun en partant dev. Alors on a deux chemins entre0etv: ils partagentle même début (entre0ety) puis empruntent le cycle dans les deux directions possibles.0 xy vAinsi, s"il n"existe pas de cycle dansG, tout sommetvn"est atteignable depuis0que par un seulchemin : dans l"exploration du parcours en profondeur,vne peut avoir qu"un seul précédesseur, sesautres voisins ne peuvent être visités qu"en provenant dev. Réciproquement, s"il existe un cycle dansG, on peut considérer un sommetxcomme dans le dessin précédent qui est le premier sommet ducycle à être visité. Depuisx, le parcours en profondeur empile tous les sommets du cycle (disons encommençant par le chemindu bas, en passant paryet en finissant par le chemindu haut). Lorsquele premier sommet du chemin du haut (voisin dex) est dépilé, appelons les,xa déjà été visité maisson prédécesseur n"est pass: le cycle est detecté.Résumé-Le parcours en profondeur permet de parcourir un graphe, en tempsO(m+n)si le grapheest représenté par listes d"adjacence.-On peut l"utiliser pour détecter la présence d"un cycle dans un graphe. On commence par lapro-grammation dynamique, qui est un paradigme algorithmique. À ce titre, c"est la suite logique du courssurdiviser pour régneret lesalgorithmes gloutons. Ensuite, on présente le problème de la recherche demotif dans un texte, et l"un des algorithmes les plus efficaces pour ce problèmes, à savoir l"algorithmede Boyer-Moore.2. 1) Programmati ondyn amiqueLaprogrammation dynamiqueest un paradigme algorithmique, au même titre quediviser pourrégnerou lesalgorithmes gloutons. Pour la présenter, on commence par étudier en détail un problème particulier, le rendude monnaie, avant de dégager les caractéristiques principales et les enjeux de cette méthode. Algorithmes avancésprésente ensuite un deuxième exemple qui utilise la programmation dynamique de manière un peuplus complexe, l"alignement de séquences.2.1. 1) U npremi erexempl e: l erend ude m onnaieLe problème durendu de monnaieconsiste à déterminer le nombre minimal de billets et piècesnécessaires pour rendre une somme donnée. La sortie est soit une liste de pièces, minimale pour atteindre cettesomme, soit simplement le nombre minimal de pièces nécessaires (sans avoir la liste). On le définitformellement.Problème 2.1- RenduDeMonnaieEntrées :EnsemblePd"entiers, entiersSortie 1 :Nombre minimal de pièces dePdont la somme vautsSortie 2 :Liste de pièces deP, minimale, dont la somme vautsELe système des euros avec des pièces à partir de 1 centime et des billets jusqu"à 500€cor-respond à l"entréef50000,20000,10000,5000,2000,1000,500,200,100,50,20,10,5,2,1g. Si ondoit rendre 14€53, la meilleure solution est de rendre les 6 pièces 10€+ 2×2€+ 50 cent. + 2cent. + 1 cent. La sortie 1 est donc6et la sortie 2 est la liste[1000,200,200,50,2,1]dont lasomme vaut bien1453.La majorité des monnaies fiduciaires sontcanoniques, c"est-à-dire que l"algorithme gloutonestoptimal pour rendre la monnaie : on commence par rendre la plus grande pièce inférieure ou égaleà la somme visée, puis on recommence jusqu"à arriver à0. Cependant, on peut facilement créerdes monnaies non canoniques10, commef6,4,1gpar exemple : pour rendre8, l"algorithme gloutonchoisit6, puis deux fois1alors que rendre deux fois4est une meilleure solution. On a donc besoind"un autre algorithme dans le cas général.Exercice?.?.Écrirel"algorithmegloutondurendudemonnaie.§Formule récursiveOn cherche à déterminer, pour un ensemblePde pièces et une sommes,le nombre minimal de pièces dePpour atteindre la sommes. On notepiecesP(s)ce minimum.Pour construire un algorithme, on décrit une formule récursive pour cette valeur. Si on a sélectionnép, il reste la sommesPà rendre : cette somme nécessite par hypothèsepiecesP(sp)pièces. 0sis=0, et1+minfpiecesP(sp):p2P,psgsinon.Decetteformulerécursive,ontireaisémentunalgorithmerécursif.Ilsuffit,pourcalculerpiecesP(s),d"effectuer une boucle qui fait un appel récursif pour chaque pièceps.9. Programmation dynamique19Algorithme 2.2- RenduNaifEntrées :EnsemblePd"entiers, entiersSortie :Nombre minimal de pièces dePdont la somme vauts1Sis=0: renvoyer02n +13Pour chaque piècep2P:4Sips:5np RenduNaif(P,sp)6Sinpn:n np7Renvoyer1+nExercice?.?.Modifierl"algorithmeprécédentpourqu"ilrenvoielalistedespièces,plutôtqueleurnombre.L"algorithme précédent est correct. Mais on ne peut pas vraiment dire qu"il fonctionne Parexemple avec une implantation en Python,RenduNaif(f50,20,10,5,2,1g,30)met environ cinq se-condes à répondre sur un ordinateur standard, et plus d"une minute si on remplace30par35.La raison est le très grand nombre d"appels récursifs. Pour s"en rendre compte, on applique l"algorithme sur un exemple pourtant très simple :RenduNaif(f6,4,1g,6). On remarque en particulierque plusieurs appels récursifs sont effectués sur les mêmes valeurs (s=2par exemple), ce qui estune perte de temps évidente.602510104032106444Figure3 - Les valeurs dessont représentées sur les sommets, et le choix de pièces sur les arêtes(sauf1, qui est omise).§Programmation dynamiquePour régler cette difficulté, une première technique, appeléemémoïsa-tion, consiste à retenir l"ensemble des appels récursifs effectués, pour éviter de les refaire quand c"estinutile. Dans notre exemple, il suffit de se rappeler l"ensemble des valeursspour lesquelles l"appelrécursif a déjà fourni une réponse (ainsi que la réponse). Algorithmes avancésla programmation que de l"algorithmique, et peut s"automatiser jusqu"à une certaine mesure. Les appels àRenduMemoavecles piècesf50,20,10,5,2,1get la somme30ou35prennent maintenant moins d"une milliseconde.Algorithme 2.3- RenduMemoEntrées :EnsemblePd"entiers, entiers, dictionnaireVassociant à des sommessun nombreVsde pièces.On suppose queVcontientV0=0.Sortie :Nombre minimal de pièces dePdont la somme vauts1Sisest dansV: renvoyerVs2n +13Pour chaque piècep2P:4Sips:5np RenduMemo(P,sp,V)6Sinpn:n np7Vs 1+n8Renvoyer1+nL"idée de la programmation dynamique est très proche de la mémoïsation. Mais au lieu d"effectuerdes appels récursifs en partant de la sommesà rendre et de mémoriser les appels récursifs effectués,on calcule explicitement le dictionnaireV, en commençantpar le bas. Mais le code est plus clair, et il ya un petit gain car il n"est pas nécessaire de stocker une pile d"appels récursifs11.Algorithme 2.4- RenduProgdynEntrées :EnsemblePd"entiers, entiersSortie :Nombre minimal de pièces dePdont la somme vauts1L tableau de longueurs+1, initialisé à+12L0 03Pouri=1às:4Pour chaque piècep2P:5SipietLip+1 5) L"algorithmeRenduProgdyncalculepiecesP(s)en tempsO(sjPj)oùjPjdésignele nombre de pièces dansP.Démonstration.La complexité en temps est assez directe : l"algorithme consiste en deux bouclesimbriquées, l"une de tailles, l"autre de taillejPj.11. On peut remarquer queRenduMemo(f50,20,10,5,2,1g,1000000,f0 : 0g)provoque une erreur en Python car tropd"appels récursifs sont effectués.©Bruno GrenetAlgorithmi quea vancée2.1. Programmation dynamique21Pour la correction12, il faut montrer qu"après l"itérationide la boucle,LicontientpiecesP(i):ainsi à la fin de l"algorithme,LscontientpiecesP(s). La démonstration se fait par récurrence suri.Avant la première étape, c"est-à-direà la fin de l"itération0,L0contient0=piecesP(0). Si le résultatest correct jusqu"au rangi1, alors après l"itérationi,Licontient1+minfpiecesP(ip):p2P,pigpuisque la boucle calcule exactement ce minimum. Leprincipe de récurrence suffit à conclure.RLa complexité de cet algorithmen"est paspolynomiale en la taille de l"entrée car la taille desestlog(s)(nombre approximatif de bits nécessaire pour écrire l"entiers). D"autre part, la complexitéen espacede l"algorithme estO(s)car on stocke l"ensemble du tableauL.§ReconstructionLe problème du rendu de monnaie admet deux sorties possibles. On a montrécomment calculer le nombre de pièces minimum, mais pas encore comment calculer la liste despièces. On peut bien sûr adapter les algorithmes précédents pour qu"ils renvoient cette liste de pièce.Mais il y a plus simple, en se basant sur l"algorithme de programmation dynamique. Étant donné letableauLrempli à la fin deRenduProgdyn, on peut calculer cette liste de pièces. Son troisième paramètre est le tableauLrempli dansRenduProgdyn.Algorithme 2.6- RenduReconstructionEntrées :EnsemblePd"entiers, entiers, tableauLd"entiersSortie :Liste de pièces deP, minimale, dont la somme vauts1S liste vide2Tant ques>0:3Pour chaque piècep2P:4SipsetLsp=Ls1:5s sp6AjouterpàS7Sortir de la boucle Pour8RenvoyerSLemme 2. 7) SiLest le tableau rempli parRenduProgdyn(P,s),RenduReconstruction(P,s,L)renvoie une liste de pièces minimales en tempsO(njPj), oùn=piecesP(s).La démonstration de ce lemme, facile, est laissée en exercice.RSi on souhaite calculer la liste de pièces grâce àRenduReconstruction, il faut modifierRenduProgdynpour qu"il renvoie le tableauLplutôt que simplementLs.12. C"est-à-dire la preuve que l"algorithme calcule effectivement ce que l"on souhaite qu"il calcule.Algorithmique avancée©Bruno Grenet222. Algorithmes avancésRésumé-Le rendu de monnaie consiste à rendre une sommesà l"aide d"une liste de piècesP.-Pour les monnaiescanoniques, l"algorithme glouton suffit. Mais pour d"autres monnaies, ilne trouve pas toujours la solution optimale.Pour obtenir une solution optimale quelque soit la monnaie, on décrit uneformule récursivepour le nombre minimal de pièces.L"algorithme obtenu directement depuis cette formule est extrêmement lent. Laprogram-mation dynamique(ainsi que lamémoïsation) permettent d"obtenir un algorithme efficace.-Pour obtenir la liste des pièces, onreconstruitla solutiona posteriori.2.1. 2) L aprogrammati ondyn amique,qu"es aquó?La programmation dynamique est un paradigme algorithmique employé pour résoudre desproblèmes d"optimisation: trouver le plus petit nombre de pièces par exemple, et de manière plusgénérale maximiser ou minimiser une quantité donnée. Développer un algorithme de programmation dynamique repose sur trois ingrédients.1.Obtenir un eformule récursivepour la valeur optimale.On exprime la valeur optimale en fonction desous-problèmes, qui peuvent être nom-breux et non disjoints. Et il fautêtre vigilant au fait que la formule récursive doit se baser sur des solutions d"instancesplus petites du même problème exactement. C"est le coeur de la technique, parfoisdifficile à obtenir.2.Décrire un algorithme itératifpour la valeur optimale.On se base sur la formule récursive. L"algorithme itératif part des plus petits sous-problèmes et calcule la valeur optimale pour des sous-problèmes de taille croissante,jusqu"au problème d"origine. Cette étape nécessite de réfléchir à l"utilisation d"unestructure de données (trèssouvent un tableau) et à la façon de le remplir. Cette étape estrelativement facile lorsqu"on a la formule récursive.3.Reconstruireune solution optimalea posteriori.Les deux premières étapes permettent de calculer la valeur d"une solution optimale.Cette dernière étape, parfois ignorée car inutile, cherche à expliciter une solution quiatteint la valeur optimale. Pour cela, on doit souvent légèrement modifier l"algorithmeitératif de l"étape précédente pour qu"il renvoie un peu plus d"information. Alors que l"algorithme itératif va des instances petites vers les plus grandes,l"algorithme de reconstruction part des instances les plus grandes etredescendversles plus petites.EDans le problème duRenduDeMonnaie, la formule récursive est l"expression depiecesP(s)àpartir depiecesP(sp)pourp2P. Pour lareconstruction, on modifieRenduProgdynpour qu"il renvoie le tableauLet on écrit l"algorithmeindépendantRenduReconstruction.©Bruno GrenetAlgorithmi quea vancée2.1. Programmation dynamique23§Comparaison avec d"autres techniquesLa programmation dynamique utilise une approche ascen-dante pour calculer la valeur optimale, et la formule récursive se base sur de nombreux sous-problèmesnon disjoints. En comparaison, le paradigmediviser pour régnerutilise une approche descendante, etexprime une solution en fonction d"un petit nombre de problèmes disjoints. On peut voir la program-mation dynamique comme une extension des algorithme gloutons : ceux-ci sont souvent insuffisants,c"est-à-dire qu"ils ne fournissent que rarement une solution optimale, et la programmation dynamiquepermet alors dans de nombreux cas de résoudre optimalement le problème.Lamémoïsationest un cousin proche de la programmation dynamique, qui conserve l"approchenaturelle descendante donnée par la formule récursive mais utilise une mémoire supplémentairepour éviter les appels récursifs inutiles. C"est plutôt une technique de programmation, qui peutêtre mise en pratique automatiquement dans des compilateurs, pour améliorer des programmes. Sicette technique est assez simple conceptuellement, elle résulte en des algorithmes moins élégants etsouvent (légèrement) moins efficaces que la programmation dynamique.§La problématique de la mémoireDans leRenduDeMonnaie, on a vu que l"espace mémoirenécessaire estO(s). De manièregénérale en programmation dynamique, la question de l"espace mémoire peut devenir problématique.En particulier lorsqu"on utilise des tableaux multi-dimensionnels (comme dans l"exemple suivant),l"espace mémoire peut devenir leréactif limitantde l"algorithme de programmation dynamique.Dans certains problèmes, il est possible de limiter l"espace mémoire en ne retenant qu"une partiedes données. Par exemple dans le cas du rendu de monnaie, si la pièce la plus grande a pour valeurpmax, on peut ne retenir que lespmaxdernières cases du tableau. On remarque cependant que dans cet exemple,ne retenir qu"une partie du tableauLempêche ensuite la reconstruction. C"est en fait un phénomèneassez général : il est souvent possible de limiter l"utilisation de la mémoire, mais uniquement pourcalculer la valeur optimale et non la solution optimale.RDans le cas de la mémoïsation, la question de la mémoire se pose dans les mêmes termes. Ilest même en général impossible de limiter l"utilisation de la mémoire comme indiqué pour laprogrammation dynamique, ce qui rend cette dernière préférable dans bien des cas.§D"où vient ce nom?Comme déjà indiqué, la programmation dynamique est un paradigmeal-gorithmique. Alors pourquoiprogrammation, et pourquoidynamique? Cette appellation est dueà Bellman (1940) qui effectuait des travaux en optimisation mathématique. Le termeprogram-mationest utilisé dans son sens de planification ou d"ordonnancement de tâches, et renvoie à laprogrammation linéaire. Quant àdynamique, Bellman a déclaré bien des années plus tard dans sonautobiographie (1984) : "it"s impossible to use the word dynamic in a pejorative sense. [ ] Thus,I thought dynamic programming was a good name. Selon lui, il avait besoin d"un tel qualificatif pour que l"armée de l"air américaine, quiétait l"un de ses principaux financeurs, accepte de continuer de le financer malgré le caractère trèsthéorique et mathématique de ses recherches. Cette histoire est très belle, mais peut-être un peu trop,cf.https://en.wikipedia.org/wiki/Dynamic_programming#History.Résumé-La programmation dynamique s"appuie sur trois ingrédients : uneformule récursive, unalgorithme itératif, et un éventuelalgorithme de reconstruction.C"est une approche ascendante, qui étend et améliore dans de nombreux cas l"approcheAlgorithmique avancée©Bruno Grenet242. Algorithmes avancésgloutonne, en exprimant le problème à résoudre en fonction de nombreux sous-problèmesnon disjoints.-Une des problématiques importantes est l"utilisation gourmande de la mémoire.2.1. 3) L "alignementde séqu encesPour mesurer ladistanceentre deux chaînes de caractères (qui peuvent être du texte en languenaturelle, de l"ADN, une séquence de protéines, ), différentes notions dedistancepeuvent êtredéfinies. Par exemple,MANGERetMENTIRsont à distance 3 pour la distance de Hamming (A→E,T→G,E→I).Dans le problème de l"alignement de séquences, on utilise une notion de distance un peu plusévoluée, appeléedistance d"édition, oudistance de Levenshteinou encoredistance d"Ulam. À partirde deux mots, on construit unalignementdes deux mots en insérant desblancs(notés_et qu"onsuppose ne pas apparaître dans les mots d"origine) dans chacun des mots, avec la contrainte que lesmots augmentés de blancs doivent avoir la même longueur. Ladistance d"éditionentre deux motsuetvest définie comme le nombre minimal dedésaccordsdans un alignement deuetv, c"est-à-dire ladistance de Hamming minimale d"un alignement deuetv.EÉtant donné les deux motsPECHEURSetECRITURE, on peut construire l"alignementPECHE_URS_ECRITUREen insérant un blanc dans chacun des deux mots. Dans cet alignement, il y a5désaccords : lePest aligné avec un blanc_, leHavec unR, le (2ème)Eavec unI, le blanc_inséréen hautavec unT, et leSavec unE. On peut vérifier que la distance d"édition est exactement5dans ce cas.Exercice?.?.Calculerladistanced"éditionentreALGORITHMEetPOLYRYTHMIE,ouentreNICHEetCHIEN.Le problème de l"alignement de séquences consiste à calculer un alignement optimal de deuxmotsuetv, ou du moins à calculer la distance d"édition entreuetv.Problème 2.8- AlignementEntrées :Deux motsuetv(de tailles quelconques)Sortie 1 :La distance d"édition entreuetvSortie 2 :Un alignement deuetv, avec le nombre minimal de désaccordsOn peut tenter d"écrire un algorithme directement pour ce problème, mais même l"algorithme deforce brute (tester toutes les possibilités) n"est pas si évident que ça. On va recourir à la programmationdynamique.ROn peut aussi définir la distance d"édition comme le nombre minimal d"opérations élémentairespour passer d"un motuà un motv, où les opérations élémentaires autorisées sont : l"insertiond"une lettre, la suppression d"une lettre, et la substitution d"une lettre par une autre. Par exemple,on retrouve quePECHEURSetECRITUREsont à distance5:PECHEURS→ECHEURS→ECREURS→ECRIURS→ECRITURS→ECRITURE.©Bruno GrenetAlgorithmi quea vancée2.1. Programmation dynamique25L"alignement ou la séquence d"opérations sont tout à fait équivalentes pour définir la distanced"édition : un désaccordL/_correspond à une suppression deL,_/Là une insertion, etL/Màune substitution.§Formule récursiveOn s"intéresse pour l"instant uniquement au calcul de la distance d"édition. Pourdéfinir la formule récursive, on utilise la définition à l"aide de l"alignement, en supposant qu"on aligneprogressivement les deux mots. Pour cela, on noteuilaièmelettre deuetu[0,i[le préfixe deuconstituédes lettres d"indices0ài1, et de même pourv. On note égalementmla longueur deuetncelle dev, de telle sorte queu[0,m[=uetv[0,n[=v.On cherche à aligner deux mots, comme dans l"exemplePECHE_URS/_ECRITURE. Il y a trois cas possibles : c"est soit une insertion (ex._/E), soitune suppression (ex.S/_), soit une substitution (ex.S/E). Dans le premier cas, cela signifie qu"on aalignéuavecv[0,n1[puis un blanc avec la dernière lettre dev. La distance entreuetvest la distance entre les deux préfixes, pluséventuellement1pour la dernière lettre de l"alignement.Notonsedit(i,j)la distance entreu[0,i[etv[0,j[, de telle sorte qu"on chercheedit(m,n). Alors ladiscussion précédente revient à dire queedit(m,n) =min8:edit(m,n1)+1edit(m1,n)+1edit(m1,n1)+1[um16=vn1]où1[um16=vn1]vaut1sium16=vn1et0sinon.ELes alignements possibles des dernières lettres pourPECHEURSetECRITUREsont_/E,S/_ouS/E. Dans le premier cas, on peut alignerPEC_HEURSavec_ECRITUR_(5désaccords), dans ledeuxièmePEC_HEUR_avec_ECRITURE(5désaccord également), et dans le troisièmePEC_HEURavec_ECRITUR(4désaccords seulement). La troisième solution est donc la meilleure, et fournitun alignement dePECHEURSetECRITUREavec5désaccords au total.Le raisonnement précédent est valable quels que soientietj. On peut en déduire la formulerécursive, valable pouri>0etj>0, à laquelle on ajoute des cas de base.Lemme 2. Alorsedit(0,j) =j,edit(i,0) =iet pouri,j>0,edit(i,j) =min8:edit(i,j1)+1edit(i1,j)+1edit(i1,j1)+1[ui16=vj1]9.Démonstration.Par définition,edit(0,j)est le nombre minimal de désaccords dans un alignementdu motu[0,0[, c"est-à-dire le mot vide, avecv[0,j[. Pour le casi,j>0, on va montrerles deux inégalités :edit(i,j)minf getedit(i,j)minf g.Pour la première inégalité, il faut montrer queedit(i,j)est inférieur ou égal à chacune desexpressions du minimum. Pour aligneru[0,i[avecv[0,j[, on peut aligner (optimalement)u[0,i[avecv[0,j1[puis finir par_/vj1: le nombre de désaccords sera par définitionedit(i,j1)+1. Puisqu"ona trouvé un alignement deu[0,i[avecv[0,j[qui aedit(i,j1) +1désaccords, le nombre minimaledit(i,j)de désaccords dans un tel alignement est bienedit(i,j1)+1. Pour cette dernière inégalité, ilfaut effectuer une disjonction de cas selon queui1etvj1sont la même lettre ou non.Pour la seconde inégalité, on effectue le raisonnement inverse et il suffit de montrer queedit(i,j)estsupérieurouégalàl"uneaumoinsdesexpressionsduminimum.Onsupposequ"onaalignéu[0,i[etv[0,j[avecedit(i,j)désaccords. Si l"alignement finit par_/vj1, alors on a un alignement deu[0,i[avecv[0,j1[,qui aedit(i,j)1désaccords. Doncedit(i,j1)edit(i,j)1, c"est-à-direedit(i,j)edit(i,j1)+1.On obtient de même que si l"alignement finit parui1/_, alorsedit(i,j)edit(i1,j)+1et que s"ilfinit parui1/vj1, alorsedit(i,j)edit(i1,j1)+1[ui16=vj1].Les deux inégalités permettent de conclure.Exercice?.?.Calculer,àl"aidedelaformulerécursive,ladistanced"éditionentreETetSEL.§Algorithme itératifComme dans le cas duRenduDeMonnaie, transformer directement la formulerécursive en un algorithme récursif ne fonctionne pas. Les casesE0,jetEi,0sont remplies directement, et les autres sont remplies à l"aidede la formule récursive.EOn peut dessiner le tableauE, en indiquant les lettres des deux mots correspondant à chaqueligne et colonne. AvecPECHEURSetECRITURE, on obtient le tableauE C R I T U R EPECHEURS26666666666640 1 2 3 4 5 6 7 81 1 2 3 4 5 6 7 82 1 2 3 4 5 6 7 73 2 1 2 345 6 74 3 2 2 3 4 5 6 75 4 3 3 3 4 5 6 66 5 4 4 4 4 4 5 67 6 5 4 5 5 5 4 58 7 6 5 5 6 6 5 53777777777775dans lequel on lit (dernière case en bas à droite) que la distance entre ces deux mots est5. Lacase4correspond à la distance entreECRITetPEC, et la valeur est obtenue à partir de la caseà gauche, qui informe que la distance entreECRIetPECest3: on peut donc alignerECRITetPECavec4désaccords, en alignantECRIetPEC, puisTavec_.On aboutit à l"algorithme suivant.©Bruno GrenetAlgorithmi quea vancée2.1. Programmation dynamique27Algorithme 2.10- EditionEntrées :Deux motsuetvSortie :la distance d"édition entreuetv1m taille deu;n taille dev2E tableau bidimensionnel de dimensions(m+1)(n+1)# Cas de base3Pouri=0àm:Ei,0=i4Pourj=0àn:E0,j=j# Formule récursive5Pouri=1àm:6Pourj=1àn:7Ei,j min(Ei,j1+1,Ei1,j+1,Ei1,j1+1[ui16=vj1])8RenvoyerEm,nTh