II. Algorithmique sur les tableaux¶

Cours¶

A. Recherche d'extremum¶

Les tableaux permettent de regrouper plusieurs valeurs au même endroit. De ces valeurs, on peut extraire des statistiques, comme trouver son minimum et son maximum.

Considérons le tableau t = [2.4, 83.0, 17.1, -28.2, -5.9]. Il faut le parcourir pour obtenir son plus petit élément.

Décrire en quelques phrases comment trouver le minimum de l'ensemble du tableau.

On parcourt ses éléments un par un. On stocke la valeur du minimum des éléments déjà parcourus dans une variable. Quand on trouve un élément de t inférieur à ce minimum, on actualise sa valeur.

Quels sont les éléments de programmation qu'il faut utiliser ?

Une boucle for parcourant l'ensemble du tableau, une variable stockant le minimum.

Proposer un algorithme de recherche du minimum d'un tableau, renvoyant cette valeur minimale.

entrée : tableau t
sortie : entier ou flottant mini

on initialise une variable mini avec t[0]
on parcourt un à un le reste des éléments de t avec leur indice i
    si l élément i de t est inférieur à mini
        on actualise mini avec t[i]
on renvoie mini

Comment faut-il le modifier pour obtenir la valeur maximale ?

On remplace le "inférieur à" par "supérieur à". On change aussi le nom de la variable mini pour l'appeler maxi.

Appliquer cet algorithme au tableau t, et compléter la table de trace suivante :

itération	variable mini	condition
init	2.4	x
1
2
3
4

B. Recherche d'occurrence¶

Définition

Compter le nombre de fois qu'apparaît une valeur dans un tableau s'appelle compter les occurrences de cette valeur.

B.1. Compter les occurrences¶

On considère t = ['chat', 'chien', 'rat', 'loup', 'chat'], et on veut pouvoir compter le nombre d'occurrences d'une valeur dans t.

Décrire en quelques phrases comment faire pour trouver le nombre d'occurrence d'une valeur v dans un tableau t.

On parcourt les éléments de t un à un, jusqu'au bout du tableau. Lorsque l'on trouve un élément égal à v, on incrémente une variable comptant les occurrences.

Quels sont les éléments de programmation qu'il faut utiliser ?

Il faut utiliser une boucle bornée (for), et une variable comptant les occurrences.

Proposer un algorithme effectuant ce comptage :

entrée : tableau t
sortie : entier nb_occ

on initialise nb_occ à 0
on parcourt un à un tous les éléments de t avec leur indice i
    si l élément i vaut v
        on incrémente nb_occ

Appliquer cet algorithme à t pour la valeur chat, et remplir la table de trace suivante :

itération	variable	condition
init	0	x
1
2
3
4
5

B.2. Trouver une occurrence¶

On veut cette fois-ci indiquer si une valeur est présente dans le tableau ou non.

Quel est le type du résultat ?

C'est un booléen.

Que faut-il changer, par rapport à l'algorithme précédent ?

Il n'est pas nécessaire de parcourir tout le tableau dans tous les cas : lorsqu'on trouve une fois l'élément, l'algorithme peut s'arrêter.

Comment, alors, écrire l'algorithme ?

Version avec boucle non-bornée

entrée : tableau t, valeur v
sortie : booléen trouve

on initialise trouve à False
tant que trouve vaut False et qu il reste des éléments dans t
    on parcourt l élément suivant de t d indice i
        si l élément i de t vaut v
            on actualise trouve à True

Version avec boucle bornée (possible dans une fonction)

fonction recherche_occurrence(t, v)
    entrée : tableau t, valeur v
    sortie : booléen trouve

    on parcourt un à un tous les éléments de t avec leur indice i
        si l élément i de t vaut v
            on renvoie True
    on renvoie False

C. Calcul de moyenne¶

Comment obtenir la moyenne d'un tableau de nombres ?

1. Quelle est la formule pour calculer la moyenne qu'il va falloir utiliser ?

moy = somme des éléments / nombre d'éléments

2. Identifier comment faire le parcours, et les variables à utiliser.

Il faut parcourir tous les éléments, et utiliser une variable stockant la somme des éléments.

Proposer un algorithme :

