Exercices - Algorithmique

Parcours séquentiel

Exercice 1 - Recherches dans un tableau

Écrire les fonctions suivantes en Python (parcours séquentiel) :

a. recherche_dernier(tab, val) : renvoie l'indice de la dernière occurrence de val, ou -1.

b. contient_doublon(tab) : renvoie True si le tableau contient au moins un élément en double.

c. deux_plus_grands(tab) : renvoie les deux plus grandes valeurs d'un tableau d'au moins 2 éléments (sous forme de tuple).

def recherche_dernier(tab, val):
  pass

def contient_doublon(tab):
  pass

def deux_plus_grands(tab):
  pass

Solution

def recherche_dernier(tab, val):
    dernier_indice = -1
    for i in range(len(tab)):
        if tab[i] == val:
            dernier_indice = i
    return dernier_indice

def contient_doublon(tab):
    for i in range(len(tab)):
        for j in range(i + 1, len(tab)):
            if tab[i] == tab[j]:
                return True
    return False

def deux_plus_grands(tab):
    assert len(tab) >= 2
    if tab[0] >= tab[1]:
        max1, max2 = tab[0], tab[1]
    else:
        max1, max2 = tab[1], tab[0]

    for i in range(2, len(tab)):
        if tab[i] > max1:
            max2 = max1
            max1 = tab[i]
        elif tab[i] > max2:
            max2 = tab[i]
    return (max1, max2)

Exercice 2 - Complexité du parcours

a. Quelle est la complexité de la fonction contient_doublon de l'exercice 1b ? Justifier.

b. Proposer une version plus efficace en utilisant un ensemble (set).

Solution

a. La complexité est en O(n²) car on a deux boucles imbriquées : pour chaque élément (n itérations), on compare avec tous les suivants (au maximum n-1 itérations).

def contient_doublon_rapide(tab):
    vus = set()
    for element in tab:
        if element in vus:
            return True
        vus.add(element)
    return False

Cette version est en O(n) car la recherche dans un set est en O(1) en moyenne.

Recherche dichotomique

Exercice 3 - Dérouler la dichotomie

Dérouler l'algorithme de recherche dichotomique sur le tableau trié [3, 7, 11, 15, 22, 28, 35, 42, 50] pour les valeurs :

a. Recherche de 28

b. Recherche de 10

Solution

a. Recherche de 28 :

Étape	gauche	droite	milieu	tab[milieu]	Action
1	0	8	4	22	28 > 22 → gauche = 5
2	5	8	6	35	28 < 35 → droite = 5
3	5	5	5	28	28 == 28 → trouvé à l'indice 5

b. Recherche de 10 :

Étape	gauche	droite	milieu	tab[milieu]	Action
1	0	8	4	22	10 < 22 → droite = 3
2	0	3	1	7	10 > 7 → gauche = 2
3	2	3	2	11	10 < 11 → droite = 1
4	2	1	-	-	gauche > droite → non trouvé (-1)

Exercice 4 - Nombre d'étapes

a. Combien d'étapes au maximum faut-il pour chercher un élément dans un tableau trié de 1 000 éléments par dichotomie ?

b. Et pour 1 000 000 d'éléments ?

c. Si un algorithme en O(n) met 1 seconde pour n = 1 000 000, combien de temps met un algorithme en O(log₂ n) ?

Solution

a. $\lceil \log_2(1000) \rceil = 10$ étapes au maximum (car $2^{10} = 1024 > 1000$ ).

b. $\lceil \log_2(1000000) \rceil = 20$ étapes au maximum (car $2^{20} = 1048576 > 1000000$ ).

c. L'algorithme en O(n) fait 1 000 000 opérations en 1 seconde. L'algorithme en O(log₂ n) fait seulement 20 opérations. Si chaque opération prend le même temps : $\frac{20}{1000000} \times 1 = 0.00002$ secondes, soit 20 microsecondes.

Algorithmes de tri

Exercice 5 - Dérouler le tri par sélection

Dérouler le tri par sélection sur le tableau [8, 3, 6, 1, 5]. À chaque étape, indiquer l'échange effectué et l'état du tableau.

Solution

