Introduction à la complexité et sa formalisation - Historique des versions

Hirschowitz le 23 mai 2025 à 08:49

2025-05-23T08:49:03Z

← Version précédente		Version du 23 mai 2025 à 08:49
Ligne 210 :		Ligne 210 :
	On peut voir que les testes apparaissent dans la phase de <b>fusion</b>. On symbolise donc cette phase par un arbre dont la profondeur est : <b>log2(n)</b>.		On peut voir que les testes apparaissent dans la phase de <b>fusion</b>. On symbolise donc cette phase par un arbre dont la profondeur est : <b>log2(n)</b>.

	Dans notre cas on va s'intéresser a un arbre de longueur 2² ( n = 2^p).		Dans notre cas on va s'intéresser a un arbre de longueur 2ᵖ ( n = 2<sup>p</sup>).

	On va donc prendre plusieurs éléments pour montrer cette complexité.		On va donc prendre plusieurs éléments pour montrer cette complexité.

Hirschowitz le 23 mai 2025 à 08:48

2025-05-23T08:48:20Z

← Version précédente		Version du 23 mai 2025 à 08:48
Ligne 210 :		Ligne 210 :
	On peut voir que les testes apparaissent dans la phase de <b>fusion</b>. On symbolise donc cette phase par un arbre dont la profondeur est : <b>log2(n)</b>.		On peut voir que les testes apparaissent dans la phase de <b>fusion</b>. On symbolise donc cette phase par un arbre dont la profondeur est : <b>log2(n)</b>.

	Dans notre cas on va s'intéresser a un arbre de longueur 2^p ( n = 2^p).		Dans notre cas on va s'intéresser a un arbre de longueur 2² ( n = 2^p).

	On va donc prendre plusieurs éléments pour montrer cette complexité.		On va donc prendre plusieurs éléments pour montrer cette complexité.

Albrecht le 11 mai 2025 à 19:51

2025-05-11T19:51:06Z

Voir les modifications

Albrecht le 11 mai 2025 à 19:20

2025-05-11T19:20:55Z

@@ Ligne 201 : / Ligne 201 : @@
 (Cette fonction est une fonction récursive)
-* Si on rentre une liste vide, cela renvoie une liste vide,
+* Si on rentre une <b>liste vide</b>, cela renvoie une liste vide,
-* Si on rentre une liste à un seul élément, on renvoie la liste de cette élément,
+* Si on rentre une <b>liste à un seul élément</b>, on renvoie la liste de cette élément,
-* Sinon en appelle notre fonction coupe et notre fonction fusionne pour trier cette liste.
+* Sinon on appelle notre fonction coupe et notre fonction fusionne pour trier cette liste.
 == Complexité en Agda/Calf ==
 === Deux fonctions « identité » ===
 == Conclusion ==

Albrecht le 11 mai 2025 à 12:27

2025-05-11T12:27:04Z

← Version précédente		Version du 11 mai 2025 à 12:27
Ligne 174 :		Ligne 174 :

	La fonction coupe utilise donc la fonction coupe_rec. Elle va donc nous permettre de couper la liste en plusieurs listes d'un élément.		La fonction coupe utilise donc la fonction coupe_rec. Elle va donc nous permettre de couper la liste en plusieurs listes d'un élément.
			Il nous faut en suite écrire la fonction fusionne :

			<pre>
			1. let rec fusionne l1 l2 = match l1 with
			2. \| [] -> l2
			4. \| e::l1' -> match l2 with
			5. \| [] -> l1
			6. \| x::l2' -> if e <= x
			7. then e :: fusionne l2 l1'
			8. else x :: fusionne l1 l2'
			</pre>

			Cette fonction est une fonction récursive, elle compare un élément d'une liste et regarde où l'ajouter pour que cela crée une liste trier à partir de deux liste.

			Enfin nous créons la fonction trieFusion :

			<pre>
			1. let rec trieFusion l = match l with
			2. \| [] -> []
			3. \| [e] -> [l]
			4. \| _ -> let l1, l2 = coupe l in
			5. fusionne (triFusion l1) (trieFusion l2)
			</pre>

			La fonction trieFusion effectue donc les taches suivante :
			(Cette fonction est une fonction récursive)

			* Si on rentre une liste vide, cela renvoie une liste vide,
			* Si on rentre une liste à un seul élément, on renvoie la liste de cette élément,
			* Sinon en appelle notre fonction coupe et notre fonction fusionne pour trier cette liste.

	== Complexité en Agda/Calf ==		== Complexité en Agda/Calf ==

Albrecht le 11 mai 2025 à 12:09

2025-05-11T12:09:36Z

← Version précédente		Version du 11 mai 2025 à 12:09
Ligne 166 :		Ligne 166 :
	3. else coupe_rec (n-1) (List.hd l :: jusquici) (List.tl l)		3. else coupe_rec (n-1) (List.hd l :: jusquici) (List.tl l)
	</pre>		</pre>

			La fonction coupe_rec est une fonction récursive, elle permet de couper une liste en deux.

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

			La fonction coupe utilise donc la fonction coupe_rec. Elle va donc nous permettre de couper la liste en plusieurs listes d'un élément.

	== Complexité en Agda/Calf ==		== Complexité en Agda/Calf ==