entrée : tableau t
sortie : flottant moy

on initialise somme à 0
on parcourt les éléments de t
    on ajoute la valeur de l élément i de t à somme
moy vaut somme/(longueur de t)

L'appliquer à t = [2, 83, 17, -20, -5]

itération	variable somme	variable moy
init	0	x
1
2
3
4
5
fin

TP : Algorithmique sur les tableaux 1¶

Nous allons voir différents algorithmes classiques appliqués à des tableaux. Ce TP traite de différents algorithmes qui se ressemblent, que vous allez déduire les uns des autres.

A. Un premier algorithme¶

Sans l'exécuter, analyser le programme ci-dessous. A quel algorithme correspond-il ?

def fonction1(tab):
    var = tab[0]
    for i in range(1, len(tab)):
        if tab[i] > var:
            var = tab[i]
    return var

a. Quel doit être le résultat de l'appel fonction1([1, -5, 14, -2, 13]) ?
b. Ecrire l'assertion correspondante.
c. Quelle est la signature de la fonction ?
Réecrire la fonction en lui donnant un nom explicite, en renommant aussi var, et avec sa signature. L'enregistrer dans un fichier Python avec l'assertion de la question 2.
Que faut-il modifier pour que l'on renvoie l'indice de l'élément plutôt que sa valeur ? C'est à dire que :
- si l'entrée vaut [1, -5, 14, -2, 13], on renvoie 2 au lieu de 14,
- si l'entrée vaut [-10, 30, 4, 7, 16], on renvoie 1 au lieu de 30.
  Faire la modification ci-dessous, renommer la fonction et l'écrire dans le fichier Python avec les assertions vérifiant les 2 tests donnés.

B. Un deuxième algorithme¶

- Que représente -5, comme caractéristique de [1, -5, 14, -2, 13] ?
- Que représente -10, comme caractéristique de [-10, 30, 4, 7, 16] ?
  Ecrire la fonction permettant d'extraire cette caractéristique. On écrira sa signature et les assertions correspondant aux tests donnés.
De manière similaire à la question A.4., on veut pouvoir renvoyer l'indice. Ecrire une autre fonction donnant les résultats suivants :
- si l'entrée vaut [1, -5, 14, -2, 13], on renvoie 1 au lieu de -5,
- si l'entrée vaut [-10, 30, 4, 7, 16], on renvoie 0 au lieu de -10 ?

Ces algorithmes, avec leurs variations, sont à savoir retrouver.

TP : Algorithmique sur les tableaux 2¶

On s'intéresse dans ce TP à la recherche d'un élément dans un tableau, de type quelconque. On parle de recherche d'occurrence d'un élément dans un tableau.

On donne un premier algorithme :

on parcourt un à un les éléments du tableau tab
    si l'élément i est égal à l'élément recherché e
        on renvoie Vrai
on renvoie Faux

Implémenter cet algorithme, en complétant la fonction suivante :

def recherche(tab, e):   
    # à compléter


assert recherche([1,18,-7,3], 3) == True
assert recherche([1,18,-7,3], 25) == False

Modifier cette fonction pour qu'elle ne renvoie pas un booléen, mais l'indice de l'élément recherché, et -1 s'il ne se trouve pas dans le tableau :

def recherche_indice(tab, e):
    # à compléter


assert recherche_indice([1,18,-7,3], 3) == 3
assert recherche_indice([1,18,-7,3], 25) == -1

Un élément peut se trouver plusieurs fois dans le tableau. Modifier l'algorithme pour que votre fonction renvoie l'indice de la dernière occurrence de e, ou -1 si e n'est pas présent :

def recherche_dernier(tab, e):
    # à compléter


assert recherche_dernier(['chat', 'chien', 'rat', 'chat'], 'chat') == 3
assert recherche_dernier(['loup', 'renard', 'belette'], 'chat') == -1

Cet algorithme, avec ses variations, est également à savoir retrouver.

TP : Implémentation du calcul de la moyenne¶

Créer un nouveau fichier Python "TP_Moyenne.py", sauvegardé dans votre répertoire NSI.

Se baser sur l'algorithme de calcul de moyenne écrit en cours pour implémenter la fonction moyenne, prenant en paramètre un tableau de nombres et renvoyant la valeur de la moyenne de ses éléments.