Étape	Recherche min dans	Min (indice)	Échange	Tableau après
1	`[8, 3, 6, 1, 5]`	1 (indice 3)	8 ↔ 1	`[1, 3, 6, 8, 5]`
2	`[3, 6, 8, 5]`	3 (indice 1)	pas d'échange	`[1, 3, 6, 8, 5]`
3	`[6, 8, 5]`	5 (indice 4)	6 ↔ 5	`[1, 3, 5, 8, 6]`
4	`[8, 6]`	6 (indice 4)	8 ↔ 6	`[1, 3, 5, 6, 8]`

Résultat final : [1, 3, 5, 6, 8]

Exercice 6 - Dérouler le tri par insertion

Dérouler le tri par insertion sur le tableau [7, 2, 5, 1, 4]. À chaque étape, indiquer la clé, les décalages et l'état du tableau.

Solution

Étape	Clé	Comparaisons et décalages	Tableau après
1	2	2 < 7, décaler 7	`[2, 7, 5, 1, 4]`
2	5	5 < 7, décaler 7 ; 5 > 2, insérer	`[2, 5, 7, 1, 4]`
3	1	1 < 7, décaler 7 ; 1 < 5, décaler 5 ; 1 < 2, décaler 2	`[1, 2, 5, 7, 4]`
4	4	4 < 7, décaler 7 ; 4 < 5, décaler 5 ; 4 > 2, insérer	`[1, 2, 4, 5, 7]`

Résultat final : [1, 2, 4, 5, 7]

Exercice 7 - Comparaison des tris

a. Compter le nombre de comparaisons effectuées par le tri par sélection et le tri par insertion pour trier le tableau [1, 2, 3, 4, 5] (déjà trié).