Albrecht le 11 mai 2025 à 12:07

2025-05-11T12:07:17Z

← Version précédente		Version du 11 mai 2025 à 12:07
Ligne 159 :		Ligne 159 :


	Pour faire cela en OCaml, on doit tout d'abord écrire la fonction coupe :		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 :

	<pre>		<pre>
Ligne 166 :		Ligne 166 :
	3. else coupe_rec (n-1) (List.hd l :: jusquici) (List.tl l)		3. else coupe_rec (n-1) (List.hd l :: jusquici) (List.tl l)
	</pre>		</pre>

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

Albrecht le 11 mai 2025 à 12:06

2025-05-11T12:06:02Z

← Version précédente		Version du 11 mai 2025 à 12:06
Ligne 118 :		Ligne 118 :

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

Ligne 131 :		Ligne 131 :

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

Ligne 157 :		Ligne 157 :

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

			<pre>
			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)
			</pre>
			<pre>
			1. let coupe l = coupe_rec (List.length 1 /2) [] l
			</pre>

	== Complexité en Agda/Calf ==		== Complexité en Agda/Calf ==

Albrecht le 11 mai 2025 à 12:00

2025-05-11T12:00:07Z

← Version précédente		Version du 11 mai 2025 à 12:00
Ligne 75 :		Ligne 75 :
	Pour présenter cela nous utilisons la notation suivante :		Pour présenter cela nous utilisons la notation suivante :

	* Complexité de id1 : O(1)		* Complexité de id1 : <b>O(1)</b>
	* Complexité de id2 : O(n)		* Complexité de id2 : <b>O(n)</b>

	Si l'on souhaite développer cette notation, nous pouvons prendre :		Si l'on souhaite développer cette notation, nous pouvons prendre :
Ligne 93 :		Ligne 93 :
	Pour créer nos différentes fonctions et comprendre leur complexité nous avons utiliser deux langages différents :		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 <b>OCaml</b>, 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.		* Le langage <b>Agda</b>, 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.		* On utilise aussi une extension d'Agda qui se nomme <b>Calf</b> et qui sert à calculer la complexité d'une fonction sous forme de coûts.

	== Tri en OCaml ==		== Tri en OCaml ==

	Nous allons donc écrire différentes fonctions de tri dans le langage OCaml.		Nous allons donc écrire différentes fonctions de tri dans le langage <b>OCaml</b>.

	=== Tri par insertion en OCaml ===		=== Tri par insertion en OCaml ===
Ligne 106 :		Ligne 106 :
	Tout d'abord, le tri par insertion consiste :		Tout d'abord, le tri par insertion consiste :

	* Prendre en argument une liste à trier.		* Prendre en argument une <b>liste à trier</b>.
	* Prendre une liste vide.		* Prendre une <b>liste vide</b>.
	* Prendre un élément de la liste non trié.		* Prendre un <b>élément</b> de la liste non trié.
	* Insérer cet élément au bon endroit dans la liste vide (il faut donc parcourir la liste).		* <b>Insérer</b> 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.		* Puis on <b>recommence</b> 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.		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 :		Pour faire cela en OCaml nous avons besoin de la fonction d'<b>insertion</b> :

	<pre>		<pre>
Ligne 128 :		Ligne 128 :


	Nous avons ensuite besoin de la fonction de tri :		Nous avons ensuite besoin de la fonction de <b>tri</b> :

	<pre>		<pre>
Ligne 142 :		Ligne 142 :
	On trouve que pour chaque élément de la liste l' le coût augmente de 1.		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 a la somme des éléments de 1 à n-1 soit (n(n-1))/2 ce qui représente une complexité O(n²).		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é <b>O(n²)</b>.

	=== Tri par fusion en OCaml ===		=== Tri par fusion en OCaml ===
Ligne 148 :		Ligne 148 :
	Nous nous intéressons donc maintenant à une fonction de tri par fusion. Le principe de cette fonction est le suivant :		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 part d'une <b>liste à trier</b>.
	* On effectue une suite de divisions récursives en deux parties jusqu'à obtenir des listes de taille 1.		* On effectue une suite de <b>divisions récursives en deux parties</b> jusqu'à obtenir des listes de <b>taille 1</b>.
	* On trie ensuite chaque liste.		* On <b>trie</b> ensuite chaque liste.
	* Puis on les fusionne entre elles tout en les triant.		* Puis on les <b>fusionne</b> entre elles tout en les triant.

Albrecht le 11 mai 2025 à 11:54

2025-05-11T11:54:20Z

← Version précédente		Version du 11 mai 2025 à 11:54
Ligne 155 :		Ligne 155 :

	[[Fichier:arbre_complexe.png\|360px]]		[[Fichier:arbre_complexe.png\|360px]]

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

	== Complexité en Agda/Calf ==		== Complexité en Agda/Calf ==