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).
Solution
a.
def recherche_dernier(tab, val):
dernier_indice = -1
for i in range(len(tab)):
if tab[i] == val:
dernier_indice = i
return dernier_indice
b.
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
c.
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).
b.
def contient_doublon_rapide(tab):
vus = set()
for element in tab:
if element in vus:
return True
vus.add(element)
return False
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¶
Objectif
Vérifier expérimentalement la complexité des algorithmes de recherche et de tri.
É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¶
Objectif
Implémenter l'algorithme KNN et tester son comportement avec différentes valeurs de k.
É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¶
Objectif
Montrer que l'algorithme glouton ne donne pas toujours la solution optimale.
É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)¶
Objectif
Utiliser l'algorithme KNN pour classifier automatiquement des fleurs d'iris à partir de leurs mesures.
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()