Merci de revoir le courts sur les arbres.

Avant d’entrer dans le vif du sujet (les algorithmes), nous allons un peu approfondir la notion d’arbre binaire :

À chaque nœud d’un arbre binaire, on associe une clé (« valeur » associée au nœud on peut aussi utiliser le terme « valeur » à la place de clé), un « sous-arbre gauche » et un « sous-arbre droit »

Soit l’arbre binaire suivant :

si on prend le nœud ayant pour clé A (le nœud racine de l’arbre) on a :

• le sous-arbre gauche est composé du nœud ayant pour clé B, du nœud ayant pour clé C, du nœud ayant pour clé D et du nœud ayant pour clé E
• le sous-arbre droit est composé du nœud ayant pour clé F, du nœud ayant pour clé G, du nœud ayant pour clé H, du nœud ayant pour clé I et du nœud ayant pour clé J

si on prend le noeud ayant pour clé B on a :

• le sous-arbre gauche est composé du nœud ayant pour clé C et du nœud ayant pour clé E
• le sous-arbre droit est uniquement composé du nœud ayant pour clé D

Un arbre (ou un sous-arbre) vide est noté NIL (NIL est une abréviation du latin nihil qui veut dire « rien »)

si on prend le nœud ayant pour clé G on a :

• le sous-arbre gauche est uniquement composé du nœud ayant pour clé I
• le sous-arbre droit est vide (NIL)

Il faut bien avoir en tête qu’un sous-arbre (droite ou gauche) est un arbre (même s’il contient un seul nœud ou pas de nœud de tout (NIL)).

Soit un arbre T : T.racine correspond au nœud racine de l’arbre T

Soit un nœud x :

• x.gauche correspond au sous-arbre gauche du nœud x
• x.droit correspond au sous-arbre droit du nœud x
• x.clé correspond à la clé du nœud x

Il faut noter que si le nœud x est une feuille, x.gauche et x.droite sont des arbres vides (NIL)

Calculer la hauteur d’un arbre

Nous allons commencer à travailler sur les algorithmes en nous intéressant à l’algorithme qui permet de calculer la hauteur d’un arbre :

À faire vous-même 1

Étudiez cet algorithme :

VARIABLE
T : arbre
x : noeud

DEBUT
HAUTEUR(T) :
  si T ≠ NIL :
    x ← T.racine
    renvoyer 1 + max(HAUTEUR(x.gauche), HAUTEUR(x.droit))
  sinon :
    renvoyer 0
  fin si
FIN
		

N.B. la fonction max renvoie la plus grande valeur des 2 valeurs passées en paramètre (exemple : max(5,6) renvoie 6)

Cet algorithme est loin d’être simple, n’hésitez pas à écrire votre raisonnement sur une feuille de brouillon. Vous pourrez par exemple essayer d’appliquer cet algorithme sur l’arbre binaire ci-dessous. N’hésitez pas à poser des questions si nécessaire.

Si vraiment vous avez des difficultés à comprendre le fonctionnement de l’algorithme sur l’arbre ci-dessus, vous trouverez ici un petit calcul qui pourrait vous aider.

Comme vous l’avez sans doute remarqué, nous avons dans l’algorithme ci-dessus une fonction récursive. Vous aurez l’occasion de constater que c’est souvent le cas dans les algorithmes qui travaillent sur des structures de données telles que les arbres.

Calculer la taille d’un arbre

Nous allons maintenant étudier un algorithme qui permet de calculer le nombre de nœuds présents dans un arbre.

À faire vous-même 2

Étudiez cet algorithme :

VARIABLE
T : arbre
x : noeud

DEBUT
TAILLE(T) :
  si T ≠ NIL :
    x ← T.racine
    renvoyer 1 + TAILLE(x.gauche) + TAILLE(x.droit)
  sinon :
    renvoyer 0
  fin si
FIN
		

Cet algorithme ressemble beaucoup à l’algorithme étudié au « À faire vous-même 1 », son étude ne devrait donc pas vous poser de problème.

Appliquez cet algorithme à l’exemple suivant :

Il existe plusieurs façons de parcourir un arbre (parcourir un arbre = passer par tous les nœuds), nous allons en étudier quelques-unes :

Parcourir un arbre dans l’ordre infixe

À faire vous-même 3