Noter ici l'implémentation trouvée :
Vérifier que l'appel de moyenne([9,18,31,7,5]) renvoie bien le résultat 14.0.

Nous avons pour l'instant utilisé des petits tableaux, mais en pratique on stocke souvent plus de données. On veut évaluer comment le temps d'exécution de notre fonction varie, en fonction de la longueur du tableau.
Créer un tableau t1 par compréhension, stockant la valeur de l'indice de chaque élément du tableau (la valeur du i du range), de longueur 100 000.
Importer la fonction time de la bibliothèque time pour pouvoir lancer un compteur, lorsqu'une ligne de votre programme s'exécute :
Code
```
from time import time
```
Utiliser le code suivant pour obtenir le temps d'exécution de la fonction moyenne lorsqu'elle prend t1 en paramètre, exprimé en millisecondes :
Code
```
debut = time()
m1 = moyenne(t1)
tps = (time()-debut)*1000
```
Reporter la valeur de tps sur le graphique suivant :

Refaire la même opération, c'est-à-dire le calcul du temps d'exécution, mais avec un tableau t2 de longueur 500 000 (lui donner les mêmes valeurs que précédemment : chaque élément stocke la valeur de son indice). Reporter la valeur obtenue sur le graphique de la question 6.
Réitérer ces opérations pour un tableau de longueur 1 000 000, 1 500 000 et 2 000 000.
Tracer la courbe qui relie les différents points sur le graphique. Qu'observe-t-on ?

TD : Algorithmes sur les tableaux¶

Exercice 1 : Recherche d'occurrence¶

Ecrire un programme recherchant si la valeur 13 est présente dans le tableau t. Elle renverra True si c'est le cas, et False sinon. On fera un parcours par valeur du tableau.
Code
```
t = [2, -6, 0, 12, 28, -9, 30
```
###
a. Transformer ce programme en une fonction recherche_occurrence(t, v) prenant en paramètre un tableau t et une valeur v, renvoyant True si v est présente dans t, False sinon.

b. Ecrire l'appel de fonction à faire dans la console pour tester le programme sur le même exemple que dans la question 1. Que doit-il renvoyer ?

Code

###
a. Ecrire une fonction indice_occurrence(t, v) prenant en paramètre un tableau t et une valeur v, renvoyant l'indice de l'occurrence de v dans t si elle est présente, -1 sinon. Il faut faire un parcours par indice**.

b. Ecrire l'assertion permettant de tester son bon fonctionnement.

Code

###
a. Ecrire une fonction compte_occurrence(t, v) prenant en paramètre un tableau t et une valeur v, et renvoyant le nombre d'occurrence de v dans t.

b. Ecrire l'assertion permettant de tester son bon fonctionnement.

Code

###

Exercice 2 : Recherche d'extrema¶

Ecrire un programme permettant de trouver la valeur du minimum d'un tableau t. On fera un parcours par valeur du tableau.
Code
```
t = [2, -6, 0, 12, 28, -9, 30]
```
###
a. Transformer ce programme en une fonction valeur_minimum(t) prenant en paramètre un tableau t et renvoyant sa valeur minimale.

b. Ecrire l'appel de fonction à faire dans la console pour tester le programme sur le même exemple que dans la question 1. Que doit-il renvoyer ?

Code

###
a. Ecrire une fonction indice_minimum(t) prenant en paramètre un tableau t et renvoyant l'indice du minimum du tableau. S'il apparaît 2 fois, l'indice de la première occurrence du minimum est conservée. Il faut faire un parcours par indice.

b. Ecrire l'assertion permettant de tester son bon fonctionnement.

Code

###
Ecrire une fonction indice_maximum(t) prenant en paramètre un tableau t et renvoyant l'indice du maximum du tableau. S'il apparaît 2 fois, l'indice de la dernière occurrence du minimum est conservée. Il faut faire un parcours par indice.

Code

###

Exercice 3 : Calcul de moyenne¶

Ecrire une fonction moyenne(tab) prenant en paramètre un tableau tab d'entiers ou de flottants et renvoyant la moyenne des éléments. On écrira la signature de la fonction, ainsi que plusieurs assertions permettant de vérifier son fonctionnement.

