Exam tips

Question 1

Question de code

Answer 1

Vérifier si il y a du code à la toute fin de l’exercice.

Question 2

Analyse d’algorithmes 1 boucle

Answer 2

• Poser soit K le nombre d’intégrations
• Expliciter la condition de fin
• Déterminer la plus petite valeur de K vérifiant la condition d’arrêt
• Conclure

Question 3

Implémentation de List : Généralement lorsqu’on écrit begin() et end() ne pas oublier qu’on veut retourner des …

Answer 3

ITERATOR (à la place des nodes directement).

Question 4

Prouver que belman-ford renvoi vrai seulement s’il n’y a pas de cycle de longueur négative

Answer 4

1- Définir un cycle < v0, v1, .., vk >

2- Poser la condition qui retourne vrai :
dv1 <= dv0 + w(v0, v1)

3 - Donc dv1 + dv2 + .. dvk <= dv0+dv1+..+dvk-1 + w(v0,v1) + w(v1,v2)+..+w(vk-1, vk)

4 - On simplifie par dv1+..+dvk-1 qui sont de chaque bord.
dv0 <= dvk + w(v0,v1) + w(v1,v2)+..+w(vk-1, vk)

5- Énoncer dv0 = dvk car c’est un cycle

6- Donc
0 <= w(v0,v1) + w(v1,v2)+..+w(vk-1, vk)

7- donc la longueur du cycle doit être >= 0 CQFD.

Question 5

Prouver que Belman-Ford va renvoyer le plus court chemin

Answer 5

• Poser un plus court chemin v0,v1,.., vk
• Pas de cycle de longueur négative donc |S|-1 arcs au plus par chemin.
• Tous les arcs de S sont relâchés à chaque |S| - 1 itérations
• (v0,v1) sera relâché à l’itération 1
• (vi-1,vi) sera relâché à l’itération i
• Donc tous les arcs du plus court chemin de v0 à vk seront relâchés dans l’ordre au court des |S|-1 itérations nonobstant les relâchements intermédiaires.
• Cela vérifie la propriété des relâchementss des plus court chemin donc dvk = D(v0, vk) = le plus court chemin de v0 à vk.