Introduction à la complexité et sa formalisation

Étudiant : ALBRECHT Maël

Tuteur : HIRSCHOWITZ Tom

Introduction

Pour introduire notre sujet nous allons partir d'un exemple, imaginez que vous vouliez trier des fichiers dans votre ordinateur (dans notre cas des fichiers numérotés et par exemple nous souhaitons les trier par ordre croissant). Pour effectuer cette tache vous pouvez donc créer un programme qui le ferra pour vous. Malheureusement, votre programme prend beaucoup de temps à s'exécuter. Pour résoudre ce problème on se tourne vers la complexité.

Complexité

La complexité permet de mesurer l'efficacité des fonctions. Elle dépend de différents critères tels que :

• le temps de calcul séquentiel , c'est à dire le temps qui est mis pour exécuter toutes les instructions une par une.

• le temps de calcul parallèle , c'est à dire le temps qui est mis pour exécuter toutes les instructions avec plusieurs processeurs donc avec des opérations exécutées en simultané.

• l'espace disque nécessaire à ces opérations qui peuvent donc rallonger le temps d'exécution d'une opération.

• ainsi que d'autres paramètres…

Pour illustrer cela nous allons utiliser deux fonctions « identité » comme exemple.

On commence donc par définir un type d'entier unaire.

1.   type nat = Z | S of nat
2.   let one = S Z
3.   let two = S (S Z) (* etc.. *)

On programme ensuite une fonction identité simple :

1.   let id1 n = n

Et une fonction identité qui inspecte son argument, puis le reconstruit :

1.   let rec id2 n = match n with
2.   | Z -> Z
3.   | S p -> S (id2 p)

Complexité en temps

On s'intéresse au nombre d'étape de calcul en fonction de la taille de l'argument.

On fait souvent des hypothèses simplificatrices pour calculer une complexité. Toutefois, celles-ci doivent rester vraies. Ici nous comptons le nombre de tests match ... with.

• Pour id1 : 0.
• Pour id2 : autant que la taille de l'argument.

Notation O

Nous allons ensuite introduire la notation O (dite « grand o »).

Pour cela, fixons des types A et B et une « manière de compter ».

On définit donc une fonction f: A -> B.

Cette fonction f nous permet de prendre la taille de a et de trouver le temps avec f(a) soit :

taille(a) -> temps(f(a))

Cela nous permet donc de trouver :

id1: n -> 1

id2: n -> n

Pour présenter cela nous utilisons la notation suivante :

• Complexité de id1 : O(1)
• Complexité de id2 : O(n)

Si l'on souhaite développer cette notation, nous pouvons prendre :

f ∈ O(g) qui signifie f(n) ≤ c * g(n)

Avec :

• c une constante bien choisie
• et pour tout n ≥ n_0

Langages utilisés

Pour créer nos différentes fonctions et comprendre leur complexité nous avons utiliser deux langages différents :

• Le langage OCaml, un langage fonctionnel et fortement typé.

• Le langage Agda, qui est un langage fonctionnel, typé et qui sert en partie à programmer des preuves mathématiques.
• On utilise aussi une extension d'Agda qui se nomme Calf et qui sert à calculer la complexité d'une fonction sous forme de coûts.

Tri en OCaml

Nous allons donc écrire différentes fonctions de tri dans le langage OCaml.

Tri par insertion en OCaml

Tout d'abord, le tri par insertion consiste :

• Prendre en argument une liste à trier.
• Prendre une liste vide.
• Prendre un élément de la liste non trié.
• Insérer cet élément au bon endroit dans la liste vide (il faut donc parcourir la liste).
• Puis on recommence le processus de sorte à trier cette liste et à renvoyer celle-ci.

Il faut donc avoir en tête que nous manipulons bien deux listes différentes pendant l'exécution.

Pour faire cela en OCaml nous avons besoin de la fonction d'insertion :

1.   let rec insert e l = match l with
2.   [] -> [e]
3.   | x :: l' -> if e <= x
4.     then e :: l
5.     else x :: (insert e l')

Cette fonction est une fonction récursive qui s'appelle donc elle-même. On peut donc voir que si la liste fournie est vide, alors elle renvoie l'élément e, sinon elle insert un élément au bon endroit.

Nous avons ensuite besoin de la fonction de tri :

1.   let rec trie l = match l with
2.   [] -> []
3.   | e::l' -> insert e (trie l')

Cette fonction est aussi une fonction récursive qui va appeler notre fonction d'insertion pour trier la liste fournie en argument.

Pour la complexité de cette fonction nous allons compter le maximum de tests que peut faire trie l. On trouve que pour chaque élément de la liste l' le coût augmente de 1.

On se retrouve donc avec une complexité totale qui correspond à la somme des éléments de 1 à n-1 soit (n(n-1))/2 ce qui représente une complexité O(n²).

Tri par fusion en OCaml

Nous nous intéressons donc maintenant à une fonction de tri par fusion. Le principe de cette fonction est le suivant :

• On part d'une liste à trier.
• On effectue une suite de divisions récursives en deux parties jusqu'à obtenir des listes de taille 1.
• On trie ensuite chaque liste.
• Puis on les fusionne entre elles tout en les triant.

Sur le schéma ci-dessus on peut donc voir une mise en pratique du tri par fusion. On voit la découpe de la liste pour obtenir des listes de tailles 1, puis le tri et la fusions des différentes listes de sorte a créer une liste trié.

Pour faire cela en OCaml, on doit tout d'abord écrire la fonction coupe qui est créer grâce a la fonction coupe_rec :

1.   let rec coupe_rec n jusquici l =
2.   if  n = 0 then List.rev jusquici , l
3.   else coupe_rec (n-1) (List.hd l :: jusquici) (List.tl l)

1.   let coupe l = coupe_rec (List.length 1 /2) [] l