TD7 : XOR, pyramide de nombres et codage binaire

Énoncé

EX 1

1.

T[i] <- true

puis, on fait un passage dans T, et on revoie l’indice $j$ tel que $T[j] ≠ true$

2.

NB : la taille de l’entrée et en $O(n\log n)$, car on a $n$ cases contenant chacune $\log n$ bits. Donc temps linéaire en la taille de l’entrée = en $O(n \log n)$

M1

On calcule $S =\frac{n(n+1)}{2}$, puis on soustrait chaque $T[i]$ à cette valeur : l’entier manquant est $S$ à la fin.

M2

On fait le XOR bit à bit de tous les éléments du tableau.

Puis : si $n$ est impair, on retourne cette valeur, sinon, on retourne le complémentaire.

Ex :

Avec 0 qui manque :

pour [1;2]

01 ^ 10 = 11 = ~00

pour [1;2;3]

01 ^ 10 ^ 11 = 00

EX 2

Ex :

42
| \
1   7
| \/ \
8 13  5

digraph mon_graphe {
    42 -> 1 -> 8;
    42 -> 7 -> 5;
    1 -> 13;
    7 -> 13;
}

M1

Djikstra entre la racine et chacune des feuilles.

M2

Parcourt militaire du bas vers le haut, en ré-étiquetant les noeuds de manière à maximiser un le poids du chemin de la racine vers une feuille, en remplaçant l’étiquette du père par le son étiquette + le max des deux fils.

digraph mon_graphe {
    42 -> 1 -> _8_;
    42 -> 7 -> _5_;
    1 -> _13_;
    7 -> _13_;
}

⇓

digraph mon_graphe {
    42 -> _14_ -> _8_;
    42 -> _20_ -> _5_;
    _14_ -> _13_;
    _20_ -> _13_;
}

⇓

digraph mon_graphe {
    _62_ -> _14_ -> _8_;
    _62_ -> _20_ -> _5_;
    _14_ -> _13_;
    _20_ -> _13_;
}

def alg(M):
  T = [0]*n
  for i in range(len(M[-1])):
    for j in range(i):
      T[j] = max(T[j], T[j+1]) + M[i,j]
  return T[0]

EX 3

1.

Si $w ≝ a_1 ⋯ a_p, w’ ≝ b_1 ⋯ b_r ∈ 𝛴^\ast$ :

\[𝛼(w) = u_1 ⋯ u_k = 𝛼(w')\]

En posant

\[i_o = \min\{i∈⟦1, k⟧ \vert ∃a∈𝛴; 𝛼(a) = u_1 ⋯ u_i \}\]

Si $𝛼(a_1) ≤ 𝛼(b_1)$ :

\[u_1 ⋯ u_{i_0} = 𝛼(a_1)\]

Or, $u_1 ⋯ u_{i_0}$ est un préfixe de $𝛼(b_1)$ : mais comme il ne peut pas être strict, c’est exactement $𝛼(b_1)$.

Donc

\[𝛼(a_1) = 𝛼(b_1)\]

et par injectivité de $𝛼$ sur les letttres :

\[a_1 = b_1\]

Puis, on conclut par un récurrence que $w = w’$.

2.

digraph mon_graphe {
    𝜀 -> 0 -> 00;
    𝜀 -> 1 -> 10;
    0 -> 01;
    1 -> 11;
}

Arbre binaire, où :

• étiquette du fils gauche = étiquette du père concaténée avec 0
• étiquette du fils droit = étiquette du père concaténée avec 1

Les feuilles sont étiquetées par les mots de $𝛴^\ast$.

Il existe un seul chemin de la racine vers une feuille donnée étiquetée par un mot de $𝛴^\ast$, car le codage est préfixe.

Seules les feuilles sont des codes de mots de $𝛴^\ast$, car sinon toute étiquette de noeud interne est préfixe de l’étiquette de ses fils : impossible.

3.

• L’arbre est binaire, donc tout noeud interne a au plus deux fils.

• Tout noeud interne $p$ a au moins deux fils :

sinon, s’il n’a qu’un fils $f$ (noeud interne) : $𝛼(f)$ est de la forme $𝜀_1 ⋯ 𝜀_r 𝜀_p 𝜀_f$ (où $𝜀_p$ (resp. $𝜀_f$ est la dernière lettre de $p$ (resp. $𝜀_f$)), mais pourrait être rendu strictement moins long $𝜀_1 ⋯ 𝜀_r 𝜀_f$

digraph mon_graphe {
    p -> p1 -> p10;
    p1 -> p11;
}

⇓

digraph mon_graphe {
    p -> p0;
    p -> p1;
}

4.

Soit $n$ un noeud interne de profondeur maximale : il a deux fils (cf. question précédente) qui sont des feuilles, par maximalité de sa profondeur.

Si on échange ses deux fils par les deux feuilles dont le nombre d’occurrences est le plus faible, et on garde un codage préfixe optimal, puisque qu’on diminue le coût du codage, de la sorte.

5.

On remarque que

\[coût(T) = coût(T') + f(x) +f(y)\]

Montrons que $T$ est optimal, si $T’$ l’était.

Comme :

\[coût\_opt(𝛴) ≤ coût(T) = coût(T') + f(x) +f(y) = coût\_opt(𝛴') + f(x) + f(y)\]

Or, pour tout $T_0$ atteignant $coût_opt(𝛴)$ (on peut supposer $x$ et $y$ soeurs dans $T_0$), en regroupant $x$ et $y$ pour construire $T’_0$, il vient que :

\[coût\_opt(𝛴') ≤ coût(T'_0) = coût(T_0) - f(x) - f(y) = coût\_opt(𝛴) - f(x) - f(y)\]

Donc $T$ est optimal pour $𝛴$.

6.

Algo récursif :

• s’il n’y a que deux lettres $x,y$ dans $𝛴$, l’arbre

digraph mon_graphe {
    𝜀 -> x[label="0"];
    𝜀 -> y[label="1"];
}

convient

• s’il y a $n$ lettres : on construit $𝛴’$ de la même maière qu’avant, $x,y$ dans $𝛴$, pour l’arbre $T’$ construit récursivement, on construit l’arbre $T$ de la manière suivante.

digraph mon_graphe {
    Tprime -> z
}

⇓

digraph mon_graphe {
  T -> x[label="0"];
  T -> y[label="1"];
}