Table of Contents¶
Correction examen ALGO1 - Décembre 2019¶
- Page du cours : https://perso.crans.org/besson/teach/info1_algo1_2019/
- Magistère d'Informatique (L3 SIF) & L3 Maths de Rennes - ENS Rennes - Année 2019/2020
- Intervenants :
- Cours : Lilian Besson (info) et François Schwarzentruber (maths)
- Travaux dirigés : Raphaël Truffet (info) et Léo Henry (maths)
Problème 1 : Programmation dynamique¶
On va représenter les dominos et les chaînes de domino de façon naïve :
In [1]:
exemple_dominos = [
("A", "H"),
("A", "Z"),
("K", "V"),
("H", "K"),
("Z", "V"),
("V", "X"),
]
Question 2.¶
On peut implémenter l'algorithme de "programmation dynamique" naïvement :
In [2]:
def calculer_tableau_C(dominos):
n = len(dominos)
x = [D[0] for D in dominos]
y = [D[1] for D in dominos]
C = [0] * n
C[0] = 1
for i in range(1, n):
meilleur = 1
for j in range(0, i-1 + 1):
if y[j] == x[i] and C[j] + 1 > meilleur:
meilleur = C[j] + 1
C[i] = meilleur
return C
Et par exemple :
In [3]:
calculer_tableau_C(exemple_dominos)
Out[3]:
Question 3.¶
In [4]:
def longueur_sous_chaine_la_plus_longue(dominos):
return max(calculer_tableau_C(dominos))
Et par exemple :
In [5]:
longueur_sous_chaine_la_plus_longue(exemple_dominos)
Out[5]:
Question 4.¶
On va juste réécrire la fonction de la question 2, en ajoutant de l'affichage :
In [22]:
def calculer_tableau_C_verbose(dominos):
n = len(dominos)
x = [D[0] for D in dominos]
y = [D[1] for D in dominos]
C = [0] * n
C[0] = 1
i = 0
print(f"- C[{i+1}] = {C[i]}.")
for i in range(1, n):
meilleur = 1
list_of_possible_j = []
list_of_values_in_max = [1]
for j in range(0, i-1 + 1):
if y[j] == x[i] and C[j] + 1 > meilleur:
meilleur = C[j] + 1
list_of_possible_j.append(j)
list_of_values_in_max.append(C[j] + 1)
C[i] = meilleur
if len(list_of_possible_j) > 1:
s1 = ", ".join(f"C[{j+1}]+1" for j in list_of_possible_j)
s2 = " et ".join(f"{j+1}-{i+1}" for j in list_of_possible_j)
print(f"- C[{i+1}] = max(1, {s1}) = {C[i]} (les couples {s2} sont compatibles).")
elif len(list_of_possible_j) == 1:
j = list_of_possible_j[0]
print(f"- C[{i+1}] = max(1, C[{j+1}]+1) = {C[i]} (les dés {j+1} et {i+1} sont compatibles).")
else:
print(f"- C[{i+1}] = {C[i+1]} (il n'y pas de dé compatible à gauche de la {i+1}ème pièce).")
return C
Et par exemple :
In [21]:
calculer_tableau_C_verbose(exemple_dominos)
Out[21]:
Question 5.¶
On va avoir besoin d'une fonction argmax :
In [23]:
def argmax(tableau):
position = 0
valeur = tableau[position] # Invariant: max(T[0],...,T[i])
for i in range(1, len(tableau)):
if tableau[i] > valeur:
valeur = tableau[i]
# Invariant: valeur' = max(T[0],...,T[i+1]) = max(valeur, T[i+1])
position = i
return position
In [25]:
argmax([1, 1, 1, 2, 2, 3])
argmax([1, 1, 2, 2, 3, 1])
argmax([1, 2, 2, 3, 1, 1])
argmax([2, 2, 3, 1, 1, 1])
argmax([2, 3, 1, 1, 1, 2])
argmax([3, 1, 1, 1, 2, 2])
Out[25]:
Out[25]:
Out[25]:
Out[25]:
Out[25]:
Out[25]:
Pour chaque $i$, il faut mémoriser le meilleur dé $j$ à mettre à gauche de $D[i]$.
Puis on prend le $i$ qui maximise $C[i]$, et on compose la sous-chaı̂ne optimale de droite à gauche : $i$, puis $J[i]$, puis $J[J[i]]$ etc, jusqu’à tomber sur un $0$.
Cela donne l'algorithme suivant :
In [35]:
def calculer_sous_chaine_longueur_maximale(dominos):
n = len(dominos)
x = [D[0] for D in dominos]
y = [D[1] for D in dominos]
C = [0] * n
J = [0] * n
C[0] = 1
J[0] = 0
for i in range(1, n):
meilleur = 1
for j in range(0, i-1 + 1):
if y[j] == x[i] and C[j] + 1 > meilleur:
meilleur = C[j] + 1
J[i] = j
C[i] = meilleur
i_maximisant_C = argmax(C)
i = i_maximisant_C
chaine_maximale = [i]
while J[i] != 0:
chaine_maximale.append(J[i])
i = J[i]
chaine = [dominos[i] for i in chaine_maximale[::-1]]
print(f"Une chaine de longueur maximale = {max(C)} a été trouvée :")
print(", ".join(f"[{d[0]}|{d[1]}]" for d in chaine))
return chaine_maximale, chaine
Et par exemple :
In [36]:
calculer_sous_chaine_longueur_maximale(exemple_dominos)
Out[36]:
Problème 3 : Morito¶
Question 1. echanger¶
In [37]:
def echanger(tableau, i, j):
tmp = tableau[i]
tableau[i] = tableau[j]
tableau[j] = tmp
# en Python, on peut aussi faire
# tableau[i], tableau[j] = tableau[j], tableau[i]
Question 2. morito¶
On implémente l'algorithme "mystère" :
In [55]:
def morito(tableau, verb=False):
n = len(tableau)
échangé = True
while échangé:
échangé = False
if verb: print("Début pour croissant...")
for i in range(0, n-2 + 1):
if verb: print(f" Tableau = {tableau} et i = {i}")
if tableau[i] > tableau[i+1]:
if verb: print(f" T[{i}] = {tableau[i]} > {tableau[i+1]} = T[{i+1}] sont échangés")
echanger(tableau, i, i+1)
échangé = True
if verb: print("Début pour décroissant...")
for i in range(n-2, 0 - 1, -1):
if verb: print(f" Tableau = {tableau} et i = {i}")
if tableau[i] > tableau[i+1]:
if verb: print(f" T[{i}] = {tableau[i]} > {tableau[i+1]} = T[{i+1}] sont échangés")
echanger(tableau, i, i+1)
échangé = True
if verb: print("Pas d'échange dans les deux parcours, l'algorithme s'arrête là.")
Question 3. Exemple¶
Par exemple :
In [56]:
tableau = [16, 18, 19, 12, 2019]
print(tableau)
morito(tableau)
print(tableau)
In [57]:
tableau = [16, 18, 19, 12, 2019]
print(tableau)
morito(tableau, verb=True)
print(tableau)
Question 5. Complexité temporelle ?¶
- Dans le meilleur cas, l'algorithme s'exécute en temps linéaire, ie., $\mathcal{O}(n)$ si $n$ est la longueur du tableau $T$. Le meilleur cas correspond à un tableau trié par ordre croissant.
In [59]:
print("Pour des tableaux triés par ordre croissant :")
for n in [100, 1000, 10000, 100000]:
print(f"Pour n = {n}, l'algorithme morito prend le temps suivant")
%timeit morito(list(range(n)))
Ce petit exemple montre que la complexité temporelle empirique semble bien linéaire : multiplier $n$ par $10$ multiplie le temps de calcul par $10$ aussi !
- Dans le cas moyen, l'algorithme s'exécute en temps quadratique, ie., $\mathcal{O}(n^2)$.
In [60]:
import numpy.random as rd
def tableau_aleatoire(n):
return rd.randint(-1000, 1000, n)
In [62]:
print("Pour des tableaux aléatoires :")
for n in [100, 1000, 10000]:
print(f"Pour n = {n}, l'algorithme morito prend le temps suivant")
%timeit morito(tableau_aleatoire(n))
Ce petit exemple montre que la complexité temporelle empirique semble bien quadratique : multiplier $n$ par $10$ multiplie le temps de calcul par $10^2=100$ ! (le temps est plus long que pour le pire cas ci dessous, mais c'est à cause du temps pris par le calcul d'un tableau aléatoire, pas le reste)
- Dans le pire cas, l'algorithme s'exécute aussi en temps quadratique, ie., $\mathcal{O}(n^2)$.
In [63]:
print("Pour des tableaux triés par ordre décroissant :")
for n in [100, 1000, 10000]:
print(f"Pour n = {n}, l'algorithme morito prend le temps suivant")
%timeit morito(list(range(n))[::-1])
Ce petit exemple montre que la complexité temporelle empirique semble bien quadratique : multiplier $n$ par $10$ multiplie le temps de calcul par $10^2=100$ !
Conclusion¶
Regardez aussi la correction papier au partiel (envoyée par mail).
Les autres problèmes pourraient aussi être implémentés, mais :
- le notebook du cours #8 sur les flots traitent déjà le problème 4
- le problème 2 ne demande pas de proposer un algorithme, mais les arbres rouge-noir peuvent être implémentés sans trop de difficultés, et on pourrait tester empiriquement les différents points du problème 2. Voir par exemple des implémentations en Python, notamment celle ci : github.com/stanislavkozlovski/Red-Black-Tree.