e3a 2017 : option informatique

Exercice 1
On suppose défini le type arbre de la manière suivante :

type arbre =
|Feuille of int
|Noeud of arbre * arbre ;;

On dit qu’un arbre est un peigne si tous les noeuds à l’exception éventuelle de la racine ont au moins
une feuille pour fils. On dit qu’un peigne est un strict si sa racine a au moins une feuille pour fils, ou
s’il est réduit à une feuille. On dit qu’un peigne est rangé si le fils droit d’un noeud est toujours une
feuille. Un arbre réduit à une feuille est un peigne rangé.

k
 HH
k
 k
 HH
j

2k
R k
1k k
@
@ @
R
@
5
3k 4k
@
R
@

Figure 1 : un peigne à cinq feuilles

1. Représenter un peigne rangé à 5 feuilles.

2. La hauteur d’un arbre est le nombre de noeuds maximal que l’on rencontre pour aller de la racine
à une feuille (la hauteur d’une feuille seule est 0). Quelle est la hauteur d’un peigne rangé à n
feuilles ? On justifiera la réponse.
3. Ecrire une fonction est range : arbre → bool qui renvoie true si l’arbre donné en argument
est un peigne rangé.
4. Ecrire une fonction est peigne strict : arbre → bool qui renvoie true si l’arbre donné
en argument est un peigne strict. En déduire une fonction est peigne : arbre → bool qui
renvoie true si l’arbre donné en argument est un peigne.
5. On souhaite ranger un peigne donné. Supposons que le fils droit N de sa racine ne soit pas une
feuille. Notons A1 le sous-arbre gauche de la racine, f l’une des feuilles du noeud N et A2 l’autre
sous-arbre du noeud N . On va utiliser l’opération de rotation qui construit un nouveau peigne
où
• le fils droit de la racine est le sous-arbre A2 ;
• le fils gauche de la racine est un noeud de sous-arbre gauche A1 et de sous-rabre droit la
feuille f .

1
  
rotation
v1 - v2
 
@ @
@ 
@ @
@
A1 v2 v1 A2
 
 T  T
 T  T
fk fk
 T  T
A2 A1

Figure 2 : une rotation

(a) Donner le résultat d’une rotation sur l’arbre de la figure 1.

(b) Ecrire une fonction rotation : arbre → arbre qui effectue l’opération décrite ci-dessus.
La fonction renverra l’arbre initial si une rotation n’est pas possible.
(c) Ecrire une fonction rangement : arbre → arbre qui range un peigne donné en argument,
c’est à dire qu’il renvoie un peigne rangé ayant les mêmes feuilles que celui donné en
argument. La fonction renverra l’arbre initial si celui-ci n’est pas un peigne.

Exercice 2
Dans une classe de n élèves, les élèves sont numérotés de 0 à n−1. Un professeur souhaite faire l’appel,
c’est à dire déterminer quels élèves sont absents.

Partie A
1. Ecrire une fonction mini : int list → (int * int list) qui prend en argument une liste
non vide d’entiers distincts, et renvoie le plus petit élément de cette liste, ainsi que la liste de
départ privée de cet élément (pas forcément dans l’ordre initial).
2. En notant k la longueur de la liste donnée en argument, quelle est la complexité en nombre de
comparaisons de la fonction précédente ?
3. En utilisant la fonction mini, écrire une fonction absents : int list → int → int list
qui, étant donné une liste non vide d’entiers distincts et n, renvoie, dans un ordre quelconque,
la liste des entiers de [0; n − 1] qui n’y sont pas.
4. En notant k la longueur de la liste donnée en argument, quelle est la complexité en nombre de
comparaisons (en fonction de n et k) de la fonction précédente ?

Partie B
Dans cette partie, une salle de classe pour n élèves est décrite par la donnée d’un tableau à n entrées.
Si tab est un tel tableau et i un entier de [0; n − 1], alors tab.(i) donne le numéro de l’élève assis à
la place i (ou −1 si cette place est vide).
5. Ecrire une fonction asseoir : int list → int → int vect, qui prend en argument une
liste non vide d’entiers distincts et un entier n, et renvoie un tableau représentant une salle de
classe pour n élèves où chaque élève de la liste à été assis à la place numérotée par son propre
numéro. Les entiers supérieurs ou égaux à n seront ignorés.
6. En déduire une fonction absent2 : int list → int → int list qui étant donné une liste
non vide d’entiers distincts et un entier n, renvoie la liste des entiers de [0; n − 1] qui n’y sont
pas. Les entiers supérieurs ou égaux à n seront ignorés.

