Cours nº1 : Dictionnaires et Programmation Dynamique

Partie 1 : Dictionnaires

1. Listes

• Notation :

ma_liste = [1, 2, 3]

• Initialisation itérative (équivalence boucle for) :

ma_liste = []
for i in range(5):
    ma_liste.append(i)

ma_liste = [i for i in range(5)]

2. Types et Objets

Les objets que l'on manipule en python appartiennent à différents types (le mot classe est synonyme de type).

3. Pseudo code

Parfois il convient d'écrire les algorithmes en pseudo-code. C'est un langage qui n'a pas de syntaxe précise, l'unique but étant que ce soit facilement compréhensible par un autre humain.

Voici un exemple :

4. Dictionnaires

Un dictionnaire est un ensemble de couples (clé : valeur).

Voici trois manières d'initialiser un dictionnaire de la même façon :

ages = {"Alice": 20, "Bob": 20}

ages = {}
Prenoms = ["Alice", "Bob"]
for p in Prenoms:
    ages[p] = 20

ages = {p : 20 for p in Prenoms}

5. Premier exercice

• Objectif : manipuler un dictionnaire

reseau = {
    "alice92": {
        "nom": "Alice",
        "age": 20,
        "amis": ["bob34", "charlie21"]
    },
    "bob34": {
        "nom": "Bob",
        "age": 22,
        "amis": ["alice92", "diane19"]
    },
    "charlie21": {
        "nom": "Charlie",
        "age": 21,
        "amis": ["alice92"]
    },
    "diane19": {
        "nom": "Diane",
        "age": 19,
        "amis": ["bob34"]
    }
}

Créer les fonctions suivantes :

• Ajouter ajouter(pseudo, nom, age)
• Retirer retirer(pseudo)
• Nombre d'amis nombre_amis(pseudo)
• Amis en commun amis_communs(pseudo1, pseudo2)
• Amis d'ordre $n$ : amis_ordre(n, pseudo) (Difficile : Renvoie la liste des amis d'ordre exactement $n$)

Un ami d’ordre n est un utilisateur qui est à une distance de n dans le graphe des relations d’amitié.

Autrement dit :

• Amis d'ordre 0 → moi
• Amis d'ordre 1 → mes amis
• Amis d'ordre 2 → les amis de mes amis
• Amis d'ordre 3 → les amis des amis de mes amis

6. Un exercice utile

Je te conseille de faire cet exo pour être sûre de ne pas confondre les noms de variables avec les chaînes de caractères :

Essaie de prédire le résultat renvoyé par Python pour chacune des lignes suivantes :

>>> print("nom")
>>> print(nom)
>>> nom = "Bob"
>>> print(nom)
>>> animal = "chat"
>>> print("animal")
>>> print(animal)
>>> print("J'aime mon " + animal)
>>> print("J'aime mon " + "animal")

>>> print("nom")
# nom

>>> print(nom)
# NameError: name 'nom' is not defined

>>> nom = "Bob"
>>> print(nom)
# Bob

>>> animal = "chat"
>>> print("animal")
# animal

>>> print(animal)
# chat

>>> print("J'aime mon " + animal)
# J'aime mon chat

>>> print("J'aime mon " + "animal")
# J'aime mon animal

Partie 2 : Programmation Dynamique

1. Fibonacci

• Exemple avec la suite de Fibonacci :

Une fonction récursive naïve avec deux appels récursifs possède une complexité exponentielle !

# Version naïve
def fibo_naif(n):
    if n <= 1:
        return n
    return fibo_naif(n-1) + fibo_naif(n-2)

Pour éviter de recalculer plusieurs fois les mêmes valeurs, on peut utiliser la programmation dynamique (mémoïsation) :

# Version optimisée avec mémoïsation
fibo = {0: 0, 1: 1}

def fibo_dyn(n):
    if n not in fibo:
        fibo[n] = fibo_dyn(n-1) + fibo_dyn(n-2)
    return fibo[n]

Idée clé : on enregistre les résultats déjà calculés dans le dictionnaire fibo pour ne pas refaire les mêmes appels récursifs.

La complexité est ramenée de O(2ⁿ) à O(n).

2. Problèmes d’optimisation vs problèmes de décision

Un problème de décision se formule toujours comme :

Données : un ensemble d’éléments (entiers, objets, graphes, etc.)

Question : Une question par laquelle on répond soit par Oui soit par Non

Un problème d’optimisation cherche à maximiser ou minimiser une quantité. Il se formule comme :

Données : un ensemble d’éléments (entiers, objets, graphes, etc.)

Question : Quelle solution $s\in {\cal S}$ maximise (ou minimise) une valeur $V(s)$ ?

À noter que pour les problèmes d'optimisation il faut définir au préalable un ensemble de solutions possibles $\cal S$ et une fonction $V : {\cal S} \to \mathbb{R}$.

