La programmation est une suite d’opérations logiques devant mener à un résultat. Peu importe la forme de ce dernier, le cheminement doit être précis et repose sur une décomposition d’un problème en sous-problèmes selon des méthodes bien précises. L’on nomme ces suites d’opérations des algorithmes.
Il semblerait que les premières décomposition d’un problème complexe en une suite de problèmes simplifiés date de l’époque d’un certain Al-Khwarizmi, le premier a avoir appliqué une telle méthodologie. Son nom a évolué pour donner algorithme. C’était un mathématicien persan vivant au Ixeme siècle. Mais son idée est plus ancienne puisque l’on sait que Euclide, vers 300 avant J.C., utilisait une méthode permettant de trouver le PGCD de deux nombres.
Quoi qu’il en soit, le résultat est que tout problème doit avoir sa ou ses solutions, que l’on peut trouver en appliquant une série d’algorithmes de résolution de sous-problèmes. Et comme l’on dit souvent : « s’il n’y a pas de solution, alors il n’y a pas de problème… ». Dans cette série d’articles, l’idée directrice va être de faire découvrir ou redécouvrir les algorithmes principaux avec une réalisation pratique afin de bien comprendre les mécanismes mis en jeu et la façon dont on peut les utiliser.
Il y a 10 sortes de gens dans le monde : ceux qui connaissent le binaire et les autres.
La complexité des algorithmes permet de déterminer la performance d'un algorithme. Cela n'a pas de lien avec la difficulté que nous allons rencontrer dans sa mise en place mais c'est plutôt l'aspect mathématique qui sera évalué avec des logarithmes et autres éléments de ce type. Nous nous concentrerons plus précisément sur le temps d'exécution qui résultera de la qualité de l'algorithme.
La complexité d'un algorithme est variable selon les traitements et les types de données. C'est toutefois une approximation que nous allons être amenés à mettre en place. Cela va dépendre du pire des cas dans les accès et les comparaisons que nous devrons faire pour tester les données.
Nous allons prendre en considération les éléments suivants : Une opération élémentaire ou une affectation d'une valeur à une variable vaudra 1. Le parcours d'un tableau vaudra la longueur de ce tableau (tableau de 100 cases = 100)
Dans le pseudo code ci-dessous, nous allons expliciter un calcul de complexité :
Fonction somme(n)
DEBUT
i <- 0 (Complexité = 1)
Pour i de 0 à n Faire (Complexité 1 pour la comparaison + 1 pour l'affectation)
res <- res + 1 (Complexité 1 pour addition et 1 pour l'affectation)
Fin Pour (Complexité 1 pour le saut en début de boucle)
(Complexité totale de la boucle : 1 + 1 + 1 + 1 + 1 = 5, répété n fois = 5n)
Retourner res (Complexité de l'affectation : 1)
FINRécapitulatif des complexités (du moins au plus complexe) :
Trier des éléments est une des opérations les plus usitées en informatique. Mais tous les algorithmes ne sont pas forcément adaptés au tri des valeurs données. Les critères sont à prendre en compte : nombre de données, données initialement ordonées ou quasi ordonnées, ... L'opération de base pour les tris est la comparaison (notamment sur les clés de tri) et la seule action est l'échange entre cellules d'un tableau par exemple.
A[i] <-> A[J] = | k <- A[i]
| A[i] <- A[j]
| A[j] <- k
On parle d'un algorithme stable s'il préserve l'ordre de départ des éléments avec la même clé. Un algorithe est en place s'il utilise un nombre constant de variables auxiliaires et qu'il ne réalise pas de copie de l'ensemble de données avant et après.
Dans cet algorithme nous allons rechercher le minimum du tableau ou de la liste et le placer en première place. On recommence à la case suivant celle qui a reçu ce minimum. Après le keme déplacement, les k plus petits éléments sont à leur place définitive. Le tableau est ainsi trié au fur et à mesure de la boucle.
Input : 101 115 30 63 47 20
Sélection : 20
Placement : 20 115 30 63 47 101
Sélection : 30
Placement : 20 30 115 63 47 101
Sélection : 47
Placement : 20 30 47 63 115 101
Sélection : 63
Placement : 20 30 47 63 115 101
Sélection : 101
Placement : 20 30 47 63 101 115
Output : 20 30 47 63 101 115
Juste avec l'exemple nous pouvons nous apercevoir qu'il va falloir faire n parcours n fois donc une complexité des comparaisons en O(n2) ce qui rend l'algorithme peu efficace à partir de seulement quelques éléments. En fait il est exactement en O((n2-n)/2) car à chaque position i de la boucle nous effectuons n - i comparaisons. La complexité des échanges est en O(n) ce qui le rend intéressant lorsque des données volumineuses sont à trier.
Procedure Tri-Selection(var A:array[1..n] of integer);
var i,j,k:integer;
begin
i := 1
while i < n do
begin
j := i
for k := i + 1 to n do
if A[k] < A[j] then j := k
A[j] <-> A[i]
i := i + 1
end
end
#include <stdio.h>
int tab[10] = {1, 6, 9, 0, 4, 5, 3, 8, 3, 7};
int main(int argc, char **argv)
{
int i, j, min;
int tmp;
int tablen = sizeof(tab)/sizeof(int);
printf("nombre d'éléments : %d\n", tablen);
printf("\n tableau avant tri : ");
for (i = 0; i < tablen; i++)
{
printf("%d, ", tab[i]);
}
printf("\n");
// Boucle de tri
for (i = 0; i < tablen; i++)
{
min = i; // Case où se trouve la valeur minimale recherchée
for (j = i+1; j < tablen; j++)
{
if (tab[j] < tab[min]) min = j; // Nouvelle case contenant une valeur minimale
}
// Inversion des cases
tmp = tab[i];
tab[i] = tab[min];
tab[min] = tmp;
}
printf("\n tableau après tri : ");
for (i = 0; i < tablen; i++)
{
printf("%d, ", tab[i]);
}
printf("\n");
}
Le Tri à bulle est un des tris les plus simples mais sa complexité algorithmique en O(n2) ne le rend pas efficace dans la majorité des cas. Son principe est de comparer des valeurs deux à deux et à déplacer les éléments selon leur ordonnancement respectif. Nous allons donc être obligé de parcourir n fois le tableau en entier ce qui explique la lenteur de cet algorithme.
La récursivité est une technique permettant à une fonction de s'appeler elle-même. Pour cela il faut que cette fonction dispose d'une valeur d'arrêt (pour éviter de partir en boucle infinie). Par exemple, avec une fonction permettant d'afficher les nombres pairs en partant de celui donné comme paramètre :
def even(n):
print(n)
if n == 0:
return n
else:
return even(n-2)
even(10)10
8
6
4
2
0Mais quel est l'intérêt d'utiliser ce type de fonction quand nous pouvons obtenir le même résultat en passant par une fonction itérative ?
def even_iter(n):
while n >= 0:
if n % 2 == 0:
print(n)
n -= 2
even_iter(10)Parmi les fonctions récursives généralement rencontrées nous pouvons citer :
La fonction Factorielle correspond à la multiplication de la série de nombres menant de 1 à n, n étant la valeur du nombre pour lequel nous cherchons cette factorielle. La notation n! en est sa notation.
Exemples de factorielles :
def factorielle(n):
if n == 1:
return 1
else:
return n * factorielle(n-1)
print(f"Factorielle de 10 = {factorielle(10)}")Factorielle de 10 = 3628800Cette fonction a pour particularité d'être une suite composée de la somme des deux précédentes valeurs de cette liste, dont les deux premiers termes sont (0, 1). Ainsi nous avons la liste composée de 0 + 1 = 1, 1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 5 + 3 = 8...