Download exercice-corrigé PDF

Titleexercice-corrigé
TagsMatrix (Mathematics) Summation Pointer (Computer Programming) Natural Number
File Size268.8 KB
Total Pages17
Document Text Contents
Page 1

AVANT-PROPOS

C’est en forgeant qu’on devient forgeron...

Ce vieil adage, dont les hommes ont usé depuis la nuit des temps, est mis dans
cet ouvrage au service des étudiants de licence et de première année de master de
mathématiques et d’informatique, des élèves-ingénieurs et de toute autre personne
souhaitant goûter les joies et maîtriser les difficultés de l’algorithmique.

Au cœur de l’informatique, cette science est celle de la conception de méthodes
efficaces pour résoudre des problèmes à l’aide d’un ordinateur. Elle définit des outils
généraux permettant de répondre aux questions suivantes : Sur quelle propriété ma-
thématique d’un problème peut-on établir une méthode de résolution ? Étant donné
un algorithme, résout-il le problème posé ? Lorsque l’on dispose de deux méthodes
de résolution différentes, laquelle est préférable ?

L’algorithmique a donné lieu à de nombreux ouvrages remarquables depuis plus
de trente ans, sur lesquels se fondent les enseignements dispensés dans les universités
et écoles d’ingénieurs, et dont nous donnons une liste non exhaustive à la fin de cet
ouvrage. L’expérience des auteurs, enseignants chevronnés dans différentes universi-
tés, les a depuis longtemps confrontés aux difficultés de leurs étudiants face à cette
matière. Celles-ci semblent de plusieurs ordres :

• il est nécessaire de pouvoir expérimenter les algorithmes sur différents exemples
pour en comprendre intuitivement le fonctionnement ;

• apprendre des éléments de cours implique de pouvoir refaire, au besoin, les dé-
monstrations qui y ont été présentées, de les rédiger ;

• les algorithmes manipulent des entités qui évoluent dans le temps, et cela ajoute
une dimension inhabituelle aux raisonnements mathématiques nécessaires pour les
prouver et analyser leurs performances ;

• l’apprentissage souvent simultané d’un langage de programmation peut parfois
ajouter des difficultés de compréhension dues à la syntaxe propre du langage.

C’est pour répondre à ces difficultés que les auteurs ont formé le projet de cet
ouvrage, à partir d’exercices progressifs conçus lors de leurs années de pratique, et
utilisés dans le cadre de travaux dirigés, d’examens, ou pour des devoirs de plus
grande envergure. L’ouvrage a pour objectif d’aider l’étudiant dans son apprentissage
de la conception et de l’analyse d’algorithmes en insistant sur le raisonnement et sa
rédaction, en vue d’écrire dans le langage de son choix des programmes efficaces.

Si la plupart des ouvrages de cours d’algorithmique contiennent des énoncés
d’exercices, peu sont corrigés. C’est donc l’une des originalités de ce livre que de©
D

un
od

.
L

a
ph

ot
oc

op
ie

no
n

au
to

ri


e
es

t
un


li

t.

VII

Page 2

Avant-propos

proposer une correction entièrement rédigée, rigoureuse et complète de chaque ques-
tion.

On y trouvera, pour chaque notion, des exercices visant la compréhension du cours,
qui permettent d’appliquer un algorithme connu à des données numériques, ou de
redémontrer, à partir d’éléments de base dont les définitions sont explicitées, les pro-
priétés de certains algorithmes du cours décomposées en questions progressives. On y
trouvera aussi des exercices qui enrichissent des algorithmes classiques de nouvelles
fonctionnalités ou qui permettent de les intégrer dans des applications originales.

Concernant la programmation, le parti pris de cet ouvrage est d’employer, pour la
rédaction des algorithmes, un pseudo-langage impératif, plutôt qu’un véritable lan-
gage de programmation, afin de se concentrer sur ce qui ressort de la conception de
l’algorithme, et non sur son implémentation. Ce choix devrait toutefois permettre une
implémentation aisée des algorithmes dans des langages comme Pascal, C ou C++,
avec sans doute un effort supplémentaire en ce qui concerne les langages objets. Nous
indiquons plus loin les conventions d’écriture de ce langage, auxquelles le lecteur
pourra se référer pour comprendre, mais aussi pour programmer les algorithmes dans
le langage de son choix.

L’ouvrage aborde un panel assez vaste de domaines d’application de l’algorith-
mique, et devrait couvrir la plupart des cours dispensés actuellement en license et
master de mathématiques et informatique et en écoles d’ingénieurs.

