Programme officiel

Contenus	Capacités attendues	Commentaires
Recherche textuelle.	Étudier l’algorithme de Boyer- Moore pour la recherche d’un motif dans un texte.	L’intérêt du prétraitement du motif est mis en avant.L’étude du coût, difficile, ne peut être exigée

La recherche d’une sous-chaine a des applications importantes en informatiques, par exemple dans les moteurs de recherche. Nous commencerons par une application naïve puis nous verrons qu’il est bien plus efficace de faire la recherche en sens inverse en partant du dernier caractère du mot pour ne pas tester toutes les positions.

Nous allons visualiser la vidéo ci-dessous et effectuer les implémentation sous python en mettent la vidéo en pause, les solutions des programme python sont données plus loin dans l’article.

Algorithme naïf

Nous allons appliquer une méthode itérative brute pour rechercher une sous-chaine dans une chaine de caractères.

Nous allons avancer dans le texte caractère par caractère, puis si le caractère considéré correspond au premier caractère du mot, nous comparerons les caractères suivants à ceux du mot. si la recherche s’avère fructueuse on renvoie True.

implémentation algorithme naïf python corrigé

L’exécution est relativement lente, la fonction doit tester N-n positions dans texte et pour chacune effectuer jusqu’à N-n comparaisons, soit jusqu’à (N−n)×n.

La complexité de cet algorithme est dans le pire des cas O ((N−n)×n), c’est une complexité quadratique O(N²) car souvent  N>>n.

Nous allons voir qu’il est beaucoup plus efficace de faire la recherche à l’envers à partir de la fin du mot.

L’algorithme de Boyer-Moore : version simplifiée de Horspool

Nous allons étudier une version simplifiée du meilleur algorithme connu : l’algorithme de Boyer-Moore qui a été proposé par Nigel Horspool.

Cet algorithme repose sur deux idées :

1. On compare le mot de droite à gauche à partir de sa dernière lettre.
2. On n’avance pas dans le texte caractère par caractère, mais on utilise un décalage dépendant de la dernière comparaison effectuée.

Déroulement de l’algorithme

Nous considérons ici la recherche du motif mot = 'dab' dans le texte texte = 'abracadabra'.

On commence la recherche à l’index 2 :

abracadabra
dab

Il n’y a pas de correspondance à la fin du mot : 'r' != 'b', donc on avance, mais de combien de caractères avance-t-on. Pour le décider, on utilise le fait que le caractère 'r' n’apparait pas dans le mot cherché, donc on peut avancer de n = len(mot) = 3 caractères sans crainte de rater le mot.

On recherche donc à l’indice 2 + 3 = 5 :

abracadabra
   dab

Il n’y a pas de correspondance à la fin du mot : 'a' != 'b', donc on avance, cependant, cette fois, comme le caractère 'a' apparait pas dans le mot cherché en avant-dernière position, on ne peut avancer que de une case pour faire une comparaison en alignant les 'a'.

On recherche donc à l’indice 5 + 1 = 6 :

abracadabra
    dab

Il n’y a pas de correspondance à la fin du mot : 'd' != 'b', donc on avance, cependant, cette fois, comme le caractère 'd' apparait dans le mot cherché en avant-avant-dernière position(première position, mais on doit lire à l’envers !), on avance de deux cases pour faire une comparaison en alignant les 'd'.

On recherche donc à l’indice 6 + 2 = 8 :

abracadabra
      dab

Maintenant lorsqu’on effectue les comparaisons à l’envers : les 'b', puis les 'a', puis les 'd' correspondent. On a trouvé le mot on renvoie VRAI.

Implémentation en Python

Pour implémenter efficacement cet algorithme, on va passer par un pré-traitement du nom pour facilement accéder au décalage à effectuer. On utilise un dictionnaire pour cela.

Implémentation du pré-traitement python corrigé.

Maintenant la fonction de recherche :

Implémentation recherche en python corrigé.

Diviser pour régner

Le diviser pour régner est une méthode algorithmique basée sur le principe suivant :

