Notes de cours № 8 (arbres) et № 9 (tas)

Note pré-doc / intra

Vous pouvez réservez un créneau de 10 minutes pour discuter votre intra à http://doodle.com/poll/ekzk25m55mgwubey. Si vous voulez juste consulter votre copie corrigée, venez pendant le temps affiché (lundi 11:30-13:00, mardi 10:30-11:30, jeudi 10-11) sans réservation.

You can reserve a time slot to discuss your mid-term/comprehensive exam at  http://doodle.com/poll/ekzk25m55mgwubey If you just want to consult your copy, come without reservation any time (Monday 11:30-13:00, Tuesday 10:30-11:30 or Thursday 10:00-11:00).

Arbres

Note 8 : notes08-trees

wikipedia logo Wikipedia

File de priorité / tas

Note 9: notes09-heap (Preuve de Théorème 9.1 fixée par rapport à l’énoncé original notes09-heap)

wikipedia logo Wikipedia

  • file de priorité EN
  • ordre de tas FR EN
  • tas binaire FR EN
  • tri par tas FR EN
  • tas d-aire EN
Publicités

Exercices pré-intra

(On choisira quelques problèmes d’ici pour la démonstration du vendredi 7 octobre — si vous avez le temps avant, venez avec vos propres solutions.)

1. Notation asymptotique

1.1 Comparaison de croissances

Remplissez le tableau suivant. Pour chaque paire f,g, écrivez « = » si f=\Theta(g), »« si f=o(g), «  » si g=o(f), et « ??? » si aucun des trois n’applique. Il n’est pas nécessaire de justifier vos réponses. \lg n dénote le logarithme binaire de n.

\begin{array}{lll}  \textbf{a} & f(n)=2^{3^n} & g(n)=3^{2^n}\\  \textbf{b} & f(n)=\lg n & g(n)=\lg\bigl((n+2015)^2\bigr)\\  \textbf{c} & f(n) = \log_3(\log_4 n) & g(n)=\log_4(\log_3 n)\\  \textbf{d} & f(n)=2015n & g(n)=n^2/2015 \\  \textbf{e} & f(n)=4n^2\lg n & g(n)=1+3n+3n^2+n^3 \\  \textbf{f} & f(n) = \sqrt{n} &  g(n) = \sqrt[3]{n}\\  \textbf{g} & f(n)=\sum_{i=0}^n 3^i & g(n)=3^n \\  \textbf{h} & f(n)=\sum_{i=1}^n n/i & g(n)=n\lg n\\  \textbf{i} & f(n)=n^{2015} &  g(n)=n! \\  \textbf{j} & f(n)=n! & g(n)=(n+1)! \\  \textbf{k} & f(n)=2.015^n & g(n)=2.015^{n+1} \\  \textbf{l} & f(n)=2.015^{n} & g(n)=2.015^{2n} \\  \textbf{m} & f(n)=2.015^{\lg n} & g(n)=2^{\lg n} \\  \textbf{n} & f(n)=n\lg n & g(n)=\lg(n!) \\  \textbf{o} & f(n)=n \lg n & g(n) = \begin{cases}  1 & \{ n<2\}\\  g(\lceil n/2\rceil) + g(\lfloor n/2\rfloor)+ O(1) & \{ n\ge 2\}  \end{cases}\\  \textbf{p} & f(n)=\max\{1,n+2015\sin n\} & g(n) =  g(n-1) + \Theta(1) \qquad \{ n>0\}\\  \textbf{q} & f(n) = n! & g(n)=\begin{cases}  1 & \{ n=0 \}\\  2n \cdot g(n-1) & \{n>0\}  \end{cases}\\  \hline  \end{array}

1.2 Preuves

  • Démontrez que n^3+2n^2+8=\Theta(n^3) .
  • Démontrez que n^{3+1/\lg n}=\Theta(n^3).
  • Démontrez que 2015^{O(\log n)} = n^{O(1)}.
  • Démontrez que 3^{n+1}=O(3^n) mais 3^{2n}\ne O(3^n)
  • Est-ce que n^{2+o(1)}=O(n^2)? Justifiez votre réponse.
  • Démontrez que 2^{\Theta(n)}=\bigl(\Theta(1)\bigr)^n.

