La méthode diviser pour régner

Le principe "diviser pour régner" ("divide and conquer") est un principe militaire ancestrale. Cette stratégie était déjà mis en avant par Jules César "divide et impera", elle est reprise également dans les écrits politiques de Nicolas Machiavel ( article wikipédia sur Machiavel ).

Ce principe en informatique s'applique de préférence avec de la récursivité.

Diviser pour régner

La méthode de "Diviser pour régner" en algorithmique se décompose en trois étapes :

  1. Diviser : on divise l'instance de départ en de plus petites.
  2. Régner : on résout l'algorithme sur les "petites" instances précédentes.
  3. On fusionne les résultats précédents pour obtenir le résultat final.

Un concours informatique est organisé. Il y a 100 candidats. Le travail de chaque candidat a été évalué et on a attribué une note à chacun.

Le règlement du concours impose de rendre les résultats dans l'ordre croissant des notes.

L'ordinateur qui devait trier les copies est en panne. (les cordonniers sont les plus mal chaussés...)

Il faut donc trier à la main.

Bob l'organisateur du concours a une idée ( si, si vraiment ) : Il va diviser le tas de copies. Il demande à son collègue Bobby de trier la moitié des copies pendant que lui triera l'autre moitié. Il procédera à la fusion par la suite.

  1. Diviser : la tas de copies est divisé en deux
  2. Régner : chaque demi paquet est trié.
  3. On finit par fusionner les deux paquets.

Encore plus malin, Bob fait appel à deux autres de ses connaissances : Bobus et Bobo. Ainsi le paquet sera divisé en quatre...

Le principe "diviser pour régner" permet d'écrire des algorithmes avec un complexité peut être plus faible que d'autres algorithmes pour un même problème (Théorème maître).

Tri fusion

L'algorithme de tri fusion est capable de trier un tableau d'objets munis d'une relation d'ordre. (entier, flottant,...)

Performance et complexité

Nous avons vu en première différents algorithmes de tri. (sélection, insertion). Ces algorithmes ont une complexité en temps quadratique, c'est-à-dire de l'ordre de $n^2$.

L'algorithme de tri fusion va nous permettre d'obtenir une complexité d'ordre $nlog_2(n)$.

Observer ces deux courbes pour comprendre le gain en temps.

Observer ce tableau pour comprendre le gain en temps.

Dans le cas d'un tri de 10 000 000 d'éléments, combien peut-on faire de tris fusion pendant le temps nécessaire à un tri insertion ?

Code de déblocage de la correction :

L'algorithme de tri fusion.

Algorithme de tri fusion et méthode diviser pour régner.

  1. Diviser : on divise notre tableau en tableaux 2 fois plus petits.
  2. Régner : on trie chacun des tableaux récursivement.
  3. Fusion : on fusionne les tableaux triés obtenus par récursivité.

Proposer un script Python qui permet de découper une liste en deux parties équivalentes :

  1. avec slice

    Code de déblocage de la correction :

  2. sans slice sans compréhension de liste

    Code de déblocage de la correction :

  3. sans slice en compréhension de liste

    Code de déblocage de la correction :

Code de déblocage de la correction en vidéo:

Ecrire une fonction fusion(gauche,droite) qui prend en argument deux listes triées gauche et droite et qui renvoie une liste triée correspondant à la fusion de gauche et droite.

Cet exercice est difficile, ne vous découragez pas, il est essentiel au cours.

Code de déblocage de la correction :

Ecrire une fonction tri_fusion(l) qui prend en argument une liste l et qui renvoie la liste l triée avec la méthode de tri par fusion.

Vous devez utiliser les deux exercices précédents.

Code de déblocage de la correction :

Quelques aides en vidéo pour les différentes fonctions :

Rotation d'image

Inspiré du livre : NSI TLE GÉNÉRALE (SPÉCIALITÉ) - PRÉPABAC COURS & ENTRAÎNEMENT chez Hatier.

Dans tout cette partie, on utilisera le module PIL.