2
 7. En notant k la longueur de la liste donnée en argument, quelle est la complexité en nombre de
lectures et d’écritures dans un tableau (en fonction de n et k) de la fonction précédente ?

Partie C
Dans cette partie indépendante des précédentes, les élèves sont déjà assis en classe.
8. On considère la fonction place : int vect → unit suivante :

let rec place tab i =

if i <> -1 then
begin
let temp=tab.(i) in
tab.(i) <- i;
place tab temp
end;;

On note classe le tableau [|-1;4;5;-1;3;0|] (on suppose n = 6 dans cette question). Donner
le tableau classe après l’exécution de place classe 1. On donnera l’état de la variable classe
à chaque appel récursif de la fonction.
9. On considère la fonction placement : int vect → int → unit ci-dessous :

let placement tab n =

for i=0 to n-1 do
if tab.(i) <> -1 && tab.(i) <>i then
begin
let temp=tab.(i) in
tab.(i) <- -1;
place tab temp
end
done;;

Si classe est un tableau d’entiers (les entiers positifs sont distincts) représentant une classe,
que fait placement classe ?

Exercice 3
On rappelle la définition de la suite de Fibonacci :

 F0 = 0
F1 = 1
Fn = Fn−1 + Fn−2 pour n ≥ 2


Partie A. Calcul des termes de la suite

1. On considère la fonction fibo : int → int suivante :

let rec fibo = function

|0->0
|1->1
|n->fibo (n-1) + fibo (n-2);;

Pourquoi est-ce une mauvaise idée d’utiliser cette fonction pour calculer Fn ?
2. Ecrire une fonction fibo2 : int → int qui, étant donné n, calcule Fn en effectuant un nombre
linéaire en n d’additions.

3
Partie B. Décomposition de Zeckendorf
Pour n ∈ N, on appelle décomposition de Zeckendorf de n une décomposition de n comme somme de
termes distincts (d’indices supérieurs ou égal à 2) de la suite de Fibonacci, de telle manière qu’il n’y ait
pas deux termes d’indices consécutifs dans la somme. Autrement dit, il existe des indices c1 , c2 , . . . , ck
tels que :
• c0 ≥ 2,
• pour tout i < k, ci+1 > ci + 1 (pas d’indices consécutifs),
Pk
• n= Fci .
i=0
Par exemple, 2 + 5 = F3 + F5 est une décomposition de Zeckendorf de 7 (avec c0 = 3 et c1 = 5), alors
que 3 + 5 = F4 + F5 n’est pas une décomposition de Zeckendorf de 8 car F4 et F5 sont deux termes
consécutifs de la suite de Fibonacci.
3. Déterminer une décomposition de Zeckendorf de 20, 21 et 22.
4. Montrer que tout entier strictement positif admet une décomposition de Zeckendorf (on admet
qu’elle est unique).

Partie B. Codage de Fibonacci

On appelle codage de Fibonacci d’un entier positif k un tableau tab de 0 et de 1 indiquant par des
1 les indices des termes de la suite de Fibonacci utilisés dans la décomposition de Zeckendorf de k
(tab.(0) indique alors si F2 est utilisé dans la représentation). On remarque que par définition de la
décomposition de Zeckendorf, tab ne peut contenir deux 1 consécutifs.
[|0; 1; 0; 1|] est ainsi un codage de Fibonacci de 7
5. Ecrire une fonction decode : int vect → int qui traduit en entier une représentation de
Fibonacci d’un entier.
6. (a) Decrire sans l’implémenter une fonction plusun : int vect → int vect, qui à partir
d’une représentation de Fibonacci d’un entier k, renvoie une représentation de Fibonacci
de l’entier k + 1.
(b) Decrire sans l’implémenter une fonction moinsun : int vect → int vect, qui à partir
d’une représentation de Fibonacci d’un entier k non nul, renvoie une représentation de
Fibonacci de l’entier k − 1.