Étudiez cet algorithme :

VARIABLE
T : arbre
x : noeud

DEBUT
PARCOURS-INFIXE(T) :
  si T ≠ NIL :
    x ← T.racine
    PARCOURS-INFIXE(x.gauche)
    affiche x.clé
    PARCOURS-INFIXE(x.droit)
  fin si
FIN
		

Vérifiez qu’en appliquant l’algorithme ci-dessus, l’arbre ci-dessous est bien parcouru dans l’ordre suivant : C, E, B, D, A, I, G, F, H, J

Parcourir un arbre dans l’ordre préfixe

À faire vous-même 4

Étudiez cet algorithme :

VARIABLE
T : arbre
x : noeud

DEBUT
PARCOURS-PREFIXE(T) :
  si T ≠ NIL :
    x ← T.racine
    affiche x.clé
    PARCOURS-PREFIXE(x.gauche)
    PARCOURS-PREFIXE(x.droit)
  fin si
FIN
		

Vérifiez qu’en appliquant l’algorithme ci-dessus, l’arbre ci-dessous est bien parcouru dans l’ordre suivant : A, B, C, E, D, F, G, I, H, J

Parcourir un arbre dans l’ordre suffixe

À faire vous-même 5

Étudiez cet algorithme :

VARIABLE
T : arbre
x : noeud

DEBUT
PARCOURS-SUFFIXE(T) :
  si T ≠ NIL :
    x ← T.racine
    PARCOURS-SUFFIXE(x.gauche)
    PARCOURS-SUFFIXE(x.droit)
    affiche x.clé
  fin si
FIN
		

Vérifiez qu’en appliquant l’algorithme ci-dessus, l’arbre ci-dessous est bien parcouru dans l’ordre suivant : E, C, D, B, I, G, J, H, F, A

Le choix du parcours infixe, préfixe ou suffixe dépend du problème à traiter, on pourra retenir pour les parcours préfixe et suffixe (le cas du parcours infixe sera traité un peu plus loin) que :

• dans le cas du parcours préfixe, un nœud est affiché avant d’aller visiter ces enfants
• dans le cas du parcours suffixe, on affiche chaque nœud après avoir affiché chacun de ses fils

Parcourir un arbre en largeur d’abord

À faire vous-même 6

Étudiez cet algorithme :

VARIABLE
T : arbre
Tg : arbre
Td : arbre
x : noeud
f : file (initialement vide)

DEBUT
PARCOURS-LARGEUR(T) :
  enfiler(T, f) //on place la racine dans la file
  tant que f non vide :
    x ← defiler(f)
    affiche x.clé
    si x.gauche ≠ NIL :
      Tg ← x.gauche
      enfiler(Tg, f)
    fin si
    si x.droit ≠ NIL :
      Td ← x.droite
      enfiler(Td, f)
    fin si
  fin tant que
FIN
		

Vérifiez qu’en appliquant l’algorithme ci-dessus, l’arbre ci-dessous est bien parcouru dans l’ordre suivant : A, B, F, C, D, G, H, E, I, J

Selon vous, pourquoi parle-t-on de parcours en largeur ?

Il est important de bien noter l’utilisation d’une file (FIFO) pour cet algorithme de parcours en largeur. Vous noterez aussi que cet algorithme n’utilise pas de fonction récursive.

Arbre binaire de recherche

Un arbre binaire de recherche est un cas particulier d’arbre binaire. Pour avoir un arbre binaire de recherche :

• il faut avoir un arbre binaire !
• il faut que les clés de nœuds composant l’arbre soient ordonnables (on doit pouvoir classer les nœuds, par exemple, de la plus petite clé à la plus grande)
• soit x un noeud d’un arbre binaire de recherche. Si y est un nœud du sous-arbre gauche de x, alors il faut que y.clé ⩽ x.clé. Si y est un nœud du sous-arbre droit de x, il faut alors que x.clé ⩽ y.clé

À faire vous-même 7

Vérifiez que l’arbre ci-dessus est bien un arbre binaire de recherche.

À faire vous-même 8

Appliquez l’algorithme de parcours infixe sur l’arbre ci-dessous :

Que remarquez-vous ?

Recherche d’une clé dans un arbre binaire de recherche

