Correction examen ALGO1 - Décembre 2019


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]:
[1, 1, 1, 2, 2, 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]:
3

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)
- C[1] = 1.
- C[2] = 0 (il n'y pas de dé compatible à gauche de la 2ème pièce).
- C[3] = 0 (il n'y pas de dé compatible à gauche de la 3ème pièce).
- C[4] = max(1, C[1]+1) = 2 (les dés 1 et 4 sont compatibles).
- C[5] = max(1, C[2]+1) = 2 (les dés 2 et 5 sont compatibles).
- C[6] = max(1, C[3]+1, C[5]+1) = 3 (les couples 3-6 et 5-6 sont compatibles).
Out[21]:
[1, 1, 1, 2, 2, 3]

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]:
5
Out[25]:
4
Out[25]:
3
Out[25]:
2
Out[25]:
1
Out[25]:
0

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)
Une chaine de longueur maximale = 3 a été trouvée :
[A|Z], [Z|V], [V|X]
Out[36]:
([5, 4, 1], [('A', 'Z'), ('Z', 'V'), ('V', 'X')])

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)
[16, 18, 19, 12, 2019]
[12, 16, 18, 19, 2019]
In [57]:
tableau = [16, 18, 19, 12, 2019]
print(tableau)

morito(tableau, verb=True)
print(tableau)
[16, 18, 19, 12, 2019]
Début pour croissant...
  Tableau = [16, 18, 19, 12, 2019] et i = 0
  Tableau = [16, 18, 19, 12, 2019] et i = 1
  Tableau = [16, 18, 19, 12, 2019] et i = 2
    T[2] = 19 > 12 = T[3] sont échangés
  Tableau = [16, 18, 12, 19, 2019] et i = 3
Début pour décroissant...
  Tableau = [16, 18, 12, 19, 2019] et i = 3
  Tableau = [16, 18, 12, 19, 2019] et i = 2
  Tableau = [16, 18, 12, 19, 2019] et i = 1
    T[1] = 18 > 12 = T[2] sont échangés
  Tableau = [16, 12, 18, 19, 2019] et i = 0
    T[0] = 16 > 12 = T[1] sont échangés
Début pour croissant...
  Tableau = [12, 16, 18, 19, 2019] et i = 0
  Tableau = [12, 16, 18, 19, 2019] et i = 1
  Tableau = [12, 16, 18, 19, 2019] et i = 2
  Tableau = [12, 16, 18, 19, 2019] et i = 3
Début pour décroissant...
  Tableau = [12, 16, 18, 19, 2019] et i = 3
  Tableau = [12, 16, 18, 19, 2019] et i = 2
  Tableau = [12, 16, 18, 19, 2019] et i = 1
  Tableau = [12, 16, 18, 19, 2019] et i = 0
Pas d'échange dans les deux parcours, l'algorithme s'arrête là.
[12, 16, 18, 19, 2019]

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)))
Pour des tableaux triés :
Pour n = 100, l'algorithme morito prends le temps suivant
16.7 µs ± 1.56 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
Pour n = 1000, l'algorithme morito prends le temps suivant
187 µs ± 6.52 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
Pour n = 10000, l'algorithme morito prends le temps suivant
2.04 ms ± 78.1 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
Pour n = 100000, l'algorithme morito prends le temps suivant
21.9 ms ± 1.31 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

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))
Pour des tableaux aléatoires :
Pour n = 100, l'algorithme morito prend le temps suivant
3 ms ± 189 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
Pour n = 1000, l'algorithme morito prend le temps suivant
287 ms ± 9.97 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
Pour n = 10000, l'algorithme morito prend le temps suivant
30.5 s ± 1.45 s per loop (mean ± std. dev. of 7 runs, 1 loop each)

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])
Pour des tableaux triés par ordre décroissant :
Pour n = 100, l'algorithme morito prend le temps suivant
2.18 ms ± 324 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
Pour n = 1000, l'algorithme morito prend le temps suivant
203 ms ± 41.2 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
Pour n = 10000, l'algorithme morito prend le temps suivant
20.4 s ± 2.44 s per loop (mean ± std. dev. of 7 runs, 1 loop each)

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