#!/usr/bin/env python # coding: utf-8 # # Table of Contents #

1  Correction examen ALGO1 - Décembre 2019
2  Problème 1 : Programmation dynamique
2.1  Question 2.
2.2  Question 3.
2.3  Question 4.
2.4  Question 5.
3  Problème 3 : Morito
3.1  Question 1. echanger
3.2  Question 2. morito
3.2.1  Question 3. Exemple
3.2.2  Question 5. Complexité temporelle ?
4  Conclusion
# # 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).