Notes de cours № 10 (tris élémentaires et tri par fusion) et № 11 (tri rapide); exercices

Note 10 : notes10-tris

Note 11: notes11-quicksort

Exercices: exo10-tris

wikipedia logo Wikipedia

  • tri par insertion FR EN
  • tri par sélection FR EN
  • tri par fusion FR EN
  • tri rapide FR 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

Exercices (volontaires): récursion et liste chaînée

Pour ceux qui meurent d’ennui ou veulent juste tester leurs connaissances, j’ai préparé deux jeux d’exercices (basés sur des examens anciens).

Si vous travaillez sur un exercice ou deux, n’hésitez pas à venir me voir pour commentaires ou à en discuter ci-dessous. (Mais ne postez pas de solutions SVP.)