2. Queue et pile

Dans les problèmes suivants, on veut implanter une queue (file FIFO) en utilisant une ou deux piles exclusivement à travers de l’interface du TA qui supporte les opérations \mathsf{push}(x), \mathsf{pop}() et \mathsf{isEmpty}(), en O(1) temps.

2.1 Couper l’herbe sous le pied

Implantez une queue (avec opérations \mathsf{enqueue}(x), \mathsf{dequeue}()) à l’aide d’une pile. Analysez le temps de calcul, et l’usage de mémoire des opérations en fonction de la taille de la file.

Indice: Il est clair qu’on peut implanter \mathsf{enqueue} par \mathsf{push}. Afin d’implanter \mathsf{dequeue}, on a besoin d’accéder au fond de la pile. Développez donc un algorithme récursif pour supprimer un élément au fond de la pile, en n’utilisant que \mathsf{push} et \mathsf{pop}.

2.2 Deux c’est mieux

  • Implantez une queue (file FIFO) avec les opérations \mathsf{enqueue}(x) et \mathsf{dequeue}(), en utilisant deux piles.
    Indice: utilisez les deux piles pour stocker les éléments aux deux extremités. deuxcestmieux
  • Ajoutez l’opération \mathsf{delete}(k) qui défile k>0 fois ou arrête plus tôt quand la queue est vide. L’implantation ne devrait jamais mener à un débordement des piles sous-jacentes. L’opération ne retourne pas de valeur.
  • Quel est le temps de calcul des opérations \mathsf{enqueue} et \mathsf{delete}(k) dans le pire cas? Donnez une implantation qui garantit que le temps de calcul est toujours O(m) pour n’importe quelle  séquence de m opérations  — autrement dit, que le coût amorti des opérations est O(1). Démontrez que cette borne vaut pour votre solution.

3. Tableaux

3.1 On implémente un sac

Le type abstract sac est une collection de paires (\mathsf{key}, \mathsf{value}); où les clés ne sont pas nécessairement uniques. Développez une structure de données basée sur un tableau non-trié (qu’on élargit/réduit dynamiquement) pour supporter les opérations suivantes:

  • \mathsf{add}(\mathsf{key},\mathsf{value}) – ajoute une nouvelle paire (on permet des clés répétées)
  • \mathsf{delete}(\mathsf{key}) — supprime tous les éléments avec cette clé
  • \mathsf{count}(\mathsf{key}) — retourne le nombre des éléments avec cette clé

Analysez l’efficacité de votre implantation.

3.2 Décalage circulaire

shift
Supposons qu’on veut faire des décalages circulaires dans un tableau A[0..n-1]. Un décalage par \delta correspond à l’exécution parallèle des affectations A[(i+\delta)\bmod n]\leftarrow A[i].

Quand \delta=1, il est clair qu’on peut performer le décalage en place par une boucle simple:

Shift1(A[0..n-1])
{
    i ⟵ 0; navette ⟵ A[0];
    do
    {
        i ⟵ (i+1) mod n;
        échanger navette ⟷ A[i]
    } while (i≄0)
}

Donnez un algorithme \mathsf{Shift}(A,g,d,\delta) qui exécute un décalage circulaire à \delta positions du sous-tableau A[g..d-1] en place. Vous pouvez assumer que n=d-g\ge 0 et que 0<\delta<n. L’algorithme doit utiliser un espace de travail (excluant l’entrée A[0..n-1])  de O(1), et s’exécuter en O(n), pour tout choix de \delta (même pour p.e., \delta=n/3).

3.3 Permutations

Une permutation de n éléments est représentée par une vecteur \pi=\pi[0..n-1] t.q. pour tout j=0,1,\dotsc,n-1, il existe exactement un indice i\pi[i]=j. La permutation peut être appliquée à n’importe quel tableau A[0..n-1] pour définir le réarrangement des ses éléments: \pi\cdot A = \begin{bmatrix} A[\pi[1]] & A[\pi[1]] & \dotsm & A[\pi[n-1]]\end{bmatrix}. Il n’est pas difficile de réarranger les éléments à l’aide d’un tableau auxiliaire:

