Informatique SEM1 - TP no 2 - Algorithmes à boucles imbriquées

Informatique – TP no 2
Algorithmes à boucles imbriquées

Sources
▷ [Link] ;
▷ [Link] ;
▷ [Link] ;
▷ [Link] ;
▷ Informatique pour tous en classes préparatoires aux grandes écoles, Eyrolles, 2013.

Le programme officiel
Exemples d’activité, au choix du professeur et non exigibles
Thème
des étudiants. Commentaires.
Algorithmes opérant sur une Recherche d’un facteur dans un texte. Recherche des deux
structure séquentielle par boucles valeurs les plus proches dans un tableau. Tri à bulles. Notion de
imbriquées. complexité quadratique. On propose des outils pour valider la
correction de l’algorithme.

Exercice 1 Recherche d’un mot dans un texte

Rechercher un mot dans un texte est un problème très courant en in-

formatique. On peut par exemple songer à la recherche d’une phrase
dans un livre, à la fonction recherche associée aux éditeurs de textes,
ou à celle des explorateurs internet. De nombreux algorithmes ont été
conçus pour permettre une recherche efficace. Dans ce TP, on s’inté-
ressera à une procédure naïve de recherche d’un mot dans un texte :

• on effectue la recherche avec une boucle qui va considérer toutes les positions possibles pour le mot
(on appelle position du mot l’indice dans le texte de la première lettre du mot) ;
• pour chaque position i, on teste si le mot a une occurrence dans le texte (Nous dirons que mot a une
occurrence dans texte à la place i si pour tout k ∈ J0, len(mot) − 1K, on a l’égalité des caractères
texte[i + k] et mot[k].
1.1. Écrire une fonction occurrence(mot, texte, i) qui vérifie si mot a une occurrence dans texte à
la position i. La fonction renverra un booléen. On ne s’autorisera pour ce faire que des comparaisons
lettre à lettre.
 
1 >>> occurrence ( ’ test ’ , ’ Ceci est un test ’ , 12)
2 True
 

2025/2026 – [Link] 1/5

Informatique SEM1 - TP no 2 - Algorithmes à boucles imbriquées

1.2. En utilisant la fonction précédente, écrire une fonction recherche_occurrences(mot, texte) don-
nant sous forme d’une liste l’ensemble des occurrences de mot dans texte. Les occurrences peuvent
se chevaucher. Ainsi, dans « bonbonbon », il y a deux occurrences de « bonbon ».
 
1 >>> r e c h e r c h e _ o c c u r r e n c e s ( ’ bonbon ’ , ’ bonbonbon ’ )
2 [0 , 3]
 

Exercice 2 Test de rapidité de la fonction recherche_occurrences

2.1. Écrire une fonction generation_texte_aleatoire(N) prenant en paramètre un entier N, et re-

tournant une chaîne de caratères aléatoire de longueur N, composée des 26 lettres de l’alphabet, et
d’espaces.
Indication : On peut créer une chaîne de caractères représentant les lettres de l’alphabet et l’espace :
 
1 characteres = ’ a b c d e f g h i j k l m n o p q r s t u v w x y z ’
 
ce qui permet de faire une correspondance entre une lettre et un entier. Le choix aléatoire d’un
caractère pourra ensuite être fait grâce à la fonction randint(i,j), du module random, qui renvoie
aléatoirement un entier compris entre i et j, inclus (cf Annexe).
 
1 >>> g e n e r a t i o n _ t e x t e _ a l e a t o i r e (40)
2 ’ ze tdygwvprjmy lpispt osuqsgn pkvfwzbhzs ’
 
2.2. Afin de pouvoir estimer le nombre moyen d’occurrences d’une chaîne mot dans un texte aléatoire
de longueur N, Écrire une fonction calcul_nb_occ_moy(mot, N, it), qui renvoie le nombre moyen
d’occurrences d’une chaîne mot dans un texte aléatoire de longueur N. Le calcul de la moyenne se
faisant à l’aide de it itérations. Tester la fonction avec le mot « bon » dans un texte aléatoire de
longueur 100000, en effectuant 100 itérations.
 
1 >>> ca lcul_n b_occ _moy ( ’ bon ’ , 100000 , 100)
2 5.16
 
2.3. Écrire une fonction tps_recherche(N,n,it) prenant en argument trois entiers N, n et it, choisissant
une fois pour toutes une chaîne texte de longueur N et répétant it fois l’opération consistant à créer
une chaîne mot aléatoire de longueur n et à rechercher ses occurrences dans texte. La fonction doit
renvoyer la durée moyenne de ces it recherches, ce que l’on pourra déterminer grâce à la fonction
time(), du module time, qui renvoie sous forme de flottant le nombre de secondes écoulées depuis le
1er janvier 1970 à minuit (cf Annexe). La durée de création de la chaîne texte ne doit pas être prise
en compte.
2.4. En fixant n=3 et it=100, tester la fonction en prenant successivement les valeurs de N suivantes :
10000, 20000 et enfin 30000. Quel commentaire peut-on faire ?
2.5. Écrire une fonction trace_graphe(Nmax, pas, n, it), permettant de tracer le temps de réponse
moyen en fonction de la longueur N du texte aléatoire dans lequel l’on recherche un mot aléatoire de
longueur n (N varie de 0 à Nmax avec un pas pas), le temps de réponse moyen étant évalué à partir de
it itérations. On utilisera le module [Link], dont certaines fonctionnalités sont décrites
en annexe. On prendra n=3, et fera varier N de 0 à 100000 par pas de 2000.

Exercice 3 Un exemple de complexité quadratique

Nous avons montré que la recherche simple d’un mot dans un texte était de complexité linéaire. Consi-
dérons maintenant cette boucle imbriquée :

2025/2026 – [Link] 2/5

Informatique SEM1 - TP no 2 - Algorithmes à boucles imbriquées

 
1 def f1 ( n ) :
2 s =0
3 for i in range ( n ) :
4 for j in range ( n ) :
5 s += 1
6 return s
 
3.1. En analysant ce code, déterminer la complexité que l’on peut prévoir.
3.2. En utilisant la fonction time() du module time, modifier la fonction précédente, afin qu’elle renvoie
comme deuxième paramètre le temps d’exécution en seconde de la boucle imbriquée.
 
1 >>> f1 (400)
2 (160000 , 0 . 0 1 1 0 0 1 3 4 8 4 9 5 4 8 3 3 9 8 )
 
3.3. Proposer une fonction affichage(f, nmax, pas) permettant de tracer le temps de calcul de la
fonction f(n) en fonction de n, pour n variant de 0 à nmax avec le pas pas.

Exercice 4 Recherche des deux plus proches voisins dans une liste

4.1. Ecrire une fonction deux_ppv(l) qui, étant donnée une liste de nombres l contenant au moins deux
éléments, renvoie les deux valeurs les plus proches. On renverra ces deux éléments par ordre croissant.
On pourra ici utiliser le nombre infini, inf, implémenté dans le module numpy. Dans l’exemple qui
suit, on construit aléatoirement une liste d’entiers à l’aide de la fonction randint(i,j) du module
random.
 
1 >>> l = [ randint (0 ,50* n ) for i in range ( n ) ]
2 >>> l
3 [22 , 418 , 156 , 52 , 385 , 125 , 494 , 67 , 297 , 257]
4 >>> deux_ppv ( l )
5 (52 , 67)
 

Exercice 5 Tri à bulles

Le tri à bulles est un algorithme de tri qui consiste à faire remonter progressivement en fin de liste les
plus grands éléments (comme des bulles de gaz remontent à la surface d’un verre de champagne).

L’algorithme parcourt la liste et compare les éléments consécutifs. Lorsque deux éléments consécutifs ne
sont pas dans l’ordre, ils sont échangés. Visualisons les différentes étapes de ce premier parcours sur la
liste [5, 1, 3, 7, 2] :

5 > 1? oui 5 > 3? oui 5 > 7? non 7 > 2? oui

5 1 3 7 2 1 5 3 7 2 1 3 5 7 2 1 3 5 7 2 1 3 5 2 7

Après un premier parcours complet de la liste, le plus grand élément est forcément en fin de liste, à
sa position définitive. En effet, aussitôt que le plus grand élément est rencontré durant le parcours, il
est mal trié par rapport à tous les éléments suivants, donc échangé à chaque fois jusqu’à la fin du parcours.

Après le premier parcours, le plus grand élément étant à sa position définitive, il n’a plus à être traité.
Le reste de la liste est en revanche encore en désordre. Il faut donc le parcourir à nouveau, en s’arrêtant

2025/2026 – [Link] 3/5

Informatique SEM1 - TP no 2 - Algorithmes à boucles imbriquées

à l’avant-dernier élément. Après ce deuxième parcours, les deux plus grands éléments sont à leur position
définitive. Il faut donc répéter les parcours de la liste, jusqu’à ce que les deux plus petits éléments soient
placés à leur position définitive.
5.1. On se propose d’implémenter l’algorithme du tri à bulles sur une liste d’entiers l, de longueur n :
• on parcourt la liste n − 1 fois ; la k-ème fois, on ne touche pas aux k − 1 derniers éléments (déjà
triés).
• à chaque parcours, on inverse l[i] et l[i+1] chaque fois que l[i]>l[i+1] ;
Écrire une fonction tri_bulles(l) permettant de renvoyer la liste l triée.
 
1 >>> tri_bulles ([5 ,1 ,3 ,7 ,2])
2 [1 , 2 , 3 , 5 , 7]
 
5.2. Une optimisation courante de ce tri consiste à l’interrompre dès qu’un parcours des éléments pos-
siblement encore en désordre est effectué sans échange. En effet, cela signifie que toute la liste est
triée. Proposer une fonction tri_bulles_optimise(l) permettant de trier ainsi la liste l. On pourra
utiliser un booléen echange qui permettra de tester s’il y a eu au moins un échange lors d’un parcours.

Une fois le programme écrit, il reste à vérifier qu’il est correct, c’est-à-dire qu’il calcule bien ce que l’on
attend ; on peut tester quelques cas significatifs, mais il est beaucoup plus satisfaisant de démontrer qu’il
est correct dans tous les cas. Dans le cas des algorithmes itératifs, une des manières les plus efficaces de
démontrer la correction de l’algorithme, est d’établir un invariant de boucle :

Invariant de boucle

Un invariant de boucle est une propriété permettant de démontrer la correction d’un algo-
rithme itératif. Elle doit être vérifiée tout au long de l’exécution d’une boucle. La démonstration
se fait en trois étapes :
• initialisation : on doit montrer que l’invariant de boucle est vrai avant la première
itération de la boucle ;
• conservation : on doit montrer que si l’invariant de boucle est vrai avant une itération
de la boucle, il le reste à la fin de celle-ci ;
• sortie de la boucle : une fois la boucle terminée, l’invariant de boucle doit fournir une
propriété utile permettant d’en déduire que le programme est correct.

5.3. On propose l’invariant de boucle « la liste l[n-k-1:] est triée » (k est le compteur de la boucle for,
variant de 0 à n-2 ; on prendra k=-1 avant la première itération). Montrer qu’il permet de prouver
que l’algorithme de la fonction tri_bulles est correct.

2025/2026 – [Link] 4/5

Informatique SEM1 - TP no 2 - Algorithmes à boucles imbriquées

Annexe : Mémento

2025/2026 – [Link] 5/5