Aller au contenu principal

TP1 - Diviser Pour Régner

Objectifs
  1. Écrire un programme récursif ;
  2. Étudier la méthode Diviser Pour Régner ;
  3. Comprendre la complexité de la méthode.
Au préalable
  1. Se créer un dossier Terminale NSI sur votre ordinateur ou clé USB
  2. Dans ce dossier, créer un dossier Récursivité

Sur EduPython ou autre instance python, faire :

  1. Créer un nouveau fichier en cliquant sur l'icône 📄, ou en appuyant sur CTRL+N
  2. Enregistrer le fichier sous le nom TP1_DPR en cliquant sur l'icône 💾, ou en appuyant sur CTRL+S
TP

L'ensemble des exercices se fait sur python.

Méthode​

"Diviser Pour Régner" est une méthode de résolution algorithmique d'un problème dit complexe (compliqué à résoudre), consistant à diviser ce problème en un ensemble de plus petits problèmes qui eux seront simples à résoudre.

Ainsi son objectif est de :

  • Diviser le problème en plus petits ;
  • Résoudre individuellement chaque petit problème ;
  • Combiner toutes les solutions pour avoir la réponse au problème initial.

Tri Fusion​

Le tri fusion est une méthode de tri dite optimale, dont l'objectif est de trier une liste donnée avec une complexité temporelle en O( n*log(n) ).
Les tris vus en Première NSI (sélection et insertion) avaient une complexité quadratique (O(n2)).

Problème donné

On souhaite trier la liste :

85261

Problème complexe : on ne peut pas trier une liste "simplement".

Solution
  1. On divise le problème en plusieurs sous-problèmes :
  • il n'est pas possible de trier une liste de n éléments ;
  • on divise la liste en plusieurs petites listes :
8
5
2
6
1

  1. On trouve la solution de chacun des sous-problèmes : on trie chaque sous-liste.
    En divisant, chaque sous-liste obtenue n'a qu'un seul élément, la liste est donc déjà triée.

  2. On combine toutes les sous-solutions pour avoir une solution finale : On rassemble les listes deux à deux, on les fusionne, et on les trie. On réitère jusqu’à avoir la taille de la liste du début :

On a les listes :

8
5
2
6
1

On trie et rassemble les liste 8 et 5, puis 2 et 6, et enfin 1.

Exercices​

Prise en main​

La suite de Fibonacci (encooore)​

On donne la fonction suivante permettant de calculer la suite de Fibonacci :

def fibonacci(n) :
    if n == 0 :
        return 0
    elif n == 1 :
        return 1
    else :
        return fibonacci(n-1) + fibonacci(n-2)
  1. Expliquer pourquoi la suite de Fibonacci répond au problème Diviser pour Régner.
  2. Déterminer l’étape Diviser dans le programme.
  3. Déterminer l’étape Régner dans le programme.
  4. Déterminer l’étape Combiner dans le programme.

Le Juste Prix​

Le Juste Prix est un jeu dans lequel un nombre aléatoire est choisi dans un certain intervalle. L’utilisateur doit le trouver avec un nombre de coût limité. À chaque fois que l’utilisateur rentre un nombre, l’ordinateur lui dit soit "Juste Prix""" s’il écrit le même nombre choisi aléatoirement, "C’est plus" si le nombre aléatoire est supérieur, "C’est moins" s’il est inférieur.

Exemple : le nombre 64 est choisi dans l'intervalle [1;100] :

  • L’utilisateur écrit "50". L’ordinateur dit "C’est plus";
  • L’utilisateur écrit "75". L’ordinateur dit "C’est moins";
  • L’utilisateur écrit "60". L’ordinateur dit "C’est plus";
  • L’utilisateur écrit "65". L’ordinateur dit "C’est moins";
  • L’utilisateur écrit "63". L’ordinateur dit "C’est plus";
  • L’utilisateur écrit "64". L’ordinateur dit "Juste Prix".
  1. Expliquer pourquoi ce jeu répond au problème Diviser pour Régner.
  2. Déterminer l’étape Diviser dans le programme.
  3. Déterminer l’étape Régner dans le programme.
  4. Déterminer l’étape Combiner dans le programme.
  5. Écrire le programme JustePrix(borneInf, borneSup) qui génère un nombre aléatoire compris entre borneInf et borneSup, 2 entiers non nuls. On demandera à l’utilisateur d'écrire un nombre, et le programme indiquera si le nombre saisi est supérieur, inférieur, ou égal à celui généré. On pourra faire un compteur d’essai.

Tri Fusion​

On souhaite écrire une fonction permettant de réaliser un tri fusion, tel qu'il est décrit au début du TP.

2 fonctions seront à écrire :

def fusion(liste1, liste2) :
    '''
    Méthode permettant de fusionner 2 listes en triant les éléments
    @param : liste1 : liste d'entiers, liste2 : liste d'entiers
    @return : liste dont les éléments sont triés
    '''
    pass
def triFusion(liste):
    '''
    Méthode récursive permettant de diviser les éléments les éléments de la liste en paramètre, puis le recombine grâce à la fonction fusion
    @param : liste : liste d'entiers
    @return : liste dont les entiers sont triés
    '''
    pass

Fonction fusion​

Fusion est la fonction qui prend 2 listes triées en paramètre, et permet de les combiner en une seule liste, en respectant un ordre croissant. Cette fonction doit avoir une complexité linéaire.

#Exemple
liste1 = [2,4,9]
liste2 = [3,10]
liste = fusion(liste1,liste2)
#liste contient [2,3,4,9,10]

Écrire la fonction fusion(liste1, liste2), qui renvoie une liste combinant et fusionnant les 2 listes en paramètre, dans l’ordre croissant des éléments.

Fonction triFusion​

TriFusion est la fonction qui prend une liste non triée en paramètre, et se charge de la diviser en plusieurs listes, jusqu’à obtenir n listes à 1 élément.
TriFusion se charge aussi d’appeler la fonction fusion pour recombiner à chaque appel récursif les listes. Elle doit ainsi avoir une complexité logarithmique.

Écrire la fonction triFusion(liste) qui renvoie la liste finale triée grâce au triFusion.

Comparaison de complexité​

On s’intéresse ici à la comparaison des temps d’exécution des différents algorithmes de tri vus en Première et Terminale.

Pré-requis pour l’exercice
  • Vous devez avoir vos fonctions de tri par sélection et insertion de Première. Si "égarées", les chercher sur le web.
  • La fonction de triFusion.
  • Les bibliothèques time et random.
  1. En utilisant la fonction sample de random, créer des listes de 1000, 10000, 100000 éléments.
    Sample

    Sample est une fonction qui permet de générer une liste aléatoire composée de nombres uniques, qui s’écrit comme suit :

    import random
    liste = random.sample(range(a, b), n)

    avec a la borne inférieure, b la borne supérieure, et n le nombre d’éléments.

  2. En utilisant la bibliothèque time, calculer le temps mis pour trier les listes de 1000, 10000 et 100000 éléments avec les tri insertion, sélection et fusion, et dresser un tableau. 
    t1 = time.time()
    #j'effectue mon tri
    t2 = time.time()
    print(t2-t1)
    #je calcule la différence entre mon premier temps, et le second après le tri
  3. On sait que le tri sélection et le tri insertion on une complexité quadratique. Déterminer la complexité du tri fusion.
  4. Expliquer le lien entre la complexité et le temps effectué pour trier.