Description

Brian.Pulfer@unige.ch
Remarques:
Veuillez suivre attentivement les sp´ecifications de l’´enonc´e.
• R´eponses – Essayez d’ˆetre exhaustif dans vos r´eponses. Les r´eponses comme ”oui” et ”non” ne permettent pas d’´evaluer vos connaissances.
• Points extra – Le nombre maximum de points pouvant ˆetre marqu´es pour un TP est de 5, ce qui conduit `a une note de 6. Vous pouvez effectuer les exercices 2 et 3 pour obtenir des points suppl´ementaires. Marquer plus de 5 points est toujours arrondi `a la note 6.
• Trac´es – Mettez toujours des ´etiquettes d’axe et des titres pour les trac´es.
• Impl´ementation – Veuillez utiliser exactement les noms fournis pour les fonctions. Vous pouvez utiliser pytest avec le script de test donn´e pour v´erifier votre impl´ementation.
• Soumission
Merci de t´el´echarg´e vos devoirs sur moodle:
– NomPrenom.pdf avec votre rapport pour tout les exercices – tp4.py avec votre implementations
– Pas d’autres fichiers (.pyc, .ipynb, DS Store, pycache , …)
• Pour toute questions et remarques, merci d’utiliser le mail Brian.Pulfer@unige.ch.
1 Voyage en train (5 Points)
Commen¸cons par nous int´eresser `a un cas particulier, le voyage en train le long de la ligne RE Annemasse – St-Maurice des CFF. Les prix diff´erents de diff´erentes communaut´es tarifaires et les prix intercommunautaires ont une structure assez particuli`ere. Les diff´erents prix peuvent ˆetre r´esum´es sous la forme d’une matrice M que voici:
Annemasse Gen`eve Coppet Nyon Morges Lausanne Vevey St-Maurice
Annemasse 0
Gen`eve 4.9 0
Coppet 6 3 0
Nyon 7.6 4.5 2.8 0
Morges 11.4 9.3 8.3 6.5 0
Lausanne 14 11.4 11.1 9.3 3.7 0
Vevey 16.5 14 13.9 12.9 7.4 5.6 0
St-Maurice 21 19 13.9 13.9 13.9 12 7.4 0
On remarque que, pour certains trajets, la somme du prix des ´etapes ”atomiques” entre deux villes peut ˆetre plus grande, ´egale ou plus petite que le prix pour le train direct.
Dans le cas ou` l’on voudrait faire le trajet Annemasse-St-Maurice, la somme du prix des ´etapes couˆterait CHF 33.90, le trajet direct CHF 21.-, mais le trajet optimal, qui consiste `a faire AnnemasseCopet-St-Maurice, couˆtera seulement CHF 19.90.
Nous allons pour cet exercice consid´erer le cas g´en´eral ou` il y a n villes, soit un nombre maximal de n − 2 ´etapes interm´ediaires. Lors d’un trajet, on ne revient jamais en arri`ere (d’ou` le fait que M soit `a moiti´e vide). On est libre de prendre n’importe quel nombre de sous-trajets. Le but est d’analyser et d’impl´ementer une strat´egie de programmation dynamique pour trouver le couˆt optimal pour aller de la ville num´ero 0 `a la ville num´ero n − 1. Pour ce faire, nous proposons de remplir un tableau T des couˆts optimaux, c’est-`a-dire un tableau similaire `a la matrice M ci-dessus, ne comprenant non pas les couˆts ”officiels” de la compagnie ferroviaire, mais les couˆts optimaux pour chaque sous-trajet. Par exemple, la case correspondant au trajet Annemasse-St-Maurice aurait une valeur de 19.90.
1.1 Fonction de r´ecurrence
• Nous avons d´efini ci-dessus en quoi consiste la matrice T des couˆts optimaux. Donnez une relation de r´ecurrence de T qui permette de trouver la valeur de Tij (=couˆt optimal pour aller de la ville num´ero i `a la ville num´ero j).N’oubliez pas que le couˆt optimal (minimal) d’un trajet est le minimum des couˆts de l’ensemble des trajets possibles. Justifiez.
• Votre formule de r´ecursion a-t-elle un impacte sur la mani`ere de ”remplir” T? Si oui, lequel?
1.2 Impl´ementation
Impl´ementez un solver pour ce probl`eme avec une strat´egie de programmation dynamique utilisant la fonction de r´ecursion que vous donnez `a la question 1.1.
Dans le code python que vous devez rendre, il doit contenir une fonction get_solution qui a comme:
• input la matrice des couˆts de la compagnie ferroviaire M, sous forme de liste de liste.
• output la matrice T des couˆts correspondants (sous forme de liste de liste), le chemin optimal (sous forme de liste) et le couˆt du chemin optimal entre la ville 0 et la ville n − 1.
1.3 Complexit´e en temps
• Quelle est selon vous la complexit´e en temps (en fonction de n) de l’algorithme de programmation dynamique (donn´e au point 1.1) pour r´esoudre le probl`eme? Argumentez. • Est-ce que la complexit´e de temps effective de votre algorithme de programmation dynamique impl´ement´e au point 1.2 correspond `a la complexit´e th´eorique donn´ee au-dessus? Argumentez
NB: Pour produire le graphique demand´e `a la question 1.3, vous pouvez utiliser la m´ethode de votre choix. La librairie matplotlib permet n´eanmoins de cr´eer rapidement des graphiques en python. Les graphiques doivent avoir un titre ainsi que des axes nomm´es et avec des unit´es le cas ´ech´eant.
2 Rendu de la monnaie (extra 0.5 Point)
Impl´ementez en python la strat´egie de programmation dynamique vue en cours pour le probl`eme du rendu de la monnaie.
3 Sequences (extra 0.5 Point)
3.1 Plus longue sous-s´equence commune
Soient deux s´equences A = a1,…an et B = b1,…,bn de symboles issus d’un alphabet Ω. La plus longue s´equence de symboles identiques entre A et B est nomm´ee plus longue sous-s´equence commune (longest common sub-sequence). Par exemple, soient les s´equences A = [a,c,t,g,a,a] et B = [c,g,a,t]: la plus longue sous-s´equence est [c,g,a].
• Trouver une solution dynamique au probl`eme (le but est de retourner la longueur de la plus longue sous-s´equence commune).
• N > 2 le nombre de s´equences `a comparer. Notre solution dynamique fonctionne-t-elle toujours?
3.2 Plus longue sous-chaˆıne commune
Soient deux s´equences A = a1,…an et B = b1,…,bn de symboles issus d’un alphabet Ω. La plus longue chaˆıne de symboles identiques entre A et B est nomm´ee plus longue sous-chaˆıne commune (longest common substring).
• Le probl`eme est-il identique au pr´ec´edent ?
• Trouver une solution dynamique au probl`eme.