b. Même question pour le tableau [5, 4, 3, 2, 1] (trié à l'envers).

c. Quel algorithme est le plus avantageux pour un tableau presque trié ? Justifier.

Solution

a. Tableau [1, 2, 3, 4, 5] (déjà trié) :

Sélection : 4 + 3 + 2 + 1 = 10 comparaisons (toujours le même nombre)
Insertion : 1 + 1 + 1 + 1 = 4 comparaisons (chaque clé est déjà à sa place)

b. Tableau [5, 4, 3, 2, 1] (trié à l'envers) :

Sélection : 4 + 3 + 2 + 1 = 10 comparaisons
Insertion : 1 + 2 + 3 + 4 = 10 comparaisons (chaque clé doit être insérée tout au début)

c. Le tri par insertion est plus avantageux pour un tableau presque trié : sa complexité est alors proche de O(n), tandis que le tri par sélection fait toujours O(n²) comparaisons.

Algorithmes gloutons

Exercice 8 - Rendu de monnaie

a. Dérouler l'algorithme glouton de rendu de monnaie pour rendre 87 centimes avec les pièces [1, 2, 5, 10, 20, 50, 100, 200].

b. Avec le système de pièces [1, 3, 4], dérouler l'algorithme glouton pour rendre 6. Le résultat est-il optimal ?

c. Pour le système [1, 3, 4] et la somme 6, trouver la solution optimale.

Solution

a. 87 = 50 + 20 + 10 + 5 + 2 → 5 pièces [50, 20, 10, 5, 2]. C'est optimal.

b. Glouton : 6 = 4 + 1 + 1 → 3 pièces [4, 1, 1]. Ce n'est pas optimal.

c. Solution optimale : 6 = 3 + 3 → 2 pièces [3, 3]. L'algorithme glouton échoue ici car en prenant la plus grande pièce possible (4), il s'empêche d'atteindre la solution optimale.

Exercice 9 - Sac à dos

On dispose des objets suivants et d'un sac de capacité 10 kg :

Objet	Poids (kg)	Valeur (€)	Ratio valeur/poids
A	3	60	20
B	4	100	25
C	5	120	24
D	2	30	15

a. Appliquer l'algorithme glouton (meilleur ratio d'abord). Quels objets sont pris ? Quelle valeur totale ?

b. Trouver une meilleure solution par essai.

Solution

a. Tri par ratio décroissant : B (25), C (24), A (20), D (15).

B : poids 4, valeur 100. Poids total : 4.
C : poids 5, valeur 120. Poids total : 9.
A : poids 3. Poids total serait 12 > 10.
D : poids 2. Poids total serait 11 > 10.

Glouton : B + C = 220 € (poids 9 kg).

b. Essayons B + A + D : poids 4 + 3 + 2 = 9 kg, valeur 100 + 60 + 30 = 190 €. Moins bien.

Essayons C + A + D : poids 5 + 3 + 2 = 10 kg, valeur 120 + 60 + 30 = 210 €. Moins bien.

Ici le glouton donne bien la meilleure solution parmi les combinaisons possibles (220 €).

K plus proches voisins

Exercice 10 - KNN à la main

On dispose des données suivantes représentant des fruits selon leur poids (g) et leur diamètre (cm) :

Poids	Diamètre	Fruit
150	7	Pomme
170	7.5	Pomme
130	6.5	Pomme
60	4	Mandarine
70	4.5	Mandarine
50	3.5	Mandarine
200	8	Poire
180	7	Poire

Un nouveau fruit a un poids de 140 g et un diamètre de 6.8 cm.

a. Calculer la distance euclidienne entre ce nouveau fruit et chacun des 8 fruits connus.

b. Quel est le résultat de KNN avec k = 3 ?

c. Et avec k = 5 ?

Solution

a. Nouveau point : (140, 6.8)

Fruit	Point	Distance
Pomme 1	(150, 7)	$\sqrt{(150-140)^2 + (7-6.8)^2} = \sqrt{100 + 0.04} \approx 10.0$
Pomme 2	(170, 7.5)	$\sqrt{900 + 0.49} \approx 30.0$
Pomme 3	(130, 6.5)	$\sqrt{100 + 0.09} \approx 10.0$
Mandarine 1	(60, 4)	$\sqrt{6400 + 7.84} \approx 80.0$
Mandarine 2	(70, 4.5)	$\sqrt{4900 + 5.29} \approx 70.0$
Mandarine 3	(50, 3.5)	$\sqrt{8100 + 10.89} \approx 90.1$
Poire 1	(200, 8)	$\sqrt{3600 + 1.44} \approx 60.0$
Poire 2	(180, 7)	$\sqrt{1600 + 0.04} \approx 40.0$

Note : les distances sont dominées par le poids (échelle bien plus grande), d'où l'intérêt de la normalisation.

b. k = 3 : les 3 plus proches sont Pomme 1 (10.0), Pomme 3 (10.0), Pomme 2 (30.0). Classe majoritaire : Pomme (3 Pommes / 0 autres).

c. k = 5 : les 5 plus proches sont Pomme 1, Pomme 3, Pomme 2, Poire 2, Poire 1. Classe majoritaire : Pomme (3 Pommes, 2 Poires).

Activités

Activité 1 - Mesurer la complexité expérimentalement

Étapes

a. Écrire les fonctions recherche_sequentielle et recherche_dichotomique.

b. Mesurer le temps d'exécution de chaque algorithme pour des tableaux de tailles 1 000, 10 000, 100 000, 1 000 000. Utiliser le module time.

c. Reporter les résultats dans un tableau. Observer que le temps de la recherche séquentielle est proportionnel à n, et que celui de la dichotomie est quasi-constant.

d. Faire la même mesure pour le tri par sélection et le tri par insertion sur des tableaux de tailles 100, 1 000, 5 000, 10 000. Vérifier que quand n est multiplié par 10, le temps est multiplié par environ 100.

Correction

import time
import random

def recherche_seq(tab, val):
    for i in range(len(tab)):
        if tab[i] == val:
            return i
    return -1

def recherche_dicho(tab, val):
    g, d = 0, len(tab) - 1
    while g <= d:
        m = (g + d) // 2
        if tab[m] == val:
            return m
        elif tab[m] < val:
            g = m + 1
        else:
            d = m - 1
    return -1

def tri_selection(tab):
    n = len(tab)
    for i in range(n - 1):
        i_min = i
        for j in range(i + 1, n):
            if tab[j] < tab[i_min]:
                i_min = j
        tab[i], tab[i_min] = tab[i_min], tab[i]

def tri_insertion(tab):
    for i in range(1, len(tab)):
        cle = tab[i]
        j = i - 1
        while j >= 0 and tab[j] > cle:
            tab[j + 1] = tab[j]
            j -= 1
        tab[j + 1] = cle

# Mesure recherche
print("=== Recherche ===")
for n in [1000, 10000, 100000, 1000000]:
    tab = list(range(n))
    val = -1  # pire cas : élément absent

    debut = time.time()
    recherche_seq(tab, val)
    t_seq = time.time() - debut

    debut = time.time()
    recherche_dicho(tab, val)
    t_dicho = time.time() - debut

    print(f"n={n:>8}  séquentielle: {t_seq:.6f}s  dichotomie: {t_dicho:.6f}s")

# Mesure tri
print("\n=== Tri ===")
for n in [100, 1000, 5000, 10000]:
    tab1 = [random.randint(0, 10000) for _ in range(n)]
    tab2 = tab1.copy()

    debut = time.time()
    tri_selection(tab1)
    t_sel = time.time() - debut

    debut = time.time()
    tri_insertion(tab2)
    t_ins = time.time() - debut

    print(f"n={n:>6}  sélection: {t_sel:.4f}s  insertion: {t_ins:.4f}s")

Activité 2 - Visualiser le KNN

Étapes

a. Créer un jeu de données avec 3 classes de points (par exemple des coordonnées (x, y) avec les classes "A", "B", "C").

b. Implémenter la fonction knn(donnees, point, k).

c. Tester avec k = 1, k = 3 et k = 7 pour un même point. Observer comment le résultat change.

d. Créer un tableau montrant les résultats de classification pour 5 points de test avec chaque valeur de k.

Correction

import math
import random

def distance(p1, p2):
    return math.sqrt((p2[0] - p1[0])**2 + (p2[1] - p1[1])**2)

def knn(donnees, point, k):
    distances = []
    for coords, classe in donnees:
        d = distance(point, coords)
        distances.append((d, classe))
    distances.sort(key=lambda x: x[0])

    compteur = {}
    for _, classe in distances[:k]:
        compteur[classe] = compteur.get(classe, 0) + 1
    return max(compteur, key=compteur.get)

# Jeu de données : 3 groupes
donnees = [
    ((1, 1), "A"), ((2, 1), "A"), ((1, 2), "A"), ((2, 2), "A"),
    ((5, 5), "B"), ((6, 5), "B"), ((5, 6), "B"), ((6, 6), "B"),
    ((1, 5), "C"), ((2, 6), "C"), ((1, 6), "C"), ((2, 5), "C"),
]

# Points de test
tests = [(3, 3), (1, 4), (4, 5), (2, 1.5), (4, 2)]

print(f"{'Point':>10} | k=1 | k=3 | k=7")
print("-" * 40)
for point in tests:
    r1 = knn(donnees, point, 1)
    r3 = knn(donnees, point, 3)
    r7 = knn(donnees, point, 7)
    print(f"{str(point):>10} |  {r1}  |  {r3}  |  {r7}")

Activité 3 - Le glouton face à ses limites

Étapes

a. Implémenter l'algorithme glouton de rendu de monnaie.

b. Tester avec le système euro [1, 2, 5, 10, 20, 50, 100, 200] pour les sommes 63, 126, 289. Vérifier que le résultat est optimal.

c. Tester avec le système [1, 3, 4] pour les sommes 6, 9, 12. Identifier les cas où le glouton échoue.

d. Pour les cas où le glouton échoue, trouver la solution optimale à la main.

Correction

def rendu_glouton(somme, pieces):
    pieces_triees = sorted(pieces, reverse=True)
    resultat = []
    for p in pieces_triees:
        while somme >= p:
            resultat.append(p)
            somme -= p
    return resultat

# Tests avec le système euro
print("=== Système euro ===")
for s in [63, 126, 289]:
    r = rendu_glouton(s, [1, 2, 5, 10, 20, 50, 100, 200])
    print(f"{s} = {r} ({len(r)} pièces)")

# Tests avec le système [1, 3, 4]
print("\n=== Système [1, 3, 4] ===")
for s in [6, 9, 12]:
    r = rendu_glouton(s, [1, 3, 4])
    print(f"{s} = {r} ({len(r)} pièces)")

Résultats :

Système euro : toujours optimal
[1, 3, 4] :
- 6 : glouton = [4, 1, 1] (3 pièces), optimal = [3, 3] (2 pièces)
- 9 : glouton = [4, 4, 1] (3 pièces), optimal = [3, 3, 3] (3 pièces) - même nombre
- 12 : glouton = [4, 4, 4] (3 pièces), optimal = [4, 4, 4] ou [3, 3, 3, 3] - glouton optimal

Projet final - Classificateur de fleurs (iris)

Partie A - Données

Le jeu de données Iris contient 150 fleurs de 3 espèces (Setosa, Versicolor, Virginica) caractérisées par 4 mesures : longueur et largeur des sépales, longueur et largeur des pétales.

a. Créer un jeu de données simplifié avec au moins 5 fleurs par espèce, en utilisant les mesures de pétales (longueur, largeur) :

iris = [
    ((1.4, 0.2), "Setosa"), ((1.3, 0.2), "Setosa"),
    ((1.5, 0.2), "Setosa"), ((1.4, 0.3), "Setosa"),
    ((1.7, 0.4), "Setosa"),
    ((4.7, 1.4), "Versicolor"), ((4.5, 1.5), "Versicolor"),
    ((4.9, 1.5), "Versicolor"), ((4.0, 1.3), "Versicolor"),
    ((4.6, 1.5), "Versicolor"),
    ((6.0, 2.5), "Virginica"), ((5.1, 1.9), "Virginica"),
    ((5.9, 2.1), "Virginica"), ((5.6, 1.8), "Virginica"),
    ((5.8, 2.2), "Virginica"),
]

Partie B - Classification

b. Implémenter les fonctions distance(p1, p2) et knn(donnees, point, k).

c. Classifier les fleurs suivantes et vérifier les résultats :

(1.6, 0.3) → devrait être Setosa
(4.3, 1.4) → devrait être Versicolor
(5.5, 2.0) → devrait être Virginica

Partie C - Évaluation

d. Diviser le jeu de données en un ensemble d'entraînement (80 %) et un ensemble de test (20 %).

e. Évaluer le taux de bonne classification pour k = 1, 3, 5.

f. Afficher une matrice de confusion (combien de Setosa sont classées comme Setosa, combien comme Versicolor, etc.).

Correction

import math
import random

def distance(p1, p2):
    return math.sqrt(sum((a - b)**2 for a, b in zip(p1, p2)))

def knn(donnees, point, k):
    distances = []
    for coords, classe in donnees:
        d = distance(point, coords)
        distances.append((d, classe))
    distances.sort(key=lambda x: x[0])

    compteur = {}
    for _, classe in distances[:k]:
        compteur[classe] = compteur.get(classe, 0) + 1
    return max(compteur, key=compteur.get)

iris = [
    ((1.4, 0.2), "Setosa"), ((1.3, 0.2), "Setosa"),
    ((1.5, 0.2), "Setosa"), ((1.4, 0.3), "Setosa"),
    ((1.7, 0.4), "Setosa"),
    ((4.7, 1.4), "Versicolor"), ((4.5, 1.5), "Versicolor"),
    ((4.9, 1.5), "Versicolor"), ((4.0, 1.3), "Versicolor"),
    ((4.6, 1.5), "Versicolor"),
    ((6.0, 2.5), "Virginica"), ((5.1, 1.9), "Virginica"),
    ((5.9, 2.1), "Virginica"), ((5.6, 1.8), "Virginica"),
    ((5.8, 2.2), "Virginica"),
]

# Partie C - Classification
print("=== Classifications ===")
tests = [((1.6, 0.3), "Setosa"), ((4.3, 1.4), "Versicolor"), ((5.5, 2.0), "Virginica")]
for point, attendu in tests:
    resultat = knn(iris, point, 3)
    ok = "✓" if resultat == attendu else "✗"
    print(f"  {point} → {resultat} (attendu: {attendu}) {ok}")

# Partie D-E - Évaluation
print("\n=== Évaluation ===")
random.seed(42)
donnees = iris.copy()
random.shuffle(donnees)
n_test = max(1, len(donnees) // 5)
test = donnees[:n_test]
train = donnees[n_test:]

for k in [1, 3, 5]:
    correct = 0
    for point, vrai_classe in test:
        pred = knn(train, point, k)
        if pred == vrai_classe:
            correct += 1
    taux = correct / len(test) * 100
    print(f"  k={k} : {correct}/{len(test)} correct ({taux:.0f}%)")

# Partie F - Matrice de confusion
print("\n=== Matrice de confusion (k=3) ===")
classes = ["Setosa", "Versicolor", "Virginica"]
matrice = {v: {p: 0 for p in classes} for v in classes}
for point, vrai in test:
    pred = knn(train, point, 3)
    matrice[vrai][pred] += 1

print(f"{'':>15}", end="")
for c in classes:
    print(f"{c:>12}", end="")
print()
for vrai in classes:
    print(f"{vrai:>15}", end="")
    for pred in classes:
        print(f"{matrice[vrai][pred]:>12}", end="")
    print()