Aller au contenu principal
Physique, Chimie et Informatique > Terminales Spé. NSI

Méthode « Diviser pour régner »

Au programme

Contenus Capacités attendues Commentaires
- Méthode « diviser pour régner ». Écrire un algorithme utilisant la méthode « diviser pour régner ». - La rotation d’une image bitmap d’un quart de tour avec un coût en mémoire constant est un bon exemple.
- L’exemple du tri fusion permet également d’exploiter la récursivité et d’exhiber un algorithme de coût en nlog⁡2nn \log_2 n dans les pires des cas.

Documents

18 nov. 2020

Sous-sections de Méthode « Diviser pour régner »

Physique, Chimie et Informatique > Terminales Spé. NSI > Méthode « Diviser pour régner »

Diviser pour régner

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.

Exemples

  • Exponentiation rapide
  • Recherche dichotomique dans un tableau trié, dans une liste triée
  • Tri rapide d’un tableau
  • Tri fusion récursif d’un tableau
  • etc.

Schéma de résolution

À retenir
Diviser
On décompose le problème initial en un ou plusieurs sous-problèmes de plus petites tailles.
Régner
Chaque sous-problème est résolu
Combiner
Les solutions des sous-problèmes sont combinées pour construire la solution du problème initial.

Remarques

  • Cette procédure se prête naturellement à un traitement récursif des problèmes mais une approche itérative reste possible.
  • Cette procédure assure que l’algorithme est correct. Il reste à valider sa terminaison (que le cas de base est toujours atteint ).

Exercice : exponentiation rapide

L’algorithme suivant permet de calculer ana^n :