3. Problèmes d’optimisation classiques

Voici deux problèmes d’optimisation classiques (uniquement pour la culture) :

3.1 Problème du voyageur de commerce (TSP)

Données : Un ensemble de villes et les distances entre elles.

Question : trouver l’ordre de visite de toutes les villes en revenant au point de départ qui minimise la distance totale parcourue.

C’est un problème de minimisation.

3.2 Problème du sac à dos (Knapsack Problem)

Données : Une collection d’objets ayant chacun un poids et une valeur, et un poids maximal autorisé.

Question : choisir les objets à placer dans le sac pour maximiser la valeur totale sans dépasser le poids maximal autorisé.

C’est un problème de maximisation.

4. Plus longue sous-suite commune (exercice classique)

Données : deux suites finies $S = (s_i)_{0 \le i \le m-1}$ et $T = (t_j)_{0 \le j \le n-1}$.

Question : trouver une suite $Z = (z_k)_{0 \le k \le p-1}$ qui soit une sous-suite extraite à la fois de $S$ et de $T$, et dont la longueur $p$ soit maximale.

On cherche donc la plus longue sous-suite commune (PLSC) entre $S$ et $T$.

4.1 Idée naïve

La pire approche consiste à générer toutes les sous-suites extraites possibles de $S$ et de $T$, puis à tester lesquelles sont communes et retenir la plus longue. Cette méthode est incomputable en pratique, car le nombre de sous-suites possibles d’une suite de longueur $m$ est $2^m$.

Heureusement, on a un ✨ théorème ✨ :

Théorème — Récurrence fondamentale de la PLSC

Deux cas se présentent :

1. Si $s_{m-1} = t_{n-1}$, alors

$$z_{p-1} = s_{m-1} = t_{n-1}$$

et

$$Z[0:p-1] = PLSC(S[0:m-1], T[0:n-1])$$

(notation Python : les tranches excluent le dernier indice).

2. Si $s_{m-1} \neq t_{n-1}$, alors :

a) Si $z_p \neq s_{m-1}$,

$$Z = PLSC(S[0:m-1], T)$$

b) Si $z_p \neq t_{n-1}$,

$$Z = PLSC(S, T[0:n-1])$$

💡 Ce théorème permet une formulation récursive efficace, base de l’algorithme de programmation dynamique pour la PLSC.

4.2 Version récursive (non dynamique)

def PLSC(S,T):
    if S=="" or T=="":
        return ""
    if S[-1]==T[-1]:
        return PLSC(S[0:-1],T[0:-1]) + S[-1]
    else:
        L1=PLSC(S[0:-1],T)
        L2=PLSC(S,T[0:-1])
        if len(L1)>=len(L2):
            return L1
        else:
            return L2

Complexité exponentielle : $\cal O(2^{n+m})$ dans le pire des cas !

4.3 Version récursive dynamique (descendante)

On rappelle que récursif = descendant.

dico={}  
def PLSC2(S,T):
    if S=="" or T=="":
        return ""
    if S[-1]==T[-1]:
        return PLSC2(S[0:-1],T[0:-1]) + S[-1]
    if (S,T) in dico:
        return dico[(S,T)]
    else:
        L1=PLSC2(S[0:-1],T)
        L2=PLSC2(S,T[0:-1])
        if len(L1)>=len(L2):
            dico[(S,T)] = L1
        else:
            dico[(S,T)] = L2
        return dico[(S,T)]

Complexité quadratique : $\cal O(n*m)$ dans le pire des cas.

La version itéraive ascendante permet de comprendre pourquoi la complexité est quadratique.

4.4 Version itérative ascendante (déconseillé)

On rapelle que itératif = ascendant.

On remarque que le dictionnaire n'a que des clés du type $S = (s_0, ..., s_i)$ et $T = (t_0, ..., t_j)$ avec $i<m$ et $j<n$.

On commence alors par remplir les valeurs de base du dictionnaire puis on remplit tout le reste dans le bon ordre.

Voici un dessin qui explique bien cela :

On utilise un tableau dp de taille $(m+1) \times (n+1)$ où dp[i][j] stocke la PLSC pour les préfixes $S[0:i]$ et $T[0:j]$.

def PLSC_iterative(S, T):
    m, n = len(S), len(T)
    dp = [["" for _ in range(n + 1)] for _ in range(m + 1)]
    
    # Remplissage du tableau
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if S[i-1] == T[j-1]:
                dp[i][j] = dp[i-1][j-1] + S[i-1]
            else:
                if len(dp[i-1][j]) > len(dp[i][j-1]):
                    dp[i][j] = dp[i-1][j]
                else:
                    dp[i][j] = dp[i][j-1]
    
    return dp[m][n]

Complexité :

• Temps : $\mathcal{O}(m \cdot n)$ pour le remplissage du tableau.
• Espace : $\mathcal{O}(m \cdot n)$ pour le tableau dp.