Fonctions récursives

Question 1

Quels sont les Algorithmes de type diviser pour régner? (3)

Answer 1

• Tri fusion
• Tri rapide
• Algorithme de sélection

Question 2

Quels sont les Analyse asymptotique des fonctions récursives? (3)

Answer 2

• Méthode itérative
• Méthode de l’arbre de récursivité
• Méthode générale

Question 3

Quelle est la particularité d’une fonction récursive?

Answer 3

Fonction dont le calcul nécessite d’invoquer la

fonction elle-même

Question 4

Quelles sont les deux parties de tout processus recursif?

Answer 4

1) Une formule simple (cas de base, règle de sortie) exécutable sans récursivité
donnant généralement une borne inférieure où le processus récursif s’arrête
(ex: 0! = 1).
2) Une méthode générale qui réduit un cas particulier en un ou plusieurs cas plus
petit, ramenant progessivement par réduction vers le cas de base (ex: n * (n - 1)! ).

Question 5

Que doit être posé pour effectuer l’analyse asymptotique d’une fonction récursive?

Answer 5

équation de récurrence

Question 6

Q’effectue la Méthode par itération? et nomme des exemples classiques

Answer 6

Effectue l’expansion de l’équation de récurrence afin
de la résoudre.
Méthode de l’arbre de récursivité
Nombre de Fibonacci
la tour de Hanoi

Question 7

voici le résumé du problème de la tour de hanoi
Transporter les anneaux empilés en ordre croissant de la tour d’origine (1) vers la tour de destination (3) en utilisant la tour intermédiaire (2)
seule règle: En aucun cas, un anneau ne peut être empilé sur un anneau de dimension
inférieure.

Solution???

Answer 7

• S’attaquer au plus difficile en premier soit déplacer l’anneau 64 (le + grand)
• L’anneau 64 doit nécessairement passer directement de la tour 1 à la tour 3.
• Faire le même processus pour les 63 autres anneaux récursivement
• Prévoir une règle d’arrêt des appels récursifs.

Question 8

Décrit l’algorithme de la tour de hanoi en étape ou avec arbre

Answer 8

DéplacerAnneau(anneau,tourDépart,tourArrivée,tourTemp)

1. si anneau > 0
2. DéplacerAnneau(anneau-1,tourDépart,tourTemp,tourArrivée)
3. Effectuer le déplacement tourDépart vers tourArrivée
4. DéplacerAnneau(anneau-1,tourTemp,tourArrivée,tourDépart)

voir dia 15 pour arbre

Question 9

Pour le problème de la tour de hanoi qu’elle est l’équation du nombre de déplacement

Answer 9

2n(exp)-1

Question 10

Algorithmes de type « diviser pour régner » a combien d’étapes et qu’elles sont-elles? avec exemple

Answer 10

– Diviser le problème en sous-problèmes indépendants.
– Conquérir en résolvant récursivement chacun des sousproblèmes.
– Combiner les solutions des sous-problèmes pour obtenir la
solution au problème original.
Exemples:
– Recherche dichotomique (binaire)
– Tri rapide
– Trouver les points les plus rapprochés

Question 11

quel est le principe de l’algorithme tri par fusion?

Answer 11

– Diviser
Sépare la liste à trier en deux listes de longueurs égales.
– Conquérir
Appel récursif sur les deux sous-listes.
– Combiner
fusionne les deux sous-listes triées pour obtenir une
seule liste triée.

Question 12

La méthode générale donne une recette pour résoudre les récurrences de la forme, quels sont les paramètres de cette recette .

Answer 12

–a ) ≥ 1 et b, > 1 constantes
– F (n) une fonction asymptotiquement positive

Récurrence de type “diviser pour régner”

Question 13

Voir pour la méthode générale les dia 23 à 28

Answer 13

Fait un des exercices de dia 27

Question 14

la plupart des données réelles ne sont pas

entièrement aléatoires, pourquoi?

Answer 14

• Il y a des séquences qui sont déjà triés
• D’autres sont en ordre décroissant
• Il est possible de prendre avantage de ces
caractéristiques pour améliorer l’algorithme

Question 15

Comment voir le Tri fusion naturel