Exercice 4
Dans cet exercice, les programmes seront écrits avec le langage Python. On pourra utiliser si besoin
la bibliothèque numpy :
• zeros([n,p]) renvoie un tableau bidimensionnel (n, p) rempli de 0 ;
• si T est un tableau bidimensionnel, T[i,j] accède à l’élément ligne i et colonne j de ce tableau.
Le réseau de métro d’une grande ville comporte N stations réparties sur un certain nombre de lignes
interconnectées (par exemple, pour la ville de Lyon, on a N = 40 avec 4 lignes).
On représente ce réseau par un graphe non orienté G = ([|0, N − 1|], A) défini par :
• l’ensemble des sommets est [|0, N − 1|] ; on a numéroté les stations de 0 à N − 1. Le sommet i
du graphe G représente la station i ;
• A désigne l’ensemble des arêtes de G. Un arête entre les sommets i et j (éléments de [|0, N − 1|])
n’existe que si les stations i et j sont des stations adjacentes sur une même ligne de métro. Ce
graphe est représenté par la liste Liste A (donnée en variable globale) de ses arêtes sous la forme
[i, j] tels que i < j.

4
 1. Ecrire une fonction voisin G qui prend en entrée un entier i ∈ [|0, N − 1|] et reourne la liste des
sommets adjacents à i dans G.
On suppose le graphe G connexe et on cherche à déterminer le trajet le plus rapide entre deux stations
du réseau.
Soit duree la fonction définie sur A qui attribue à une arête (i, j) la durée du trajet entre la station i
et la station j en minutes, arrondie sur un nombre entier.
Un trajet entre deux stations i et j correspond à un chemin dans G qui part de i et arrive en j. La
durée d’un tel trajet i = i0 → i1 → · · · → in = j utilisant n arêtes est la somme des durées des arêtes :
n−1
X
duree(i = i0 → i1 → · · · → in = j) = duree((ik , ik+1 ))
k=0

Pour simplifier, on ne tient pas compte des durées correspondant aux changements de métro.
On dispose de la liste Duree des listes [i, j, duree(i, j)], pour 0 ≤ i < j ≤ N − 1 tels que (i, j) ∈ A. On
note D la valeur

D=sum([U[2] for U in Duree])

2. Soient i, j deux sommets de G. Démontrer qu’il existe au moins un trajet de durée minimale
entre i et j.
Pour i, j sommets de G, on note δmin (i, j) la durée minimale d’un trajet entre i et j.
3. Soient i, j deux sommets de G. Soit i = i0 → i1 → · · · → in = j un chemin dans G qui part de i
et arrive en j en utilisant n arêtes (n ≥ 1). On suppose que ce chemin réalise un trajet de durée
minimale entre i et j. Justifier que pour tout k entre 1 et n, i = i0 → i1 → · · · → ik est un trajet
de durée minimale entre i0 et ik et ik → · · · → in = j est un trajet de durée minimale entre ik
et j.
4. En déduire, pour i et j distincts tels que (i, j) ∈
/ A, une expression de δmin (i, j) en fonction des
valeurs δmin (i, k) et δmin (k, j) pour k parcourant la liste des sommets de G à l’exception de i et
j. Justifier votre réponse.
5. Définir Tinit le tableau bidimensionnel (N, N ) tel que

 0 si i = j
∀(i, j) ∈ [|0, N − 1|]2 , Tinit[i, j] = duree(i, j) si (i, j) ∈ A
D sinon


6. Définir la fonction FW qui prend en antrée un tableau bidimensionnel (N, N ) T et retourne le

tableau bidimensionnel (N, N ) T 0 défini par

∀(i, j) ∈ [|0, N − 1|]2 , T 0 [i, j] = min(T [i, j], T [i, k] + T [k, j], k ∈ [|0, N − 1|])

7. Ecrire un programme qui, en utilisant le tableau Tinit et la fonction FW, permet de calculer un
tableau bidimensionnel (N, N ) dont le (i, j)-ième coefficient vaut δmin (i, j), pour tous sommets
i et j. Combien d’itérations sont-elles nécessaires pour conclure ?
8. Expliquer comment modifier le programme pour obtenir un trajet de durée minimale entre i et
j pour tous sommets i, j. On ne demande pas de le programmer précisément mais d’expliquer
ce qu’il faudrait ajouter au programme précédent pour obtenir de plus ces informations.

