Introduction à la complexité et sa formalisation

Étudiant : ALBRECHT Maël

Tuteur : HIRSCHOWITZ Tom

Introduction

Pour introduire notre sujet nous allons partir d'un exemple, imaginer que vous vouliez trier des fichiers dans votre ordinateur ( dans notre cas des fichiers numéroter et par exemple nous souhaitons les triés 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 a 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 tel que :

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

• le temps de calcul parallèle , c'est a dire le temps qui es mis pour exécuter toute les instructions avec plusieurs processeur donc avec des opération exécuté en simultané.

• l'esapace disque nécessaire a ces opération qui peut donc ralonger le temps d'execution d'une opérations.

• ainsi que beaucoup d'autre paramètre...

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

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

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

Nombre d'étape de calcul en fonction de la taille de l'argument.

On fait souvent des hypothèses simplificatrices. Ici : comptons le nombre de tests match ... with.

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

Notation O

Fixons des types A et B et une « manière de compter ».

TODO a faire

>