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.
De nombreux algorithmes « classiques » manipulent des structures de données plus complexes que des simples nombres (nous aurons l’occasion d’en voir plusieurs cette année). Nous allons ici voir quelques-unes de ces structures de données. Nous allons commencer par des types de structures relativement simples : les listes, les piles et les files. Ces trois types de structures sont qualifiés de linéaires.
Les listes
Une liste est une structure de données permettant de regrouper des données. Une liste L est composée de 2 parties : sa tête (souvent noté car), qui correspond au dernier élément ajouté à la liste, et sa queue (souvent noté cdr) qui correspond au reste de la liste.
Le langage de programmation Lisp (inventé par John McCarthy en 1958) a été un des premiers langages de programmation à introduire cette notion de liste (Lisp signifie « list processing »). Voici les opérations qui peuvent être effectuées sur une liste :
créer une liste vide (L=vide() on a créé une liste L vide)
tester si une liste est vide (estVide(L) renvoie vrai si la liste L est vide)
ajouter un élément en tête de liste (ajouteEnTete (x,L) avec L une liste et x l’élément à ajouter)
supprimer la tête x d’une liste L et renvoyer cette tête x (supprEnTete(L))
Compter le nombre d’éléments présents dans une liste (compte(L) renvoie le nombre d’éléments présents dans la liste L)
La fonction cons permet d’obtenir une nouvelle liste à partir d’une liste et d’un élément (L1 = cons(x,L)). Il est possible « d’enchaîner » les cons et d’obtenir ce genre de structure : cons(x, cons(y, cons(z,L)))
Exemples :
Voici une série d’instructions (les instructions ci-dessous s’enchaînent):
L=vide() => on a créé une liste vide
estVide(L) => renvoie vrai
ajoutEnTete(3,L) => La liste L contient maintenant l’élément 3
estVide(L) => renvoie faux
ajoutEnTete(5,L) => la tête de la liste L correspond à 5, la queue contient l’élément 3
ajoutEnTete(8,L) => la tête de la liste L correspond à 8, la queue contient les éléments 3 et 5
t = supprEnTete(L) => la variable t vaut 8, la tête de L correspond à 5 et la queue contient l’élément 3
L1 = vide()
L2 = cons(8, cons(5, cons(3, L1))) => La tête de L2 correspond à 8 et la queue contient les éléments 3 et 5
À faire vous-même 1
Voici une série d’instructions (les instructions ci-dessous s’enchaînent), expliquez ce qui se passe à chacune des étapes :
On retrouve dans les piles une partie des propriétés vues sur les listes. Dans les piles, il est uniquement possible de manipuler le dernier élément introduit dans la pile. On prend souvent l’analogie avec une pile d’assiettes : dans une pile d’assiettes la seule assiette directement accessible et la dernière assiette qui a été déposée sur la pile.
Les piles sont basées sur le principe LIFO (Last In First Out : le dernier rentré sera le premier à sortir). On retrouve souvent ce principe LIFO en informatique.
Voici les opérations que l’on peut réaliser sur une pile :
on peut créer une pile
on peut savoir si une pile est vide (pile_vide?)
on peut empiler un nouvel élément sur la pile (push)
on peut récupérer l’élément au sommet de la pile tout en le supprimant. On dit que l’on dépile (pop)
on peut accéder à l’élément situé au sommet de la pile sans le supprimer de la pile (sommet)
on peut connaitre le nombre d’éléments présents dans la pile (taille)
Exemples :
Soit une pile P composée des éléments suivants : 12, 14, 8, 7, 19 et 22 (le sommet de la pile est 22) Pour chaque exemple ci-dessous on repart de la pile d’origine :
pop(P) renvoie 22 et la pile P est maintenant composée des éléments suivants : 12, 14, 8, 7 et 19 (le sommet de la pile est 19)
push(P,42) la pile P est maintenant composée des éléments suivants : 12, 14, 8, 7, 19, 22 et 42
sommet(P) renvoie 22, la pile P n’est pas modifiée
si on applique pop(P) 6 fois de suite, pile_vide?(P) renvoie vrai
Après avoir appliqué pop(P) une fois, taille(P) renvoie 5
À faire vous-même 2
Soit une pile P composée des éléments suivants : 15, 11, 32, 45 et 67 (le sommet de la pile est 67). Quel est l’effet de l’instruction pop(P)
Les files
Comme les piles, les files ont des points communs avec les listes. Différences majeures : dans une file on ajoute des éléments à une extrémité de la file et on supprime des éléments à l’autre extrémité. On prend souvent l’analogie de la file d’attente devant un magasin pour décrire une file de données.
Les files sont basées sur le principe FIFO (First In First Out : le premier qui est rentré sera le premier à sortir. Ici aussi, on retrouve souvent ce principe FIFO en informatique.
Voici les opérations que l’on peut réaliser sur une file :
on peut savoir si une file est vide (file_vide?)
on peut ajouter un nouvel élément à la file (ajout)
on peut récupérer l’élément situé en bout de file tout en le supprimant (retire)
on peut accéder à l’élément situé en bout de file sans le supprimer de la file (premier)
on peut connaitre le nombre d’éléments présents dans la file (taille)
Exemples :
Soit une file F composée des éléments suivants : 12, 14, 8, 7, 19 et 22 (le premier élément rentré dans la file est 22 ; le dernier élément rentré dans la file est 12). Pour chaque exemple ci-dessous on repart de la file d’origine :
ajout(F,42) la file F est maintenant composée des éléments suivants : 42, 12, 14, 8, 7, 19 et 22 (le premier élément rentré dans la file est 22 ; le dernier élément rentré dans la file est 42)
retire(F) la file F est maintenant composée des éléments suivants : 12, 14, 8, 7, et 19 (le premier élément rentré dans la file est 19 ; le dernier élément rentré dans la file est 12)
premier(F) renvoie 22, la file F n’est pas modifiée
si on applique retire(F) 6 fois de suite, file_vide?(F) renvoie vrai
Après avoir appliqué retire(F) une fois, taille(F) renvoie 5.
À faire vous-même 3
Soit une file F composée des éléments suivants : 1, 12, 24, 17, 21 et 72 (le premier élément rentré dans la file est 72 ; le dernier élément rentré dans la file est 1). Quel est l’effet de l’instruction ajout(F,25)
Types abstraits et représentation concrète des données
Nous avons évoqué ci-dessus la manipulation des types de données (liste, pile et file) par des algorithmes, mais, au-delà de la beauté intellectuelle de réfléchir sur ces algorithmes, le but de l’opération est souvent, à un moment ou un autre, de « traduire » ces algorithmes dans un langage compréhensible pour un ordinateur (Python, Java, C,…). On dit alors que l’on implémente un algorithme. Il est donc aussi nécessaire d’implémenter les types de données comme les listes, les piles ou les files afin qu’ils soient utilisables par les ordinateurs. Les listes, les piles ou les files sont des « vues de l’esprit » présent uniquement dans la tête des informaticiens, on dit que ce sont des types abstraits de données (ou plus simplement des types abstraits). L’implémentation de ces types abstrait, afin qu’ils soient utilisables par une machine, est loin d’être une chose triviale. L’implémentation d’un type de données dépend du langage de programmation. Il faut, quel que soit le langage utilisé, que le programmeur retrouve les fonctions qui ont été définies pour le type abstrait (pour les listes, les piles et les files cela correspond aux fonctions définies ci-dessus). Certains types abstraits ne sont pas forcément implémentés dans un langage donné, si le programmeur veut utiliser ce type abstrait, il faudra qu’il le programme par lui-même en utilisant les « outils » fournis par son langage de programmation.
Pour implémenter les listes (ou les piles et les files), beaucoup de langages de programmation utilisent 2 structures : les tableaux et les listes chaînées.
Un tableau est une suite contiguë de cases mémoires (les adresses des cases mémoire se suivent) :
Le système réserve une plage d’adresse mémoire afin de stocker des éléments.
La taille d’un tableau est fixe : une fois que l’on a défini le nombre d’éléments que le tableau peut accueillir, il n’est pas possible modifier sa taille. Si l’on veut insérer une donnée, on doit créer un nouveau tableau plus grand et déplacer les éléments du premier tableau vers le second tout en ajoutant la donnée au bon endroit !
Dans certains langages de programmation, on trouve une version « évoluée » des tableaux : les tableaux dynamiques. Les tableaux dynamiques ont une taille qui peut varier. Il est donc relativement simple d’insérer des éléments dans le tableau. Ce type de tableaux permet d’implémenter facilement le type abstrait liste (de même pour les piles et les files)
À noter que les « listes Python » (listes Python) sont des tableaux dynamiques. Attention de ne pas confondre avec le type abstrait liste défini ci-dessus, ce sont de « faux amis ».tableau dynamique
Autre type de structure que l’on rencontre souvent et qui permet d’implémenter les listes, les piles et les files : les listes chaînées.
Dans une liste chaînée, à chaque élément de la liste on associe 2 cases mémoire : la première case contient l’élément et la deuxième contient l’adresse mémoire de l’élément suivant.
Il est relativement facile d’insérer un élément dans une liste chaînée :
Il est aussi possible d’implémenter les types abstraits en utilisant des structures plus complexes que les tableaux et les listes chaînées. Par exemple, en Python, il est possible d’utiliser les tuples pour implémenter le type abstrait liste :
Arbre 1
Arbre 3
système de fichiers de type UNIX
tableau dynamique
