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.
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(N2) 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 :
On compare le mot de droite à gauche à partir de sa dernière lettre.
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.
Etudions d’abord l’algorithme de la fusion de 2 listes:
FUSIONNER (`liste_gauche`, `liste_droite`): * On parcourt les deux listes `gauche` et `droite` en même temps, Pour chaque paire d’éléments, on place le plus petit dans liste resultat. * S’il reste des éléments dans `gauche` ou dans `droite` on les place à la fin de liste resultat
Développement graphique:
Soit 2 listes à fusionner:
Liste gauche : [3, 1, 4, 7, 8] et la liste droite : [2, 5, 6]
implémenter sous pyzo la fonction FUSIONNE donc voici le début:
def fusionne(lst1, lst2):
"""
list1 est une liste
list2 est une liste
la fonction retourne une liste resultat fusion des 2 listes list1 et list2
Example
-------
>>> fusionne([3, 1, 4, 7, 8], [2, 5, 6])
# listes non ordonnées
[2, 3, 1, 4, 5, 6, 7, 8]
>>> fusionne([1, 3, 4, 7, 8], [2, 5, 6])
# listes ordonnées
[1, 2, 3, 4, 5, 6, 7, 8]
"""
Maintenant regardons l’algorithme de la fonction TRI FUSION
TRI FUSION (liste): • Si liste est de taille <= 1 on ne fait rien. • Sinon, On sépare liste en 2 parties gauche et droite, • On appelle Tri fusion sur gauche et sur droite • On fusionne gauche et droite dans liste
Développement graphique :
Soit la liste [2, 3, 1, 4, 5, 6, 7, 8] à trier par fusion
on sépare d’abord :
et on fusionne avec la fonction FUSIONNE décrite juste avant:
implémenter cette fonction
def fusionne(lst1, lst2):
"""
list1 est une liste
list2 est une liste
la fonction retourne une liste resultat fusion des 2 listes list1 et list2
Example
-------
>>> fusionne([3, 1, 4, 7, 8], [2, 5, 6])
# listes non ordonnées
[2, 3, 1, 4, 5, 6, 7, 8]
>>> fusionne([1, 3, 4, 7, 8], [2, 5, 6])
# listes ordonnées
[1, 2, 3, 4, 5, 6, 7, 8]
"""
def tri_fusion(lst):
'''lst est une liste non triées
Elle est coupé en 2 listes gauche et droite par le milieu (ou presque si taille impaire),
puis la fonction tri_fusion est rappelée pour chaque liste gauche et droite, jusqu'à n'obtenir des listes de taille 1.
en fin on applique la fonction fusionne les listes gauche et droite dans une liste que la fonction renvoie.
Exemple:
>>> tri_fusion([2, 3, 1, 4, 5, 6, 7, 8])
[1, 2, 3, 4, 5, 6, 7, 8]'''''
voici un programme pour créer des listes triées ou aléatoire pour faire des tests:
import random
def liste_triee(nb):#Création d'une liste trièe dans l'ordre croissant de nb valeur
nmax=nb
L=[]
for i in range(0,nmax):
L.append(i)
return L
def liste_aleatoire(nb):# fabrication d'une liste de nb valeurs aléatoires
nmax=nb
L=[]
for i in range(0,nmax):
L.append(random.randint(0,nmax))
return L
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.
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.
Le but de ce projet est d’implémenter en Python les algorithmes sur les arbres binaires précédemment étudiés. Il sera donc sans doute nécessaire de reprendre ce qui a été vu sur la structure de données « arbre » et sur « les algorithmes sur les arbres binaires ».
Comme nous l’avons déjà dit, Python ne propose pas de structure de données permettant d’implémenter directement les arbres binaires. Il va donc être nécessaire de créer cette structure. Pour programmer ce type de structure, nous allons utiliser le paradigme objet (à voir si pas encore étudier paradigme objet)
Vous trouverez ci-dessous la classe « ArbreBinaire » qui va nous permettre d’implémenter des arbres binaires.
Étudiez attentivement la classe « ArbreBinaire » (méthodes et attributs). Vous pouvez, par exemple, vous interroger sur l’utilité de toutes les méthodes de cette classe.
Voici un exemple d’utilisation de cette classe pour construire un arbre binaire :
Soit l’arbre binaire suivant : Arbre 1
Voici le programme qui va permettre de construire cet arbre à l’aide de la classe « ArbreBinaire » :
class ArbreBinaire:
def __init__(self, valeur):
self.valeur = valeur
self.enfant_gauche = None
self.enfant_droit = None
def insert_gauche(self, valeur):
if self.enfant_gauche == None:
self.enfant_gauche = ArbreBinaire(valeur)
else:
new_node = ArbreBinaire(valeur)
new_node.enfant_gauche = self.enfant_gauche
self.enfant_gauche = new_node
def insert_droit(self, valeur):
if self.enfant_droit == None:
self.enfant_droit = ArbreBinaire(valeur)
else:
new_node = ArbreBinaire(valeur)
new_node.enfant_droit = self.enfant_droit
self.enfant_droit = new_node
def get_valeur(self):
return self.valeur
def get_gauche(self):
return self.enfant_gauche
def get_droit(self):
return self.enfant_droit
#######fin de la classe########
######début de la construction de l'arbre binaire###########
racine = ArbreBinaire('A')
racine.insert_gauche('B')
racine.insert_droit('F')
b_node = racine.get_gauche()
b_node.insert_gauche('C')
b_node.insert_droit('D')
f_node = racine.get_droit()
f_node.insert_gauche('G')
f_node.insert_droit('H')
c_node = b_node.get_gauche()
c_node.insert_droit('E')
g_node = f_node.get_gauche()
g_node.insert_gauche('I')
h_node = f_node.get_droit()
h_node.insert_droit('J')
######fin de la construction de l'arbre binaire###########
À faire vous-même 2
Étudiez attentivement le programme ci-dessus afin de comprendre le principe de « construction d’un arbre binaire »
Il est possible d’afficher un arbre binaire dans la console Python, pour cela, nous allons écrire une fonction « affiche ». Cette fonction renvoie une série de tuples de la forme (valeur,arbre_gauche, arbre_droite), comme « arbre_gauche » et « arbre_droite » seront eux-mêmes affichés sous forme de tuples, on aura donc un affichage qui ressemblera à : (valeur,(valeur_gauche,arbre_gauche_gauche,arbre_gauche_droite),(valeur_droite,arbre_droite_gauche,arbre_droite_droite)), mais comme « arbre_gauche_gauche » sera lui-même représenté par un tuple… Nous allons donc avoir des tuples qui contiendront des tuples qui eux-mêmes contiendront des tuples…
N.B : la fonction « affiche » n’a pas une importance fondamentale, elle sert uniquement à vérifier que les arbres programmés sont bien corrects.
À faire vous-même 4
Programmez à l’aide de la classe « ArbreBinaire », l’arbre binaire suivant :
Arbre 2
Vérifiez votre programme à l’aide de la fonction « affiche »
Vous allez maintenant pouvoir commencer à travailler sur l’implémentation des algorithmes sur les arbres binaires :
À faire vous-même 5
Programmez la fonction « hauteur » qui prend un arbre binaire T en paramètre et renvoie la hauteur de T (algorithme correspondant, voir ici)
Testez votre fonction en utilisant l’arbre vu plus haut (schéma « Arbre 1 »).
À faire vous-même 6
Programmez la fonction « taille » qui prend un arbre binaire T en paramètre et renvoie la taille de T (algorithme correspondant, voir ici)
Testez votre fonction en utilisant l’arbre vu plus haut (schéma « Arbre 1 »).
À faire vous-même 7
Programmez la fonction « parcours_infixe » qui prend un arbre binaire T en paramètre et qui permet d’obtenir le parcours infixe de l’arbre T (algorithme correspondant, voir ici)
Testez votre fonction en utilisant l’arbre vu plus haut (schéma « Arbre 1 »).
À faire vous-même 8
Programmez la fonction « parcours_prefixe » qui prend un arbre binaire T en paramètre et qui permet d’obtenir le parcours préfixe de l’arbre T (algorithme correspondant, voir ici)
Testez votre fonction en utilisant l’arbre vu plus haut (schéma « Arbre 1 »).
À faire vous-même 9
Programmez la fonction « parcours_suffixe » qui prend un arbre binaire T en paramètre et qui permet d’obtenir le parcours suffixe de l’arbre T (algorithme correspondant, voir ici)
Testez votre fonction en utilisant l’arbre vu plus haut (schéma « Arbre 1 »).
À faire vous-même 10
Programmez la fonction « parcours_largeur » qui prend un arbre binaire T en paramètre et qui permet d’obtenir le parcours en largeur de l’arbre T (algorithme correspondant, voir ici)
Testez votre fonction en utilisant l’arbre vu plus haut (schéma « Arbre 1 »).
Nous allons maintenant travailler sur les arbres binaires de recherche.
À faire vous-même 11
Programmez, à l’aide de la classe « ArbreBinaire », l’arbre binaire de recherche ci-dessous : Arbre 3
Vérifiez votre réponse à l’aide de la fonction « affichage »
À faire vous-même 12
Afin de vérifier que l’arbre binaire « Arbre 3 » est bien un arbre binaire de recherche, utilisez la fonction « parcours_infixe » programmée dans le « À faire vous-même 7 ».
À faire vous-même 13
Programmez la fonction « arbre_recherche » qui prend un arbre binaire T et un entier k en paramètres et qui renvoie True si k appartient à T et False dans le cas contraire (algorithme correspondant, voir ici)
Testez votre fonction en utilisant l’arbre vu plus haut (schéma « Arbre 3 ») avec k = 13 et k = 16.
À faire vous-même 14
Programmez la fonction « arbre_recherche_ite » (version itérative de la fonction « arbre_recherche ») qui prend un arbre binaire T et un entier k en paramètres et qui renvoie True si k appartient à T et False dans le cas contraire (algorithme correspondant, voir ici)
Testez votre fonction en utilisant l’arbre vu plus haut (schéma « Arbre 3 ») avec k = 13 et k = 16.
À faire vous-même 15
Programmez la fonction « arbre_insertion » qui prend T (un arbre binaire) et y (un objet de type « ArbreBinaire ») en paramètres et qui insert y dans T (algorithme correspondant, voir ici)
Testez votre fonction en utilisant l’arbre vu plus haut (schéma « Arbre 3 ») avec y.valeur = 16.
Ces exercices vous permettront de vous entrainer en vue de l’évaluation sur la programmation.
Exercice 1
On dispose de la formule suivante pour convertir les degrés Fahrenheit en degrés Celsius : C = 0,55556 × (F – 32)
où F est une température en degrés Fahrenheit et C la température correspondante en degrés Celsius. 1. Ecrire un programme qui convertit en degrés Celsius une température rentrée au clavier en degrés Fahrenheit. 2. Même question pour la conversion inverse.
Exercice 2
Écrire un programme qui affiche un triangle rempli d’étoiles (*) sur un nombre de lignes donné passé en paramètre, exemple :
• 1ère version : à l’aide de deux boucles for, en imprimant les * une par une.
On remarquera que, par défaut dans l’instruction print() , figure end = ‘\n’, qui fait passer à la ligne.
print(…, end =’’) ne fera donc pas passer à la ligne.
• 2ème version : avec une seul boucle for, et une chaîne de caractères où vous accumulerez des étoiles (pour ceux qui vont un peu plus vite, print(« machin » end= ‘’) évite de passer à la ligne.
Exercice 3
Programmation d’un petit jeu de devinette. L’ordinateur choisit au hasard un nombre compris entre 1 et 100.
Le but du jeu est de le deviner en un nombre d’essai minimal. À chaque tentative, l’ordinateur, indique « gagné », « trop petit » ou « trop grand ». L’utilisateur dispose d’un nombre d’essais limités.
Écrire l’algorithme en « langage naturel ». Programmer le jeu, et le tester.
Remarque : on utilisera la bibliothèque random. Pour cela, on écrit « import random » en début de programme. nombre = random.randint(a, b) renverra un nombre aléatoire tel que a ≤ Nombre ≤ b
Exercice 4
Convertir une note scolaire N quelconque, entrée par l’utilisateur sous forme de points (par exemple 27 sur 85), en une note standardisée suivant le code ci-dessous :
Note N
Appréciation
N >= 80 %
A
80 % > N >= 60 %
B
60 % > N >= 50 %
C
50 % > N >= 40 %
D
N < 40 %
E
Exercice 5
Ecrire un programme qui affiche les carrés des entiers de 1 à 7 .
Exercice 6
Ecrire un programme qui affiche n fois la suite de symboles suivante : A #Si n=1 AA #si n=2 AAA etc…sans utiliser le * comme par exemple print(3* »A »).
n est donné par l’utilisateur.
Exercice 7
Ecrire un programme qui demande un prénom. Si ce prénom est Paul, le programme affiche « enfin c’est toi », sinon le programme redemande un nouveau prénom car ce n’est pas la personne qu’il attend (un genre de mot de passe non ?).
Exercice 8
Ecrire un programme qui additionne tous les nombres que vous entrez (tour à tour) et qui s’arrête lorsque la somme dépasse 100.
On considère deux jeux de 54 cartes à jouer. Pour les mélanger, on créer un troisième paquet en empilant les cartes aléatoirement piochées dans un des deux jeux. Quand l’un des deux jeux est vide, on empile le jeu restant sur le troisième paquet. On modélisera les deux jeux de 54 cartes par deux listes contenant respectivement les entiers de 101 à 154 et de 201 à 254. Écrire une fonction python qui réalise le mélange.
Exercice 2 (Bataille, pile)
On considère un jeu de 52 cartes à jouer (pas de joker) que l’on modélise par une liste contenant quatre fois les entiers de 1 à 13. La valeur d’une carte est égale à son numéro. On distribue ensuite aléatoirement 13 cartes à quatre joueurs qui les empilent consciencieusement devant eux. A chaque tour de jeu, les quatre joueurs posent la carte au sommet de leur pile au milieu. Celui qui a la carte la plus forte remporte le pli, c’est à dire les quatre cartes du tour. S’il y a égalité, on tire au sort le joueur qui gagne rafle le pli. Le joueur qui a la fin a le plus de points gagne la partie. Écrire un programme Python qui simule ce jeu.
Exercice 3 (La bonne syntaxe,pile)
L’analyse syntaxique est une phase indispensable de la compilation des programmes. Les piles sont particulièrement bien adaptées à ce genre de traitements. On va se limiter à la reconnaissance des expressions bien parenthésés. Nous devons écrire un programme qui :—accepte les expressions comme (a), (a b)((c d e)) ou (((a)(b c d))(e)) où a, b, etc. sont des expressions quelconques sans parenthèses—rejette les expressions comme a )(, (a b)((c) ou (((a b)(c d e f))))On remarque d’abord que les expressions a, b, c .. qui apparaissent n’ont aucune importance pour savoir si l’expression est bien parenthésée. On va lire l’expression sous la forme d’une chaine de caractères et utiliser une pile. Lors de la lecture dela chaine, on empile les ”(”. Pour les ”)”, on vérifie d’abord si le sommet de la pile est ”(”, dans ce cas, on dépile. Sinon, on empile le ”(”. A la fin de l’algorithme, si l’expression est bien parenthésée, la pile est vide.Écrire un algorithme utilisant une pile et ses primitives.
Exercice 4 (Évaluation d’une expression arithmétique, pile)
Nous allons voir ici une utilisation des piles pour évaluer des expressions arithmétiques.Par exemple, on souhaite évaluer(3×(5+2×3)+4)×2On se contentera d’évaluer des expressions correctement écrites avec seulement des nombres à un seul chiffre et uniquement des sommes et des produits.
1. On commence par écrire l’expression en notation ”postfixé” ou inverse polonaise Dans cette notation, on écrit les opérations après les nombres plutôt qu’avant.Par exemple,2+3s’écrira2,3,+
Ecrire l’expression(3×(5+2×3)+4)×2 en postfixé.
2. En lisant de gauche à droite l’expression postfixé, on construit une Pile suivant les règles suivantes :—Si on lit un nombre, on l’empile—Si on lit une opération, on dépile deux nombres et on effectue l’opération entre ces deux nombres
3. Ecrire en pseudo code, une séquence qui permet d’évaluer l’expression.
4. Implémenter l’algorithme en python.
Exercice 5 (file)
Dans un supermarché il y a 5 caisses et une file d’attente commune. Dès qu’une caisse est libre, le client en tête de file y est envoyé. Le temps de passage en caisse est aléatoirement compris entre 3 et 10 minutes. Il y a dix clients dans la file d’attente.
1. Réaliser une simulation de leurs passages en caisses et afficher en combien de minutes tous les clients sont passés.
2. Refaire quelques essais avec plus de clients.
Pour la file d’attente , vous utiliserez une file avec l’objet deque sous python, voir description objet deque ici.
Par exemple voici la liste d’attente:
from collections import deque #import container deque
file_attente=['1','2','3','4','5','6','7','8','9','10'] #la liste d'attente commune avec 10 clients
d = deque(file_attente) #création file client
Retire et renvoie un élément de l’extrémité droite de la deque. S’il n’y a aucun élément, lève une exception IndexError.
popleft()
Retire et renvoie un élément de l’extrémité gauche de la deque. S’il n’y a aucun élément, lève une exception IndexError.
Pour la liste des caisses, vous utiliserez une liste [0,0,0,0,0], premier élément temps caisse 1, ici à 0, puis temps caisse 2 ou un dictionnaire {1: 0, 2: 0, 3: 0, 4: 0, 5: 0}, clé 1 = caisse 1 avec sa valeur = temps ici à 0.
Exercice 6
Un poste de contrôle est alimenté en pièces toutes les 7 minutes. Ces pièces sont de quatre types qui nécessitent respectivement
4, 6, 8 et 9 minutes pour être contrôlés. Les fréquences des quatre types sont identiques.
1. A l’aide d’une file, simuler le fonctionnement du poste de contrôle pendant 1 heure, puis 80 heures.
2. Calculer le nombre de pièces en attente de contrôle
3. Déterminer la durée de séjour des pièces dans le poste de contrôle. Afficher celle de la dernière
4. Le contrôleur fait une pause de 15 minutes toutes les 4 heures. Déterminer le nombre d’heures effectives de travail.
Exercice 7
Un restaurant de 50 tables à 2 couverts ouvre ses portes pendant 4 heures chaque soir. L’intervalle de temps entre l’arrivée de deux groupes de clients est d’environ 2 minutes. Les groupes sont constitués aléatoirement de 2 à 6 convives avec des fréquences identiques.
Les tables peuvent être rassemblées pour les groupes de plus de 2 personnes. Lorsqu’un groupe arrive, il attend que des tables en nombre suffisant soient libres.
Une fois assis, le groupe reste pendant une durée aléatoirement comprise entre 60 et 120 minutes.
Simuler le fonctionnement du restaurant pendant une soirée.
Afficher le nombre de clients servis lors d’un service et nombre moyen de clients par table.
Exercice 2 du sujet 10 de l’épreuve pratique de 2021
Faire l’exercice 2 du Sujet n°10 de l’épreuve pratique de 2021
Beaucoup de tournoi sportif sont organisés avec une structure qui représente les matchs joués ou à jouer dans le tournoi. Le principe de base est que chaque branche rassemble deux joueurs (ou deux équipes). Le gagnant avance et le perdant est éliminé. C’est en tout cas le fonctionnement avec élimination Directe.
Ce graphique si on commence par le vainqueur ressemble à un arbre.
Nous avons ci-dessous ce que l’on appelle une structure en arbre. On peut aussi retrouver cette même structure dans un arbre généalogique :
Dernier exemple, les systèmes de fichiers dans les systèmes de type UNIX ont aussi une structure en arbre.système de fichiers de type UNIX
Les arbres sont des types abstraits très utilisés en informatique. On les utilise notamment quand on a besoin d’une structure hiérarchique des données : dans l’exemple ci-dessous le fichier grub.cfg ne se trouve pas au même niveau que le fichier rapport.odt (le fichier grub.cfg se trouve « plus proche » de la racine / que le fichier rapport.odt). On ne pourrait pas avec une simple liste qui contiendrait les noms des fichiers et des répertoires, rendre compte de cette hiérarchie (plus ou moins « proche » de la racine). On trouve souvent dans cette hiérarchie une notion de temps (les quarts de finale sont avant les demi-finales ou encore votre grand-mère paternelle est née avant votre père), mais ce n’est pas une obligation (voir l’arborescence du système de fichiers).
Les arbres binaires sont des cas particuliers d’arbre : l’arbre du tournoi de rugby et l’arbre « père, mère… » sont des arbres binaires, en revanche, l’arbre représentant la structure du système de fichier n’est pas un arbre binaire. Dans un arbre binaire, on a au maximum 2 branches qui partent d’un élément (pour le système de fichiers, on a 7 branches qui partent de la racine : ce n’est donc pas un arbre binaire). Dans la suite nous allons uniquement travailler sur les arbres binaires.
Soit l’arbre binaire suivant :
Un peu de vocabulaire :
chaque élément de l’arbre est appelé noeud (par exemple : A, B, C, D,…,P et Q sont des noeuds)
le noeud initial (A) est appelé noeud racine ou plus simplement racine
On dira que le noeud E et le noeud D sont les fils du noeud B. On dira que le noeud B est le père des noeuds E et D
Dans un arbre binaire, un noeud possède au plus 2 fils
Un noeud n’ayant aucun fils est appelé feuille (exemples : D, H, N, O, J, K, L, P et Q sont des feuilles)
À partir d’un noeud (qui n’est pas une feuille), on peut définir un sous-arbre gauche et un sous-arbre droite (exemple : à partir de C on va trouver un sous-arbre gauche composé des noeuds F, J et K et un sous-arbre droit composé des noeuds G, L, M, P et Q)
On appelle arête le segment qui relie 2 noeuds.
On appelle profondeur d’un nœud ou d’une feuille dans un arbre binaire le nombre de nœuds du chemin qui va de la racine à ce nœud. La racine d’un arbre est à une profondeur 1, et la profondeur d’un nœud est égale à la profondeur de son prédécesseur plus 1. Si un noeud est à une profondeur p, tous ses successeurs sont à une profondeur p+1. Exemples : profondeur de B = 2 ; profondeur de I = 4 ; profondeur de P = 5 ATTENTION : on trouve aussi dans certains livres la profondeur de la racine égale à 0 (on trouve alors : profondeur de B = 1 ; profondeur de I = 3 ; profondeur de P = 4). Les 2 définitions sont valables, il faut juste préciser si vous considérez que la profondeur de la racine est de 1 ou de 0.
On appelle hauteur d’un arbre la profondeur maximale des nœuds de l’arbre. Exemple : la profondeur de P = 5, c’est un des noeuds les plus profond, donc la hauteur de l’arbre est de 5. ATTENTION : comme on trouve 2 définitions pour la profondeur, on peut trouver 2 résultats différents pour la hauteur : si on considère la profondeur de la racine égale à 1, on aura bien une hauteur de 5, mais si l’on considère que la profondeur de la racine est de 0, on aura alors une hauteur de 4.
Il est aussi important de bien noter que l’on peut aussi voir les arbres comme des structures récursives : les fils d’un noeud sont des arbres (sous-arbre gauche et un sous-arbre droite dans le cas d’un arbre binaire), ces arbres sont eux mêmes constitués d’arbres…
À faire vous-même 1
Trouvez un autre exemple de données qui peuvent être représentées par un arbre binaire (dans le domaine de votre choix). Dessinez au moins une partie de cet arbre binaire. Déterminez la hauteur de l’arbre que vous aurez dessiné.
Python ne propose pas de façon native l’implémentation des arbres binaires. Mais nous aurons, plus tard dans l’année, l’occasion d’implémenter des arbres binaires en Python en utilisant un peu de programmation orientée objet.
Nous aurons aussi très prochainement l’occasion d’étudier des algorithmes permettant de travailler sur les arbres binaires.
Nous avons eu l’occasion d’étudier la structure d’une base de données relationnelle, nous allons maintenant apprendre à réaliser des requêtes, c’est-à-dire que nous allons apprendre à créer une base des données, créer des attributs, ajouter de données, modifier des données et enfin, nous allons surtout apprendre à interroger une base de données afin d’obtenir des informations.
Pour réaliser toutes ces requêtes, nous allons devoir apprendre un langage de requêtes : SQL (Structured Query Language). SQL est propre aux bases de données relationnelles, les autres types de bases de données utilisent d’autres langages pour effectuer des requêtes.
Pour créer une base de données et effectuer des requêtes sur cette dernière, nous allons utiliser le logiciel « DB Browser for SQLite » (il se stue dans echange\DB Browser for SQLite).
SQLite est un système de gestion de base de données relationnelle très répandu. Noter qu’il existe d’autres systèmes de gestion de base de données relationnelle comme MySQL ou PostgreSQL. Dans tous les cas, le langage de requête utilisé est le SQL (même si parfois on peut noter quelques petites différences). Ce qui sera vu ici avec SQLite pourra, à quelques petites modifications près, être utilisé avec, par exemple, MySQL.
Nous allons commencer par créer notre base de données :
À faire vous-même 1
Après avoir lancé le logiciel « DB Browser for SQLite », vous devriez obtenir ceci :
Cliquez sur Nouvelle base de données. Après avoir choisi un nom pour votre base de données (par exemple « db_livres.db »), vous devriez avoir la fenêtre suivante :
Cliquez alors sur Annuler
Notre base de données a été créée :
mais pour l’instant elle ne contient aucune table (aucune relation), pour créer une table, cliquez sur l’onglet « Exécuter le SQL ». On obtient alors :
Copiez-collez le texte ci-dessous dans la fenêtre « SQL 1 »
CREATE TABLE LIVRES
(id INT, titre TEXT, auteur TEXT, ann_publi INT, note INT);
Cliquez ensuite sur le petit triangle situé au-dessus de la fenêtre SQL 1 Exécuter (ou appuyez sur F5), vous devriez avoir ceci :
Comme indiqué dans la fenêtre, « Requête exécutée avec succès » !
Vous venez de créer votre première table.
Revenons sur cette première requête :
Le CREATE TABLE LIVRES ne devrait pas vous poser de problème : nous créons une nouvelle table nommée « LIVRES ».
La suite est à peine plus complexe :
nous créons ensuite les attributs :
id
titre
auteur
ann_pulbi
note
Nous avons pour chaque attribut précisé son domaine : id : entier (INT), titre : chaîne de caractères (TEXT), auteur : chaîne de caractères, ann_publi : entier et note : entier
L’attribut « id » va jouer ici le rôle de clé primaire. On peut aussi, par souci de sécurité (afin d’éviter que l’on utilise 2 fois la même valeur pour l’attribut « id »), modifier l’instruction SQL vue ci-dessus, afin de préciser que l’attribut « id » est bien notre clé primaire :
CREATE TABLE LIVRES
(id INT, titre TEXT, auteur TEXT, ann_publi INT, note INT, PRIMARY KEY (id));
Notre système de gestion de base de données nous avertira si l’on tente d’attribuer 2 fois la même valeur à l’attribut »id ».
Nous allons maintenant ajouter des données :
À faire vous-même 2
Toujours dans l’onglet « Exécuter le SQL », après avoir effacé la fenêtre SQL 1, copiez-collez dans cette même fenêtre la requête ci-dessous :
INSERT INTO LIVRES(id,titre,auteur,ann_publi,note)
VALUES
(1,'1984','Orwell',1949,10),
(2,'Dune','Herbert',1965,8),
(3,'Fondation','Asimov',1951,9),
(4,'Le meilleur des mondes','Huxley',1931,7),
(5,'Fahrenheit 451','Bradbury',1953,7),
(6,'Ubik','K.Dick',1969,9),
(7,'Chroniques martiennes','Bradbury',1950,8),
(8,'La nuit des temps','Barjavel',1968,7),
(9,'Blade Runner','K.Dick',1968,8),
(10,'Les Robots','Asimov',1950,9),
(11,'La Planète des singes','Boulle',1963,8),
(12,'Ravage','Barjavel',1943,8),
(13,'Le Maître du Haut Château','K.Dick',1962,8),
(14,'Le monde des Ā','Van Vogt',1945,7),
(15,'La Fin de l’éternité','Asimov',1955,8),
(16,'De la Terre à la Lune','Verne',1865,10);
Ici aussi, aucun problème, la requête a bien été exécutée :
La table LIVRES contient bien les données souhaitées (onglet « Parcourir les données ») :
Nous allons apprendre à effectuer des requêtes d’interrogation sur la base de données que nous venons de créer.
Toutes les requêtes se feront dans la fenêtre SQL 1 de l’onglet « Exécuter le SQL »
À faire vous-même 3
Saisissez la requête SQL suivante :
SELECT id, titre, auteur, ann_publi, note
FROM LIVRES
puis appuyez sur le triangle (ou la touche F5)
Après un temps plus ou moins long, vous devriez voir s’afficher ceci :
Comme vous pouvez le constater, notre requête SQL a permis d’afficher tous les livres. Nous avons ici 2 mots clés du langage SQL SELECTqui permet de sélectionner les attributs qui devront être « affichés » (je mets « affichés » entre guillemets, car le but d’une requête sql n’est pas forcément d’afficher les données) et FROMqui indique la table qui doit être utilisée.
Il est évidemment possible d’afficher seulement certains attributs (ou même un seul) :
À faire vous-même 4
Saisissez la requête SQL suivante :
SELECT titre, auteur
FROM LIVRES
Vérifiez que vous obtenez bien uniquement les titres et les auteurs des livres
À faire vous-même 5
Écrivez et testez une requête permettant d’obtenir uniquement les titres des livres.
N.B. Si vous désirez sélectionner tous les attributs, vous pouvez écrire :
SELECT *
FROM LIVRES
à la place de :
SELECT id, titre, auteur, ann_publi, note
FROM LIVRES
Pour l’instant nos requêtes affichent tous les livres, il est possible d’utiliser la clause WHEREafin d’imposer une (ou des) condition(s) permettant de sélectionner uniquement certaines lignes.
La condition doit suivre le mot-clé WHERE:
À faire vous-même 6
Saisissez et testez la requête SQL suivante :
SELECT titre, ann_publi
FROM LIVRES
WHERE auteur='Asimov'
Vérifiez que vous obtenez bien uniquement les livres écrits par Isaac Asimov.
À faire vous-même 7
Écrivez et testez une requête permettant d’obtenir uniquement les titres des livres écrits par Philip K.Dick.
Il est possible de combiner les conditions à l’aide d’un ORou d’un AND
À faire vous-même 8
Saisissez et testez la requête SQL suivante :
SELECT titre, ann_publi
FROM LIVRES
WHERE auteur='Asimov' AND ann_publi>1953
Vérifiez que nous obtenons bien le livre écrit par Asimov publié après 1953 (comme vous l’avez sans doute remarqué, il est possible d’utiliser les opérateurs d’inégalités).
À faire vous-même 9
D’après vous, quel est le résultat de cette requête :
SELECT titre
FROM LIVRES
WHERE auteur='K.Dick' OR note>=8
À faire vous-même 10
Écrire une requête permettant d’obtenir les titres des livres publiés après 1945 qui ont une note supérieure ou égale à 9.
Il est aussi possible de rajouter la clause SQL ORDER BY afin d’obtenir les résultats classés dans un ordre précis.
À faire vous-même 11
Saisissez et testez la requête SQL suivante :
SELECT titre
FROM LIVRES
WHERE auteur='K.Dick' ORDER BY ann_publi
Nous obtenons les livres de K.Dick classés du plus ancien ou plus récent.
Il est possible d’obtenir un classement en sens inverse à l’aide de la clause DESC
À faire vous-même 12
Saisissez et testez la requête SQL suivante :
SELECT titre
FROM LIVRES
WHERE auteur='K.Dick' ORDER BY ann_publi DESC
Nous obtenons les livres de K.Dick classés du plus récent au plus ancien.
À faire vous-même 13
Que se passe-t-il quand la clause ORDER BY porte sur un attribut de type TEXT ?
Vous pouvez constater qu’une requête du type :
SELECT auteur
FROM LIVRES
affiche plusieurs fois certains auteurs (les auteurs qui ont écrit plusieurs livres présents dans la base de données)
Il est possible d’éviter les doublons grâce à la clause DISTINCT
À faire vous-même 14
Saisissez et testez la requête SQL suivante :
SELECT DISTINCT auteur
FROM LIVRES
Nous avons vu précédemment qu’une base de données peut contenir plusieurs relations (plusieurs tables).
À faire vous-même 15
Créez une nouvelle base de données que vous nommerez par exemple db_livres_auteurs.db
À faire vous-même 16
Créez une table AUTEURS(id INT, nom TEXT, prenom TEXT, ann_naissance INT, langue_ecriture TEXT) à l’aide d’une requête SQL.
À faire vous-même 17
Créez une table LIVRES(id INT, titre TEXT, id_auteur INT, ann_publi INT, note INT) à l’aide d’une requête SQL.
À faire vous-même 18
Ajoutez des données à la table AUTEURS à l’aide de la requête SQL suivante :
Ajoutez des données à la table LIVRES à l’aide de la requête SQL suivante :
INSERT INTO LIVRES
(id,titre,id_auteur,ann_publi,note)
VALUES
(1,'1984',1,1949,10),
(2,'Dune',2,1965,8),
(3,'Fondation',3,1951,9),
(4,'Le meilleur des mondes',4,1931,7),
(5,'Fahrenheit 451',5,1953,7),
(6,'Ubik',6,1969,9),
(7,'Chroniques martiennes',5,1950,8),
(8,'La nuit des temps',7,1968,7),
(9,'Blade Runner',6,1968,8),
(10,'Les Robots',3,1950,9),
(11,'La Planète des singes',8,1963,8),
(12,'Ravage',7,1943,8),
(13,'Le Maître du Haut Château',6,1962,8),
(14,'Le monde des Ā',9,1945,7),
(15,'La Fin de l’éternité',3,1955,8),
(16,'De la Terre à la Lune',10,1865,10);
Nous avons 2 tables, grâce aux jointures nous allons pouvoir associer ces 2 tables dans une même requête.
En général, les jointures consistent à associer des lignes de 2 tables. Elles permettent d’établir un lien entre 2 tables. Qui dit lien entre 2 tables dit souvent clef étrangère et clef primaire.
Dans notre exemple l’attribut « id_auteur » de la tables LIVRES est bien une clé étrangère puisque cet attribut correspond à l’attribut « id » de la table « AUTEURS« .
À noter qu’il est possible de préciser au moment de la création d’une table qu’un attribut jouera le rôle de clé étrangère. Dans notre exemple, à la place d’écrire :
CREATE TABLE LIVRES
(id INT, titre TEXT, id_auteur INT, ann_publi INT, note INT, PRIMARY KEY (id));
grâce à cette précision, sqlite sera capable de détecter les anomalies au niveau de clé étrangère : essayez par exemple d’ajouter un livre à la table LIVRES avec l’attribut « id_auteur » égal à 11 !
Passons maintenant aux jointures :
À faire vous-même 20
Saisissez et testez la requête SQL suivante :
SELECT *
FROM LIVRES
INNER JOIN AUTEURS ON LIVRES.id_auteur = AUTEURS.id
Le « FROM LIVRES INNER JOIN AUTEURS » permet de créer une jointure entre les tables LIVRES et AUTEURS (« rassembler » les tables LIVRES et AUTEURS en une seule grande table). Le « ON LIVRES.id_auteur = AUTEURS.id » signifie qu’une ligne quelconque A de la table LIVRES devra être fusionnée avec la ligne B de la table AUTEURS à condition que l’attribut id de la ligne A soit égal à l’attribut id_auteur de la ligne B.
Par exemple, la ligne 1 (id=1) de la table LIVRES (que l’on nommera dans la suite ligne A) sera fusionnée avec la ligne 1 (id=1) de la table AUTEURS (que l’on nommera dans la suite B) car l’attribut id_auteur de la ligne A est égal à 1 et l’attribut id de la ligne B est aussi égal à 1.
Autre exemple, la ligne 1 (id=1) de la table LIVRES (que l’on nommera dans la suite ligne A) ne sera pas fusionnée avec la ligne 2 (id=2) de la table AUTEURS (que l’on nommera dans la suite B’) car l’attribut id_auteur de la ligne A est égal à 1 alors que l’attribut id de la ligne B’ est égal à 2.
Cette notion de jointure n’est pas évidente, prenez votre temps pour bien réfléchir et surtout n’hésitez pas à poser des questions.
À faire vous-même 21
Saisissez et testez la requête SQL suivante :
SELECT *
FROM AUTEURS
INNER JOIN LIVRES ON LIVRES.id_auteur = AUTEURS.id
Comme vous pouvez le constater, le résultat est différent, cette fois-ci ce sont les lignes de la table LIVRES qui viennent se greffer sur la table AUTEURS.
Dans le cas d’une jointure, il est tout à fait possible de sélectionner certains attributs et pas d’autres :
À faire vous-même 22
Saisissez et testez la requête SQL suivante :
SELECT nom, prenom, titre
FROM AUTEURS
INNER JOIN LIVRES ON LIVRES.id_auteur = AUTEURS.id
À faire vous-même 23
Saisissez et testez la requête SQL suivante :
SELECT titre,nom, prenom
FROM LIVRES
INNER JOIN AUTEURS ON LIVRES.id_auteur = AUTEURS.id
Si un même nom d’attribut est présent dans les 2 tables (par exemple ici l’attribut id), il est nécessaire d’ajouter le nom de la table devant afin de pouvoir les distinguer (AUTEURS.id et LIVRES.id)
À faire vous-même 24
Saisissez et testez la requête SQL suivante :
SELECT titre,AUTEURS.id,nom, prenom
FROM LIVRES
INNER JOIN AUTEURS ON LIVRES.id_auteur = AUTEURS.id
Il est possible d’utiliser la clause WHERE dans le cas d’une jointure :
À faire vous-même 25
Saisissez et testez la requête SQL suivante :
SELECT titre,nom, prenom
FROM LIVRES
INNER JOIN AUTEURS ON LIVRES.id_auteur = AUTEURS.id
WHERE ann_publi>1950
Enfin, pour terminer avec les jointures, vous devez savoir que nous avons abordé la jointure la plus simple (INNER JOIN). Il existe des jointures plus complexes (CROSS JOIN, LEFT JOIN, RIGHT JOIN), ces autres jointures ne seront pas abordées ici.
Nous en avons terminé avec les requêtes d’interrogation, intéressons-nous maintenant aux requêtes de mise à jour (INSERT, UPDATE, DELETE).
Nous allons repartir avec une base de données qui contient une seule table :
À faire vous-même 26
Créez une nouvelle base de données que vous nommerez par exemple db_livres2.db
À faire vous-même 27
Créez une table LIVRES à l’aide de la requête SQL suivante :
CREATE TABLE LIVRES
(id INT, titre TEXT, auteur TEXT, ann_publi INT, note INT, PRIMARY KEY (id));
À faire vous-même 28
Ajoutez des données à la table LIVRES à l’aide de la requête SQL suivante :
INSERT INTO LIVRES
(id,titre,auteur,ann_publi,note)
VALUES
(1,'1984','Orwell',1949,10),
(2,'Dune','Herbert',1965,8),
(3,'Fondation','Asimov',1951,9),
(4,'Le meilleur des mondes','Huxley',1931,7),
(5,'Fahrenheit 451','Bradbury',1953,7),
(6,'Ubik','K.Dick',1969,9),
(7,'Chroniques martiennes','Bradbury',1950,8),
(8,'La nuit des temps','Barjavel',1968,7),
(9,'Blade Runner','K.Dick',1968,8),
(10,'Les Robots','Asimov',1950,9),
(11,'La Planète des singes','Boulle',1963,8),
(12,'Ravage','Barjavel',1943,8),
(13,'Le Maître du Haut Château','K.Dick',1962,8),
(14,'Le monde des Ā','Van Vogt',1945,7),
(15,'La Fin de l’éternité','Asimov',1955,8),
(16,'De la Terre à la Lune','Verne',1865,10);
Nous avons déjà eu l’occasion de voir la requête permettant d’ajouter une entrée (utilisation d’INSERT)
À faire vous-même 29
Que va faire cette requête ? Vérifiez votre réponse en l’exécutant et en faisant une requête « SELECT * FROM LIVRES« .
INSERT INTO LIVRES
(id,titre,auteur,ann_publi,note)
VALUES
(17,'Hypérion','Simmons',1989,8);
À faire vous-même 30
Écrivez et testez une requête permettant d’ajouter le livre de votre choix à la table LIVRES.
« UPDATE » va permettre de modifier une ou des entrées. Nous utiliserons « WHERE« , comme dans le cas d’un « SELECT« , pour spécifier les entrées à modifier.
Voici un exemple de modification :
À faire vous-même 31
Que va faire cette requête ? Vérifiez votre réponse en l’exécutant et en faisant une requête « SELECT * FROM LIVRES« .
UPDATE LIVRES
SET note=7
WHERE titre = 'Hypérion'
À faire vous-même 32
Écrivez une requête permettant d’attribuer la note de 10 à tous les livres écrits par Asimov publiés après 1950. Testez cette requête.
« DELETE » est utilisée pour effectuer la suppression d’une (ou de plusieurs) entrée(s). Ici aussi c’est le « WHERE » qui permettra de sélectionner les entrées à supprimer.
À faire vous-même 33
Que va faire cette requête ? Vérifiez votre réponse en l’exécutant et en faisant une requête « SELECT * FROM LIVRES« .
DELETE FROM LIVRES
WHERE titre='Hypérion'
À faire vous-même 34
Écrivez une requête permettant de supprimer les livres publiés avant 1945. Testez cette requête.
Arbre 1
Arbre 3
système de fichiers de type UNIX
