Algorithmes Classiques

1. Numériques
2. Séquences
3. Boucles imbriquées
4. Algorithmes Dichotomiques
- 4.1. Recherche dichotomique dans une liste triée
5. Algorithmes récursifs

1. Numériques

1.1. Algorithme d’Euclide

Entrées : Deux entiers \(a\) et \(b\)
Sortie : \(\mathtt{pgcd}(a,b)\)

def euclide(a, b) :
    while a != b :
        if a > b :
            a = a - b
        else :
            b = b - a
    return a

1.2. Test de Primalité

Entrées : un entier \(n \geq 2\)
Sortie : True ssi \(n\) est premier

def premier(n) :
    p = True
    d = 2
    # Recherche d'un diviseur entre 2 et la racine carré de n
    while d * d <= n :
        if n % d == 0 :
            p = False
        d = d + 1
    return p

1.3. Suite de Fibonacci

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
    f_suivant = 1
    rang = 0
    # Calcul du rang n en calculant chaque rang i successivement
    while rang != n :
        f_suivant2 = f + f_suivant
        f = f_suivant
        f_suivant = f_suivant2
        rang = rang + 1
    return f

1.4. Suite de Syracuse

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 :
        if s % 2 == 0 :
            s = s // 2
        else :
            s = 3 * s + 1
        rang = rang + 1
    return rang

2. Séquences

2.1. Somme des éléments d’une liste

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

2.2. Maximum

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(1,len(l)) :
        if l[i] > maxi :
            maxi = l[i]
            i_max = i
    return i_max

2.3. Recherche linéaire - version while

Entrées : Liste l et un objet 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) :
    n = len(l)
    i_x = -1
    i = 0
    while i < n and i_x == -1 :
        if l[i] == x :
            i_x = i
        i = i + 1
    return i_x

2.4. Recherche linéaire - version for

Entrées : Liste l et un objet 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

2.5. Comptage

Entrées : Liste l et un objet x
Sortie : Le nombre de fois que x apparaît dans l

def compter(l, x) :
    c = 0
    for e in l :
        if e == x :
            c = c + 1
    return c

2.6. Second Minimum

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 i in range(2,len(l)) :
        x = l[i]
        if x < m :
            second_m = m
            m = x
        elif x < second_m :
            second_m = x
    return second_m

3. Boucles imbriquées

3.1. Algorithme de la Fenêtre Glissante

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

3.2. Création d’une matrice \(n \times m\)

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

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

3.3. Copie d’une matrice

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

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

3.4. Histogramme d’une image

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

4. Algorithmes Dichotomiques

4.1. Recherche dichotomique dans une liste triée

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

5. Algorithmes récursifs

5.1. Somme

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))

5.2. Maximum

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))

5.3. Exponentiation rapide

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)