On prend un problème (généralement complexe à résoudre), on divise ce problème en une multitude de petits problèmes, l’idée étant que les « petits problèmes » seront plus simples à résoudre que le problème original. Une fois les petits problèmes résolus, on recombine les « petits problèmes résolus » afin d’obtenir la solution du problème de départ.

Le paradigme « diviser pour régner » repose donc sur 3 étapes :

• DIVISER : le problème d’origine est divisé en un certain nombre de sous-problèmes
• RÉGNER : on résout les sous-problèmes (les sous-problèmes sont plus faciles à résoudre que le problème d’origine)
• COMBINER : les solutions des sous-problèmes sont combinées afin d’obtenir la solution du problème d’origine.

Les algorithmes basés sur le paradigme « diviser pour régner » sont très souvent des algorithmes récursifs.

Nous allons maintenant étudier un de ces algorithmes basés sur le principe diviser pour régner : le tri-fusion

Tri-fusion

Nous avons déjà étudié des algorithmes de tri : le tri par insertion et le tri par sélection. Nous allons maintenant étudier une nouvelle méthode de tri, le tri-fusion. Comme pour les algorithmes déjà étudiés, cet algorithme de tri fusion prend en entrée un tableau non trié et donne en sortie, le même tableau, mais trié.

À faire vous-même 1

Étudiez cet algorithme :

TRI FUSION (tableau):
• Si tableau est de taille <= 1 on ne fait rien.
• Sinon, On sépare tableau en 2 parties gauche et droite,
• On appelle Tri fusion sur gauche et sur droite
• On fusionne gauche et droite dans tableau

FUSIONNER (`tableau`, `gauche`, `droite`):
* On parcourt les deux tableaux `gauche` et `droite` en même temps,
Pour chaque paire d'éléments, on place le plus petit dans tableau.
* S'il reste des éléments dans `gauche` ou dans `droite` on les place à la fin
de tableau		

Pour trier un tableau A, on fait l’appel initial TRI-FUSION(A, 1, A.longueur)

Rappel : Attention, en algorithmique, les indices des tableaux commencent à 1

---

Cet algorithme est un peu difficile à appréhender, on notera qu’il est composé de deux fonctions FUSIONNER et TRI-FUSION (fonction récursive). La fonction TRI-FUSION assure la phase « DIVISER » et la fonction FUSION assure les phases « RÉGNER » et « COMBINER ».

Voici un exemple d’application de cet algorithme sur le tableau A = [23, 12, 4, 56, 35, 32, 42, 57, 3] :

À faire vous-même 2

Étudiez attentivement le schéma ci-dessous afin de mieux comprendre le principe du tri-fusion (identifiez bien les phases « DIVISER » et « COMBINER »).

---

On remarque que dans le cas du tri-fusion, la phase « RÉGNER » se réduit à sa plus simple expression, en effet, à la fin de la phase « DIVISER », nous avons à trier des tableaux qui comportent un seul élément, ce qui est évidemment trivial.

À faire vous-même 3

Reprenez tout le raisonnement qui vient d’être fait sur le tableau T = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]. Vous n’hésiterez pas à faire un schéma et à expliquer la fusion de 2 tableaux triés.

---

Nous avons vu que le tri par insertion et tri par sélection ont tous les deux une complexité O(n2)

. Qu’en est-il pour le tri-fusion ?

Le calcul rigoureux de la complexité de cet algorithme sort du cadre de ce cours. Mais, en remarquant que la première phase (DIVISER) consiste à « couper » les tableaux en deux plusieurs fois de suite, intuitivement, on peut dire qu’un logarithme base 2 doit intervenir. La deuxième phase consiste à faire des comparaisons entre les premiers éléments de chaque tableau à fusionner, on peut donc supposer que pour un tableau de n éléments, on aura n comparaisons. En combinant ces 2 constations on peut donc dire que la complexité du tri-fusion est en O(n.log(n))

(encore une fois la « démonstration » proposée ici n’a rien de rigoureux).

La comparaison des courbes de la fonction n2 (en rouge) et n.log(n)

(en bleu) :

