[PDF] Algorithmique Récursivité





Previous PDF Next PDF



Exemples dalgorithmes récursifs 1 Des exercices sur les suites

Stage d'Algorithmique. Exemples d'algorithmes récursifs. Les programmes sont disponibles dans l'archive associée. Par exemple algo1Rtrous.sce désigne la 



Examen dalgorithmique

30 Jan 2008 (2 points) Proposez un algorithme récursif retournant true si et seulement si l'arbre binaire passé en argument est un Arbre Binaire de ...



Algorithmique Récursivité

1 de 11. Algorithmique. Récursivité. Florent Hivert. Mél : Florent.Hivert@lri.fr. Adresse universelle : http://www.lri.fr/˜hivert 



Algorithmes et programmation II : La récursivité

Algorithmes et programmation II : La récursivité Une fonction récursive est une fonction qui s'appelle elle-même. ... Test factorielle :.



Correction TD 09 : Algorithmes récursifs

Les algorithmes log et somme sont récursifs : chacun contient au moins un appel `a lui même par contre



Corrigé de la Fiche de TD Récursivité Exercice 1

Corrigé de la Fiche de TD Récursivité. Exercice 1 a) Déroulez les procédures récursives suivantes pour k=6 : Procédure test (?k : entier).



Examen dalgorithmique

30 Jan 2008 (2 points) Proposez un algorithme récursif retournant true si et seulement si l'arbre binaire passé en argument est un Arbre Binaire de ...



Examen dalgorithmique

2. Décrire ce que fait l'algorithme P appelé avec le param`etre 22. Exercice 2 : Dérouler un algorithme récursif (4 points).



Algorithmes récursifs - Licence 1 MASS - Introduction