On y développe notamment, après un chapitre méthodologique qui traite de la
preuve et de l’analyse de la complexité d’un algorithme, les types de données abstraits
pour représenter, gérer et manipuler des ensembles dynamiques, et leur implémenta-
tion à l’aide de structures de données linéaires ou arborescentes (piles, files, listes,
arbres binaires de recherche, arbres équilibrés, tas). On aborde ensuite l’étude des
algorithmes de tri. Les chapitres suivants sont consacrés à l’étude de l’algorithmique
de base des graphes valués et non valués : connexité, accessibilité, parcours, arbres
couvrants et chemins de coût minimum, pour ne citer que les principaux problèmes
abordés. Ensuite, deux chapitres consacrés l’un aux algorithmes relatifs à la géomé-
trie plane et l’autre aux algorithmes relatifs aux automates et aux mots achèvent cet
ouvrage.

Dans chaque section, les exercices sont présentés dans un ordre de difficulté crois-
sante, sauf nécessité de regroupement thématique, et souvent les questions d’un exer-
cice respectent une certaine progressivité dans la difficulté.

D’autres algorithmes auraient mérité de figurer dans ce livre, plus proches de l’al-
gorithmique numérique, ou de la recherche opérationnelle. Avec quelques encoura-
gements, les auteurs pourraient envisager une suite...

VIII

Page 8

Chapitre 1 • Preuve et complexité

L’ordre d’inclusion est donc finalement :

O(1) ⊂ O(log n) ⊂ O(n) ⊂ O(n log n) ⊂ O(n2) ⊂ O(n3) ⊂ O(2n)

Un algorithme ayant une complexité logarithmique sera donc meilleur (en terme de com-
plexité) qu’un algorithme linéaire, lui-même meilleur qu’un algorithme polynomial, à
son tour meilleur qu’un algorithme exponentiel.

3. Le tableau suivant est calculé en utilisant un logarithme népérien :

f (n) 10 20 30 60

log n 2,30 × 10−6 3,00 × 10−6 3,40 × 10−6 4,09 × 10−6

n 10−5 2 × 10−5 3 × 10−5 6 × 10−5

n log n 2,30 × 10−5 5,99 × 10−5 1,02 × 10−4 2,46 × 10−4

n2 10−4 4 × 10−4 9 × 10−4 3,60 × 10−3

n3 10−3 8 × 10−3 2,70 × 10−2 2,16 × 10−1

2n 1,02 × 10−3 1,05 1,07 × 103 1,15 × 1012

Il est intéressant de remarquer que 1, 15 × 1012 s ≈ 36 558 ans.

4. Si f (n) ∈ O(g(n)), alors il existe k > 0 et n0 ≥ 0 tels que

f (n) ≤ kg(n) ∀n ≥ n0

On déduit de l’expression précédente que

1
k

f (n) ≤ g(n) ∀n ≥ n0

Donc g(n) est en Ω( f (n)).

5. Si f (n) ∈ O(g(n)), alors il existe k > 0 et n0 ≥ 0 tels que

f (n) ≤ kg(n) ∀n ≥ n0

On déduit de l’expression précédente que

f (n) + g(n) ≤ (k + 1)g(n) ∀n ≥ n0

Donc f (n) + g(n) est en O(g(n)).

6. De façon évidente,

max( f (n), g(n)) ≤ f (n) + g(n) ≤ 2 max( f (n), g(n)) ∀n ≥ 0

f (n) + g(n) est donc en Θ(max( f (n), g(n))).

7. Pour montrer l’égalité des deux ensembles O( f (n) + g(n)) et O(max( f (n), g(n))), il
faut montrer la double inclusion.

O( f (n) + g(n)) ⊂ O(max( f (n), g(n))) :

4

Page 9

coinleftn.eps


Exercices

Pour toute fonction h(n) ∈ O( f (n) + g(n)), il existe k > 0 et n0 ≥ 0 tels que

h(n) ≤ k( f (n) + g(n)) ≤ 2k max( f (n), g(n)) ∀n ≥ n0

Donc h(n) est donc en O(max( f (n), g(n))).

O(max( f (n), g(n))) ⊂ O( f (n) + g(n)) :
Pour toute fonction h(n) ∈ O(max( f (n), g(n))), il existe k > 0 et n0 ≥ 0 tels que

h(n) ≤ k max( f (n), g(n)) ≤ k( f (n) + g(n)) ∀n ≥ n0

Donc h(n) est en O( f (n) + g(n)).

