Complexité et algorithmes classiques

Question 1

f = Θ(g)

Answer 1

f = Θ(g) si f = O(g) et g = O(f) => traduit un encadrement

Question 2

Calcul de Sn = ∑kⁿ [k variant de 0 à p]

Answer 2

On somme les égalités suivantes pour k entre 0 et p
(k+1)ⁿ⁺¹ - kⁿ = ∑(i parmi n+1)kⁱ [i variant de 0 à n]
Soit (p+1)ⁿ⁺¹ = (n+1)Sn + ∑(i parmi n+1)Sᵢ [i variant de 0 à n-1]

Question 3

Relation de récurrence C(n) = aC(n-1) + f(n)

Answer 3

On étudie D(n) = C(n) / aⁿ
D’où D(n) = D(n-1) + f(n) / aⁿ = ∑ f(i) / aⁱ [i variant de 0 à n]
(démonstration par récurrence)

Question 4

C(n) = C(⌊n/2⌋) + C(⌈n/2⌉) + a

Answer 4

C(n) = C(⌊n/2⌋) + C(⌈n/2⌉) + a = n*C(1) + a(n-1)

Question 5

Algorithme de Horner itératif

Answer 5

let horner tab x =
	let n = Array.length tab - 1 in let res = ref tab.(n) in 
	for i = n-1 downto 0 do
		res := !res *. x +. tab.(i)
	done;
	!res ;;

Question 6

Algorithme de Horner récursif

Answer 6

let rec horner l x =
	match l with
	| [] -> 0.
	| t::q -> t +. x *. horner q x
;;

Question 7

Recherche d’élément dans un tableau

Answer 7

let recherche elmt tab = let n = Array.length tab -1 in let i = ref 0 in
	while !i <= n &amp;&amp; tab.(!i) <> elmt do incr i done;
	!i <= n ;;

Question 8

Tri insertion récursif

Answer 8

let rec tri_insertion l = let rec insere a l = 
	match l with
	|[] -> [a]
	|t::q -> if a <= t then a::l else t::(insere a q)
	in
	match l with
	|[] -> []
	|t::q -> insere t (tri_insertion q)
;;

Question 9

Exponentiation rapide

Answer 9

let rec expo_rapide x n =
	match n with
	|0 -> 1.
	|_ -> let x0 = expo_rapide x (n/2) in if n mod 2 == 0 then x0 *. x0 else x0 *. x0 *. x
;;

Question 10

Tri fusion récursif

Answer 10

let rec fusion l1 l2 = 
	match l1, l2 with
	|[],_ -> l2
	|_,[] -> l1
	|t1::q1, t2::q2 -> if t1 > t2 then t2::(fusion l1 q2) else t1::(fusion q1 l2)
;;
let rec division l =
	match l with
	|[] -> [],[]
	|[a] -> [a],[]
	|t::t1::q -> let div1, div2 = division q in t::div1, t1::div2
;;
let rec tri_fusion l = 
	match l with
	|[] -> []
	|[a] -> [a]
	|_ -> let l1, l2 = division l in fusion (tri_fusion l1) (tri_fusion l2)
;;

Question 11

Formule du binôme par le triangle de Pascal

Answer 11

let rec binom1 n p =
	match n,p with
	|n, p when p = 0 || p = n -> 1
	|n, p when 2*p > n -> binom1 n (n-p)
	|n, p -> (binom1 (n-1) (p-1)) + (binom1 (n-1) p)
;;

Question 12

Formule du binôme par le triangle de Pascal (+ mémoïzation)

Answer 12

let rec binom2 n p = 
	match n,p with
	|n, p when p = 0 || p = n -> 1
	|n, p when 2*p > n -> binom1 n (n-p)
	|n, p -> let tab = Array.make_matrix (n+1) (p+1) 1 in
		for i = 1 to p do 
			for j = 1 to i-1 do
				tab.(i).(j)

Question 13

Formule du binôme par (p parmi n) = n/p * (p-1 parmi n-1)

Answer 13

let rec binom3 n p =
	match n,p with
	|n, p when p = 0 || p = n -> 1
	|n, p when 2*p > n -> binom1 n (n-p)
	|n, p -> (n*(binom3 (n-1) (p-1)))/p
;;