TD 11 - Files

1 Des files et des piles

1.1 Exercice 1

Expliquer comment implémenter une file à l’aide de deux piles. Analyser le temps d’exécution des opérations de file.

AstucePrincipe

Utiliser deux piles P1 (entrée) et P2 (sortie) : - Enfiler : empiler dans P1 - Défiler : si P2 vide, transférer tout P1 vers P2, puis dépiler P2

Complexité amortie : \(O(1)\) par opération

1.2 Exercice 2 🏠

Expliquer comment implémenter une pile à l’aide de deux files. Analyser le temps d’exécution des opérations de pile.

2 Énumération

2.1 Exercice 3

Écrire un algorithme qui prend comme entrée un entier \(n\) et affiche l’écriture ternaire (en base 3) de tous les nombres entre 1 et \(3^n-1\).

NoteBase 3 (ternaire)

En base 3, on utilise les chiffres 0, 1, 2.

Exemples : - \(1_{10} = 1_3\) - \(2_{10} = 2_3\) - \(3_{10} = 10_3\) - \(4_{10} = 11_3\) - \(5_{10} = 12_3\) - \(8_{10} = 22_3\) - \(9_{10} = 100_3\)

3 Tri et file

3.1 Exercice 4

On considère une file Q qui contient \(n\) entiers distincts dans un ordre quelconque.

On souhaite trier cette file par ordre croissant, en utilisant uniquement des files (pas de tableaux, ni de piles).

On pourra déclarer et manipuler autant de files auxiliaires que nécessaire.

  1. Écrire un algorithme qui trie la file Q en utilisant seulement des opérations de manipulation de files :

    • Enfiler(F,x) (ajouter à la fin)
    • Defiler(F) (retirer au début)
    • EstVide(F) (tester si la file est vide)

    On pourra se servir de l’idée générale suivante :

    1. On prend comme minimum temporaire le premier élément de Q.

    2. Tant que la file Q n’est pas vide :

      • Parcourir \(k\) valeurs de Q pour trouver son plus petit élément.
        • si l’élément est plus grand, on le met dans une file Q1.
        • sinon, on place l’élément temporaire minimum dans la file Q1 et on le garde par le nouveau minimum temporaire.
      • On ajoute ce minimum dans une nouvelle file résultat R.
      • on transfère tous les éléments de Q1 dans Q

    3. Répéter jusqu’à ce que Q soit vide.

  2. Illustrer le déroulement de l’algorithme pour la file Q = [5, 2, 4, 1] : indiquer à chaque étape le contenu des files utilisées et expliquer le processus de recherche et retrait du minimum.

  3. Quelle est la complexité de ce tri ?

Étape 1 : Trouver min (1) - Q = [5, 2, 4, 1] - min temporaire = 5 - Parcours : 5 < 2 ? Non → Q1 = [5] - 2 est nouveau min, 5 dans Q1 - Parcours continue… - R = [1], Q = [5, 2, 4]

Étapes suivantes : répéter pour 2, 4, 5

Résultat final : R = [1, 2, 4, 5]

4 En plus

4.1 Exercice 5 : Fisher-Yates 🏠

Objectif : On souhaite écrire un algorithme qui prend en entrée une file contenant \(n\) entiers distincts (par exemple les entiers de 1 à \(n\)), et qui rend en sortie ces entiers mélangés de façon totalement aléatoire grâce à une permutation équiprobable.

On considère : - Une file Q, initialisée avec les éléments de 1 à \(n\). - Une file résultat R, initialement vide.

On supposera que l’on dispose d’une fonction Alea(k) qui renvoie un nombre entier aléatoire entre 1 et k.

  1. Écrire un algorithme qui, à chaque étape, sélectionne aléatoirement un élément de la file Q, le retire de Q et le place à la fin de la file R.

  2. Quelle est la complexité de votre algorithme ?

NoteAlgorithme de Fisher-Yates

L’algorithme de Fisher-Yates (aussi appelé Knuth shuffle) garantit une permutation équiprobable : chaque permutation des \(n!\) possibles a la même probabilité \(1/n!\) d’être générée.

Complexité : \(O(n^2)\) avec des files (car sélectionner le k-ième élément nécessite de défiler k éléments)