#!/usr/bin/env python
# coding: utf-8
# # Table of Contents
#
# # Correction examen ALGO1 - Décembre 2019
#
# - [Page du cours](https://perso.crans.org/besson/teach/info1_algo1_2019/) : 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](https://perso.crans.org/besson/) (info) et [François Schwarzentruber](http://people.irisa.fr/Francois.Schwarzentruber/math1_algo1_2019/) (maths)
# + Travaux dirigés : [Raphaël Truffet](http://perso.eleves.ens-rennes.fr/people/Raphael.Truffet/) (info) et [Léo Henry](http://perso.eleves.ens-rennes.fr/people/leo.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)
# ## 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)
# ## 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)
# ## 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])
# 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)
# ---
# # 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")
get_ipython().run_line_magic('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")
get_ipython().run_line_magic('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")
get_ipython().run_line_magic('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](https://perso.crans.org/besson/teach/info1_algo1_2019/notebooks/CoursMagistral_8.html)
# + 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](https://duckduckgo.com/?q=code+for+red-black+tree+in+python&t=canonical&ia=web), notamment celle ci : [github.com/stanislavkozlovski/Red-Black-Tree](https://github.com/stanislavkozlovski/Red-Black-Tree).