Algorithmes Classiques

La suite de Fibonacci est définie par récurrence double :

\[ F_0 = 0 ,\, F_1 = 1 ,\, F_{n+2} = F_{n+1} + F_{n} \]

Entrées : un entier \(n \geq 0\)
Sortie : \(F_n\)

def fibonacci(n) :
    f = 0
    if n > 0 : # Si n = 0, il n'y a aucun calcul à faire
        # Rang 1
        f = 1
        f_prev = 0
        rang = 1
        # Calcul du rang n en calculant chaque rang i successivement
        while rang != n :
            f_suivant = f + f_prev
            f_prev = f
            f = f_suivant
            rang = rang + 1
    return f

La suite de Syracuse est définie par récurrence :

\[S_{{n+1}}={\begin{cases}{\dfrac {S_{n}}{2}}&{\mbox{si }}S_{n}{\mbox{ est pair,}}\\3S_{n}+1&{\mbox{si }}S_{n}{\mbox{ est impair.}}\end{cases}} \]

Entrées : un entier \(s \geq 1\)
Sortie : Le premier entier \(n \geq 0\) tel que \(S_n = 1\)

def syracuse(s0) :
    # Rang 0
    s = s0
    rang = 0
    # Calcul du rang suivant dans s, jusqu'à ce que s == 1
    while s != 1 :
        rang = rang + 1
        if s % 2 == 0 :
            s = s // 2
        else :
            s = 3 * s + 1
    return rang

Entrées : une liste d’entiers relatifs.
Sortie : la somme des entiers de la liste.

def somme_liste(l) :
    somme = 0
    for x in l  :
        somme = somme + x
    return somme

Complexité : \(\O(\symtt{len}(l))\).
Invariant : On note \(i\) l’indice de \(x\) dans \(l\). \[I : \symtt{somme} = \symtt{sum(L[:i])} = \sum_{k = 0}^{i-1} \symtt{L[k]} \]

Entrées : une liste d’entiers L
Sortie : l’indice du maximum de la liste

def imax(l) :
    if len(l) == 0 :
        return -1
    i_max = 0
    maxi = l[0]
    for i in range(len(l)) :
        if l[i] > maxi :
            maxi = l[i]
            i_max = i
    return i_max

Complexité : \(\O(\symtt{len}(l))\).
Invariant : \(\symtt{maxi} = \symtt{max(L[:i])}\) et \(\symtt{L[i\_max]} = \symtt{maxi}\)

Entrées : Liste l et un élément x
Sortie : L’indice de la première occurrence de x dans l, ou -1 si x n’est pas dans l

def recherche_lineaire(l, x) :
    i_x = -1
    i = 0
    n = len(l)
    while i < n and i_x == -1 :
        if l[i] == x :
            i_x = i
        i = i + 1
    return i_x

Complexité : \(\O(\symtt{len}(l))\).
Invariant : En posant \(\min(\emptyset) = -1\), \[\symtt{i\_x} = \min\{ 0 \leq k < i \, | \, \symtt{L[k] = x}\}\]

Entrées : Liste l et un élément x
Sortie : L’indice de la première occurrence de x dans l, ou -1 si x n’est pas dans l

def recherche_lineaire(l, x) :
    for i in range(len(l)) :
        if l[i] == x :
            return i
    return -1

Complexité : \(\O(\symtt{len}(l))\).
Invariant : \(\symtt{x} \not\in \symtt{l[:i]}\)

Entrées : Liste d’entiers positifs, disjoints, l de taille supérieure à 2
Sortie : Le second minimum de l

def deuxieme_minimum(l) :
    if l[0] < l[1] :
        m = l[0]
        second_m = l[1]
    else :
        m = l[1]
        second_m = l[0]
    for x in l[2:] :
        if x < m :
            second_m = m
            m = x
        elif x < second_m :
            second_m = x
    return second_m

Complexité : \(\O(\symtt{len}(l))\).
Invariant : On note \(i\) l’indice de \(x\). \[ \symtt{m} = \symtt{min(L[:i])} \text{ et } \symtt{second_m} = \symtt{min(L[:i]} \setminus \{ \symtt{m} \} ) \]

