@Mathieu Nivoliez

Algorithmique avec RUST

2017-04-25 / 2 minutes.

Bonjour, aujourd'hui on va discuter algorithmique!

"Algorithmique? Kezako?"

Très bonne question! Définissons d'abord un algorithme. Selon Wikipédia:

Un algorithme est une suite finie et non ambiguë d’opérations ou d'instructions permettant de résoudre un problème ou d'obtenir un résultat.

Pour donner un exemple concret, quand nous cuisinons nous suivons une recette avec différentes "étapes" ou "opérations" (mettre la farine, rajouter de l'eau, battre les blanc en neige, etc...) permettant de réaliser un plat (obtenir le résultat).

Et donc toujours selon Wikipédia:

L'algorithmique est l'étude et la production de règles et techniques qui sont impliquées dans la définition et la conception d'algorithmes, c'est-à-dire de processus systématiques de résolution d'un problème permettant de décrire précisément des étapes pour résoudre un problème algorithmique.

Ou plus, simplement, il s'agit de concevoir et d'étudier des algorithmes. Cela signifie également à réfléchir à l'efficacité de l'algorithme, et par conséquent, à son coût.

"Faut payer en plus?"

Oui, chaque algorithme se paie. Pas d'inquiétude, on ne va pas vous prendre de l'argent mais des ressources liées à l'exécution de l'algorithme.

Pour continuer sur mon exemple de la cuisine, pour chaque opération (mettre la levure, remuer, etc...) nous mobilisons nos mains, un saladier, notre temps etc....

L'idée est de pouvoir quantifier cette "complexité".

Selon Wikipédia (oui, encore):

La théorie de la complexité est un domaine des mathématiques, et plus précisément de l'informatique théorique, qui étudie formellement la quantité de ressources (temps et/ou espace mémoire) nécessaire pour résoudre un problème algorithmique au moyen de l'exécution d'un algorithme. Il s'agit donc d'étudier la difficulté intrinsèque de problèmes, pour ensuite les organiser par classes de complexité.

"Ok, comment on compte cette complexité?"

Alors, d'abord il existe une notation spécifique: O(f(n)) qui se lit "grand O de f(n)" où f est une fonction mathématique de n.

Considérons maintenant l'algorithme suivant:

Entrée: tableau t de taille n
Pour i de 1 à n faire
  ecrire t[i] // on à une action ici
Fin pour

On a un tableau avec n éléments en entré. Pour chaque élément, nous réalisons une action. A la fin de cette algorithme on aura donc fait n actions. La complexité est O(n).

Si on avait fait deux actions, le nombre d'actions serait de 2n. Toutefois, les constantes ne sont pas importante car relatives au facteur n.

En revanche,

Entrée: tableau t de taille n
Pour i de 1 à n faire
  Pour j de 1 à n faire
    ecrire t[i] // on à une action ici
  Fin pour
Fin pour

Dans cette algorithme on fait de boucle imbriqué on a donc n action répété n fois d'où la complexité est de O(n2).

"Ok, et le Rust dans tout ça?"

Ben on va juste écrire les algorithmes en Rust.

Bon je me rends compte que cet article commence à être long donc je vous donne rendez-vous dans le prochain article pour l'étude du tri à bulle.

-- Mathieu