Les algorithmes sont des approches logiques qui proposent un certain nombre de traitements permettant de répondre à un besoin
dans le cadre d’un développement applicatif. Un algorithme est dit « correct » lorsqu’il produit la bonne sortie (le résultat souhaité)
Il est dit « performant » lorsqu’il propose le moins de traitements possibles pour un résultat équivalent. Leurs complexités pour certains
d’entre eux font qu’ils ne sont utilisés que de façon admises pour nous simples mortels. Nous allons voir ici ceux qui ont révolutionné la
programmation.

 

Codage de Huffman (Compression)

 

2-huffman

 

Le principe du codage de Huffman repose sur la création d’un arbre composé de nœuds. Supposons que la phrase à coder est « wikipédia ». On recherche tout d’abord le nombre d’occurrences de chaque caractère (ici les caractères ‘a’, ‘d’, ‘é’, ‘k’, ‘p’ et ‘w’ sont représentés chacun une fois et le caractère ‘i’ trois fois). Chaque caractère constitue une des feuilles de l’arbre à laquelle on associe un poids valant son nombre d’occurrences. Puis l’arbre est créé suivant un principe simple : on associe à chaque fois les deux nœuds de plus faibles poids pour donner un nœud dont le poids équivaut à la somme des poids de ses fils jusqu’à n’en avoir plus qu’un, la racine. On associe ensuite par exemple le code 0 à la branche de gauche et le code 1 à la branche de droite.

Pour obtenir le code binaire de chaque caractère, on remonte l’arbre à partir de la racine jusqu’aux feuilles en rajoutant à chaque fois au code un 0 ou un 1 selon la branche suivie. Il est en effet nécessaire de partir de la racine pour obtenir les codes binaires car lors de la décompression, partir des feuilles entraînerait une confusion lors du décodage. Ici, pour coder ‘Wikipédia’, nous obtenons donc en binaire : 101 11 011 11 100 010 001 11 000, soit 24 bits au lieu de 63 (9 caractères x 7 bits par caractère) en utilisant les codes ASCII (7 bits).

 

Cryptographie asymétrique

 

La cryptographie asymétrique, ou cryptographie à clé publique est fondée sur l’existence des fonctions à sens unique et à brèche secrète.
Les fonctions à sens unique sont des fonctions mathématiques telles qu’une fois appliquées à un message, il est extrêmement difficile de retrouver le message original (ex md5, sha1, …) .
L’existence d’une brèche secrète permet cependant à la personne qui a conçu la fonction à sens unique de décoder facilement le message grâce à un élément d’information qu’elle possède, appelé clé privée.

clefpgp[1]

 

Algorithme de Dijkstra

 

L’algorithme de Dijkstra (prononcer [dɛj.kstra]) sert à résoudre le problème du plus court chemin. Il s’applique à un graphe connexe dont le poids lié aux arêtes est un réel positif.
Il s’agit de construire progressivement, à partir des données initiales, un sous-graphe dans lequel sont classés les différents sommets par ordre croissant de leur distance minimale au sommet de départ. La distance correspond à la somme des poids des arêtes empruntées.

Dijkstra_Animation

Pseudo code

Fonction Dijkstra (nœuds, fils, distance, début, fin)
     Pour n parcourant nœuds
         n.parcouru = infini   // Peut être implémenté avec -1 (*)
         n.précédent = 0
     Fin pour
     début.parcouru = 0
     pasEncoreVu = nœuds
     Tant que pasEncoreVu != liste vide
         n1 = minimum(pasEncoreVu)   // Le nœud dans pasEncoreVu avec parcouru le plus petit
         pasEncoreVu.enlever(n1)
         Pour n2 parcourant fils(n1)   // Les nœuds reliés à n1 par un arc
             Si n2.parcouru > n1.parcouru + distance(n1, n2)   // distance correspond au poids de l'arc reliant n1 et n2
                 n2.parcouru = n1.parcouru + distance(n1, n2)
                 n2.précédent = n1   // Dit que pour aller à n2, il faut passer par n1
             Fin si
         Fin pour
     Fin tant que
     chemin = liste vide
     n = fin
     Tant que n != début
         chemin.ajouterAvant(n)
         n = n.précédent
     Fin tant que
     chemin.ajouterAvant(début)
     Retourner chemin
 Fin fonction Dijkstra

 

Dichotomie

 