nous montre que l’algorithme de tri-fusion est plus « efficace » que l’algorithme de tri par insertion ou que l’algorithme de tri par sélection.

Présentation vidéo détaillée du tri fusion

Utilisation du tri fusion:
Contrairement au tri par sélection ou par insertion, le tri fusion est réellement utilisé en pratique.
Il a de nombreux avantages :
• complexité optimale (cela ne signifie pas qu’il est le plus rapide)
• stable (voir plus bas)
• facile à mettre en œuvre
Cependant, il est possible d’améliorer la méthode :
timsort, le tri natif en Python et Javascript utilise une combinaison du tri fusion et du tri par insertion.

Exercices Diviser pour régner

---

FICHE REVISION

Auteur : David Roche

---

Présentation des d’algorithmes gloutons avec exemples et TD. cet article est une copie d’un article du site www.math93.com/ , vous pouvez le voir ici .

Voici une petite vidéo sur les algorithmes Glouton

1. Présentation de la notion d’algorithme glouton.
   1. Les problèmes d’optimisation.
   2. Résoudre un problème d’optimisation : les algorithmes gloutons
2. Le problème du rendu de monnaie.
3. Le TD sur les algorithmes gloutons et le rendu de monnaie.

1. Présentation de la notion d’algorithme glouton

---

1.1. Les problèmes d’optimisation

L’optimisation est une branche des mathématiques cherchant à modéliser, à analyser et à résoudre les problèmes qui consistent à minimiser ou maximiser une fonction sur un ensemble.

Les problèmes d’optimisation classiques sont par exemple : 

1.2. Résoudre un problème d’optimisation : les algorithmes gloutons

De nombreuses techniques informatiques sont susceptibles d’apporter une solution exacte ou approchée à ces problèmes.

2. Le problème du rendu de monnaie

---

Un achat dit en espèces se traduit par un échange de pièces et de billets. Dans la suite, les pièces désignent indifféremment les véritables pièces que les billets.

Supposons qu’un achat induise un rendu de 49 euros on considérant pour simplifier que les ‘pièces’ prennent les valeurs 1, 2, 5, 10, 20, 50, 100 euros. Quelles pièces peuvent être rendues ?

soit 7 pièces au total
(Quatre pièces de 10 euros, 1 pièce de 5 euros et deux pièces de 2 euros.) ou 49=9×5+2×2  soit 11 pièces au total ou 49=9×5+4×1  soit 13 pièces au total ou 49=49×1

Le problème du rendu de monnaie consiste à déterminer la solution avec le nombre minimal de pièces.

Rendre 49 euros avec un minimum de pièces est un problème d’optimisation. En pratique, tout individu met en œuvre un algorithme glouton.

1. Il choisit d’abord la plus grandeur valeur de monnaie, parmi 1, 2, 5, 10, contenue dans 49 euros.
   En l’occurrence, quatre fois une pièce de 10 euros.
2. La somme de 9 euros restant à rendre, il choisit une pièce de 5 euros,
3. Puis deux pièces de 2 euros.

Solution optimale et système canonique du rendu de monnaie

Cette stratégie gagnante pour la somme de 49 euros l’est-elle pour n’importe quelle somme à rendre ?

3. Le TD sur les algorithmes gloutons et le rendu de monnaie

On cherche à implémenter un algorithme glouton de rendu de monnaie en ne considérant que des valeurs entières des pièces du système.
Par ailleurs, la plus petite pièce du système sera toujours 1, on est ainsi certain de pouvoir rendre la monnaie quelque soit la somme choisie.

Fonctionnement de l’algorithme glouton du rendu de monnaie

1. On choisit un système de monnaies, par exemple  systeme=[1,2,5,10,20,50,100]
2. On choisit une valeur, par exemple valeur=49 euros .
3. On choisit la plus grande ‘pièce’ du système inférieure à la valeur et on l’ajoute à la liste des pièces à rendre.
4. On calcule le reste à rendre et on recommence jusqu’à obtenir un reste à rendre nul.

 

Exercice 1