Nous allons maintenant étudier un algorithme permettant de rechercher une clé de valeur k dans un arbre binaire de recherche. Si k est bien présent dans l’arbre binaire de recherche, l’algorithme renvoie vrai, dans le cas contraire, il renvoie faux.

À faire vous-même 9

Étudiez l’algorithme suivant:

VARIABLE
T : arbre
x : noeud
k : entier
DEBUT
ARBRE-RECHERCHE(T,k) :
  si T == NIL :
    renvoyer faux
  fin si
  x ← T.racine
  si k == x.clé :
    renvoyer vrai
  fin si
  si k < x.clé :
    ARBRE-RECHERCHE(x.gauche,k)
  sinon :
    ARBRE-RECHERCHE(x.droit,k)
  fin si
FIN
		

À faire vous-même 10

Appliquez l’algorithme de recherche d’une clé dans un arbre binaire de recherche sur l’arbre ci-dessous. On prendra k = 13.

À faire vous-même 11

Appliquez l’algorithme de recherche d’une clé dans un arbre binaire de recherche sur l’arbre ci-dessous. On prendra k = 16.

Cet algorithme de recherche d’une clé dans un arbre binaire de recherche ressemble beaucoup à la recherche dichotomique vue en première. C’est principalement pour cette raison qu’en général, la complexité en temps dans le pire des cas de l’algorithme de recherche d’une clé dans un arbre binaire de recherche est O(log2(n))

À noter qu’il existe une version dite « itérative » (qui n’est pas récursive) de cet algorithme de recherche :

À faire vous-même 12

Étudiez l’algorithme suivant:

VARIABLE
T : arbre
x : noeud
k : entier
DEBUT
ARBRE-RECHERCHE_ITE(T,k) :
  x ← T.racine
  tant que T ≠ NIL et k ≠ x.clé :
    x ← T.racine
    si k < x.clé :
      T ← x.gauche
    sinon :
      T ← x.droit
    fin si
  fin tant que
  si k == x.clé :
    renvoyer vrai
  sinon :
    renvoyer faux
  fin si
FIN
		

Insertion d’une clé dans un arbre binaire de recherche

Il est tout à fait possible d’insérer un nœud y dans un arbre binaire de recherche (non vide) :

À faire vous-même 13

Étudiez l’algorithme suivant:

VARIABLE
T : arbre
x : noeud
y : noeud
DEBUT
ARBRE-INSERTION(T,y) :
  x ← T.racine
  tant que T ≠ NIL :
    x ← T.racine
    si y.clé < x.clé :
      T ← x.gauche
    sinon :
      T ← x.droit
    fin si
  fin tant que
  si y.clé < x.clé :
    insérer y à gauche de x
  sinon :
    insérer y à droite de x
  fin si
FIN
		

À faire vous-même 14

Appliquez l’algorithme d’insertion d’un nœud y dans un arbre binaire de recherche sur l’arbre ci-dessous. On prendra y.clé = 16.

Merci à l’auteur : David Roche

• Listes, piles et files
• Dictionnaires
• Arbres
• Graphes

Dans la section précédente, vous avez utilisé un logiciel de traitement d’image (Photofiltre) qui contient différents algorithmes permettant de modifier automatiquement des images. Dans un appareil photo ou un smartphone, il y a aussi de tels types d’algorithmes. Ici, vous allez programmer vous-mêmes en Python différents algorithmes permettant de modifier des images.

INDISPENSABLE : Pour travailler avec Python, il faut créer un répertoire (par exemple travail) dans lequel vous enregistrerez à la fois vos fichiers Python (format .py) et vos images (format .png)

A la fin de la section, vous zipperez (= clic droit > compresser) ce répertoire contenant l’intégralité des fichiers .py et .png pour nous le rendre avec votre compte-rendu.

A faire vous-même 0 : Configurer le logiciel Thonny dans lequel on va programmer en Python

Ouvrez le logiciel Thonny (faire une recherche avec la loupe)

Une boite de dialogue apparaît avec le message suivant : « Can’t find backend ‘LocalCPython’. Please select another backend from options »

• ouvrir le menu Outils > Options > Onglet Interpéteur
• choisir l’option par défaut : « Le même interpréteur qui exécute Thonny »