Entrées : s, w deux chaînes de caractères non vides.
Sortie : i >= 0, le plus petit indice de s tel que w est une sous-chaîne de s à la position i.

def rechercher(s,w) :
    n = len(s)
    m = len(w)
    # Recherche linéaire (for) d'une fenetre qui contient w
    for i in range(0,n-m+1) :
        # Recherche linéaire (while) d'un caractère différent
        # dans la fenêtre.
        j = 0
        i_diff = -1
        while j < m :
            if w[j] != s[i+j] :
                i_diff = j
            j += 1
        # Si on n'a pas trouvé de caractère dans la fenêtre
        # c'est la bonne fenêtre.
        if i_diff == -1 :
            return i
    return -1

Complexité : \(\O(\symtt{len}(s)\,\symtt{len}(w))\).
Invariants : Ce sont les invariants des recherches linéaires.

Entrées : n, m deux entiers positifs non nuls
Sortie : Une matrice de dimension \(n \times m\) remplie de None

def matrice(n,m) :
    M = []
    for i in range(n) :
        L = [ None ] * m
        M.append(L)
    return M

ou

def matrice(n,m) :
    return [ [ None ] * m for i in range(n) ]

Complexité : \(\O(nm)\).

Entrées : m une matrice \(p\times q\)
Sortie : Une copie de m

def copie(m) :
    m_copie = []
    for l in m : # pour chaque ligne de m
        l_copie = []
        for x in l : # pour chaque élément de la ligne
            l_copie.append(x)
        m_copie.append(l_copie)
    return m_copie

ou

def copie(M) :
    return [ [ x for x in L ] for L in M ]

Complexité : \(\O(pq)\).

Entrées : m une matrice \(p \times q\), d’entiers entre 0 et 255
Sortie : h, l’histogramme de m. i.e. une liste de taille 256 telle que h[i] soit le nombre d’occurrences de i dans m.

def histogramme(m) :
    h = [0]*256
    for l in m : # Pour chaque ligne de M
        for x in l : # Pour chaque élément de la ligne
            h[x] += 1
    return h

Complexité : \(\O(pq)\).

On suppose que le système monétaire choisi permet toujours de rendre la monnaie.
Entrées : Un liste, L, de billets (entiers) dans l’ordre croissant et un montant, m, (entier).

Sortie : Une liste de billet de L dont la somme vaut m de taille minimale.

def rendu(L,m) :
    R = []
    reste = m
    i = len(L)-1 # i représente le plus gros billet éventuellement utilisable.
    while reste > 0 :
        if L[i] <= reste : # si on peux utiliser le plus gros billet, on l'utilise
            R.append(L[i])
            reste = reste - L[i]
        else : # sinon on considère le billet d'en dessous.
            i = i-1
    return R

Complexité : \(\O(\symtt{len(L) + reste}\)\).
Invariants : \(\symtt{reste + sum(R) = m}\).
Variant : \(\symtt{reste}+i\)

Entrées : \(a\) un entier et \(b\) un entier positifs.
Sortie : \(a^b\)

def exponentiation_rapide(a,b) :
    r = 1
    u = a
    v = b
    while v > 0 :
        if v % 2 == 1 :
            r = r * u
        u = u * u
        v = v // 2
    return r

Complexité : \(\O(\log_{2}(b))\).
Invariants : \(ru^{v} = a^{b}\).
Variant : \(\symtt{v}\)

Entrées : Une liste d’entiers triés dans l’ordre croissant et un entier x.
Sortie : -1 si x n’est pas dans L ; l’indice de x dans L sinon.

def recherche_dichotomique(L,x) :
    debut = 0
    fin = len(L)
    while fin - debut > 0 :
        milieu = (debut + fin) // 2
        if L[milieu] == x :
            return milieu
        elif L[milieu] < x :
            debut = milieu + 1
        else :
            fin = milieu
    return -1