Code

###

Exercice 4 : QCM¶

On considère la fonction suivante :

Code

def f(T,i):
    indice = i
    m = T[i]
    for k in range(i+1, len(T)):
        if T[k] < m:
            indice = k
            m = T[k]
    return indice

Quelle est la valeur de f([ 7, 3, 1, 8, 19, 9, 3, 5 ], 0) ?

A 1 | B 2 | C 3 | D 4

Quelle est la valeur de c à la fin de l'exécution du code suivant :

Code

L = [1,2,3,4,1,2,3,4,0,2]
c = 0
for k in L:
    if k == L[1]:
        c = c+1

A 0 | B 2 | C 3 | D 10

On exécute le script suivant :
Code
```
liste = [17, 12, 5, 18, 2, 7, 9, 15, 14, 20]
somme = 0
i = 0
while i < len(liste):
    somme = somme + liste[i]
    i = i + 1
resultat = somme / len(liste)
```
Quelle affirmation est fausse parmi les suivantes ?

A le corps de la boucle a été exécuté 10 fois
B à la fin de l'exécution la valeur de i est 9
C resultat contient la moyenne des éléments de liste
D len est une fonction

On définit la fonction suivante :

Code

def traitement(liste) :
    m = liste[0]
    for i in range (len(liste)) :
        if liste[i] > m:
            m = liste[i]
    return m

Que vaut traitement([-2,5,6,-10,35]) ?
A None | B -10 | C -6 | D 35

TP : Dessin automatique d'images¶

Codes de correction

Répondre aux questions sur votre cahier de TP.

Une image est un tableau à 2 dimensions, autrement dit une matrice. Chacun des points contient une valeur : sa couleur.

A. Images en noir et blanc¶

Pour cette partie, créer un fichier TP_Image_Bichrome.py.

Nous allons commencer par manipuler des images n'ayant que deux couleurs, représentées par des 0 et des 1.

On commence par initialiser l'image avec des 0. Compléter l'instruction suivante, créant un tableau de taille 25x25 par compréhension avec des 0 à chaque coordonnée :
image = [ [... for i in range(...)] for j in range(...)]
On veut dessiner un carré, en mettant des 1 sur :
- la première ligne, d'indice ......................
- la dernière ligne, d'indice ......................
- la première colonne, d'indice ......................
- la dernière colonne, d'indice ......................
a. Faire un parcours de tous les éléments de image et mettre à 1 les éléments (image[i][j]) identifiés. On utilise 2 boucles imbriquées :
Code
```
for i in range(len(image)):
    for j in range(len(image[0])):
        # à compléter
```
b. Visualiser ensuite le résultat avec matplotlib. Pour cela, rajouter au début du fichier l'import : from matplotlib.pyplot import *, et ajouter à la fin de votre code les instructions suivantes :
Code
```
imshow(image)    # fonction affichant les images
show()
```
Ecrire le code permettant de générer les formes ci-dessous. Pour cela, identifier à chaque fois pour quelles coordonnées i et j il faut faire passer la valeur à 1.

B. Images en couleur¶

La couleur est représentée par un triplet de nombres : un pour l'intensité du rouge, un pour le vert, et un pour le bleu (R, V, B). Ce nombre est stocké sur 1 octet, donc varie entre 0 et 255. Le schéma ci-contre indique comment coder les couleurs de base.

Pour représenter le triplet, on utilise un tuple : un ensemble de valeurs séparées par des virgules.

Créer un fichier TP_Image_Carre_Couleurs.py.

Pour initialiser l'image avec du noir pour tous les pixels, on utilise l'instruction image = [ [(0, 0, 0) for i in range(...)] for j in range(...)].
Créer une fonction permettant de créer un carré soit rouge, soit vert, soit bleu, soit jaune : carre_couleur(image, c) prenant en paramètre l'image image dont on a initialisé la couleur, et la couleur c écrite sous la forme d'une chaîne de caractères remplissant tous les pixels sauf les bords de cette couleur.

Créer un fichier TP_Image_Carre_Multicolor.py.
Ecrire le code permettant de créer l'image suivante :