Ensuite, il est nécessaire d’importer la librairie PILLOW (Python Imaging Library) qui fournit les outils nécessaires pour les manipulations d’images :

• de nouveau, ouvrir le Menu Outil > Gérer les paquets…
• écrire « Pillow » dans la barre de recherche et cliquer sur rechercher
• Cliquer sur le lien « pillow » dans la liste obtenue

A faire vous-même 1 : Créer une image avec Python

Voici un script qui génère deux images en couleurs RVB (=RGB en anglais) de dimension 100 x 100.

Tapez-le dans l’éditeur de script de Thonny (fenêtre du haut) et enregistrez-le sous le nom afvm1.py dans votre dossier de travail créé précédemment.

Exécutez le script (icône « lecture »)

from PIL import Image
im=Image.new("RGB", (100, 100)) 
im2= Image.new("RGB", (100, 100), (255,255,255))
im.save("afvm1_1.png")
im2.save("afvm1_2.png") 

• Vérifiez que vous avez 2 images créées dans le dossier de travail (sinon demander de l’aide)
• Lancez le logiciel Photofiltre et ouvrez les 2 images créées
• Expliquez la couleur de l’image afvm1_1.png

Pour modifier la couleur de l’image, il suffit de modifier la couleur de chaque pixel.

On va utiliser la commande putpixel((x,y), (a, b, c)) qui permet de colorer le pixel de coordonnées (x, y) avec la couleur RVB (a, b, c) où a, b et c sont les valeurs de luminance de chaque canal, comprises entre 0 et 255.

Remarque : x est le n° de colonne et y est le n° de ligne. Le 1er pixel en haut à gauche a pour coordonnées (0,0)

A faire vous-même 2 : mettre de la couleur

Dans l’éditeur Thonny, modifiez le script précédent en ajoutant la boucle « for » suivante.

Attention  !

• respectez l’indentation qui délimite les blocs de code (Elle se fait avec la touche de tabulation « tab »)
• n’oubliez pas les « deux-points » : à la fin de la ligne for

from PIL import Image
im=Image.new("RGB", (100, 100))
for x in range (100):
    for y in range(100):
        im.putpixel((x,y),(0,255,0))
im.save("afvm2.png")

• Expliquez ce que produit la boucle ajoutée sur l’image.
• Remplacez la boucle par celle donnée ci-dessous et expliquez le résultat.

for x in range (50):
    for y in range (50,100):
        im.putpixel((x,y),(0,255,0))  

A faire vous-même 3 : coder des drapeaux

Le script suivant permet de produire le drapeau français sous forme d’une image de dimension 120×100 pixels. Une première boucle « for » permet de parcourir les lignes de l’image. Les boucles for imbriquées (attention aux indentations) parcourent les colonnes dans un rectangle donné et y affectent une couleur.

from PIL import Image
col=120
lgn=100
im=Image.new("RGB", (col,lgn))
#il y a 3 bandes verticales, on définit la variable bande :
bande=col//3
for y in range (100):
    for x in range (bande):
        im.putpixel((x,y),(0,0,255))
    for x in range (bande, (2*bande)):
        im.putpixel((x,y),(255,255,255))
    for x in range ((2*bande), col):
        im.putpixel((x,y),(255,0,0))
im.save("france.png")

Après avoir compris le script précédent, vous allez le modifier pour produire d’autres drapeaux. Pensez à enregistrer votre script modifié sous un autre nom et à modifier également le nom de l’image enregistrée par python pour ne pas écraser l’image précédente.

Enregistrez vos différentes versions de script jusqu’à ce que cela fonctionne. Vous joindrez vos scripts python afvm3-irlande et afm3-colombie à votre compte-rendu.

• Modifiez les arguments de la commande putpixel() pour reproduire le drapeau irlandais. (pour avoir le code RGV des couleurs, vous pouvez les sélectionner sur une image avec Pixie ou avec la pipette de Photofiltre)

• Pour ceux qui aiment les défis : plus difficile : modifiez les arguments de la commande putpixel() pour reproduire le drapeau colombien

A faire vous-même 4 : apporter des nuances

Avec quelques petites astuces, on peut aussi produire des dégradés assez facilement. Voici un script qui permet d’obtenir deux dégradés de bleu différents.