1. Écrire une une fonction python qui reçoit deux arguments – la somme à rendre et le système de monnaie – et qui renvoie la liste des pièces choisies par l’algorithme glouton.
2. Tester votre fonction avec les valeurs et les systèmes proposés dans les exemples du cours ci-dessus.
3. Inventez un système non canonique différent de celui de l’exemple (mais toujours de valeur minimale 1) et trouver un exemple qui le prouve.
   Votre fonction devra donc donner une solution mais qui n’est pas optimale.
4. Complément : créer un programme (ou une autre fonction) qui va afficher toutes les informations suivantes :
   49=4×10+1×5+2×2
   Soit 7 pièces au total
   C’est à dire : Quatre pièces de 10 euros, 1 pièce de 5 euros et deux pièces de 2 euros.

---

Aide pour l’exercice 1:

# valeurs des pièces du système choisi
systeme = [1,2,5,10,20,50,100]
# valeur à tester (par exemple 49 euros)
valeur=49
# indice de la première pièce à comparer à la somme à rendre
i = len(systeme) - 1

---

Exercice 2

1. Modifier donc votre programme afin qu’il affiche le nombre les pièces à rendre et les billets.
2. Tester les avec plusieurs exemples.
3. Et si il n’y avait ni billet de 5, ni billet de 10 euros.
   Montrer avec un exemple bien choisi que la solution donnée par l’algorithme n’est pas optimale

Exercice 3 – Une pièce de 7 euros

1. Tester votre algorithme en ajoutant une pièce de 7 euros dans le système.
2. Trouver un exemple qui renvoie une solution qui n’est pas optimale.

1. Introduction
   L’algorithme des k plus proches voisins appartient à la famille des algorithmes d’apprentissage automatique (machine learning).
   L’idée d’apprentissage automatique ne date pas d’hier, puisque le terme de machine learning a été utilisé pour la première fois par
   l’informaticien américain Arthur Samuel en 1959. Les algorithmes d’apprentissage automatique ont connu un fort regain d’intérêt
   au début des années 2000 notamment grâce à la quantité de données disponibles sur internet.
   L’algorithme des k plus proches voisins est un algorithme d’apprentissage supervisé, il est nécessaire d’avoir des données labellisées. À partir d’un ensemble E de données labellisées, il sera possible de classer (déterminer le label) d’une nouvelle donnée (donnée n’appartenant pas à E). À noter qu’il est aussi possible d’utiliser l’algorithme des k plus proches voisins à des fins de régression (on cherche à déterminer une valeur à la place d’une classe), mais cet aspect des choses ne sera pas abordé ici. L’algorithme des k plus proches voisins est une bonne introduction aux principes des algorithmes d’apprentissage automatique, il est en effet relativement simple à appréhender (l’explication donnée aux élèves peut être très visuelle). Cette première approche des algorithmes d’apprentissage peut aussi amener les élèves à réfléchir sur l’utilisation de leurs données personnelles (même si ce sujet a déjà abordé auparavant) : de nombreuses sociétés (exemple les GAFAM) utilisent les données concernant leurs utilisateurs afin de ”nourrir” des algorithmes de machine learning qui permettront à ces sociétés d’en savoir toujours plus sur nous et ainsi de mieux cerné nos ”besoins” en termes de consommation.

2. Principe de l’algorithme
   L’algorithme de k plus proches voisins ne nécessite pas de phase d’apprentissage à proprement parler, il faut juste stocker le jeu de
   données d’apprentissage.
   Soit un ensemble E contenant n données labellisées : E = {(yi
   , x⃗i)} avec i compris entre 1 et n, où yi correspond à la classe
   (le label) de la donnée i et où le vecteur x⃗i de dimension p (x⃗i = (x1i
   , x2i, …, xpi)) représente les variables prédictrices de la donnée i. Soit une donnée u qui n’appartient pas à E et qui ne possède pas de label (u est uniquement caractérisée par un vecteur x⃗u de dimension p). Soit d une fonction qui renvoie la distance entre la donnée u et une donnée quelconque appartenant à E. Soit un entier k inférieur ou égal à n. Voici le principe de l’algorithme de k plus proches voisins :
   ▷ On calcule les distances entre la donnée u et chaque donnée appartenant à E à l’aide de la fonction d
   ▷ On retient les k données du jeu de données E les plus proches de u
   ▷ On attribue à u la classe qui est la plus fréquente parmi les k données les plus proches.

