TD6 : Algorithmes gloutons, Matroïdes,

Énoncé

EX 1

1)

M1

Quand une tâche est faite en retard, elle est faite en retard (la pénalité est encaissée)… : on n’a plus rien à perdre, on peut la repousser après les tâches en avance qui sont après elle dans la permutation.

M2

Si un couple de tâches $(a_i, a_j)$, avec $i<j$ est tel que :

  • $a_i$ est en retard
  • $a_j$ est en avance

Alors permuter $a_i$ et $a_j$ ne fait pas diminuer la pénalité, et le processus termine (nombre fini d’inversions, et décrément à chaque étape d’une inversion).

2) On considère un tuple de tâche $(t_1, ⋯, t_n)$ en avance : on classe les $t_i$ par ordre croissant de date d’échéance : $t_i$ est placée en position $k_i$.

Nécessairement : les $(t_{k_i})_j$ restent en avance.

Car la première tâche était en avance avec une position ultérieure, et on conclut par une récurrence immédiate en :

  • plaçant l’instant initial $t_0$ après avoir effectué la première tâche.
  • décrémentant les $d_i$ de 1.

Hypothèse de récurrence sur $k$ : si $a_1, ⋯, a_k$ est un ordonnancement partiel de tâches, il peut être trié par ordre d’échéance croissant.

3)

(1) ⟹ (2) : évident, par l’absurde.

Lemme des tiroirs : on a $N_t(F)>t$ tâches à mettre de manière injective (deux tâches ne peuvent pas s’exécuter en même temps) dans $t$ cases : impossible.

(2)⟹(3) : Si les tâches de $F$ sont ordonnancées $(a_1, ⋯, a_n)$ par ordre monotone croissant de dates d’échéances, alors aucune des tâches n’est en retard, car sinon :

  • ABS : en notant $a_t$ une tâche en retard, il vient que $N_t(F)>t$, car les $t-1$ tâches qui la précèdent sont aussi

(3)⟹(1) : utiliser 1. et 2.

4.

  • $I≠∅$
  • Clos par inclusion : en conservant le même ordonnancement.
  • Propriété d’échange :
    • Soient $E’, E’’ ∈ I$, tq $\vert E’ \vert < \vert E’’ \vert$ : alors il existe $e∈E’‘\backslash E’$ tq $E’∪{e}∈I$
    • \[k ≝ \max \{t \vert N_t(E')≥N_t(E'')\}\]

En particulier : \(N_{k+1}(E')<N_{k+1}(E'') ≤ k+1\)

Pour $e∈E’‘\backslash E’$ qui doit s’effectuer avant $k+1$ :

\(F≝ E'∪\{e\}\) implique que

  • $N_i(F)≤i$ pour $i≤k$
  • Pour $i≥k+1$ : $N_i(E’) < N_i(E’’) ≤ i$
\[\{a ∈F \vert d(a) ≤ i\} = \{a ∈E' \vert d(a) ≤ i\} ∪ \{e\} \\ N_i(F) = N_i(E') + 1 ≤ N_i(E'') ≤ i\]

Donc d’après 3. : $F∈I$.

  1. Matroïde ⟹ Algo glouton optimal.

À somme totale des pénalités est constante, on diminue les pénalités des tâches en retard en augmentant au maximum les pénalités des tâches en avance.

EX 3

Différents cas

Zig

digraph graphname {
    graph [ordering="out"];
    1 [shape=triangle];
    2 [shape=triangle];
    3 [shape=triangle];
    p -> x;
    x -> 1;
    x -> 2;
    p -> 3;
 }

⇓

digraph graphname {
    graph [ordering="out"];
    1 [shape=triangle];
    2 [shape=triangle];
    3 [shape=triangle];
     x -> 1;
     x -> p;
     p -> 2;
     p -> 3;

 }

Zig-zig

digraph graphname {
    graph [ordering="out"];
    1 [shape=triangle];
    2 [shape=triangle];
    3 [shape=triangle];
    4 [shape=triangle];
     g -> p;
     g -> 4;
     p -> x -> 1;
     x -> 2;
     p -> 3;

 }

⇓

digraph graphname {
    graph [ordering="out"];
    1 [shape=triangle];
    2 [shape=triangle];
    3 [shape=triangle];
    4 [shape=triangle];
     x -> 1;
     x -> p;
     p -> 2;
     p -> g;
     g -> 3;
     g -> 4;

 }

Zig-zag

digraph graphname {
    graph [ordering="out"];
    1 [shape=triangle];
    2 [shape=triangle];
    3 [shape=triangle];
    4 [shape=triangle];
     g -> p;
     g -> 4;
     p -> 1;
     x -> 2
     x -> 3;
     p -> x;

 }

⇓

digraph graphname {
    graph [ordering="out"];
    1 [shape=triangle];
    2 [shape=triangle];
    3 [shape=triangle];
    4 [shape=triangle];
     x -> p;
     p -> 1;
     p -> 2;
     x -> g;
     g -> 3;
     g -> 4;
 }

Zig / Zig-zig / Zig-zag

3.

On suppose

\[∀x,y ∈ A_1 \times A_2; x≤y\] \[A'_1 = Splay(\max A_1) \\ A'_2 = Splay(\min A_2)\]

4.

Potentiel : somme des rangs.

\[P(A) = \sum\limits_{n ∈ \text{ noeuds de } A} rank(n)\]

Zig

\[𝛥P = \log(\#2 + \#3 + 1) - \log(\#1 + \#2 + 1) \\ = 𝛥rank(x)\]

Zig-zig

\[\begin{align*} P(A) &= rank'(g) - rank(g) + rank'(p) - rank(p) + rank'(x)- rank(x) \\ &= rank'(g) + rank'(p) - rank(p) - rank(x) &&(rank(g) = rank'(x)\\ &≤ 2(rank'(x)-rank(x)) \end{align*}\]

Zig-zag

\[\begin{align*} P(A) &= rank'(g) - rank(g) + rank'(p) - rank(p) + rank'(x)- rank(x) \\ &= rank'(g) + rank'(p) - rank(p) - rank(x) &&(rank(g) = rank'(x)\\ &≤ 2(rank'(x)-rank(x)) \end{align*}\]

Taille de l’arbre : $n$.

Complexité amortie :

\[C_a = rank(x_{fin}) - rank(x_{ini}) \\ = log(n) - cste \\ = O(\log(n))\]

Pour $m$ opérations :

Complexité :

\[C ≤ \sum_x rank'(x) - rank(x) \\ = O(n \log(n) + m \log(n))\]

Complexité = Complexité amorties ($m$ opérations de coût $\log(n)$) + Différence de potientiel (= somme des différences de rangs)

Leave a comment