from PIL import Image
largeur = 255
hauteur = 255
im=Image.new('RGB', (largeur, hauteur))
for x in range(largeur):
    for y in range(hauteur):
        im.putpixel((x, y), (0, 0, y))
im2=Image.new('RGB', (largeur, hauteur))
for x in range(largeur):
    for y in range(hauteur):
        im2.putpixel((x, y), (0, 0, x))
im.save("camaieubleu1.png")
im2.save("camaieubleu2.png")   

• Expliquez la ligne 7 du script précédent.
• Expliquez la différence entre les 2 images.
• Modifiez le script pour produire le dégradé suivant et enregistrer l’image sous le nom degrade.png

Dans un logiciel de traitement d’image comme Photofiltre, ou celui qui est présent dans l’appareil photo, il est possible de faire des corrections automatiques comme passer l’image en négatif.

Le principe de l’algorithme est de donner pour chaque pixel la couleur inverse : cette couleur est calculée selon le principe suivant :

A faire vous-même 5 : l’image en négatif

• Enregistrez une image de votre choix dans votre répertoire de travail (pensez à choisir une image dont la licence vous permet sa modification)

Voici une partie du script permettant de créer le même effet négatif.

La commande pix = img.getpixel((x,y)) permet d’affecter dans une variable pix  les valeurs des canaux RVB extraites du pixel de coordonnées (x,y).

On peut exprimer ces valeurs sous forme d’un 3-tuple (c’est-à-dire une collection de 3 valeurs, ici correspondant aux 3 canaux RVG) :      p = (pix[0], pix[1], pix[2]) que l’on peut affecter à une variable (ici p) pour l’utiliser ensuite.

Remarque : les indices entre [ ] permettent d’accéder aux différents éléments du tuple. Pour accéder à un élément d’indice   i  d’un tuple t , on écrit      t[i]

• On veut transformer chaque pixel de l’image (variable pix) en son négatif (variable pixneg). Trouvez comment calculer pixneg à partir de pix.

L’extrait de script ci-dessous permet d’ouvrir l’image que vous avez enregistrée, puis de créer une nouvelle image qui sera son négatif. Il manque dans le script suivant 3 lignes (respectez les indentations !) qui permettent de passer l’image en négatif.

• À vous de les écrire et de tester le résultat. Vous joindrez vos images et votre script à votre compte-rendu.

from PIL import Image
  
img = Image.open(MonImage)
col,lgn = img.size
imgF = Image.new(img.mode,img.size)
print("Patientez pendant l'exécution du script …")
  
for x in range(col):
    for y in range(lgn):
...
...
... 
print("… C'est fait !, voir le résultat avec Photofiltre")
imgF.save("image_negatif.png")   

Parmi les retouches d’images très utilisées pour incruster un logo, un copyright ou une signature dans une image, il y a la fusion de deux images. Il s’agit de transformer plus ou moins légèrement la couleur des pixels de manière à ce que l’incrustation ne puisse pas être enlevée facilement.

L’opération mathématique à appliquer pour modifier l’encodage des pixels est la suivante :

                (R₁, V₁, B₁)           est le 3-tuple de l’image 1,         

                (R₂, V₂, V₂)          est le 3-tuple de l’image 2

                a             est le coefficient de dominance d’une image sur l’autre, dont la valeur est comprise entre 0 et 1.

A faire vous-même 6 : fusion d’images

• Utilisez les informations ci-dessus pour compléter le script suivant de façon à obtenir une fusion des drapeaux de la France et de la Colombie.

Astuce : les valeurs (R,V,B) d’un pixel sont obligatoirement des entiers à utilisez     int()

La ligne 2 indique qu’il faudra entrer la valeur de a dans le shell (fenêtre de droite). Vous pourrez essayer différentes valeurs de a et comparer les images produites. Dans ce cas, pensez à modifier le nom du fichier enregistré (ligne 17) sous peine d’écraser le fichier précédent.

(Vous pouvez bien sûr utiliser des images de votre choix dans ce script, mais les 2 images doivent avoir les mêmes dimensions)

from PIL import Image
a=float(input("Entrez la valeur de a : "))
  
im1 = Image.open('france.png')
im2 = Image.open('colombie.png')
  
largeur,hauteur = im1.size
  