an={1if n=0a×an−1if n>0a^n = \begin{cases} 1 &\text{if } n=0 \\ a \times a^{n-1} &\text{if } n>0 \end{cases}
  1. Programmer la fonction puissance1 dont la spécification est :
def puissance1(a: int, n: int) -> int:
    """
    Calcul de a^n.
    """

Penser à écrire quelques tests.

Réponse
def puissance1(a: int, n: int) -> int:
    """
    Calcul de a^n.
    Implémentation de l'algorithme 1.
    """
    if n == 0:
        return 1
    else:
        return a * puissance1(a, n - 1)


if __name__ == "__main__":
    assert puissance1(3, 2) == 9
    assert puissance1(5, 0) == 1
    assert puissance1(2, 8) == 256

    print("Done!")
  1. Quelle est la complexité de cet algorithme ?
Réponse

Le calcul nécessite nn appels récursifs et n+1n+1 multiplications. La complexité est donc en O(n)O(n).

L’algorithme suivant permet aussi de calculer ana^n :

an={1if n=0(ak)2if n=2k (n est pair)a×(ak)2if n=2k+1 (n est impair)a^n = \begin{cases} 1 &\text{if } n=0 \\ ( a^k )^2 &\text{if } n = 2k \text{ (n est pair)} \\ a \times ( a^k )^2 &\text{if } n = 2k + 1 \text{ (n est impair)} \end{cases}
  1. Programmer la fonction puissance2 dont la spécification est :
def puissance2(a: int, n: int) -> int:
    """
    Calcul de a^n.
    Implémentation de l'algorithme 2.
    """

Penser à écrire quelques tests.

Réponse
def puissance2(a: int, n: int) -> int:
    """
    Calcul de a^n.
    """
    if n == 0:
        return 1

    calc = puissance2(a, n // 2)

    if n % 2 == 0:
        return calc**2
    else:
        return a * (calc) ** 2


if __name__ == "__main__":
    assert puissance2(3, 2) == 9
    assert puissance2(5, 0) == 1
    assert puissance2(2, 8) == 256

    print("Done!")
  1. Justifier que le seconde algorithme met en œuvre le raisonnement « Diviser pour règner ».

    Réponse
    • La première ligne de l’algorithme correspond au cas de base pour lequel n=0n=0 et an=1a^n=1.
    • Pour n>0n>0, à partir de la valeur nn, le calcul se poursuit avec la valeur ⌊n2⌋\left\lfloor \dfrac{n}{2} \right\rfloor. On décompose le calcul de ana^n en celui de a⌊n2⌋a^{\left\lfloor \dfrac{n}{2} \right\rfloor}, puis celui de a⌊n2⌋/2a^{\left\lfloor \dfrac{n}{2} \right\rfloor / 2}, etc. jusqu’à atteindre le cas de base. Chaque calcul intermédiaire se fait sur une instance plus petite.
    • Chaque calcul intermédiaire est aussi indépendant du calcul précédent.

    Remarque

    • ⌊n2⌋\left\lfloor \dfrac{n}{2} \right\rfloor est la notation mathématique pour l’opération en Python n // 2, c’est à dire le plus grand entier inférieur au résultat de la division de nn par 2.

    • ⌈n2⌉\left\lceil \dfrac{n}{2} \right\rceil est la notation mathématique pour l’opération en Python n // 2 + 1, c’est à dire pour le plus petit entier supérieur au résultat de la division de nn par 2.

  2. Pourquoi appelle-t-on l’algorithme 2, l’exponentiation rapide ?

    Réponse

    Soit kk le nombre de fois qu’il faut diviser (division euclidienne) nn par 2 pour parvenir à la valeur 1. kk est tel que

    1=n2k  ⟺  2k=n  ⟺  k=log⁡2n1 = \dfrac{n}{2^k} \iff 2^k = n \iff k = \log_2 n

    .
    Il reste un appel récursif supplémentaire à effectuer pour arriver au cas de base.
    La complexité de l’algorithme est donc en O(log⁡2n)O(\log_2 n) ; elle est bien meilleure que celle de l’algorithme 1.

Conclusion

À retenir
  • La méthode « Diviser pour régner » est le paradigme naturel de la récursivité.
  • La complexité d’un algorithme qui s’appuit sur le paradigme « Diviser pour régner » est parfois optimale (exponentiation rapide, recherche dichotomique, tri fusion, etc.) mais pas toujours (recherche du minimum et du maximum dans une liste, somme des éléments d’une liste, recherche dans une liste non triée, etc.).
  • L’efficacité d’un algorithme qui s’appuit sur le paradigme « Diviser pour régner » dépend de l’implémentation de la récursivité par le langage choisi.

Exercice : recherche dichotomique

  1. Écrire le code de la fonction recherche1 dont la spécification est la suivante :
def recherche1(liste: list[int], val: int) -> int:
    """
    Retourne l'indice de la valeur dans la liste si cette
    dernière est présente, -1 sinon.

    HYPOTHÈSE : val est unique si présente.

    Algorithme itératif.
    """
Réponse
def recherche1(liste: list[int], val: int) -> int:
    """
    Retourne l'indice de la valeur dans la liste si cette
    dernière est présente, -1 sinon.

    HYPOTHÈSE : val est unique si présente.

    Algorithme itératif.
    """
    g = 0  # indice le plus petit
    d = len(liste) - 1  # indice le plus grand

    trouve = False
    while (g < d) and not trouve:
        m = (g + d) // 2  # indice milieu
        if liste[m] == val:
            trouve = True
        elif liste[m] > val:
            d = m - 1
        else:
            g = m + 1
    return m if trouve else -1
  1. Tester la fonction recherche1.

  2. Écrire le code de la fonction recherche2 dont la spécification est la suivante :

def recherche2(liste: list[int], val: int, g: int, d: int) -> bool:
    """
    Retourne l'indice de la valeur dans la liste si cette
    dernière est présente, -1 sinon.

    HYPOTHÈSE : val est unique si présente.

    Algorithme récursif.
    """
Réponse
def recherche2(liste: list[int], val: int, g: int, d: int) -> bool:
    """
    Retourne l'indice de la valeur dans la liste si cette
    dernière est présente, -1 sinon.

    HYPOTHÈSE : val est unique si présente.

    Algorithme récursif.
    """
    if g > d:
        return -1
    else:
        m = (g + d) // 2  # indice milieu
        if liste[m] == val:
            return m
        elif liste[m] > val:
            return recursive(liste, val, g, m - 1)
        else:
            return recursive(liste, val, m + 1, d)
  1. Tester la fonction recherche2.
Physique, Chimie et Informatique > Terminales Spé. NSI > Méthode « Diviser pour régner »

Décomposition d'un problème en sous-problèmes

Principe

À retenir
  • On décompose le problème en sous-problèmes plus simples.
  • On résout les sous-problèmes.
  • On combine les sous-problèmes de façon à construire la solution du problème initial.

Indépendance des sous-problèmes

À retenir
  • Si les sous-problèmes sont indépendants les uns des autres : « Diviser pour règner ».
  • Si les sous-problèmes dépendent les uns des autres : « Programmation dynamique ».
Physique, Chimie et Informatique > Terminales Spé. NSI > Méthode « Diviser pour régner »

Le tri fusion

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 nn éléments d’une séquence SS :

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

  2. Régner : Trier récursivement S1S_1 et S2S_2.

  3. Combiner : Reformer la séquence SS en combinant, dans l’ordre, les éléments des séquences triées S1S_1 et S2S_2.

Info
  • ⌊n2⌋\left\lfloor \dfrac{n}{2} \right\rfloor est la notation mathématique pour l’opération en Python n // 2, c’est à dire le plus grand entier inférieur au résultat de la division de nn par 2.
  • ⌈n2⌉\left\lceil \dfrac{n}{2} \right\rceil est la notation mathématique pour l’opération en Python n // 2 + 1, c’est à dire pour le plus petit entier supérieur au résultat de la division de nn par 2.

Pour bien comprendre la méthode employée, le plus simple est de construire un arbre binaire dans lequel chaque nœud est le résultat d’un appel récursif.

flowchart TD
    S("85 &nbsp;&nbsp; 24  &nbsp;&nbsp;  63  &nbsp;&nbsp;  45  &nbsp;&nbsp;  17  &nbsp;&nbsp;  31  &nbsp;&nbsp;  96  &nbsp;&nbsp;  50") --> S1("85  &nbsp;&nbsp;  24  &nbsp;&nbsp;  63  &nbsp;&nbsp;  45")
    S --> S2("17  &nbsp;&nbsp;  31  &nbsp;&nbsp;  96  &nbsp;&nbsp;  50")
    S1 --> S11("85  &nbsp;&nbsp;  24")
    S1 --> S12("63  &nbsp;&nbsp;  45")
    S11 --> S111(("85"))
    S11 --> S112(("24"))
    S12 --> S121(("63"))
    S12 --> S122(("45"))
    S2 --> S21("17  &nbsp;&nbsp;  31")
    S21 --> S211((17))
    S21 --> S212((31))
    S2 --> S22("96  &nbsp;&nbsp; 50")
    S22 --> S221((96))
    S22 --> S222((50))

Résultats des différents appels récursifs (Partie Diviser).

flowchart BT
    S111((85)) --> S11("24 &nbsp;&nbsp; 85")
    S112((24)) --> S11
    S121((63)) --> S12("45 &nbsp;&nbsp; 63")
    S122((45)) --> S12
    S11 --> S1("24 &nbsp;&nbsp; 45 &nbsp;&nbsp; 63 &nbsp;&nbsp; 85")
    S12 --> S1
    S1 --> S("17 &nbsp;&nbsp; 24 &nbsp;&nbsp; 31 &nbsp;&nbsp; 45 &nbsp;&nbsp; 50 &nbsp;&nbsp; 63 &nbsp;&nbsp; 85 &nbsp;&nbsp; 96")
    S211((17)) --> S21("17 &nbsp;&nbsp; 31")
    S212((31)) --> S21
    S221((96)) --> S22("50 &nbsp;&nbsp; 96")
    S222((50)) --> S22
    S21 --> S2("17 &nbsp;&nbsp; 31 &nbsp;&nbsp; 50 &nbsp;&nbsp; 96")
    S22 --> S2
    S2 --> S

Résultats progressifs après les étapes Régner et Fusionner.

Décomposition de l’exécution de l’algorithme


Légende

  • Chaque nœud représente un appel récursif ;
  • Nœud avec une bordure en pointilles : appels récursifs non encore effectués ;
  • Nœud avec une bordure en gras : appel récursif en cours ;
  • Nœud vide avec une bordure : partie déjà traitée ;
  • Nœud en partie vide (contenant tout de même des valeurs) : appels récursifs en attente.

flowchart TD
    S("85 &nbsp;&nbsp; 24  &nbsp;&nbsp;  63  &nbsp;&nbsp;  45  &nbsp;&nbsp;  17  &nbsp;&nbsp;  31  &nbsp;&nbsp;  96  &nbsp;&nbsp;  50") -.- S1("—  &nbsp;&nbsp;  —  &nbsp;&nbsp; — &nbsp;&nbsp;  —")
    S -.- S2("—  &nbsp;&nbsp;  —  &nbsp;&nbsp;  —  &nbsp;&nbsp;  —")
    S1 -.- S11("—  &nbsp;&nbsp;  —")
    S1 -.- S12("—  &nbsp;&nbsp;  —")
    S11 -.- S111(("—"))
    S11 -.- S112(("—"))
    S12 -.- S121(("—"))
    S12 -.- S122(("—"))
    S2 -.- S21("—  &nbsp;&nbsp;  —")
    S21 -.- S211(("—"))
    S21 -.- S212(("—"))
    S2 -.- S22("—  &nbsp;&nbsp; —")
    S22 -.- S221(("—"))
    S22 -.- S222(("—"))
    classDef pointillet stroke-dasharray: 5 5;
    class S1,S2,S11,S12,S21,S22,S111,S112,S121,S122,S211,S212,S221,S222 pointillet;
    classDef gras stroke-width:3px;
    class S gras;
flowchart TD
    S("— &nbsp;&nbsp; —  &nbsp;&nbsp;  —  &nbsp;&nbsp;  —  &nbsp;&nbsp;  17  &nbsp;&nbsp;  31  &nbsp;&nbsp;  96  &nbsp;&nbsp;  50") --> S1("85  &nbsp;&nbsp;  24  &nbsp;&nbsp; 63 &nbsp;&nbsp;  45")
    S -.- S2("—  &nbsp;&nbsp;  —  &nbsp;&nbsp;  —  &nbsp;&nbsp;  —")
    S1 -.- S11("—  &nbsp;&nbsp;  —")
    S1 -.- S12("—  &nbsp;&nbsp;  —")
    S11 -.- S111(("—"))
    S11 -.- S112(("—"))
    S12 -.- S121(("—"))
    S12 -.- S122(("—"))
    S2 -.- S21("—  &nbsp;&nbsp;  —")
    S21 -.- S211(("—"))
    S21 -.- S212(("—"))
    S2 -.- S22("—  &nbsp;&nbsp; —")
    S22 -.- S221(("—"))
    S22 -.- S222(("—"))
    classDef pointillet stroke-dasharray: 5 5;
    class S2,S11,S12,S21,S22,S111,S112,S121,S122,S211,S212,S221,S222 pointillet;
    classDef gras stroke-width:3px;
    class S1 gras;
flowchart TD
    S("— &nbsp;&nbsp; —  &nbsp;&nbsp;  —  &nbsp;&nbsp;  —  &nbsp;&nbsp;  17  &nbsp;&nbsp;  31  &nbsp;&nbsp;  96  &nbsp;&nbsp;  50") --> S1("—  &nbsp;&nbsp;  —  &nbsp;&nbsp; 63 &nbsp;&nbsp;  45")
    S -.- S2("—  &nbsp;&nbsp;  —  &nbsp;&nbsp;  —  &nbsp;&nbsp;  —")
    S1 --> S11("85  &nbsp;&nbsp;  24")
    S1 -.- S12("—  &nbsp;&nbsp;  —")
    S11 -.- S111(("—"))
    S11 -.- S112(("—"))
    S12 -.- S121(("—"))
    S12 -.- S122(("—"))
    S2 -.- S21("—  &nbsp;&nbsp;  —")
    S21 -.- S211(("—"))
    S21 -.- S212(("—"))
    S2 -.- S22("—  &nbsp;&nbsp; —")
    S22 -.- S221(("—"))
    S22 -.- S222(("—"))
    classDef pointillet stroke-dasharray: 5 5;
    class S2,S12,S21,S22,S111,S112,S121,S122,S211,S212,S221,S222 pointillet;
    classDef gras stroke-width:3px;
    class S11 gras;
flowchart TD
    S("— &nbsp;&nbsp; —  &nbsp;&nbsp;  —  &nbsp;&nbsp;  —  &nbsp;&nbsp;  17  &nbsp;&nbsp;  31  &nbsp;&nbsp;  96  &nbsp;&nbsp;  50") --> S1("—  &nbsp;&nbsp;  —  &nbsp;&nbsp; 63 &nbsp;&nbsp;  45")
    S -.- S2("—  &nbsp;&nbsp;  —  &nbsp;&nbsp;  —  &nbsp;&nbsp;  —")
    S1 --> S11("—  &nbsp;&nbsp;  24")
    S1 -.- S12("—  &nbsp;&nbsp;  —")
    S11 --> S111(("85"))
    S11 -.- S112(("—"))
    S12 -.- S121(("—"))
    S12 -.- S122(("—"))
    S2 -.- S21("—  &nbsp;&nbsp;  —")
    S21 -.- S211(("—"))
    S21 -.- S212(("—"))
    S2 -.- S22("—  &nbsp;&nbsp; —")
    S22 -.- S221(("—"))
    S22 -.- S222(("—"))
    classDef pointillet stroke-dasharray: 5 5;
    class S2,S12,S21,S22,S112,S121,S122,S211,S212,S221,S222 pointillet;
    classDef gras stroke-width:3px;
    class S111 gras;
flowchart TD
    S("— &nbsp;&nbsp; —  &nbsp;&nbsp;  —  &nbsp;&nbsp;  —  &nbsp;&nbsp;  17  &nbsp;&nbsp;  31  &nbsp;&nbsp;  96  &nbsp;&nbsp;  50") --> S1("—  &nbsp;&nbsp;  —  &nbsp;&nbsp; 63 &nbsp;&nbsp;  45")
    S -.- S2("—  &nbsp;&nbsp;  —  &nbsp;&nbsp;  —  &nbsp;&nbsp;  —")
    S1 --> S11("85  &nbsp;&nbsp;  —")
    S1 -.- S12("—  &nbsp;&nbsp;  —")
    S11 <--> S111(("—"))
    S11 --> S112(("24"))
    S12 -.- S121(("—"))
    S12 -.- S122(("—"))
    S2 -.- S21("—  &nbsp;&nbsp;  —")
    S21 -.- S211(("—"))
    S21 -.- S212(("—"))
    S2 -.- S22("—  &nbsp;&nbsp; —")
    S22 -.- S221(("—"))
    S22 -.- S222(("—"))
    classDef pointillet stroke-dasharray: 5 5;
    class S2,S12,S21,S22,S121,S122,S211,S212,S221,S222 pointillet;
    classDef gras stroke-width:3px;
    class S112 gras;
flowchart TD
    S("— &nbsp;&nbsp; —  &nbsp;&nbsp;  —  &nbsp;&nbsp;  —  &nbsp;&nbsp;  17  &nbsp;&nbsp;  31  &nbsp;&nbsp;  96  &nbsp;&nbsp;  50") --> S1("—  &nbsp;&nbsp;  —  &nbsp;&nbsp; 63 &nbsp;&nbsp;  45")
    S -.- S2("—  &nbsp;&nbsp;  —  &nbsp;&nbsp;  —  &nbsp;&nbsp;  —")
    S1 --> S11("24 &nbsp;&nbsp;  85")
    S1 -.- S12("—  &nbsp;&nbsp;  —")
    S11 <--> S111(("—"))
    S11 <--> S112(("—"))
    S12 -.- S121(("—"))
    S12 -.- S122(("—"))
    S2 -.- S21("—  &nbsp;&nbsp;  —")
    S21 -.- S211(("—"))
    S21 -.- S212(("—"))
    S2 -.- S22("—  &nbsp;&nbsp; —")
    S22 -.- S221(("—"))
    S22 -.- S222(("—"))
    classDef pointillet stroke-dasharray: 5 5;
    class S2,S12,S21,S22,S121,S122,S211,S212,S221,S222 pointillet;
    classDef gras stroke-width:3px;
    class S11 gras;
flowchart TD
    S("— &nbsp;&nbsp; —  &nbsp;&nbsp;  —  &nbsp;&nbsp;  —  &nbsp;&nbsp;  17  &nbsp;&nbsp;  31  &nbsp;&nbsp;  96  &nbsp;&nbsp;  50") --> S1("24  &nbsp;&nbsp;  85  &nbsp;&nbsp; 63 &nbsp;&nbsp;  45")
    S -.- S2("—  &nbsp;&nbsp;  —  &nbsp;&nbsp;  —  &nbsp;&nbsp;  —")
    S1 <--> S11("— &nbsp;&nbsp;  —")
    S1 -.- S12("—  &nbsp;&nbsp;  —")
    S11 <--> S111(("—"))
    S11 <--> S112(("—"))
    S12 -.- S121(("—"))
    S12 -.- S122(("—"))
    S2 -.- S21("—  &nbsp;&nbsp;  —")
    S21 -.- S211(("—"))
    S21 -.- S212(("—"))
    S2 -.- S22("—  &nbsp;&nbsp; —")
    S22 -.- S221(("—"))
    S22 -.- S222(("—"))
    classDef pointillet stroke-dasharray: 5 5;
    class S2,S12,S21,S22,S121,S122,S211,S212,S221,S222 pointillet;
    classDef gras stroke-width:3px;
    class S1 gras;
flowchart TD
    S("— &nbsp;&nbsp; —  &nbsp;&nbsp;  —  &nbsp;&nbsp;  —  &nbsp;&nbsp;  17  &nbsp;&nbsp;  31  &nbsp;&nbsp;  96  &nbsp;&nbsp;  50") --> S1("24  &nbsp;&nbsp;  85  &nbsp;&nbsp; — &nbsp;&nbsp;  —")
    S -.- S2("—  &nbsp;&nbsp;  —  &nbsp;&nbsp;  —  &nbsp;&nbsp;  —")
    S1 <--> S11("— &nbsp;&nbsp;  —")
    S1 --> S12("63  &nbsp;&nbsp;  45")
    S11 <--> S111(("—"))
    S11 <--> S112(("—"))
    S12 -.- S121(("—"))
    S12 -.- S122(("—"))
    S2 -.- S21("—  &nbsp;&nbsp;  —")
    S21 -.- S211(("—"))
    S21 -.- S212(("—"))
    S2 -.- S22("—  &nbsp;&nbsp; —")
    S22 -.- S221(("—"))
    S22 -.- S222(("—"))
    classDef pointillet stroke-dasharray: 5 5;
    class S2,S21,S22,S121,S122,S211,S212,S221,S222 pointillet;
    classDef gras stroke-width:3px;
    class S12 gras;
flowchart TD
    S("— &nbsp;&nbsp; —  &nbsp;&nbsp;  —  &nbsp;&nbsp;  —  &nbsp;&nbsp;  17  &nbsp;&nbsp;  31  &nbsp;&nbsp;  96  &nbsp;&nbsp;  50") --> S1("24  &nbsp;&nbsp;  85  &nbsp;&nbsp; — &nbsp;&nbsp;  —")
    S -.- S2("—  &nbsp;&nbsp;  —  &nbsp;&nbsp;  —  &nbsp;&nbsp;  —")
    S1 <--> S11("— &nbsp;&nbsp;  —")
    S1 --> S12("—  &nbsp;&nbsp;  45")
    S11 <--> S111(("—"))
    S11 <--> S112(("—"))
    S12 --> S121(("63"))
    S12 -.- S122(("—"))
    S2 -.- S21("—  &nbsp;&nbsp;  —")
    S21 -.- S211(("—"))
    S21 -.- S212(("—"))
    S2 -.- S22("—  &nbsp;&nbsp; —")
    S22 -.- S221(("—"))
    S22 -.- S222(("—"))
    classDef pointillet stroke-dasharray: 5 5;
    class S2,S21,S22,S122,S211,S212,S221,S222 pointillet;
    classDef gras stroke-width:3px;
    class S121 gras;
flowchart TD
    S("— &nbsp;&nbsp; —  &nbsp;&nbsp;  —  &nbsp;&nbsp;  —  &nbsp;&nbsp;  17  &nbsp;&nbsp;  31  &nbsp;&nbsp;  96  &nbsp;&nbsp;  50") --> S1("24  &nbsp;&nbsp;  85  &nbsp;&nbsp; — &nbsp;&nbsp;  —")
    S -.- S2("—  &nbsp;&nbsp;  —  &nbsp;&nbsp;  —  &nbsp;&nbsp;  —")
    S1 <--> S11("— &nbsp;&nbsp;  —")
    S1 --> S12("63  &nbsp;&nbsp; —")
    S11 <--> S111(("—"))
    S11 <--> S112(("—"))
    S12 <--> S121(("—"))
    S12 --> S122(("45"))
    S2 -.- S21("—  &nbsp;&nbsp;  —")
    S21 -.- S211(("—"))
    S21 -.- S212(("—"))
    S2 -.- S22("—  &nbsp;&nbsp; —")
    S22 -.- S221(("—"))
    S22 -.- S222(("—"))
    classDef pointillet stroke-dasharray: 5 5;
    class S2,S21,S22,S211,S212,S221,S222 pointillet;
    classDef gras stroke-width:3px;
    class S122 gras;
flowchart TD
    S("— &nbsp;&nbsp; —  &nbsp;&nbsp;  —  &nbsp;&nbsp;  —  &nbsp;&nbsp;  17  &nbsp;&nbsp;  31  &nbsp;&nbsp;  96  &nbsp;&nbsp;  50") --> S1("24  &nbsp;&nbsp;  85  &nbsp;&nbsp; — &nbsp;&nbsp;  —")
    S -.- S2("—  &nbsp;&nbsp;  —  &nbsp;&nbsp;  —  &nbsp;&nbsp;  —")
    S1 <--> S11("— &nbsp;&nbsp;  —")
    S1 --> S12("45  &nbsp;&nbsp; 63")
    S11 <--> S111(("—"))
    S11 <--> S112(("—"))
    S12 <--> S121(("—"))
    S12 <--> S122(("—"))
    S2 -.- S21("—  &nbsp;&nbsp;  —")
    S21 -.- S211(("—"))
    S21 -.- S212(("—"))
    S2 -.- S22("—  &nbsp;&nbsp; —")
    S22 -.- S221(("—"))
    S22 -.- S222(("—"))
    classDef pointillet stroke-dasharray: 5 5;
    class S2,S21,S22,S211,S212,S221,S222 pointillet;
    classDef gras stroke-width:3px;
    class S12 gras;
flowchart TD
    S("— &nbsp;&nbsp; —  &nbsp;&nbsp;  —  &nbsp;&nbsp;  —  &nbsp;&nbsp;  17  &nbsp;&nbsp;  31  &nbsp;&nbsp;  96  &nbsp;&nbsp;  50") --> S1("24  &nbsp;&nbsp;  45  &nbsp;&nbsp; 63 &nbsp;&nbsp;  85")
    S -.- S2("—  &nbsp;&nbsp;  —  &nbsp;&nbsp;  —  &nbsp;&nbsp;  —")
    S1 <--> S11("— &nbsp;&nbsp;  —")
    S1 <--> S12("—  &nbsp;&nbsp; —")
    S11 <--> S111(("—"))
    S11 <--> S112(("—"))
    S12 <--> S121(("—"))
    S12 <--> S122(("—"))
    S2 -.- S21("—  &nbsp;&nbsp;  —")
    S21 -.- S211(("—"))
    S21 -.- S212(("—"))
    S2 -.- S22("—  &nbsp;&nbsp; —")
    S22 -.- S221(("—"))
    S22 -.- S222(("—"))
    classDef pointillet stroke-dasharray: 5 5;
    class S2,S21,S22,S211,S212,S221,S222 pointillet;
    classDef gras stroke-width:3px;
    class S1 gras;
flowchart TD
    S("24 &nbsp;&nbsp; 45  &nbsp;&nbsp;  63  &nbsp;&nbsp;  85  &nbsp;&nbsp;  —  &nbsp;&nbsp;  —  &nbsp;&nbsp;  —  &nbsp;&nbsp;  —") <--> S1("—  &nbsp;&nbsp;  —  &nbsp;&nbsp; — &nbsp;&nbsp;  —")
    S --> S2("17  &nbsp;&nbsp;  31  &nbsp;&nbsp;  96  &nbsp;&nbsp;  50")
    S1 <--> S11("— &nbsp;&nbsp;  —")
    S1 <--> S12("—  &nbsp;&nbsp; —")
    S11 <--> S111(("—"))
    S11 <--> S112(("—"))
    S12 <--> S121(("—"))
    S12 <--> S122(("—"))
    S2 -.- S21("—  &nbsp;&nbsp;  —")
    S21 -.- S211(("—"))
    S21 -.- S212(("—"))
    S2 -.- S22("—  &nbsp;&nbsp; —")
    S22 -.- S221(("—"))
    S22 -.- S222(("—"))
    classDef pointillet stroke-dasharray: 5 5;
    class S21,S22,S211,S212,S221,S222 pointillet;
    classDef gras stroke-width:3px;
    class S2 gras;
... et après quelques appels supplémentaires...
flowchart TD
    S("24 &nbsp;&nbsp; 45  &nbsp;&nbsp;  63  &nbsp;&nbsp;  85  &nbsp;&nbsp;  —  &nbsp;&nbsp;  —  &nbsp;&nbsp;  —  &nbsp;&nbsp;  —") <--> S1("—  &nbsp;&nbsp;  —  &nbsp;&nbsp; — &nbsp;&nbsp;  —")
    S --> S2("17  &nbsp;&nbsp;  31  &nbsp;&nbsp;  50  &nbsp;&nbsp;  96")
    S1 <--> S11("— &nbsp;&nbsp;  —")
    S1 <--> S12("—  &nbsp;&nbsp; —")
    S11 <--> S111(("—"))
    S11 <--> S112(("—"))
    S12 <--> S121(("—"))
    S12 <--> S122(("—"))
    S2 <--> S21("—  &nbsp;&nbsp;  —")
    S21 <--> S211(("—"))
    S21 <--> S212(("—"))
    S2 <--> S22("—  &nbsp;&nbsp; —")
    S22 <--> S221(("—"))
    S22 <--> S222(("—"))

    classDef gras stroke-width:3px;
    class S2 gras;
flowchart TD
    S("17 &nbsp;&nbsp; 24  &nbsp;&nbsp;  31  &nbsp;&nbsp;  45  &nbsp;&nbsp;  50  &nbsp;&nbsp;  63  &nbsp;&nbsp;  85  &nbsp;&nbsp;  96") <--> S1("—  &nbsp;&nbsp;  —  &nbsp;&nbsp; — &nbsp;&nbsp;  —")
    S <--> S2("—  &nbsp;&nbsp;  —  &nbsp;&nbsp;  —  &nbsp;&nbsp;  —")
    S1 <--> S11("— &nbsp;&nbsp;  —")
    S1 <--> S12("—  &nbsp;&nbsp; —")
    S11 <--> S111(("—"))
    S11 <--> S112(("—"))
    S12 <--> S121(("—"))
    S12 <--> S122(("—"))
    S2 <--> S21("—  &nbsp;&nbsp;  —")
    S21 <--> S211(("—"))
    S21 <--> S212(("—"))
    S2 <--> S22("—  &nbsp;&nbsp; —")
    S22 <--> S221(("—"))
    S22 <--> S222(("—"))

    classDef gras stroke-width:3px;
    class S gras;
Info

On peut montrer que la hauteur de l’arbre des appels récursifs est voisine (en fonction de la définition choisie pour la hauteur) de log⁡2(n)\log_2 (n) où nn est le nombre d’éléments dans la séquence.

Implémentation du tri fusion pour un tableau

  1. Étudier le code suivant et remplacer les … pour chaque numéro.
def tri_fusion(S: list[int]) -> None:
    """
    Implémentation du tri fusion.
    La liste S est modifiée en place.
    """
    n = len(S)  # ... (0)

    if n < 2:
        return None  # ... (1)

    # Diviser, Régner, Combiner ? ... (2)
    milieu = n // 2
    S1 = S[:milieu]  # .... (3)
    S2 = S[milieu:]  # .... (4)

    # Diviser, Régner, Combiner ? ... (5)
    tri_fusion(S1)  # ... (6)
    tri_fusion(S2)  # ... (7)

    # Diviser, Régner, Combiner ? ... (8)
    fusion(S1, S2, S)  # ... (9)
  1. Étudier le code suivant et expliquer comment s’effectue la fusion.
def fusion(S1: list[int], S2: list[int], S: list[int]) -> None:
    """
    Combine les éléments des deux listes S1 et S2 dans la liste S (en place).
    i est le nombre d'élément(s) de S1 copié(s) dans S.
    j est le nombre d'élément(s) de S2 copié(s) dans S.
    On doit donc avoir i + j <= len(S).
    """
    i = 0
    j = 0

    while i + j < len(S):
        if j == len(S2) or (i < len(S1) and S1[i] < S2[j]):
            S[i + j] = S1[i]
            i = i + 1
        else:
            S[i + j] = S2[j]
            j = j + 1
  1. Étudier le comportement du programme complet à l’aide de pythontutor. Construire la liste à l’aide de l’instruction :
liste = [randint(1, 400) for i in range(5)]
  1. Quelle est la complexité de la fonction fusion ?

  2. Essayer d’évaluer la complexité de l’algorithme sans faire de calcul.



Le tri fusion d’une liste chaînée

Dans cette section, on cherche à adapter l’algorithme de tri fusion à une liste chaînée.

  1. Écrire le code de la classe Cellule permettant d’implémenter une liste chaînée. Cette classe sert juste de structure et définit les champs valeur, de type int, et suivant, de type Cellule, initialisé à None.

  2. Dans la partie principale du programme, écrire le code qui crée la liste chaînée [14, 11, 2, 35, 9, 1].

  3. Définir le code de la fonction tri_fusion dont la spécification est

def tri_fusion(lst: Cellule) -> Cellule:
    """
    Implémente l'algorithme de tri-fusion.
    Une nouvelle liste chaînée est créée.
    """

Cette fonction doit utiliser la fonction coupe (définie un peu plus bas), qui découpe une liste chaînée en deux sous-listes, et la fonction fusion (définie elle aussi un peu plus bas) qui réalise la fusion de deux listes triées.

La fonction tri_fusion doit mettre en œuvre le principe « Diviser pour régner ».

  1. Définir la fonction coupe dont la spécification est
def coupe(lst: Cellule) -> Cellule:
    """
    Découpe la liste L2 est deux sous-listes de même
    longueur à un élément près.
    """
  1. Définir la fonction fusion dont la spécification est
def fusion(l1: Cellule, l2: Cellule) -> Cellule:
    """
    Réalise la fusion des deux listes l1 et l2
    triées.

    Algorithme récursif.
    """
Physique, Chimie et Informatique > Terminales Spé. NSI > Méthode « Diviser pour régner »

Recherche des plus grand et petit éléments dans un tableau

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.

    Réponse
    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.

    Réponse
        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 :

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

    Paradigme « Brute force »
    """
Réponse
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)
  1. 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.

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

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

    Réponse

    Il est nécessaire de parcourir tout le tableau, la complexité est donc en O(N)O(N).

  3. Comparer l’efficacité de la fonction maxmin1 à celle des fonctions fournies par Python en mesurant les durées d’exécution à l’aide de la fonction time du module time.

    Réponse
    import time
    
    if __name__ == "__main__":
        tab = [randint(1, int(1e12)) for i in range(int(1e6))]
    
        print("Fonctions Python")
        t1 = time.time()
        val_min, val_max = (min(tab), max(tab))
        t2 = time.time()
        print("min = {}, max = {}".format(val_min, val_max))
        print("Durée de la recherche : {} s".format(t2 - t1))
    
        print("Recherche « Brute Force »")
        t1 = time.time()
        val_min, val_max = maxmin1(tab)
        t2 = time.time()
        print("min = {}, max = {}".format(val_min, val_max))
        print("Durée de la recherche : {} s".format(t2 - t1))

    Il existe un rapport 2 entre les durées d’exécution des deux fonctions. Elles sont donc du même ordre de grandeur.

  4. En faisant varier le nombre d’éléments dans le tableau, vérifier si les durées d’exécution de la fonction maxmin1 correspond bien à la complexité établie à la question 5. La complexité des fonctions max et min fournies par Python vous semblent-elles être en O(N)O(N) ?

  5. Écrire et implémenter la fonction maxmin2 qui implémente le raisonnement «Diviser pour régner » pour résoudre ce problème. Dans un premier temps, écrire une fonction qui se contente de déterminer le maximum dans la liste passée en argument. Compléter ensuite le code de façon à ce que le maximum et le minimum soient retournés. La spécification de la fonction est :

def maxmin2(tab: List[float]) -> float:
    """
    Recherche du maximum dans le tableau tab.
    
    Paradigme : Diviser pour règner
    """
Réponse
def maxmin2(tab: List[float]) -> float:
    """
    Recherche du maximum dans le tableau tab.
    
    Paradigme : Diviser pour régner
    """
    # Cas de base
    if len(tab) == 1:
        return tab[0]

    # Diviser
    milieu = len(tab) // 2
    max1 = maxmin2(tab[:milieu])
    max2 = maxmin2(tab[milieu:])

    # Régner
    maximum = max(max1, max2)

    # Combiner
    return maximum

Remarque : on peut aussi développer sa propre fonction max.

  1. Vérifier le bon fonctionnement de la fonction à la suite des précédentes vérifications.

    Réponse
        print("Diviser pour régner")
        val_max = maxmin2(tab)
        print("max = {}".format(val_max))

  2. Modifier la fonction maxmin2 afin qu’elle retourne les maximum et minimum dans la liste. La spécification de la fonction est :

def maxmin2(tab: List[float]) -> Tuple[float, float]:
    """
    Recherche du minimum et du maximum dans le tableau tab.
    
    Paradigme : Diviser pour régner
    """
Réponse
def maxmin2(tab: List[float]) -> Tuple[float, float]:
    """
    Recherche du minimum et du maximum dans le tableau tab.
    
    Paradigme : Diviser pour régner
    """
    # Cas de base
    if len(tab) == 1:
        return (tab[0], tab[0])

    # Diviser
    milieu = len(tab) // 2
    max1, min1 = maxmin2(tab[:milieu])
    max2, min2 = maxmin2(tab[milieu:])

    # Régner
    maximum = max(max1, max2)
    minimum = min(min1, min2)

    # Combiner
    return (minimum, maximum)
  1. Quelle est la complexité de cette fonction ?

    Réponse

    Si on note C(n)C(n) la complexité en nombre de comparaisons à effectuer pour résoudre le problème en fonction de la taille du tableau, on obtient la relation suivante :

    C(n)={0si n=12si n=22 C(n//2)+2si n>2C(n) = \begin{cases} 0 &\text{si } n = 1 \\ 2 &\text{si } n = 2 \\ 2\, C(n//2) + 2 &\text{si } n > 2 \end{cases}

    Dans la suite de cette partie, pour résoudre cette récurrence, on simplifie le problème en posant n=2kn = 2^k (on ne restreint pas la généralité de la conclusion en effectuant cette hypothèse). On a alors

    C(n)=2×C(2k2)+2=2×[2×C(2k2×2)+2]+2=2×2×C(2k2×2)+4+2\begin{array}{rl} C(n) &= 2 \times C \left(\dfrac{2^k}{2} \right) + 2 \\ &= 2 \times \left[ 2 \times C\left(\dfrac{2^k}{2\times 2}\right) + 2 \right] + 2 \\ &= 2 \times 2 \times C\left(\dfrac{2^k}{2\times 2}\right) + 4 + 2 \\ \end{array}

    il faut diviser k−1k-1 fois pour parvenir au cas de base, on a alors

    C(n)=2k−1×C(2)+∑i=1k−12iC(n) = 2^{k-1}\times C(2) + \sum_{i=1}^{k-1} 2^i

    Comme C(2)=2C(2)=2 et ∑i=1k−12i=2k−2\sum_{i=1}^{k-1} 2^i = 2^k - 2,

    C(n)=2k−1×2+2k−2=2k+2k−2C(n) = 2^{k-1}\times 2 + 2^k - 2 = 2^k + 2^k - 2

    Finalement

    C(n)=2n−2C(n) = 2n - 2

    Il faut donc 2n−22n - 2 comparaisons pour résoudre le problème. La complexité est donc linéaire.

  2. Vérifier le bon fonctionnement de la fonction à la suite des précédentes vérifications.

    Réponse
    print("Diviser pour régner")
        t1 = time.time()
        val_min, val_max = maxmin2(tab)
        t2 = time.time()
        print("min = {}, max = {}".format(val_min, val_max))
        print("Durée de la recherche : {} s".format(t2 - t1))

  3. La fonction maxmin2 est-elle, théoriquement, plus efficace que la fonction maxmin1 ? Dans la pratique ? Comment expliquer ce comportement ?

    Réponse

    La fonction maxmin2 n’est théoriquement pas plus efficace que la fonction maxmin1 puisque dans les deux cas, la complexité est linéaire.
    En pratique, la fonction maxmin2 peut même être moins efficace que la fonction maxmin1 ! Tout dépend de l’implémentation de la récursivité par le langage.

Physique, Chimie et Informatique > Terminales Spé. NSI > Méthode « Diviser pour régner »

Les tours de Hanoï

Info

Le problème mathématique des tours de Hanoï a été inventé par Édouard Lucas. Paru d’abord en fascicule en 1889 , il est publié ensuite dans le tome 3 de ses « Récréations mathématiques », parues à titre posthume en 1892. Il annonce que ce problème est dû à un de ses amis, N. Claus de Siam (anagramme de Lucas d’Amiens, Amiens étant sa ville de naissance), prétendument professeur au collège de Li-Sou-Stian (anagramme de Saint Louis, le lycée où Lucas enseignait).

Sous le titre « Les brahmes tombent », Lucas relate que « N. Claus de Siam a vu, dans ses voyages pour la publication des écrits de l’illustre Fer-Fer-Tam-Tam, dans le grand temple de Bénarès, au-dessous du dôme qui marque le centre du monde, trois aiguilles de diamant, plantées dans une dalle d’airain, hautes d’une coudée et grosses comme le corps d’une abeille. Sur une de ces aiguilles, Dieu enfila au commencement des siècles, 64 disques d’or pur, le plus large reposant sur l’airain, et les autres, de plus en plus étroits, superposés jusqu’au sommet. C’est la tour sacrée du Brahmâ. Nuit et jour, les prêtres se succèdent sur les marches de l’autel, occupés à transporter la tour de la première aiguille sur la troisième, sans s’écarter des règles fixes que nous venons d’indiquer, et qui ont été imposées par Brahma. Quand tout sera fini, la tour et les brahmes tomberont, et ce sera la fin des mondes ! ».

Info

Au début du jeu, les disques sont tous positionnés sur la première tige (du plus grand au plus petit) et l’objectif est de déplacer tous ces disques sur la troisième tige, en respectant les règles suivantes :

  • Un seul disque peut être déplacé à la fois ;
  • On ne peut jamais poser un disque sur un disque de diamètre inférieur.
  1. Numéroter chaque disque pour un empilement à 4 disques et écrire l’enchaînement des étapes nécessaires à la réalisation de la tâche.

  2. Faire émerger le raisonnement récursif qui permet de résoudre le problème.

    Réponse

    Pour pouvoir déplacer le dernier disque (celui du dessous), il est nécessaire de déplacer les n−1n − 1 disques qui le couvrent sur la tige centrale. Une fois ces déplacements effectués, on peut le déplacer sur la troisième tige. Il reste alors à déplacer les n−1n − 1 autres disques vers la troisième tige.

  3. Écrire le code de la fonction dont la spécification est

def hanoi(n: int, source: str, milieu: str, destination: str) -> None:
    """
    Fonction qui déplace récursivement les disques selon les règles des tours de Hanoï.
    """

Tester cette fonction.

Aide
Info

L’algorithme est le suivant :

  • Si le nombre de disques est égal à 0, ne rien faire ;
  • Si le nombre de disques est égal à 1, déplacer directement le disque du piquet AA au piquet CC ;
  • Si le nombre de disques est supérieur ou égal à 2, enchaîner les étapes suivante :
    • Déplacer n−1n-1 disques du piquet AA jusqu’au piquet BB ;
    • Déplacer le disque qui reste du piquet AA au piquet CC ;
    • Déplacer n−1n-1 disques du piquet BB au piquet CC.
  1. Indiquer tous les appels de fonctions et toutes les instructions exécutées pour n=3n=3.

    Réponse
    • hanoi(3, "A", "B", "C")
      • hanoi(2, "A", "C", "B")
        • hanoi(1, "A", "B", "C")
          • hanoi(0, "A", "C", "B")
          • Affichage : 1 de A à C
          • hanoi(0, "B", "A", "C")
        • Affichage : 2 de A à B
        • hanoi(1, "C", "A", "B")
          • hanoi(0, "C", "B", "A")
          • Affichage : 1 de C à B
          • hanoi(0, "A", "C", "B")
      • Affichage : 3 de A à C
      • hanoi(2, "B", "A", "C")
        • hanoi(1, "B", "C", "A")
          • hanoi(0, "B", "A", "C")
          • Affichage : 1 de B à A
          • hanoi(0, "C", "B", "A")
        • Affichage : 2 de B à C
        • hanoi(1, "A", "B", "C")
          • hanoi(0, "A", "C", "B")
          • Affichage : 1 de A vers C
          • hanoi(0, "B", "A", "C")

  2. Quelle est la complexité de la fonction ?

    Réponse

    Récurrence

    Si on note xnx_n le nombre de mouvement pour déplacer nn disques, on obtient la relation de récurrence :

    x0=0xn=2xn−1+1 si n≥1\begin{aligned} x_0 &= 0\cr x_n &= 2 x_{n-1} + 1 \text{ si } n \ge 1\cr \end{aligned}

    ce qui donne

    xn=2n−1x_n = 2^n - 1

    La complexité est en O(2n)O(2^n).

Physique, Chimie et Informatique > Terminales Spé. NSI > Méthode « Diviser pour régner »

Problème de la sous-séquence de somme maximale

Ce document étudie le problème de la sous-séquence de somme maximale. Ce problème est intéressant parce qu’il existe nombre d’algorithmes pour le résoudre et la complexité (en nombre d’opérations de somme) de ces algorithmes varie considérablement. Seulement deux algorithmes seront abordés, un prochain document présentera l’algorithme le plus efficace (cf. programmation dynamique).

Présentation

Info

Étant donné un tableau tab[1..n] d’entiers (positifs et négatifs), déterminer la valeur maximale du sous-tableau tab[g..h] donnant la plus grande somme de tous les sous-tableaux contigus de tab. Pour plus de commodité, la sous-séquence de somme maximale est 0 si tous les entiers sont négatifs.

Exemples

  • Pour le tableau tab = [-2, -5, 6, -2, -3, 1, 5, -6], la sous séquence de somme maximale est [6, -2, -3, 1, 5] et sa somme est 7.
  • Pour le tableau tab = [0, 1, 2, -2, 3, 2], la sous séquence de somme maximale est [1, 2, -2, 3, 2] et sa somme est 6.
  • Pour le tableau tab = [1, -2, 3, 10, -4, 7, 2, -5], la sous séquence de somme maximale est [3, 10, -4, 7, 2] et sa somme est 18.

Paradigme « Brute force »

  1. On envisage dans un premier temps un algorithme basé sur le paradigme « Brute force » : on évalue la somme de chaque sous-tableau (parmi les n(n+1)/2n(n + 1)/2 sous-tableaux possibles) et à chaque évaluation on mémorise la somme maximale. Écrire le code de la fonction sous_tab_max dont la spécification est :
def sous_tab_max(tab: List[int]) -> int:
    """
    Recherche de la somme maximale dans un tableau.
    
    Paradigme : « Brute force ».
    """

Tester cette fonction.

Réponse
def sous_tab_max(tab: List[int]) -> int:
    """
    Recherche de la somme maximale dans un tableau.
    
    Paradigme : « Brute force ».
    """
    smax = 0
    for i in range(len(tab) - 1):
        somme = 0
        for j in range(i, len(tab)):
            somme += tab[j]
            smax = max(smax, somme)
    return smax
  1. Quelle est la complexité de cette fonction ?
Réponse

On retrouve deux boucles imbriquées dans la fonction, la complexité est donc en O(n2)O(n^2).

Paradigme « Diviser pour régner »

Dans la suite, on cherche à mettre en œuvre le paradigme « Diviser pour régner ».

Le tableau initial est scindé en deux parties de tailles à peu près égales (selon que nn est pair ou impair) : la plus grande somme se trouve soit dans le sous-tableau BB de droite, soit dans le sous-tableau AA de gauche, soit à cheval sur les deux sous-parties. Dans ce dernier cas elle est constituée d’une plus grande somme de la partie gauche se terminant à la fin de la partie gauche (c.-à-d. en mm), et d’une plus grande somme de la partie droite commençant au début de la partie droite (c’est à dire en m+1m+1).

La procédure est récursive. Pour « sortir » des appels récursifs, il est nécessaire de rencontrer un « couple de données-paramètres » (transmis à l’appel) dont la solution est triviale. C’est le cas si le tableau est composé d’au plus un élément.

  1. Écrire le code de la fonction somme_max dont la spécification est :
def somme_max(tab: List[int]) -> int:
    """
    Recherche de la somme maximale dans un
    sous-tableau en appliquant le paradigme
    « Diviser pour régner ».
    """

Remarque

Ne pas effectuer le calcul de la somme maximale se trouveant dans la séquence à cheval sur les deux sous-parties. Ce calcul doit être effectué par un appel à la fonction max_sous_tab définie ci-dessous.

Réponse
def somme_max(tab: List[int]) -> int:
    """
    Recherche de la somme maximale dans un
    sous-tableau en appliquant le paradigme
    « Diviser pour régner ».
    """
    # Cas de base
    if len(tab) == 1:
        return max(0, tab[0])

    # Diviser
    milieu = len(tab) // 2

    s_max1 = somme_max(tab[:milieu])
    s_max2 = somme_max(tab[milieu:])
    s_max3 = max_sous_tab(tab, milieu)

    # Régner
    s_max = max(s_max1, s_max2, s_max3)

    # Combiner
    return s_max
  1. Écrire le code de la fonction max_sous_tab dont la spécification est :
def max_sous_tab(tab: List[float], milieu: int) -> float:
    """
    Recherche la somme maximale entre les deux
    sous-tableaux du tableau tab à partir du milieu.
    """
Réponse
def max_sous_tab(tab: List[float], milieu: int) -> float:
    """
    Recherche la somme maximale entre les deux
    sous-tableaux du tableau tab à partir du milieu.
    """
    # Sous-tableau gauche
    gmax = 0
    somme = 0
    for i in range(milieu, -1, -1):
        somme += tab[i]
        gmax = max(gmax, somme)
    # Sous-tableau droit
    dmax = 0
    somme = 0
    for i in range(milieu + 1, len(tab)):
        somme += tab[i]
        dmax = max(dmax, somme)
    return gmax + dmax
  1. Quelle est la complexité de la fonction somme_max ?
Physique, Chimie et Informatique > Terminales Spé. NSI > Méthode « Diviser pour régner »

Recherche numérique de zéros de fonctions

Dans ce document on introduit une méthode permettant d’évaluer numériquement une solution de l’équation f(x)=0f (x) = 0, avec ff une fonction de R\mathbb{R} dans R\mathbb{R} (lorsque la solution existe, bien sur) : la méthode de dichotomie.

  • La méthode de dichotomie est efficace et converge relativement vite. De plus, les conditions de son utilisation sont assez simples : la fonction ff doit seulement être continue et changer de signe sur l’intervalle choisi ;
  • La méthode de Newton converge étonnement vite ! Les conditions de son utilisation sont cependant plus contraignantes : la fonction ff doit être dérivable.

Méthode de la dichotomie

Le raisonnement à mettre en œuvre s’appuie sur le théorème des valeurs intermédiaires.

Théorème des valeurs intermédiaires

Soit f:[a,b]→Rf: [a,b] \to \mathbb{R} une fonction continue sur un segment. Si f(a)⋅f(b)⩽0f(a) \cdot f(b) \leqslant 0, alors il existe ℓ∈[a,b]\ell \in [a, b] tel que f(ℓ)=0f(\ell)=0.

Principe de résolution du problème

Info
  1. On choisit un intervalle [a,b][a, b] dans lequel on pense que la fonction ff s’annule une seule fois (il peut donc être nécessaire de limiter la largeur de cet intervalle).

  2. Étape 1. On détermine les coordonnées du point milieu de l’intervalle : a+b2\dfrac{a + b}{2}

    • Si f(a)⋅f(a+b2)⩽0f(a) \cdot f \left( \dfrac{a + b}{2} \right) \leqslant 0, le théorème des valeurs intermédiaires permet de conclure qu’il existe un point c∈[a,a+b2]c \in \left[a, \dfrac{a + b}{2} \right] tel que f(c)=0f(c) = 0.
    • Si f(a)⋅f(a+b2)⩾0f(a) \cdot f \left( \dfrac{a + b}{2} \right) \geqslant 0, le théorème des valeurs intermédiaires permet de conclure qu’il existe un point c∈[a+b2,b]c \in \left[ \dfrac{a + b}{2}, b \right] tel que f(c)=0f(c) = 0. On est donc parvenu, à l’issu de cette étape, à définir un intervalle dans lequel f(x)=0f(x) = 0, de longueur moitié par rapport à l’intervalle initial.
  3. Étape suivante. On répète le processus mis en œuvre dans l’Étape 1 pour l’intervalle [a,a+b2]\left[a, \dfrac{a + b}{2} \right] ou [a+b2,b]\left[ \dfrac{a + b}{2}, b \right].

  4. Étapes suivantes. On continue à répéter le processus jusqu’à ce que l’intervalle soit de longueur inférieure à une longueur choisie (arbitrairement).

La méthode converge-t-elle réellement ?

  1. On construit deux suites (an)(a_n) et (bn)(b_n) qui évoluent comme les bornes de l’intervalle, et la suite (xn)(x_n), zéro de ff pour chaque intervalle.

    • Au rang 0. On pose a0=aa_0 = a, b0=bb_0 = b. Comme f(a)⋅f(b)⩽0f (a) \cdot f (b) \leqslant 0, il existe une solution, notée x0x_0, de l’équation f(x)=0f (x) = 0 dans l’intervalle [a0,b0][a_0, b_0].

    • Au rang 1. Si f(a0)⋅f(a0+b02)⩽0f (a_0) \cdot f \left( \dfrac{a_0 + b_0}{2} \right) \leqslant 0, alors on pose a1=a0a_1 = a_0 et b1=a0+b02b_1 = \dfrac{a_0 + b_0}{2}, sinon on pose a1=a0+b02a_1 = \dfrac{a_0 + b_0}{2} et b1=b0b_1 = b_0. Comme f(a1)⋅f(b1)⩽0f (a_1) \cdot f (b_1) \leqslant 0, il existe une solution, notée x1x_1, de l’équation f(x)=0f (x) = 0 dans l’intervalle [a1,b1][a_1, b_1].

    • Au rang nn. On suppose construit un intervalle [an,bn][a_n, b_n], de longueur bn−an2n\dfrac{b_n - a_n}{2^n}, contenant une solution xnx_n de l’équation f(x)=0f (x) = 0. Si f(an)⋅f(an+bn2)⩽0f (a_n) \cdot f \left( \dfrac{a_n + b_n}{2} \right) \leqslant 0, alors on pose an+1=ana_{n + 1} = a_n et bn+1=an+bn2b_{n + 1} = \dfrac{a_n + b_n}{2}, sinon on pose an+1=an+bn2a_{n + 1} = \dfrac{a_n + b_n}{2} et bn+1=bnb_{n + 1} = b_n. Comme f(an+1)⋅f(bn+1)⩽0f (a_{n + 1}) \cdot f (b_{n + 1}) \leqslant 0, il existe une solution, notée xn+1x_{n + 1}, de l’équation f(x)=0f (x) = 0 dans l’intervalle [an+1,bn+1][a_{n + 1}, b_{n + 1}].

  2. Étude des suites construites Par construction : - an⩽xn⩽bna_n \leqslant x_n \leqslant b_n - (an)(a_n) est une suite croissante, (bn)(b_n) une suite décroissante. La limite de (bn−an)(b_n - a_n) tend donc vers 0 lorsque nn tend vers +∞+ \infty :

    lim⁡(bn−an)→n→+∞0\lim (b_n - a_n) \xrightarrow [n \rightarrow + \infty]{} 0

    Les suites (an)(a_n) et (bn)(b_n) sont adjacentes. Elles admettent donc une même limite, ℓ\ell.

    Par application du théorème des gendarmes, on peut aussi en conclure que

    lim⁡(xn)→n→+∞ ℓ\lim (x_n) \xrightarrow[n \rightarrow + \infty] \ \ell

    et, comme ff est une fonction continue,

    f(ℓ)=lim⁡n→+∞f(xn)=lim⁡n→+∞0=0f (\ell) = \lim_{n \rightarrow + \infty} f (x_n) = \lim_{n \rightarrow + \infty} 0 = 0

    En conclusion, les suites (an)(a_n) et (bn)(b_n) tendent vers la valeur ℓ\ell, solution de f(x)=0f (x) = 0.

Remarque

En pratique, on arrête le processus dès que bn−an=b−a2nb_n - a_n = \dfrac{b - a}{2^n} est inférieur à la précision souhaitée.

Exemple : Approximation de 10\sqrt{10}

  • On définit la fonction ff définie par f(x)=x2−10f (x) = x^2 - 10. ff est une fonction continue sur R\mathbb{R} qui s’annule en 10\sqrt{10} et −10-\sqrt{10}.

  • On limite l’étude à l’intervalle [3;4][3 ; 4] puisque : f(3)=32−10=−1<0f (3) = 3^2 - 10 = - 1 < 0 et f(4)=42−10=6>0f (4) = 4^2 - 10 = 6 > 0 entraîne 10∈[3;4]\sqrt{10} \in [3 ; 4].

  • On écrit le processus itératif :

    • On pose a0=3a_0 = 3 et b0=4b_0 = 4. f(a0)⩽0f (a_0) \leqslant 0 et f(b0)⩾0f (b_0) \geqslant 0. a0+b02=3,5\dfrac{a_0 + b_0}{2} = \pu{3,5} donc f(a0+b02)=f(3,5)=3,52−10=2,25⩾0f \left( \dfrac{a_0 + b_0}{2} \right) = f (\pu{3,5}) = \pu{3,5}^2 - 10 = \pu{2,25} \geqslant 0. f(a0)⋅f(a0+b02)⩽0f (a_0) \cdot f \left( \dfrac{a_0 + b_0}{2} \right) \leqslant 0, on en déduit que 10\sqrt{10} est dans l’intervalle [3;3,5][3 ; \pu{3,5}].

    • On pose a1=3a_1 = 3 et b1=3,5b_1 = \text{3,5}. a1+b12=3,25\dfrac{a_1 + b_1}{2} = \pu{3,25} donc f(a1+b12)=f(3,25)=0,5625⩾0f \left( \dfrac{a_1 + b_1}{2} \right) = f (\pu{3,25}) = \pu{0,5625} \geqslant 0. f(a1)⋅f(a1+b12)⩽0f (a_1) \cdot f \left( \dfrac{a_1 + b_1}{2} \right) \leqslant 0, on en déduit que 10\sqrt{10} est dans l’intervalle [3;3,25][3 ; \pu{3,25}].

    • On pose a2=3a_2 = 3 et b2=3,25b_2 = \pu{3,25}. a2+b22=3,125\dfrac{a_2 + b_2}{2} = \pu{3,125} donc f(a2+b22)=f(3,125)=−0,23  ⋅  ⋅  ⋅ ⩽0f \left( \dfrac{a_2 + b_2}{2} \right) = f (\pu{3,125}) = - \pu{0,23...} \leqslant 0. f(b2)⩾0f (b_2) \geqslant 0, ff s’annule sur l’intervalle [3,125;3,25][\text{3,125} ; \pu{3,25}].

      À ce stade, on a donc démontré que : 3,125⩽10⩽3,25\pu{3,125} \leqslant \sqrt{10} \leqslant \pu{3,25}.

Avec quelques étapes de plus, on obtient :

a0=3a_0=3 b0=4b_0=4
a1=3a_1=3 b1=3,5b_1=\pu{3,5}
a2=3a_2=3 b2=3,25b_2=\pu{3,25}
a3=3,125a_3=\pu{3,125} b3=3,25b_3=\pu{3,25}
a4=3,125a_4=\pu{3,125} b4=3,1875b_4=\pu{3,1875}
a5=3,15625a_5=\pu{3,15625} b5=3,1875b_5=\pu{3,1875}
a6=3,15625a_6=\pu{3,15625} b6=3,171875b_6=\pu{3,171875}
a7=3,15625a_7=\pu{3,15625} b7=3,164062b_7=\pu{3,164062}
a8=3,16015a_8=\pu{3,16015} b8=3,164062b_8=\pu{3,164062}

En 8 étapes, on obtient donc l’encadrement :

3,160⩽10⩽3,165\pu{3,160} \leqslant \sqrt{10} \leqslant \pu{3,165}

ce qui donne les deux premières décimales du résultat.

Nombre d’itérations nécessaires pour atteindre un résultat

La longueur de l’intervalle [an,bn][a_n, b_n] est b−a2n\dfrac{b - a}{2^n} puisqu’il a été nécessaire de découper nn fois l’intervalle de départ en deux pour parvenir à cet intervalle.

On peut alors rechercher le nombre d’itérations nécessaires pour atteindre une précision choisie lors de la phase préliminaire de l’étude ; il suffit de rechercher le nombre nn tel que b−a2n⩽10−N\dfrac{b - a}{2^n} \leqslant 10^{- N} :

(b−a)10N⩽2n(b - a) 10^N \leqslant 2^nlog⁡(b−a)+log⁡(10N)⩽log⁡(2n)\log (b - a) + \log (10^N) \leqslant \log (2^n)log⁡(b−a)+N⩽nlog⁡(2)\log (b - a) + N \leqslant n \log (2)n⩾log⁡(b−a)+Nlog⁡(2)n \geqslant \dfrac{\log (b - a) + N}{\log (2)}

Exemple. log⁡(2)≃0,3  ⟺  1log⁡(2)=3,3\log (2) \simeq \pu{0,3} \iff \dfrac{1}{\log (2)} = \pu{3,3} donc si log⁡(b−a)⩽1\log (b - a) \leqslant 1, une précision de :

  • 10−1010^{- 10} (∼\thicksim 10 décimales) nécessite 34 itérations ;

  • 10−10010^{- 100} (∼\thicksim 100 décimales) nécessite 333 itérations ;

  • 10−100010^{- 1000} (∼\thicksim 1000 décimales) nécessite 3322 itérations.

Ajouter une décimale nécessite donc 3 ou 4 itérations supplémentaires.

Implémentation en Python de l’algorithme

L’objectif de cette partie pratique est de mettre en œuvre la méthode de dichotomie en Python pour rechercher la racine carré de 10.

Utiliser un algorithme itératif puis un algorithme récursif.

Corrigé
Physique, Chimie et Informatique > Terminales Spé. NSI > Méthode « Diviser pour régner »

Rotation d'une image bitmap d'un quart de tour

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

L’image matricielle

Une image matricielle, ou « carte de points » (de l’anglais « bitmap »), est une image constituée d’une matrice de points colorés, c’est-à-dire, constituée d’un tableau, d’une grille, où chaque case possède une couleur qui lui est propre et est considérée comme un point. Il s’agit donc d’une juxtaposition de points de couleurs formant, dans leur ensemble, une image.

Caractéristiques

Numérisation

Le codage ou la représentation informatique d’une image implique sa numérisation. Cette numérisation se fait dans deux espaces :

  • l’espace spatial dans lequel l’image est numérisée suivant l’axe des abscisses et l’axe des ordonnées : on parle d’échantillonnage. Les échantillons dans cet espace sont nommés pixels (« picture element ») et leur nombre va constituer la définition de l’image.

  • l’espace des couleurs dans lequel les différentes valeurs de luminosité que peut prendre un pixel sont numérisées pour représenter sa couleur et son intensité ; on parle de quantification. La précision dans cet espace dépend du nombre de bits sur lesquels on code la luminosité et est appelée profondeur de l’image.

À retenir

La qualité d’une image matricielle est déterminée par le nombre total de pixels et la quantité d’information contenue dans chaque pixel (souvent appelée profondeur de numérisation des couleurs).

Définition d’une image

On appelle définition le nombre de points (pixels) constituant une image: c’est le nombre de colonnes de l’image que multiplie son nombre de lignes.

La définition d’une image indique donc le niveau de détails qui seront visibles dans l’image. Pour une taille donnée, plus il y aura de pixels, plus il y aura de détails fins visibles.

Exemple. Une image numérisée avec une définition de 640×480640 \times 480 pixels (donc contenant 307 200 pixels) apparaîtra très approximative et sous forme d’un pavage de petits carrés de couleur, par comparaison à une image de 1280×10241280 \times 1024 pixels (soit 1 310 720 pixels).

Résolution d’une image

On appelle résolution le nombre de points (pixels) contenus dans une longueur donnée, le pouce (un pouce mesure 2,54 cm\pu{2,54 cm}, c’est une unité de mesure britannique). Elle est exprimée en « points par pouce » (PPP) en français et « Dots Per Inch » (DPI) en anglais.

La résolution permet ainsi d’établir le rapport entre la définition d’une image et la dimension réelle de sa représentation sur un support physique (écran, papier, etc.)

> Source : http://www.raphaelisdant.fr/paris8/
Codage des couleurs

En plus de sa définition, une image numérique utilise plus ou moins de mémoire selon le codage des informations de couleur qu’elle possède. C’est ce que l’on nomme le codage de couleurs ou profondeur des couleurs, exprimé en bits par pixel (bpp) : 1, 4, 8, 16, 24, … bits.

Le codage des informations de couleur est donc le nombre de bits utilisés pour coder une couleur.

Remarque

Les écrans utilisent la synthèse additive pour restituer les couleurs : chaque pixel est composé de trois sous-éléments munis respectivement d’un filtre : rouge, vert, bleu.

Quelques modes de représentation des couleurs
  • Mode bitmap (noir et blanc) : Avec ce mode, il est possible d’afficher uniquement des images en deux couleurs: noir et blanc. Il présente une profondeur de 1 bpp.
  • Mode niveau de gris : Avec ce mode, il est possible d’afficher des images utilisant 254 ou 65534 nuances de gris entre le blanc et le noir. Le niveau de gris représente la luminosité d’un pixel, lorsque les valeurs de ses composantes de couleur sont identiques. Pour convertir une image couleur en niveau de gris il faut remplacer, pour chaque pixel les trois valeurs représentant les niveaux de rouge, de vert et de bleu, en une seule valeur représentant la luminosité. Il présente une profondeur de 8 bpp ou 16 bpp.
  • Mode RVB : Dans ce mode, la couleur de chaque pixel de l’image est codée à l’aide d’un triplet de valeurs pour le rouge, le vert et le bleu. Chaque canal peut être codé sur 8 bits (le plus fréquent) ou 16 bits (appareils de photo modernes).

Exploitation des documents

  1. Déterminer la résolution d’une image de 300×300300 \times 300 pixels mesurant 2 pouces par coté.
  2. Quelle serait la définition en pixels d’une feuille scannée d’une largeur de 8,5 pouces sur une hauteur de 11 pouces en 300 dpi ?
  3. Quel est le poids, en octets, d’une image d’une définition de 640×480640 \times 480, codée sur 1 bit (image en « noir et blanc ») ? codée sur 8 bits (« niveau de gris ») ? codée sur 24 bits (« RVB ») ?
  4. Pourquoi le mode « niveau de gris » divise-t-il par trois le nombre d’octets nécessaire au codage ?
  5. Quelle particularité doivent présenter les sous-éléments de chaque pixel lors de l’affichage d’une image en « niveau de gris » ?
  6. Déterminer le nombre de couleurs que l’on peut coder en mode RVB (8 bpp).

Manipulation d’une image en niveaux de gris avec Python

  1. Étudier le code suivant, essayer de déterminer quel traitement effectue la fonction mystere et le tester.
import PIL.Image as pi


def mystere(im):
    """
    Cette fonction réalise un traitement qu'il faut deviner, sur
    l'image dont l'objet qui la représente est passé en argument.

    Paramètre
    ---------
    im: PIL.Image.Image
        Objet image

    Retour
    ------
    None
    """
    (largeur, hauteur) = (im.width, im.height)

    for y in range(hauteur):
        for x in range(largeur):
            niveau = im.getpixel((x, y))
            niveau = 255 - niveau
            im.putpixel((x, y), niveau)


def main():
    """Fonction principale"""

    # Chemin de l'image
    image = "tigrenb.png"
    # Création de l'objet image
    im_nb = pi.open(image)
    # Visualisation du fichier
    im_nb.show()

    # Modification du fichier
    mystere(im_nb)
    # Visualisation des modifications
    im_nb.show()


main()
  1. À partir de la fonction précédente, écrire une fonction nommée noir_et_blanc qui, en fonction d’un seuil s, transforme tous les pixels de valeur inférieure à s en 0 (noir) et tous les autres en 255 (blanc).

  2. En modifiant les couleurs des pixels, il est possible de « dessiner » dans une image. Par exemple, on peut tracer une ligne horizontale blanche dans l’image. Écrire la fonction ligne_blanche qui trace une ligne blanche horizontale au niveau de l’ordonnée yy de l’image et le tester.

  3. Écrire la fonction ligne, évolution de la fonction précédente, qui permet de tracer une ligne horizontale d’une « couleur », codée en niveau de gris, dont le niveau est passé en argument.

  4. On veut maintenant pouvoir assombrir ou éclaircir des images. Pour assombrir une image, on décide de diviser par 2 le niveau de tous les pixels. À l’opposé, pour éclaircir une image, on décide de multiplier par 2 le niveau de tous les pixels, en prenant soin de ne pas dépasser la valeur maximale de 255 (on limite donc les valeurs supérieures à 255). Écrire la fonction traitement qui réalise ces opérations (la fonction doit être capable d’éclaircir ou d’assombrir l’image).

  5. Écrire la fonction grille qui trace une grille à l’écran. Cette fonction doit recevoir en argument le pas de la grille, la couleur des traits horizontaux et verticaux (en niveaux de gris) et l’objet image.

Manipulation d’une image en couleur avec Python

  1. Étudier le code suivant.
from PIL import Image


def recuperation_niveaux(im: Image, pt: tuple) -> None:
    """
    Récupère la couleur du pixel pt.
    """
    # On vérifie que le point est dans l'image
    (largeur, hauteur) = (im.width, im.height)
    if pt[0] > (largeur - 1) or pt[0] < 0 or pt[1] < 0 or pt[1] > (hauteur - 1):
        raise Exception("Le point indiqué n'est pas dans l'image.")

    # Récupération des niveaux de couleur
    triplet = im.getpixel(pt)

    return triplet


def modification_couleur(im: Image, pt: tuple, triplet: tuple) -> None:
    """
    Attribue la couleur (triplet) au pixel pt.
    """

    # On vérifie que le point est dans l'image
    (largeur, hauteur) = (im.width, im.height)
    if pt[0] > (largeur - 1) or pt[0] < 0 or pt[1] < 0 or pt[1] > (hauteur - 1):
        raise Exception("Le point indiqué n'est pas dans l'image.")

    # Modification de la couleur
    im.putpixel(pt, triplet)


def grille(im: Image, pas: int, triplet: tuple) -> None:
    """
    Trace une grille à l'écran, de pas 'pas' dont la couleur
    est donnée par le triplet triplet.
    """
    pass


def augmentation_contraste(im: Image, offset: int) -> None:
    """
    Augmente le contraste de l'image d'une valeur offset.
    """
    pass


def teinte_plus_chaude(im: Image, offset: int) -> None:
    pass


def main():
    """Fonction principale."""
    nom_image = "tigre.jpg"

    # Création de l'objet image
    im = Image.open(nom_image)
    im.show()

    # Récupération des niveaux de couleur
    pt = (600, 250)
    (rouge, vert, bleu) = recuperation_niveaux(im, pt)

    # Affichage du résultat
    print("Au point {} : R : {}, V : {}, B : {}".format(pt, rouge, vert, bleu))


main()
  1. Quelle est la couleur du pixel de coordonnées (600,250)(600, 250) ?

  2. Adapter la fonction grille de la partie précédente de façon à ce qu’on puisse choisir la couleur de la grille.

  3. Écrire le corps de la fonction augmentation_contraste.

  4. Écrire le corps de la fonction teinte_plus_chaude.

Rotation d’une image d’un quart de tour

Dans la suite de cette activité on suppose que l’image est carrée et que sa dimension est une puissance de 2, par exemple 256×256256 \times 256.

Une solution se trouve à cette adresse

Info

L’idée de l’algorithme consiste à découper l’image en quatre, à effectuer la rotation de 90 degrés de chacun des quatre morceaux, puis de les déplacer vers leur position finale.

Afin de pouvoir procéder récursivement, définir la fonction (et sa spécification !) rotation_aux(px, x, y, t) qui effectue la rotation de la portion carrée de l’image comprise entre les pixels (x,y)(x,y) et (x+t,y+t)(x+t, y+t). Cette fonction ne renvoie rien, elle modifie le tableau px pour effectuer la rotation de cette portion de l’image, au même endroit. On suppose que t est une puissance de 2. Le code de cette fonction est :

def rotation_aux(im, x: int, y: int, t: int) -> None:
    if t == 1:
        return

    t = t // 2
    rotation_aux(im, x, y, t)
    rotation_aux(im, x + t, y, t)
    rotation_aux(im, x, y + t, t)
    rotation_aux(im, x + t, y + t, t)

    for i in range(x, x + t):
        for j in range(y, y + t):
            # print(x, y)
            t_1 = im.getpixel((i, j))
            t_2 = im.getpixel((i, j + t))
            t_3 = im.getpixel((i + t, j + t))
            t_4 = im.getpixel((i + t, j))

            im.putpixel((i, j), t_4)
            im.putpixel((i + t, j), t_3)
            im.putpixel((i + t, j + t), t_2)
            im.putpixel((i, j + t), t_1)
  1. Étudier ce code afin de bien le comprendre. En particulier, faire fonctionner à la main la fonction pour une image de définition 8×88 \times 8.

  2. En déduire la fonction rotation(px) qui effectue une rotation de l’image toute entière, sa dimension étant donnée par le paramètre taille. Une fois la rotation effectuée, on pourra sauvegarder le résultat dans un autre fichier avec l’instruction im.save("Apres_rotation.png").

Physique, Chimie et Informatique > Terminales Spé. NSI > Méthode « Diviser pour régner »

Somme des $n$ nombres d'un tableau

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 nn nombres (entiers) d’un tableau.

  1. Écrire le code de fonction somme1 dont la spécification est :
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.

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

    Algorithme : Récursivité enveloppée
    """
    if len(tab) == 1:
        return tab[0]

    return tab[0] + somme1(tab[1:])


if __name__ == "__main__":
    tab = [1, 2, 3, 4, 5, 6, 7]
    n = tab[len(tab) - 1]
    assert somme1(tab) == n * (n + 1) // 2

    print("Done!")

  1. Réfléchir à un algorithme utilisant le principe « Diviser pour régner » qui résoud le même problème.
    Écrire le code de la fonction somme2 qui implémente cet algorithme.
    Tester cette fonction.
Réponse
def somme2(tab: List[float]) -> float:
    """
    Calcul de la somme des nombres éléments
    de tab.

    Algorithme : Diviser pour Régner.
    """
    # Cas de base
    if len(tab) == 1:
        return tab[0]

    # Diviser
    m = len(tab) // 2

    somme_g = somme2(tab[:m])
    somme_d = somme2(tab[m:])

    # Régner
    total = somme_g + somme_d

    # Recombiner
    return total


if __name__ == "__main__":
    tab = [1, 2, 3, 4, 5, 6, 7]
    n = tab[len(tab) - 1]
    assert somme1(tab) == n * (n + 1) // 2
    assert somme2(tab) == n * (n + 1) // 2

    print("Done!")
  1. Décrire le fonctionnement de l’algorithme pour la liste [1, 2, 3, 4, 5, 6, 7].
    Réponse
    somme([1, 2, 3, 4, 5, 6, 7])
        somme_g = somme([1, 2, 3])
            somme_g = somme([1])
                retourne 1
            somme_d = somme([2, 3])
                somme_g = somme([2])
                    retourne 2
                somme_d([3])
                    retourne 3
                total = 5
                retourne 5
            total = 6
            retourne 6
        somme_d = somme([4, 5, 6, 7])
            somme_g = somme([4, 5])
                somme_g = somme([4])
                    retourne 4
                somme_d = somme([5])
                    retourne 5
                total = 9
                retourne 9
            somme_d = somme([6, 7])
                somme_g = somme([6])
                    retourne 6
                somme_d = somme([7])
                    retourne 7
                total = 13
                retourne 13
            total = 22
            retourne 22
        total = 28
        retourne 28