Answer 15

• Trouver les séquences en ordre croissant
• Trouver les séquences en ordre strictement
décroissant
• Inverser les séquences avec un algorithme linéaire
• Fusionner les différentes séquences trouvées

Question 16

Trimsort!! Pour faire quoi??

Answer 16

Lors de la fusion, il arrive que tous les éléments d’un
tableau doivent se trouver du même côté. l’algorithme va le détecter et copier le bloc
entier

Question 17

Optimisations au tri fusion naturel comment faire

Answer 17

L’algorithme de fusion est plus efficace quand les deux
sections sont de la même grandeur
• Des « runs » de longueurs minimales vont être utilisés
• Longueur optimale:
• Entre 32 et 64
• Choisi de tel sorte que N/longueur soit une puissance de 2
• Un tri par insertion binaire est utilisé pour agrandir les
« runs » naturels
• Les « runs » sont ensuites fusionner de manière
« intelligente »

Question 18

Décrit le Tri rapide (Quicksort)

Answer 18

Diviser
Divise un tableau T[1..N] en deux sections
Régner
Trier les deux sections par des appels récursifs à
TriRapide.
– Combinaison
Les sous-tableaux sont triés en place, donc aucune
mémoire de travail est requis.

ex voir dia 36 a 39

Question 19

Décrit les Meilleur et pire cas de partition pour Tri rapide (Quicksort)

Answer 19

Meilleur cas de partition
Se produit lorsque l’algorithme produit deux
sous-tableaux de mêmes dimensions (n/2)
Pire cas de partition
Se produit lorsque l’algorithme produit un
sous-tableau de n-1 élément et un autre vide
(tableau déjà trié)

Question 20

Comment améliorer le Tri rapide (Quicksort)

Answer 20

Choix du pivot
– Utiliser un algorithme aléatoire
– Utiliser la moyenne
Lorsque le nombre d’élément à trier devient plus
petit qu’une certaine constante (exemple: 10),
utiliser un autre algorithme comme le tri par
insertion.

Question 21

Déterminer le kième plus petit élément d’un
tableau non-trié.
Exemple:
- Trouver la médiane (k = N/2)
- Trouver le max (k=N)

Answer 21

soit:
Principe de l’algorithme de partition
- Le pivot T[q] est au bon endroit dans le tableau
- Les éléments à gauche de T[q] sont plus petits
- Les éléments à droite sont plus grands

l’algorithme explore toutes les possibilités
• Lorsque l’algorithme se retrouve dans un cul-de-sac, il
revient en arrière et explore une nouvelle solution

voir dia 42 a 46 pour solution

Question 22

Placer 8 dames sur un échiquier de 8x8 de telle sorte
qu’elles ne puissent s’attaquer entres-elles, selon les règles du jeu d’échecs.
fait l’algorithme de ce problème

Answer 22

AjouterReine()

1. pour chaque position non gardé p sur le plateau
2. placer la reine à la position p
3. nombreReine = nombreReine + 1
4. si nombreReine == 8
5. Imprimer le plateau
6. sinon
7. AjouterReine()
8. Enlever la reine à la position p
9. nombreReine = nombreReine – 1

Question 23

Analyse de l’algorithme du problème des 8 dames.

Answer 23

Nombre d’arrangements possible à calculer si on
procède par la méthode empirique = 4,426,165,368 possibilités
Par observation, on note qu’il ne peut y avoir
seulement qu’une dame par rangée, ce qui réduit
le nombre de possibilité à = 16,777,216 possibilités
On peut encore réduire ce nombre du fait que les
positions en prise (colonnes et diagonales) sont
aussi éliminées.
La seule spécification qu’il ne peut y avoir
qu’une dame par colonne réduit le nombre de
possibilités à 8! = 40 320 possibilités

Question 24

Que peut-on constater de la récursivité? (3)

Answer 24

La récursivité peut toujours être remplacée par
l’itération;
Vice versa l’itération peut toujours être remplacée
par la récursivité;
Si le programme sous construction manipule des
données à l’aide d’une pile, toujours se demander
si l’utilisation de la récursivité ne produira pas un
programme plus compréhensible et naturel du côté
formulation.