im = Image.new('RGB', (largeur, hauteur))
    for x in range(largeur):
        for y in range(hauteur):
            pix1 = im1.getpixel((x,y))
            pix2 = im2.getpixel((x,y))
            fusion = .......................... 
            im.putpixel((x,y),fusion)
  
im.save('fusion.jpg') 

Commençons par un bref historique de la photo sur cette vidéo:

Revenons un petit peu en arrière à l’époque du Noir et Blanc:

Bien entendu, le codage en noir et blanc ne donne pas des images de bonne qualité !

On appelle profondeur de couleur le nombre de bits utilisés pour coder la couleur d’un pixel. Pour une image en noir et blanc, la profondeur est de 2 bits. Cela ne suffit pas pour donner une image correcte d’un ensemble complexe : en fait, la photographie en « noir et banc », n’est pas codée en noir et banc, mais en nuances de gris.

Ces 2 images correspondent à une même prise de vue, mais l’une est en noir et blanc (image en noir et blanc) et l’autre en nuances de gris (= image monochrome)

Un capteur photographique (dans un appareil photo ou un smartphone) contient des photosites : il s’agit de composants électroniques qui convertissent l’énergie lumineuse en tension électrique. Les tensions électriques seront converties en valeurs numériques par l’ordinateur afin de reconstituer les pixels.

A faire vous-même 1: codage en niveau de gris

Dans les travaux précédents, vous avez utilisé des images en noir et blanc : chaque pixel était encodé sur 1 bit. Pour avoir des nuances de gris, il est nécessaire d’avoir un encodage plus complexe utilisant davantage de bits pour un pixel. Par exemple, chaque bit pouvant prendre 2 valeurs, avec 2 bits, on peut obtenir 4 nuances.

En général, pour une image monochrome, la profondeur de couleur est de 8 bits : combien de nuances de gris sont possibles ?

Une photographie en couleur rendra encore mieux la réalité. Dans l’œil humain, la rétine contient des cellules sensibles au changement de luminosité (les bâtonnets) et des cellules sensibles à des radiations particulières de la lumière : les cônes.  Il existe 3 types de cônes : ceux qui sont sensibles aux radiations bleues, ceux qui sont sensibles au vert et ceux qui captent plutôt les rouges.  Grâce à ces 3 types de cônes, on peut voir toutes les couleurs par synthèse additive.

Ces 3 couleurs de lumière sont dites primaires.

Pour obtenir une photographie en couleurs, il y a devant le capteur photographique des filtres colorés comme la matrice Bayer RVB (Rouge, Vert, Bleu). On utilise donc un codage en Rouge/Vert/bleu.

La matrice Bayer est composée de 50 % de filtres verts (car l’œil humain est capable de distinguer de très nombreuses nuances de verts), 25 % de filtres rouges et autant de bleus.  