8. Si S (n) ∈ O( f (n)) et T (n) ∈ O(g(n)), alors il existe k > 0, k′ > 0, n0 ≥ 0 et n′0 ≥ 0 tels
que

S (n) ≤ k f (n) ∀n ≥ n0
T (n) ≤ k′g(n) ∀n ≥ n′0

Si f (n) ∈ O(g(n)), alors il existe k′′ > 0 et n′′0 ≥ 0 tels que

f (n) ≤ k′′g(n) ∀n ≥ n0

On définit alors K = kk′′ + k′ et m0 = max(n0, n′0, n
′′
0 ). De façon évidente :

S (n) + T (n) ≤ k f (n) + k′g(n) ≤ (kk′′ + k′)g(n) = Kg(n) ∀n ≥ m0

Donc S (n) + T (n) est en O(g(n)).

Si dans un algorithme, on a une première partie en O( f (n)) suivie (séquentiellement)
d’une seconde partie en O(g(n)) et que f (n) ∈ O(g(n)), alors l’algorithme est globalement
en O(g(n)).

9. De la même façon, si on définit K = kk′ et m0 = max(n0, n′0), on a de façon évidente :

S (n)T (n) ≤ K f (n)g(n) ∀n ≥ m0

Donc S (n)T (n) est en O( f (n)g(n)).

Si dans un algorithme, on a une première partie en O( f (n)) dans laquelle est imbriquée
une seconde partie en O(g(n)), alors l’algorithme est globalement en O( f (n)g(n)).

Exercice 1.2 Somme des éléments d’un tableau

Soit A un tableau de n entiers (n ≥ 1).

1. Écrire un algorithme itératif qui calcule la somme des éléments de A et prouver
cet algorithme.

2. Déterminer la complexité de cet algorithme.©
D

un
od

.
L

a
ph

ot
oc

op
ie

no
n

au
to

ri


e
es

t
un


li

t.

5

Page 16

coinleftn.eps


Chapitre 1 • Preuve et complexité

Algorithme C
i ← 1 ; j ← 1
tant que j ≤ n faire

si i ≤ m
alors

i ← i + 1
sinon

j ← j + 1
fin si

fin tant que

Algorithme D
i ← 1 ; j ← 1
tant que j ≤ n faire

si i ≤ m
alors

i ← i + 1
sinon

j ← j + 1
i ← 1

fin si
fin tant que

Solution

Le corps des différents algorithmes ne contient que des opérations en O(1). En comptant
le nombre d’itérations effectuées par chacun des algorithmes, on obtient immédiatement
que :

• l’algorithme A est en O(min(m, n)) ;

• l’algorithme B est en O(max(m, n)) ;

• l’algorithme C est en O(m + n) ;

• l’algorithme D est en O(mn).

Exercice 1.6 Polynômes

On considère la fonction suivante, qui a deux arguments : un tableau T [0..n] de n+ 1
nombres réels et un nombre réel x.

12

Page 17

Exercices

fonction Calcul(T : tableau ; x : réel) : réel
s ← T [n]
pour i ← n − 1 à 0 faire

s ← T [i] + x ∗ s
fin pour
retourner(s)

1. Donner le déroulement de l’algorithme pour la donnée suivante :

n = 5 T = 3 8 0 1 1 2 et x = 2

2. Exprimer le résultat de la fonction Calcul en fonction de x et de T . Que calcule
cette fonction ? Le prouver.

3. Écrire une fonction récursive réalisant le même calcul. Prouver l’algorithme.

Solution

1. On donne les valeurs de s et de T [i] à l’initialisation et à la fin de chaque itération :
s T[i]

Init. 2 2
i = 4 5 1
i = 3 11 1

i = 2 22 0
i = 1 52 8
i = 0 107 3

2. On note si la valeur de la variable s à la fin de l’itération i et sn sa valeur initiale.
On a :

sn = T [n] et si = T [i] + x × si+1
On montre facilement par récurrence (inversée) que :

si =
n∑

j=i

T [ j] × x j−i

On en déduit que la fonction Calcul évalue le polynôme de degré n dont les coefficients
sont les valeurs du tableau T , au point x :

s0 =
n∑

j=0

T [ j] × x j

On vient en fait de démontrer la validité de l’algorithme. Il reste à vérifier la terminaison.
Celle-ci est bien sûr triviale puisque l’algorithme n’est constitué que d’une boucle de
n itérations.©

D
un

od
.

L
a

ph
ot

oc
op

ie
no

n
au

to
ri


e

es
t

un


li
t.

13

Similer Documents