Complexité : \(\O(\log_{2}(\symtt{len}(L)))\).
Invariants : \(x \not\in \symtt{L[:debut]}\) et \(x \not\in \symtt{L[fin:]}\).
Variant : \(\symtt{fin-debut}\)

Entrées : une liste d’entiers.
Sortie : la somme des éléments de la liste.

On défini \(\symtt{somme\_rec(L,i)} = \sum_{\symtt{k}=0}^{\symtt{i}-1} \symtt{L[k]}\) par la formule de récurrence suivante : \[ \symtt{somme\_rec(L,i)} = \begin{cases} 0 & \text{si } \symtt{i} = 0 \\ \symtt{somme\_rec(L,i-1)} + \symtt{L[i-1]} & sinon \end{cases} \]

def somme_rec(L, i) :
    """
    Entrées : L une liste d'entier, $0 \leq i \leq \symtt{len}(L)$.
    Sorties : \symtt{sum(L[:i])
    """
    if i == 0 :
        return 0
    s = somme_rec(L,i-1)
    return s + L[i-1]
 
def somme(L) :
    return somme_rec(L,len(L))

Entrées : une liste d’entiers relatifs.
Sortie : le maximum de la liste

On défini \(\symtt{maximum\_rec(L,i)} = \symtt{max(L[:i]})\) par la formule de récurrence suivante : \[ \symtt{maximum\_rec(L,i)} = \begin{cases} -\infty & \text{si } \symtt{i} = 0 \\ max(\symtt{maximum\_rec(L,i-1)}, \symtt{L[i-1]}) & sinon \end{cases} \]

def maximum_rec(L, i) :
    """
    Entrées : L une liste d'entier, $0 \leq i \leq \symtt{len}(L)$.
    Sorties : \symtt{max(L[:i])
    """
    if i == 0 :
        return -float('inf')
    m = maximum_rec(L,i-1)
    if m > L[i-1] :
        return m
    return L[i-1]
 
def maximum(L) :
    return maximum_rec(L,len(L))

Entrées : \(a\) un entier et \(b\) un entiers positifs.
Sortie : \(a^b\)

\[ a^{b} = \begin{cases} 1 & \text{si } b = 0 \\ (a^{2})^{k} & \text{sinon si } b = 2\,k \\ a\,(a^{2})^{k} & \text{sinon, (i.e. } b = 2\,k+1) \end{cases}\]