3 May 2013 Algorithmes récursifs. Résolution de probl`emes par récursivité. Objectifs de la séance 11. Ecrire un algorithme récursif avec un seul test.



L3 Math-Info Algorithmique: examen terminal

L3 Math-Info Algorithmique: examen terminal. 17 décembre 2020 Un algorithme faisant 4 appels récursifs sur des instances de taille.





CHAPITRE 1 LA RECURSIVITE

2 LMD Classique Algorithmique et SDD Chapitre 1 : La récursivité CC : GOLEA N H Page 1 CHAPITRE 1 LA RECURSIVITE 1 Introduction : La récursivité est une notion importante de la programmation qui permet de régler des problèmes extrêmement complexes avec seulement quelques lignes



Algorithmes et programmation II : La récursivité

Principe de la récursivité I Décomposer le problème en un problème plus simple)réduire la taille du problème considéré I Pour la récursion sur des entiers : la taille du problème est dé nie par un entier on réduit la valeur de cet entier à chaque appel récursif I Pour la récursion sur les tableaux :



Searches related to examen algorithmique récursivité PDF

UE J1BS7202 : Algorithmique et Programmation Epreuve : Examen Date : Jeudi 19 d ecembre 2013 Heure : 9 heures Dur ee : 2 heures Documents : autoris es Epreuve de M Alain Griffault SUJET + CORRIGE Avertissement {La plupart des questions sont ind ependantes { A chaque question vous pouvez au choix r epondre par un algorithme ou bien par un

Comment définir un algorithme récursif?

Un algorithme est dit récursif lorsqu’il est défini en fonction de lui-même. Dans le cadre de ce cours, nous ne nous intéresserons qu’aux programmes et algorithmes récursifs. Mais la notion de définition récursive est beaucoup plus générale : en mathématiques : définition de l’exponentielle : ? x ? R, f 0 ( x) = f ( x) et f (0) = 1.

Quelle est la seconde règle de conception d’un algorithme récursif?

D’où la seconde règle de conception d’un algorithme récursif : Tout appel récursif doit se faire avec des données plus proches de données satisfaisant les conditions de terminaison. La remarque suivante est assez utile, lorsqu’on souhaite prouver qu’un algorithme récursif s’arrête.

Qu'est-ce que la récursivité ?

CHAPITRE 1 LA RECURSIVITE 1. Introduction : La récursivité est une notion importante de la programmation qui permet de régler des problèmes extrêmement complexes avec seulement quelques lignes. C’est cependant une méthode avec laquelle il est facile de se perdre et d’avoir des résultats imprévisibles ou erronés.

Comment prouver la terminaison d'un algorithme récursif ?

Dans le cas des algorithmes récursifs, ces méthodes sont spécifiques. Pour prouver la terminaison d'un algorithme récursif, la méthode la plus usuelle est la suivante: chacun des ensembles dans lesquels les paramètres prennent leurs valeurs sont équipés d'une relation d'ordre.

1 de 11

Algorithmique

Récursivité

Florent Hivert

Mél :Florent.Hivert@lri.fr

Adresse universelle :http://www.lri.fr/˜hivert

2 de 11

Récursivité et Récurrence

Deux notions très proche :mathématiques : récurrence informatique : récursivité De nombreuses définitions mathématiques sont récursives :Définition (Peano)

0 est un entier naturel.

Tout entierna un successeur uniqueSn(=n+1);Tout entier sauf0est le successeur d"un unique entier;Pour tout énoncéP(n)siP(0)est vrai et si pour toutn,P(n)

impliqueP(Sn)alors l"énoncé8n:P(n)est vrai.

3 de 11

Définition

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

Entrée : un entier positif N

Sortie : factorielle de N

si N = 0 retourner 1 sinon retourner N x Fact(N-1)

4 de 11

Exemple dans un vrai langage de programmation

unsigned int fact(unsigned int N) if (N == 0) return 1; else return N*fact(N-1);

4 de 11

Exemple dans un vrai langage de programmation

unsigned int fact(unsigned int N) if (N == 0) return 1; else return N*fact(N-1);

Ça marche!!!

5 de 11

Comment ça marche?

Appel à fact(4)

. 4*fact(3) = ? . Appel à fact(3) . . 3*fact(2) = ? . . Appel à fact(2) . . . 2*fact(1) = ? . . . Appel à fact(1) . . . . 1*fact(0) = ? . . . . Appel à fact(0) . . . . Retour de la valeur 1 . . . . 1*1 . . . Retour de la valeur 1 . . . 2*1 . . Retour de la valeur 2 . . 3*2 . Retour de la valeur 6 . 4*6

Retour de la valeur 24

6 de 11

Notion de pile d"exécution

Définition (Pile d"exécution)

LaPile d"exécution(call stack) du programme en cours est un emplacement mémoire destiner à mémo riserles pa ramètres,les variables locales ainsi que l"adresse de retour de chaque fonction en cours d"exécution.Elle fonctionne selon le principe LIFO (Last-In-First-Out) : dernier entré premier sorti.

Attention!

La pile à une taille fixée, une mauvaise utilisation de la récursivité peut entraîner un débordement de pile (stack overflow).

6 de 11

Notion de pile d"exécution

Définition (Pile d"exécution)

LaPile d"exécution(call stack) du programme en cours est un emplacement mémoire destiner à mémo riserles pa ramètres,les variables locales ainsi que l"adresse de retour de chaque fonction en cours d"exécution.Elle fonctionne selon le principe LIFO (Last-In-First-Out) : dernier entré premier sorti.Attention!La pile à une taille fixée, une mauvaise utilisation de la récursivité peut entraîner un débordement de pile (stack overflow).

6 de 11

Notion de pile d"exécution

Définition (Pile d"exécution)

LaPile d"exécution(call stack) du programme en cours est un emplacement mémoire destiner à mémo riserles pa ramètres,les variables locales ainsi que l"adresse de retour de chaque fonction en cours d"exécution.Elle fonctionne selon le principe LIFO (Last-In-First-Out) : dernier entré premier sorti.Attention!La pile à une taille fixée, une mauvaise utilisation de la récursivité peut entraîner un débordement de pile (stack overflow).

7 de 11

Point terminal

Retenir

Comme dans le cas d"une boucle, il faut un cas d"arrêt où l"on ne fait pas d"appel récursif.procédure récursive(paramètres): si TEST_D"ARRET: instructions du point d"arrêt sinon instructions récursive(paramètres changés); // appel récursif instructions

8 de 11

Détail d"un appel de fonction

PA =Programme App elant F

=F onctionapp elée1LeP Aréserveet initialise les pa ramètressur la pile 2transfert du contrôle duP AàF avec

enregistrement de l"adresse de retoursur la pile3réservation sur la pile des variables locales deF Retenir

L"ensemble : paramètres + adresse de retour + variables locales

constitue leTableau d"activation (Stack Frame)deF 4exécution du code deF dansson T Ajusqu"à return5désallocation du TA deF dela pile 6retour auP Aàl"adresse enregistrée à l"étap e2, avec

transmission de lavaleur de retourdans le cas échéant

9 de 11

La récursivité terminale

Définition

On dit qu"un fonction est récursive terminale, si tout appel récursif est de la formereturn f(...)Autrement dit, la valeur retournée est directement la valeur obtenue par un appel récursif, sans qu"il n"y ait aucune opération sur cette valeur. Il n"y a ainsi rien à retenir sur la pile.

Entrée : Entiers positifs n, a

Sortie : a*n!

si n == 0 retourner a sinon retourner Algo(n-1,n*a)

9 de 11

La récursivité terminale

Définition

On dit qu"un fonction est récursive terminale, si tout appel récursif est de la formereturn f(...)Autrement dit, la valeur retournée est directement la valeur obtenue par un appel récursif, sans qu"il n"y ait aucune opération sur cette valeur. Il n"y a ainsi rien à retenir sur la pile.Entrée : Entiers positifs n, a

Sortie : a*n!

si n == 0 retourner a sinon retourner Algo(n-1,n*a)

10 de 11

La récursivité terminale (2)

Idée : Il n"y a rien à retenir sur la pile.Retenir Quand une fonction est récursive terminale, on peut transformer l"appel récursif en une boucle, sans utilisation de mémoire supplémentaire.Attention!cette optimisation n"est pas supp ortéepa rtous les compilateurs et est optionnelle (ex :-O3avecgcc). si n == 0 retourner a sinon retourner Algo(n-1,n*a)

Devient :

Tant que n <> 0:

a <- n*a; n <- n-1 retourner a

10 de 11

La récursivité terminale (2)

Idée : Il n"y a rien à retenir sur la pile.Retenir Quand une fonction est récursive terminale, on peut transformer l"appel récursif en une boucle, sans utilisation de mémoire supplémentaire.Attention!cette optimisation n"est pas supp ortéepa rtous les compilateurs et est optionnelle (ex :-O3avecgcc). si n == 0 retourner a sinon retourner Algo(n-1,n*a)

Devient :

Tant que n <> 0:

a <- n*a; n <- n-1 retourner a

11 de 11

La récursivité terminale (3)

L"optimisation peut se faire appel par appel.Retenir Quand une appel est récursive terminal, on peut le transformer en un saut, sans utilisation de mémoire supplémentaire.Exemple : le tri rapide tri_rapide(tableau T, entier premier, entier dernier) si premier < dernier alors pivot := choix_pivot(T, premier, dernier) pivot := partitionner(T, premier, dernier, pivot) tri_rapide(T, premier, pivot-1) // Non terminal tri_rapide(T, pivot+1, dernier) // terminalquotesdbs_dbs11.pdfusesText_17
[PDF] examen algorithmique avancée corrigé

[PDF] qcm biologie animale l1

[PDF] sujet dexamen de biologie animale

[PDF] qcm biologie animale s2

[PDF] examen biologie animale l1

[PDF] mécanique quantique solutions des examens corrigés

[PDF] examen corrige de mecanique quantique s5

[PDF] examen pharmacologie générale

[PDF] exercices corrigés de pharmacologie générale

[PDF] qcm pharmacologie generale corrigé

[PDF] exercice pharmacologie infirmier

[PDF] qcm pharmacologie speciale pdf

[PDF] exercices corrigés de pharmacologie générale pdf

[PDF] exercice+pharmacocinétique+correction

[PDF] exercice corrigé estimateur sans biais