Image

Une image est un tableau de pixels.

Une image en 1024x720 se compose de 1024x720 pixels.

Chaque pixel a une couleur. La couleur est définie à partir de ses trois composantes : rouge, vert et bleu.

On définit un repère en prenant comme origine le coin en haut à gauche de l'image.

Voici une représentation d'une image :

La taille de cette image est : 7x6

A l'aide la library PIL de Python nous allons manipuler des images (plus d'informations sur le module PIL ici).

Nous allons travailler sur cette image :

la photo du prof

Télécharger ici

  1. Tester et commenter le code ci-dessous :

    from PIL import Image
    im=Image.open("image.png")
    largeur, hauteur=im.size
    im.show()
    

    Code de déblocage de la correction :

  2. Donner les dimensions de l'image.

    Code de déblocage de la correction :

  3. Donner la couleur du pixel de coordonnées (100;100). ( utiliser la methode getpixel())

    Code de déblocage de la correction :

  4. Remplacer la couleur des pixels se situant dans un carré de dimension 100 pixels au centre de la photo par la couleur en RGB (25,153,89).

    Code de déblocage de la correction :

  5. Redimensioner l'image pour qu'elle soit deux fois plus petite. On pourra aller voir les fonctionnalités du module PIL.

    Code de déblocage de la correction :

Rotation image, algorithme naïf.

Rotation d'un quart de tour. Un pixel de coordonnées $(x;y)$ dans une image de taille $n\times n$ a pour coordonnées avant rotation d'un quart de tour en sens horaire $(y;n-1-x)$.

Ecrire la fonction rotation(image,n) qui reçoit pour paramètres une chaîne de caractères correspondant au nom de l'image carrée et un entier $n$ correspondant à la taille de l'image et qui affiche l'image retournée de 90° dans le sens des aiguilles d'une montre.

Code de déblocage de la correction :

Déterminer l'ordre de grandeur de la complexité de cet algorithme.

Code de déblocage de la correction :

On divise, on règne sur les images !

Diviser pour régner

La méthode de "Diviser pour régner" en algorithmique se décompose en trois étapes :

  1. Diviser : on découpe l'image en images de taille 2x2
  2. Régner : on effectue la rotation de chaque image de taille 2x2
  3. Fusion : la fusion est réalisée en échangeant les cadrants lors des appels récursifs .

Ecrire une fonction echangePixel(image,x1,y1,x2,y2) qui échange la valeur des pixels de coordonnées (x1,y1) et (x2,y2) dans l'image nommée image.

Code de déblocage de la correction :

Ecrire une fonction echangeCarre(image,x1,y1,x2,y2,n) qui échange des parties de l'image carrées de taille n dont les coordonnées de leur premier pixel est (x1,y1) et (x2,y2).

On utilisera la fonction echangePixel.

Code de déblocage de la correction :

Vous disposez d'une fonction echange(Carré_a,Carré_b) qui permet d'échanger deux carrés dans une image.

On notera une image carré découpée en quatre carrés de cette manière:

Quelle est la procédure qui permet de réaliser l'echange ci-dessous ?

A, B, C et D sont des carrés.

Code de déblocage de la correction :

L'image est de taille $m\times m$. Le premier pixel de carré1 a pour coordonnées $(x;y)$. Les quatre carrés ont la même dimension.

Donner les coordonnées du premier pixel des carré2, carré3 et carré4 en fonction de $x$,$y$ et $m$.

Code de déblocage de la correction :

Ecrire la procédure récursive tourneCarre(image,x,y,n) tourne d'un quart en sens horaire le carré de l'image de taille n dont le premier pixel a pour coordonnées (x,y).

Code de déblocage de la correction :

Ecrire la fonction rotation(image,n) qui réalise la rotation de image de taille n d'un quart de tour.

Code de déblocage de la correction :

Licence Creative Commons
Les différents auteurs mettent l'ensemble du site à disposition selon les termes de la licence Creative Commons Attribution - Pas d’Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International