3. Étude d’un exemple
   3.1. Les données
   Nous avons choisi ici de nous baser sur le jeu de données ”iris de Fisher” (il existe de nombreuses autres possibilités). Ce jeu de
   données est composé de 50 entrées, pour chaque entrée nous avons :
   ▷ la longueur des sépales (en cm)
   ▷ la largeur des sépales (en cm)
   ▷ la longueur des pétales (en cm)
   ▷ la largeur des pétales (en cm)
   ▷ l’espèce d’iris : Iris setosa, Iris virginica ou Iris versicolor (label)
   Il est possible de télécharger ces données au format csv, par exemple sur le site GitHub Gist ou en le téléchargeant ici
   Une fois ces données téléchargées, Il est nécessaire de les modifier à l’aide d’un tableur :
   ▷ dans un souci de simplification, nous avons choisi de travailler uniquement sur la taille des pétales, nous allons donc supprimer les colonnes ”sepal_length” et ”sepal_width”
   ▷ il est nécessaire d’encoder les espèces avec des chiffres : 0 pour Iris setosa, 1 pour Iris virginica et 2 pour Iris versicolor (ce
   processus d’encodage des données textuelles est relativement classique en apprentissage automatique).
   3.2. Bibliothèques Python utilisées
   Nous allons utiliser 3 bibliothèques Python :
   ▷ Pandas [3] qui va nous permettre d’importer les données issues du fichier csv
   ▷ Matplotlib [4] qui va nous permettre de visualiser les données (tracer des graphiques)
   ▷ Scikit-learn [5] qui propose une implémentation de l’algorithme des k plus proches voisins.
   Ces bibliothèques sont facilement installables notamment en utilisant la distribution Anaconda (ou Miniconda).
   3.3. Première visualisation des données
   Une fois le fichier csv modifié, il est possible d’écrire un programme permettant de visualiser les données sous forme de graphique
   (abscisse : ”petal_length”, ordonnée : ”petal_width”) :
   

import pandas
import matplotlib.pyplot as plt
iris=pandas.read_csv("iris.csv")
x=iris.loc[:,"petal_length"]
y=iris.loc[:,"petal_width"]
lab=iris.loc[:,"species"]
plt.scatter(x[lab == 0], y[lab == 0], color='g', label='setosa')
plt.scatter(x[lab == 1], y[lab == 1], color='r', label='virginica')
plt.scatter(x[lab == 2], y[lab == 2], color='b', label='versicolor')
plt.scatter(2.5, 0.75, color='k')
plt.legend()
plt.show()

3.4. Utilisation de l’algorithme des k plus proches voisins Le graphique ci-dessus (figure 1) montre que les 3 classes (Iris setosa, Iris virginica et Iris versicolor) sont relativement bien séparées. On peut alors ajouter une donnée non labellisée n’appartenant pas à l’ensemble d’origine (voir figure 2) :

Dans l’exemple ci-dessus (figure 2) les élèves n’auront aucune difficulté à déterminer l’espèce de l’iris qui a été ajouté au jeu de données.
Dans certains cas (exemple : largeur pétale = 0,75 cm ; longueur pétale = 2,5 cm) il est un peu plus difficile de se prononcer ”au premier coup d’oeil” (voir figure 3) :

À partir de l’exemple ci-dessus (voir figure 3), il est possible de demander aux élèves de proposer une méthode permettant de traiter
ce genre de cas litigieux. L’enseignant peut, grâce à une série de ”questions-réponses”, amener doucement les élèves à la solution
proposée par l’algorithme des k plus proches voisins :
▷ on calcule la distance entre notre point (largeur du pétale = 0,75 cm ; longueur du pétale = 2,5 cm) et chaque point issu du
jeu de données ”iris” (à chaque fois c’est un calcul de distance entre 2 points tout ce qu’il y a de plus classique) ;
▷ on sélectionne uniquement les k distances les plus petites (les k plus proches voisins) ;