5
 e3a 2017 : option informatique
Un corrigé

Exercice 1
1. Un peigne rangé à cinq feuilles est par exemple :


HH
 HH


 HH 
j
H
 0
@
 R
@
@
 1


A



A
U
A
 2


A



A
U
A
4
 3


2. Comme l’énoncé stipule que la hauteur d’une feuille est nulle, il me semble que la définition
cohérente de hauteur d’un arbre est le nombre maximal d’arêtes de la racine vers une feuille.
Montrons par récurrence sur n ≥ 1 que la hauteur d’un peigne rangé à n feuilles est égale à
n − 1.
- Un peigne rangé à 1 feuille es une feuille et sa hauteur vaut 1.
- Supposons le résultat vrai jusqu’à un rang n ≥ 1. Un peigne rangé à n + 1 feuilles s’écrit
Noeud(g,d) avec d qui est une feuille et g qui est un peigne rangé à n feuilles. La hauteur de
cet arbre est égale à 1 plus le maximum des hauteurs de g et d qui valent n − 1 (hypothèse
de récurrence) et 1. Notre arbre est donc de hauteur n, ce qu’il fallait prouver.

Un peigne rangé à n feuilles est de hauteur n − 1

3. Si l’arbre n’est pas une feuille, on vérifie qu’il y a une feuille à droite et, récursivement, que le
fils gauche est un peine rangé.

let rec est_range a = match a with

|Feuille x -> true
|Noeud (g,Feuille x) -> est_range g
|_ -> false ;;

4. Si l’arbre n’est pas une feuille, on vérifie que l’un des fils est une feuille et, récursivement, que
l’autre est un peigne strict.

let rec est_peigne_strict a = match a with

|Feuille x -> true
|Noeud(g,Feuille x) -> est_peigne_strict g
|Noeud(Feuille x,d) -> est_peigne_strict d
|_ -> false;;

1
 Il reste à particulariser la racine et à vérfiier que, s’ils existent, fils gauche et droit sont des
peignes stricts.

let est_peigne a = match a with

|Feuille x -> true
|Noeud (g,d) -> (est_peigne_strict g)&&(est_peigne_strict d);;

5. (a) Une rotation sur l’arbre exemple donne

k
 HH
k
 k
 HH
j

k @R k
3k 4k
@ @
R
@
1
2k 5k
@
R
@

(b) La rotation est possible dès que le fils droit est un noeud qui a au moins un fils qui est une
feuille.
let rotation a = match a with
|Noeud(a1,Noeud(a2,Feuille f))->Noeud(Noeud(a1,Feuille f),a2)
|Noeud(a1,Noeud(Feuille f,a2))->Noeud(Noeud(a1,Feuille f),a2)
|_ -> a;;
(c) Je propose d’écrire une fonction range qui agit comme rangement mais en SUPPOSANT
que l’argument est un peigne. Il reste alors à tester si c’est le cas.
L’idée de la fonction range est d’effectuer une rotation si c’est possible et de recommencer
récursivement. On va finir par tomber sur le cas où le fils droit est une feuille. Il suffit alors
de ranger le fils gauche.
let rec range a = match a with
|Feuille f -> Feuille f
|Noeud(g,Feuille f) -> Noeud(range g,Feuille f)
|_ -> range (rotation a) ;;

let rangement a =
if est_peigne a then range a
else a;;

Exercice 2
Partie A
1. C’est un parcours classique de liste. Si on sait trouver le minimum de la queue, on sait trouver
le minimum de la liste globale.

let rec mini l = match l with

|[x] -> (x,[])
|x::q -> let (y,r)=mini q in

2
 if x<y then (x,y::r)
else (y,x::r);;

2. Notons Ck le nombre de comparaisons effetuées dans l’appel à mini avec une liste de taille k.
On a C1 = 0 et Ck = 1 + Ck−1 si k ≥ 2. On en déduit que

mini l effectue |l| comparaisons

3. La question est assez étrange car il ne me semble pas y avoir de tactique “naturelle” utilisant
mini pour obtenir la liste des absents.
Dans un premier temps, la fonction mini permet de mettre en oeuvre un tri de liste (par selec-
tion).

let rec tri l = match l with

|[] -> []
|_ -> let (x,t)= mini l in
x::(tri t);;

