TD2 : Correction, Master Theorem.

Énoncé

TD 2

EX1

1.

Spécification :

Préconditions : $x = v ∧ x \geq 0$

f91(x)

Postconditions : \(out = \begin{cases} 91 \text{ si $x \leq 100$ } \\ x-11 \text{ sinon} \end{cases}\)

2.

Correction :

  • Cas 1: $x > 100$ : immédiat
  • Cas 2: $x ∈ ⟦90, 100⟧$ : alors f91(x) = f91(f91(x+11)) = f91(x+1)

Donc :

  • si $x = 100$, f91(x) = 91
  • si $x = 99$, f91(x) = f91(100) = 91

et par une récurrence immédiate : $∀ x ∈ ⟦90, 100⟧, f91(x)=91$

  • si $x ∈ ⟦0, 89⟧$ : par une récurrence immédiate (par “tranche” de 10) : $f91(x)=91$

3.

Terminaison : cf. Correction

Correction

On écrit la précondition en haut, la postcondition en bas, puis on va dans le else (le if : trivial) :

y ⟵ f91(x+11)
z ⟵ f91(y)

$x \leq 100$, et :

$x+11>100$ $x+11 \leq 100$
$90\leq x \leq 100$ $0\leq x \leq 89$
$y = x+1$ $y ⟵ 91$
$z = f91(y)$ $z ⟵ 91$
Cas 1: $y=101$ → $z=91$  
Cas 2: $y\leq 100$ → $z=91$  

##EX2

  1. C’est tri, car on compose la permutation de départ par des transpositions distinctes, et toute permutation est produit de transpositions. (correction : négation de la condition du “while”).

Variant : nombre de transpositions distinctes dans la décomposition de la permutation de départ en produit de transpositions distinctes (décroît strictement).

  1. Ne termine pas :

Ex: (2,2,1) ⟶ (2,1,1) (en permutant les deux derniers) ⟶ (2,2,1) (en permutant les deux premiers)

3.

M1 : On pose $p ≝ 1 + max_i(T[i])$ (qu’on fixe une fois pour toutes). \(f(T) ≝ \sum\limits_{1\leq i \leq n} p^i T[i] \leq \sum\limits_{1\leq i \leq n} p^{i+1} = cste\)

Montrons que cet invariant décroît strictement :

\begin{align} f(T)-f(T’) &= p^i(T[i] - T’[i]) + p^j(T[j] - T’[j])
&= p^i\underbrace{(T[i] - a_i)}_{< p} + p^j\underbrace{(T[j] - a_j)}_{\leq -1}
&< p^{i+1} - p^j
&< p^{i+1}(1 - p^{j-i-1})
&< 0
\end{align}

Donc $f$ est strictement croissante et majorée ⟶ ça termine.

M2: Dans le polytope $⟦0,p⟧^n$ : Pour l’ordre lexicographique de droite à gauche, le $n$-uplet croît. En fait, le polynôme donne plus de poids

EX3

  1. Opération élémentaire : addition OU multiplication de deux chiffres (entre 0 et 9). 
         0 1 1 0
     1 0 1 0
     _______
     0 0 0 0
   1 0 1 0
  0 0 0 0
1 0 1 0

Complexité : $O(n log(n) + n^2) = O(n^2)$

  1. Algorithme de Karatsuba : Pour faire le produit de deux nombres : 3 multiplications, 6 additions = $O(n)$
\[T(n) = 3T(n/10) + O(n)\]

Master Theorem :

\(T(n) = aT(n/b) + f(n)\)

  • Si $f(n) = o(n^{\log_b(a)})$ alors $T(n) = O(n^{\log_b(a)})$
  • Si $f(n) = 𝛩(n^{\log_b(a)})$ alors $T(n) = O(n^{\log_b(a)} \log(n))$
  • Si $n^{\log_b(a)} = o(f(n))$ ET $a f(n/b) \overset{\text{ult}}{<} f(n)$ alors $T(n) = O(f(n))$

Pour les polynômes : on procède de même, avec $10 ⟵ X$

EX 4

  1. En $𝛩(nk)$ : on met le min en 1ère place, puis on considère $T[2⋯n]$ (dont on met le min en 1ère place), etc… $k$ fois.
  2. En $𝛩(n \log(n))$ : on trie le tableau en $𝛩(n \log(n))$, puis : on récupère le $k$-ième élément.
  3. Comparer $k$ et $ln(n)$. 4.
    • Terminaison : évidente
    • Correction : par récurrence sur la taille du tableau :
      • Initialisation : claire.
      • Hérédité : naturelle, par disjonction des cas à la fin de l’algo.

Partition rendant l’algo efficace : lorsque la valeur est proche de la médiane.

Pire des cas : la valeur est un élément extrémal.

  1. On prend la médiane des médianes (faites sur des paquets de 5 éléments, qu’on appellera “médianes intermédiaires”).

On veut borner le nb d’éléments en-dessous de la médiane.

Nb de médianes intermédiaires : $(n-4)/5$

Nb d’éléments plus petits que chaque sous médiane : $\frac 1 2 \frac{n-4}{5}$

Nb d’éléments plus petits au total, au moins ($n \geq 25$) : $3 \frac 1 2 \frac{n-4}{5} = \frac{3n}{10} - \frac 6 5 = N$

\(n_3 = n - N = \frac{7n}{10} + \frac 6 5 < 3n/4\) ($n=24$)

6)

  • $cn$ : vient :
    • du tri (en temps constant, puisque tabelaux de taille fixée) des $n/5$ sous tableaux pour en déterminer les médianes.
    • du parcours final pour placer les éléments dans $T_1, T_2, T_3$
  • $Temps(n/5)$ : recherche du médian des médianes
  • $Temps(3n/4)$ : application de l’algo dans $T_1$ ou $T_3$.

⟹ Cours : $T(n) \leq O(n)$

Leave a comment