▷ parmi les k plus proches voisins, on détermine quelle est l’espèce majoritaire. On associe à notre ”iris mystère” cette ”espèce
majoritaire parmi les k plus proches voisins”.
Dans l’exemple évoqué ci-dessus (largeur pétale = 0,75 cm ; longueur pétale = 2,5 cm), pour k=3, nous obtenons graphiquement :

Un iris ayant une largeur de pétale égale à 0,75 cm et une longueur de pétale égale à 2,5 cm a une ”forte” probabilité (cette notion
de probabilité d’obtenir un résultat correct grâce à cet algorithme, bien que très intéressante, pourra difficilement être abordée avec
des élèves de première) d’appartenir à l’espèce setosa.

3.5. Utilisation de scikit-learn (à installer si absente de votre éditeur)
La bibliothèque Python scikit-learn propose un grand nombre d’algorithmes lié à l’apprentissage automatique (c’est sans aucun
doute la bibliothèque la plus utilisée en apprentissage automatique). Parmi tous ces algorithmes, scikit-learn propose l’algorithme
des k plus proches voisins. Voici un programme Python permettant de résoudre le problème évoqué ci-dessus (largeur pétale = 0,75
cm ; longueur pétale = 2,5 cm) :

import pandas
import matplotlib.pyplot as plt
from sklearn.neighbors import KNeighborsClassifier

#traitement CSV
iris=pandas.read_csv("iris.csv")
x=iris.loc[:,"petal_length"]
y=iris.loc[:,"petal_width"]
lab=iris.loc[:,"species"]
#fin traitement CSV

#valeurs
longueur=2.5
largeur=0.75
k=3
#fin valeurs

#graphique
plt.scatter(x[lab == 0], y[lab == 0], color='g', label='setosa')
plt.scatter(x[lab == 1], y[lab == 1], color='r', label='virginica')
plt.scatter(x[lab == 2], y[lab == 2], color='b', label='versicolor')
plt.scatter(longueur, largeur, color='k')
plt.legend()
#fin graphique

#algo knn
d=list(zip(x,y))
model = KNeighborsClassifier(n_neighbors=k)
model.fit(d,lab)
prediction= model.predict([[longueur,largeur]])
#fin algo knn

#Affichage résultats
txt="Résultat : "
if prediction[0]==0:
    txt=txt+"setosa"
if prediction[0]==1:
    txt=txt+"virginica"
if prediction[0]==2:
    txt=txt+"versicolor"
plt.text(3,0.5, f"largeur : {largeur} cm longueur : {longueur} cm", fontsize=12)
plt.text(3,0.3, f"k : {k}", fontsize=12)
plt.text(3,0.1, txt, fontsize=12)
#fin affichage résultats

plt.show()

Nous obtenons le résultat suivant (voir figure 5) :

Il est ensuite possible de demander aux élèves de m le programme ci-dessus afin d’étudier les changements induits par la
modification du paramètre k (notamment pour k=5) en gardant toujours les mêmes valeurs de largeur et de longueur (largeur pétale
= 0,75 cm ; longueur pétale = 2,5 cm).
Pour terminer, il est aussi possible de demander aux élèves de travailler avec d’autres valeurs de longueur et largeur.

4. Possibilité de projet
   Il est possible, dans le cadre d’un projet, de faire travailler les élèves sur un autre jeu de données, par exemple, ”Prédire les survivants
   du Titanic”. Le jeu de données peut être récupéré sur le site kaggle [6]. Le label est ”survivant” ou ”décédé”. Il sera nécessaire de
   retravailler les données comme nous l’avons fait pour le jeu de données ”Iris” (supprimer des colonnes, encodage…). Dans ce projet
   il sera possible de faire travailler les élèves sur des vecteurs d’entrée de dimension supérieure à 2 (le genre, l’âge, la classe occupée
   par le passager sur le bateau, …).

voici un lien vers le projet Titanic développé par Benoit Fourlegnie:

projet titanic