On peut alors écrire une fonction auxiliaire aux : int list → int → int → list qui prend
en argument une liste t supposée triée ainsi que deux entiers i et j. Elle renvoie la liste des
éléments k ∈ [i, j − 1] qui ne sont pas dans la liste.

let rec aux t i j=

match t with
|[] -> if i=j then [] else i::(aux t (i+1) j)
|x::q -> if i=j then []
else if i=x then aux q (i+1) j
else if i<x then i::(aux t (i+1) j)
else aux q i j;;

Il suffit de l’utiliser avec la liste triée ainsi que 0 et n.

let absents l n =
aux (tri l) 0 n;;

Il y a d’autres tactiques possibles mais l’énoncé n’est pas assez clair. On pourrait ainsi chercher
le minimum m de la liste l et ajouter dans une liste en construction les éléments 0, 1, . . . , m − 1
puis recommencer avec le reste de la liste. On a alors besoin d’une première fonction liste :
int → int → int list telle que l’appel liste i j renvoie la liste des entiers ≥ i et < j.

let rec liste i j =

if i>=j then []
else i::(liste (i+1) j);;

La fonction aux : int list → int → int → int list renvoie la liste des éléments ≥ i et
< j qui ne sont pas dans la liste.

let rec aux l i j = match l with

|[] -> liste i j
|_ -> let (m,q)=mini l in
if m>=j then []
else (liste i m)@(aux q (m+1) j) ;;

Il suffit de l’appeler avec la liste initiale et les entiers 0 et n.

3
 let absents l n =
aux l 0 n;;

4. Le tri utilise de l’ordre de n2 comparaisons du fait des n appels à mini. La fonction auxiliaire
se contente de parcourir la liste et utilise de l’ordre de n opérations.

absents l n effectue O(n2 ) comparaisons

Partie B
5. On créé un tableau de bonne taille. On utilise alors une fonction auxilaire parcours : int list
→ unit qui parcourt la liste en plaçant les élèves.

let asseoir l n =
let tab=make_vect n (-1) in
let rec parcours l =match l with
|[] -> ()
|i::q -> if i<=n || i<0 then tab.(i) <- i ;
parcours q
in parcours l;
tab;;

6. La fonction construit : int → int list est telle que dans l’appel construit i, on renvoie
la liste des absents de numéro ≥ i.

let absent2 l n =
let tab=asseoir l n in
let rec construit i =
if i=n then []
else if tab.(i) <> -1 then i::(construit (i+1))
else construit (i+1)
in construit 0;;

7. Créer tab coûte de l’ordre de 2n opérations (création du tableau et remplissage). La construction

de la liste s’opère avec de l’ordre de n consultations du tableau.

absents2 l n effectue O(n) accès à une case de tableau

Partie C
8. L’évolution des arguments d’appel est résumé dans le tableau ci-dessous

tab i
[| − 1; 4; 5; −1; 3; 0|] 1
[| − 1; 1; 5; −1; 3; 0|] 4
[| − 1; 1; 5; −1; 4; 0|] 3
[| − 1; 4; 5; −1; 3; 0|] −1

L’appel place tab i met l’élève i à sa place (en replaçant celui qui était éventuellement en
place i, le processus se répétant alors).
9. La fonction remet en ordre dans la classe les élèves présente initialement (un élève i présent
initialement sera à la place i en fin de processus).

4
Exercice 3
Partie A. Calcul des termes de la suite
1. En notant Cn le nombre d’addition induites par l’appel fibo n, on a C0 = C1 = 0 et ∀n ≥
2, Cn = C√ n
n−1 +Cn−2 . Lé résolution de cette récurrence linéaire d’ordre 2 montre que Cn = O(φ )
où φ = 1+2 5 . La complexité est donc exponentielle vis à vis de n et la fonction est donc peu utile
en pratique. Non seulement, le temps d’exécution sera grand mais la pile de récursivité risque
d’être vite insuffisante.
2. On gère deux variable a et b prenant successivement les valeurs (F0 , F1 ) puis (F1 , F2 ) etc. jusqu’à
(Fn , Fn+1 ).

let fibo2 n =
let a=ref 0 and b=ref 1 in
for i=1 to n do
let temp= !a in
a:= !b ;
b:= !b+temp
done;
!a;;

Partie B. Décomposition de Zeckendorf