La dichotomie est un processus itératif ou récursif de recherche où, à chaque étape, on coupe en deux parties (pas forcément égales) un espace de recherche qui devient restreint à l’une de ces deux parties.

3-Binary

 

Tri rapide (qsort)

 

La méthode consiste à placer un élément du tableau (appelé pivot) à sa place définitive, en permutant tous les éléments de telle sorte que tous ceux qui sont inférieurs au pivot soient à sa gauche et que tous ceux qui sont supérieurs au pivot soient à sa droite. Cette opération s’appelle le partitionnement. Pour chacun des sous-tableaux, on définit un nouveau pivot et on répète l’opération de partitionnement. Ce processus est répété récursivement, jusqu’à ce que l’ensemble des éléments soit trié.

Quicksort

Pseudo code

partitionner(tableau T, premier, dernier, pivot)
    échanger T[pivot] et T[dernier]
    j := premier
    pour i de premier à dernier - 1
        si T[i] <= T[dernier] alors
            échanger T[i] et T[j]
            j := j + 1
    échanger T[dernier] et T[j]
    renvoyer j

 tri_rapide(tableau t, entier premier, entier dernier)
   début
     si premier < dernier alors
       pivot := choix_pivot(t, premier, dernier)
       pivot := partitionner(t, premier, dernier, pivot)
       tri_rapide(t ,premier, pivot-1)
       tri_rapide(t, pivot+1, dernier)
     fin si
   fin

 

Algorithme de Karatsuba

 

L’algorithme de Karatsuba (1960) est une méthode permettant de multiplier rapidement deux nombres de n chiffres avec une complexité en O(n^log2(3)) au lieu de O(n^2) pour la méthode naïve (log2(3) = 1.58). Karatsuba remarque que le calcul de (a × 10^k + b)(c × 10^k + d) qui, sous forme développée ac × 10^2k + (ad + bc) × 10^k + bd, semble nécessiter les quatre produits ac, ad, bc et bd, peut en fait être effectué seulement avec les trois produits ac, bd et (a – b)(c – d)

Pour les machines dont les calculs se font en binaire les additions sont beaucoup moins couteuses que les multiplications. Ainsi le calcul 12378456 × 25874215 ne demande que 27 produits au lieu de 64 par la méthode de Karatsuba

Karatsuba-algorithm

 

Algorithme d’Euclide

 

L’algorithme d’Euclide est un algorithme permettant de déterminer le plus grand commun diviseur (P.G.C.D.) de deux entiers dont on ne connaît pas la factorisation.

Dans la tradition grecque, en comprenant un nombre entier comme une longueur, un couple d’entiers comme un rectangle, leur PGCD est la longueur du côté du plus grand carré permettant de carreler entièrement ce rectangle. L’algorithme décompose ce rectangle en carrés, de plus en plus petits, par divisions euclidiennes successives, de la longueur par la largeur, puis de la largeur par le reste, jusqu’à un reste nul.

350px-Euclide2115.svg

 

Explication arithmétique

Soient deux entiers naturels a et b, dont on cherche le PGCD. On commence donc par calculer le reste de la division de a par b, qu’on note r. Puis on remplace a par b, puis b par r, et on réapplique le procédé depuis le début.
On obtient ainsi une suite, qui vaut 0 à un certain rang ; le PGCD cherché est le terme précédent de la suite.

Calculons, par exemple, le PGCD de 1071 et de 1029 à l’aide de l’algorithme d’Euclide :

1071 = 1029 × 1 + 42
1029 = 42 × 24 + 21
42 = 21 × 2 + 0

Il faut prendre le dernier reste avant le zéro, donc PGCD(1071 ; 1029) = 21La définition même de la suite A(n) par division euclidienne montre que, pour tout n tel que A(n+1) est non nul, il existe un entier Q(n+2) tel que : A(n)=Q(n+2)*A(n+1)+A(n+2) avec 0 <= A(n+2) < A(n+1). La suite d’entiers naturels (a_n) est donc strictement décroissante (tant qu’elle est non nulle)

 

Algorithme de PageRank Google

 

Inconnu à ce jour c’est très certainement l’algorithme qui a le plus révolutionné l’internet puisqu’il permettra d’établir un classement (pagerank) pertinent des milliards de pages web dans le monde. La manière dont Google calcule le poids des pages est à ce jour inconnu et son algorithme subit des évolutions perpétuelles.

 

 

Lire également