Algorithmes itératifs
Exercice-1 : Recherche du maximum
1. Concevoir un algorithme de recherche du maximum dans un ensemble à n éléments
2. Quelle est la complexité de votre algorithme en nombre de comparaisons ?
3. Montrer qu'il est optimal.
Exercice-2 : Complexité de séquences itératives
Déterminer (en fonction de n à O( ) près) la complexité en nombre « d’opérations » de
chaque séquence :
Séq-1 : For i = 1 to N do Séq-6: i=1
Opération ; For j=1 To n do
Endfor i = 2*i
Endfor
Séq-2 : For i = 1 to N do For j= 1 to i do
For j = 1 to i do Opération;
Opération ; Endfor
Endfor Séq-7 : For k = 1 to n do
Endfor i=1
Séq-3 : i=1 For j = 1 to k do
While ( i < N) Do i = 2*i
i = 2*i Endfor
Opération ; For j = 1 to i do
Endwhile Opération
Séq-4: For i = 1 To N Do Endfor
J=1 Endfor
While (J < N ) Do
J=2*J
Opération;
Endwhile
Endfor
Séq-5: i=1
While ( i < N ) Do
i = 2*i
For j = 1 to i Do
Opération;
Endwhile
Exercice-3 : Recherche du maximum et du minimum
Nous supposons ici que l'ensemble considéré ne contient pas deux fois la même valeur.
1. Proposer un algorithme naif de recherche du maximum et du minimum d'un ensemble de
n éléments.
2. Quelle est sa complexité en nombre de comparaisons ?
3. Proposer un algorithme plus efficace.
Indication : dans une première phase les éléments sont comparés par paire.
4. Quelle est sa complexité en nombre de comparaisons ?
1/2
Exercice-4 : Recherche du deuxième plus grand élément
Nous supposons ici que l'ensemble considéré ne contient pas deux fois la même valeur.
1. Proposer un algorithme simple de recherche du deuxième plus grand élément.
2. Quelle est sa complexité en nombre de comparaisons ?
3. Réécrire l’algorithme de recherche du maximum sous la forme d'un tournoi de tennis. Il
n'est pas nécessaire de formaliser l'algorithme ici, une figure explicative suffit.
4. Dans combien de comparaisons, le deuxième plus grand élément de l'ensemble s’est
rendu compte qu’il est le plus petit des deux éléments comparés ?
5. Proposer un nouvel algorithme de recherche du deuxième plus grand élément.
6. Quelle est sa complexité en nombre de comparaisons ?
Exercice-5 : Anagramme
Deux mots sont dits anagrammes s’ils sont composés des mêmes lettres mais dans un ordre différent.
Exemple : UN et NU, ELLES et SELLE, SURE et RUSE
Etant donné, un tableau de N pointeurs. Chaque pointeur pointe sur une chaîne de caractères
représentant un mot.
a- Ecrire une fonction « max_anagram » qui permet de retourner la longueur du plus long
anagramme. On vous conseille de commencer par écrire une fonction « anagram » qui vérifie
si deux mots sont ou non anagrammes. Elle doit retourner la longueur du mot s’ils sont des
anagrammes et 0 sinon.
b- En supposant que les mots ont une longueur moyenne égale à M, estimer en fonction de N et
M, la complexité nécessaire pour déterminer l’anagramme le plus long en nombre de
comparaisons de caractères.
c- Proposer un autre algorithme pour la fonction « anagram » pour réduire la complexité
2/2