3.
20 = 13 + 5 + 2 = F7 + F5 + F3
21 = F8
22 = 21 + 1 = F8 + F2

4. On imagine un algorithme récurrent pour trouver la décomposition d’un entier n.

- 1 = F2 donne une décomposition de l’entier 1
- Si n ≥ 2, on cherche le plus grand indice k tel que Fk ≤ n (qui existe et est unique car
(Fp )p≥1 est une suite strictement croissante d’entiers).
Si Fk = n, on a une décomposition
Sinon n = Fk + (n − Fk ) et on sait décomposer n − Fk . Le plus grand indice i tel que
Fi intervient dans la décomposition de n − Fk n’est pas k − 1 car sinon n − Fk ≥ Fk−1
et donc n ≥ Fk+1 ce qui est faux par maximalité de k. On a donc une décomposition
valable pour n.

Partie B. Codage de Fibonacci

5. On gère une référence n qu’on fait évoluer. Lors du parcours du tableau, on doit ajoputer à n
une valeur Fi si la case vaut 1. Il serait maladroit de recalculer à chaque fois les Fk . Je gère donc
des références a et b telles que a = Fi−1 et b = Fi où Fi est le prochain nombre de Fibonacci à
utiliser.

let decode tab =

let a=ref 1 and b=ref 1 in
let n=ref 0 in
for i=0 to vect_length tab - 1 do
if tab.(i)=1 then n:= !n+ !b;
let temp= !a in

5
 a:= !b ;
b:= !b+temp ;
done;
!n;;

6. (a) On suppose connu le codage de k = b0 b1 . . . bn où les bi valent 0 ou 1 et où deux bi consécutifs
ne peuvent valoir 1. Quitte à ajouter des bi nuls en fin de chaı̂ne, on peut supposer qu’il
existe deux bi consécutifs nuls. On prend cette première paire bi bi+1 .
Le codage peut alors avoir deux formes.
- Si le codage commence par un 1, il y a une suite de 10 puis au moins un 0 en plus et
ainsi
k = F2 + F4 + · · · + F2p + b2p+3 F2p+3 + b2p+4 F2p+4 + . . .
On a alors, comme 1 = F1 ,

1 + k = F1 + F2 + F4 + · · · + F2p + b2p+3 F2p+3 + b2p+4 F2p+4 + . . .

= F3 + F4 + · · · + F2p + b2p+3 F2p+3 + b2p+4 F2p+4 + . . .
= ...
= F2p+1 + b2p+3 F2p+3 + b2p+4 F2p+4 + . . .

et on a une décomposition convenable.

- Si le codage commence par un 0, on a de même

k = F3 + F5 + · · · + F2p−1 + b2p+2 F2p+2 + b2p+3 F2p+3 + . . .

et ainsi, comme 1 = F2 ,

1 + k = F2 + F3 + F5 + · · · + F2p−1 + b2p+2 F2p+2 + b2p+3 F2p+3 + . . .

= F4 + F5 · · · + F2p−1 + b2p+2 F2p+2 + b2p+3 F2p+3 + . . .
= ...
= F2p + b2p+2 F2p+2 + b2p+3 F2p+3 + . . .

L’idée est donc de parcourir le tableau jusqu’à trouver deux 0 consécutifs, à annuler les
cases parcourues et à ajouter 1 dans la case où se trouve le premier des deux zéros.
Dans la fonction ci-dessous (non demandée), on suppose le tableau assez grand et on le
modifie puis on le renvoie.
let plusun tab =
let i=ref 0 in
while tab.(!i)==1 || tab.(!i+1)==1 do
tab.(!i) <- 0 ;
incr i
done ;
tab.(!i) <- 1 ;
tab;;
(b) Comme on suppose k ≥ 1, il y a au moins une case du tableau qui vaut 1. Le codage va
s’écrire bi bi+1 . . . avec bi = 1 et on a

k = Fi + bi+1 Fi+1 + . . .

6
 On écrit alors que
