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 ET PROGRAMMATION

Next PDF List

Page 1Algorithmique AvancéeProblèmes RécursifsIUT Nancy CharlemagneA. IMINEPage 2Présentation‡Enseignant :M.

Abdessamad IMINEBureau : 140email : Abdessamad.Imine@univ-lorraine.fr‡Progression du module :Cours, TD et TP‡Examens :Un partiel (fin octobre)Un projet à rendrePage 3Introduction‡Une procédure est dite récursive si, et seulement si, elle faitappel à elle-même, soit directement soit indirectement‡La récursivité est une technique de résolution de problèmeutilisée en informatique.problèmes complexes : on réduit le problème initial à unproblème similaire mais de taille plus petite.‡Elle permet de trouver des solutions élégantes et claires àcertains problèmesPage 4Exemple-(vision itérative)- (vision récursive)GH OMXPHXU O í 1Page 5Exemple (suite)Version itérative :fonction monter_escalier( h : entier )débutpour i de 1 à h fairemonter_marche()fpourfinVersion récursive :fonction monter_escalier( h : entier )débutsi h>0alors monter_marche()monter_escalier(h-1)fsifinPage 6Exemple (suite)Récursivité en actionmonter_escalier( 3 )monter_marche();monter_escalier( 2 );monter_marche();monter_marche();monter_escalier( 1 );monter_marche();monter_marche();monter_marche();appels à monter_marche()Page 7‡ Tout algorithme récursif comporte une instruction (ou un blocappelsrécursifs et qui porte sur les paramètres.‡ Pour tout problème récursif, il faut :‡ définir une formule de récurrence.fonction monter_escalier( h : entier )débutsi h>0alors monter_marche()monter_escalier(h-1)fsifinPage 8Recette de récursivitéou plusieurs sous-problèmes de même nature‡,GHQWLILHUOHcas de base (ou cas trivial) qui est le plus petitproblème qui ne se décompose pas en sous-problèmes‡5pVRXGUH3‡VL3HVWXQFDVGHEDVHOHUpVRXGUHGLUHFWHPHQW‡VLQRQ‡GpFRPSRVHU3HQVRXV-problèmes P1, P2,‡UpVRXGUHUpFXUVLYHPHQW33‡FRPELQHUOHVUpVXOWDWVREWHQXVSRXU33"pour obtenir la solution pour avoir la solution auproblème de départ.Page 9Algorithme généralfonction F_récursive (paramètres)débutinstructions résolvant directement les cas particulierssinoninstructionsappel(s) récursif(s) à F_récursive(paramètres modifiés)instructionsfsifinPage 10Consignes‡ Il faut noter que les paramètres passés à la fonction récursiverécursifs ne se termineront jamais.

Ils sont généralementExemple : fonction monter_escalier( h : entier )débutsi h>0alors monter_marche()monter_escalier(h-1)fsifinPage 11des types de problèmes à résoudre et des solutions proposées :‡ les problèmes définis par récurrence‡ les recherches avec retour arrière‡ les techniques de découpage du type " diviser pour régner »Nous étudierons des exemples dans chacune de ces classes.Page 1Algorithmique AvancéeAlgorithmes de recherche avecretour arrière(Techniques de Backtracking)IUT Nancy CharlemagneA.

IMINEPage 2Exemple illustratifbits.

Chercher tous les vecteurs dont la somme des" 1 » est supérieure ou égale à 2.‡Le seul moyen pour résoudre ce problème est devérifier toutes les possibilités :(000, 001, 010, ,111).‡Il y a huit (08) possibilités (espace de recherche).Page 3Exemple illustratif (suite)0 0 _0 0 0 0 0 10 1 _0 1 0 0 1 11 _ _ 0 _ _1 0 _1 0 0 1 0 11 1 _1 1 0 1 1 1Page 4Recherche avec retour arrière : principe‡Faire des choix et prendre des décisions puis deimpasse‡Revenir légèrement en arrière sur des décisionsprises afin de sortir d'un blocage‡Idée : essayer chaque possibilité (combinaison)jusqu'à trouver la bonnePage 5Recherche avec retour arrière : principe‡Pendant la recherche, si on essaie une alternativequi ne satisfait plus une contrainte, on effectue unretour arrière à un point où d'autres alternativess'offraient à nous, et on essaie la possibilitésuivante.

Si on n'a plus de tels points la rechercheéchoue.‡Le point fort du " backtracking » est que beaucoupde ses réalisations évitent d'essayer un maximumde combinaisons partielles, diminuant ainsi le tempsd'exécution.Page 6Trouver une seule solution pour un problème donnéefonction UHFKHUFKHU6ROXWLRQ"ERROpHQdébutsi solution complète alorsinfructueux Å fauxsinoninfructueux Å vraiinitialiser la sélection des candidatsrépétersi acceptable alors (* Le candidat satisfait certaines conditions *)enregistrer (* Le candidat est enregistré.

Construction partielle de la solution *)infructueux Å UHFKHUFKHU6ROXWLRQ"si infructueux alorseffacer enregistrementfsifsifsiretourne infructueuxfinPage 7Trouver toutes les solutions pour un problème donnéefonction UHFKHUFKHU6ROXWLRQ"débutsi solution complète alorsimprimer la solutionsinoninitialiser la sélection des candidatspour chaque candidatsi acceptable alorsenregistrerUHFKHUFKHU6ROXWLRQ"effacer enregistrementfsifpourfsifinPage 8Recherche de chemins dans un graphe avec circuitsExemple de grapheUn graphe est un ensemble de et de relations (ouDUFVHQWUHFHVQ°XGV/HJUDSKHGRQQpHQH[HPSOHDSRXUQ°XGVa, b, c,d, e, f, g, h et i/HQ°XGGpEXWGXJUDSKHHVWaHWOHQ°XGILQ.

