Introduction à la complexité et sa formalisation

Étudiant : ALBRECHT Maël

Tuteur : HIRSCHOWITZ Tom

Introduction

Lorsque nous créons de grands programmes, l'optimisation de ceux-ci est importante pour diminuer le temps d'exécution et la longueur de ceux-ci. Pour cela, nous allons donc nous intéresser au principe de complexité.

Complexité

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

• 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