Chapitre 2 Exemples dalgorithmes itératifs et récursifs
Algorithme 1: Euclide forme récursive. Entrée: Deux entiers relatifs : a
Algorithmique et programmation avancée
définition par récurrence 3) Récursivité et itération. Tout algorithme récursif peut être ... Choisir entre itératif et récursif. Version récursive.
LIFAP2 : ALGORITHMIQUE ET PROGRAMMATION RECURSIVE
Algorithme itératif / récursif L'exécution d'un algorithme ne doit pas impliquer ... comparaison entre le premier élément de la liste (ici 3).
Algorithmique Trier et Trouver
Entrée : un tableau tab de taille taille et un élément e. Algorithme (RechDichoIt recherche dichotomique itérative) ... différence et différence.
Algorithmique Récursivité
On appelle récursive toute fonction ou procédure qui s'appelle elle même. Algorithme Fact. Entrée : un entier positif N. Sortie : factorielle de N si N = 0
Trois algorithmes de calcul des nombres de Fibonacci
Exercice 1 (Algorithme récursif) Soit l'algorithme suivant : si n = 0 ou n = 1 alors Exercice 2 (Algorithme itératif) Soit l'algorithme suivant :.
livre-algorithmes EXo7.pdf
Arithmétique – Algorithmes récursifs . ci-dessus) avec par définition tan?i = 10?i. ... Écrire une version itérative de l'algorithme d'Euclide.
Algorithmes récursifs: une introduction pragmatique pour un
27 oct. 2019 retourner fact. Algorithme 1 : FactorielleItérative : calcule itérativement la valeur de n!. Essayons-nous à la même démarche avec l'équation (2) ...
Algorithmique & programmation en langage C - vol.1 - Archive
1 févr. 2019 COMPARAISON ITÉRATIF/RÉCURSIF . ... d'ores et déjà d'établir l'indépendance entre un algorithme et sa mise en œuvre c'est à dire.
Première partie : Algorithmique avancée pour les graphes
Algorithme 5 : Parcours en profondeur récursif d'un graphe La différence entre les trois algorithmes réside dans la stratégie utilisée pour décider de ...
[PDF] LIFAP2 : ALGORITHMIQUE ET PROGRAMMATION RECURSIVE
Algorithme itératif / récursif Langage commun entre la machine et nous : comparaison entre le premier élément de la liste (ici 3) et min (ici -2)
[PDF] Spécificités des algorithmes itératifs et récursifs - CNRS
4 oct 2022 · Complexité des algorithmes itératifs : – Utilisation des règles révisées dans les slides 103 et 104 • Complexité des algorithmes récursifs
[PDF] Chapitre 2 Exemples dalgorithmes itératifs et récursifs
Algorithme 1: Euclide forme récursive Entrée: Deux entiers relatifs : a b; Sortie: Un entier pgcd de a et b; Fonction PGCD(a b);
[PDF] Algorithmique et programmation avancée
Tout algorithme récursif peut être transformé en un algorithme itératif équivalent : c'est la dérécursivation La méthode à suivre dépend du type de récursivité
[PDF] Algorithmique Récursivité
Moyen simple et élégant de résoudre certain problème Définition On appelle récursive toute fonction ou procédure qui s'appelle elle même Algorithme Fact
[PDF] cours 2:Complexité des algorithmes récursifs - Esentn
Algorithmes récursifs Définition La récursivité est le fait pour une méthode de s'appeler elle même On parle alors de méthode récursive
[PDF] Récursivité
3 fév 2020 · Une procédure (ou une fonction) est dite récursive si elle contient au moins un énoncé d'appel direct ou non à elle-même dans son corps
Différence entre récursivité et itération - WayToLearnX
14 juil 2018 · La principale différence entre récursion et itération est que la récursivité est un processus toujours appliqué à une fonction
[PDF] ALGORITHMIQUE II
Un algorithme (ou fonction) est dit récursif s'il est défini en fonction de lui-même ? Exemples ? Fonction puissance(x : réel n : entier) : réel
[PDF] Récursivité - LACL
- ´Ecrire deux fonctions C l'une utilisant un algorithme itératif l'autre un algorithme récursif permettant de calculer l'entier naturel n étant donné en
Quelle est la différence entre un programme itératif et un programme récursif ?
Un programme est dit récursif lorsqu'une entité s'appelle elle-même. Un programme est appelé itératif lorsqu'il y a une boucle (ou répétition).Comment transformer un algorithme récursif en itératif ?
Tout algorithme récursif peut être transformé en un algorithme itératif équivalent : c'est la dérécursivation. La méthode à suivre dépend du type de récursivité de l'algorithme. Un algorithme est dit récursif terminal s'il ne contient aucun traitement après un appel récursif.Quand Dit-on qu'un algorithme est récursif ?
L'algorithme est récursif parce qu'il s'invoque lui-même. En effet, pour construire toutes les permutations de belle Marquise -- vos beaux yeux -- me font mourir -- d'amour, il faut construire toutes les permutations de vos beaux yeux -- me font mourir -- d'amour.- En informatique et en mathématiques, le terme fonction récursive ou fonction calculable désigne la classe de fonctions dont les valeurs peuvent être calculées à partir de leurs paramètres par un processus mécanique fini.
Algorithme itératif / récursifProgrammation impérative / fonctionnelleLIFAP2 : ALGORITHMIQUE ET PROGRAMMATION RECURSIVE
QU'EST-CEQU'UNALGORITHME?¢On souhaite résoudre le problème :Trouver le minimum d'une liste de nombres : par exemple (3 6,5 12 -2 0 7)¢Expliquer à une machine comment trouver le minimum de n'importe quelle liste de nombres¢Langage commun entre la machine et nous : SchemeN. Guin -M. LefevreLicence Lyon1 -UE LIFAP22
DÉFINITIOND'UNALGORITHME¢Un algorithme est une méthodeSuffisamment générale pour pouvoir traiter toute une classe de problèmesCombinant des opérations suffisamment simples pour être effectuées par une machineN. Guin -M. LefevreLicence Lyon1 -UE LIFAP23
COMPLEXITÉ D'UN ALGORITHME¢Il faut :que la machine trouve le plus vite possible¢Complexité en tempsqu'elle trouve en utilisant aussi peu de place mémoire que possible¢Complexité en espaceN. Guin -M. LefevreLicence Lyon1 -UE LIFAP24
RAPPEL: LAMACHINEN'ESTPASINTELLIGENTE¢L'exécution d'un algorithme ne doit pas impliquer des décisions subjectives, ni faire appel à l'utilisation de l'intuition ou de la créativité¢Exemple : une recette de cuisine n'est pas un algorithme si elle contient des notions vagues comme "ajouter du sel»N. Guin -M. LefevreLicence Lyon1 -UE LIFAP25
MONPREMIERALGORITHME¢Déterminer le minimum d'une liste de nombres par exemple (3 6,5 12 -2 0 7)N. Guin -M. LefevreLicence Lyon1 -UE LIFAP26
MÉTHODEITÉRATIVE¢Je parcours la liste de gauche à droite, en retenant à chaque pas le minimum provisoire(3 6,5 12 -2 0 7)Entre 3 et 6,5, c'est 3Entre 3et 12, c'est 3Entre 3et -2, c'est -2Entre -2et 0, c'est -2etc.N. Guin -M. LefevreLicence Lyon1 -UE LIFAP27
8DEQUOIAI-JEBESOINPOURÉCRIREL'ALGORITHME? (1)¢La séquenceDébutInstruction(s)Fin¢L'affectationVariable ¬Expression¢A ¬2¢BX4 ¬A+2*racine(15)Licence Lyon1 -UE LIFAP2N. Guin -M. Lefevre
9DEQUOIAI-JEBESOINPOURÉCRIREL'ALGORITHME? (2)¢La conditionnelle (1)SiCondition AlorsInstruction(s)FinSi¢Exemple :Si(A > 27) AlorsB ¬A*3FinSiLicence Lyon1 -UE LIFAP2N. Guin -M. Lefevre
10DEQUOIAI-JEBESOINPOURÉCRIREL'ALGORITHME? (3)¢La conditionnelle (2)SiCondition AlorsInstruction(s)SinonInstruction(s)FinSiLicence Lyon1 -UE LIFAP2N. Guin -M. Lefevre¢Exemple :Si((A<10) et(B > racine(A*5))) AlorsB ¬A*3A ¬A+BSinonA ¬A+2B ¬A*BFinSi
11DEQUOIAI-JEBESOINPOURÉCRIREL'ALGORITHME? (4)La conditionest :•soit une condition élémentaire•soit une condition complexe, c'est à dire une conjonction, disjonction, ou négation de conditions élémentaires et/ou complexesLicence Lyon1 -UE LIFAP2N. Guin -M. Lefevre
12DEQUOIAI-JEBESOINPOURÉCRIREL'ALGORITHME? (5)¢L'itérative, ou boucleTantQueCondition FaireInstruction(s)FinTantQue¢Exemple :TantQuei<10 Fairea¬a*ii¬i+1FinTantQueLicence Lyon1 -UE LIFAP2N. Guin -M. Lefevre
13OPÉRATEURSBOOLÉENS¢Pour écrire une conjonction, disjonction, ou négation de conditions, on a besoin des opérateurs booléens ET, OU, NON¢Une variable booléenneest une variable dont les valeurs peuvent être vrai oufaux¢Un opérateur booléen est un opérateur dont les arguments sont des variables booléennes et dont le résultat est booléenLicence Lyon1 -UE LIFAP2N. Guin -M. Lefevre
14L'OPÉRATEURETXYX ETYVraiVraiVraiVraiFauxFauxFauxVraiFauxFauxFauxFauxLicence Lyon1 -UE LIFAP2N. Guin -M. Lefevre
15L'OPÉRATEUROUXYX OUYVraiVraiVraiVraiFauxVraiFauxVraiVraiFauxFauxFauxLicence Lyon1 -UE LIFAP2N. Guin -M. Lefevre
16L'OPÉRATEURNONXNONXVraiFauxFauxVraiN. Guin -M. LefevreLicence Lyon1 -UE LIFAP2
ALGORITHMEITÉRATIF¢Soient L : la listepremier, longueur, ièmeet écrire: des primitives (i.e. algorithmes déjà définis)N. Guin -M. LefevreLicence Lyon1 -UE LIFAP217Définition de minimum(L)Débutmin ¬premier(L)i ¬2TantQuei <= longueur(L) FaireSiième(L,i) < min Alorsmin ¬ième(L,i)FinSii ¬i+1FinTantQueÉcrire("Le minimum est»)Écrire(min)Fin
N. Guin -M. LefevreLicence Lyon1 -UE LIFAP218VOCABULAIRE¢minimumet écriresont des procédures, i.e. modifient l'environnement¢premier, longueuret ièmesont des fonctions, i.e. retournent une valeur, mais ne modifient pas l'environnement¢L est le paramètrede la procédure minimum¢i est l'indiceou le compteurde la boucle
COMPLEXITÉ EN TEMPS DE L'ALGORITHME ITÉRATIF DU MINIMUMDéfinition de minimum(L)Débutmin¬premier(L)i ¬2TantQuei <= longueur(L) FaireSiième(L,i) < min Alorsmin ¬ième(L,i)FinSii ¬i+1FinTantQueÉcrire("Le minimum est»)Écrire(min)FinN. Guin -M. LefevreLicence Lyon1 -UE LIFAP219Soit n la longueur de la liste L1 affectation (initialisation)1 affectation (initialisation)n comparaisonsn-1 comparaisonsm affectationsn-1 affectation (incrémentation)1 écriture1 écriture
LE NOMBRE m DÉPEND DE LA LISTE¢Meilleur cas : m=0 si le premier nombre de la liste est le minimum¢Pire cas : m=n-1 si les nombres de la liste sont rangés en ordre décroissant¢Cas moyen : m=1+1/2+...+1/n (de l'ordre de ln n)s'ils respectent une distribution parfaitement aléatoireN. Guin -M. LefevreLicence Lyon1 -UE LIFAP220
COMPLEXITÉ EN ESPACE DE L'ALGORITHME¢Une variable minpour stocker leminimum provisoire¢Une variable ipour savoir où on en est dans la listeN. Guin -M. LefevreLicence Lyon1 -UE LIFAP221
MÉTHODERÉCURSIVE(1)¢Pour trouver le minimum de la liste (3 6,5 12 -2 0 7)¢On suppose le problème résolu pour la liste privée de son premier élément i.e. (6,5 12 -2 0 7)¢Soit minle minimum de cette sous-liste, ici -2¢Le minimum de la liste complète s'obtient par comparaison entre le premier élément de la liste (ici 3) et min(ici -2)N. Guin -M. LefevreLicence Lyon1 -UE LIFAP222
MÉTHODERÉCURSIVE(2)¢Comment résout-on le problème pour la sous-liste ? ØEn faisant le même raisonnement. ¢C'est la récursivité.¢Quand s'arrête-t-on ? ØQuand on ne peut plus parler de sous-liste, i.e. quand la liste a un seul élément. C'est alors le minimum.N. Guin -M. LefevreLicence Lyon1 -UE LIFAP223
ILLUSTRATIONDELAMÉTHODEN. Guin -M. Lefevre24Licence Lyon1 -UE LIFAP2(6,5 12 -2 0 7)Enlever le premier élémentComparer -2 et 3(3 6,5 12 -2 0 7)-2minimumSur quoi faire l'appelrécursif ?Comment passerdu résultat de l'appel récursif au résultat qu'on cherche ?-2minimumappelrécursif
ALGORITHMERÉCURSIF¢Soient vide?, resteet premierdes fonctions primitivesN. Guin -M. LefevreLicence Lyon1 -UE LIFAP225Définition de la fonction minimum (L)Sivide?(reste(L)) Alorsretournepremier(L)SinonSipremier(L) < minimum(reste(L)) Alorsretournepremier(L)Sinonretourneminimum(reste(L))FinSiFinSi
REMARQUES¢minimumest ici une fonction, le mot retournepermet de dire quel est son résultat¢minimumest l'appel récursif¢En programmation fonctionnelle, on n'a plus besoin de la séquence¢En programmation récursive, on n'a plus besoin de la boucleN. Guin -M. LefevreLicence Lyon1 -UE LIFAP226
ILLUSTRATIONDEL'ALGORITHMEN. Guin -M. LefevreLicence Lyon1 -UE LIFAP227(3 6,5 12 -2 0 7)(6,5 12 -2 0 7)(12 -2 0 7)(-2 0 7)(0 7)(7)36,512-2 07appel récursifpremier élémentminimumappel récursifappel récursifappel récursifappel récursifpremier élémentpremier élémentpremier élémentpremier élément0-2 -2 -2 -2
COMPLEXITÉ EN TEMPS DE L'ALGORITHME RÉCURSIF DU MINIMUMDéfinition de la fonction minimum(L)Sivide?(reste(L)) Alorsretournepremier(L)SinonSipremier(L) < minimum(reste(L)) Alorsretournepremier(L)Sinonretourneminimum(reste(L))FinSiFinSiN. Guin -M. LefevreLicence Lyon1 -UE LIFAP2281 test1 comparaison+ le nombre de comparaisons de l'appel récursif
COMPLEXITÉ EN TEMPS DE L'ALGORITHME (2)¢Si n est la longueur de la liste¢Si C(i) est le nombre de comparaisons de l'algorithme pour une liste de longueur i¢Alors C(n)= 1+C(n-1)= 1+1+C(n-2)= ...= 1+1+...+C(1)= 1+1+...+0= n-1N. Guin -M. LefevreLicence Lyon1 -UE LIFAP229
RÉSUMÉ SUR LA COMPLEXITÉ¢Choisir ce que l'on va compterunité de comparaison des algorithmespar exemple le nombre de comparaisons¢Ce qui importe est l'ordre de grandeur de la complexitéconstant, log n, linéaire, n*log n, n2, 2n¢En LIFAP2 on s'intéressera essentiellement au nombre de fois où l'on parcourt une structure de donnée (liste, arbre)N. Guin -M. LefevreLicence Lyon1 -UE LIFAP230
POURÉCRIREUNALGORITHMERÉCURSIF¢Il faut choisir1.Sur quoi on fait l'appel récursif2.Comment on passe du résultat de l'appel récursif au résultat que l'on cherche3.Le cas d'arrêtØDANS CET ORDRE LÀ !!!N. Guin -M. LefevreLicence Lyon1 -UE LIFAP231
STRUCTURETYPED'UNEFONCTIONRÉCURSIVESije suis dans le cas d'arrêtAlorsvoila le résultatSinonle résultat est le résultat de l'application d'une fonction sur le résultat de l'appel récursifN. Guin -M. LefevreLicence Lyon1 -UE LIFAP232
LESBUGS¢Mon algorithme est faux car son résultat n'est pas défini si la liste est vide ou si elle contient autre chose que des nombres ¢Pour éviter les bugs il faut :Définir le problème aussi bien que possibleC'est la spécificationTenter de prouver que son programme répond à la spécificationPasser des jeux d'essai, aussi divers et tordus que possibleN. Guin -M. LefevreLicence Lyon1 -UE LIFAP233
POURRÉSUMERN. Guin -M. LefevreLIFAP1 : ProgrammationLIFAP2 : ProgrammationImpérativeItérativeFonctionnelleRécursiveSéquence(faire les choses l'une après l'autre)Boucle(répéter)Appliquer une fonction à des arguments pour obtenir un résultatComposer les fonctions pour enchaîner les traitementsLa répétition est assurée par l'enchaînement des appels récursifsLe test de la boucle est remplacé par le cas d'arrêtLangage CLangage Scheme34Licence Lyon1 -UE LIFAP234
DÉBUTSENSCHEMEÉvaluer une expressionDéfinir une fonctionNOTIONDEFONCTION¢Une fonction a des paramètres et retourne un résultat¢Paramètres et résultat peuvent être de n'importe quel type:NombreBooléenCaractèreChaîne de caractèresListeFonctionN. Guin -M. LefevreLicence Lyon1 -UE LIFAP236
ÉCRITUREDEL'APPELÀUNEFONCTION(1)¢Syntaxe :Parenthèse ouvranteNom de la fonctionEspacePremier argumentEspaceDeuxième argumentEtc.Parenthèse fermanteN. Guin -M. LefevreLicence Lyon1 -UE LIFAP237(NomFctArg1 Arg2 ... Argn)
ÉCRITUREDEL'APPELÀUNEFONCTION(2)¢Sémantique : il faut donner à la fonction le bon nombre d'arguments, et du bon type¢Exemples :(+ 5 13) retourne 18(-10 b) retourne la différence si b a une valeur numérique, une erreur sinon(+ (* 2 5) (-3 1)) retourne 12(* 5) n'est pas correct(/ 5 "a") non plusN. Guin -M. LefevreLicence Lyon1 -UE LIFAP238
ÉVALUATIONDEL'APPELÀUNEFONCTION¢Lorsqu'on lui fournit un appel de fonction, SchemeÉvalue chacun des argumentsRegarde s'il connaît la fonction, sinon affiche un message d'erreurApplique la fonction aux résultats de l'évaluation des argumentsAffiche le résultat¢C'est un processus récursifN. Guin -M. LefevreLicence Lyon1 -UE LIFAP239
EXEMPLESD'ERREURS¢(1 + 2) ®erreur : 1 n'est pas une fonction¢(toto (1 2 3)) ®erreur : 1 n'est pas une fonction¢Dans certains cas particuliers, les arguments ne sont pas évalués avant l'application de la fonction. On parle alors de forme spéciale plutôt que de fonctionN. Guin -M. LefevreLicence Lyon1 -UE LIFAP240
LESVARIABLES¢Dans le langage Scheme, une variable se nomme symbole¢L'affectation revient à attribuer une valeur à un symbole. On utilise pour cela la forme spéciale define¢Exemples :(definea 5)(defineb 2)(+ a b) ®7N. Guin -M. LefevreLicence Lyon1 -UE LIFAP241
LAFORMESPÉCIALEQUOTE¢La forme spéciale quotepermet d'empêcher l'évaluation¢Exemples :(definea 5)a ®5(quotea) ®a(quote(+ 1 2)) ®(+ 1 2)'(+ 1 2) ®(+ 1 2)N. Guin -M. LefevreLicence Lyon1 -UE LIFAP242
LAFORMESPÉCIALEEVAL¢À l'inverse de quote, evalforce l'évaluation¢Exemples :(eval'(+ 3 2)) ®5(definetoto 5)(definetata toto)tata ®5(definetiti 'toto)titi ®toto(evaltiti) ®5N. Guin -M. Lefevre43Licence Lyon1 -UE LIFAP25toto5tata5tototototiti
DÉFINITIOND'UNEFONCTION¢Syntaxe :(definefonction(lambdaliste-des-paramètresinstructions))¢Exemple :(defineplus-1(lambda (x)(+ x 1)))¢Test : (plus-1 3) ®4N. Guin -M. LefevreLicence Lyon1 -UE LIFAP244
SPÉCIFICATIOND'UNEFONCTION; description de ce que fait la fonction(definefonction ; ®type du résultat(lambda liste-des-paramètres ; type des paramètresinstructions))Exemple :; ajoute 1 à un nombre(defineplus-1 ; ®un nombre(lambda (x) ; x un nombre(+ x 1)))N. Guin -M. LefevreLicence Lyon1 -UE LIFAP245
L'ALTERNATIVE¢L'alternative est définie en Schemepar la forme spéciale if¢Syntaxe :(ifcondition valeur-si-vraivaleur-si-faux)¢Exemples :(if (> 3 2) 'yes'no) ®yes(if (> 2 3) 'yes'no) ®no(if (> 3 2) (-3 2) (+ 3 2)) ®1N. Guin -M. LefevreLicence Lyon1 -UE LIFAP246
QUELQUESFONCTIONSPRÉDÉFINIES(1)¢Opérateurs arithmétiques :+, -, *, /, sqrt, min, max, abs, ...(sqrt9) ®3(min 5 2 1 3) ®1¢Opérateurs booléens : not, or, and(not #t) ®#f(and (> 3 2) (> 2 5)) ®#f(or (> 3 2) (> 2 5)) ®#tN. Guin -M. LefevreLicence Lyon1 -UE LIFAP247
QUELQUESFONCTIONSPRÉDÉFINIES(2)¢Opérateurs de comparaison :=, <, >, <=, >= pour les nombresequal?pour tout y compris les listes¢Pour tester le type d'un objet :boolean?, number?, symbol?, string?¢modulo: reste de la division entière(modulo 12 5) ®2 (modulo 5 12) ®5N. Guin -M. LefevreLicence Lyon1 -UE LIFAP248
MAPREMIÈREFONCTIONRÉCURSIVE: CHOIXDELAMÉTHODE¢On veut écrire une fonction qui étant donné un entier n calcule n!N. Guin -M. LefevreLicence Lyon1 -UE LIFAP249n-1-1´nnn!factorielleSur quoi faire l'appel récursif ?Comment passer du résultat de l'appel récursif au résultat qu'on cherche ?(n-1)!factorielleappel récursif
MAPREMIÈREFONCTIONRÉCURSIVE: ÉCRITURE(definefactorielle; ®entier positif(lambda (n) ; n entier positif(if (= n 0)1(* n (factorielle(-n 1))))))N. Guin -M. Lefevre50Licence Lyon1 -UE LIFAP2Cas d'arrêt : 0! = 1 Récursivité : n! = 1 x 2 x 3 x ... x n = n x (n-1)! pour n>0
UNEAUTREFONCTIONRÉCURSIVE: CHOIXDELAMÉTHODE¢On veut écrire une fonction qui étant donné un nombre x et un entier positif n calcule xnN. Guin -M. LefevreLicence Lyon1 -UE LIFAP251x,n-1-1 sur n´xx,nxnpuissanceSur quoi faire l'appel récursif ?Comment passer du résultat de l'appel récursif au résultat qu'on cherche ?xn-1puissanceappel récursif
UNEAUTREFONCTIONRÉCURSIVE: ÉCRITURE(definepuissance; ®nombre(lambda (x n) ; x nombre, n entier positif(if (= n 0)1(* x (puissancex (-n 1))))))N. Guin -M. Lefevre52Licence Lyon1 -UE LIFAP2Cas d'arrêt : x0= 1 Récursivité : xn= xx xx ... x x= xx x(n-1)
quotesdbs_dbs44.pdfusesText_44[PDF] fonction récursive
[PDF] automobile in corsa
[PDF] pélican volant de marey (1882)
[PDF] dynamisme d'un cycliste
[PDF] le futurisme mouvement artistique
[PDF] futurisme caractéristiques
[PDF] futurisme définition
[PDF] l5a les clans majeurs pdf
[PDF] l5a pdf
[PDF] l5a 4eme edition pdf
[PDF] pendule élastique vertical
[PDF] l5a 4eme edition pdf download
[PDF] pendule elastique definition
[PDF] l5a 4 edition pdf