Un chemincommence en a, se termine en f et ne passe jamais 2 fois par le mêmeQ°XGLes chemins du graphe donné en exemple sont les suivants :a b c d e f, a b c i d e f, a c d e f, a c i d e f.Page 9Recherche de chemins dans un graphe avec circuitsRechercher tous les chemins dans un graphe avec circuitsMéthode de résolution1.

2) QFRQVWUXLWOHVFKHPLQVXQjXQQ°XGSDUQ°XG2.

6) LjXQLQVWDQWGRQQpRQVHWURXYHDXQ°XG quiFKRLVLVVDQWXQGHVQ°XGVVXFFHVVHXUVGH3./HQ°XGFKRLVLQHGRLWSDVGpMjDSSDUWHQLUDXFKHPLQ6Len question le choix de Îretour arrière).rechercherChemin(début_chemin, extrémité, arrivée, graphe)Page 10Algorithme informelsuivant : rechercherChemin(a, a, f, graphe)Page 11Première possibilité :/HJUDSKHHVWUHSUpVHQWpSDUXQHWDEOHGRQWOHVFOpVVRQWOHVFRXSOHVGHQ°XGVHWles valeurs vrai ou faux :&Op ^LMLMVRQWGHVQ°XGV`HW9DOHXU ^YUDLIDX[`$XQFRXSOHGHQ°XGLMJUDSKHDVVRFLHYUDLVLRQSHXWDOOHUGXQ°XGLDXQ°XGMLe graphe exemple peut être schématisé de la manière suivante :Page 12Deuxième possibilité :/HJUDSKHHVWUHSUpVHQWpSDUXQHWDEOHGRQWOHVFOpVVRQWOHVQ°XGVHWOHVYDOHXUVGHVOLVWHVGHQ°XGV&Op ^1°XG`HW9DOHXU ^OLVWH1°XG`$FKDTXHQ°XGJUDSKHDVVRFLHODOLVWHGHVHVVXFFHVVHXUVPage 13Complexité des algorithmesAlgorithmique Avancée2ème Année DUT Informatique1Complexité des Algorithmes‡Plusieurs algorithmes peuvent exister pour résoudreun même problème.‡Quel algorithme choisir? Quel est le plus efficace?évaluer les ressources utilisées :- temps,- mémoire,- nombre de processeurs,- etc.2terme de tempsLa complexité temporelle est la plus importanteindépendante de la machine,du langage de programmation,du programmeur,3Objectif :proposer des méthodes qui permettent d'estimer le coût d'unalgorithme, de comparer deux algorithmes différents (sans avoir à lesprogrammer effectivement)déterminer une fonction associant un coût en unité de temps à unparamètre entier n qui résume la taille des données.Exemples :- recherche d'un élément dans un tableau : n est la taille du tableau,- tri d'une liste : n est la taille de la liste,4Différents types de complexitéLa complexité dans le pire des cas :AE la plus utiliséeLa complexité en moyenne :AE difficile à calculer en généralLa complexité dans le meilleur des cas :AE très peu utilisée5Exemple 1Algorithme:x Å x + 3*jCoût total de cet algorithme (ou sa complexité) :c x n = c.n6pour j de 1 à n fairex Å x + 3*jfpourcn foisExemple 2Algorithme:Coût total de cet algorithme (ou sa complexité) :n x c1 + n x n x c2 = c2 . n2 + c1.n7pour j de 1 à n fairex Å j * 2fpourpour i de 1 à n fairepour j de 1 à n fairex Å x + i*x+jfpourfpourc1n foisc2n foisn foisOrdre de grandeurest négligeable sur le coût final lorsque n est grand.Î la complexité est indépendante de la machine.- Le monôme ayant la puissance la plus élevée est le plusimportant.