def exp(a,b) :
    if b == 0 :
        return 1
    elif b % 2 == 0 :
        return exp(a * a , b // 2)
    else :
        return a * exp( a * a, b // 2)

Entrées : Une liste d’entiers
Sortie : Une copie de cette liste triée dans l’ordre croissant.

On suppose qu’il existe une fonction ayant la spécification suivante :

def fusion(l1 : list[int], l2 : list[int]) -> list[int] :
    """
    Entrées : deux listes d'entiers triés.
    Sortie: une liste triée contenant les éléments des deux listes en entrée.
    """

\[ \symtt{tri\_fusion(L)} = \begin{cases} \symtt{[]} & \text{si } \symtt{L = []} \\ \symtt{fusion(tri\_fusion(L[:n//2]),tri\_fusion(L[n//2:]))} & \text{sinon} \end{cases} \]

def tri_fusion(l) :
    n = len(l)
    if n < 2 :
        return l[:]
    l1 = tri_fusion(l[:n//2])
    l2 = tri_fusion(l[n//2:])
    return fusion(l1,l2)

Complexité : \(\O(n\,\log_2(n))\)

Entrées : Un entier n.
Sortie : Une chaîne donnant la représentation binaire de n.

\[ \symtt{bin(n)} = \begin{cases} \text{""} & \text{si } \symtt{n = 0} \\ \symtt{bin(n//2)} + \text{'0'} & \text{si n est pair} \\ \symtt{bin(n//2)} + \text{'1'} & \text{si n est impair} \end{cases} \]

def bin(n) :
    if n == 0 :
        return ""
    bin_quot = bin(n//2)
    if n % 2 == 0 :
        return bin_quot + "0"
    return bin_quot + "1"

Complexité : \(\O(\log_{2}(\symtt{n}))\).

Entrées : Deux entiers n et k tel que \(\symtt{n} \in \ints{-2^{\symtt{k}-1}}{2^{\symtt{k}-1}-1}\).
Sortie : Une liste donnant la représentation binaire de n en complément à 2 sur k bits.

def bin2(n, k) :
    if n == 0 :
        return "0"*k
    if n < 0 :
        return bin2(2**k + n, k)
    bin_quot = bin2(n//2)
    if n % 2 == 0 :
        return bin_quot + "0"
    return bin_quot + "1"

Complexité : \(\O(\log_{2}(\symtt{n}))\).

Entrées : Une chaîne de caractère s.
Sortie : Le nombre d’occurrence de chaque caractère dans un dictionnaire.

def nb_occ(s) :
    d = {}
    for c in s :
        if c  in d :
            d[c] += 1
        else :
            d[c] = 1
    return d

Complexité : \(\O(\symtt{len(s)})\).
Invariants : On note \(i\) l’indice de \(c\) dans \(s\). d est toujours le nombre d’occurrence de chaque caractère de s[:i].

Entrées : la liste d’adjacence d’un graphe orienté à \(n\) sommets et \(m\) arêtes.
Sortie : la liste des degrés de chaque sommets.

def degre(g) :
    deg = [ len(g[s]) for s in range(len(g)) ]
    for s in range(len(g)) :
        for v in g[s] :
            deg[v] += 1
    return deg

Complexité : \(\O(n+m)\)

Entrées : la liste d’adjacence d’un graphe à \(n\) sommets et \(m\) arêtes, source un sommet de g.
Sortie : ?? dépend du problème
Complexité : \(\O(n+m)\)

from collections import deque

# Utilisation d'une file : fifo pour avoir la bonne complexité.

def parcours_largeur(g, source) :
    n = len(g)
    marquage = [False] * n
    fifo = deque()
    fifo.append(source)
    marquage[source] = True
    # Traiter source ...
    while len(fifo) > 0 :
        s = fifo.popleft()
        for v in g[s] :
            if not marquage[v] :
                fifo.append(v)
                marquage[v] = True
                # Traiter v ...
    return # Quelque chose peut-être

Entrées : la liste d’adjacence d’un graphe à \(n\) sommets et \(m\) arêtes, source un sommet de g.
Sortie : ?? dépend du problème
Complexité : \(\O(n+m)\)

# Utilisation d'une pile : lifo pour avoir la bonne complexité.
def parcours_profondeur(g, source) :
    n = len(g)
    marquage = [False] * n
    lifo = []
    lifo.append(source)
    while len(lifo) > 0 :
        s = lifo.pop()
        if not marquage[s] :
            marquage[s] = True
            # Traiter s ...
            for v in g[s] :
                if not marquage[v] :
                    lifo.append(v)
    return # Quelque chose peut-être

La version récursive est meilleure.

def visiter(g, s, marquage) :
    marquage[s] = True
    # Traitement de source
    for v in g[s] :
        if marquage[v] != True :
            visiter(g, v, marquage)
            # ou ; r = visiter(g, v, marquage)
    return # Quelque chose peut-être
 
def parcours_profondeur(g, source) :
    n = len(g)
    marquage = [False] * n
    visiter(g,source,marquage)
    # ou ; r = visiter(g, source, marquage)
    return # Quelque chose peut-être

Entrées : la liste d’adjacence d’un graphe pondéré orienté à \(n\) sommets et \(m\) arêtes, source un sommet du graphe.
Sortie : la liste des distances minimales de source à chaque autre sommet du graphe et des relations de parentés qui permettent d’attendre ces distances.

On suppose qu’on dispose d’une structure de donnée file de priorité qui supporte les opérations suivantes :

• creer() : renvoie une file de priorité vide.
• est_vide(file) : renvoie vrai si la file est vide.
• ajoute(file, x, prio) : ajoute l’élément x dans la file avec priorité prio s’il n’y est pas déjà. Si x est déjà dans la file on change seulement sa priorité.
• enleve_min(file) : enleve de la file et renvoie l’élément de priorité minimale.

def dijkstra(g,source) :
    n = len(g)
    # Structures
    distances = [float(inf)]*n
    parents = [None]*n
    file_prio = creer()
    # Initialisation
    distances[source] = 0
    ajoute(file_prio, source, 0)
    # Algorithme
    while not est_vide(file_prio) :
        # On récupère le sommet non visité à distance minimale
        s = enleve_min(file_prio)
        # On relache tous les voisins
        for voisin, poids in g[s] :
            distance_par_s = distances[s] + poids
            if distance_par_s < distances[voisins] :
                distances[voisins] = distance_par_s
                parents[voisin] = s
                ajoute(file_prio, voisin, distances[voisins])
    return distances, parents

On peut trouver une implémentation de la structure de file de priorité telle que les fonctions creer et est_vide soient en \(\O(1)\) et les fonctions enleve_min et ajoute soient en \(\O(\log(n))\). La complexité finale est alors en \(\O(n\log(n)+m)\).

Voici une autre implémentation utilisant un marquage par dictionnaire avec les outils du programme, et la fonction d.pop(key) qui permet d’enlever une clé d’un dictionnaire :

def creer() : # $\O(1)$
    return {}
 
def est_vide(file_prio) : # $\O(1)$
    return len(file_prio) == 0
 
def ajoute(file_prio, x, prio) : # $\O(1)$
    file_prio[x] = prio
 
def enleve_min(file_prio) : # $\O(\symtt{len(file_prio)})$
    min_key, min_prio = None, float('inf')
    for x, prio in file_prio.items() :
        if prio < min_prio :
            min_key, min_prio = x, prio
    file_prio.pop(min_key)
    return min_key

La complexité finale est alors en \(\O(n^2+m) = \O(n^{2})\) car \(m \leq n^{2}\).

Entrées :

• la liste d’adjacence d’un graphe pondéré orienté à \(n\) sommets et \(m\) arêtes,
• source un sommet du graphe,
• destination un sommet du graphe,
• heuristique une fonction qui prend en entrée g, source, destination et un sommet s de g et qui renvoie une valeur entière.
  

Sortie : une liste de distances de source à chaque autre sommet du graphe et des relations de parentés qui permettent d’attendre ces distances.
Si h ne surestime jamais la distance de s à destination, les distances sont les plus petites. Si h = 0, c’est l’algorithme de Dijkstra. Complexité : La même que Dijkstra si h est en \(\O(1)\). Mais en pratique on atteindra la destination plus rapidement.

def astar(g, heuristique, source, destination) :
    n = len(g)
    # Structures
    distances = [float(inf)]*n
    parents = [None]*n
    file_prio = creer()
    # Initialisation
    distances[source] = 0
    ajoute(file_prio, source, 0)
    # Algorithme
    while not est_vide(file_prio) :
        # On récupère le sommet non visité à distance minimale
        s = enleve_min(file_prio)
        # ***** Une différence est ici *****
        if s == destination :
            break
        # On relache tous les voisins
        for voisin, poids in g[s] :
            distance_par_s = distances[s] + poids
            if distance_par_s < distances[voisins] :
                distances[voisins] = distance_par_s
                parents[voisin] = s
                ajoute(file_prio, voisin,
                       # ***** Une autre différence est ici *****
                       distances[voisins]+h(g,source,destination,voisin))
    return distances, parents

Entrées : Une liste L d’entiers positifs de longueur n.
Sortie : La différence de charge minimale entre deux listes L1 et L2 se repartissant les éléments de L.
Complexité recherche exhaustive : \(\O(n\,2^{n})\).
Complexité programme dynamique : \(\O(n*\symtt{sum(L)})\).

Sous-problèmes : \(\symtt{ordo(L,i,\Delta)}\) correspond à la différence de charge minimale sachant que les éléments L[i:] sont déjà repartis avec une différence de \Delta. Pour \(0 \leq i \leq \symtt{len(L)}\) et \(0 \leq \Delta \leq \symtt{sum(L)}\).

Formule : \[ \symtt{ordo(L,i,}\Delta) = \begin{cases} \Delta & \text{si } i = 0 \\ \min(\symtt{ordo(L,i-1,}\Delta+\symtt{L[i-1]}), \symtt{ordo(L,i-1,}|\Delta-\symtt{L[i-1]}|) & \text{sinon} \end{cases} \] Le problème \(\symtt{ordo(L)}\) correspond au sous-problème \(\symtt{ordo(L,0,0)}\).

def ordo_memo(L,i,delta,memo) :
    if i == 0 :
        memo[(i,delta)] = delta
        return
    delta_1 = delta + L[i-1]
    delta_2 = abs(delta - L[i-1])
    if (i-1, delta_1) not in memo :
        ordo_memo(L,i-1,delta_1,memo)
    if (i-1, delta_2) not in memo :
        ordo_memo(L,i-1,delta_2,memo)
    memo[(i,delta)] = min(memo[(i-1,delta_1)], memo[(i-1,delta_2)])
    return
 
def ordo(L) :
    memo = {}
    ordo_memo(L,len(L),0,memo)
    return memo[(len(L),0)]

Entrées : Un graphe pondéré orienté g à n sommets et m arrêtes, représenté par sa matrice d’adjacence.
Sortie : La matrice des distances minimales entre chaque paire de sommets.
Complexité recherche exhaustive : \(\O(n\,n!)\).
Complexité programme dynamique : \(\O(n^{3})\).
Complexité Dijkstra entre chaque paire (s,d) : \(\O(n^{3}\log(n))\).

Sous-problèmes : \(\symtt{fw(g,k) = M^{k}}\) correspond aux distances minimales entre chaque paire de sommets. Sachant que les seuls sommets intermédiaires utilisés sont les sommets \(0 \leq s < k\). Formule : \[ M^{k+1}_{i,j} = \min(M^{k}_{i,j}, M^{k}_{i,k} + M^{k}_{k,j}) \] Le problème \(\symtt{fw(G)}\) correspond au sous-problème \(\symtt{fg(G,n)}\).

On peut utiliser une approche montante ici.

def fw(g) :
    n = len(g) :
    m_new = [ [ x for x in line ] for line in g ]
    for k in range(1,n+1) :
        m_prev = m_new
        m_new = [ [ float("inf") for x in line ] for line in g ]
        for i in range(n) :
            for j in range(n) :
                m_new[i][j] = min(m_prev[i][j], m_prev[i][k] + m_prev[k][j])
    return m_new

Entrées : Deux chaînes de caractère, s1 et s2 de longueur \(n_1\) et \(n_2\).
Sortie : Le nombre minimal d’insertion, suppression, substitution qu’il faut appliquer à s1 pour obtenir s2. Appelé distance d’édition.
Complexité recherche exhaustive : \(\O(3^{n_{1} + n_{2}})\).
Complexité programme dynamique : \(\O(n^{2})\).

Sous-problèmes : \(\symtt{lev(s1,s2,i,j)}\) correspond à la distance d’édition entre s[:i] et s[:j]. Pour \(0 \leq i \leq n_{1}\) et \(0 \leq j \leq n_{2}\).
Formule : \[ \symtt{lev(s1,s2,i,j)} = \begin{cases} j & \text{si } i = 0 \\ i & \text{sinon si } j = 0 \\ 1 + \min(symtt{lev(s1,s2,i-1,j)}, symtt{lev(s1,s2,i,j-1)}, symtt{lev(s1,s2,i-1,j-1)}) & \text{sinon si } \symtt{s1[i-1] != s2[j-1]} \\ 1 + symtt{lev(s1,s2,i-1,j-1)} & \text{sinon } \\ \end{cases} \]

Le problème \(\symtt{lev(s1,s2)}\) correspond au sous-problème \(\symtt{lev(s1,s2,}n_{1},n_{2})\).

def lev_memo(s1,s2,i,j,memo) :
    if i == 0 :
        memo[(i,j)] = j
        return
    elif j == 0 :
        memo[(i,j)] = i
        return
    elif s1[i-1] == s2[j-1] :
        if (i-1,j) not in memo :
            lev_memo(s1,s2,i-1,j,memo)
        if (i,j-1) not in memo :
            lev_memo(s1,s2,i,j-1,memo)
        if (i-1,j-1) not in memo :
            lev_memo(s1,s2,i-1,j-1,memo)
        memo[(i,j)] = 1 + min(memo[(i-1,j)], memo[(i,j-1)], memo[(i-1,j-1)])
        return
    else :
        if (i-1,j-1) not in memo :
            lev_memo(s1,s2,i-1,j-1,memo)
        memo[(i,j)] = 1 + memo[(i-1,j-1)]
        return
     
def lev(s1,s2) :
    memo = {}
    lev_memo(s1,s2,len(s1),len(s2),memo)
    return memo[(len(s1), len(s2))]

Entrées : Un graphe pondéré orienté g = (S,A) à n sommets et m arrêtes.
Sortie : Le chemin le plus court permettant de passer par chaque sommet exactement une fois.
Complexité recherche exhaustive : \(\O(n!)\).
Complexité programme dynamique : \(\O(2^{n}\,n^{2})\).

Sous-problèmes : \(\symtt{hk(g,E,i,j)}\) correspond au poids du chemin le plus cours reliant i et j en passant exactement une fois par tous les sommets de E, ensemble de sommets de g tel que i et j ne sont pas dans E.
Formule : En notant \(d(u,v)\) le poids de l’arête \((u,v)\) (éventuellement \(+\infty\)). \[ \symtt{hk(g,E,i,j)} = \begin{cases} d(i,j) & \text{si } E = \emptyset \\ \min_{v \in E}(d(v,u) + \symtt{hk(g,E \setminus \{v\},v,j)}) & \text{sinon} \\ \end{cases} \]

Le problème \(\symtt{hk(g,i,j)}\) correspond au sous-problème \(\symtt{hk(g,S \setminus \{i,j\}, i,j)}\), avec S l’ensemble des sommets de g.

S doit être représenté par son indicatrice sous la forme de tuple pour pouvoir être mémoïsé. On représente ici g par sa matrice d’adjacence.

def hk_memo(g,E,i,j,memo) :
    vide = True
    for s_in_E in E :
        if s_in_E :
            vide = False
    if vide :
        memo[(E,i,j)] = g[i][j]
        return
    m = float("inf")
    for s in range(len(E)) :
        if E[s] :
            E_sans_s = E[:i] + (False,) + E[i+1:]
            if (E_sans_s,s,j) not in memo :
                hk_memo(g,E_sans_s,s,j,memo)
            val = g[i][s] + memo[(E_sans_s,s,j)]
            if val < m :
                m = val
    memo[(E,i,j)] = m
    return
 
def hk(g,i,j) :
    memo = {}
    S = (True,) * len(g)
    S = S[:i] + (False,) + S[i+1:]
    S = S[:j] + (False,) + S[j+1:]
    # ou S = tuple( [ x != i and x != j for x in range(len(g)) ] )
    hk_memo(g,S_sans_ij,i,j,memo)
    return memo[(len(s1), len(s2))]

Entrées : Un ensemble de \(n\) données d’entraînements étiquetées, une distance entre les données, un entier \(k\), une donnée \(x\).
Sortie : L’étiquette majoritaire parmis les \(k\) plus proches voisins de \(x\).

L’ensemble des données d’entraînement est ici un dictionnaire dont la clé est la donnée et la valeur est l’étiquette.

def kvoisins(e,d,k,x) :
    pp = kplusproches(e,d,k,x)
    return majo(pp,e,d,k)

Il y a plusieurs algorithmes pour kplusproches. Parmis elles :

• l’algorithme ci-après en \(\O(kn)\) si on suppose la complexité de \(d\) en \(\O(1)\).
• trier la liste et récupérer les k premiers en \(\O(n\log(n))\)
• Beaucoup plus compliqué : un variante du quickselect, linéaire en moyenne mais quadratique au pire cas. Qui peut devenir linéaire en le combinant avec une méthode de médiane des médianes.

def kplusproches(e,d,k,x) :
    L = []
    for data in e.keys() :
        if len(L) < k :
            L.append(data)
        elif d(data,x) < d(data,L[k-1]) :
            L.pop()
            L.append(data)
        j = k-1
        while j > 0 and L[j] < L[j-1] :
            L[j], L[j-1] = L[j-1], L[j]
            j += 1
    return L

Pour la fonction majo, cela dépend de l’heuristique utiliser pour décider de l’étiquette majoritaire. Dans ça version la plus simple :

def majo(pp,e,d,k) :
    etiquettes = {}
    for data in pp :
        if e[data] not in etiquettes :
            e[data] = 1
        else :
            e[data] += 1
    e_max = None
    m = -1
    for et in etiquettes :
        if etiquettes[et] > m :
            e_max = et
            m = etiquettes[et]
    return e_max

Entrées : Un ensemble de \(n\) données d’entraînements, une distance entre les données, un entier \(k\), une fonction moyenne qui calcule la moyenne d’un ensemble de données.
Sortie : \(k\) catégories.

L’ensemble des données d’entraînement est ici une liste de données.

from random import sample
def kmoyenne(e,d,k,moyenne) :
    centroides = sample(e,k)
    old_centroides = None
    while old_centroides != centroides :
        categories = [ [] for i in range(k) ]
        for data in e :
            centroide_plus_proche = 0
            min_distance = d(data, centroides[0])
            for i in range(1,k) :
                distance = d(centroide[i], data)
                if distance < min_distance :
                    centroide_plus_proche = i
                    min_distance = distance
            categories[centroide_plus_proche].append(data)
            old_centroides = centroides
            centroides = [ moyenne(cat[i]) for i in range(k) ]
    return categories

Si les données sont des vecteurs, la distance et la moyennes peuvent être implémentées par :

def distance(x,y) :
    d = 0
    for i in range(len(x)) :
        d += (x[i]-y[i])**2
    return d ** 0.5
 
def moyenne(e) :
    m = [0.0] * len(e[0])
    for x in e :
        for i in range(len(x)) :
            m[i] += x[i]
    return [ x / len(m) for x in m ]

Entrées : Le graphe d’un jeux sous forme de liste d’adjacence (\(n\) sommets et \(m\) arêtes), les conditions de victoires d’un joueur sous la forme d’une liste de sommets du graphe, le joueur en question.
Sortie : L’ensemble des attracteurs (sommets gagnants) du joueur en question.
Complexité : \(\O(n + m)\)

Dans le graphe d’un jeux chaque sommet est contrôlé par un joueur. Il y a plusieurs manière de représenté cela. On supposera que chaque sommet est de la forme (j,s) avec j le numéro, 0 ou 1, du joueur contrôlant le sommet.

def transpose(g) :
    tg = [ [] for s in g ]
    for s in g :
        for v in g[s] :
            tg[v].append(s)
    return tg
 
def attracteurs(g,v,joueur) :
    tg = transpose(g)
    marquage = [ len(tg[s]) for s in tg ]
    a = [ False for i in range(len(tg)) ]
    for s in v :
        parcours(tg,s,a,marquage, joueur)
    return a
 
def parcours_dfs(g,s,a,marquage, joueur) :
    if a[s] :
        return
    a[s] = True
    for v in g[s] :
        if not a[v] :
            marquage[v] -= 1
            j,_ = v
            if j = joueur or marquave[v] == 0:
                parcours_dfs(v)

Entrées : Un arbre de jeux à profondeur fixé, donné par sa liste d’adjacence, r la racine de l’arbre, une heuristique \(h\) permettant d’estimer le score des feuilles, le joueur (0 pour max, 1 pour min) qui joue à la racine.
Sortie : Le score du joueur à la racine de l’arbre, et le coup qui permet de l’attendre.

def minmax(a, r, h, j) :
    if len(a[r]) == 0 :
        return h(r), None
    L = []
    for v in a[r] :
        L.append((minmax(a,v,h,1-j), v))
    if i == 0 :
        return max(L)
    return min(L)