k = Fi−2 + Fi−1 + bi+1 Fi+1 + . . .
= Fi−4 + Fi−3 + Fi−1 + bi+1 Fi+1 + . . .
= Fi−6 + Fi−5 + Fi−3 + Fi−1 + bi+1 Fi+1 + . . .
= ...
On cherche donc le premier i tel que tab.(i) = 1. On met la case à 0 et on repart en arrière
en plaçant un 1 une fois sur deux.
let moinsun tab=
let i=ref 0 in
while tab.(!i)==0 do incr i done ;
tab.(!i) <- 0 ;
decr i ;
while !i>=0 do
tab.(!i) <- 1 ;
decr i;
decr i
done ;
tab;;

Exercice 4
ATTENTION : le code informatique ci-dessous n’a PAS été testé. Il est possible qu’il y ait des erreurs
(mineures).
1. On gère une liste l que l’on va faire grossir. Pour chaque arête a=[a[0],a[1]], on doit ajouter
a[0] si a[1]=i ou a[1] si a[0]=i.
def voisins_G i =
l=[]
for a in liste_A:
if a[0]==i:
l.append(a[1])
if a[1]==i:
l.append(a[0])
return l
2. Les durées étant positives, on peut se contenter de ne regarder que des chemins simples, c’est
à dire des chemins qui ne passent pas deux fois par la même station (faire une boucle ne fait
qu’augmenter la durée).
Le graphe étant connexe, il existe au moins un chemin de i vers j. L’ensemble des longueurs de
ces chemins (le nombre des arêtes empruntées) est non vide et inclus dans N et admet donc un
minimum. Ce minimum est associé à un chemin simple de vers i vers j.
L’ensemble des chemins simples de i vers j est non vide. Il est fini (car il n’y a qu’un nombre fini
de sommets). L’ensemble des durées des chemins simples de i vers j admet donc un minimum
(ensemble non vide et fini).
Ceci montre qu’il existe un chemin de durée minimum reliant i à j.
3. Si, par l’absurde, il existait un meilleur chemin de ia à ib que le sous-chemin ia → · · · → ib du
chemin considéré alors on pourrait remplacer ce sous-chemin par un autre en faisant diminuer
la durée. Ceci contredirait la minimalité du chemin de départ.
Ceci montre que tout sous-chemin d’un chemin minimal est minimal et entraı̂ne les résultats
demandés.

7
4. Si (i, j) ∈ A, un chemin de i vers j transite forcément par un autre sommet k. En notant k
un sommet de transit pour un chemin minimal de i vers j, ce chemin est composé d’un chemin
minimal de i vers k puis d’un chemin minimal de k vers j. Son poids est donc δmin (i, k) +
δmin (k, j). On a donc a fortiori

δmin (i, j) ≥ min (δmin (i, k) + δmin (k, j))

k6=i,j

Réciproquement, pour un k atteignant le minimum de droite, on construit un chemin de i vers

j de poids δmin (i, k) + δmin (k, j) en aboutant deux chemins. On a ainsi l’inégalité dans l’autre
sens et
∀(i, j) ∈
/ A, δmin (i, j) = min (δmin (i, k) + δmin (k, j))
k6=i,j

5. On crée un tableau à deux dimensions avec uniquement des D. On remplit alors les cases comme
il faut.

Tinit=[[D for i in range(N)] for j in range(N)]

for i in range(N):
Tinit[i][j]=0
for a in Duree:
Tinit[a[0]][a[1]]=a[2]

6. On crée une copie de T et on met à jour ses cases.

def FW(T):
TT=[[T[i][j] for i in range(N)] for j in range(N)]
for i in range(N):
for j in range(N):
for k in range(N):
TT[i][j]=min(TT[i][j],T[i][k]+T[k][j])
return TT

7. Tinit ne prend en compte que les arêtes i.e. les chemins de longueur ≤ 1. Un passage par FW
permet de prendre en compte les chemins de longueur ≤ 2. Un second passage permet la prise en
compte de chemins de longueur ≤ 3. Comme on peut se limiter aux chemins simples de longueur
≤ N − 1, il suffit d’itérer N − 2 fois.
Dans le code ci-dessous, on modifie Tinit à chaque étape.

for i in range(N-2):
Tinit=FW(Tinit)

8. Quand on met à jour une case dans FW, c’est à dire quand T 0 [i, j] < T [i, j], on découvre un
meilleur chemin allant de i en concaténant des chemins de i à un certain k et de k à j. On
pourrait donc gérer un tableau donnant en case (i, j) un chemin optimal de i à j et faire évoluer
ce tableau.