CowBloke : Mise en place du wiki de notes

2026-09-24T18:51:16Z

Mise en place du wiki de notes

Nouvelle page

''Fiche d'exemple : code OCaml et C avec coloration. Modifie-la ou supprime-la librement.''

== Principe ==
{{Définition
|titre=Diviser pour régner
|contenu=
On découpe un problème de taille <math>n</math> en <math>a</math> sous-problèmes de taille <math>n/b</math>, on les résout récursivement, puis on combine les solutions.
}}

== Tri fusion (OCaml) ==
<syntaxhighlight lang="ocaml" line>
let rec scinder = function
| [] -> [], []
| [x] -> [x], []
| x :: y :: q -> let a, b = scinder q in x :: a, y :: b

let rec fusion l1 l2 = match l1, l2 with
| [], l | l, [] -> l
| x :: q1, y :: q2 ->
if x <= y then x :: fusion q1 l2 else y :: fusion l1 q2

let rec tri_fusion = function
| ([] | [_]) as l -> l
| l -> let a, b = scinder l in fusion (tri_fusion a) (tri_fusion b)
</syntaxhighlight>

{{Formule
|titre=Complexité du tri fusion
|contenu=
<math display="block">C(n)=2\,C(n/2)+\Theta(n)\quad\Longrightarrow\quad C(n)=\Theta(n\log n)</math>
}}

== Recherche dichotomique (C) ==
<syntaxhighlight lang="c" line>
/* Renvoie un indice de x dans t (trié, de taille n), ou -1. */
int dichotomie(const int *t, int n, int x) {
int g = 0, d = n - 1;
while (g <= d) {
int m = g + (d - g) / 2; /* évite le dépassement de g + d */
if (t[m] == x) return m;
if (t[m] < x) g = m + 1; else d = m - 1;
}
return -1;
}
</syntaxhighlight>

{{Méthode
|titre=Prouver la terminaison et la correction
|contenu=
* ''Terminaison'' : le variant <math>d-g</math> est un entier qui décroît strictement à chaque tour tant que <math>g\le d</math>.
* ''Correction'' : invariant « si <math>x</math> est dans <math>t</math>, il est dans <math>t[g..d]</math> ».
}}

On peut aussi écrire du code dans une phrase : <syntaxhighlight lang="ocaml" inline>List.map (fun x -> x * x) l</syntaxhighlight>.

Prépa:Informatique/Diviser pour régner - Historique des versions

CowBloke : Mise en place du wiki de notes

CowBloke : Mise en place du wiki de notes