Diviser Pour Régner

L’objectif de ce document est d’écrire et d’implémenter un algorithme s’appuyant sur le raisonnement « Diviser pour régner » qui permet de déterminer la somme des $n$ nombres (entiers) d’un tableau.

1. Écrire le code de fonction somme1 dont la spécification est :

1
2
3
4
5
6
7

def somme1(tab: List[float]) -> float:
    """
    Calcul de la somme des nombres éléments
    de tab.

    Algorithme : Récursivité enveloppée
    """

Penser à écrire un jeu de tests.

Dans quel cas ?

• On parvient à découper un problème en sous-problèmes indépendants les uns des autres. On poursuit cette démarche jusqu’à aboutir à une situation simple : cas de base.
• La solution du cas de base est généralement simple à obtenir et permet la construction de la solution du problème.

Remarque

C’est l’indépendance des sous-problèmes qui permet la construction de la solution globale directe par recombinaison des solutions intermédiaires.

Principe

Indépendance des sous-problèmes

L’objectif de ce document est d’écrire et d’implémenter un algorithme s’appuyant sur le raisonnement « Diviser pour régner » qui permet de déterminer le maximum et le minimum des éléments dans un tableau.

1. Générer une liste contenant un million de termes choisis aléatoirement entre un et mille milliards.

1
2
3
4

from random import randint

if __name__ == "__main__":
    tab = [randint(1, int(1e12)) for i in range(int(1e6))]

2. Utiliser les fonctions min et max fournies par le langage Python afin d’afficher les maximum et minimum dans la liste.

1
2
3
4

    print("Fonctions Python")
    val_min, val_max = (min(tab), max(tab))

    print("min = {}, max = {}".format(val_min, val_max))

3. Écrire le code de la fonction maxmin1 qui, à partir d’un algorithme de « brute force », détermine les maximum et minimum dans la liste passée en argument. La spécification de la fonction est :

1
2
3
4
5
6

def maxmin1(tab: List[float]) -> Tuple[float, float]:
    """
    Recherche du minimum et du maximum dans le tableau tab.

    Paradigme « Brute force »
    """

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

def maxmin1(tab: List[float]) -> Tuple[float, float]:
    """
    Recherche du minimum et du maximum dans le tableau tab.

    Paradigme « Brute force »
    """
    val_max = tab[0]
    val_min = tab[0]

    for elt in tab:
        if elt > val_max:
            val_max = elt
        if elt < val_min:
            val_min = elt

    return (val_min, val_max)

4. Vérifier le bon fonctionnement de la fonction maxmin1 en affichant les maximum et minimum dans la liste, à la suite de ceux déterminés à l’aide des fonctions fournies par Python.

1
2
3

    print("Recherche « Brute Force »")
    val_min, val_max = maxmin1(tab)
    print("min = {}, max = {}".format(val_min, val_max))

5. Quelle est la complexité de la fonction maxmin1 ?

L’objectif de cette activité est l’écriture d’une fonction qui effectue la rotation d’une image bitmap de 90 degrés en utilisant le principe « Diviser pour régner ».

On peut manipuler des images en Python à l’aide du module PIL (Python Image Library). Une première partie de l’activité est consacrée à la prise en main de ce module. Dans un second temps, la fonction de manipulation des bits est développée.

Images numériques

Définition

Le tri fusion d’un tableau

Description du tri

Dans cette partie, nous allons essayer de comprendre les principes sur lesquels s’appuie ce tri. Son implémentation, pour des tableaux ou des listes chaînées, sera développée dans les prochaines sections.

Le tri fusion s’appuie sur la méthode Diviser pour régner pour trier les $n$ éléments d’une séquence $S$ :

1. Diviser : Si la séquence $S$ est composée de 0 ou un élément, retourner $S$ immédiatement ; cette séquence est déjà triée. Si la séquence $S$ est composée de plus de deux éléments, la diviser en deux sous-séquences $S_1$ et $S_2$ contenant chacune environ la moitié des éléments de $S$ ; donc $S_1$ est formée des $\left\lfloor \dfrac{n}{2} \right\rfloor$ premiers éléments de $S$ contient les $\left\lceil \dfrac{n}{2} \right\rceil$ derniers éléments de $S$.

2. Régner : Trier récursivement $S_1$ et $S_2$.

3. Combiner : Reformer la séquence $S$ en combinant, dans l’ordre, les éléments des séquences triées $S_1$ et $S_2$.