Perm(A[0..n-1], π[0..n-1]) 
{
    initialiser tableaux auxiliaire aux[0..n-1]
    for (i ⟵ 0,1,...n-1) {aux[i] ⟵ A[π[i]]}
    for (i ⟵ 0,1,...n-1) {A[i] ⟵ aux[i]} 
}

Le but de cet exercice est de développer un algorithme pour faire le même réarrangement en place, sans utiliser un tableau auxiliaire.

permutation-cyclesL’idée est de considérer la décomposition de la permutation en chaînes d’affectations qu’on peut exécuter l’une après l’autre. Un cycle de la permutation est une suite maximale d’indices différents i, \pi[i], \pi[\pi[i]], \pi[\pi[\pi[i]]],\dotsc. On peut décomposer chaque permutation uniquement en un ensemble de cycles. Par exemple, la permutation \pi=\begin{bmatrix} 0 & 4 & 2 & 1 & 3\end{bmatrix} comprend trois cycles: (0), \begin{pmatrix} 1 & 4 & 3\end{pmatrix} et (2).

Donnez un algorithme \mathsf{Perm}(A,\pi) pour calculer \pi\cdot A en place.
Les arguments \pi,A sont des tableaux de taille (connue) n. L’algorithme doit prendre O(n) temps et utiliser O(1) mémoire de travail (à l’addition de \pi et A). L’algorithme a le droit de changer les éléments de \pi pendant son exécution.

Indice: Décalez les éléments au long des cycles i,\pi[i], \pi[\pi[i]]\dotsc,.

4. Liste chaînée

4.1 Comment battre les cartes?

Le but de battre les cartes est d’obtenir un ordre aléatoire dans le paquet. Mathématiquement, on veut une permutation aléatoire uniformement distribuée. L’algorithme suivant construit une telle permutation.

RndPerm(n) // contruit permutation aléatoire π[0..n-1]
{
    initialiser π[0..n-1]
    for (i ⟵ 0,1,...,n-1) { π[i] ⟵ i }
    for (i ⟵ 0,1,...,n-2)
    {
        j ⟵ Random(i, i + 1, . . . , n − 1) // une des valeurs i..n-1 tirée au hasard
        échanger π[i] ⟷ π[j]
    } 
}

La fonction Random est un générateur de nombres pseudoaléatoires
pour choisir l’indice j uniformement distribué parmi i,i+1,\dotsc,n-1.

  • Implémentez la logique de RndPerm pour calculer la permutation aléatoire d’une
    liste simplement chaînée. Plus précisement, donnez le pseudocode pour \mathsf{ListPerm}(x,n) qui retourne la tête d’une liste avec n noeuds (par exemple, n cartes d’un jeu) après une permutation aléatoire de distribution uniforme. L’argument x est la tête de la liste initiale avec n noeuds. Analysez le temps de calcul de votre algorithme (Random prend O(1)).
  • Proposez un algorithme qui implante le battage par feuilleter (le «riffle shuffle», illustré ci-dessous) à l’aide de listes simplement chaînées. Analysez le temps de calcul de l’algorithme. Pour comparer à \mathsf{ListPerm}, notez qu’il suffit de refaire le battage O(\log n) fois pour convergence à la distribution uniforme [Dave Bayer et Persi Diaconis, 1992]. (En particulier, sept itérations suffisent pour 52 cartes.)riffle-shuffle
    À l’entrée (a), on a une liste \mathbf{x}=(x_1,x_2,\dotsc,x_n) et un argument k\in\{0,1,\dotsc,n\}. L’algorithme (b) découpe la liste en A=(x_1,\dotsc,x_k) et B=(x_{k+1}, \dotsc, x_n) (les listes peuvent être vide), (c) entrelace les deux listes au hasard, (d) et ainsi construit la fusion aléatoire des deux listes, où l’ordre original entre les éléments de la même sous-liste reste le même.card-shuffling