8) Exemple 1Algorithme:x Å x + 3*jCoût total de cet algorithme (ou sa complexité) :c x n = c.nCet algorithme a une complexité en O(n)9pour j de 1 à n fairex Å x + 3*jfpourcn foisExemple 2Algorithme:Coût total de cet algorithme (ou sa complexité) :n x c1 + n x n x c2 = c2 . n2 + c1.nCet algorithme a une complexité en O(n²) 10pour j de 1 à n fairex Å j * 2fpourpour i de 1 à n fairepour j de 1 à n fairex Å x + i*x+jfpourfpourc1n foisc2n foisn foisOrdre de grandeurPropriétés : (pour n suffisamment grand)- Si a < b , alors un algorithme qui est en O(nb) a une complexité plusimportante quun algorithme en O(na)- Les algorithmes ayant une complexité en log n sont plus rapides que lesalgorithmes ayant une complexité en n ( > 0 ).- Les algorithmes ayant une complexité en nk (pour tout k>0) sont plusrapides que les algorithmes ayant une complexité en cn (pour c > 0)11Complexité de A : n² - 12n +60 O(n²)Complexité de B : 11n O(n)Ordre de grandeurncoût12Exemples de croissance de fonctionscoûtLinéaire O(n)Quadratique : O(n²)Polynomial : O(np)n13Les principales classes de complexitéComplexité logarithmique : coût en O(log2 n)- recherche dichotomique dans un tableau trié t[1 n].Complexité linéaire : coût en O(n)- factorielle nComplexité quasi-linéaire : coût en O(n log n)- tri par fusion, tri rapideComplexité polynomiale : coût en O(np) , p > 1- p = 2, tri par sélectionComplexité exponentielle : coût en O(an) avec a > 1- tours de Hanoï14Importance des ordres de grandeurs15algorithme 1 2 3 4 5Coût en temps(micro sec.)33 n 46 n lg n 13 n2 3.4 n3 2nTaille des données Temps de résolution10 0.00033 sec 0.0015 sec 0.0013 sec 0.0034 sec 0.001 sec100 0.003 sec 0.03 sec 0.13 sec 3.4 sec 4 .1016 années1000 0.033 sec 0.45 sec 13 sec 0.94 heures10 000 0.33 sec 6.1 sec 22 min 39 jours100 000 3.3 sec 1.3 min 1.5 jours 108 annéesImportance des ordres de grandeursCray-1TRS-80Si un algorithme a une complexité importante, même si on16Importance des ordres de grandeurs17Taille des données Cray-1 TRS-80n 3 n3 nanosecondes 19 500 000 n nanosecondes10 3 microsecondes 0.2 secondes100 3 millisecondes 2 secondes1000 3 secondes 20 secondes2 500 50 secondes 50 secondes10 000 49 minutes 3.2 minutes1 000 000 95 années 5.4 heures2 ordinateurs des années 1977, Cray 1 plus rapide que TRS-80Factoriellefonction calculerFactorielle ( n : entier ) : entierdébutsi n = 0 alors factorielle 1sinon factorielle n * calculerFactorielle ( n-1 )fsiretourne factoriellefinC1 est le coût de la multiplication18Factoriellefonction calculerFactorielle ( n : entier ) : entierdébutsi n = 0 alors factorielle 1sinon factorielle n * calculerFactorielle ( n-1 )fsiretourne factoriellefinCC(n) = 1 + C(n-1) (1 est le coûtde la multiplication)C(n) = 1 + C(n-1) = 2+C(n-2) = 3 + C(n-3) = . . . = n + C(0) = nDonc la complexité de factorielle est en O(n) (linéaire)19Tours de Hanoïfonction hanoï (n : entier, d : chaine, a : chaine, i : chaine)débutsi n 0 alorshanoï (n -1, d, i, a )écrire (" déplacer le disque », n , " de », d, " vers », a)hanoï (n -1, i, a, d )fsifinC = 1C(n-1)C(n-1)20Tours de Hanoïfonction hanoï (n : entier, d : chaine, a : chaine, i : chaine)débutsi n 0 alorshanoï (n -1, d, i, a )écrire (" déplacer le disque », n , " de », d, " vers », a)hanoï (n -1, i, a, d )fsifinC = 1C(n-1)C(n-1)C(0) = 0C(n) = 1 + 2 x C( n -1)Par récurrence, C(n) = 2n 1C(n) = O(2n) (exponentiel)21Recherche dichotomiqueAlgorithmefonction rechercheDicho (tab : Tab, borne_inf : entier, borne_sup : entier, élément : Elément) : entierdébutsi borne_inf = borne_sup alorssi tab[borne_inf] = élément alorsindice borne_infsinonindice -1fsisinonmilieu (borne_inf + borne_sup) 2si élément tab[milieu] alorsindice rechercheDicho (tab, borne_inf, milieu, élément)sinonindice rechercheDicho (tab, milieu + 1, borne_sup, élément)fsifsiretourne indicefinTraitement non récursifCoût = 1Appels récursifsCoût = 122Recherche dichotomiqueAlgorithmefonction rechercheDicho (tab : Tab, borne_inf : entier, borne_sup : entier, élément : Elément) : entierdébutsi borne_inf = borne_sup alorssi tab[borne_inf] = élément alorsindice borne_infsinonindice -1fsisinonmilieu (borne_inf + borne_sup) 2si élément tab[milieu] alorsindice rechercheDicho (tab, borne_inf, milieu, élément)sinonindice rechercheDicho (tab, milieu + 1, borne_sup, élément)fsifsiretourne indicefinTraitement non récursifCoût = 1Appels récursifsC(n) = C(n 2) + 1 pour n > 1C(1) = 1Coût = 123nn/2 n/2n/4 n/4 n/4 n/41 1 1 1 1 1 1 1 1 1lg nncoût du traitement non récursifTaille initiale des données24