Il existe différents types de filtres (voir https://geometrian.com/programming/reference/subpixelzoo/index.php) qui permettent tous de capter pour chaque pixel, la luminance en rouge, vert et bleu.

Un pixel sera donc composé des informations en luminance des photosites par synthèse additive des couleurs primaires R, V, B

Expliquez en quoi consiste la synthèse additive (si besoin, faites une recherche)

On codera donc un pixel à l’aide d’un triplet de valeurs (par exemple 247, 56, 98). La première valeur donnant l’intensité du canal rouge, la deuxième valeur donnant l’intensité du canal vert et la troisième valeur donnant l’intensité du canal bleu (RVB ou RGB en anglais).

Expliquez pourquoi, pour chaque canal de chaque pixel, l’intensité lumineuse est comprise entre 0 et 255.

Si chaque canal est codé avec 8 bits, quelle est la profondeur de couleur ?

Combien de couleurs différentes sont-elles possibles avec une telle profondeur ?

A faire vous-même 2

Lancez le logiciel photofiltre puis ouvrez l’image souris.jpeg

Avec l’outil pipette (copie d’écran), prélevez différentes couleurs et donnez les codes correspondants en RVB.

A faire vous-même 3

Menu Réglage > négatif

Que deviennent les différentes couleurs ?

Donnez les codes RVB correspondants.

A faire vous-même 4

 A l’aide de l’outil Pixies à lancer ici, relevez le code RVB de la couleur sélectionnée en avant plan.

https://icn-isn-boissy.yj.fr/wp/wp-content/uploads/2020/02/pixie.zip

Calculez la couleur qu’on obtiendrait avec le réglage négatif réalisé dans le « à faire vous-même 3 ». Quel nom pourrait-on lui donner ?

Le codage le plus simple de l’image est celui en noir et blanc. Dans ce type de codage, la couleur est encodée sur un bit (=binary digit) qui peut prendre 2 valeurs (vrai ou faux, 0 ou 1, blanc ou noir, ouvert ou fermé… etc.)

Pour une image matricielle en noir et blanc, telle que votre image initiale1.png, chaque pixel est encodé par 1 bit noir ou blanc. Le format le plus élémentaire d’image en noir et blanc est le format .pbm (Portable Bit Map).

Vous disposez du fichier carré8×8.pbm qui correspond à un carré blanc de 8 X 8 pixels. Vous allez manipuler l’image avec le logiciel EditHexa ou éditeur en ligne HexEd.it.

Télécharger l’image zippé ci dessous, pensez à la dézipper et à l’enregistrer dans votre dossier.

Vous allez créer une image en manipulant son encodage. Pour chaque étape, votre compte-rendu comportera la copie d’écran de l’encodage et l’image obtenue.

A faire vous-même 1 : le codage d’un carré blanc

Lancez le logiciel EditHexa (ou HexEd.it en ligne) et ouvrez le fichier carré8×8.pbm

Dans la fenêtre centrale, la partie encadrée contient l’encodage en octets et à droite, il y a la traduction sous forme de texte selon la norme ASCII (à un code sur 7 ou 8 bits, correspond un caractère ou une commande)

A partir de ce fichier,

Quel est le nombre d’octets qui encodent l’entête de l’image ? (astuce : cliquer sur différents octets dans la fenêtre centrale et vérifier à droite, à quelle « partie » du fichier cela correspond)

Déterminez le nombre d’octets qui encodent l’image elle-même. Quelle valeur ont-ils ?

Vous avez vu précédemment qu’un octet de l’image (ou du texte de l’entête) correspond à un « nombre » à 2 éléments.

Exemples : le G de GIMP correspond à 47, l’espace entre les deux 8, c’est 20 ou le point correspond à 0A.

• Le système décimal utilise 10 symboles (de 0 à 9) : c’est notre système habituel de numération.
• Le système binaire utilise 2 symboles (0 et 1) : utilisé car en électronique, le courant passe ou pas.
• Le système hexadécimal utilise 16 symboles (0 à 9 et A à F) : cela permet d’écrire des nombres plus longs avec moins de symboles à avantage pour le stockage en informatique. C’est l’idéal pour les images !

Pour faire le travail suivant, il va falloir convertir un octet écrit avec 8 bits dans le système binaire (donc une série de huit 0 ou 1) en sa correspondance dans le système hexadécimal.

Prenons l’exemple de 2 octets 0000 0000 et 0011 1101. (remarque, on on écrit le nombre binaire en 2 paquets de 4 )

Pour convertir ces octets dans le système hexadécimal, on utilise le tableau de conversion ci-dessous pour chaque paquet de 4.

• 0000 0000 du système binaire devient 00 dans le système hexadécimal.
• 0011 1101 du système binaire devient 3D dans le système hexadécimal.

A faire vous-même 2 : le codage d’un carré noir et d’un damier

Modifiez les bits des octets de l’image de manière à former un carré noir. (si besoin, revoir ce qui a été fait sur le codage d’un pixel dans la section précédente)

• Avec l’outil en ligne HexEd.it, modifiez les valeurs des octets de l’image.
• Avec EditHexa : Utilisez menu Outils avancés > manipuler les bits ou modifiez directement les valeurs dans la fenêtre centrale.

Enregistrez votre image sous le nom carrénoir.pbm

Vérifiez votre manipulation en ouvrant le fichier avec Photofiltre ou Gimp (Par défaut, les fichiers du format .pbm sont masqués : cliquez sur le menu déroulant « images les plus courantes » puis sélectionnez « toutes les images »)

Pour obtenir un carré 8×8 à rayure, il faut par exemple que la première ligne soit noire. Ce sera donc une suite de huit bits à 1, c’est-à-dire un octet dont tous les bits valent 1 qu’on peut écrire 1111 1111 ou alors FF.
La deuxième ligne doit être blanche, donc c’est l’octet 0000 0000 ou 00 dans le système hexadécimal.
Et ainsi de suite…

Procédez de la même façon pour obtenir un damier que vous appellerez damier.pbm
astuce : au brouillon, réalisez un tableau de 8×8, coloriez les cases noires du damier que vous voulez obtenir.

A faire vous-même 3 : le codage de l’initiale

Avec Photofiltre ou Gimp, ouvrez l’image initiale2.png créée à la séance précédente. Affichez la grille de repérage avec un pas de 2 pixels.

Avec EditHexa ou HexEd.it, modifiez l’encodage de l’image carré8×8.pbm de manière à reproduire le motif de votre initiale2.png    Vous obtenez alors votre image (vérifiez avec Photofiltre) sur 8 X 8 pixels.

Groupe 1:

Estelle

Binbachi

Linda

sujet: Jeu Snake

Groupe 2:

Mael

Romain

Tommy

Sujet: Jeu Labyrinthe

Groupe 3:

Max

Rémi

Guillaume

Sujet: Morpion ou Tic Tac Toe

Activité 1

visionnez le film

lisez le document

L’obsession des nombres pairs

Note: vous êtes libres d’écrire les fonctions demandées dans l’ordre que vous souhaitez. Lisez l’énoncé en entier avant de commencer. Vous pouvez bien sûr, à l’intérieur d’une fonction, faire des appels aux fonctions que vous avez écrites plus haut.

De plus, dans cet exercice, tous les nombres considérés seront des entiers positifs ou nuls. Les listes passées en argument ne doivent pas être modifiées.

• Ecrire une fonction somme_pairs qui prend en argument une liste et qui renvoie la somme des nombres pairs contenus dans la liste.

Test :

somme_pairs([4, 7, 12, 0, 21, 5]) vaut 16 (car 16=4+12+0).

• Ecrire une fonction nb_elem_pairs qui prend en argument une liste et qui renvoie le nombre d’entiers pairs contenus dans la liste.

Test :

nb_elem_pairs([4, 7, 12, 0, 21, 5]) vaut 3 (car 4, 12 et 0 sont pairs).

• Ecrire une fonction max_pair qui prend en argument une liste et qui renvoie le plus grand entier pair contenu dans la liste. On supposera pour simplifier (dans cette question uniquement) que la liste contient toujours au moins un nombre pair.

Test :

 max_pair([4, 7, 12, 0, 21, 5]) vaut 12.

• Ecrire une fonction min_pair qui prend en argument une liste et qui renvoie le plus petit entier pair contenu dans la liste. Si la liste ne contient aucun entier pair, la fonction renverra None.

Test :

 min_pair([4, 7, 12, 0, 21, 5]) vaut 0

et min_pair([9, 3, 1]) vaut None.

• Ecrire une fonction indice_de qui prend en argument un entier (supposé pair) et une liste, et qui renvoie l’indice auquel apparaît cet entier dans la liste. Si l’entier n’apparaît pas, la fonction renverra None. On suppose ici pour simplifier que l’entier cherché n’apparaît pas plusieurs fois dans la liste. Indice: si la boucle for e in liste ne vous convient pas, n’oubliez pas que vous pouvez faire un for + range ou un while...

Test :

indice_de(12, [4, 7, 12, 0, 21, 5]) vaut 2 (car 12 est placé à l’indice 2), et indice_de(6, [4, 7, 12, 0, 21, 5]) vaut None.

• Ecrire une fonction trouve_premier_pair qui prend en argument une liste et qui renvoie l’entier pair qui apparaît en premier dans la liste. Si la liste ne contient pas d’entier pair, la fonction renverra None.

Test :

trouve_premier_pair([1, 15, 4, 7, 12, 3]) vaut  4

et trouve_premier_pair([1, 17, 7]) vaut  None.

• Ecrire une fonction extrait_pairs qui prend en argument une liste l1 et qui renvoie la liste obtenue à partir de l1 en ne gardant que  les entiers pairs (et sans changer leur ordre). Attention, l1 ne doit pas être modifiée par la fonction.

Test :

extrait_pairs([4, 7, 12, 0, 3]) vaut  [4, 12, 0]

et extrait_pairs([21, 17, 3]) vaut  [ ].